第8章信道編碼

1、第第8 8章章 信道編碼信道編碼8.1 信道編碼的基本概念信道編碼的基本概念8.2 譯碼規(guī)則譯碼規(guī)則8.3 信道編碼定理信道編碼定理8.4 線性分組碼線性分組碼8.5 循環(huán)碼循環(huán)碼8.6 卷積碼卷積碼8.7 突發(fā)錯(cuò)誤的糾正突發(fā)錯(cuò)誤的糾正 本章小結(jié)本章小結(jié)8.1 信道編碼的基本概念信道編碼的基本概念8.1.1 編譯碼規(guī)則、檢糾錯(cuò)能力編譯碼規(guī)則、檢糾錯(cuò)能力8.1.2 平均錯(cuò)誤譯碼概率平均錯(cuò)誤譯碼概率信源編碼信源編碼信道編碼信道編碼目的目的壓縮，通過去除壓縮，通過去除信源冗余實(shí)現(xiàn)信源冗余實(shí)現(xiàn)糾錯(cuò)，通過引入冗余實(shí)現(xiàn)糾錯(cuò)，通過引入冗余實(shí)現(xiàn)主要指標(biāo)主要指標(biāo)平均碼長(zhǎng)平均碼長(zhǎng)平均錯(cuò)誤譯碼概率平均錯(cuò)誤譯碼概率影

2、響主要指影響主要指標(biāo)的因素標(biāo)的因素編碼方法編碼方法編碼方法、譯碼方法編碼方法、譯碼方法編譯碼之間編譯碼之間的關(guān)系的關(guān)系一個(gè)編碼方法對(duì)一個(gè)編碼方法對(duì)應(yīng)一個(gè)譯碼方法，應(yīng)一個(gè)譯碼方法，譯碼是編碼的逆過譯碼是編碼的逆過程程一個(gè)編碼方法可能對(duì)應(yīng)多個(gè)一個(gè)編碼方法可能對(duì)應(yīng)多個(gè)譯碼方法，在這多個(gè)譯碼方譯碼方法，在這多個(gè)譯碼方法中有一個(gè)能使平均錯(cuò)誤譯法中有一個(gè)能使平均錯(cuò)誤譯碼概率最小碼概率最小8.1.1 編譯碼規(guī)則、檢糾錯(cuò)能力編譯碼規(guī)則、檢糾錯(cuò)能力例子例子1 1【例例8-1，P130】奇偶校驗(yàn)碼是一種簡(jiǎn)單而又常用的編碼方奇偶校驗(yàn)碼是一種簡(jiǎn)單而又常用的編碼方法。分為奇校驗(yàn)和偶校驗(yàn)。法。分為奇校驗(yàn)和偶校驗(yàn)。加入奇偶

3、校驗(yàn)位（冗余位），使奇偶校驗(yàn)碼具有檢錯(cuò)加入奇偶校驗(yàn)位（冗余位），使奇偶校驗(yàn)碼具有檢錯(cuò)能力；能力；不具有糾錯(cuò)能力；不具有糾錯(cuò)能力；奇偶校驗(yàn)碼能錯(cuò)出一位錯(cuò)誤，即檢錯(cuò)能力為奇偶校驗(yàn)碼能錯(cuò)出一位錯(cuò)誤，即檢錯(cuò)能力為1位。位。例子例子2 2【例例8-2，P131】重復(fù)碼也是一種常見的信道編碼方式。試分析重復(fù)碼也是一種常見的信道編碼方式。試分析一次、二次和重復(fù)編碼。一次、二次和重復(fù)編碼。l設(shè)要傳送設(shè)要傳送A和和B兩個(gè)消息兩個(gè)消息l一次重復(fù)編碼：一次重復(fù)編碼：A0，B 1此時(shí)沒有冗余，無檢、糾錯(cuò)能力；此時(shí)沒有冗余，無檢、糾錯(cuò)能力；當(dāng)接收到當(dāng)接收到010011時(shí)，譯碼為時(shí)，譯碼為ABAABB無法發(fā)現(xiàn)接收到的字符

4、串中是否有錯(cuò)誤；無法發(fā)現(xiàn)接收到的字符串中是否有錯(cuò)誤；l二次重復(fù)編碼：二次重復(fù)編碼： 00、B 11此時(shí)有此時(shí)有1位冗余，稱為位冗余，稱為監(jiān)督位（監(jiān)督元、校驗(yàn)元）監(jiān)督位（監(jiān)督元、校驗(yàn)元）當(dāng)接收到當(dāng)接收到010011時(shí)時(shí)會(huì)發(fā)現(xiàn)無法譯碼（會(huì)發(fā)現(xiàn)無法譯碼（01）具有檢測(cè)具有檢測(cè)1位錯(cuò)誤能力；無糾錯(cuò)能力；位錯(cuò)誤能力；無糾錯(cuò)能力；“01”和和“10”稱為稱為禁用碼字禁用碼字，而，而“00”和和“11”稱為稱為許用碼許用碼字。字。l三次重復(fù)編碼：三次重復(fù)編碼： A000，B 111有有2位冗余位冗余；能檢測(cè)能檢測(cè)1位或位或2位錯(cuò)誤，即檢錯(cuò)能力為位錯(cuò)誤，即檢錯(cuò)能力為2位；位；當(dāng)接收到當(dāng)接收到010011時(shí)，會(huì)

5、發(fā)現(xiàn)出現(xiàn)了禁用碼字（時(shí)，會(huì)發(fā)現(xiàn)出現(xiàn)了禁用碼字（010、011）無論無論000010，還是，還是111010，均可判斷出現(xiàn)錯(cuò)誤，均可判斷出現(xiàn)錯(cuò)誤因此可以因此可以檢檢2位錯(cuò)位錯(cuò)如果按照如果按照“大數(shù)法則大數(shù)法則”譯碼譯碼則譯碼結(jié)果為則譯碼結(jié)果為AB具有糾錯(cuò)能力；具有糾錯(cuò)能力；如果如果000010，可正確譯碼為，可正確譯碼為A；如果；如果111010，不能，不能正確譯碼，即該錯(cuò)誤不能被正確糾正過來正確譯碼，即該錯(cuò)誤不能被正確糾正過來因此只能因此只能糾糾1位錯(cuò)位錯(cuò)8.1.2 平均錯(cuò)誤譯碼概率平均錯(cuò)誤譯碼概率1、平均錯(cuò)誤譯碼概率的計(jì)算方法、平均錯(cuò)誤譯碼概率的計(jì)算方法平均錯(cuò)誤譯碼概率平均錯(cuò)誤譯碼概率Pe為

6、錯(cuò)誤譯碼概率的均值為錯(cuò)誤譯碼概率的均值 其中其中p(xi)是信源符號(hào)是信源符號(hào)xi的概率，的概率，pei是信源符號(hào)是信源符號(hào)xi被錯(cuò)誤譯碼被錯(cuò)誤譯碼的概率。的概率。Pe是衡量譯碼方法好壞的一個(gè)重要指標(biāo)，所選擇的譯碼規(guī)是衡量譯碼方法好壞的一個(gè)重要指標(biāo)，所選擇的譯碼規(guī)則應(yīng)該使則應(yīng)該使Pe盡可能小。盡可能小。nieiiepxpP1)(【例例8-3，P131】對(duì)于三次重復(fù)碼，假設(shè)信源輸出的兩個(gè)對(duì)于三次重復(fù)碼，假設(shè)信源輸出的兩個(gè)符號(hào)為等概分布，即符號(hào)為等概分布，即信源符號(hào)經(jīng)過三次重復(fù)編碼后在信道上傳輸，信道矩陣為信源符號(hào)經(jīng)過三次重復(fù)編碼后在信道上傳輸，信道矩陣為試計(jì)算此時(shí)的平均錯(cuò)誤譯碼概率。試計(jì)算此時(shí)的

7、平均錯(cuò)誤譯碼概率。212110PX99. 001. 001. 099. 0P平均錯(cuò)誤譯碼概率例子平均錯(cuò)誤譯碼概率例子解：解：0003. 0)01. 099. 001. 03(21 2)(3221ieiiepxpP2、平均錯(cuò)誤譯碼概率與編碼規(guī)則有關(guān)、平均錯(cuò)誤譯碼概率與編碼規(guī)則有關(guān)【例例8-4，P132】對(duì)于例對(duì)于例8-3中的信源和信道，如果進(jìn)行一次重復(fù)中的信源和信道，如果進(jìn)行一次重復(fù)編碼，平均錯(cuò)誤譯碼概率是多少？并與例編碼，平均錯(cuò)誤譯碼概率是多少？并與例8-3的結(jié)果進(jìn)行比較。的結(jié)果進(jìn)行比較。解：解：10 . 001. 02101. 021)(21ieiiepxpP說明：說明： 與例與例8-3的結(jié)

8、果不一樣；的結(jié)果不一樣； 平均錯(cuò)誤譯碼概率與編碼規(guī)則有關(guān)。平均錯(cuò)誤譯碼概率與編碼規(guī)則有關(guān)?！纠?-5，P132】對(duì)于二進(jìn)制對(duì)稱信道，信道矩陣和信源分布對(duì)于二進(jìn)制對(duì)稱信道，信道矩陣和信源分布分別為：分別為：信源符號(hào)不經(jīng)過任何編碼，直接在信道上傳輸，采用兩種不信源符號(hào)不經(jīng)過任何編碼，直接在信道上傳輸，采用兩種不同的譯碼規(guī)則：同的譯碼規(guī)則： 譯碼規(guī)則譯碼規(guī)則1：00、 11 譯碼規(guī)則譯碼規(guī)則2：01、 10試分別計(jì)算這兩種不同譯碼規(guī)則的平均錯(cuò)誤譯碼概率。試分別計(jì)算這兩種不同譯碼規(guī)則的平均錯(cuò)誤譯碼概率。3、平均錯(cuò)誤譯碼概率與譯碼規(guī)則也有關(guān)、平均錯(cuò)誤譯碼概率與譯碼規(guī)則也有關(guān)ppPX1104143434

9、1P解：解：譯碼規(guī)則譯碼規(guī)則143)1 (4343)(21pppxpPieiie譯碼規(guī)則譯碼規(guī)則241)1 (4141)(21pppxpPieiie 說明：說明：在同樣的編碼規(guī)則下，不同譯碼規(guī)則的平均錯(cuò)在同樣的編碼規(guī)則下，不同譯碼規(guī)則的平均錯(cuò)誤譯碼概率是不一樣的；誤譯碼概率是不一樣的；平均錯(cuò)誤譯碼概率與譯碼規(guī)則有關(guān)。平均錯(cuò)誤譯碼概率與譯碼規(guī)則有關(guān)。8.2 譯碼規(guī)則譯碼規(guī)則【定義定義8-1】 設(shè)信道輸入符號(hào)集為設(shè)信道輸入符號(hào)集為 ， 輸出符號(hào)集為輸出符號(hào)集為 ，若對(duì)每一個(gè)輸出符號(hào)，若對(duì)每一個(gè)輸出符號(hào)yj都有一個(gè)確定的函數(shù)都有一個(gè)確定的函數(shù)F(yj)，使，使yj對(duì)應(yīng)于唯一的一個(gè)輸入符號(hào)對(duì)應(yīng)于唯一的

10、一個(gè)輸入符號(hào)xi，則稱這樣的函數(shù)為，則稱這樣的函數(shù)為譯碼規(guī)則譯碼規(guī)則，記為，記為nxxxX,21myyyY,21ijxyF)(問題的引出：?jiǎn)栴}的引出：平均錯(cuò)誤譯碼概率與譯碼規(guī)則有關(guān)。平均錯(cuò)誤譯碼概率與譯碼規(guī)則有關(guān)。有沒有一種譯碼規(guī)則能使平均錯(cuò)誤譯碼概率有沒有一種譯碼規(guī)則能使平均錯(cuò)誤譯碼概率Pe達(dá)到最?。窟_(dá)到最?。吭诓豢紤]編碼規(guī)則的前提下，極大似然譯碼能在不考慮編碼規(guī)則的前提下，極大似然譯碼能使平均錯(cuò)誤譯碼概率使平均錯(cuò)誤譯碼概率Pe達(dá)到最小。達(dá)到最小?！径x定義8-2】 選擇譯碼函數(shù)選擇譯碼函數(shù)F(yj)=x*，使之滿足，使之滿足 則稱為則稱為極大似然譯碼規(guī)則極大似然譯碼規(guī)則。 極大似然譯碼能使

11、極大似然譯碼能使平均錯(cuò)誤譯碼概率最小。平均錯(cuò)誤譯碼概率最小。上述條件可改為上述條件可改為平均錯(cuò)誤譯碼概率可用下式計(jì)算：平均錯(cuò)誤譯碼概率可用下式計(jì)算：證明證明)()()()(iijjxpxypxpxyp)()(jijyxpyxp，YyyFxXxjinieiiejjiiyxppxpP)(,1),()(【例例8-6，P133】 對(duì)例對(duì)例8-5給出的信源和信道，試設(shè)計(jì)極大似給出的信源和信道，試設(shè)計(jì)極大似然譯碼規(guī)則，并求平均錯(cuò)誤譯碼概率。然譯碼規(guī)則，并求平均錯(cuò)誤譯碼概率。ppPX11041434341P譯碼規(guī)則例子譯碼規(guī)則例子1 1410 p)1 (4143)1 (4341pppp且1) 1 (, 1)

12、0(FFYyyFxXxjinieiiejjiipppyxppxpP)(,14341),()(1 1、當(dāng)、當(dāng)時(shí)，有時(shí)，有因此極大似然譯碼規(guī)則為因此極大似然譯碼規(guī)則為此時(shí)，平均錯(cuò)誤譯碼概率為此時(shí)，平均錯(cuò)誤譯碼概率為解：解：聯(lián)合概率分布為聯(lián)合概率分布為 )1 (41)1 (434341) 1 () 11 () 1 () 10()0()01 ()0()00(),(ppppppppppppPXXYXXYXXYXXYYX)1 (4143)1 (4341pppp且0) 1 (, 1)0(FF2 2、當(dāng)、當(dāng)時(shí)，有時(shí)，有因此極大似然譯碼規(guī)則為因此極大似然譯碼規(guī)則為此時(shí)，平均錯(cuò)誤譯碼概率為此時(shí)，平均錯(cuò)誤譯碼概率為

13、4341 pYyyFxXxjinieiiejjiippyxppxpP)(,141)1 (4141),()()1 (4143)1 (4341pppp且0) 1 (, 0)0(FF3 3、當(dāng)、當(dāng)時(shí)，有時(shí)，有因此極大似然譯碼規(guī)則為因此極大似然譯碼規(guī)則為此時(shí)，平均錯(cuò)誤譯碼概率為此時(shí)，平均錯(cuò)誤譯碼概率為143 pYyyFxXxjinieiiejjiipppyxppxpP)(,11)1 (41)1 (43),()()1 (41)1 (434341) 1 () 11 () 1 () 10()0()01 ()0()00(),(ppppppppppppPXXYXXYXXYXXYYX 設(shè)信道矩陣：設(shè)信道矩陣：1、

14、當(dāng)輸入等概時(shí)，給出極大似然譯碼規(guī)則，并計(jì)算平均錯(cuò)誤譯碼概率。、當(dāng)輸入等概時(shí)，給出極大似然譯碼規(guī)則，并計(jì)算平均錯(cuò)誤譯碼概率。2、若若 給出極大似然譯碼規(guī)則；計(jì)算平均錯(cuò)誤概率。給出極大似然譯碼規(guī)則；計(jì)算平均錯(cuò)誤概率。解：解：1、（、（1）當(dāng)輸入等概時(shí)，極大似然譯碼規(guī)則：當(dāng)輸入等概時(shí)，極大似然譯碼規(guī)則： （2）計(jì)算錯(cuò)誤譯碼概率計(jì)算錯(cuò)誤譯碼概率216131312161613121P2)2(1) 1 (0)0(FFF【例，增例，增】譯碼規(guī)則例子譯碼規(guī)則例子2 241)2() 1 (21)0(ppp，611819191611811819161)2()22()2()21 ()2()20() 1 () 12(

15、) 1 () 11 () 1 () 10()0()02()0()01 ()0()00(),(XXYXXYXXYXXYXXYXXYXXYXXYXXYYXppppppppppppppppppP31)2() 1 ()0(ppp219118118191)91181(),()(,)(）（）（XxYyyFxjieiiieijjiyxppxpP81241121121812411216141)2()22()2()21 ()2()20() 1 () 12() 1 () 11 () 1 () 10()0()02()0()01 ()0()00(),(XXYXXYXXYXXYXXYXXYXXYXXYXXYYXpppp

16、ppppppppppppppP2)2(0) 1 (0)0(FFF241112112124181)121241(),()(,)(）（）（XxYyyFxjieiiieijjiyxppxpP（1）極大似然譯碼規(guī)則）極大似然譯碼規(guī)則（2 2）計(jì)算錯(cuò)誤譯碼概率）計(jì)算錯(cuò)誤譯碼概率2、當(dāng)輸入不等概時(shí)，當(dāng)輸入不等概時(shí)，41)2() 1 (21)0(ppp，216131312161613121P8.3 信道編碼定理信道編碼定理【定理定理8-1】 有噪信道編碼定理（香農(nóng)第二定理）有噪信道編碼定理（香農(nóng)第二定理） 對(duì)于一個(gè)給定的離散無記憶信道，信道容量為對(duì)于一個(gè)給定的離散無記憶信道，信道容量為C，如，如果信息傳輸率

17、果信息傳輸率Rt)個(gè)個(gè)錯(cuò) 碼 ， 則 要 求 最 小 碼 距 為錯(cuò) 碼 ， 則 要 求 最 小 碼 距 為dmine+t+1【例例8-10，P138】接例接例8-7，試分析（，試分析（7，3）線性分組碼的檢）線性分組碼的檢錯(cuò)和糾錯(cuò)能力。錯(cuò)和糾錯(cuò)能力。解解：例：例8-9得到得到dmin=4。碼的檢錯(cuò)和糾錯(cuò)的例子碼的檢錯(cuò)和糾錯(cuò)的例子 最多能檢測(cè)最多能檢測(cè)dmin-1=3個(gè)錯(cuò)誤；個(gè)錯(cuò)誤； 最多能糾正最多能糾正 個(gè)錯(cuò)誤；個(gè)錯(cuò)誤； 當(dāng)它同時(shí)用于檢錯(cuò)和糾錯(cuò)時(shí)，要求當(dāng)它同時(shí)用于檢錯(cuò)和糾錯(cuò)時(shí)，要求 即能糾正即能糾正1位錯(cuò)誤，同時(shí)檢位錯(cuò)誤，同時(shí)檢2位錯(cuò)誤。位錯(cuò)誤。121mind1, 31, 231mintete

18、tedte或8.4.4 生成矩陣和監(jiān)督矩陣生成矩陣和監(jiān)督矩陣1、生成矩陣、生成矩陣【例例8-11，P138】接例接例8-7，（，（7，3）線性分組碼的編碼規(guī)則如）線性分組碼的編碼規(guī)則如右，試給出生成矩陣。右，試給出生成矩陣。解解：設(shè)分組碼是設(shè)分組碼是C=(c6, c5, c4, c3, c2, c1, c0)，信息元是，信息元是M=(c6, c5, c4)，即，即C是碼字，是碼字，M是信息，則編碼規(guī)則可以表示為是信息，則編碼規(guī)則可以表示為即即C=MG，其中其中 稱為稱為生成矩陣生成矩陣c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4 c6=c6c5=c5c4=c4c3=c

19、6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4 6543210654100111001001110011101cccccccccc100111001001110011101G生成矩陣生成矩陣在在(n, k)線性分組碼中線性分組碼中, 每個(gè)碼字每個(gè)碼字C都可以表示為都可以表示為CMG則則G是該是該(n, k)線性分組碼的生成矩陣，即線性分組碼的生成矩陣，即生成矩陣生成矩陣G建立了消息與碼矢間的一一對(duì)應(yīng)關(guān)系，它起著建立了消息與碼矢間的一一對(duì)應(yīng)關(guān)系，它起著編碼器編碼器的變換作用；的變換作用；生成矩陣的每一行都是一個(gè)碼字。（生成矩陣的每一行都是一個(gè)碼字。（后面定理后面定理8-4給出給出

20、）111212122212nnkkknggggggGggg生成矩陣不是唯一的例子生成矩陣不是唯一的例子12101011100110110101 ,010011111000001101GG【例例8-12，P139】給出兩給出兩個(gè)生成矩陣。分別求出個(gè)生成矩陣。分別求出碼字空間，并進(jìn)行分析。碼字空間，并進(jìn)行分析。解解： CMG 結(jié)果如右結(jié)果如右l討論討論這兩個(gè)碼的檢錯(cuò)和這兩個(gè)碼的檢錯(cuò)和糾錯(cuò)能力一樣糾錯(cuò)能力一樣但是但是G2是系統(tǒng)碼，是系統(tǒng)碼，G1是非是非系統(tǒng)碼系統(tǒng)碼系統(tǒng)碼的編譯比較系統(tǒng)碼的編譯比較簡(jiǎn)單，而性能與非簡(jiǎn)單，而性能與非系統(tǒng)碼一樣，因此系統(tǒng)碼一樣，因此系統(tǒng)碼得到了廣泛系統(tǒng)碼得到了廣泛的應(yīng)用和研

21、究的應(yīng)用和研究系統(tǒng)碼的生成矩陣系統(tǒng)碼的生成矩陣可以表示為可以表示為GIk PIk-kk階單位方階單位方陣陣12101011100110110101 ,010011111000001101GG不同的生成矩陣可能生成相同的碼字空間不同的生成矩陣可能生成相同的碼字空間生成矩陣的初等變換變換生成矩陣的初等變換變換l非系統(tǒng)碼生成矩陣非系統(tǒng)碼生成矩陣變?yōu)榕c它等價(jià)變?yōu)榕c它等價(jià)的系統(tǒng)碼生成矩陣的方法的系統(tǒng)碼生成矩陣的方法交換行的位置；交換行的位置；將一行加到另一行上；將一行加到另一行上；交換列的位置。交換列的位置。 如例如例8-1212101011100110110101 ,01001111100000110

22、1GG101100110010011001101100011001110010101100101011110010000111101011110010000111101011110101212213321131G生成矩陣的每一行都是一個(gè)碼字生成矩陣的每一行都是一個(gè)碼字【定理定理8-4】生成矩陣的每一行都是一個(gè)碼字。生成矩陣的每一行都是一個(gè)碼字。證明證明l在線性分組碼在線性分組碼(n, k)中，如果中，如果矩陣矩陣H使得對(duì)使得對(duì)任意碼字任意碼字C都有下都有下式成立式成立則則H稱為稱為(n, k)線性碼的線性碼的一致監(jiān)督矩陣一致監(jiān)督矩陣(或或校驗(yàn)矩陣校驗(yàn)矩陣)其中其中TTT00HCCH111212

23、122212nnrrrnhhhhhhHhhh2、監(jiān)督矩陣、監(jiān)督矩陣監(jiān)督矩陣的標(biāo)準(zhǔn)形式監(jiān)督矩陣的標(biāo)準(zhǔn)形式對(duì)對(duì)H各行實(shí)行初等變換，將后各行實(shí)行初等變換，將后r列化為單位子陣列化為單位子陣:HQ Ir這種形式的這種形式的 H稱為監(jiān)督矩陣稱為監(jiān)督矩陣H的標(biāo)準(zhǔn)形式的標(biāo)準(zhǔn)形式如例如例8-11：(7,3)分組碼，監(jiān)督矩陣是標(biāo)準(zhǔn)形式為分組碼，監(jiān)督矩陣是標(biāo)準(zhǔn)形式為1011000111010011000100110001Hc3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4 c6+c4+c3=0c6+c5+c4+c2=0c6+c5+c1=0c5+c4+c0=0一般關(guān)系：一般關(guān)系：HGT 0T 或

24、或 GHT 0 如例如例8-11系統(tǒng)碼的生成矩陣與監(jiān)督系統(tǒng)碼的生成矩陣與監(jiān)督矩陣標(biāo)準(zhǔn)形之間的關(guān)系矩陣標(biāo)準(zhǔn)形之間的關(guān)系（G=Ik P、H=Q Ir）：）： 其中：其中：PQT 或或 Q=PT T1000101011000000001111010000010111000100001110110001000110011HG3、生成矩陣和監(jiān)督矩陣關(guān)系、生成矩陣和監(jiān)督矩陣關(guān)系【例例8-13，P141】接例接例8-11，已知（，已知（7，3）線性分組碼的生）線性分組碼的生成矩陣為成矩陣為求監(jiān)督矩陣。求監(jiān)督矩陣。解解： （G=Ik P、H=Q Ir）：）： 其中：其中：PQT 或或 Q=PT 生成矩陣與監(jiān)督

25、矩陣關(guān)系的例子生成矩陣與監(jiān)督矩陣關(guān)系的例子100111001001110011101G1011000111010011000100110001H100111001001110011101G8.4.5 對(duì)偶碼對(duì)偶碼對(duì)一個(gè)對(duì)一個(gè)(n, k)線性碼線性碼CI，由于，由于 HGT 0T，如果以，如果以G作監(jiān)督矩陣，作監(jiān)督矩陣，而以而以H作生成矩陣，可構(gòu)造另一個(gè)碼作生成矩陣，可構(gòu)造另一個(gè)碼CJCJ是一個(gè)是一個(gè)(n, n-k)線性碼，稱為線性碼，稱為 CI的對(duì)偶碼的對(duì)偶碼(7,3)碼的生成矩陣和監(jiān)督矩陣為碼的生成矩陣和監(jiān)督矩陣為則將兩個(gè)矩陣的作用對(duì)換，得到對(duì)偶碼則將兩個(gè)矩陣的作用對(duì)換，得到對(duì)偶碼(7,4)

26、碼的生成矩陣和碼的生成矩陣和監(jiān)督矩陣為監(jiān)督矩陣為變換后為標(biāo)準(zhǔn)形式變換后為標(biāo)準(zhǔn)形式(7,3)100111001001110011101G(7,3)1011000111010011000100110001H(7,4)100111001001110011101H(7,4)1011000111010011000100110001G(7,4)111010001110101101001H(7,4)1000101010011100101100001011G對(duì)偶碼的例子對(duì)偶碼的例子【例例8-14，P141】求（求（7，3）線性分組碼的對(duì)偶碼。）線性分組碼的對(duì)偶碼。解解： 得到的：得到的：(7,3)碼和碼和(7

27、,4)碼碼8.4.6 伴隨式及錯(cuò)誤檢測(cè)伴隨式及錯(cuò)誤檢測(cè)l伴隨式（監(jiān)督子，校驗(yàn)子）伴隨式（監(jiān)督子，校驗(yàn)子）對(duì)接收碼字對(duì)接收碼字R，用監(jiān)督矩陣，用監(jiān)督矩陣H來檢驗(yàn)來檢驗(yàn)R是否滿足監(jiān)督方程，是否滿足監(jiān)督方程，即即HRT0T是否成立是否成立若若HRT0T成立，則認(rèn)為成立，則認(rèn)為R是一個(gè)碼字，否則判為碼字在是一個(gè)碼字，否則判為碼字在傳輸中發(fā)生了錯(cuò)誤傳輸中發(fā)生了錯(cuò)誤把把SRHT或或STHRT，稱為接收碼字，稱為接收碼字R的伴隨式的伴隨式(或監(jiān)督或監(jiān)督子，或校驗(yàn)子子，或校驗(yàn)子)1、伴隨式、伴隨式l錯(cuò)誤圖樣錯(cuò)誤圖樣錯(cuò)誤圖樣錯(cuò)誤圖樣：設(shè)發(fā)送碼字：設(shè)發(fā)送碼字C(cn-1，cn-2，c0)，而接收到，而接收到的碼字

28、為的碼字為R(rn-1, rn-2, , r0)，則定義，則定義E(en1，en2，e0)=R-C，為信道的，為信道的錯(cuò)誤圖樣錯(cuò)誤圖樣 錯(cuò)誤圖樣含義：錯(cuò)誤圖樣含義：若若ei0，表示第，表示第i位無錯(cuò)，若位無錯(cuò)，若ei1，則表，則表示第示第i位有錯(cuò)位有錯(cuò)2、伴隨式的錯(cuò)誤圖樣表示、伴隨式的錯(cuò)誤圖樣表示l伴隨式的錯(cuò)誤圖樣表示伴隨式的錯(cuò)誤圖樣表示則此時(shí)伴隨式為則此時(shí)伴隨式為 ST HRT H(CE)T HCT+HET HET若將監(jiān)督矩陣若將監(jiān)督矩陣H表示為表示為H=h1 h2 hn 式中，式中，hi為為H的第的第i列列即即則此時(shí)伴隨式可表示為則此時(shí)伴隨式可表示為 STHET h1en1h2en2+hn

29、e0，這叫做，這叫做伴隨式的錯(cuò)伴隨式的錯(cuò)誤圖樣表示誤圖樣表示022110222212101212111021212222111211eheheheheheheheheheeehhhhhhhhhHESrnnrnrnnnnnnnnrnrrnnTTl基本結(jié)論基本結(jié)論伴隨式僅與錯(cuò)誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅與錯(cuò)誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅由錯(cuò)誤圖樣決定伴隨式僅由錯(cuò)誤圖樣決定伴隨式是錯(cuò)誤的判別式：若伴隨式是錯(cuò)誤的判別式：若S0，則判沒有出錯(cuò)，接收字，則判沒有出錯(cuò)，接收字是一個(gè)碼字，若是一個(gè)碼字，若S0，則判有錯(cuò)，則判有錯(cuò)二元碼伴隨式是二元碼伴隨式是H陣中與錯(cuò)誤碼元對(duì)應(yīng)

30、列之和陣中與錯(cuò)誤碼元對(duì)應(yīng)列之和 如如E=00101，則伴隨式是監(jiān)督矩陣中第，則伴隨式是監(jiān)督矩陣中第3和第和第5列的和。列的和。利用這點(diǎn)可以用來糾錯(cuò)（譯碼）。利用這點(diǎn)可以用來糾錯(cuò)（譯碼）。 STHET h1en1h2en2+hne0， 這叫做這叫做伴隨式的錯(cuò)誤圖樣表示伴隨式的錯(cuò)誤圖樣表示伴隨式譯碼的基本過程伴隨式譯碼的基本過程3、根據(jù)伴隨式譯碼、根據(jù)伴隨式譯碼結(jié)束【例例8-15，P143】接例接例8-13，二元（，二元（7，3）線性）線性分組碼的監(jiān)督矩陣為分組碼的監(jiān)督矩陣為設(shè)發(fā)送碼字設(shè)發(fā)送碼字 C(1010011)試分別對(duì)三個(gè)接收碼字試分別對(duì)三個(gè)接收碼字R1=1010011、 R2=111001

31、1、 R3=0011011譯碼。譯碼。解解： 伴隨式的例子伴隨式的例子1 11011000111010011000100110001H1、接收到的碼字、接收到的碼字R(1010011)接收碼字接收碼字 R的伴隨式為的伴隨式為譯碼器判接收字無錯(cuò)，即傳輸中譯碼器判接收字無錯(cuò)，即傳輸中沒有發(fā)生錯(cuò)誤沒有發(fā)生錯(cuò)誤101011000111101000011000100011000111TTTSHR 2、接收到的碼字、接收到的碼字R(1110011) 接收碼字接收碼字 R的伴隨式為的伴隨式為ST0，譯碼器判為有錯(cuò)，譯碼器判為有錯(cuò)(7，3)碼是糾單個(gè)錯(cuò)誤的碼，且碼是糾單個(gè)錯(cuò)誤的碼，且ST等于等于H的第二列，因

32、此的第二列，因此判定接收碼字判定接收碼字R的第二位是錯(cuò)的，因此譯碼為的第二位是錯(cuò)的，因此譯碼為(1010011)由于接收字中錯(cuò)誤碼元數(shù)與碼的糾錯(cuò)能力相符，所以譯由于接收字中錯(cuò)誤碼元數(shù)與碼的糾錯(cuò)能力相符，所以譯碼正確碼正確111011000011110100101100010100110001111TTSHR 發(fā)送碼字發(fā)送碼字 C(1010011)伴隨式例伴隨式例1 1（續(xù)）（續(xù)）伴隨式例伴隨式例1 1（續(xù)）（續(xù)）發(fā)送碼字發(fā)送碼字 C(1010011)3、接收碼字、接收碼字 R(0011011)碼元錯(cuò)誤多于碼元錯(cuò)誤多于1個(gè)個(gè) 其伴隨式為其伴隨式為ST不等于不等于0，但與，但與H陣的任何一列都不相

33、同；陣的任何一列都不相同；至少是監(jiān)督矩陣兩列的和（如第至少是監(jiān)督矩陣兩列的和（如第1、4列的和或第列的和或第2、7列的列的和）和）無法判定錯(cuò)誤出在哪些位上，即此時(shí)只能發(fā)現(xiàn)有錯(cuò)無法判定錯(cuò)誤出在哪些位上，即此時(shí)只能發(fā)現(xiàn)有錯(cuò)001011000011110100111100010100110001011TTSHR 伴隨式例伴隨式例2 2【例，增例，增】(15,7)碼的生成矩陣和監(jiān)督碼的生成矩陣和監(jiān)督矩陣分別為矩陣分別為該碼可以糾正該碼可以糾正2位錯(cuò)位錯(cuò)發(fā)送碼字發(fā)送碼字C(101001100101110)如：接收碼字如：接收碼字R=(111101100101110)ST不等于不等于0，H陣的陣的第第2、

34、4列的和列的和相相同，因此同，因此錯(cuò)誤出現(xiàn)在第錯(cuò)誤出現(xiàn)在第2、4位位上，上，碼字可以糾正為碼字可以糾正為(101001100101110)10001011100010111000101110001011100010111000101110001011100010111000101111001111111011010111011110110001010110010010110100010111H111110001011001100111111111011011101110111001011000110010110010100101101000001011111110TTSHR 111010001

35、111010001111010001111010001111010001111010001111010001G8.4.7 漢明碼漢明碼l漢明碼漢明碼是是1950年由漢明提出的能夠年由漢明提出的能夠糾正糾正1位錯(cuò)碼且編碼效位錯(cuò)碼且編碼效率較高率較高的一種線性分組碼。的一種線性分組碼。l它不僅性能好而且編譯碼電路非常簡(jiǎn)單，易于工程實(shí)現(xiàn)，它不僅性能好而且編譯碼電路非常簡(jiǎn)單，易于工程實(shí)現(xiàn)，因此是工程中常用的一種糾錯(cuò)碼因此是工程中常用的一種糾錯(cuò)碼l二元漢明碼的參數(shù)二元漢明碼的參數(shù)n，k和和d分別為分別為碼長(zhǎng)：碼長(zhǎng)：n=2r-1信息位數(shù)信息位數(shù)：k=2r-r-1監(jiān)督位數(shù)：監(jiān)督位數(shù)：r=n-k最小碼距：最小

36、碼距：dmin=3l由于由于dmin=3，因此能糾正，因此能糾正1個(gè)隨機(jī)錯(cuò)誤或檢測(cè)個(gè)隨機(jī)錯(cuò)誤或檢測(cè)2個(gè)錯(cuò)誤個(gè)錯(cuò)誤漢明碼的構(gòu)造漢明碼的構(gòu)造漢明碼的監(jiān)督矩陣漢明碼的監(jiān)督矩陣H的的列為所有非零的列為所有非零的r維向量維向量組成，所以組成，所以一旦一旦r給定，就可構(gòu)造出具體的給定，就可構(gòu)造出具體的(n，k)漢明碼。漢明碼。漢明碼的構(gòu)造例子漢明碼的構(gòu)造例子【例例8-16，P145】試構(gòu)造一個(gè)二元的（試構(gòu)造一個(gè)二元的（7,4,3）漢明碼。）漢明碼。解：解：由于由于r=7-4=3因此因此H中共有中共有23-1=7列列將該監(jiān)督矩陣進(jìn)行將該監(jiān)督矩陣進(jìn)行行列交換行列交換，得到監(jiān)督矩陣的標(biāo)準(zhǔn)形，得到監(jiān)督矩陣的標(biāo)準(zhǔn)形

37、式式HQ Ir這種行列交換，對(duì)碼的性能沒有影響。此時(shí)得到的漢這種行列交換，對(duì)碼的性能沒有影響。此時(shí)得到的漢明碼為明碼為系統(tǒng)漢明碼系統(tǒng)漢明碼。000111101100111010101H011110010110101101001H列為所有非零的列為所有非零的7維向量維向量011110010110101101001H根據(jù)監(jiān)督矩陣可得到系統(tǒng)漢明碼的生成矩陣，即根據(jù)監(jiān)督矩陣可得到系統(tǒng)漢明碼的生成矩陣，即 （G=Ik P、H=Q Ir）：）： 其中：其中：PQT 或或 Q=PT得到二元的（得到二元的（7,4,3）漢明碼為）漢明碼為1111000011010010100101100001G漢明碼的構(gòu)造例子

38、（續(xù)）漢明碼的構(gòu)造例子（續(xù)）信息元碼字信息元碼字00000000 00010001000 01100010001 11110011001 10000100010 11010101010 10100110011 00110111011 01001000100 10111001100 11001010101 01011011101 00101100110 01111101110 00001110111 10011111111 1118.5 循環(huán)碼循環(huán)碼循環(huán)碼是一類循環(huán)碼是一類最主要、最有用最主要、最有用的線性分組碼；的線性分組碼；1957年年普朗格普朗格(Prange)首先開始研究循環(huán)碼；首先開始

39、研究循環(huán)碼；循環(huán)碼具有許多循環(huán)碼具有許多優(yōu)良的性質(zhì)優(yōu)良的性質(zhì)，在理論和實(shí)踐中都是十分重，在理論和實(shí)踐中都是十分重要的。要的。8.5.1 循環(huán)碼的基本概念循環(huán)碼的基本概念8.5.2 循環(huán)碼的生成多項(xiàng)式和監(jiān)督多項(xiàng)式循環(huán)碼的生成多項(xiàng)式和監(jiān)督多項(xiàng)式8.5.3 循環(huán)碼的譯碼循環(huán)碼的譯碼8.5.4 BCH碼碼8.5.5 RS碼碼8.5.1 循環(huán)碼的基本概念循環(huán)碼的基本概念設(shè)設(shè)C是一個(gè)是一個(gè)(n, k)線性碼；線性碼；如果如果C中的中的任意一個(gè)碼字經(jīng)任意循環(huán)移位之后仍然是任意一個(gè)碼字經(jīng)任意循環(huán)移位之后仍然是C中中的一個(gè)碼字的一個(gè)碼字，那么就稱此碼是一個(gè)，那么就稱此碼是一個(gè)循環(huán)碼；循環(huán)碼；循環(huán)左移與循環(huán)右移是

40、等價(jià)的循環(huán)左移與循環(huán)右移是等價(jià)的循環(huán)左移循環(huán)左移i位等于循環(huán)右移位等于循環(huán)右移n-i位位因此可以默認(rèn)循環(huán)移位為循環(huán)左移因此可以默認(rèn)循環(huán)移位為循環(huán)左移碼字碼字C=(cn-1, cn-2, , c1, c0)循環(huán)移位循環(huán)移位i位之后為位之后為C(i)(cn-i-1,cn-i-2,c0,cn-1,cn-i+1,cn-i)循環(huán)碼舉例循環(huán)碼舉例如：例如：例8-7給出的（給出的（7，3）線性分組碼是一個(gè)循環(huán)碼：）線性分組碼是一個(gè)循環(huán)碼：l碼字的多項(xiàng)式碼字的多項(xiàng)式設(shè)碼字設(shè)碼字C=(cn-1, cn-2, , c1, c0)，用各個(gè)分量作為系數(shù)，用各個(gè)分量作為系數(shù)，可以寫出一個(gè)多項(xiàng)式可以寫出一個(gè)多項(xiàng)式C(x)

41、=cn-1xn-1cn-2xn-2c1xc0則則C(x)就是相應(yīng)就是相應(yīng)碼字的多項(xiàng)式；碼字的多項(xiàng)式；碼字碼字C與多項(xiàng)式與多項(xiàng)式C(x)是一一對(duì)應(yīng)的。是一一對(duì)應(yīng)的。循環(huán)碼的碼字多項(xiàng)式循環(huán)碼的碼字多項(xiàng)式l碼字循環(huán)移位之后，碼字多項(xiàng)式的變化碼字循環(huán)移位之后，碼字多項(xiàng)式的變化(選選3個(gè)編碼為例個(gè)編碼為例)：C1(0111010)的多項(xiàng)式的多項(xiàng)式C1(x)= x5+x4+x3+x C2(1110100)的多項(xiàng)式的多項(xiàng)式C2(x)= x6+x5+x4+x2C3(1101001)的多項(xiàng)式的多項(xiàng)式C3(x)= x6+x5+x3+1三者的關(guān)系為三者的關(guān)系為C2(x)= xC1(x)=C1(1)(x)，C3(x)

42、= x2C1(x) mod (x7+1)= C1(2)(x)l這表明這表明C(i)(x)xiC(x) mod (xn1)C(x)乘以乘以xi的目的是左移的目的是左移i位，對(duì)位，對(duì)xn+1取余式的目的是循取余式的目的是循環(huán)環(huán)左移左移循環(huán)循環(huán)循環(huán)碼的多項(xiàng)式舉例循環(huán)碼的多項(xiàng)式舉例【例，增例，增】(7，3)循環(huán)碼可由任一個(gè)碼字，比如循環(huán)碼可由任一個(gè)碼字，比如0011101經(jīng)過循環(huán)經(jīng)過循環(huán)移位，得到其他移位，得到其他6個(gè)非個(gè)非0碼字碼字 (7，3)循環(huán)碼也可由碼多項(xiàng)式循環(huán)碼也可由碼多項(xiàng)式x4+x3x21，乘以，乘以xi ，再，再模模x71得到其他得到其他6個(gè)非個(gè)非0碼多項(xiàng)式碼多項(xiàng)式8.5.2 循環(huán)碼的生

43、成多項(xiàng)式和監(jiān)督多項(xiàng)式循環(huán)碼的生成多項(xiàng)式和監(jiān)督多項(xiàng)式1、生成多項(xiàng)式、生成多項(xiàng)式循環(huán)碼可由一個(gè)非零碼字經(jīng)過循環(huán)移位得到其他非循環(huán)碼可由一個(gè)非零碼字經(jīng)過循環(huán)移位得到其他非0碼字；碼字；因此在因此在(n，k)循環(huán)碼的循環(huán)碼的2k個(gè)碼多項(xiàng)式中，只要給出一個(gè)就個(gè)碼多項(xiàng)式中，只要給出一個(gè)就可以推得其它可以推得其它選擇其中前選擇其中前k-1位皆為位皆為0的碼多項(xiàng)式的碼多項(xiàng)式g(x) (次數(shù)次數(shù)rn-k)，這，這個(gè)多項(xiàng)式叫做個(gè)多項(xiàng)式叫做(n，k)循環(huán)碼的循環(huán)碼的生成多項(xiàng)式生成多項(xiàng)式g(x)gn-k xn-kgn-k-1xn-k-1 g1xg0生成多項(xiàng)式的性質(zhì)生成多項(xiàng)式的性質(zhì)g(x)gn-k xn-kgn-k-1

44、xn-k-1 g1xg0生成多項(xiàng)式的次數(shù)為生成多項(xiàng)式的次數(shù)為n-k；生成多項(xiàng)式是生成多項(xiàng)式是(n,k)線性分組碼的所有非零碼多項(xiàng)式中，次線性分組碼的所有非零碼多項(xiàng)式中，次數(shù)最低的多項(xiàng)式；數(shù)最低的多項(xiàng)式；在在(n,k)循環(huán)碼中，循環(huán)碼中，g(x)是唯一的是唯一的n-k次多項(xiàng)式；次多項(xiàng)式；生成多項(xiàng)式生成多項(xiàng)式g(x)一定是一定是xn+1的因式。的因式。 因此，分解因此，分解xn+1，其中次數(shù)為，其中次數(shù)為n-k的因式就是生成多項(xiàng)式的因式就是生成多項(xiàng)式說明說明說明說明生成多項(xiàng)式的構(gòu)造生成多項(xiàng)式的構(gòu)造分解多項(xiàng)式分解多項(xiàng)式 x7+1=(x+1)(x3+x2+1)(x3+x+1)因此生成多項(xiàng)式為：因此生成

45、多項(xiàng)式為：g1(x)=(x+1)(x3+x2+1)=x4+x2+x+1或者或者 g2(x)=(x+1)(x3+x+1)=x4+x3+x2+1【例例8-17，P147】求求(7,3)循環(huán)碼的生成多項(xiàng)式。循環(huán)碼的生成多項(xiàng)式。解：解：00000000111001001011111100100101110110010110111001001011由由g1(x)生成的循環(huán)碼生成的循環(huán)碼00000001101001001110110100110111010010011111101001001110由由g2(x)生成的循環(huán)碼生成的循環(huán)碼l如果如果g(x)為為(n，k)循環(huán)碼的生成多項(xiàng)式，則必為循環(huán)碼的生成多

46、項(xiàng)式，則必為xn1的因式，的因式，因此因此xn1h(x)g(x)l如果多項(xiàng)式如果多項(xiàng)式h(x)滿足滿足xn1h(x)g(x)，且，且hk1, h0，則稱，則稱h(x)為為(n，k)循環(huán)碼的循環(huán)碼的監(jiān)督多項(xiàng)式監(jiān)督多項(xiàng)式h(x)hkxkhk-xk-h1xh0l對(duì)偶碼對(duì)偶碼以以n-k次多項(xiàng)式次多項(xiàng)式g(x)為生成多項(xiàng)式，則生成一個(gè)為生成多項(xiàng)式，則生成一個(gè)(n，k)循環(huán)循環(huán)碼碼以以h(x)為生成多項(xiàng)式，則生成為生成多項(xiàng)式，則生成(n，n-k)循環(huán)碼循環(huán)碼這兩個(gè)循環(huán)碼互為對(duì)偶碼這兩個(gè)循環(huán)碼互為對(duì)偶碼2、監(jiān)督多項(xiàng)式、監(jiān)督多項(xiàng)式生成矩陣生成矩陣(n,k)循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式g(x) 經(jīng)經(jīng)k-

47、1次循環(huán)移位次循環(huán)移位，共得到，共得到k個(gè)個(gè)碼多項(xiàng)式：碼多項(xiàng)式： g(x)，xg(x)，xk-1g(x)這這k個(gè)碼多項(xiàng)式的系數(shù)可作為個(gè)碼多項(xiàng)式的系數(shù)可作為生成矩陣生成矩陣G(x)的的k行行，即，即110200( ).( ).( ).( ).1( )knn kkn kn kxg xggxxg xggG xxxg xggg x 3、生成矩陣和監(jiān)督矩陣、生成矩陣和監(jiān)督矩陣生成矩陣舉例生成矩陣舉例解：解：3643253242365432654326543265432( )( )( )( )( )1101100001011000010110000011x g xxxxx g xxxxG xxg xxxx

48、g xxxxxxxxxxxxxxxxxxxxxxxxxxx【例，增例，增】設(shè)設(shè)(7, 4)循環(huán)碼循環(huán)碼的生成多項(xiàng)式的生成多項(xiàng)式g(x)x3x1，求其生，求其生成矩陣成矩陣G。1011000010110000101100001011G監(jiān)督矩陣監(jiān)督矩陣(n，k)循環(huán)碼的監(jiān)督多項(xiàng)式為循環(huán)碼的監(jiān)督多項(xiàng)式為h(x)hkxkhk-xk-h1xh0則則(n，k)循環(huán)碼的循環(huán)碼的監(jiān)督矩陣監(jiān)督矩陣為為011011011000000kkkkkkhhhhhhhhHhhhh 循環(huán)碼的生成矩陣、監(jiān)督矩陣舉例循環(huán)碼的生成矩陣、監(jiān)督矩陣舉例(7，3)碼：碼：x71(x3x1)(x4x2x1)4次多項(xiàng)式為生成多項(xiàng)式：次多項(xiàng)式

49、為生成多項(xiàng)式： g(x)x4x2x1g4x4g3x3g2x2g1xg03次多項(xiàng)式則是監(jiān)督多項(xiàng)式：次多項(xiàng)式則是監(jiān)督多項(xiàng)式： h(x)x3x1h3x3h2x2h1xh0則生成矩陣和監(jiān)督矩陣分別為則生成矩陣和監(jiān)督矩陣分別為(7,3)101110001011100010111G(7,3)0001101001101001101001101000H【例例8-18，P148】求求(7,3)循環(huán)碼的生成多項(xiàng)式、監(jiān)督多項(xiàng)循環(huán)碼的生成多項(xiàng)式、監(jiān)督多項(xiàng)式、生成矩陣、監(jiān)督矩陣。式、生成矩陣、監(jiān)督矩陣。解：解：8.5.3 循環(huán)碼的譯碼循環(huán)碼的譯碼l循環(huán)碼的譯碼包括三個(gè)步驟循環(huán)碼的譯碼包括三個(gè)步驟計(jì)算伴隨式計(jì)算伴隨式求伴

50、隨式對(duì)應(yīng)的錯(cuò)誤圖樣求伴隨式對(duì)應(yīng)的錯(cuò)誤圖樣用錯(cuò)誤圖樣糾錯(cuò)（譯碼）用錯(cuò)誤圖樣糾錯(cuò)（譯碼）l相比于一般線性分組碼，循環(huán)碼的譯碼更加簡(jiǎn)單相比于一般線性分組碼，循環(huán)碼的譯碼更加簡(jiǎn)單易行易行伴隨式伴隨式一般線性分組碼的伴隨式（矩陣形式）：一般線性分組碼的伴隨式（矩陣形式）：S=RHT或或ST=HRT，這對(duì)循環(huán)碼也是適用的；這對(duì)循環(huán)碼也是適用的；循環(huán)碼伴隨式的特殊求法（多項(xiàng)式形式）循環(huán)碼伴隨式的特殊求法（多項(xiàng)式形式）S(x)R(x) mod g(x)即循環(huán)碼的伴隨式是接收多項(xiàng)式即循環(huán)碼的伴隨式是接收多項(xiàng)式R(x)除以除以g(x)的余式的余式循環(huán)碼譯碼例循環(huán)碼譯碼例接收到碼字：接收到碼字：R(x)=x6+x3

51、+x+1S(x)R(x) mod g(x)=x2+1，即，即S=1 0 1T而而h(x)=x7+1/g(x)=x4+x2+x+1，即，即伴隨式是監(jiān)督矩陣的第一列，因此碼字的第伴隨式是監(jiān)督矩陣的第一列，因此碼字的第1位出錯(cuò)位出錯(cuò)，譯，譯碼為碼為0001011，正確譯碼，正確譯碼001110111010010111010011101011101001110100H【例例8-19，P148】一個(gè)一個(gè)(7,4)循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式g(x)x3+x+1 ，一個(gè)碼字為，一個(gè)碼字為0001011，若該碼字在傳輸過程中，若該碼字在傳輸過程中發(fā)生錯(cuò)誤，接收到的碼字變?yōu)榘l(fā)生錯(cuò)誤，接收到的碼字變?yōu)?

52、001011，試對(duì)其譯碼。，試對(duì)其譯碼。解：解：8.5.4 BCH碼碼l是一種獲得廣泛應(yīng)用的能夠糾正多個(gè)隨機(jī)錯(cuò)碼的循環(huán)碼，是一種獲得廣泛應(yīng)用的能夠糾正多個(gè)隨機(jī)錯(cuò)碼的循環(huán)碼，是迄今為止所發(fā)現(xiàn)的一類性能較優(yōu)的碼；是迄今為止所發(fā)現(xiàn)的一類性能較優(yōu)的碼；lBCH碼的重要性在于它解決了生成多項(xiàng)式與糾錯(cuò)能力的關(guān)碼的重要性在于它解決了生成多項(xiàng)式與糾錯(cuò)能力的關(guān)系問題系問題lBCH的歷史（是以的歷史（是以3位發(fā)明這種碼的人名位發(fā)明這種碼的人名(Bose - Chaudhuri - Hocguenghem)命名的）命名的）1959年霍昆格姆年霍昆格姆(Hocgenghem)和和1960年博斯年博斯(Bose)及查及

53、查德胡里德胡里(Chaudhuri)分別提出的糾正多個(gè)隨機(jī)錯(cuò)誤的循分別提出的糾正多個(gè)隨機(jī)錯(cuò)誤的循環(huán)碼，稱為環(huán)碼，稱為BCH碼碼1960年彼得森年彼得森(Pelerson)找到了二元找到了二元BCH碼的第一個(gè)有碼的第一個(gè)有效算法，后經(jīng)多人的推廣和改進(jìn)效算法，后經(jīng)多人的推廣和改進(jìn)1967年由伯利坎普年由伯利坎普(Berlekamp)提出了提出了BCH碼譯碼的迭碼譯碼的迭代算法，從而將代算法，從而將BCH碼由理論研究推向?qū)嶋H應(yīng)用階段，碼由理論研究推向?qū)嶋H應(yīng)用階段，使它成為應(yīng)用廣泛而有效的一類線性碼使它成為應(yīng)用廣泛而有效的一類線性碼BCHBCH碼的基本參數(shù)碼的基本參數(shù)l對(duì)任何正整數(shù)對(duì)任何正整數(shù)m( 3

54、)和和t(2m-1)，存在一個(gè)二元，存在一個(gè)二元BCH碼，碼，具有下面的參數(shù)具有下面的參數(shù)碼長(zhǎng)：碼長(zhǎng)：n=2m-1一致校驗(yàn)位的數(shù)目：一致校驗(yàn)位的數(shù)目：n-k mt最小碼距：最小碼距：dmin 2t+1能糾正能糾正n=2m-1個(gè)碼元中任意不超過個(gè)碼元中任意不超過t個(gè)錯(cuò)誤個(gè)錯(cuò)誤l即給定符合條件即給定符合條件m 3、t2m-1的的m和和t之后，總能設(shè)計(jì)之后，總能設(shè)計(jì)出一個(gè)二元出一個(gè)二元BCH，滿足碼長(zhǎng)為，滿足碼長(zhǎng)為2m-1，并能糾正，并能糾正t個(gè)隨個(gè)隨機(jī)錯(cuò)誤。機(jī)錯(cuò)誤。1、BCH碼的生成多項(xiàng)式和參數(shù)碼的生成多項(xiàng)式和參數(shù)BCHBCH碼的定義碼的定義g(x)是一個(gè)循環(huán)碼的生成多項(xiàng)式，如果是一個(gè)循環(huán)碼的生成

55、多項(xiàng)式，如果g(x)=0的根的根中包括中包括2t個(gè)連續(xù)根個(gè)連續(xù)根 , 2, 3, , 2t，則由，則由g(x)生成生成的循環(huán)碼叫做的循環(huán)碼叫做BCH碼。碼。此時(shí)此時(shí)g(x)=(x- )(x- 2)(x- 2t)=0如何構(gòu)造出滿足該條件的生成多項(xiàng)式如何構(gòu)造出滿足該條件的生成多項(xiàng)式g(x)是比較是比較困難的，有興趣的同學(xué)可以自學(xué)困難的，有興趣的同學(xué)可以自學(xué)nktg(x)（八進(jìn)制）74113151112315727211553246731261453121235513116310765731115542332531673133650473126175635711032、部分常用、部分常用BCH碼的生

56、成多項(xiàng)式碼的生成多項(xiàng)式說明：說明：(721)8=111 010 0011)(4678xxxxxg【例例8-20，P150】對(duì)對(duì)(7,4)BCH碼，一個(gè)碼字為碼，一個(gè)碼字為1101001，若該碼，若該碼字在傳輸過程中發(fā)生錯(cuò)誤，接收到的碼字變?yōu)樽衷趥鬏斶^程中發(fā)生錯(cuò)誤，接收到的碼字變?yōu)?101000，試對(duì)，試對(duì)其譯碼。其譯碼。解：解：(13)8=0010111011000010110000101100001011G1000101010011100101100001011GBCHBCH碼舉例碼舉例nktg(x)（八進(jìn)制）74113 （001011）151112315727211553246731261

57、45312123551311631076573111554233251)(3xxxg則生成矩陣為則生成矩陣為初等變換為系統(tǒng)碼生成矩陣為初等變換為系統(tǒng)碼生成矩陣為1000101010011100101100001011G111010001110101101001H 如果信息元為如果信息元為1101，則對(duì)應(yīng)的碼字為則對(duì)應(yīng)的碼字為1101001 如果接收到的碼字如果接收到的碼字為為1101000，則伴隨，則伴隨式為式為001，是監(jiān)督矩，是監(jiān)督矩陣的最后一列，則陣的最后一列，則譯碼結(jié)果為譯碼結(jié)果為1101001BCHBCH碼舉例（續(xù)）碼舉例（續(xù)）監(jiān)督矩陣監(jiān)督矩陣H為為（G=Ik P、H=Q Ir）：）

58、： 其中：其中：PQT 或或 Q=PT因此伴隨式為因此伴隨式為1000001011100101101011100010111TTHRS8.5.5 RS碼碼l里德里德-索羅蒙（索羅蒙（Reed-Solomon）碼，簡(jiǎn)稱）碼，簡(jiǎn)稱RS碼碼lRS碼是碼是q元元BCH碼碼編碼方式類似編碼方式類似RS碼是以數(shù)據(jù)塊進(jìn)行編碼碼是以數(shù)據(jù)塊進(jìn)行編碼l例如例如如果如果q=4，數(shù)據(jù)塊的長(zhǎng)度就是，數(shù)據(jù)塊的長(zhǎng)度就是2如果如果q=8，數(shù)據(jù)塊的長(zhǎng)度就是，數(shù)據(jù)塊的長(zhǎng)度就是3lRS碼即可以糾隨機(jī)錯(cuò)誤，又可以糾突發(fā)錯(cuò)誤。碼即可以糾隨機(jī)錯(cuò)誤，又可以糾突發(fā)錯(cuò)誤。8.6 卷積碼卷積碼8.6.1 卷積碼的基本概念和基本原理卷積碼的基本概

59、念和基本原理8.6.2 卷積碼的編碼卷積碼的編碼8.6.3 卷積碼的矩陣表述卷積碼的矩陣表述1955年埃里亞斯年埃里亞斯(Elias)最早提出卷積碼的概念最早提出卷積碼的概念卷積碼卷積碼(又稱連環(huán)碼又稱連環(huán)碼)指的是在任意給定時(shí)刻，編碼器輸指的是在任意給定時(shí)刻，編碼器輸出的出的n0個(gè)碼元中，每一個(gè)碼元不僅和此時(shí)刻輸入的個(gè)碼元中，每一個(gè)碼元不僅和此時(shí)刻輸入的k0個(gè)個(gè)信息元有關(guān)，還與前面連續(xù)信息元有關(guān)，還與前面連續(xù)m0個(gè)時(shí)刻輸入的信息元有關(guān)，個(gè)時(shí)刻輸入的信息元有關(guān)，可以用（可以用（n0, k0, m0）表示；）表示；8.6.1 卷積碼的基本概念和基本原理卷積碼的基本概念和基本原理幾點(diǎn)說明：幾點(diǎn)說明

60、：典型的卷積碼一般選較小的典型的卷積碼一般選較小的n0和和k0(k0n0)，但存儲(chǔ)器數(shù)，但存儲(chǔ)器數(shù)m0則取較大的值則取較大的值(m010)卷積碼的編碼效率為卷積碼的編碼效率為Rk0/n0在同樣的編碼效率在同樣的編碼效率R下，卷積碼的性能優(yōu)于分組碼，至下，卷積碼的性能優(yōu)于分組碼，至少不低于分組碼少不低于分組碼但是卷積碼不像分組碼有嚴(yán)格的代數(shù)結(jié)構(gòu)，至今沒有嚴(yán)但是卷積碼不像分組碼有嚴(yán)格的代數(shù)結(jié)構(gòu)，至今沒有嚴(yán)密的數(shù)學(xué)手段將糾錯(cuò)能力與碼的結(jié)構(gòu)十分有規(guī)律的聯(lián)系密的數(shù)學(xué)手段將糾錯(cuò)能力與碼的結(jié)構(gòu)十分有規(guī)律的聯(lián)系起來。起來。8.6.2 卷積碼的編碼卷積碼的編碼設(shè)卷積碼編碼器輸入碼序列為設(shè)卷積碼編碼器輸入碼序列為