信息論-基礎理論與應用：第九章 信道的糾錯編碼

1、1 信道編碼定理指出：在信息傳輸率小于信道容量的條件下，通過編碼可以使譯碼錯誤概率任意小，從而達到可靠通信。給出的結果只說明存在一種編碼方式。其誤碼率隨著碼長n的增長趨于任意小。證明是非構造性的，它沒有告訴我們如何構造實際上可實現(xiàn)的、具有上述性能的這類碼的方法。 信道編碼/糾錯編碼/差錯控制：就是為解決這一問題而產生的學科，它的目的是尋找在實際上易于實現(xiàn)且能達到有效而可靠通信的編譯碼方法。 第九章 信道的糾錯編碼2前向糾錯(FEC)：發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯能力的碼。接收端信道譯碼器對接收碼字進行譯碼，若傳輸中產生的差錯數(shù)目在碼的糾錯能力之內時，譯碼器對差錯進行定位并加以糾

2、正。反饋重發(fā)(ARQ)：用于檢測的糾錯碼在譯碼器輸出端只給出當前碼字傳輸是否可能出錯的指示，當有錯時按某種協(xié)議通過一個反向信道請求發(fā)送端重傳已發(fā)送的碼字全部或部分。9.1 差錯控制的基本方式3混合糾錯(HEC)：是FEC與ARQ方式的結合。發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼組，收端收到碼組后，檢查差錯情況，如果差錯在碼的糾錯能力以內，則自動進行糾正。如果信道干擾很嚴重，錯誤很多，超過了碼的糾錯能力，但能檢測出來，則經反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。信息反饋(IRQ)：也稱回程校驗方式。收端把收到 的數(shù)據(jù)，原封不動地通過反饋信道送回到發(fā)端，發(fā)端比較發(fā)的數(shù)據(jù)與反饋來的數(shù)據(jù)，從而發(fā)現(xiàn)錯誤，并且把錯

3、誤的消息再次傳送，直到發(fā)端沒有發(fā)現(xiàn)錯誤為止。4按糾正差錯的類型可分為糾正隨機錯誤的碼和糾正突發(fā)錯誤的碼；按碼的數(shù)學結構中校驗元和信息元的關系線性碼：編碼規(guī)則可以用線性方程表示；非線性碼：編碼規(guī)則不能用線性方程表示；按碼字的結構分系統(tǒng)碼：前 k 個碼元與信息碼組一致；非系統(tǒng)碼：沒有系統(tǒng)碼的特性。按碼字中每個碼元的取值可分為二進制碼和多進制碼。按碼是否具有循環(huán)性分類,糾錯碼可分為循環(huán)碼和非循環(huán)碼；9.2 糾錯編碼的分類及基本概念5按碼的結構中對信息序列的處理方式分為分組碼和卷積碼分組碼：編碼的規(guī)則僅局限于本碼組之內，本 碼組的校驗元僅和本碼組的信息元相關。 信息碼組由 k 個二進制碼元組成，共有

4、2k 個不同的信息碼組； 附加nk個碼元，每個校驗元取值與該信息碼組的k個碼元有關； 編碼器輸出長度 n； 碼字的數(shù)目共有 2k ； 這2k 個碼字的集合稱為 (n,k) 分組碼； 分組碼的每個碼字只取決于相應的信息碼組，編碼器是無記憶的，可用組合邏輯實現(xiàn)。卷積碼：本碼組的校驗元不僅和本碼組的信息元相關，而且還與本碼組相鄰的前 n1 個碼組的信息元相關。67(1) 數(shù)字通信系統(tǒng)工作原理數(shù)字通信系統(tǒng)模型信源：可以是人或機器（例如計算機、傳感器）；信源編碼器：將信源輸出變換成信息序列；調制器：把輸入的消息序列變換為適合于在實際信道中傳輸/存儲的信號波形；9.2.2 糾錯碼的基本概念及其糾錯能力8傳

5、輸信道/存儲媒介有線：實際的傳輸信道可能是光纜、電纜等有線信道；無線：高頻無線線路、衛(wèi)星中繼等無線信道；存儲媒介：媒介可以是磁帶、磁盤、光盤等；無論何種傳輸媒介，都受到不同性質的干擾：有線信道中的的脈沖干擾；無線信道中的噪聲和衰落；存儲媒介的缺損也被看做是脈沖干擾。解調器：其輸入信號一般是受到干擾的混合波形，解調器的任務就是從有用信號和干擾的混合波形中恢復有用的信號，這個過程與調制器的過程相反。由于干擾的作用，解調器的輸出信號不可避免地包含著差錯，差錯的多少不應超過系統(tǒng)所規(guī)定的數(shù)值。9(2) 通信系統(tǒng)的主要技術指標傳輸速率碼元：攜帶數(shù)據(jù)信息的信號單元。碼元傳輸速率/波特率/調制速率：每秒鐘通過

6、信道傳輸?shù)拇a元數(shù)。單位是波特(Bd)。比特率/比特傳輸速率：每秒鐘通過信道傳輸?shù)男畔⒘?。單位是比?秒(bit/s)。這兩種傳輸速率的定義不同，它們都是衡量系統(tǒng)傳輸能力的主要指標。二進制：每個碼元的信息含量為1比特，二進制的波特率與比特率在數(shù)值上是相等的。M進制：每一個碼元的信息含量為 log2M。如果碼元傳輸速率為 rs 波特，相應的比特率 rb 為rb = rs log2M (bit/s)10差錯率：差錯率是衡量傳輸質量的重要指標之一， 它有以下幾種不同的定義。碼元差錯率：指在傳輸?shù)拇a元總數(shù)中發(fā)生差錯的碼元數(shù)所占的比例（平均值），簡稱誤碼率。比特差錯率 /比特誤碼率：指在傳輸?shù)谋忍乜倲?shù)中發(fā)

7、生差錯的比特數(shù)所占的比例（平均值）。在二進制傳輸系統(tǒng)中，碼元差錯率就是比特差錯率。碼組差錯率：指在傳輸?shù)拇a組總數(shù)中發(fā)生差錯的碼組數(shù)所占的比例（平均值）。11(3) 采用信道編碼的數(shù)字通信系統(tǒng)在某些情況下，信道的改善可能較困難或者不經濟，這就要求采用信道編碼，以便滿足系統(tǒng)差錯率的技術指標要求。信道編碼為系統(tǒng)設計者提供了一個降低系統(tǒng)差錯率的措施。采用信道編碼后的數(shù)字通信系統(tǒng)可用下圖所示。12編碼信道：是研究糾錯編碼和譯碼的一種模型。如下圖所示。編碼信道無線通信中的發(fā)射機、天線、自由空間、接收機等的全體；有線通信中的如調制解調器、電纜等的全體；Internet 網的多個路由器、節(jié)點、電纜、底層協(xié)議等

8、的全體；信道編碼的基本思想和分類13二進制信道：當碼字 C 和接收向量 R 均由二元序列/向量表示時，稱編碼信道為二進制信道。C=(C0,C1,Cn-1), Ci0,1R=(R0,R1,Rn-1), Ci0,1 描述二進制信道輸入輸出關系或噪聲干擾程度的是轉移概率p(R/C)。無記憶二進制信道：對任意的n都有 則稱為無記憶二進制信道。14只要噪聲是白噪聲，大多數(shù)二進制傳輸信道的模型都可以等效為一個BSC信道。無記憶二進制對稱信道/BSC/硬判決信道：無記憶二進制信道的轉移概率又滿足 p(0/1)=p(1/0)，稱為無記憶二進制對稱信道。如下圖所示。15信道編碼的基本思想信道編碼的對象：是信源編

9、碼器輸出的信息序列m。 通常是二元符號1、0組成的序列。信道編碼的基本思想按一定規(guī)則給數(shù)字序列m增加一些多余的碼元，使不具有規(guī)律性的信息序列 m 變換為具有某種規(guī)律性的數(shù)碼序列 C；碼序列中的信息序列碼元與多余碼元之間是相關的；信道譯碼器利用這種預知的 編碼規(guī)則譯碼。檢驗接收到的數(shù)字序列 R 是否符合既定的 規(guī)則，從而發(fā)現(xiàn) R 中是否有錯，或者糾正其中的差錯；根據(jù)相關性來檢測/發(fā)現(xiàn)和糾正傳輸過程中產生的差錯就是信道編碼的基本思想。16碼元的組成及其它們之間的關系信息碼組：數(shù)字序列 m 總是以 k 個碼元為一 組傳輸，稱這k 個碼元的碼組為信息碼組。碼組/碼字：信道編碼器按一定的規(guī)則對每個信息碼

10、組附加一些多余的碼元，構成了 n 個碼元的碼組。碼組的 n 個碼元之間是相關的，附加的 (nk) 個多余碼元為何種符號序列與待編碼的信息碼組有關。校驗碼元/校驗元：附加的 (nk) 個碼元稱為該碼組的校驗碼元或校驗元。17可靠性與帶寬、速度的關系從信息傳輸?shù)慕嵌?，校驗元不載有任何信息，所 以是多余的。這種多余度使碼字具有一定的糾錯和檢錯能力，提高了傳輸?shù)目煽啃裕档土苏`碼率；如果要求信息傳輸速度不變，在附加了校驗元后必須減小碼組中每個碼元符號的持續(xù)時間，對二進制碼，就是要減小脈沖寬度；若編碼前每個碼脈沖的歸一化寬度為1，則編碼后的歸一化寬度為 k/n (kn,k/nk) 碼字，其中 (nk)

11、個附加碼元是由信息碼元的線性運算產生的。信息碼組長 k 位，有 2k 個不同的信息碼組，則有 2k 個碼字與它們一一對應。9.3線性分組碼28名詞解釋線性分組碼：通過預定的線性運算將長為 k 位的信息碼組變換成 n 重的碼字 (nk)。由 2k 個信息碼組所編成的 2k個碼字集合，稱為線性分組碼。碼矢：一個 n 重的碼字可以用矢量來表示C=(Cn1,Cn1,C1,C0 ) 所以碼字又稱為碼矢。(n,k) 線性碼：信息位長為 k，碼長為 n 的線性碼。編碼效率/編碼速率/碼率/傳信率：R=k /n。它說明了信道的利用效率，R是衡量碼性能的一個重要參數(shù)。29(1) 一致校驗方程編碼就是給已知信息碼

12、組按預定規(guī)則添加校驗碼元，以構成碼字。在 k 個信息碼元之后附加 r(r=nk) 個校驗碼元，使每個校驗元是其中某些信息元的模2和。舉例：k=3, r=4，構成 (7,3) 線性分組碼。設碼字為(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4為信息元，C3,C2,C1,C0為校驗元，每個碼元取“0”或“1”校驗元可按下面方程組計算一致校驗方程和一致校驗矩陣30一致校驗方程：確定信息元得到校驗元規(guī)則的一組方程稱為校驗方程。由于所有碼字都按同一規(guī)則確定，又稱為一致校驗方程。由于一致校驗方程是線性的，即校驗元和新信源之間是線性運算關系，所以由線性校驗方程所確定的分組碼是線性分組碼。31(

13、2) 舉例信息碼組 (101)，即C6=1, C5=0, C4=1代入 (9.18) 得： C3=0, C2=0, C1=1, C0=1由信息碼組 (101) 編出的碼字為 (1010011)。其它7個碼字如表9.1。32(3) 一致校驗矩陣為了運算方便，將校驗方程寫成矩陣形式，得可寫成 H CT=0T或 C HT=0 CT、HT、0T分別表示C、H、0的轉置矩陣。33系數(shù)矩陣 H 的后四列組成一個 (44) 階單位子陣， 用 I4 表示，H 的其余部分用 P 表示34推廣到一般情況：對 (n,k) 線性分組碼，每個 碼字中的 r(r=nk) 個校驗元與信息元之間的關系可由下面的線性方程組確定

14、35令上式的系數(shù)矩陣為 H，碼字行陣列為 C36(4) 一致校驗矩陣特性對H 各行實行初等變換，將后面 r 列化為單位子陣，于是得到下面矩陣，行變換所得方程組與原方程組同解。校驗矩陣H 的標準形式：后面 r 列是一單位子陣的校驗矩陣H。H 陣的每一行都代表一個校驗方程，它表示與該行中“1”相對應的碼元的模2和為0。37線性分組碼的生成矩陣在由 (n,k) 線性碼構成的線性空間 Vn 的 k 維子空間中， 一定存在 k 個線性獨立的碼字：g1,g2, gk,。碼 CI 中其它任何碼字C都可以表為這 k 個碼字的一種線性組合，即38G中每一行 gi=(gi1,gi2, gin ) 都是一個碼字；對

15、每一個信息組m，由矩陣G都可以求得 (n,k) 線性碼對應的碼字。生成矩陣：由于矩陣 G 生成了 (n,k) 線性碼，稱矩陣 G 為 (n,k) 線性碼的生成矩陣。(n,k) 線性碼的每一個碼字都是生成矩陣 G 的行矢量的線性組合，所以它的 2k 個碼字構成了由 G 的行組成的 n 維空間的一個 k 維子空間 Vk。39線性系統(tǒng)分組碼 通過行初等變換，將 G 化為前 k 列是單位子陣 的標準形式 40線性系統(tǒng)分組碼：用標準生成矩陣 Gkn 編成的碼字，前面 k 位為信息數(shù)字，后面 r=nk 位為校驗字，這種信息數(shù)字在前校驗數(shù)字在后的線性分組碼稱為線性系統(tǒng)分組碼。當生成矩陣 G 確定之后，(n,

16、k) 線性碼也就完全被確定了，只要找到碼的生成矩陣，編碼問題也同樣被解決了。41舉例 (7,4) 線性碼的生成矩陣為42生成矩陣與一致校驗矩陣的關系由于生成矩陣G的每一行都是一個碼字，所以G 的每行都滿足HrnCTn1=0Tr1，則有HrnGTnk=0Trk 或 GknHTnr=0kr線性系統(tǒng)碼的校驗矩陣 H 和生成矩陣 G 之間可以直接互換。43舉例 已知(7,4)線性系統(tǒng)碼的校驗矩陣為44對偶碼對偶碼：對一個(n,k)線性碼 CI，由于HrnGTnk=0Trk，如果以G 作校驗矩陣，而以H 作生成矩陣，可構造另一個碼CId，碼CId是一個(n,nk)線性碼，稱碼CId為原碼的對偶碼。例如：

17、 (7,4)線性碼的對偶碼是(7,3)碼：(7,3)碼的校驗矩陣H(7,3)是(7,4)碼生成矩陣G(7,4) 45(7,3) 碼的生成矩陣 G(7,3) 是 (7,4) 碼校驗矩陣 H(7,4) 46(n,k) 線性碼的編碼就是根據(jù)線性碼的校驗矩陣或生成矩陣將長為 k 的信息組變換成長為 n(nk) 的碼字。利用校驗矩陣構造 (7,3) 線性分組碼的編碼電路：設碼字矢量為C=(C6 C5C4C3C2C1C0)碼的校驗矩陣為線性分組碼的編碼47根據(jù)方程組可直接畫出 (7,3) 碼的并行編碼電路及串行編碼電路，如圖。48設某二元碼為C=11100，01001，10010，00111，碼組間的最小

18、距離為 ，此碼最多能發(fā)現(xiàn) 個獨立隨機錯誤，或者最多能糾正 個獨立隨機錯誤。若采用最小距離譯碼準則，則接收序列10000譯為 ， 01100譯為 ，00100譯為 。 499.3.3 漢明碼 常見的線形分組碼有重復碼，漢明碼，里德-穆勒碼，戈雷碼（1）漢明碼的構造和譯碼 漢明碼是漢明于1950年提出的糾一個錯誤的線性碼，也是第一個糾錯碼。由于它編碼簡單，因而是在通信系統(tǒng)和數(shù)據(jù)存儲系統(tǒng)中得到廣泛應用的一類線性碼。50漢明碼的結構參數(shù)：糾一個錯誤的線性碼，其最小距離 dmin=3 ；監(jiān)督矩陣任意兩列線性無關/ H 的任兩列互不相同；沒有全0的列。監(jiān)督元個數(shù) nk=r；H 陣中每列有 r 個元素，至多可構成 2r1種互不相同的非0列。對于任意正整數(shù) r3，漢明碼的結構參數(shù)為碼長： n=2r1信息位數(shù)： k=2rr1監(jiān)督位數(shù)： r= nk碼的最小距離：