信息論與編碼第八章 糾錯(cuò)編碼

1、第八章第八章 糾錯(cuò)編碼糾錯(cuò)編碼白慧慧辦公地址：9號教學(xué)樓北605Email: 手機(jī)容提要n一、糾錯(cuò)碼的基本概念n二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)n三、線性分組碼n四、循環(huán)碼n五、卷積碼內(nèi)容提要一、糾錯(cuò)碼的基本概念一、糾錯(cuò)碼的基本概念n二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)n三、線性分組碼n四、循環(huán)碼n五、卷積碼1.信道糾錯(cuò)編碼一、糾錯(cuò)碼的基本概念一、糾錯(cuò)碼的基本概念2. 差錯(cuò)控制系統(tǒng)模型及分類一、糾錯(cuò)碼的基本概念一、糾錯(cuò)碼的基本概念2. 差錯(cuò)控制系統(tǒng)模型及分類一、糾錯(cuò)碼的基本概念一、糾錯(cuò)碼的基本概念2. 差錯(cuò)控制系統(tǒng)模型及分類一、糾錯(cuò)碼的基本概念一、糾錯(cuò)碼的基本概念2. 差錯(cuò)控制系統(tǒng)模型及分類

2、一、糾錯(cuò)碼的基本概念一、糾錯(cuò)碼的基本概念2. 差錯(cuò)控制系統(tǒng)模型及分類一、糾錯(cuò)碼的基本概念一、糾錯(cuò)碼的基本概念3. 差錯(cuò)類型一、糾錯(cuò)碼的基本概念一、糾錯(cuò)碼的基本概念3. 差錯(cuò)類型一、糾錯(cuò)碼的基本概念一、糾錯(cuò)碼的基本概念4. 糾錯(cuò)碼的分類一、糾錯(cuò)碼的基本概念一、糾錯(cuò)碼的基本概念4. 糾錯(cuò)碼的分類一、糾錯(cuò)碼的基本概念一、糾錯(cuò)碼的基本概念內(nèi)容提要n一、糾錯(cuò)碼的基本概念二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)n三、線性分組碼n四、循環(huán)碼n五、卷積碼近世代數(shù)簡介n近世代數(shù)又稱抽象代數(shù)，其研究對研究對象是定義在某些運(yùn)算下的集合象是定義在某些運(yùn)算下的集合，運(yùn)算對象可以是數(shù)、多項(xiàng)式、矢量、矩陣、線性空間等。

3、n編碼理論是建立在碼的代數(shù)結(jié)構(gòu)基礎(chǔ)上的，為便于初學(xué)者理解，我們將簡單介紹抽象代數(shù)中與編碼直接相關(guān)的基礎(chǔ)知識，主要涉及整數(shù)及多項(xiàng)式的一些基本概念及群、環(huán)、群、環(huán)、域域的基本知識。二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)1. 群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)整數(shù)的相關(guān)概念整數(shù)的相關(guān)概念1. 群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)1. 群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群的定義群的定義1. 群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)n在實(shí)數(shù)加法下整數(shù)集是一個(gè)交換群。在這種情況下，整數(shù)0是單位元，整數(shù)-i是整數(shù)i的逆元。除去0的有理數(shù)集合在實(shí)數(shù)乘法下是交換群。

4、整數(shù)1是關(guān)于實(shí)數(shù)乘法的單位元，有理數(shù)b/a是a/b的乘法逆元。1. 群n這樣的二元運(yùn)算稱為模2(modulo-2)加法。集合G=0,1在模2加法下是一個(gè)群。由模2加法 的定義，G在 下是封閉的，同時(shí) 滿足交換律、結(jié)合律。元素0是單位元，0的逆元是它本身，1的逆元也是它本身。這樣，定義了 的G是一個(gè)交換群。二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)模模2加加1. 群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)1. 群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)1. 群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)1. 群n令p為一個(gè)素?cái)?shù)(例如p=2,3,5,7,11,)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、

5、糾錯(cuò)編碼的代數(shù)基礎(chǔ)模模p乘乘n易驗(yàn)證模p乘法滿足交換律和結(jié)合律，其單位元是1。G中任何元素i關(guān)于模p乘法都有逆元。n群G=1,2,3,p-1在模p乘法下稱為乘群 (multiplication group)1. 群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)模模p乘乘1. 群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群的同構(gòu)群的同構(gòu)1. 群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群的同構(gòu)群的同構(gòu)1. 群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)子群子群1. 群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)子群子群1. 群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群的陪集群的陪集1. 群

6、二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群的陪集分解群的陪集分解1. 群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群的陪集分解群的陪集分解2. 域二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)域的定義域的定義2. 域二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群和域的區(qū)別群和域的區(qū)別n需要指出群(G)與域(F)的區(qū)別：n一個(gè)群只有規(guī)定的一種代數(shù)運(yùn)算(加法或乘法)，n而域是有兩種代數(shù)運(yùn)算(加法和乘法)的代數(shù)系統(tǒng)。2. 域二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群和域的區(qū)別群和域的區(qū)別2. 域二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)素?cái)?shù)域素?cái)?shù)域G(p)2. 域二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、

7、糾錯(cuò)編碼的代數(shù)基礎(chǔ)素?cái)?shù)域素?cái)?shù)域G(p)3. 環(huán)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)多項(xiàng)式的相關(guān)概念多項(xiàng)式的相關(guān)概念3. 環(huán)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)多項(xiàng)式的相關(guān)概念多項(xiàng)式的相關(guān)概念3. 環(huán)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)環(huán)的定義環(huán)的定義3. 環(huán)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)整數(shù)剩余類環(huán)整數(shù)剩余類環(huán)3. 環(huán)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)多項(xiàng)式剩余類環(huán)多項(xiàng)式剩余類環(huán)3. 環(huán)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)內(nèi)容提要n一、糾錯(cuò)碼的基本概念n二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)三、線性分組碼三、線性分組碼n四、循環(huán)碼n五、卷積碼1. 分組碼

8、相關(guān)定義三、線性分組碼三、線性分組碼n假設(shè)信源信息是二進(jìn)制數(shù)字序列，將信道編碼器的輸出序列構(gòu)成長度為n的段，記為C C=c1,c2,cn 設(shè)有m個(gè)不同的信息序列，每個(gè)不同的序列由k(kn)位相繼的信息數(shù)字組成。由于每個(gè)信息序列組成k位二進(jìn)制數(shù)字，則有2k個(gè)可能不同的信息序列，即m=2k，這2k個(gè)碼字的集合稱為(n,k)分組碼。(n,k)分組碼定義分組碼定義1.分組碼相關(guān)定義n對于2k個(gè)n長碼字全體構(gòu)成的分組碼，其碼字中的k位稱為信息位，n-k位稱為校驗(yàn)位或監(jiān)督位。n例如，當(dāng)k=3，n=7時(shí)，可能的消息序列數(shù)m=2k=8個(gè)，可能的長為n=7的預(yù)選序列有27=128個(gè)。具體如表：n對于所選定的n長

9、序列稱為允許使用序列，即碼字；而其他序列則是不允許使用的，即禁用序列。n該例中，信息位為3，碼長為7，監(jiān)督位為4，如果用R=k/n表示碼字中信息位所占比重，稱為編碼效率。表明了信道的利用率。三、線性分組碼三、線性分組碼消息序列碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100校驗(yàn)位和信息位校驗(yàn)位和信息位1.分組碼相關(guān)定義n若(n,k)分組碼中k個(gè)信息位同原始k個(gè)信息位相同，且位于n長碼字的前(或后)k位，而校驗(yàn)位位于其后(或前)，則稱該分組碼為系統(tǒng)碼，否則為非系統(tǒng)碼。n右表所示為系

10、統(tǒng)碼。三、線性分組碼三、線性分組碼消息序列碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100系統(tǒng)碼與非系統(tǒng)碼系統(tǒng)碼與非系統(tǒng)碼n定義：定義：n, k線性分組碼是GF(q)上的n維線性空間中的一個(gè)k維子空間。2k2n2. 線性分組碼定義三、線性分組碼三、線性分組碼2. 線性分組碼定義三、線性分組碼三、線性分組碼n也可以這樣理解：n長碼字C=c1,c2,cn中每一位同原始的k個(gè)信息位d=d1,d2,dk之間滿足一定的函數(shù)關(guān)系ci=f(d1,d2,dk), (n=1,2,n) 若函數(shù)關(guān)系是

11、線性的，則稱該分組碼為線性分組碼，否則為非線性分組碼。2. 線性分組碼定義三、線性分組碼三、線性分組碼2. 線性分組碼定義三、線性分組碼三、線性分組碼2. 線性分組碼定義三、線性分組碼三、線性分組碼n容易驗(yàn)證C是線性的。假設(shè)消息序列與碼字序列的映射關(guān)系為如下兩種：n第一種： 映射關(guān)系為：n第二種： 映射關(guān)系與第一種截然不同。三、線性分組碼三、線性分組碼2. 線性分組碼定義三、線性分組碼三、線性分組碼3. 線性分組碼編碼消息序列碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100三、線

12、性分組碼三、線性分組碼3. 線性分組碼編碼n由校驗(yàn)方程，可將n=7，k=3的線性分組碼寫成6655443642654165054ccccccccccccccccccc654,mc c c100111001001110011101G令則因此，C=mG且 G=Ik Pk*(n-k)三、線性分組碼三、線性分組碼3. 線性分組碼編碼令則因此，C=mG三、線性分組碼三、線性分組碼3. 線性分組碼編碼三、線性分組碼三、線性分組碼3. 線性分組碼編碼三、線性分組碼三、線性分組碼3. 線性分組碼編碼消息序列碼字00000000000010011101010010011101101110101001001110

13、1011010011110110100111111101001011000111010011000100110001H三、線性分組碼三、線性分組碼3. 線性分組碼編碼n生成矩陣和校驗(yàn)矩陣關(guān)系生成矩陣和校驗(yàn)矩陣關(guān)系*()kkn kGIP()*Tn kkn kHPI100111001001110011101G1011000111010011000100110001H例題111001111101P100111001001110011101GTQP已知生成矩陣為求其校驗(yàn)矩陣H，如果將H作為生成矩陣，則所生成的碼字是什么？由于G=Ik Pk*(n-k)則有又因?yàn)?01100011101001100010

14、0110001HQI100111001001110011101G由生成矩陣生成的(7,3)碼為：mC00000000000010011101010010011101101110101001001110101101001111011010011111110100把校驗(yàn)矩陣當(dāng)作生成矩陣，mC000000000000001000101100100010110001100111010100010011101010101100011001100010111011101010001000101100110011101010101001110111011000110011000101101110100111

15、101110100111111111111011000111010011000100110001H產(chǎn)生(7,4)碼為：1000101010011100101100001011H（n，k）線性分組碼編碼電路6655443642654165054ccccccccccccccccccc4. 伴隨式與譯碼4. 伴隨式與譯碼4. 伴隨式與譯碼n證明：根據(jù)線性分組碼的封閉性可知，任意兩個(gè)碼字的和應(yīng)為一個(gè)碼字。根據(jù)碼字之間距離的定義可知，兩個(gè)碼字和的非零個(gè)數(shù)則與其距離相等，且又為新碼字的重量。所以，不難理解，線性分組碼的最小距離必定等于非零碼字的最小重量。4. 伴隨式與譯碼 設(shè)設(shè)C是線性分組碼，是線性分組碼

16、，H是它的校驗(yàn)矩陣，那么碼是它的校驗(yàn)矩陣，那么碼C的最小重量就等的最小重量就等于于H中線性相關(guān)的最小列數(shù)。因此，如果中線性相關(guān)的最小列數(shù)。因此，如果H中的中的2t個(gè)和小于個(gè)和小于2t個(gè)列個(gè)列的任一子集都線性無關(guān)，而的任一子集都線性無關(guān)，而H中有中有2t+1個(gè)列線性相關(guān)，那么碼個(gè)列線性相關(guān)，那么碼C就就是糾正是糾正t個(gè)錯(cuò)誤的糾錯(cuò)碼，或能檢出個(gè)錯(cuò)誤的糾錯(cuò)碼，或能檢出2t個(gè)錯(cuò)誤的檢錯(cuò)碼。個(gè)錯(cuò)誤的檢錯(cuò)碼?！纠浚ā纠浚?，4）線性分組碼）線性分組碼100101101011010011110HH的前的前3列相加等于列相加等于0，因此，因此H線性相關(guān)的最小列數(shù)為線性相關(guān)的最小列數(shù)為3故：故：wmin(C

17、)=3例：某一個(gè)例：某一個(gè)(5,2)系統(tǒng)線性碼的生成矩陣是系統(tǒng)線性碼的生成矩陣是 設(shè)接收到碼字是設(shè)接收到碼字是r=(10101)，先構(gòu)造該碼的標(biāo)準(zhǔn)陣，先構(gòu)造該碼的標(biāo)準(zhǔn)陣列譯碼表，然后譯出發(fā)碼的估值列譯碼表，然后譯出發(fā)碼的估值C。1 0 1 1 01 1 1 0 1G(1)(1)信息組：信息組：m=(00),(10),(01),(11)m=(00),(10),(01),(11)(2)(2)求得求得4 4個(gè)許用碼字個(gè)許用碼字C=mGC=mG為為 C C1 1=(00000),C=(00000),C2 2=(10111=(10111 ),), C C3 3=(01101), C=(01101), C

18、4 4=(11010) =(11010) (3)(3)求出校驗(yàn)矩陣求出校驗(yàn)矩陣 1 1 1 0 01 0 0 1 01 1 0 0 1H1 0 1 1 01 1 1 0 1G(4)求出伴隨式求出伴隨式1 1 1 0 010101 1 0 0 1 01 1 0 0 111110110101010100010001TTSrH(5)標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列S1=000E1+ C1=00000C2=10111C3=01101C4=11010S2=111E2=10000001111110101010S3=101E3=01000111110010110010S4=100E4=0010010011010011111

19、0S5=010E5=00010101010111111000S6=001E6=00001101100100111011S7=011E7=00011101000111011001S8=110E8=00110100010101111100選擇重量最小的n重作為陪集首S=EHT111101100010001TH【例【例】（7，3）線性分組碼）線性分組碼101110011100100111001G1000110010001100101110001101H00101110101110110010110010110111001111001010111000000000c4)(minCw31minttd11

20、2minttd能檢出能檢出3重錯(cuò)誤，糾正重錯(cuò)誤，糾正1重錯(cuò)誤。重錯(cuò)誤。0111101r如：如： （一個(gè)錯(cuò)）（一個(gè)錯(cuò)）11101000000011101000001101001000010000001000010000001000010000001000010000001seTTrH)0111(10111101000110010001100101110001101)0011101()0100000()0111101(erc如兩個(gè)錯(cuò)：如兩個(gè)錯(cuò)：1111101r0)1001(TTrH，但無伴隨式與之對應(yīng)，不能糾正。，但無伴隨式與之對應(yīng)，不能糾正。n例例 已知（7，3）碼的校驗(yàn)矩陣為101100011

21、1010011000100110001Hn若錯(cuò)誤圖樣en =（0010000），則00101100011110100()0110001000110001010101Tn TSHe 是是H矩陣第三列！矩陣第三列！若錯(cuò)誤圖樣中只有一個(gè)分量非零，則ST是H矩陣相應(yīng)的列，因而能夠糾正單個(gè)錯(cuò)誤！n若錯(cuò)誤圖樣en =（0010100），則001011000101111010011()01100010001011010000011100Tn TSHe 是是H矩陣第三列與第矩陣第三列與第五列之和！五列之和！由定義可以求得， rn的伴隨式：是是H矩陣第一列與第矩陣第一列與第二列之和！二列之和！111011000

22、100111010011()01100010110011010001011000Tn TSHe 若發(fā)生兩個(gè)錯(cuò)誤，譯碼器只能判決傳輸有錯(cuò)（ en 0 ）,不能判定由哪幾位錯(cuò)誤引起！漢明碼：漢明碼：一類能糾單個(gè)錯(cuò)誤的糾錯(cuò)碼。一類能糾單個(gè)錯(cuò)誤的糾錯(cuò)碼?！纠纠浚?，4）線性碼）線性碼100101101011010011110H1h2h3h4h5h6h0h5. 漢明碼（1）H中列為非全零元素；中列為非全零元素；（2）H中任意兩列都不相同，但存中任意兩列都不相同，但存 在相加等于在相加等于0的三個(gè)列的子集。的三個(gè)列的子集。0120hhhH中線性相關(guān)的最小列數(shù)為中線性相關(guān)的最小列數(shù)為3，故，故 ，該碼是

23、糾單個(gè)，該碼是糾單個(gè)錯(cuò)誤的碼。錯(cuò)誤的碼。3)(minminCwd定理：定理：C是一個(gè)線性分組碼，是一個(gè)線性分組碼，H是校驗(yàn)矩陣，是校驗(yàn)矩陣，C是可以糾單個(gè)錯(cuò)誤的糾錯(cuò)是可以糾單個(gè)錯(cuò)誤的糾錯(cuò)碼的充要條件：碼的充要條件：（1）H中沒有元素全為中沒有元素全為0的列矢量；的列矢量；（2）H中任意兩個(gè)列矢量都不相同。中任意兩個(gè)列矢量都不相同。100101101011010011110H0h1h2h3h4h5h6h幾個(gè)結(jié)論：幾個(gè)結(jié)論：對于具有糾單個(gè)錯(cuò)誤能力的線性分組碼。對于具有糾單個(gè)錯(cuò)誤能力的線性分組碼。（1）若接收矢量的伴隨式）若接收矢量的伴隨式 ，則譯碼器認(rèn)為接收矢量沒有錯(cuò)誤；，則譯碼器認(rèn)為接收矢量沒有

24、錯(cuò)誤；0s （2）如果）如果 ，且，且 等于等于H矩陣中的某一列，則譯碼器糾認(rèn)為接矩陣中的某一列，則譯碼器糾認(rèn)為接收矢量在該列對應(yīng)校驗(yàn)矩陣中的位置出錯(cuò)，此時(shí)只需將接收字該收矢量在該列對應(yīng)校驗(yàn)矩陣中的位置出錯(cuò)，此時(shí)只需將接收字該位置的碼元取反就能糾錯(cuò)；位置的碼元取反就能糾錯(cuò)；Ts0Ts（3）若）若 ，但不等于，但不等于H中的任一列，則錯(cuò)誤不能糾正。中的任一列，則錯(cuò)誤不能糾正?！纠纠?01000111011001110101011100011111000H)101000101 (r（1）0s 00011101000101101000111011001110101011100011111000T

25、TrHs伴隨式對應(yīng)于伴隨式對應(yīng)于H中的第五列，故：中的第五列，故：) 101010101 (erc) 101000100(r0)1101(s（2）H中無對應(yīng)列與之對應(yīng)，不能正確譯碼。中無對應(yīng)列與之對應(yīng)，不能正確譯碼。結(jié)論：為了得到具有糾一個(gè)錯(cuò)誤的二元（結(jié)論：為了得到具有糾一個(gè)錯(cuò)誤的二元（n，n-m）線性碼，（其中）線性碼，（其中n-m=k，m為校驗(yàn)位的個(gè)數(shù)），只需從定義在為校驗(yàn)位的個(gè)數(shù)），只需從定義在F2上的上的m維非零列矢量中選取彼此不維非零列矢量中選取彼此不同的同的n個(gè)列矢量個(gè)列矢量 并依任意次序把它們排成一個(gè)并依任意次序把它們排成一個(gè)mn的矩陣：的矩陣：011nHhhh那么以那么以H為校

26、驗(yàn)矩陣的二元（為校驗(yàn)矩陣的二元（n，n-m）線性碼）線性碼C就是一個(gè)可以糾正所有就是一個(gè)可以糾正所有單個(gè)錯(cuò)誤的的碼。單個(gè)錯(cuò)誤的的碼。1定義：定義：設(shè)設(shè)Vm(F2)是定義在是定義在F2上的一個(gè)上的一個(gè)m維的矢量空間維的矢量空間 令令H是二元是二元 m（2m-1）矩陣，這個(gè)矩陣的列是）矩陣，這個(gè)矩陣的列是Vm（F2）中按某種）中按某種次序排列的次序排列的2m-1個(gè)非零矢量，那么定義在個(gè)非零矢量，那么定義在F2上的上的n=2m-1，k = 2m-1-m的線性分組碼（校驗(yàn)矩陣為的線性分組碼（校驗(yàn)矩陣為H）就稱為長）就稱為長2m-1的漢明碼。的漢明碼。1,.,10,nhhh設(shè)消息或數(shù)據(jù)以二進(jìn)制形式表示，

27、并以設(shè)消息或數(shù)據(jù)以二進(jìn)制形式表示，并以F2 = 0 , 1 表示這個(gè)二元集。表示這個(gè)二元集。如：如：100101101011010011110H的（的（7，4）線性分組碼就是漢明碼）線性分組碼就是漢明碼m=3，n=23-1=7，k=7-3=42定理：定理：二元（二元（2m-1，2m-1-m）漢明碼是能夠糾單個(gè)錯(cuò)誤的線性碼，而）漢明碼是能夠糾單個(gè)錯(cuò)誤的線性碼，而且是校驗(yàn)位數(shù)為且是校驗(yàn)位數(shù)為m的所有二元線性碼種編碼效率最高的碼，其的所有二元線性碼種編碼效率最高的碼，其最小重量：最小重量：wmin（C）=3。3完備碼：完備碼：設(shè)設(shè)C是（是（n，k）線性分組碼，其糾錯(cuò)能力為）線性分組碼，其糾錯(cuò)能力為t

28、，如果用且只用，如果用且只用小于等于小于等于t個(gè)錯(cuò)誤的全部錯(cuò)誤圖樣作為陪集首就能做成標(biāo)準(zhǔn)陣個(gè)錯(cuò)誤的全部錯(cuò)誤圖樣作為陪集首就能做成標(biāo)準(zhǔn)陣列，那么稱這個(gè)碼為完備碼。列，那么稱這個(gè)碼為完備碼。 四四. . 漢明碼的編譯碼電路框圖漢明碼的編譯碼電路框圖1.1.編碼器設(shè)計(jì)編碼器設(shè)計(jì)例例 (7,4)(7,4)漢明碼漢明碼011110010110101101001H1000110010001100101110001101GvuG 0123()uuuuu由 ，402350126123,0 3iivu ivuuuvuuuvuuu2. 2. 譯碼器設(shè)計(jì)譯碼器設(shè)計(jì)令接收字為令接收字為 0123456()rrrrrr

29、rr0123456()rrrrrrrr伴隨式為伴隨式為 012()ssss由校驗(yàn)矩陣由校驗(yàn)矩陣H， 01234srrrr51023srrrr20136srrrr 令令5012346()eeeeeeee11010000000110100000111001000010100010001000000100010000001000100000010s5e4e3e2e1e0e2s1s6e00 1 2es s s10 1 2es s s20 1 2es s s30 1 2es s s40 1 2es s s50 1 2es s s60 1 2es s s 漢明碼的譯碼電路框圖漢明碼的譯碼電路框圖vre00

30、1166()rerere 內(nèi)容提要n一、糾錯(cuò)碼的基本概念n二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)三、線性分組碼四、循環(huán)碼四、循環(huán)碼n五、卷積碼1.循環(huán)碼的定義n定義一 一個(gè)(n,k)線性分組碼，如果每個(gè)碼字經(jīng)任意循環(huán)移位之后仍然在碼字的集合中，那么就稱此碼是一個(gè)循環(huán)碼。n定義二 設(shè) 是某(n,k)線性分組碼的碼字集合， 如果對于任何 ， 它的循環(huán)移位 ，則稱該碼為循環(huán)碼。 這種循環(huán)性可以推廣到任意 次循環(huán)移位， 記作：120(,.,)nnAaaa(1)201(,.,)nnAaa a(01)iin ( )121012(,.,.,)in in innn iAaaa a aaa 【例】（【例】（7，3）線性分組碼）

31、線性分組碼1000110010001100101110001101H101110011100100111001G由：由： 得得vu G由兩組碼字循環(huán)構(gòu)成的循環(huán)碼由兩組碼字循環(huán)構(gòu)成的循環(huán)碼。2. 碼字的多項(xiàng)式描述n對于任意個(gè)長度為n的碼字， 可用下列多項(xiàng)式來描述：121210( ).nnnnA xaxaxa xan這里，把各碼元當(dāng)作多項(xiàng)式的系數(shù)；x及其冪次數(shù)僅是碼元位置的標(biāo)記，我們并不關(guān)心它的取值；稱系數(shù)不為零的x的最高次數(shù)為多項(xiàng)式A(x)的次數(shù)，或稱為多項(xiàng)式的階數(shù)。120(,.,)nnAaaa多項(xiàng)式的模運(yùn)算示例 如果A（an-1 an-2 a1 a0）是（n，k）循環(huán)碼的一個(gè)碼字，則A (1)

32、（an-2 a1 a0 an-1）也是該循環(huán)碼的一個(gè)碼字。這就是說A (x)an-1xn-1an-2xn-2a1xa0 和 A (1) (x)an-2xn-1a1x2a0 xan-1都是（n，k）循環(huán)碼的碼字多項(xiàng)式。 循環(huán)多項(xiàng)式的模運(yùn)算比較A(x)和A (1) (x)后可得 A (1) (x)x A (x), mod xn+1以及 A(i) (x)xiA (x) （i1,2,n1）, mod xn+1 循環(huán)多項(xiàng)式的模運(yùn)算n定理：對于(n,k)循環(huán)碼， 若A(x)對應(yīng)碼字 ， 對應(yīng)A(x)的i次左循環(huán)移位， 則 等于 除以 后的余式，即： 120(,.,)nnAaaa( )( )iAx( )(

33、)iAx( )ix A x(1)nx ( )( )( )(1)iinx A xAxx模n例題：設(shè)循環(huán)碼(7,4)中一個(gè)碼字為00001101，則該循環(huán)碼的所有碼字及其碼多項(xiàng)式如表所示。序號循環(huán)碼左移位數(shù)i00011010001101010110100211010003101000140100011510001106( )ix A x7(1)x 求模的余數(shù)多項(xiàng)式321xx32(1)x xx232(1)xxx332(1)xxx432(1)xxx532(1)xxx632(1)xxx321xx43xxx542xxx653xxx641xx51xx62xxx3.生成多項(xiàng)式和生成矩陣n生成多項(xiàng)式記為g(x)

34、,所有循環(huán)碼(n,k)的碼多項(xiàng)式A(x)可由g(x)生成，即A(x)=m(x)g(x), 式中，m(x)為消息多項(xiàng)式，它與消息位對應(yīng)。n生成多項(xiàng)式g(x)性質(zhì)：循環(huán)碼(n,k)的生成多項(xiàng)式是xn+1的一個(gè)因子，且最高次數(shù)為n-k。 證明： 由于A(x)=m(x)g(x), 而m(x)最高次數(shù)為k-1，A(x)最高次數(shù)為n-1， 所以g(x)最高次數(shù)為 (n-1)-(k-1)=n-k。n例：求循環(huán)碼(7,4)的生成多項(xiàng)式g(x)解：將x7+1分解得 x7+1=(x+1)(x3+x+1)(x3+x2+1) ， 因?yàn)間(x)最高次數(shù)為n-k=3，所以，其生成多項(xiàng)式有兩種可能，即： x3+x+1或x3

35、+x2+1n由生成多項(xiàng)式g(x)容易得到生成矩陣。生成矩陣的每一行必定為線性無關(guān)的，且每行都是一個(gè)碼字。g(x)為n-k階多項(xiàng)式，則g(x),xg(x), x2g(x), xk-1g(x)必是線性無關(guān)的，將此對應(yīng)的碼字作為矩陣的每一行，得到生成矩陣。與生成矩陣對應(yīng)的生成矩陣多項(xiàng)式G(x)可記作：3.生成多項(xiàng)式和生成矩陣12( )( )( )( )( )kxg xG xx g xxg xg x例題：已知循環(huán)碼(7,4)的生成多項(xiàng)式g(x)有兩種可能 x3+x+1或x3+x2+1，分別求其生成矩陣n解：若生成多項(xiàng)式g(x)=x3+x+1,則生成矩陣多項(xiàng)式為：336432353234233(1)(1

36、)( )(1)11xxxxxxxxxxxxG xx xxxxxxxxxn所對應(yīng)的生成矩陣為：1011000010110000101100001011G例題：已知循環(huán)碼(7,4)的生成多項(xiàng)式g(x)有兩種可能 x3+x+1或x3+x2+1，分別求其生成矩陣n解：若生成多項(xiàng)式g(x)=x3+x2+1,則生成矩陣多項(xiàng)式為：33265323254232433232(1)(1)( )(1)11xxxxxxxxxxxxG xx xxxxxxxxxn所對應(yīng)的生成矩陣為：1101000011010000110100001101G例題：如果循環(huán)碼(7,4)的生成多項(xiàng)式g(x)= x3+x+1求對應(yīng)的所有碼字n解

37、：可得生成矩陣為1011000010110000101100001011G10111000101111011000100111011000110001011000010001011000010001011000011011000010100101100010100101101001000101111111100011000110000110100101110011100100111101001111010011110100011101000111010000000111111116個(gè)碼字構(gòu)成4個(gè)循環(huán)組，前兩組分別7個(gè)碼字，后兩組為自循環(huán)的單獨(dú)碼字?？梢?，循環(huán)碼并不是只由一個(gè)碼字循環(huán)就可以得到全

38、部碼字。n將生成矩陣通過矩陣初等變換轉(zhuǎn)換成IkPk*r的形式，即可得到系統(tǒng)生成矩陣。3.生成多項(xiàng)式和生成矩陣生成多項(xiàng)式g(x)生成矩陣多項(xiàng)式G(x)生成矩陣G系統(tǒng)生成矩陣Gn解：可以先得到兩個(gè)生成矩陣，后經(jīng)過矩陣初等變換得到系統(tǒng)生成矩陣11011000010110000101100001011G例題：已知循環(huán)碼(7,4)的生成多項(xiàng)式g(x)有兩種可能 x3+x+1或x3+x2+1，分別求其系統(tǒng)生成矩陣21101000011010000110100001101G10001010100111001011000010111000110010001100101110001101矩陣初等變換矩陣初等變換

39、100010001011100110001001100110001101110110000101010110000100010110000110001010100101001110100001011010100001011110111100111001100001101001011100111001001111010011110100111101000111010001110100000001111111通過比較，可以發(fā)現(xiàn)，對于生成矩陣G1及系統(tǒng)生成矩陣G1,最后所生成的碼字相同，唯一不同的是消息位與碼字的對應(yīng)關(guān)系不同。由生成多項(xiàng)式g(x)直接產(chǎn)生系統(tǒng)循環(huán)碼n步驟：n(1)將消息多項(xiàng)式m(x)

40、乘以xn-k；n(2)將xn-k m(x)除以g(x)得到余式r(x)；n(3)將r(x)加進(jìn)xn-k m(x)，得到系統(tǒng)碼。n解:(1)消息碼為1101，所以消息多項(xiàng)式為m(x)=x3+x2+1，則 xn-km(x)=x3m(x)=x6+x5+x3 (2)求余式 (3)求系統(tǒng)碼多項(xiàng)式 C(x)= xn-km(x) +r(x)= x6+x5+x3 +1 所以對應(yīng)的系統(tǒng)循環(huán)碼為1101001例題：如果循環(huán)碼(7,4)的生成多項(xiàng)式g(x)= x3+x+1，消息碼為1101，求對應(yīng)的系統(tǒng)循環(huán)碼653( )( )mod ( )mod ( )1mod ( )n kr xxm xg xxxxg xg x4

41、. 校驗(yàn)多項(xiàng)式和校驗(yàn)矩陣4. 校驗(yàn)多項(xiàng)式和校驗(yàn)矩陣4. 校驗(yàn)多項(xiàng)式和校驗(yàn)矩陣5.伴隨多項(xiàng)式和伴隨矩陣n伴隨多項(xiàng)式S(x)與收到的碼多項(xiàng)式R(x)同余( )( )mod ( )S xR xg xn伴隨多項(xiàng)式S(x)與差錯(cuò)圖樣多項(xiàng)式E(x)之間也存在一一對應(yīng)關(guān)系( )( )( )mod ( )( ) ( )( )mod ( )( )S xC xE xg xm x g xE xg xE x5.伴隨多項(xiàng)式和伴隨矩陣n循環(huán)碼譯碼步驟n(1)利用 ，建立差錯(cuò)圖樣多項(xiàng)式E(x)和伴隨多項(xiàng)式S(x)之間的映射表；n(2)收到R(x)后，利用 得到某個(gè)S(x)，然后利用步驟(1)中建立的映射表，即可查到所對應(yīng)的

42、差錯(cuò)多項(xiàng)式E(x);n(3) 將差錯(cuò)多項(xiàng)式E(x)與R(x)相加，即可得到經(jīng)過糾錯(cuò)的C(x)。 ( )( )mod ( )S xE xg x( )( )mod ( )S xR xg xn解，由 得到( )( )mod ( )S xE xg x例題：如果循環(huán)碼(7,4)的生成多項(xiàng)式g(x)= x3+x+1，確定差錯(cuò)圖樣多項(xiàng)式與伴隨多項(xiàng)式的映射表差錯(cuò)圖樣多項(xiàng)式E(x)伴隨多項(xiàng)式S(x)0011xxx2x2x3x+1x4x2+xx5x2+x+1x6x2+1n若已知伴隨多項(xiàng)式S(x)，可以容易求得對應(yīng)的伴隨矩陣S。例如，S(x)=x2+x+1,則伴隨矩陣S=1 1 1n當(dāng)然，由于循環(huán)碼是線性分組碼的子

43、類，所以，伴隨矩陣仍可以由S=RHT求得。5.伴隨多項(xiàng)式和伴隨矩陣6. BCH碼和RS碼nBCH碼是循環(huán)碼中的一個(gè)大類，分為二進(jìn)制BCH碼和非二進(jìn)制BCH碼(例如RS碼)。n二進(jìn)制BCH碼可記為(2m-1,k)，其中m為正整數(shù)且 ，即碼長n=2m-1，且 (t為可糾正的差錯(cuò)數(shù))，t由最小碼距決定，即n二進(jìn)制BCH碼的優(yōu)點(diǎn)是，具有糾正多個(gè)隨機(jī)差錯(cuò)的能力。具有嚴(yán)謹(jǐn)?shù)拇鷶?shù)結(jié)構(gòu)，可以按照碼長n和糾錯(cuò)能力t直接將BCH碼構(gòu)造出來。該特點(diǎn)優(yōu)于一般線性分組碼，一般線性分組碼在設(shè)計(jì)出來之后，需要計(jì)算最小距離dmin，才能知道糾錯(cuò)能力。若不符合要求，還要重復(fù)設(shè)計(jì)過程。3m nkmtmin21dt6. BCH碼和

44、RS碼n確定BCH碼的生成多項(xiàng)式g(x)，取決于兩方面：n(1) g(x)是xn+1因式中最高階為n-k的多項(xiàng)式，這是任何循環(huán)碼都必須滿足的條件。由于BCH碼的碼長n=2m-1， ，所以其碼長的取值只能是7,15,31,63,127,255,當(dāng)n較大時(shí)，xn+1的因式分解就只能用計(jì)算機(jī)來計(jì)算。n(2) g(x)必須滿足對糾錯(cuò)能力t的要求，即對最小碼距的要求。n實(shí)際應(yīng)用中，將滿足上述兩個(gè)條件的系數(shù)整理成“BCH碼生成多項(xiàng)式系數(shù)”表，以便查用。3m 例題：求碼長為15且能糾正3個(gè)差錯(cuò)的BCH碼n解：碼長n=2m-1=15，所以m=4；糾錯(cuò)能力t=3；將x15+1因式分解后， 得x15+1=(x+1

45、)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1) 查前述的“BCH碼生成多項(xiàng)式系數(shù)”表，可得滿足條件的BCH碼為(15,5)，其相應(yīng)的生成多項(xiàng)式的最高階為n-k=10，則生成多項(xiàng)式為 g(x)=(x2+x+1)(x4+x+1)(x4+x3+x2+x+1) =x10+x8+x5+x4+x2+x+16. BCH碼和RS碼nRS(Reed-Solomn)碼是一種非二進(jìn)制BCH碼。nRS碼是極大最小距離碼(MDC碼)。n若某個(gè)碼的最小距離dmin=n-k+1，則稱線性分組碼(n,k)為極大最小距離碼。在(n,k)線性分組碼中，極大最小距離碼具有最大的檢錯(cuò)、糾錯(cuò)能力。n由

46、于RS碼是多進(jìn)制，所以很容易與M進(jìn)制調(diào)制技術(shù)相匹配；RS碼特別適合糾正突發(fā)錯(cuò)誤。內(nèi)容提要n一、糾錯(cuò)碼的基本概念n二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)三、線性分組碼四、循環(huán)碼五、卷積碼五、卷積碼卷積碼與線性分組碼的比較卷積碼線性分組碼表示符號(n,k,K)，K為約束長度(n,k)記憶性有記憶，輸出的n個(gè)比特不僅與當(dāng)前輸入的k比特有關(guān)，而且與以前輸入的K個(gè)k比特有關(guān)無記憶，輸出的n個(gè)比特僅與當(dāng)前輸入的k個(gè)比特有關(guān)(可視為K=0時(shí)的無記憶卷積碼)代數(shù)結(jié)構(gòu)無嚴(yán)格的代數(shù)結(jié)構(gòu)，目前多采用計(jì)算機(jī)來搜索好碼，缺乏有效的數(shù)學(xué)分析工具有嚴(yán)格的代數(shù)結(jié)構(gòu)，借用數(shù)學(xué)工具研究較為透徹編碼效率()LkLK nknkkkn輸入k位當(dāng)前時(shí)間

47、以前K個(gè)時(shí)間輸入n位kn輸入k位輸入n位卷積碼卷積碼線性分組碼線性分組碼1. 卷積碼的組織結(jié)構(gòu)n卷積碼(n,k,K)與線性分組碼(n,k)的重要區(qū)別在于，卷積碼是有記憶的，并用約束長度表示記憶長度，記為K。輸出的n位比特不僅與當(dāng)前時(shí)間輸入的k比特有關(guān)，還與以前時(shí)間輸入的多個(gè)k比特有關(guān)，到底與以前多長時(shí)間有關(guān)，就由約束長度K來度量。n卷積碼可以視為多個(gè)線性分組碼的線性疊加，只不過多個(gè)線性分組碼是來源于同一個(gè)輸入源的多個(gè)不同時(shí)間段(包括當(dāng)前時(shí)間段和K個(gè)以前時(shí)間段)。顯然，當(dāng)K=0時(shí)，卷積碼就退化為線性分組碼。例題：設(shè)卷積碼(2,1,2)，其組織結(jié)構(gòu)如圖(a)所示，假設(shè)輸入序列為1011，通過求輸出序列，來說明卷積碼編碼的全過程10011010011011011010011000010100000(a)(b)(