信息論與編碼

1、6.3線性分組碼分組碼的編碼包括兩個(gè)基本步驟首先將信源的輸出序列分為 k 位一組的信息組然后信道編碼器根據(jù)一定的編碼規(guī)則將 k 位信息組變換成n 個(gè)碼元的碼字，即(n，k)分組碼信息組和碼字用矩陣表示如下：信息組： k 位信息 碼字： n 個(gè)碼元 k 位信息位r = n - k 位校驗(yàn)位1通常對(duì)編碼器附加一個(gè)線性約束條件，使得碼字的校驗(yàn)位與信息位之間呈線性關(guān)系，這種碼稱為 (n, k ) 線性分組碼采用線性分組碼進(jìn)行信道編碼，就是給已知信息組按預(yù)定規(guī)則添加校驗(yàn)碼元以構(gòu)成碼字。在 k 個(gè)信息元之后附加 r = n - k 個(gè)校驗(yàn)碼元，使每個(gè)校驗(yàn)碼元是其中某些信息碼元的和 消息m (n , k)

2、碼字c m=(m1,m2 ,，mk) 分組編碼器 c=(c1,c2 ,cn) 2例：設(shè)信息分組長(zhǎng)度為k=3, m=(m1,m2,m3)，在每一信息組后加上 4 個(gè)校驗(yàn)碼元，構(gòu)成 (7,3) 線性分組碼設(shè)該碼的碼字為c=(c1,c2,c3,c4,c5,c6,c7) ，其中c1,c2,c3 為信息碼元，c4,c5,c6,c7為校驗(yàn)碼元，ci0,1；信息碼元和校驗(yàn)碼元可按右方的方程組計(jì)算：模 2 加(異或)3利用上式每給出一個(gè) 3 位的信息組，就可編出一個(gè)碼字，結(jié)果如下表所示線性方程組的后 4 個(gè)方程確定了由信息碼元得到校驗(yàn)碼元的規(guī)則，這 4 個(gè)方程稱為校驗(yàn)方程。由于所有碼字都按同一規(guī)則確定，因此又

3、稱為一致校驗(yàn)方程，所得到的校驗(yàn)碼元稱為一致校驗(yàn)碼元上述這種編碼方法稱為一致校驗(yàn)編碼。由于一致校驗(yàn)方程是線性的，亦即校驗(yàn)碼元和信息碼元間是線性運(yùn)算關(guān)系，所以由線性校驗(yàn)方程所確定的分組碼是線性分組碼消息碼字消息碼字000000 0000100100 1110001001 1101101101 0011010101 0111110110 1001011011 1010111111 010046.3.1線性分組碼的生成矩陣和一致校驗(yàn)矩陣在 (n, k ) 線性分組碼中，編碼器輸出的碼字可以由如下方程組來(lái)決定：如設(shè)：則方程組的矩陣表示為：c = mG所有滿足上式碼字(n 維向量)的全體構(gòu)成 (n, k)

4、 線性分組碼 C生成矩陣5生成矩陣 G 是一個(gè) k 行 n 列(n k)秩為 k 的矩陣，它 建立了消息向量m與碼字c的一一對(duì)應(yīng)關(guān)系，它起著編碼器的變換作用G 的每一行都是一個(gè)碼字，分別是 k 維消息向量組 1000, 01000, , 00010, 00001 所對(duì)應(yīng)的碼字其中：m 是任意 k 維消息向量運(yùn)算：模 2 加、模 2 乘6線性分組碼的生成矩陣的性質(zhì)設(shè) 是某個(gè)二元線性分組碼 的生成矩陣，則：n 維零向量 是一個(gè)碼字，稱為零碼字封閉性：任意兩個(gè)碼字的和仍是一個(gè)碼字，即：(n, k ) 線性分組碼實(shí)質(zhì)上是 n 維 n 長(zhǎng)向量構(gòu)成的線性空間中的一個(gè) k 維線性子空間 線性分組碼的任意一個(gè)

5、碼字均是生成矩陣 的行向量 的線性組合，即 ，存在一組不全為 0 的系數(shù) ，使得：7系統(tǒng)碼消息G1 碼字G2 碼字000000 000000 000001111 000001 101010110 101010 011011001 101011 110100101 011100 110101010 011101 011110011 110110 101 111100 110111 000生成矩陣 G 的選擇不是惟一的；如下面的G1 和 G2 都可作為同一個(gè) (6, 3) 碼的生成矩陣，所對(duì)應(yīng)的碼字如下表所示：8雖然二者用了不同形式的生成矩陣，卻都是 (6, 3) 線性分組碼，因此它們的檢錯(cuò)和糾錯(cuò)

6、能力是一樣的，但是 G2 生成的碼，其前 k 位與消息碼完全相同，等于把信息組m原封不動(dòng)搬到碼字的前k位，這種碼稱為系統(tǒng)碼，其余的n-k位叫冗余位或一致校驗(yàn)位，是前k個(gè)信息位的線性組合。其生成矩陣和一致校驗(yàn)矩陣分別記為 Gs , Hs系統(tǒng)碼的編碼器僅需存儲(chǔ) k (n - k) 個(gè)數(shù)字(非系統(tǒng)碼要存儲(chǔ) k n 個(gè)數(shù)字)，譯碼時(shí)僅需對(duì)前 k 個(gè)信息位糾錯(cuò)即可恢復(fù)信息；可見(jiàn)系統(tǒng)碼的編碼和譯碼比較簡(jiǎn)單，而性能與非系統(tǒng)碼一樣，所以系統(tǒng)碼得到了十分廣泛的應(yīng)用9線性分組碼的生成矩陣和一致校驗(yàn)矩陣的相互轉(zhuǎn)換系統(tǒng)碼的生成矩陣可用分塊矩陣表示為在系統(tǒng)碼字 c 中，前 k 位是信息位 m，后 r 位為碼字的校驗(yàn)位

7、q，并且 c = mGs，所以：即：q = mQkr 10H 矩陣的每一行都代表一個(gè)校驗(yàn)方程一致校驗(yàn)矩陣對(duì)于 2 進(jìn)制編碼mQkr + q = 011線性分組碼的生成矩陣和校驗(yàn)矩陣的關(guān)系由于 G 的每一行都是一個(gè)碼字，所以 G 的每一行 c i 都滿足：從而有： 12在碼字集合不變的前提下，給定任何一個(gè)線性分組碼，通過(guò)其生成矩陣 G 實(shí)施行初等變換，均可以轉(zhuǎn)換為某個(gè)系統(tǒng)碼13例6-2(6,3)線性分組碼，其生成矩陣是 G= 求：(1)計(jì)算碼集，列出信息組與碼字的映射關(guān)系。(2)將該碼系統(tǒng)化處理后，計(jì)算系統(tǒng)碼碼集并列出映射關(guān)系。(3)計(jì)算系統(tǒng)碼的校驗(yàn)矩陣H。若收碼r = 100110, 檢驗(yàn)它是

8、否為碼字？ (4)根據(jù)系統(tǒng)碼生成矩陣畫(huà)出編碼器電原理圖。 1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 14例6-2 碼集與映射關(guān)系信息 碼字 系統(tǒng)碼字000 000000 00000000101110100101101011000101011001110110001110110011101010011110110011110110011000101111000111101011011101015例6-2 二元(6,3)線性分組碼編碼器 m1m2m3 輸入 輸出 c4c5c616例： (7,3)線性分組碼下面利用校驗(yàn)矩陣來(lái)構(gòu)造(7，3)線性分組碼的編碼電路。設(shè)二元碼字

9、矢量為C=(c1,c2,c3,c4,c5,c6,c7)，而碼的監(jiān)督矩陣為17由 HC T= 0 T得： c4=c1+c3c5=c1+c2+c3c6=c1+c2c7=c2+c3 18根據(jù)上式可直接畫(huà)出(7,3)碼的并行編碼電路和串行編碼電路，如圖3所示。類似地，也可以利用生成矩陣來(lái)編碼。設(shè)信息組為M=(m1,m2,m3)，生成矩陣為19根據(jù) C=(c1,c2,c3,c4,c5,c6,c7)= MG，將M和G代入得：c1=m1c2=m3c3=m3c4=m1+m3=c1+c3c5=m1+m2+m3=c1+c2+c3c6=m1+m2=c1+c2c7=m2+m3=c2+c3 20 圖3 線性系統(tǒng)碼編碼電

10、路(a)并行編碼電路；(b)串行編碼電路216.3.2 伴隨式與標(biāo)準(zhǔn)陣列譯碼編碼器譯碼器線性分組碼用生成矩陣 G 編碼，用校驗(yàn)矩陣 H 譯碼：當(dāng)收到一個(gè)接收向量 R 后，檢驗(yàn)R 是否滿足校驗(yàn)方程 R H T = 0，若關(guān)系式成立，則認(rèn)為R 是一個(gè)碼字，否則判為碼字在傳輸中發(fā)生了錯(cuò)誤。因此 R H T 的值是否為 0 是接收向量出錯(cuò)與否的依據(jù)稱r (r = n-k) 維向量S =R HT 為(n,k)線性分組碼的 伴隨式S = R HT = ( C+E ) HT = CHT + EHT = 0 + EHT =EHT22伴隨式僅與差錯(cuò)圖案有關(guān)，與發(fā)送的具體碼字無(wú)關(guān)，它反映了信道被干擾的情況差錯(cuò)圖案

11、E是n重矢量，共有2n個(gè)可能的組合，而伴隨式S是(n-k)重矢量，只有2r個(gè)可能的組合.不同的差錯(cuò)圖案可以具有相同的伴隨式伴隨式是差錯(cuò)的判別式：若 S = 0，則接收向量是一個(gè)碼字,說(shuō)明傳輸過(guò)程中或者沒(méi)有發(fā)生差錯(cuò)，或者差錯(cuò)圖案恰為一個(gè)碼字；若 S 0 ，則傳輸過(guò)程中一定發(fā)生了差錯(cuò)23設(shè)接收向量為 譯碼器判接收向量 R無(wú)錯(cuò)，即傳輸中沒(méi)有發(fā)生錯(cuò)誤，發(fā)送碼字為：設(shè)某（7,4）線性分組碼的校驗(yàn)矩陣如右，發(fā)送碼字c=1 0 1 0 0 1 1,求接收向量r的伴隨式。R = 1 0 1 0 0 1 124假設(shè)接收向量中有一位發(fā)生差錯(cuò)，設(shè)接收向量為 由于 ， 譯碼器判定傳輸中有差錯(cuò)發(fā)生。又 (7, 4) 碼

12、是糾單個(gè)錯(cuò)誤的碼，且 等于 H 的第二列，因此判定接收碼字 r 的第二位是錯(cuò)的，糾正該位錯(cuò)誤后譯出發(fā)送碼字為：R = 1 1 1 0 0 1 125假設(shè)接收向量中發(fā)生了兩位差錯(cuò)，設(shè)接收向量為 ，且 是 H 的第 1 列和第 4 列的和，但與 H 中的任何一列均不相同，因此譯碼器無(wú)法判定差錯(cuò)發(fā)生在接收向量的哪些位置，此時(shí)只能發(fā)現(xiàn)差錯(cuò)，不能糾正差錯(cuò)R = 0 0 1 1 0 1 126一般而言，譯碼時(shí)需要由接收向量R來(lái)確定發(fā)送碼字 C，若能確定差錯(cuò)圖案 E，就可以得到發(fā)送碼字 C的估計(jì)值 ：因此，譯碼的關(guān)鍵是確定差錯(cuò)圖案E。根據(jù)伴隨式 S 確定差錯(cuò)圖案 E，再由上式得到譯碼估計(jì)值 ，這種譯碼方法稱

13、為伴隨式譯碼由于S = RHT 是一個(gè)含有 r = n-k 個(gè)方程的線性方程組，欲從中解出 e 的 n 個(gè)分量，得不到唯一解；通常的做法是，在所有解中，選碼字重量最小者作為 E，因?yàn)镋 = R +C，E 的碼字重量最小意味著接收向量R與發(fā)送碼字C 的漢明距離最小C= R + E27標(biāo)準(zhǔn)陣列譯碼表上述的概率譯碼，如每接收一個(gè)碼R就要解一次線性方程，那就太麻煩了。好在伴隨式S的數(shù)目是有限的2n-k個(gè)，如果n-k不太大，我們可以預(yù)先把不同S下的方程組解出來(lái)，把各種情況下的最大概率譯碼輸出列成一個(gè)碼表。這樣，在實(shí)時(shí)譯碼時(shí)就不必再去解方程，而只要象查字典那樣查一下碼表就可以了。這樣構(gòu)造的表格叫做標(biāo)準(zhǔn)陣列

14、譯碼表。 28對(duì)給定的(n，k)線性碼，將2n個(gè)n重矢量劃分為2k個(gè)子集的方法就是構(gòu)造所謂的“標(biāo)準(zhǔn)陣列”。方法如下：先將2k個(gè)碼字排成一行，作為“標(biāo)準(zhǔn)陣列”的第一行，并將全0碼字 C0(0,0,0)放在最左面的位置上；然后在剩下的2n2k個(gè)n重矢量中選取一個(gè)重量最輕的n重 E1放在全0碼字 C0的下面，再將 E1分別和碼字 C1，C2，C2k-1相加，放在對(duì)應(yīng)碼字下面構(gòu)成陣列第二行，在第二次剩下的n重矢量中，選取重量最輕的n重 E2，放在E1下面，并將E2分別加到第一行各碼字上，得到第三行，繼續(xù)這樣做下去，直到全部n重矢量用完為止，按上述方法構(gòu)造的標(biāo)準(zhǔn)陣列如表所示。29E0+C0= 0+0=

15、0E0+C1= C1E0+Ci= CiE1+C0= E1E1+CiEj+C0= EjEj+C1Ej+Ci 標(biāo)準(zhǔn)陣列譯碼表 E1+C1 S0 E0S1 E1 Sj Ej S2n-k-1 E2n-k-1 30陪集和子集譯碼表中有2n-k行，每行是一個(gè)陪集，每陪集的第一個(gè)元素(位于第一列)叫陪集首。同一陪集(同一行)中的所有元素對(duì)應(yīng)共同的一個(gè)伴隨式。第一行陪集的陪集首是全零伴隨式S0所對(duì)應(yīng)的全零差錯(cuò)圖案E0(無(wú)差錯(cuò))，而第j行陪集的陪集首是伴隨式Sj所對(duì)應(yīng)的重量最小的差錯(cuò)圖案Ej (C0=0, Rj=Ej)。譯碼表中有2k列，每列是一個(gè)子集，每子集的第一個(gè)元素(位于第一行)叫子集頭。同一子集(同一列

16、)中的所有元素對(duì)應(yīng)同一個(gè)碼字，第一列子集的子集頭是全零碼字C0，而第i列子集的子集頭是碼字Ci (E0=0, Ri=Ci) 。31例：已知校驗(yàn)矩陣： 若接收為： R= 0 0 0 0 0 1 1 ，試確定是否錯(cuò)誤，若接收錯(cuò)誤，試進(jìn)行糾錯(cuò)。解：計(jì)算伴隨式320 0 00 0 10 1 01 0 00 1 11 0 11 1 01 1 1誤碼位置無(wú)錯(cuò) C0 C1 C2 C3 C4 C5 C6S1 S2 S3錯(cuò)誤圖樣： E= 0 0 0 1 0 0 0 對(duì)照伴隨式與誤碼位置，確定錯(cuò)誤圖樣：33于是：C=R+E= 0 0 0 0 0 1 1 + 0 0 0 1 0 0 0 由于 ，當(dāng)只發(fā)生一位錯(cuò)碼時(shí)，

17、矩陣E中只有一個(gè)非零元素，與H的轉(zhuǎn)置相乘的結(jié)果是選出其中的一列，即校正子與H矩陣的哪一列相同，則該列即為碼元發(fā)生錯(cuò)誤的位置。 = 0 0 0 1 0 1 1 34例 6-3 一個(gè)(5,2)系統(tǒng)線性碼的生成矩陣是G = 設(shè)收碼R = (10101)，構(gòu)造標(biāo)準(zhǔn)陣列譯碼表，譯出發(fā)碼的估值解：(1)構(gòu)造標(biāo)準(zhǔn)陣列譯碼表。分別以信息組m= (00)、(01) 、(10)、(11)及已知的G求得4個(gè)許用碼字為C1 =(00000)、C2 = (10111) 、C3 = (01101)、C4 = (11010)。求出校驗(yàn)矩陣： H = 列出方程組：35例 6-3 譯碼表的構(gòu)成伴隨式有2n-k238種組合，差錯(cuò)

18、圖案中代表無(wú)差錯(cuò)的有一種，代表一個(gè)差錯(cuò)的圖案有 種，已有6種。代表兩個(gè)差錯(cuò)的圖案有 種。只需挑選其中的兩個(gè)，挑選方法可有若干種，不是唯一的。先將Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的線性方程組，解得對(duì)應(yīng)的Sj分別是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴隨式中，(011)所對(duì)應(yīng)的差錯(cuò)圖案是2k個(gè)即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最輕，任選其中一個(gè)如(00011)。同樣可得伴隨式(110)所對(duì)應(yīng)的最輕差錯(cuò)圖案之一

19、是(00110)。 36S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100例 6-3 標(biāo)準(zhǔn)陣列譯碼表37將接收碼R10101譯碼可選以下三種方法之一譯碼：直接搜索

20、碼表，查得(10101)所在列的子集頭是(10111)，因此譯碼輸出取為(10111)。先求伴隨式RHT = (10101) HT = (010) = S4，確定S4所在行，再沿著行對(duì)碼表作一維搜索找到(10101), 最后順著所在列向上找出碼字(10111)。先求出伴隨式RHT = (010) = S4并確定S4所對(duì)應(yīng)的陪集首(差錯(cuò)圖案)E4=(00010)，再將陪集首與收碼相加得到碼字C= R+ E4= (10101)+ (00010)= (10111)。 上述三種方法由上而下，查表的時(shí)間下降而所需計(jì)算量增大，實(shí)際使用時(shí)可針對(duì)不同情況選用。38對(duì)上例作進(jìn)一步分析，還可以看到，該(5,2)碼

21、的dmin=3。糾錯(cuò)能力是t = INT(3-1)/2 = 1。因此，譯碼陣列中只有前6行具有唯一性、可靠性，真正體現(xiàn)了最大似然譯碼準(zhǔn)則。而第7、8行的差錯(cuò)圖案(00011)和(00110)中包含兩個(gè)“1”，已超出了t= 1的糾錯(cuò)能力，譯碼已不可靠。比如，當(dāng)收碼R(10100)時(shí)，根據(jù)碼表譯出的碼字是(10111)，與收碼R的漢明距離是2，然而收碼R與全零碼字(00000)的漢明距離也是2，為什么不能譯成(00000)呢？事實(shí)上，碼表的第7、8行本身就不是唯一的。注意在碼表計(jì)算過(guò)程中，伴隨式(011)所對(duì)應(yīng)的4個(gè)差錯(cuò)圖案中有兩個(gè)并列重量最輕，如果當(dāng)時(shí)選的不是(00011)而是(10100)，那

22、么碼表第7行就不是現(xiàn)在這樣了。 39例：已知(6,3)線性分組碼的生成矩陣為求它的標(biāo)準(zhǔn)陣列。解：由生成矩陣可得該碼許用碼組的全部碼字：消息碼線性分組碼消息碼線性分組碼00000000010010011000100110110110101101001001111011010101101111011111100040則它的標(biāo)準(zhǔn)陣列為：00000000110101001101111010011010101111010111100000000100110001001001111110011110101011010011100100001000010000100001000010000010000100

23、111100100100010101110110110110110001000101011101101100001111001111001001110001101001011000111011111011111110010010001010111011011000011000011110100110111110001111101101010100101011011111000111110110010100101101010011101011110011000010100001100001100141在信道編碼中，定義碼字中非零碼元(“1”)的數(shù)目為碼字的漢明(Hamming)重量，或碼組重量、

24、碼字重量，簡(jiǎn)稱重。例如“010”碼字的碼重為1，“011”碼字的碼重為2。非零碼字中，重量最小者稱為該碼的最小漢明重量。 顯然，不同碼字的漢明重量是不同的。把兩個(gè)碼字中對(duì)應(yīng)碼元位置上具有不同碼元的位數(shù)定義為兩碼字的漢明(Hamming)距離，或碼組距離，簡(jiǎn)稱碼距。在一種編碼中，任意兩個(gè)合法碼字(許用碼字)間距離的最小值，即碼字集合中任意兩碼字間的最小距離，稱為這一編碼的最小漢明(Hamming)距離，以dmin表示。6.3.3 碼距、糾錯(cuò)能力、MDC碼及重量譜 42對(duì)于二進(jìn)制編碼：碼重(weight)一個(gè)碼組中“1”的數(shù)目碼距(distance)兩個(gè)碼組之間對(duì)應(yīng)位置上1、0不同的位數(shù)，又叫漢明

25、(Hamming)距。10 1 1 0 碼重：301 1 0 0 2 距離：343用d(C1，C2)表示兩個(gè)n重C1、C2之間的漢明距離，則漢明距離有以下三個(gè)性質(zhì)：(1)對(duì)稱性：d( C1，C2)=d (C2，C1)；(2)非負(fù)性：d(C1，C2)0；(3)滿足距離三角不等式：d(C1，C2)d (C1，C3)+d (C3，C2)。44定理6.1 任何最小距離dmin的線性分組碼，其檢錯(cuò)能力為（ dmin-1）, 糾錯(cuò)能力t為逐一計(jì)算各個(gè)碼字之間的漢明距離是非常麻煩的。由于各個(gè)碼字之和滿足封閉性，兩個(gè)碼字之間漢明距離即為單個(gè)碼字的漢明重量！定理6.2 線性分組碼的最小距離等于碼集中非零碼字的最

26、小重量： dmin = min w (C i )C iC 及C i 0 45下面討論碼的檢錯(cuò)、糾錯(cuò)能力與最小碼距的數(shù)量關(guān)系。在一般情況下，對(duì)于分組碼有以下結(jié)論：(1)最小碼距與檢錯(cuò)能力的關(guān)系 檢測(cè)e個(gè)錯(cuò)碼，則要求最小碼距：dmine+1或者說(shuō)：若一種編碼的最小距離為dmin，則它最多能檢出(dmin-1)個(gè)錯(cuò)碼。46(2)最小碼距與糾錯(cuò)能力的關(guān)系 糾正t個(gè)錯(cuò)碼，則要求最小碼距為：dmin2t+1或者說(shuō)：若一種編碼的最小碼距為dmin，則它最多能糾正(dmin-1)/2個(gè)錯(cuò)碼。47(3)最小碼距與檢、糾錯(cuò)能力的關(guān)系糾正t個(gè)錯(cuò)碼，同時(shí)能檢測(cè)e(et)個(gè)錯(cuò)碼，則要求最小碼距為dmine+t+1, e

27、t這里所述能糾正t個(gè)錯(cuò)碼，同時(shí)能檢測(cè)e個(gè)錯(cuò)碼的含義，是指：當(dāng)錯(cuò)碼不超過(guò)t個(gè)時(shí)錯(cuò)碼能自動(dòng)予以糾正，而當(dāng)錯(cuò)碼超過(guò)t個(gè)時(shí)，則不可能糾正錯(cuò)誤，但仍可檢測(cè)e個(gè)錯(cuò)碼，這正是混合檢錯(cuò)、糾錯(cuò)的控制方式。48定理6.3 (n,k) 線性分組碼最小距離等于dmin的充要條件是：校驗(yàn)矩陣H中有（dmin-1)列線性無(wú)關(guān)。定理6.4 (n,k) 線性分組碼的最小距離必定小于等于 (n-k+1)，即：dmin (n-k+1) 49例： (7，4)線性碼H各列都不相同，任意2列之和不等于0，2列線性無(wú)關(guān)；任意2列之和一定等于矩陣中某一列，任意3列線性相關(guān)。所以該碼的最小距離為3，小于n-k +14。50(n,k)線性碼最

28、小距離dmin的上邊界是n-k +1。如果設(shè)計(jì)的一種(n,k)線性碼的dmin達(dá)到了n-k +1，就是達(dá)到了設(shè)計(jì)性能的極點(diǎn)。因此， dminn-k +1的碼稱為極大最小距離碼 (MDC Maximized minimum Distance Code)?？傮w的、平均的糾錯(cuò)能力不但與最小距離有關(guān)，而且與其余碼距或者說(shuō)與碼字的重量分布特性有關(guān)。51采用差錯(cuò)控制編碼后，在隨機(jī)信道中即使只能糾正(或檢測(cè))這種碼字中12個(gè)錯(cuò)誤，也可以使誤碼率下降幾個(gè)數(shù)量級(jí)。說(shuō)明，即使是簡(jiǎn)單的差錯(cuò)控制編碼也具有較大的實(shí)用價(jià)值。當(dāng)然，如在突發(fā)信道中傳輸，由于錯(cuò)碼是成串集中出現(xiàn)的，所以上述只能糾正碼字中1或2個(gè)錯(cuò)碼的編碼，其效

29、用就不像在隨機(jī)信道中那樣明顯了，需要采用更為有效的糾錯(cuò)編碼。526.3.4 完備碼(Perfect code) 任何一個(gè)二元(n,k)線性分組碼都有2n-k個(gè)伴隨式，假如該碼的糾錯(cuò)能力是t，則對(duì)于任何一個(gè)重量小于等于t的差錯(cuò)圖案，都應(yīng)有一個(gè)伴隨式與之對(duì)應(yīng)，也就是說(shuō)，伴隨式的數(shù)目滿足條件 上式稱作漢明限，任何一個(gè)糾t碼都應(yīng)滿足上述條件。 53某二元(n,k)線性分組碼能使等式 成立，即該碼的伴隨式數(shù)目不多不少恰好和不大于t個(gè)差錯(cuò)的差錯(cuò)圖樣的數(shù)目相等，相當(dāng)于在標(biāo)準(zhǔn)譯碼陣列中能將所有重量不大于t的差錯(cuò)圖案選作陪集首，而沒(méi)有一個(gè)陪集首的重量大于t，這時(shí)的校驗(yàn)位得到最充分的利用。這樣的二元(n,k)線性

30、分組碼稱為完備碼。 54漢明碼(Hamming Code)漢明碼是1950年由漢明提出的一種能糾正單個(gè)錯(cuò)誤(糾錯(cuò)能力t=1)的線性分組碼。它不僅性能好而且編譯碼電路非常簡(jiǎn)單，易于工程實(shí)現(xiàn)，因此是工程中常用的一種糾錯(cuò)碼。漢明碼不是指一個(gè)碼，而是代表一類碼。漢明碼的，既有二進(jìn)制的，也有非二進(jìn)制的。55漢明碼是一種特殊的(n，k，d)線性分組碼。對(duì)于二進(jìn)制的碼元，漢明碼的參數(shù)n，k和d分別為 碼長(zhǎng) 信息位數(shù) 監(jiān)督位數(shù) 最小距離 碼率 56漢明碼校驗(yàn)矩陣的構(gòu)成漢明碼的校驗(yàn)矩陣H具有特殊的性質(zhì)，能使編碼的構(gòu)造方法簡(jiǎn)化。一個(gè)(n,k)碼的校驗(yàn)矩陣H有n-k行和n列，二進(jìn)制時(shí)n-k個(gè)監(jiān)督碼元所能組成的非全0

31、列矢量總數(shù)是2n-k-1, 恰好和校驗(yàn)矩陣的列數(shù)n =2r-1相等。只要排列所有列，(按 m 位的 2 進(jìn)制數(shù)的自然順序從左到右排列(不包括全 0 列)，通過(guò)列置換將矩陣H轉(zhuǎn)換成系統(tǒng)形式，就可以進(jìn)一步得到相應(yīng)的生成矩陣G。 57例 6.4 構(gòu)造一個(gè) r =3的二元(7，4)漢明碼。解：先利用漢明碼的特性構(gòu)造一個(gè)(7，4)漢明碼的校驗(yàn)矩陣H，再通過(guò)列置換將它變?yōu)橄到y(tǒng)形式： 0 0 0 1 1 1 1 列置換 1 1 1 0 1 0 0 H = 0 1 1 0 0 1 1 0 1 1 1 0 1 0 = QT I3 1 0 1 0 1 0 1 1 1 0 1 0 0 1再得生成矩陣G為 1 0 0

32、 0 1 0 1 G = I4 Q = 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 58由于漢明碼的最小距離是3，故漢明碼能糾正一個(gè)隨機(jī)錯(cuò)誤或檢測(cè)兩個(gè)錯(cuò)誤,且碼的校驗(yàn)矩陣H中任意兩列線性無(wú)關(guān)。漢明碼的校驗(yàn)矩陣H由一切r(r=n-k)維非零二元向量排列而成，即H的列為所有非零的r維向量組成，所以H的各列在二元和之下是封閉的，一旦r給定，就可構(gòu)造出具體的(n，k)漢明碼。 59高萊（Golay）碼 是二進(jìn)制（23，12）線性碼，其最小距離dmin7，糾錯(cuò)能力t =3。是完備碼，因?yàn)闈M足等式 223-12 = 2048 = 在(23,12)碼上添加一位奇偶位即

33、得二進(jìn)制線性（24，12）擴(kuò)展高萊碼，其最小距離dmin8。 60循環(huán)碼是線性碼的一個(gè)子類。循環(huán)碼的最引人注目的特點(diǎn)有兩個(gè):一是，可以用反饋線性移位寄存器很容易地實(shí)現(xiàn)其編碼和伴隨式計(jì)算(普通的線性分組碼需要存儲(chǔ)碼字陣列)；二是，由于循環(huán)碼有許多固有的代數(shù)結(jié)構(gòu)，從而可以找到各種簡(jiǎn)單實(shí)用的譯碼方法。循環(huán)碼滿足下列循環(huán)移位特性：碼集C中任何一個(gè)碼字的循環(huán)移位仍是碼字。6.3.5 循環(huán)碼 61循環(huán)碼的多項(xiàng)式描述循環(huán)右移 i 位可得： 循環(huán)左移 i 位可得： 將一個(gè)碼字 的分量循環(huán)右移 1 位就可以得到碼字：將一個(gè)碼字 的分量循環(huán)左移 1 位就可以得到碼字：62消息碼字消息碼字000000 000010

34、0100 1110001001 1101101101 0011010010 0111110110 1001011011 1010111111 0100上表給出的 (7, 3) 分組碼的所有 8 個(gè)碼字在移位(左移或右移)之下是封閉的，此碼是一個(gè)循環(huán)碼循環(huán)碼的定義：線性分組碼的任意一個(gè)碼字任意循環(huán)移位后得到的碼字是封閉的(仍是許用碼字)可見(jiàn)左、右循環(huán)移位彼此等價(jià)的，在不引起混淆的情況下統(tǒng)稱為循環(huán)移位易證：對(duì)任意 i ( 0 i n -1 )，左、右循環(huán)移位滿足：63循環(huán)碼的多項(xiàng)式定義任意一個(gè)n維矢量C=(cn-1，cn-2，c1,c0)或者碼字C=cn-1cn-2 c1c0都可以用一個(gè)次數(shù)不超過(guò)

35、n-1的多項(xiàng)式惟一確定，即C(x)=cn-1xn-1+cn-2xn-2+c1x+c0 當(dāng)C是一個(gè)碼字時(shí)，C(x)稱為相應(yīng)碼字的碼/碼字多項(xiàng)式。對(duì)于二進(jìn)制碼，ci0,1, i = 0,，n-1。顯然，碼字C和碼字多項(xiàng)式C(x)是一一對(duì)應(yīng)的。因此任何一個(gè)(n,k)線性分組碼都可以等價(jià)地看作一類由2k個(gè)次數(shù)不超過(guò)n-1的多項(xiàng)式組成的集合。6465將式C(x)乘以x，再除以xn+1得：上式表明，碼字循環(huán)左移一次的碼多項(xiàng)式C(1)(x)是原碼多項(xiàng)式C(x)乘x再除以xn+1所得的余式。寫(xiě)作：C(1)(x)xC(x) mod(xn+1) 模運(yùn)算66由此可以推知，C(x)的i次循環(huán)移位C(i)(x)是C(x

36、)乘xi再除以xn+1所得的余式。即：C(i)(x)xiC(x) mod(xn+1) 循環(huán)碼的碼字的i次循環(huán)移位等效于將碼多項(xiàng)式乘xi后再模xn+1。上式揭示了(n，k)線性碼中碼字多項(xiàng)式與碼字循環(huán)移位之間的關(guān)系，它對(duì)循環(huán)碼的研究起著重要作用。67循環(huán)移一位：(cn-1cn-2 c1c0) (cn-2 c1c0 cn-1)循環(huán)移一位：C (x) =cn-1 xn-1+cn-2 xn-2+c1x +c0 C (1)(x) = cn-2 xn-1+cn-3 xn-2+c0 x +cn-1比較循環(huán)移位的前后，可用如下的多項(xiàng)式運(yùn)算來(lái)表達(dá)循環(huán)移位移1位：C (1) (x) = xC (x) mod(xn

37、 +1) 移2位：C (2) (x) = xC (1) (x) = x2C (x)mod(xn +1) 移n-1位：C(n-1)(x)= xC(n-2)(x) = xn-1C(x) mod(xn +1) 循環(huán)碼的循環(huán)移位68例如，(7，3)循環(huán)碼可由任一個(gè)碼字，比如0011101經(jīng)過(guò)循環(huán)移位，得到其他6個(gè)非0碼字；也可由相應(yīng)的碼多項(xiàng)式x4+x3+x2+1，乘以xi(i=1，2，6)，再模x7+1得到其他6個(gè)非0碼多項(xiàng)式。這個(gè)移位過(guò)程和相應(yīng)的多項(xiàng)式運(yùn)算如表所示。最后加上一個(gè)全0碼字，構(gòu)成碼字空間。69表 (7，3)循環(huán)碼的循環(huán)移位 70生成多項(xiàng)式C(x) =m(x) g(x) 碼多項(xiàng)式 信息多項(xiàng)式 生成多項(xiàng)式生成多項(xiàng)式不是唯一的；g(x)=x n-k + gn-k-1 x n-k-1+ g2 x2+ g1 x +1是(n-k)次的首一碼多項(xiàng)式 ，即(n-k)次項(xiàng)的系數(shù)為1 。g(x)一定是(xn+1)的因子。71校驗(yàn)多項(xiàng)式多項(xiàng)式xn+1可因式分解為xn+1g(x)h