通信原理樊昌信版第11章差錯(cuò)控制編碼2

1、1第第1111章章 差錯(cuò)控制編碼差錯(cuò)控制編碼11.1 概述概述11.2 糾錯(cuò)編碼的基本原理糾錯(cuò)編碼的基本原理11.3 糾錯(cuò)編碼的性能糾錯(cuò)編碼的性能11.4 簡(jiǎn)單的實(shí)用編碼簡(jiǎn)單的實(shí)用編碼11.5 線性分組碼線性分組碼11.6 循環(huán)碼循環(huán)碼211.5 11.5 線性分組碼線性分組碼 (1) 分組碼分組碼： 先將信息碼分組，然后給每組信碼附加若干先將信息碼分組，然后給每組信碼附加若干監(jiān)督碼的編碼稱為分組碼，用符號(hào)監(jiān)督碼的編碼稱為分組碼，用符號(hào)(n,k)表示，表示，k是信息碼的位數(shù)，是信息碼的位數(shù)，n是編碼組總位數(shù)，又稱為是編碼組總位數(shù)，又稱為碼長(zhǎng)，碼長(zhǎng)，r = n-k為監(jiān)督位數(shù)。為監(jiān)督位數(shù)。 (2)

2、 代數(shù)碼代數(shù)碼： 建立在代數(shù)學(xué)基礎(chǔ)上的編碼稱為代數(shù)碼。例建立在代數(shù)學(xué)基礎(chǔ)上的編碼稱為代數(shù)碼。例如奇偶校驗(yàn)碼。如奇偶校驗(yàn)碼。 1、基本概念、基本概念3 (3) 線性碼線性碼： 線性碼中信息位和監(jiān)督位是按一組線性碼中信息位和監(jiān)督位是按一組線性方線性方程程構(gòu)成的。線性碼是一種代數(shù)碼。奇偶監(jiān)督構(gòu)成的。線性碼是一種代數(shù)碼。奇偶監(jiān)督碼是最簡(jiǎn)單的線性碼。碼是最簡(jiǎn)單的線性碼。(4) 線性分組碼線性分組碼： 信息碼分組后，附加的監(jiān)督碼和信息碼由信息碼分組后，附加的監(jiān)督碼和信息碼由一些線性代數(shù)方程聯(lián)系著的編碼稱為線性分一些線性代數(shù)方程聯(lián)系著的編碼稱為線性分組碼。組碼。42、線性分組碼的性質(zhì)、線性分組碼的性質(zhì)任意兩

3、個(gè)許用碼組之和（對(duì)應(yīng)位模任意兩個(gè)許用碼組之和（對(duì)應(yīng)位模2和加）和加）仍為一許用碼組，即具有仍為一許用碼組，即具有封閉性封閉性。最小碼距最小碼距=非零碼的最小碼重非零碼的最小碼重 (1的個(gè)數(shù)的個(gè)數(shù))。5 以漢明碼為例來說明編碼原理。以漢明碼為例來說明編碼原理。 漢明碼是一種能夠糾正一位錯(cuò)碼且編碼效漢明碼是一種能夠糾正一位錯(cuò)碼且編碼效率較高的線性分組碼。率較高的線性分組碼。3、線性分組碼的編碼原理、線性分組碼的編碼原理6（1）回憶奇偶監(jiān)督偶校驗(yàn)碼）回憶奇偶監(jiān)督偶校驗(yàn)碼 發(fā)送端編碼：將一位監(jiān)督碼元附加在信息發(fā)送端編碼：將一位監(jiān)督碼元附加在信息碼元后，使得碼元中碼元后，使得碼元中“1”碼元個(gè)數(shù)為偶數(shù)。

4、碼元個(gè)數(shù)為偶數(shù)。 接收端譯碼：接收端譯碼：計(jì)數(shù)接收碼組中計(jì)數(shù)接收碼組中“1”碼元個(gè)數(shù)是否為偶數(shù)，碼元個(gè)數(shù)是否為偶數(shù)，即計(jì)算：即計(jì)算： (11.5-1)S=0認(rèn)為沒錯(cuò)，認(rèn)為沒錯(cuò)，S=1認(rèn)為有錯(cuò)。認(rèn)為有錯(cuò)。(11.5-1)式稱為式稱為監(jiān)督方程監(jiān)督方程/監(jiān)督關(guān)系式監(jiān)督關(guān)系式，S 稱為稱為校校正子正子/校驗(yàn)子校驗(yàn)子/伴隨式伴隨式。0121aaaaSnn7 監(jiān)督位增加到監(jiān)督位增加到2位：有兩個(gè)監(jiān)督方程，兩個(gè)位：有兩個(gè)監(jiān)督方程，兩個(gè)校正子；校正子； 兩個(gè)校正子組合有四種（兩個(gè)校正子組合有四種（00表示無錯(cuò)，表示無錯(cuò)，01、10、11表示表示1位錯(cuò)碼的位錯(cuò)碼的3種可能位置）種可能位置） 監(jiān)督位增加到監(jiān)督位增

5、加到r位：可指示位：可指示1位錯(cuò)碼的位錯(cuò)碼的(2r-1)個(gè)個(gè)可能位置可能位置對(duì)于對(duì)于(n,k)分組碼，若用分組碼，若用r=n-k個(gè)監(jiān)督位構(gòu)造出個(gè)監(jiān)督位構(gòu)造出的的r個(gè)監(jiān)督關(guān)系式來指示個(gè)監(jiān)督關(guān)系式來指示1位錯(cuò)碼的位錯(cuò)碼的n種可能位種可能位置，則要求：置，則要求： 可以這樣來考慮可以這樣來考慮:2r-1n 即即2r k+r+1 (11.5-2)8欲糾正一位錯(cuò)碼，由欲糾正一位錯(cuò)碼，由（11.5-2）式知式知r 3。取取r=3，則，則n=k+r=7設(shè)設(shè)7位碼元為：位碼元為：a6 a5 a4 a3 a2 a1 a0；三個(gè)伴隨式：三個(gè)伴隨式：S1、S2、S3；可規(guī)定可規(guī)定S1S2S3的八種組合與一位錯(cuò)碼的對(duì)

6、應(yīng)的八種組合與一位錯(cuò)碼的對(duì)應(yīng)關(guān)系（也可規(guī)定為另一種對(duì)應(yīng)關(guān)系）：關(guān)系（也可規(guī)定為另一種對(duì)應(yīng)關(guān)系）：構(gòu)造一構(gòu)造一 (n, k) 分組碼，分組碼，k=4并能糾正一位錯(cuò)碼并能糾正一位錯(cuò)碼(2) 漢明碼的構(gòu)造漢明碼的構(gòu)造2r-1n 即即2r k+r+1 （11.5-2）9S1 S2 S3錯(cuò)碼位置錯(cuò)碼位置S1 S2 S3錯(cuò)碼位置錯(cuò)碼位置0 0 1a01 0 1a40 1 0a11 1 0a51 0 0a21 1 1a60 1 1a30 0 0無錯(cuò)碼無錯(cuò)碼僅當(dāng)一位錯(cuò)碼的位置在僅當(dāng)一位錯(cuò)碼的位置在a2、a4、a5或或a6時(shí)，校時(shí)，校正子正子S1為為1；否則；否則S1為零。這就意味著為零。這就意味著a2、a4、

7、a5和和a6四個(gè)碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：四個(gè)碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：24561aaaaS10S1 S2 S3錯(cuò)碼位置錯(cuò)碼位置S1 S2 S3錯(cuò)碼位置錯(cuò)碼位置0 0 1a01 0 1a40 1 0a11 1 0a51 0 0a21 1 1a60 1 1a30 0 0無錯(cuò)碼無錯(cuò)碼24561aaaaS13562aaaaS03463aaaaS以及以及a0、a3、a4 和和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系構(gòu)成偶數(shù)監(jiān)督關(guān)系:同理，同理， a1、a3、a5和和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系：構(gòu)成偶數(shù)監(jiān)督關(guān)系：24561aaaaS13562aaaaS11（3）發(fā)端編碼的原則）發(fā)端編碼的原則 信息碼元信息碼元a6、a5、a4、a3來源于

8、待編碼的來源于待編碼的信息序列；信息序列； 監(jiān)督碼元監(jiān)督碼元 a2、a1、 a0的取值應(yīng)的取值應(yīng)根據(jù)信息碼根據(jù)信息碼元按監(jiān)督關(guān)系式來決定，即使前面三式中元按監(jiān)督關(guān)系式來決定，即使前面三式中的的S1、S2、S3均為均為0：000034613562456aaaaaaaaaaaa034631356224561aaaaSaaaaSaaaaS12000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa上式經(jīng)過移項(xiàng)運(yùn)算，解出監(jiān)督位上式經(jīng)過移項(xiàng)運(yùn)算，解出監(jiān)督位: 給定信息位后，可以直接按上式算出監(jiān)督給定信息位后，可以直接按上式算出監(jiān)督位，位， 結(jié)果見下表：結(jié)果見

9、下表：13信息位信息位a6 a5 a4 a3監(jiān)督位監(jiān)督位a2 a1 a0信息位信息位a6 a5 a4 a3監(jiān)督位監(jiān)督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111346035614562aaaaaaaaaaaa034631356224561aaaaSaaaaSaaaaS14該漢明碼的編碼效率較高該漢明碼的編碼效率較高=k/n = (n - r) /n =1 r/n，故當(dāng)故當(dāng)n很大和很大和r很小時(shí)，很小

10、時(shí)，碼率接近碼率接近1?？梢?，漢明碼是一種高效碼?？梢姡瑵h明碼是一種高效碼。 =k/n=4/757% 該碼的該碼的最小碼距為最小碼距為3，能糾正一個(gè)錯(cuò)碼或檢測(cè)，能糾正一個(gè)錯(cuò)碼或檢測(cè)兩個(gè)錯(cuò)碼。兩個(gè)錯(cuò)碼。設(shè)收到碼組設(shè)收到碼組0000011，按監(jiān)督方程計(jì)算可得：，按監(jiān)督方程計(jì)算可得：S1=0，S2=1，S3=1；根據(jù)校正子組合與一位錯(cuò)碼；根據(jù)校正子組合與一位錯(cuò)碼位置的對(duì)應(yīng)關(guān)系，查表可知錯(cuò)碼發(fā)生在位置的對(duì)應(yīng)關(guān)系，查表可知錯(cuò)碼發(fā)生在a3位，并位，并加以糾正。加以糾正。000101115（4）監(jiān)督矩陣（）監(jiān)督矩陣（ H 矩陣）矩陣）000034613562456aaaaaaaaaaaa上面上面(7, 4)

11、漢明碼的例子有漢明碼的例子有:現(xiàn)在將上面它改寫為現(xiàn)在將上面它改寫為:010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa上式中已經(jīng)將上式中已經(jīng)將“ ”簡(jiǎn)寫成簡(jiǎn)寫成“+”。160001001101010101100101110123456aaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa上式可以表示成如下矩陣形式：上式可以表示成如下矩陣形式：17H稱為線性碼監(jiān)督矩陣。稱為線性碼監(jiān)督矩陣。只要監(jiān)督矩陣只要監(jiān)督矩陣H 給定，給

12、定，編碼時(shí)監(jiān)督位和信息位的關(guān)系就完全確定了。編碼時(shí)監(jiān)督位和信息位的關(guān)系就完全確定了。 可化簡(jiǎn)為：可化簡(jiǎn)為：HAT=0T 或或AHT=0A = a6 a5 a4 a3 a2 a1 a0 0 = 000101100111010101110100H0001001101010101100101110123456aaaaaaa18監(jiān)督矩陣監(jiān)督矩陣H 特點(diǎn)：特點(diǎn)：001101101011011001110H1) H 的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，它等于的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，它等于監(jiān)督位的數(shù)目監(jiān)督位的數(shù)目r。H的每行中的每行中“1”的位置表示的位置表示相應(yīng)碼元之間存在的監(jiān)督關(guān)系。相應(yīng)碼元之間存在的監(jiān)督關(guān)

13、系。H矩陣可以矩陣可以分成兩部分，例如分成兩部分，例如P 為為r k 階矩陣，階矩陣，Ir為為r r 階單位方陣。我階單位方陣。我們將具有們將具有P Ir形式的形式的H 矩陣稱為矩陣稱為典型陣典型陣。rPI192) 由代數(shù)理論可知，由代數(shù)理論可知，H矩陣的各行應(yīng)該是線性矩陣的各行應(yīng)該是線性無關(guān)的無關(guān)的，否則將得不到，否則將得不到 r 個(gè)線性無關(guān)的監(jiān)督關(guān)個(gè)線性無關(guān)的監(jiān)督關(guān)系式，從而也得不到系式，從而也得不到 r 個(gè)獨(dú)立的監(jiān)督位。若一個(gè)獨(dú)立的監(jiān)督位。若一矩陣能寫成典型陣形式矩陣能寫成典型陣形式P Ir，則其各行一定，則其各行一定是線性無關(guān)的。因?yàn)槿菀昨?yàn)證是線性無關(guān)的。因?yàn)槿菀昨?yàn)證Ir的各行是線的各

14、行是線性無關(guān)的，故性無關(guān)的，故P Ir的各行也是線性無關(guān)的。的各行也是線性無關(guān)的。rPIH001101101011011001110203456012101111011110aaaaaaa346035614562aaaaaaaaaaaa(5) 生成矩陣生成矩陣( G 矩陣矩陣 ) 漢明碼例子中的監(jiān)督位公式為漢明碼例子中的監(jiān)督位公式為:可以改寫成矩陣形式：可以改寫成矩陣形式： Q34563456012011101110111aaaaaaaaaaa或者寫成或者寫成:21 Q34563456012011101110111aaaaaaaaaaaTaaaaP3456rPIH001101101011011

15、001110式中式中Q為一個(gè)為一個(gè)k r階矩陣，為階矩陣，為P的轉(zhuǎn)置，的轉(zhuǎn)置，Q = PT 上式表示，在信息位給定后，用信息位的行矩上式表示，在信息位給定后，用信息位的行矩陣乘矩陣陣乘矩陣Q就產(chǎn)生出監(jiān)督位。就產(chǎn)生出監(jiān)督位。011101110111Q22將將Q 的左邊加上的左邊加上1個(gè)個(gè)k k 階單位方陣，構(gòu)成矩階單位方陣，構(gòu)成矩陣陣GQGkI IG 稱為稱為生成矩陣生成矩陣，由它可以產(chǎn)生整個(gè)碼組，由它可以產(chǎn)生整個(gè)碼組:G34560123456aaaaaaaaaaaGA3456aaaa或者或者: Tkk1 0 0 0 1 1 10 1 0 0 1 1 0G IQ IP0 0 1 0 1 0 10

16、 0 0 1 0 1 1 生生 成成 矩矩 陣陣23G34560123456aaaaaaaaaaaGA3456aaaa或者或者 如果找到了碼的生成矩陣如果找到了碼的生成矩陣G，則編碼的方法，則編碼的方法就完全確定了。具有就完全確定了。具有IkQ形式的生成矩陣稱為形式的生成矩陣稱為典型生成矩陣典型生成矩陣。由典型生成矩陣得出的碼組。由典型生成矩陣得出的碼組A中，信息位的位置不變，監(jiān)督位附加于其后。中，信息位的位置不變，監(jiān)督位附加于其后。這種形式的碼稱為這種形式的碼稱為系統(tǒng)碼系統(tǒng)碼。 QGkI I24(6) G 矩陣的性質(zhì)矩陣的性質(zhì) G矩陣的各行是線性無關(guān)的。矩陣的各行是線性無關(guān)的。實(shí)際上，實(shí)際上

17、，G的各行本身就是一個(gè)碼組。因此，的各行本身就是一個(gè)碼組。因此，如果已有如果已有k個(gè)線性無關(guān)的碼組，則可以用其作個(gè)線性無關(guān)的碼組，則可以用其作為生成矩陣為生成矩陣G，并由它生成其余碼組。，并由它生成其余碼組。QGkI IG34560123456aaaaaaaaaaa Tkk1 0 0 0 1 1 10 1 0 0 1 1 0G IQ IP0 0 1 0 1 0 10 0 0 1 0 1 1 生生 成成 矩矩 陣陣250121bbbbnnB(7) 錯(cuò)碼矩陣和錯(cuò)誤圖樣錯(cuò)碼矩陣和錯(cuò)誤圖樣設(shè)發(fā)送碼組為設(shè)發(fā)送碼組為A，接收碼組為，接收碼組為B，0121aaaannA0121eeeeABnnE則錯(cuò)誤矩陣：

18、則錯(cuò)誤矩陣： (模模2)iiiiiiiabababe當(dāng)當(dāng)10260121eeeennEiiiiiiiabababe當(dāng)當(dāng), 1, 0B A = E (模模2) B A = E 可以改寫成可以改寫成 B = A + E 例例: 若發(fā)送碼組若發(fā)送碼組A = 1000111， 錯(cuò)碼矩陣錯(cuò)碼矩陣E = 0000100， 則接收碼組則接收碼組B = 1000011。 錯(cuò)碼矩陣有時(shí)也稱為錯(cuò)碼矩陣有時(shí)也稱為錯(cuò)誤圖樣錯(cuò)誤圖樣。27當(dāng)接收碼組有錯(cuò)且未超過檢錯(cuò)能力時(shí)，將當(dāng)接收碼組有錯(cuò)且未超過檢錯(cuò)能力時(shí)，將B當(dāng)當(dāng)作作A代入上式，不成立，即其右端不等于代入上式，不成立，即其右端不等于0。假設(shè)這時(shí)該式的右端為假設(shè)這時(shí)該式

19、的右端為S，即，即B H T = S將將B = A + E代入上式，可得：代入上式，可得：校正子校正子SAHT = 0 B A = E (模模2)S = (A + E) HT = A HT + E HT= E HTS稱為校正子。它能用來指示錯(cuò)碼的位置。稱為校正子。它能用來指示錯(cuò)碼的位置。S和錯(cuò)碼和錯(cuò)碼E之間有確定的線性變換關(guān)系。若之間有確定的線性變換關(guān)系。若S和和E之間一一對(duì)應(yīng)，則之間一一對(duì)應(yīng)，則S將能代表錯(cuò)碼的位置。將能代表錯(cuò)碼的位置。284、線性分組碼的性質(zhì)、線性分組碼的性質(zhì)封閉性封閉性 是指一種線性碼中的任意兩個(gè)碼組之和仍為是指一種線性碼中的任意兩個(gè)碼組之和仍為這種碼中的一個(gè)碼組。這種碼

20、中的一個(gè)碼組。 這就是說，若這就是說，若A1和和A2是一種線性碼中的兩個(gè)是一種線性碼中的兩個(gè)許用碼組，則許用碼組，則(A1+A2)仍為其中的一個(gè)碼組。仍為其中的一個(gè)碼組。證明：若證明：若A1和和A2是兩個(gè)碼組，則有：是兩個(gè)碼組，則有： A1 HT = 0,A2 HT = 0將上兩式相加，得出：將上兩式相加，得出：A1 HT + A2 HT = (A1 + A2) HT = 0所以所以(A1 + A2)也是一個(gè)碼組。也是一個(gè)碼組。29由于線性碼具有封閉性，所以兩個(gè)碼組由于線性碼具有封閉性，所以兩個(gè)碼組(A1和和A2)之間的距離（即對(duì)應(yīng)位不同的數(shù)目）之間的距離（即對(duì)應(yīng)位不同的數(shù)目）必定是另一個(gè)碼組

21、必定是另一個(gè)碼組(A1 + A2)的重量（即的重量（即“1”的數(shù)目）。因此，碼的最小距離就是碼的最的數(shù)目）。因此，碼的最小距離就是碼的最小重量（除全小重量（除全“0”碼組外）。碼組外）。30例例 已知（已知（6，3）漢明碼的生成矩陣如下，）漢明碼的生成矩陣如下，(1)列出所有許用碼組列出所有許用碼組; (2)最小碼距最小碼距d0;(3)檢錯(cuò)糾錯(cuò)能力；檢錯(cuò)糾錯(cuò)能力； (4)編碼效率。編碼效率。100101G010011001110 （1）列出所有許用碼組）列出所有許用碼組GA345aaa信息碼信息碼編碼碼字編碼碼字碼重碼重0 0 00 0 0 0 0 000 0 10 0 1 1 1 0 30

22、1 00 1 0 0 1 130 1 10 1 1 1 0 141 0 01 0 0 1 0 131 0 11 0 1 0 1 141 1 01 1 0 1 1 041 1 1 1 1 1 0 0 03（2）最小碼距）最小碼距0d3 （3）檢錯(cuò)糾錯(cuò)能力）檢錯(cuò)糾錯(cuò)能力（4）編碼效率）編碼效率000e=d -1=2d -1t=12et1det 該該碼碼可可以以檢檢2 2位位錯(cuò)錯(cuò)該該碼碼可可以以糾糾1 1位位錯(cuò)錯(cuò)該該碼碼不不能能同同時(shí)時(shí)用用于于檢檢錯(cuò)錯(cuò)與與糾糾錯(cuò)錯(cuò)k350%n6 3311.6 循環(huán)碼循環(huán)碼循環(huán)碼是循環(huán)碼是一種重要的一種重要的線性分組碼線性分組碼。這種。這種碼的編碼和解碼設(shè)備都不太復(fù)雜

23、，且有較碼的編碼和解碼設(shè)備都不太復(fù)雜，且有較強(qiáng)的檢（糾）錯(cuò)能力。強(qiáng)的檢（糾）錯(cuò)能力。共共n位。通常前位。通常前k 位為信息位，后位為信息位，后r 位位為為監(jiān)督位。監(jiān)督位。11.6.1 循環(huán)碼編碼原理循環(huán)碼編碼原理34循環(huán)碼的循環(huán)碼的特點(diǎn)特點(diǎn)： 封閉性封閉性；任意兩個(gè)碼組之和仍是一個(gè)碼組任意兩個(gè)碼組之和仍是一個(gè)碼組 循環(huán)性循環(huán)性；即碼中任一碼組循環(huán)一位；即碼中任一碼組循環(huán)一位(將最右將最右端的碼元移到左端或反之）以后，仍為該碼端的碼元移到左端或反之）以后，仍為該碼中的一個(gè)碼組。中的一個(gè)碼組。 (an-1,an-2,a1,a0)是某是某(n,k)循環(huán)碼的碼組，則：循環(huán)碼的碼組，則： (an-2 ,

24、an-3 ,a1,a0 ,an-1)(an-3 ,an-4 , , a0 , an-1 ,an-2) ( a0 ,an-1 , an-2 ,an-3 ,a2 ,a1) 也是該循環(huán)碼的碼組也是該循環(huán)碼的碼組35表表11-5 一種（一種（7，3）循環(huán)碼的全部碼組）循環(huán)碼的全部碼組碼組碼組編號(hào)編號(hào)信息位信息位監(jiān)督位監(jiān)督位碼組碼組編號(hào)編號(hào)信息位信息位監(jiān)督位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010為便于計(jì)算，把碼組中各碼元當(dāng)作多項(xiàng)式系數(shù)為便于計(jì)算，把碼組中

25、各碼元當(dāng)作多項(xiàng)式系數(shù)若碼組若碼組A=(an-1,an-2,a1,a0)，則其相應(yīng)的碼，則其相應(yīng)的碼多項(xiàng)式為：多項(xiàng)式為：T(x)= an-1xn-1+ an-1xn-1+ + a1x+ a0對(duì)于（對(duì)于（7，3）循環(huán)碼的任意碼組可表示為：）循環(huán)碼的任意碼組可表示為： T(x)= a6x6+ a5x5+ a4x4 + a3x3 + a2x2 + a1x+ a0如碼組（如碼組（1100101）對(duì)應(yīng)的碼多項(xiàng)式可表示為）對(duì)應(yīng)的碼多項(xiàng)式可表示為T7(x)=1x6+1x5+ 0 x4 +0 x3 +1x2+0 x+1 = x6 + x5 + x2 +11、碼多項(xiàng)式、碼多項(xiàng)式T(x)37碼多項(xiàng)式與碼組的關(guān)系：碼

26、多項(xiàng)式與碼組的關(guān)系： 本質(zhì)上是一回事，僅是表示方法的不同而已。本質(zhì)上是一回事，僅是表示方法的不同而已。對(duì)于二進(jìn)制碼組，多項(xiàng)式的每個(gè)系數(shù)不是對(duì)于二進(jìn)制碼組，多項(xiàng)式的每個(gè)系數(shù)不是0就就是是1，x 僅是碼元位置的標(biāo)志。因此，這里并僅是碼元位置的標(biāo)志。因此，這里并不關(guān)心不關(guān)心x 的取值。的取值。如碼組如碼組 1100101 對(duì)應(yīng)的碼多項(xiàng)式可表示為對(duì)應(yīng)的碼多項(xiàng)式可表示為T7(x)=1x6+1x5+ 0 x4 +0 x3 +1x2+0 x+1 = x6 + x5 + x2 +138npnpQnm2、 循環(huán)碼的運(yùn)算循環(huán)碼的運(yùn)算(1) 整數(shù)的按模運(yùn)算整數(shù)的按模運(yùn)算在整數(shù)運(yùn)算中，有模在整數(shù)運(yùn)算中，有模n運(yùn)算。例

27、如，在模運(yùn)算。例如，在模4運(yùn)運(yùn)算中，有算中，有: 1 + 1 = 2 0 1 + 2 = 3 1 2 3 = 6 0 等等。等等。一般說來，若整數(shù)一般說來，若整數(shù)m可以表示為可以表示為:式中，式中，Q為整數(shù)，則在模為整數(shù)，則在模n運(yùn)算下，有運(yùn)算下，有:m p (模模n)在模在模n運(yùn)算下，整數(shù)運(yùn)算下，整數(shù)m等于它被等于它被n除得的余數(shù)。除得的余數(shù)。39)()()()(xRxQxNxF）（模)()()(xNxRxF(2) 碼多項(xiàng)式的按模運(yùn)算碼多項(xiàng)式的按模運(yùn)算 若任意一個(gè)多項(xiàng)式若任意一個(gè)多項(xiàng)式F(x)被一個(gè)被一個(gè)n次多項(xiàng)式次多項(xiàng)式N(x)除，得到商式除，得到商式Q(x)和一個(gè)次數(shù)小于和一個(gè)次數(shù)小于n

28、的余式的余式R(x)，即，即:則在按模則在按模N(x)運(yùn)算下，有運(yùn)算下，有 這時(shí)，碼多項(xiàng)式系數(shù)仍按模這時(shí)，碼多項(xiàng)式系數(shù)仍按模2運(yùn)算，即系數(shù)運(yùn)算，即系數(shù)只取只取 0 和和1。40）（模) 1(133xx）模) 1(113224xxxxx同理：同理：例：例：x3被被(x3 + 1)除，得到余項(xiàng)除，得到余項(xiàng)1，即，即因?yàn)橐驗(yàn)?應(yīng)當(dāng)注意，由于在模應(yīng)當(dāng)注意，由于在模2運(yùn)算中，用加法代替了運(yùn)算中，用加法代替了減法，故余項(xiàng)不是減法，故余項(xiàng)不是x2 x + 1，而是，而是x2 + x + 1。在模在模2運(yùn)算中加法和減法一樣。運(yùn)算中加法和減法一樣。 xx3 + 1 x4 +x2 + 1 x4 + x x2 +x

29、 +141(3) 循環(huán)碼的數(shù)學(xué)表示法循環(huán)碼的數(shù)學(xué)表示法 在循環(huán)碼中，設(shè)在循環(huán)碼中，設(shè)T(x)是一個(gè)長(zhǎng)度為是一個(gè)長(zhǎng)度為n的碼組，的碼組，若若: 則則T (x)也是該編碼中的一個(gè)碼組，是碼組也是該編碼中的一個(gè)碼組，是碼組T (x)向左循環(huán)移位向左循環(huán)移位 i 次的結(jié)果。次的結(jié)果。）（模) 1()()(nixxTxTx421)(256xxxxTxxxxxxxxxTx23535893)(例：例： 一循環(huán)碼為一循環(huán)碼為1100101，即，即若給定若給定 i = 3，則有，則有 上式對(duì)應(yīng)的碼組為上式對(duì)應(yīng)的碼組為0101110，它正是，它正是T(x)向左向左移移3位的結(jié)果。位的結(jié)果。 結(jié)論：一個(gè)長(zhǎng)為結(jié)論：一

30、個(gè)長(zhǎng)為n的循環(huán)碼必定為按模的循環(huán)碼必定為按模(xn + 1)運(yùn)算的一個(gè)余式。運(yùn)算的一個(gè)余式。 ）（模) 1(7x43(4) 循環(huán)碼的生成多項(xiàng)式與生成矩陣循環(huán)碼的生成多項(xiàng)式與生成矩陣GA3456aaaa 可知，有了生成矩陣可知，有了生成矩陣G，就可以由，就可以由k個(gè)信息位個(gè)信息位得出整個(gè)碼組，而且生成矩陣得出整個(gè)碼組，而且生成矩陣G的每一行都是的每一行都是一個(gè)碼組。由于一個(gè)碼組。由于G是是k行行n列的矩陣，因此若能列的矩陣，因此若能找到找到k個(gè)已知碼組個(gè)已知碼組(必須是線性不相關(guān)的必須是線性不相關(guān)的)，就，就能構(gòu)成矩陣能構(gòu)成矩陣G。44在循環(huán)碼中，一個(gè)在循環(huán)碼中，一個(gè)(n, k)碼有碼有2k個(gè)不

31、同的碼組。個(gè)不同的碼組。若用若用g(x)表示其中前表示其中前(k-1)位皆為位皆為“0”的碼組，的碼組，則則g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是碼都是碼組，而且這組，而且這k個(gè)碼組是線性無關(guān)的。因此它們個(gè)碼組是線性無關(guān)的。因此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣可以用來構(gòu)成此循環(huán)碼的生成矩陣G。在循環(huán)碼中除全在循環(huán)碼中除全“0”碼組外，再?zèng)]有連續(xù)碼組外，再?zèng)]有連續(xù)k位均為位均為“0”的碼組，即連的碼組，即連“0”的長(zhǎng)度最多只能的長(zhǎng)度最多只能有有(k - 1)位。位。 45g(x)必須是一個(gè)常數(shù)項(xiàng)不為必須是一個(gè)常數(shù)項(xiàng)不為“0”的的(n - k)次次多項(xiàng)式，而且這個(gè)多項(xiàng)式，

32、而且這個(gè)g(x)還是這種還是這種(n, k)碼中次碼中次數(shù)為數(shù)為(n k)的的唯一唯一多項(xiàng)式。多項(xiàng)式。我們稱這唯一的我們稱這唯一的(n k)次多項(xiàng)式次多項(xiàng)式g(x)為碼的為碼的生成多項(xiàng)式生成多項(xiàng)式。一旦確定了。一旦確定了g(x)，則整個(gè)，則整個(gè)(n, k)循環(huán)碼就被確定了。循環(huán)碼就被確定了。 因此，循環(huán)碼的生成矩陣因此，循環(huán)碼的生成矩陣G可以寫成可以寫成)()()()()(21xgxxgxgxxgxxkkG46例：表例：表11-5所給出的所給出的(7, 3)循環(huán)碼中，循環(huán)碼中，n=7, k=3, nk=4。由表可見，唯一的一個(gè)。由表可見，唯一的一個(gè)(n k)= 4次碼次碼多項(xiàng)式代表的碼組是第二

33、碼組多項(xiàng)式代表的碼組是第二碼組0010111，與它相，與它相對(duì)應(yīng)的碼多項(xiàng)式（即生成多項(xiàng)式）：對(duì)應(yīng)的碼多項(xiàng)式（即生成多項(xiàng)式）：g(x) = x4 + x2 + x + 1。將此。將此g(x)代入上式，得到代入上式，得到)()()()(2xgxxgxgxxG0010111010111010111001)(242352346xxxxxxxxxxxxG)()()()()(2456456xgxxgxgxaaaxaaaxTG可以寫出此循環(huán)碼組，即可以寫出此循環(huán)碼組，即:47)()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaa

34、axTG上式表明，所有碼多項(xiàng)式上式表明，所有碼多項(xiàng)式T(x)都可被都可被g(x)整除，整除，而且任意一個(gè)次數(shù)不大于而且任意一個(gè)次數(shù)不大于(k 1)的多項(xiàng)式乘的多項(xiàng)式乘g(x)都是碼多項(xiàng)式。都是碼多項(xiàng)式。48可以證明生成多項(xiàng)式可以證明生成多項(xiàng)式g(x)具有以下特性：具有以下特性： （1） g(x)是一個(gè)常數(shù)項(xiàng)為是一個(gè)常數(shù)項(xiàng)為1的的 次次多項(xiàng)式；多項(xiàng)式； （2） g(x)是是 的一個(gè)因式；的一個(gè)因式； （3）該循環(huán)碼中其它碼多項(xiàng)式都是）該循環(huán)碼中其它碼多項(xiàng)式都是g(x)的倍式。的倍式。 g(x)， xg(x) ， xk-1g(x)。knr1nx49由上式可知，任一循環(huán)碼多項(xiàng)式由上式可知，任一循環(huán)碼

35、多項(xiàng)式T(x)都是都是g(x)的倍式，故它可以寫成的倍式，故它可以寫成 : T(x) = h(x) g(x)而生成多項(xiàng)式而生成多項(xiàng)式g(x)本身也是一個(gè)碼組，即有本身也是一個(gè)碼組，即有 T (x) = g(x)由于碼組由于碼組T (x)是一個(gè)是一個(gè)(n k)次多項(xiàng)式，故次多項(xiàng)式，故xkT (x)是一個(gè)是一個(gè)n次多項(xiàng)式。由下式次多項(xiàng)式。由下式）（模) 1()()(nixxTxTx(5)如何尋找任一如何尋找任一(n, k)循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式 50）（模) 1()()(nixxTxTx1)()(1)(nnkxxTxQxxTx 可知，可知，xk T (x)在模在模(xn + 1)運(yùn)算

36、下也是一運(yùn)算下也是一個(gè)碼組，故可以寫成：個(gè)碼組，故可以寫成：上式左端分子和分母都是上式左端分子和分母都是n次多項(xiàng)式，故商式次多項(xiàng)式，故商式Q(x) = 1。因此，上式可以化成：。因此，上式可以化成：)() 1()(xTxxTxnk 將將T(x) = h(x) g(x)和和T (x) = g(x)代入上式并代入上式并化簡(jiǎn)。化簡(jiǎn)。51)() 1()(xTxxTxnk)()(1xhxxgxknT(x) = h(x) g(x) T (x) = g(x) 上式表明，上式表明，生成多項(xiàng)式生成多項(xiàng)式g(x)應(yīng)該是應(yīng)該是(xn + 1)的的一個(gè)因子一個(gè)因子。這一結(jié)論為我們尋找循環(huán)碼的生成。這一結(jié)論為我們尋找循

37、環(huán)碼的生成多項(xiàng)式指出了一條道路，即循環(huán)碼的生成多項(xiàng)多項(xiàng)式指出了一條道路，即循環(huán)碼的生成多項(xiàng)式應(yīng)該是式應(yīng)該是(xn +1)的一個(gè)的一個(gè)(n k)次因式。次因式。52例：例：試求（試求（7，3）循環(huán)碼的生成多項(xiàng)式和生）循環(huán)碼的生成多項(xiàng)式和生成矩陣。成矩陣。解解1：對(duì)（：對(duì)（7, 3）循環(huán)碼，）循環(huán)碼，n=7，k=3, r=4由于由于g(x)是一個(gè)常數(shù)項(xiàng)為是一個(gè)常數(shù)項(xiàng)為1的的 n-k次多項(xiàng)式，次多項(xiàng)式，查表查表11-5知知生成多項(xiàng)式為：生成多項(xiàng)式為：g(x)= x4+x2+x+11)()()()(2423523462xxxxxxxxxxxxgxxgxgxxG53生成多項(xiàng)式生成多項(xiàng)式g(x)是是xn+

38、1的一個(gè)因式，且的一個(gè)因式，且g(x)是一是一個(gè)個(gè)r 次因式。次因式。因此，就可以先對(duì)因此，就可以先對(duì)xn+1進(jìn)行因式分解，找到它進(jìn)行因式分解，找到它的的r 次次因式。因式。下面仍以（下面仍以（7，3）循環(huán)碼為例進(jìn)行分析。）循環(huán)碼為例進(jìn)行分析。 54解解2：對(duì)（：對(duì)（7, 3）循環(huán)碼，）循環(huán)碼，n=7，k=3, r=4第一步：第一步：對(duì)對(duì)x7+1進(jìn)行因式分解進(jìn)行因式分解得：得： x7+1=(x+1)(x3+x2+1)(x3+x+1) .(1)第二步：第二步：構(gòu)造構(gòu)造r 次生成多項(xiàng)式次生成多項(xiàng)式g(x)。從從(1)中找中找r=n-k=4次的因子次的因子,這樣的因子有兩個(gè)這樣的因子有兩個(gè)： (x+

39、1)(x3+x2+1)=x4+x2+x+1(a) (x+1)(x3+x+1)=x4+x3+x2+1(b)第三步：若按第三步：若按(a)構(gòu)成生成多項(xiàng)式構(gòu)成生成多項(xiàng)式:生成多項(xiàng)式為：生成多項(xiàng)式為：g(x)= x4+x2+x+1例例求求(7,3)循環(huán)碼的生成多項(xiàng)式和生成矩陣。循環(huán)碼的生成多項(xiàng)式和生成矩陣。1)()()()(2423523462xxxxxxxxxxxxgxxgxgxXG生成矩陣為：生成矩陣為：為典型生成為典型生成矩陣矩陣111010001110101101001G生成多項(xiàng)式為：生成多項(xiàng)式為：g(x)= x4+x2+x+1111010001110100011101G將第將第1行與第行與第

40、3行行模模2加加作為第作為第1行，則有行，則有若按若按(b)構(gòu)成生成多項(xiàng)式構(gòu)成生成多項(xiàng)式:生成多項(xiàng)式為：生成多項(xiàng)式為：g(x)= x4+x3+x2+11)()()()(23434524562xxxxxxxxxxxxgxxgxgxXG101110011100100111001G進(jìn)行線性變換，得進(jìn)行線性變換，得典型生成矩陣典型生成矩陣為：為：101110001011100010111G生成矩陣為：生成矩陣為：571111111111010011010011100010101100010100111001110100010101110100110001010110001001110011101001

41、011000010110000000例：已知（例：已知（7，4）循環(huán)碼的全部碼組為：）循環(huán)碼的全部碼組為：試寫出該循環(huán)碼的生成多項(xiàng)式試寫出該循環(huán)碼的生成多項(xiàng)式g(x)和生和生成矩陣成矩陣G，并將，并將G化成典型矩陣?；傻湫途仃嚒＝猓航猓簄=7，k=4，n-k=3。碼組中的。碼組中的(n-k)=3次碼次碼多項(xiàng)式為第多項(xiàng)式為第2組，它所對(duì)應(yīng)的碼多項(xiàng)式組，它所對(duì)應(yīng)的碼多項(xiàng)式g(x)即即為生成多項(xiàng)式：為生成多項(xiàng)式：g(x)=x3+x+1。58g(x)=x3+x+1。生成矩陣為：生成矩陣為：364325321423x g(x)xxxx g(x)xxxG (x)x g(x)xxxg(x)xx110110

42、001000101010110001001110010110001011000010110001011 364325321423x g(x)xxxx g(x)xxxG(x)x g(x)xxxg(x)xx110110001000101010110001001110010110001011000010110001011 364325321423x g(x)xxxx g(x)xxxG(x)x g(x)xxxg(x)xx11011000100010101011000100111001011000101100001011000101159 首先從首先從xn+1的因子中選一個(gè)（的因子中選一個(gè)（n-k）次多

43、）次多項(xiàng)式作為項(xiàng)式作為g(x)； 然后，利用循環(huán)碼的編碼特點(diǎn)，即所有循然后，利用循環(huán)碼的編碼特點(diǎn)，即所有循環(huán)碼多項(xiàng)式環(huán)碼多項(xiàng)式T(x)都可以被都可以被g(x)整除，來定義整除，來定義生成多項(xiàng)式生成多項(xiàng)式g(x)。 11.6.2 循環(huán)碼的編碼、解碼方法循環(huán)碼的編碼、解碼方法1、循環(huán)碼的循環(huán)碼的編碼方法編碼方法（1）原理）原理60設(shè)信息位對(duì)應(yīng)的多項(xiàng)式為設(shè)信息位對(duì)應(yīng)的多項(xiàng)式為m(x)用用xn-k乘乘m(x)，相當(dāng)于把信息碼后附加上，相當(dāng)于把信息碼后附加上(n-k)個(gè)個(gè)“0” 用用g(x)除除xn-k m(x)，得到余式為，得到余式為r(x)編出碼組為：編出碼組為：T(x)= xn-k m(x)+ r

44、(x) xgxrxQxgxmxkn(2)編碼步驟編碼步驟61例如例如:信息碼為信息碼為110，它相當(dāng)于，它相當(dāng)于m(x)x2+x。 當(dāng)當(dāng)n-k7-34時(shí)，時(shí)， xn-k m(x)x4(x2+x)= x6+x5，相當(dāng)于，相當(dāng)于1100000。而希望的到得系統(tǒng)循環(huán)碼多項(xiàng)式應(yīng)當(dāng)是而希望的到得系統(tǒng)循環(huán)碼多項(xiàng)式應(yīng)當(dāng)是: T(x) = xn-k m(x) + r(x)。 6211) 1(1)()(24222456xxxxxxxxxxxxgxmxkn即余式即余式r(x)=x2+1則對(duì)應(yīng)碼組則對(duì)應(yīng)碼組T(x)= xn-k m(x)+r(x)= x6+x5+ x2+1編碼為編碼為1100101例例 設(shè)設(shè)(7,3

45、)循環(huán)碼的生成多項(xiàng)式為循環(huán)碼的生成多項(xiàng)式為g(x)=x4+x2+x+1，待編碼信息位為，待編碼信息位為110，求對(duì)應(yīng)，求對(duì)應(yīng)循環(huán)碼碼組。循環(huán)碼碼組。解：解：m(x)=x2+x，xn-k m(x)=x4(x2+x)=x6+x5632、循環(huán)碼的解碼方法、循環(huán)碼的解碼方法（1）解碼要求：檢錯(cuò)和糾錯(cuò)。）解碼要求：檢錯(cuò)和糾錯(cuò)。（2）檢錯(cuò)解碼原理）檢錯(cuò)解碼原理 由于任意一個(gè)碼組多項(xiàng)式由于任意一個(gè)碼組多項(xiàng)式T(x)都應(yīng)該能被都應(yīng)該能被生成多項(xiàng)式生成多項(xiàng)式g(x)整除，所以在接收端可以將整除，所以在接收端可以將接收碼組接收碼組R(x)用原生成多項(xiàng)式用原生成多項(xiàng)式g(x)去除。去除。傳輸中未發(fā)生錯(cuò)誤：接收碼組與

46、發(fā)送碼組傳輸中未發(fā)生錯(cuò)誤：接收碼組與發(fā)送碼組相同，即相同，即R(x) = T(x)，故接收碼組，故接收碼組R(x)必定能必定能被被g(x)整除；整除；64傳輸中發(fā)生錯(cuò)誤，則傳輸中發(fā)生錯(cuò)誤，則R(x) T(x)，R(x)被被g(x)除時(shí)可能除不盡而有余項(xiàng)，即有：除時(shí)可能除不盡而有余項(xiàng)，即有：)(/ )()()(/ )(xgxrxQxgxR 以余項(xiàng)是否為零來判別接收碼組中有無錯(cuò)碼。以余項(xiàng)是否為零來判別接收碼組中有無錯(cuò)碼。 有錯(cuò)碼的接收碼組也有可能被有錯(cuò)碼的接收碼組也有可能被g(x)整除，這整除，這時(shí)的錯(cuò)碼就不能檢出了。這種錯(cuò)誤稱為時(shí)的錯(cuò)碼就不能檢出了。這種錯(cuò)誤稱為不可不可檢錯(cuò)誤檢錯(cuò)誤。不可檢錯(cuò)誤中

47、的誤碼數(shù)必定超過了。不可檢錯(cuò)誤中的誤碼數(shù)必定超過了這種編碼的檢錯(cuò)能力。這種編碼的檢錯(cuò)能力。65（3）糾錯(cuò)解碼原理）糾錯(cuò)解碼原理為了能夠糾錯(cuò)，要求每個(gè)可糾正的錯(cuò)誤圖樣必為了能夠糾錯(cuò)，要求每個(gè)可糾正的錯(cuò)誤圖樣必須與一個(gè)特定余式有一一對(duì)應(yīng)關(guān)系。原則上糾須與一個(gè)特定余式有一一對(duì)應(yīng)關(guān)系。原則上糾錯(cuò)可按下述步驟進(jìn)行：錯(cuò)可按下述步驟進(jìn)行：用生成多項(xiàng)式用生成多項(xiàng)式g(x)除接收碼組除接收碼組R(x)，得出余，得出余式式r(x)。按余式按余式r(x)，用查表的方法或通過某種計(jì)算，用查表的方法或通過某種計(jì)算得到錯(cuò)誤圖樣得到錯(cuò)誤圖樣E(x)；如通過計(jì)算校正子；如通過計(jì)算校正子S和查和查表，可確定錯(cuò)碼的位置。表，可確

48、定錯(cuò)碼的位置。從從R(x)中減去中減去E(x)，便得到已經(jīng)糾正錯(cuò)碼的，便得到已經(jīng)糾正錯(cuò)碼的原發(fā)送碼組原發(fā)送碼組T(x)。6611.6.3 截短循環(huán)碼截短循環(huán)碼截短目的截短目的：在設(shè)計(jì)糾錯(cuò)編碼方案時(shí)，常常：在設(shè)計(jì)糾錯(cuò)編碼方案時(shí)，常常信息位數(shù)信息位數(shù)k、碼長(zhǎng)、碼長(zhǎng)n和糾錯(cuò)能力都是預(yù)先給定和糾錯(cuò)能力都是預(yù)先給定的。但是，并不一定有恰好滿足這些條件的的。但是，并不一定有恰好滿足這些條件的循環(huán)碼存在。這時(shí)，可以采用將碼長(zhǎng)截短的循環(huán)碼存在。這時(shí)，可以采用將碼長(zhǎng)截短的方法，得出滿足要求的編碼。方法，得出滿足要求的編碼。67截短方法截短方法：設(shè)給定一個(gè)：設(shè)給定一個(gè)(n, k)循環(huán)碼，它循環(huán)碼，它共有共有2k種

49、碼組，現(xiàn)使其前種碼組，現(xiàn)使其前i (0 i k)個(gè)信息個(gè)信息位全為位全為“0”，于是它變成僅有，于是它變成僅有2k-i種碼組。種碼組。然后從中刪去這然后從中刪去這i位全位全“0”的信息位，最終的信息位，最終得到一個(gè)得到一個(gè)(n i, k i)的線性碼。將這種碼稱的線性碼。將這種碼稱為為截短循環(huán)碼截短循環(huán)碼。截短循環(huán)碼性能截短循環(huán)碼性能：循環(huán)碼截短前后至少具：循環(huán)碼截短前后至少具有相同的糾錯(cuò)能力，并且編解碼方法仍和截有相同的糾錯(cuò)能力，并且編解碼方法仍和截短前的方法一樣。短前的方法一樣。68例例：要求構(gòu)造一個(gè)能夠糾正：要求構(gòu)造一個(gè)能夠糾正1位錯(cuò)碼的位錯(cuò)碼的(13,9)碼。這時(shí)可以由碼。這時(shí)可以由(

50、15,11)循環(huán)碼的循環(huán)碼的11種碼組中種碼組中選出前兩信息位均為選出前兩信息位均為“0”的碼組，構(gòu)成一個(gè)的碼組，構(gòu)成一個(gè)新的碼組集合。然后在發(fā)送時(shí)不發(fā)送這兩位新的碼組集合。然后在發(fā)送時(shí)不發(fā)送這兩位“0”。于是發(fā)送碼組成為。于是發(fā)送碼組成為(13,9)截短循環(huán)碼。截短循環(huán)碼。 6911.6.4 BCH碼碼什么是什么是BCH碼？碼？ 它是一種獲得廣泛應(yīng)用的能夠糾正多個(gè)錯(cuò)碼它是一種獲得廣泛應(yīng)用的能夠糾正多個(gè)錯(cuò)碼的循環(huán)碼，是以的循環(huán)碼，是以3位發(fā)明這種碼的人名位發(fā)明這種碼的人名(Bose - Chaudhuri - Hocguenghem)命名的。命名的。 BCH碼的重要性在于它解決了生成多項(xiàng)式與碼

51、的重要性在于它解決了生成多項(xiàng)式與糾錯(cuò)能力的關(guān)系問題，可以在給定糾錯(cuò)能力要糾錯(cuò)能力的關(guān)系問題，可以在給定糾錯(cuò)能力要求的條件下尋找到碼的生成多項(xiàng)式。有了生成求的條件下尋找到碼的生成多項(xiàng)式。有了生成多項(xiàng)式，編碼的基本問題就隨之解決了。多項(xiàng)式，編碼的基本問題就隨之解決了。70BCH碼分類：碼分類：本原本原BCH碼碼：其生成多項(xiàng)式：其生成多項(xiàng)式g(x)中含有最高中含有最高次數(shù)為次數(shù)為m的本原多項(xiàng)式，且碼長(zhǎng)為的本原多項(xiàng)式，且碼長(zhǎng)為n=2m1，(m 3，為正整數(shù)，為正整數(shù))。非本原非本原BCH碼碼：其生成多項(xiàng)式中不含這種：其生成多項(xiàng)式中不含這種本原多項(xiàng)式，且碼長(zhǎng)本原多項(xiàng)式，且碼長(zhǎng)n是是(2m 1)的一個(gè)因子

52、，的一個(gè)因子，即碼長(zhǎng)即碼長(zhǎng)n一定除得盡一定除得盡2m 1。本原多項(xiàng)式：不能分解因子；可整除本原多項(xiàng)式：不能分解因子；可整除xm+1 (m=2n-1);除不盡除不盡xq+1 (qm)。71BCH碼的性能：碼的性能：碼長(zhǎng)碼長(zhǎng)n與監(jiān)督位、糾錯(cuò)個(gè)數(shù)與監(jiān)督位、糾錯(cuò)個(gè)數(shù) t 之間的關(guān)系：之間的關(guān)系： 對(duì)于正整數(shù)對(duì)于正整數(shù)m (m 3)和正整數(shù)和正整數(shù)t1，且除得盡，且除得盡(2m -1)），），則為非本原則為非本原BCH碼。碼。72漢明碼是能夠糾正單個(gè)隨機(jī)錯(cuò)誤的碼?？蓾h明碼是能夠糾正單個(gè)隨機(jī)錯(cuò)誤的碼?？梢宰C明，具有循環(huán)性質(zhì)的漢明碼就是能糾正以證明，具有循環(huán)性質(zhì)的漢明碼就是能糾正單個(gè)隨機(jī)錯(cuò)誤的本原單個(gè)隨機(jī)錯(cuò)誤的本原BCH碼。碼。例如，例如，(7, 4)漢明碼就是以漢明碼就是以g1(x) = x3 + x + 1或或g2(x) = x3+x2+1生成的生成的BCH碼，而用碼，而用g3(x) = x4 + x + 1或或g4(x) = x4 + x3 + 1都能生成都能生成(15, 11)漢明碼。漢明碼。73 BCH碼的設(shè)計(jì)碼的設(shè)計(jì) 在工程設(shè)計(jì)中，一般不需要用計(jì)算方法在工程設(shè)計(jì)中，一般不需要用計(jì)算方法去尋找生成多項(xiàng)式去尋找生成多項(xiàng)式g(x)。因?yàn)榍叭嗽缫褜?。因?yàn)榍叭嗽缫褜ふ业降恼业降膅(x)列