信息論與編碼第6章(3)

1、第第6 6章章 信道編碼信道編碼 2022-7-31信道編碼信道編碼 第第6 6章章第第6 6章章 信道編碼信道編碼 2022-7-326.16.1 有擾離散信道的編碼理論有擾離散信道的編碼理論6.26.2 糾錯(cuò)編譯碼的基本原理與分析方法糾錯(cuò)編譯碼的基本原理與分析方法6.3 6.3 線性分組碼線性分組碼6.4 6.4 卷積碼卷積碼6.56.5 其它信道編碼其它信道編碼內(nèi)容第第6 6章章 信道編碼信道編碼 2022-7-336.3 線性分組碼線性分組碼 6.3.1 線性分組碼的生成矩陣和校驗(yàn)矩陣線性分組碼的生成矩陣和校驗(yàn)矩陣 6.3.2 伴隨式與標(biāo)準(zhǔn)陣列譯碼伴隨式與標(biāo)準(zhǔn)陣列譯碼 6.3.3 碼距

2、碼距,糾錯(cuò)碼糾錯(cuò)碼,MDC碼等碼等 6.3.4 完備碼完備碼 6.3.5 循環(huán)碼循環(huán)碼,BCH和和RS碼碼 6.3.6 分組碼的擴(kuò)展分組碼的擴(kuò)展,縮短和縮短和CRC第第6 6章章 信道編碼信道編碼 2022-7-346.3 線性分組碼線性分組碼(n,k)分組碼是把信息流分割成一串前后獨(dú)立的分組碼是把信息流分割成一串前后獨(dú)立的k比特信息組，比特信息組，再將每組信息元映射成再將每組信息元映射成n個(gè)碼元組成的碼字。如下圖：個(gè)碼元組成的碼字。如下圖：m0 m1 m2 mk-1 m0 m1 m2. mk-1 m0 m1 m2 mk-1 . C0C1C3.Cn-1 C0C1C3.Cn-1 C0C1C3.C

3、n-1 K個(gè)信息元可以寫成矢量個(gè)信息元可以寫成矢量(mk-1,.m1,m0)或者矩陣的形式或者矩陣的形式mk-1,.m1,m0。同樣碼字可以表示為同樣碼字可以表示為(Cn-1,.C1,C0)或者或者Cn-1,.C1,C0第第6 6章章 信道編碼信道編碼 2022-7-35線性分組碼中，必須考慮的問題：線性分組碼中，必須考慮的問題：（1）碼集）碼集C能否構(gòu)成能否構(gòu)成n維維n重矢量空間的一個(gè)重矢量空間的一個(gè)k維維n重子空間重子空間。（2）如何尋找）如何尋找最佳的碼空間最佳的碼空間。（3）qk個(gè)信息元組以怎樣的算法一一映射到碼空間。個(gè)信息元組以怎樣的算法一一映射到碼空間。碼率碼率對(duì)于對(duì)于二元二元分組

4、碼分組碼(n,k),其碼率定義為：其碼率定義為：RC=k/n對(duì)于對(duì)于q元元分組碼分組碼(n,k),其碼率定義為：其碼率定義為： RC=klbq/n 消息消息m (n , k) 碼字碼字c m=(mk-1,m1,m0) 分組編碼器分組編碼器 c=(cn-1,c1,c0) qk qn第第6 6章章 信道編碼信道編碼 2022-7-366.3.1生成矩陣和校驗(yàn)矩陣生成矩陣和校驗(yàn)矩陣 線性分組碼的碼空間線性分組碼的碼空間C 是由是由 k 個(gè)線性無關(guān)的基底個(gè)線性無關(guān)的基底 gk-1 g1 ，g0 張成的張成的k維維n重子空間，所有碼字都可寫成重子空間，所有碼字都可寫成k個(gè)基底的線性組合，個(gè)基底的線性組合

5、，即即c = mk-1 gk-1+ m1 g1+m0 g0 =mG(1)(1)(1)1(1)012101(1)11100(1)0100.,.,.knkkTkknngggGggg ggggggg 由于由于k個(gè)基底即個(gè)基底即G的的k個(gè)行矢量線性無關(guān)，矩陣個(gè)行矢量線性無關(guān)，矩陣G的秩一的秩一定等于定等于k。當(dāng)信息元確定后，碼字僅由。當(dāng)信息元確定后，碼字僅由G矩陣決定，因此我矩陣決定，因此我們稱這們稱這kn 矩陣矩陣G為該為該(n,k)線性分組碼的線性分組碼的生成矩陣生成矩陣。 第第6 6章章 信道編碼信道編碼 2022-7-37生成矩陣生成矩陣G(kn)的特點(diǎn)的特點(diǎn) 想要保證想要保證 (n,k)線性

6、分組碼能夠構(gòu)成線性分組碼能夠構(gòu)成k維維n重子空間，重子空間，G 的的k個(gè)行矢量個(gè)行矢量gk-1, g1, g0必須是線性無關(guān)的，只有這樣才符必須是線性無關(guān)的，只有這樣才符合作為基底的條件。合作為基底的條件。 由于基底不是唯一的，所以由于基底不是唯一的，所以G也就不是唯一的。也就不是唯一的。 不同的基底有可能生成同一碼集，但因編碼涉及碼集和映不同的基底有可能生成同一碼集，但因編碼涉及碼集和映射兩個(gè)因素，碼集一樣而映射方法不同也不能說是同樣的射兩個(gè)因素，碼集一樣而映射方法不同也不能說是同樣的碼。碼。 第第6 6章章 信道編碼信道編碼 2022-7-38系統(tǒng)形式的生成矩陣系統(tǒng)形式的生成矩陣 (n,k

7、)碼的任何生成矩陣都可以通過碼的任何生成矩陣都可以通過行運(yùn)算行運(yùn)算（不改變碼集，只（不改變碼集，只改變映射規(guī)則）簡(jiǎn)化成改變映射規(guī)則）簡(jiǎn)化成“系統(tǒng)形式系統(tǒng)形式” 。G = Ik P =(1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp 前前k位由單位矩陣位由單位矩陣Ik決定，等于把信息組決定，等于把信息組m原封不動(dòng)搬到碼字的前原封不動(dòng)搬到碼字的前k位；其余的位；其余的n-k位叫冗余位或位叫冗余位或一致校驗(yàn)位一致校驗(yàn)位，是前，是前k個(gè)信息位的線個(gè)信息位的線性組合。這樣生成的（性組合。這樣生成的（n,k）碼叫做）碼叫做系統(tǒng)碼系統(tǒng)

8、碼。 若生成矩陣若生成矩陣G不具備系統(tǒng)形式，則生成的碼叫做不具備系統(tǒng)形式，則生成的碼叫做非系統(tǒng)碼非系統(tǒng)碼。 系統(tǒng)化不改變碼集，只是改變了映射規(guī)則。系統(tǒng)化不改變碼集，只是改變了映射規(guī)則。 第第6 6章章 信道編碼信道編碼 2022-7-39空間構(gòu)成空間構(gòu)成 n維維n重空間有相互重空間有相互正交的正交的n個(gè)基底個(gè)基底 選擇選擇k個(gè)基底構(gòu)成個(gè)基底構(gòu)成碼空間碼空間C 選擇另外的選擇另外的(n-k)個(gè)個(gè)基底構(gòu)成空間基底構(gòu)成空間D C和和D是對(duì)偶的是對(duì)偶的 n維維n重空間重空間V k維維k重重 k維維n重重 n-k維維 信息組信息組 碼空間碼空間 n重重H 空間空間m C第第6 6章章 信道編碼信道編碼

9、2022-7-310校驗(yàn)矩陣校驗(yàn)矩陣 將將D空間的空間的n-k個(gè)基底排列起來可構(gòu)成一個(gè)個(gè)基底排列起來可構(gòu)成一個(gè)(n-k)n矩陣，矩陣，稱為稱為校驗(yàn)矩陣校驗(yàn)矩陣H。用來校驗(yàn)接收到的碼字是否是正確的；。用來校驗(yàn)接收到的碼字是否是正確的；即：若即：若c為為碼空間為為碼空間C中的任意碼字，則中的任意碼字，則 若不滿足此等式，則若不滿足此等式，則c必定不是碼空間必定不是碼空間C中的碼字。中的碼字。0TcH G是是(n,k)碼的生成矩陣，碼的生成矩陣，H是它的校驗(yàn)矩陣；是它的校驗(yàn)矩陣； H是是(n,n-k)對(duì)偶碼的生成矩陣，它的每一行是一個(gè)基底。對(duì)偶碼的生成矩陣，它的每一行是一個(gè)基底。 G則是它的校驗(yàn)矩陣

10、。則是它的校驗(yàn)矩陣。 GHT=0 ，H PT In-k ，二進(jìn)制時(shí)，負(fù)號(hào)可省略。，二進(jìn)制時(shí)，負(fù)號(hào)可省略。如果系統(tǒng)碼的生成矩陣為如果系統(tǒng)碼的生成矩陣為G=IKP,則其對(duì)應(yīng)校驗(yàn)矩陣為則其對(duì)應(yīng)校驗(yàn)矩陣為H=-PTIn-k第第6 6章章 信道編碼信道編碼 2022-7-31121010121022032415062100123456210,101110011100100111001,101110011100100111001) 3 , 7(mmcmmcmmmcmmcmcmcmcmmmcccccccCmmmmG，則有如果信息位為為線性分組碼的生成矩陣已知第第6 6章章 信道編碼信道編碼 2022-7-3

11、1236464326546542165651054540000,0cccccccccccccccccccccccccc由前面的等式可以得到：，即，即，即，即如果寫成矩陣的形式便為：6543210101100001110100001100010001100010Tccccccc 第第6 6章章 信道編碼信道編碼 2022-7-3136.3.2 伴隨式與標(biāo)準(zhǔn)陣列譯碼伴隨式與標(biāo)準(zhǔn)陣列譯碼 m C=(cn-1,c1,c0) R=(rn-1,r1,r0) (n,k) 信道信道定義定義差錯(cuò)圖案差錯(cuò)圖案E(en1,e1,e0) RC (rn-1cn-1,r1c1,r0c0) 因?yàn)橐驗(yàn)镃HT = 0 , 所以

12、所以RHT(CE)HTCHTEHT= EHT 在在HT固定的前提下，固定的前提下，RHT僅僅與差錯(cuò)圖案僅僅與差錯(cuò)圖案E有關(guān)，而與發(fā)送碼有關(guān)，而與發(fā)送碼C無關(guān)。定義無關(guān)。定義伴隨式伴隨式S S = (sn-k-1,s1,s0) = RHT = EHT 從物理意義上看，伴隨式從物理意義上看，伴隨式S并不反映發(fā)送的碼字是什么，而只是并不反映發(fā)送的碼字是什么，而只是反映信道對(duì)碼字造成怎樣的干擾。反映信道對(duì)碼字造成怎樣的干擾。 差錯(cuò)圖案差錯(cuò)圖案E是是n重矢量，共有重矢量，共有2n個(gè)可能的組合，而伴隨式個(gè)可能的組合，而伴隨式S是是(n-k)重矢量，只有重矢量，只有2n-k個(gè)可能的組合，因此不同的差錯(cuò)圖案可

13、能有相個(gè)可能的組合，因此不同的差錯(cuò)圖案可能有相同的伴隨式。同的伴隨式。第第6 6章章 信道編碼信道編碼 2022-7-314差錯(cuò)圖案差錯(cuò)圖案E的求解的求解(1) 可以通過解線性方程求解可以通過解線性方程求解E：S = (sn-k-1,s1, s0) = EHT = (en-1, e1,e0)得到線性方程組：得到線性方程組：sn-k-1=en-1h(n-k-1)(n-1)+e1h(n-k-1)1+ e0 h(n-k-1)0 s1 = en-1h1(n-1) + + e1 h11 + e0 h10s0 = en-1h0(n-1) + + e1 h01 + e0 h00(1)(1)(1)1(1)01

14、(1)11100(1)0100Tn knn kn knnhhhhhhhhh 第第6 6章章 信道編碼信道編碼 2022-7-315 上述方程組中有上述方程組中有n個(gè)未知數(shù)個(gè)未知數(shù)en1, e1,e0 ，卻只有，卻只有n-k個(gè)個(gè)方程，可知方程組有多解。方程，可知方程組有多解。 在有理數(shù)或?qū)崝?shù)域中，少一個(gè)方程就可能導(dǎo)致無限多在有理數(shù)或?qū)崝?shù)域中，少一個(gè)方程就可能導(dǎo)致無限多個(gè)解，而在二元域中，少一個(gè)方程導(dǎo)致兩個(gè)解，少兩個(gè)解，而在二元域中，少一個(gè)方程導(dǎo)致兩個(gè)解，少兩個(gè)方程四個(gè)解，以此類推，少個(gè)方程四個(gè)解，以此類推，少n-( n-k) = k個(gè)方程導(dǎo)致個(gè)方程導(dǎo)致每個(gè)未知數(shù)有每個(gè)未知數(shù)有2k個(gè)解。個(gè)解。 概

15、率譯碼：概率譯碼：把所有把所有2k個(gè)解的重量個(gè)解的重量(差錯(cuò)圖案差錯(cuò)圖案E中中1的個(gè)的個(gè)數(shù)數(shù))作比較，選擇其中最輕者作為作比較，選擇其中最輕者作為E的估值。該方法概的估值。該方法概念上很簡(jiǎn)單但計(jì)算效率不高。念上很簡(jiǎn)單但計(jì)算效率不高。差錯(cuò)圖案差錯(cuò)圖案E的求解的求解(2) 第第6 6章章 信道編碼信道編碼 2022-7-316標(biāo)準(zhǔn)陣列譯碼表標(biāo)準(zhǔn)陣列譯碼表 在伴隨式在伴隨式S的數(shù)目是有限的的數(shù)目是有限的2n-k個(gè)，如果個(gè)，如果n-k不太大不太大，我們可，我們可以預(yù)先把不同以預(yù)先把不同S下的方程組解出來，把各種情況下的最大概下的方程組解出來，把各種情況下的最大概率譯碼輸出率譯碼輸出列成一個(gè)碼表列成一個(gè)

16、碼表。這樣，在實(shí)時(shí)譯碼時(shí)就不必再。這樣，在實(shí)時(shí)譯碼時(shí)就不必再去解方程，而只要象查字典那樣查一下碼表就可以了。這去解方程，而只要象查字典那樣查一下碼表就可以了。這樣構(gòu)造的表格叫做樣構(gòu)造的表格叫做標(biāo)準(zhǔn)陣列譯碼表標(biāo)準(zhǔn)陣列譯碼表。 表中所列碼字是接收到的碼字表中所列碼字是接收到的碼字R； 將將沒有任何差錯(cuò)沒有任何差錯(cuò)時(shí)的收碼時(shí)的收碼R放在第一行，放在第一行，收碼等于發(fā)碼收碼等于發(fā)碼R=C(C Ci,i =0,1,2k-1), 差錯(cuò)圖案為全零差錯(cuò)圖案為全零E0=(0,00)，伴隨，伴隨式為全零式為全零S0=(0,00)。由于有。由于有2k個(gè)碼字，碼表有個(gè)碼字，碼表有2k列列。第第6 6章章 信道編碼信道

17、編碼 2022-7-317 在在第第2到第到第n+1的的n行中差錯(cuò)圖案的所有行中差錯(cuò)圖案的所有重量為重量為1 (共共n個(gè)個(gè))。 如果如果(1+ n)t)01dte 第第6 6章章 信道編碼信道編碼 2022-7-327 設(shè)有設(shè)有8個(gè)碼組個(gè)碼組“000000”，“001110”，“010101”，011011，100011，101101，1101110，111000，試求它們的最小碼距。若用，試求它們的最小碼距。若用于檢錯(cuò)，能檢出幾位錯(cuò)碼？若用于糾錯(cuò)，能糾于檢錯(cuò)，能檢出幾位錯(cuò)碼？若用于糾錯(cuò)，能糾正幾位錯(cuò)碼？若糾檢錯(cuò)結(jié)合，各能糾、檢幾位正幾位錯(cuò)碼？若糾檢錯(cuò)結(jié)合，各能糾、檢幾位錯(cuò)碼？錯(cuò)碼？ 第第6

18、6章章 信道編碼信道編碼 2022-7-328 （n,k）線性碼最小距離）線性碼最小距離dmin的上邊界是的上邊界是n-k+1。如果。如果我們?cè)O(shè)計(jì)的（我們?cè)O(shè)計(jì)的（n,k）線性碼的）線性碼的dmin達(dá)到了達(dá)到了n-k+1，就是，就是達(dá)到了設(shè)計(jì)性能的極點(diǎn)。因此，達(dá)到了設(shè)計(jì)性能的極點(diǎn)。因此，dmin n-k+1的碼稱的碼稱為為極大最小距離碼極大最小距離碼 (MDC)。 (1) 二進(jìn)制碼中，除了將一位信息重復(fù)二進(jìn)制碼中，除了將一位信息重復(fù)n 次的次的 （n,1）碼外，不存在其它二進(jìn)制碼外，不存在其它二進(jìn)制MDC碼；碼； (2) 非二進(jìn)制碼中，非二進(jìn)制碼中，MDC碼是存在的，如碼是存在的，如RS碼碼 （

19、reed-solomon)。MDC碼碼（Maximized minimum Distance Code）第第6 6章章 信道編碼信道編碼 2022-7-329 糾錯(cuò)能力糾錯(cuò)能力t只是說明距離只是說明距離t的差錯(cuò)一定能糾，的差錯(cuò)一定能糾，并非說并非說距距離大于離大于t的差錯(cuò)一定不能糾。的差錯(cuò)一定不能糾。 總體的、平均的糾錯(cuò)能力不但與總體的、平均的糾錯(cuò)能力不但與最小距離最小距離有關(guān)，而且有關(guān)，而且與與其余碼距其余碼距或者說與碼字的或者說與碼字的重量分布特性重量分布特性有關(guān)。把碼有關(guān)。把碼距（碼重）的分布特性稱為距（碼重）的分布特性稱為距離（重量）譜距離（重量）譜，其中最，其中最小重量就是小重量就是

20、dmin。當(dāng)所有碼距相差不大時(shí)，性能較好。當(dāng)所有碼距相差不大時(shí)，性能較好。重量譜多項(xiàng)式表示：重量譜多項(xiàng)式表示： 含義：在碼長含義：在碼長n的碼集里，包含重量為的碼集里，包含重量為0的碼字的碼字A0個(gè)，個(gè)，重量為重量為1的碼字的碼字A1個(gè)，個(gè)，-，重量為，重量為n的碼字的碼字An個(gè)。個(gè)。 20121nniniiA xAAxA xA xAx重量譜重量譜第第6 6章章 信道編碼信道編碼 2022-7-330 任何一個(gè)二元任何一個(gè)二元(n,k)線性分組碼都有線性分組碼都有2n-k個(gè)伴隨式，假如個(gè)伴隨式，假如該碼的糾錯(cuò)能力是該碼的糾錯(cuò)能力是t，則對(duì)于任何一個(gè)重量小于等于，則對(duì)于任何一個(gè)重量小于等于t的的

21、差錯(cuò)圖案，都應(yīng)有一個(gè)伴隨式與之對(duì)應(yīng)，也就是說，差錯(cuò)圖案，都應(yīng)有一個(gè)伴隨式與之對(duì)應(yīng)，也就是說，伴隨式的數(shù)目滿足條件伴隨式的數(shù)目滿足條件 上式稱作上式稱作漢明限漢明限，任何一個(gè)糾，任何一個(gè)糾t碼都應(yīng)滿足上述碼都應(yīng)滿足上述條件。條件。 02012tnkinnnnnti6.3.4完備碼完備碼(Perfect code) 第第6 6章章 信道編碼信道編碼 2022-7-331完備碼完備碼 某二元某二元(n,k)線性分組碼能使等式線性分組碼能使等式 成立，即該碼的伴隨式數(shù)目成立，即該碼的伴隨式數(shù)目不多不少恰好和不大于不多不少恰好和不大于t個(gè)差錯(cuò)的圖案數(shù)目相等個(gè)差錯(cuò)的圖案數(shù)目相等，相當(dāng)于在標(biāo)準(zhǔn)譯碼陣列中能，

22、相當(dāng)于在標(biāo)準(zhǔn)譯碼陣列中能將所有重量不大于將所有重量不大于t的的差錯(cuò)圖案差錯(cuò)圖案選作選作陪集首陪集首，而沒有一，而沒有一個(gè)陪集首的重量大于個(gè)陪集首的重量大于t，這時(shí)的校驗(yàn)位得到最充分的利，這時(shí)的校驗(yàn)位得到最充分的利用。這樣的二元用。這樣的二元(n,k)線性分組碼稱為線性分組碼稱為完備碼完備碼。 02tnkini第第6 6章章 信道編碼信道編碼 2022-7-332漢明碼漢明碼(Hamming Code) 漢明碼的漢明碼的糾錯(cuò)能力糾錯(cuò)能力t = 1，既有二進(jìn)制的，也有非二進(jìn)，既有二進(jìn)制的，也有非二進(jìn)制的。二進(jìn)制時(shí)，漢明碼碼長制的。二進(jìn)制時(shí)，漢明碼碼長n和信息位和信息位k服從以下規(guī)服從以下規(guī)律：律：

23、(n,k)=(2m-1, 2m-1-m)，其中其中m= n-k，是正整數(shù)。，是正整數(shù)。 當(dāng)當(dāng)m3、4、5、6、7、8時(shí)，有漢明碼時(shí)，有漢明碼(7,4)、(15,11)、(31,26)、(63,57)、(127,120) 漢明碼是完備碼漢明碼是完備碼，因?yàn)樗鼭M足上述等式。，因?yàn)樗鼭M足上述等式。1011(21)22mmnkinni第第6 6章章 信道編碼信道編碼 2022-7-333漢明碼校驗(yàn)矩陣的構(gòu)成漢明碼校驗(yàn)矩陣的構(gòu)成 漢明碼的校驗(yàn)矩陣漢明碼的校驗(yàn)矩陣H具有特殊的性質(zhì)，能使具有特殊的性質(zhì)，能使構(gòu)造方法簡(jiǎn)化。一個(gè)構(gòu)造方法簡(jiǎn)化。一個(gè)(n,k)碼的校驗(yàn)矩陣有碼的校驗(yàn)矩陣有nk行和行和n列，二進(jìn)制時(shí)列

24、，二進(jìn)制時(shí)n-k個(gè)碼元所能組成的列矢?jìng)€(gè)碼元所能組成的列矢量總數(shù)是量總數(shù)是2n-k-1 =2m-1= n, 恰好和校驗(yàn)矩陣的恰好和校驗(yàn)矩陣的列列數(shù)相等數(shù)相等。只要排列所有列，通過。只要排列所有列，通過列置換列置換將矩陣將矩陣H轉(zhuǎn)換成轉(zhuǎn)換成系統(tǒng)形式系統(tǒng)形式，就可以進(jìn)一步得到相應(yīng)的，就可以進(jìn)一步得到相應(yīng)的生成矩陣生成矩陣G。 第第6 6章章 信道編碼信道編碼 2022-7-334例例 6.4 構(gòu)造一個(gè)構(gòu)造一個(gè)m=3的二元的二元(7，4)漢明碼。漢明碼。解：先利用漢明碼的特性構(gòu)造一個(gè)解：先利用漢明碼的特性構(gòu)造一個(gè)(7，4)漢明碼的漢明碼的校驗(yàn)矩陣校驗(yàn)矩陣H，再通過列置換將它變?yōu)橄到y(tǒng)形式：，再通過列置換

25、將它變?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 = PT I3 1 0 1 0 1 0 1 1 1 0 1 0 0 1再得生成矩陣再得生成矩陣G為為 1 0 0 0 1 0 1 G = I4 P = 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 第第6 6章章 信道編碼信道編碼 2022-7-335高萊（高萊（Golay）碼）碼 二進(jìn)制（二進(jìn)制（23，12）線性碼）線性碼，其最小距離，其最小距離dmin7，糾，糾錯(cuò)能力錯(cuò)能力t =3。 是完備碼，因?yàn)闈M

26、足等式是完備碼，因?yàn)闈M足等式 223-12 = 2048 = 在在(23,12)碼上添加一位奇偶位即得二進(jìn)制線性（碼上添加一位奇偶位即得二進(jìn)制線性（24，12）擴(kuò)展高萊碼擴(kuò)展高萊碼，其最小距離，其最小距離dmin8。 2323231123第第6 6章章 信道編碼信道編碼 2022-7-3366.3.5 6.3.5 循循 環(huán)環(huán) 碼碼 1 循環(huán)碼的概念循環(huán)碼的概念循環(huán)碼是循環(huán)碼是1957年由普蘭奇年由普蘭奇(Prange)提出的。它是線性分組碼中提出的。它是線性分組碼中最重要的一個(gè)子類。目前，實(shí)用差錯(cuò)控制編碼中所使用的線性分最重要的一個(gè)子類。目前，實(shí)用差錯(cuò)控制編碼中所使用的線性分組碼幾乎都是循環(huán)碼

27、或循環(huán)碼的子類。組碼幾乎都是循環(huán)碼或循環(huán)碼的子類。 循環(huán)碼除了具有循環(huán)碼除了具有(n,k)線性分組碼的一般性質(zhì)外，還具有線性分組碼的一般性質(zhì)外，還具有循環(huán)循環(huán)性性，即若將其任意一個(gè)碼字，即若將其任意一個(gè)碼字(cn-1,cn-2,c1,c0)的碼元的碼元向右或向左循環(huán)向右或向左循環(huán)移一位移一位，所得的，所得的(c0,cn-1,cn-2,c1)或或(cn-2,c1,c0,cn-1)仍然是碼字。仍然是碼字。第第6 6章章 信道編碼信道編碼 2022-7-337表表 6-3-1（7， 3）循環(huán)碼）循環(huán)碼 第第6 6章章 信道編碼信道編碼 2022-7-3382 2 循環(huán)碼的碼多項(xiàng)循環(huán)碼的碼多項(xiàng)式式在整

28、數(shù)運(yùn)算中，有模在整數(shù)運(yùn)算中，有模n運(yùn)算。例如，在模運(yùn)算。例如，在模2運(yùn)算中運(yùn)算中1+1=20 (模模2)， 1+2=31 (模模2)， =60 (模模2) 對(duì)于整數(shù)對(duì)于整數(shù)m進(jìn)行模進(jìn)行模n運(yùn)算運(yùn)算, 有有 )(npnpQnm模式中，式中，Q為整數(shù)，為整數(shù)，pn。這說明：在模。這說明：在模n運(yùn)算下，一個(gè)整數(shù)運(yùn)算下，一個(gè)整數(shù)m等等于它被于它被n除得的余數(shù)。例如，在模除得的余數(shù)。例如，在模3運(yùn)算中，運(yùn)算中，7/3=2+1/31 (模模3)。 對(duì)碼多項(xiàng)式也可以按模運(yùn)算。若任意一個(gè)多項(xiàng)式對(duì)碼多項(xiàng)式也可以按模運(yùn)算。若任意一個(gè)多項(xiàng)式F(x)被一個(gè)被一個(gè)n次多項(xiàng)式次多項(xiàng)式N(x)除，得到商式除，得到商式Q(x

29、)和一個(gè)次數(shù)小于和一個(gè)次數(shù)小于n的余式的余式R(x)， 即即 第第6 6章章 信道編碼信道編碼 2022-7-339F(x)=N(x)Q(x)+R(x) 則在按模則在按模N(x)運(yùn)算下，有運(yùn)算下，有 )()(xRxF(模N(x) 此時(shí)，碼多項(xiàng)式系數(shù)仍按模此時(shí)，碼多項(xiàng)式系數(shù)仍按模2運(yùn)算，系數(shù)只取運(yùn)算，系數(shù)只取0和和1。例如。例如F(x)=x4+x2+1被被N(x)=x3+1除，得到余式除，得到余式R(x)=x2+x+1，即，即x4+x2+1 x2+x+1（模（模(x3+1)。 xxxxx424311x12 xx第第6 6章章 信道編碼信道編碼 2022-7-340 在在(n, k)循環(huán)碼中，循環(huán)

30、碼中， 若若C(x)是一個(gè)長度為是一個(gè)長度為n的碼字，則的碼字，則xiC(x)在按模在按模(xn+1)運(yùn)算下，也是該循環(huán)碼中的一個(gè)碼字。運(yùn)算下，也是該循環(huán)碼中的一個(gè)碼字。 即若即若 xiC(x)=Q(x)(xn+1)+C(x)C(x) (模模(xn+1) 則則C(x)也是該循環(huán)碼中的一個(gè)碼組。其中，也是該循環(huán)碼中的一個(gè)碼組。其中，i為碼字左移的位數(shù)，為碼字左移的位數(shù)，Q(x)為為xiC(x)除以除以xn+1的商式，的商式，C(x)為為xiC(x)被被xn+1除得的余式。除得的余式。 例如碼字例如碼字(1101001)， 若將此碼字左移兩位，若將此碼字左移兩位， 可得到可得到 x2(x6+x5+

31、x3+1)=(x+1)(x7+1)+x5+x2+x+1 即即Q(x)=x+1；C(x)=x5+x2+x+1，對(duì)應(yīng)的碼字為，對(duì)應(yīng)的碼字為(0100111)，與直接，與直接對(duì)碼字進(jìn)行循環(huán)左移兩位的結(jié)果相同。對(duì)碼字進(jìn)行循環(huán)左移兩位的結(jié)果相同。 第第6 6章章 信道編碼信道編碼 2022-7-3413 循環(huán)碼的生成多項(xiàng)式和生成矩陣循環(huán)碼的生成多項(xiàng)式和生成矩陣1） 循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式如果一種碼的所有碼多項(xiàng)式都是多項(xiàng)式如果一種碼的所有碼多項(xiàng)式都是多項(xiàng)式g(x)的倍式，則稱的倍式，則稱g(x)為該碼的生成多項(xiàng)式為該碼的生成多項(xiàng)式。循環(huán)碼的碼多項(xiàng)式都是最低次碼多項(xiàng)式。循環(huán)碼的碼多項(xiàng)式都是最低

32、次碼多項(xiàng)式g(x)的倍式。例如的倍式。例如表表6-3-1所示的所示的(7，3)循環(huán)碼中，生成多項(xiàng)式循環(huán)碼中，生成多項(xiàng)式g(x)=x4+x3+x2+1。顯然，循環(huán)碼中次數(shù)最低的多項(xiàng)式。顯然，循環(huán)碼中次數(shù)最低的多項(xiàng)式(除全除全0碼字外碼字外)就是生成多項(xiàng)式就是生成多項(xiàng)式g(x)。 可以證明，可以證明，g(x)是常數(shù)項(xiàng)為是常數(shù)項(xiàng)為1的的r=(n-k)次多項(xiàng)式，是次多項(xiàng)式，是xn+1的一的一個(gè)因子。一旦確定了個(gè)因子。一旦確定了g(x)，則整個(gè)，則整個(gè)(n, k)循環(huán)碼就被確定了。循環(huán)碼就被確定了。 如何確定任意一個(gè)如何確定任意一個(gè)(n,k)循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式g(x)?第第6 6章章

33、信道編碼信道編碼 2022-7-342例如，例如，(x7+1)可以分解為：可以分解為：x7+1=(x+1)(x3+x2+1)(x3+x+1)。為。為了求出了求出(7，3)循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式g(x)，需要從中找到一個(gè)，需要從中找到一個(gè)r=nk=73=4次的因子。不難看出，次的因子。不難看出， 這樣的因子有兩個(gè)：這樣的因子有兩個(gè)： (x+1)(x3+x2+1)=x4+x2+x+1； (x+1)(x3+x+1)=x4+x3+x2+1。 這兩個(gè)因子都可以作為生成多項(xiàng)式。這兩個(gè)因子都可以作為生成多項(xiàng)式。 注意選用不同的生成多注意選用不同的生成多項(xiàng)式，所產(chǎn)生的循環(huán)碼的碼字不同。項(xiàng)式，所產(chǎn)

34、生的循環(huán)碼的碼字不同。 (n,k) 循環(huán)碼的生成多項(xiàng)式滿足下面三條性質(zhì)：循環(huán)碼的生成多項(xiàng)式滿足下面三條性質(zhì)： (1) g(x)是一個(gè)（是一個(gè)（nk）次多項(xiàng)式。）次多項(xiàng)式。 (2) g(x)的常數(shù)項(xiàng)不為的常數(shù)項(xiàng)不為0。 (3) g(x)是是xn+1的一個(gè)因子。的一個(gè)因子。 第第6 6章章 信道編碼信道編碼 2022-7-3432 2） 循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣G常用多項(xiàng)式的形式來表示，即常用多項(xiàng)式的形式來表示，即 )()()()()(21xgxxgxgxxgxxGkk第第6 6章章 信道編碼信道編碼 2022-7-344例如例如表表6-3-1所示的所示的(

35、7，3)循環(huán)碼，循環(huán)碼，n=7,k=3, r=4，其生成，其生成多項(xiàng)式多項(xiàng)式g(x)=x4+x3+x2+1，可得，可得 1)()()()(23434524562xxxxxxxxxxxxgxxgxgxxG100010101110111011001G即 110011111101100010001G 第第6 6章章 信道編碼信道編碼 2022-7-3454 4 循環(huán)碼的校驗(yàn)（監(jiān)督）多項(xiàng)式和校驗(yàn)（監(jiān)督）矩陣循環(huán)碼的校驗(yàn)（監(jiān)督）多項(xiàng)式和校驗(yàn)（監(jiān)督）矩陣1 1） 循環(huán)碼的監(jiān)督多項(xiàng)式循環(huán)碼的監(jiān)督多項(xiàng)式由于由于g(x)能除盡能除盡xn+1，因此有，因此有 )(1)(xgxxhn其中，其中，g(x)是常數(shù)項(xiàng)為是

36、常數(shù)項(xiàng)為1的的r次生成多項(xiàng)式次生成多項(xiàng)式；h(x)是常數(shù)項(xiàng)為是常數(shù)項(xiàng)為1的的k次次多項(xiàng)式多項(xiàng)式，稱為，稱為監(jiān)督多項(xiàng)式監(jiān)督多項(xiàng)式。令。令h(x)=xk+hk-1xk-1+h1x+1，h(x)的的逆多項(xiàng)式逆多項(xiàng)式h*(x)=xk+h1xk-1+h2xk-2+hk-1x+1（ h*(x)= xkh(1/x)）。例如例如(7，3)循環(huán)碼中，循環(huán)碼中，g(x)=x4+x3+x2+1，則，則 1)(1)(1)(3*237xxxhxxxgxxh第第6 6章章 信道編碼信道編碼 2022-7-3462 2）循環(huán)碼的監(jiān)督矩陣）循環(huán)碼的監(jiān)督矩陣由監(jiān)督多項(xiàng)式很容易得到循環(huán)碼的監(jiān)督矩陣，由監(jiān)督多項(xiàng)式很容易得到循環(huán)碼的

37、監(jiān)督矩陣， 即即 )()()()(*1xhxxhxhxxHkn例如可得例如可得(7， 3)循環(huán)碼的監(jiān)督矩陣為循環(huán)碼的監(jiān)督矩陣為 1)()()()()(324235346*2*3xxxxxxxxxxxxhxxhxhxxhxxH1 0 1 1 0 0 00 1 0 1 1 0 00 0 1 0 1 1 00 0 0 1 0 1 1H 第第6 6章章 信道編碼信道編碼 2022-7-347 【例例】 已知（已知（7，4）循環(huán)碼的全部碼組為）循環(huán)碼的全部碼組為0000000， 0100111，1000101，1100010，0001011，0101100， 1001110， 1101001，00101

38、10，0110001，1010011， 1110100， 0011101， 0111010，1011000，1111111。試求該循環(huán)碼的生成多項(xiàng)式、。試求該循環(huán)碼的生成多項(xiàng)式、 生成矩陣和監(jiān)生成矩陣和監(jiān)督矩陣。督矩陣。 解解 （1） 求生成多項(xiàng)式求生成多項(xiàng)式g(x)。已知。已知 n=7，k=4， r=nk=74=3x7+1=(x+1)(x3+x+1)(x3+x2+1) 因?yàn)樯啥囗?xiàng)式因?yàn)樯啥囗?xiàng)式g(x)必須滿足：必須滿足： 是一個(gè)是一個(gè)nk=3次多項(xiàng)式，其次多項(xiàng)式，其常數(shù)項(xiàng)不為常數(shù)項(xiàng)不為0，是，是x7+1的一個(gè)因子，顯然滿足上述條件的因子有的一個(gè)因子，顯然滿足上述條件的因子有兩個(gè)兩個(gè): x

39、3+x+1和和x3+x2+1。由于本題給出了循環(huán)碼的全部碼字，因。由于本題給出了循環(huán)碼的全部碼字，因此符合本題條件的生成多項(xiàng)式此符合本題條件的生成多項(xiàng)式g(x)只有一個(gè)，假定只有一個(gè)，假定g(x)=x3+x+1。 第第6 6章章 信道編碼信道編碼 2022-7-348（2） 求生成矩陣求生成矩陣G。 1)()()()()(32423534623xxxxxxxxxxxxgxxgxgxxgxxG0001011001011001011001011000G0001011001011001001111000101QIGk 第第6 6章章 信道編碼信道編碼 2022-7-349經(jīng)檢驗(yàn)，由經(jīng)檢驗(yàn)，由g(x)

40、=x3+x+1得到的生成矩陣得到的生成矩陣G能產(chǎn)生本題所給能產(chǎn)生本題所給定的全部生成碼字。而定的全部生成碼字。而g(x)=x3+x2+1所生成的循環(huán)碼與本題所所生成的循環(huán)碼與本題所給的碼組不符。給的碼組不符。 （3） 求監(jiān)督矩陣。求監(jiān)督矩陣。 110100101110101110100)(,110101111110,011110111101TrIPHQPQ第第6 6章章 信道編碼信道編碼 2022-7-350例例 6.5 研究一個(gè)長度研究一個(gè)長度n=7的循環(huán)碼的構(gòu)成方法的循環(huán)碼的構(gòu)成方法(1) 對(duì)對(duì)(x7+1)作分解，找出作分解，找出n-k次因式。次因式。 x7+1(x+1)(x3+x2+1)

41、(x3+x+1)， n-k 因式因式g(x) 對(duì)偶式對(duì)偶式h(x) 循環(huán)碼循環(huán)碼 1 (x+1) (x3+x2+1)(x3+x+1) (7,6) 3 (x3+x2+1) (x+1)(x3+x+1) (7,4) 3 (x3+x+1) (x+1)(x3+x2+1) (7,4) 4 (x+1)( x3+x2+1) (x3+x+1) (7,3) 4 (x+1)(x3+x+1) (x3+x2+1) (7,3) 6 (x3+x2+1)(x3+x+1) (x+1) (7,1)第第6 6章章 信道編碼信道編碼 2022-7-351(2) 構(gòu)成構(gòu)成(7,3)循環(huán)碼：循環(huán)碼：選選g(x) =(x+1) (x3+x

42、+1) = (x4+x3+x2+1)，則，則C(x)=m(x)g(x)= (m2x2+m1x+m0) (x4+x3+x2+1)。 當(dāng)輸入信息當(dāng)輸入信息m=(011)時(shí)，時(shí)，m(x)=(x+1)，C(x)=( x+ 1)(x4x3x21) = x5+ x2+ x1+ 1，對(duì)應(yīng)碼矢對(duì)應(yīng)碼矢C = (0100111)。 例例 6.5 研究一個(gè)長度研究一個(gè)長度n=7的循環(huán)碼的構(gòu)成方法的循環(huán)碼的構(gòu)成方法第第6 6章章 信道編碼信道編碼 2022-7-352信息矢量信息矢量m(m2 m1 m0) 碼矢碼矢C(c6c5c4c3c2c1c0) 000001010011100101110111000000000

43、11101011101001001111110100110100110011101010011例例 6.5 研究一個(gè)長度研究一個(gè)長度n=7的循環(huán)碼的構(gòu)成方法的循環(huán)碼的構(gòu)成方法第第6 6章章 信道編碼信道編碼 2022-7-3535 循環(huán)碼的系統(tǒng)化編碼方法循環(huán)碼的系統(tǒng)化編碼方法循環(huán)碼編碼時(shí)，首先要根據(jù)給定的循環(huán)碼編碼時(shí)，首先要根據(jù)給定的(n,k)值來選定生成多項(xiàng)式值來選定生成多項(xiàng)式g(x)，即從，即從(xn+1)的因式中選定一個(gè)的因式中選定一個(gè)r=nk次多項(xiàng)式作為次多項(xiàng)式作為g(x)。 根根據(jù)據(jù)循環(huán)碼中的所有碼多項(xiàng)式都可被循環(huán)碼中的所有碼多項(xiàng)式都可被g(x)整除整除這條原則，就可以對(duì)這條原則，就

44、可以對(duì)給定的信息碼元進(jìn)行編碼。假設(shè)編碼前的給定的信息碼元進(jìn)行編碼。假設(shè)編碼前的信息碼多項(xiàng)式為信息碼多項(xiàng)式為m(x)，其次數(shù)小于其次數(shù)小于k。用。用xr乘以乘以m(x)，得到，得到xrm(x)的次數(shù)小于的次數(shù)小于n。 用用xrm(x) 除以除以g(x) ，得到，得到余式余式R(x), R(x)次數(shù)必小于次數(shù)必小于g(x)的次數(shù)，即小于的次數(shù)，即小于(nk)。將此余數(shù)。將此余數(shù)R(x)加在信息碼元之后作為加在信息碼元之后作為監(jiān)督位監(jiān)督位，即將，即將R(x)與與xrm(x)相加，得到的多項(xiàng)式必為相加，得到的多項(xiàng)式必為碼多項(xiàng)式碼多項(xiàng)式。因?yàn)樗啬鼙?。因?yàn)樗啬鼙籫(x)整除，整除，且最高次數(shù)不大于且最

45、高次數(shù)不大于(n-1)。因此，循環(huán)碼的碼多項(xiàng)式為。因此，循環(huán)碼的碼多項(xiàng)式為 )()()(xRxmxxCr第第6 6章章 信道編碼信道編碼 2022-7-354循環(huán)碼的編碼方法可歸納如下：循環(huán)碼的編碼方法可歸納如下： (1) 用用xr乘以乘以m(x)。該運(yùn)算的作用是在信息碼元后附加上該運(yùn)算的作用是在信息碼元后附加上r個(gè)個(gè)“0”。例如在。例如在(7，3)碼中信息碼組為碼中信息碼組為(110)，它可以寫成，它可以寫成m(x)=x2+x；由于由于r=nk=73=4，所以，所以xrm(x)=x4(x2+x)=x6+x5，它表示碼組，它表示碼組1100000，即信息碼元后附加四個(gè)，即信息碼元后附加四個(gè)“0

46、”。 (2) 用用xrm(x) 除以除以g(x) ， 得到商得到商Q(x)和余式和余式R(x)， 即即 )()()()()(xgxRxQxgxmxr第第6 6章章 信道編碼信道編碼 2022-7-355若選定若選定g(x)=x4+x2+x+1，則有，則有 11) 1(1)()(24222456xxxxxxxxxxxxgxmxr即即Q(x)=x2+x+1，R(x)=x2+1。 上式等效于上式等效于 10111101111101111100000 (3) 編碼器輸出的碼字為編碼器輸出的碼字為 C(x)=xrm(x)+R(x)=1100000+101=1100101第第6 6章章 信道編碼信道編碼

47、2022-7-3566 循環(huán)碼的譯碼方法循環(huán)碼的譯碼方法1. 循環(huán)碼的檢錯(cuò)循環(huán)碼的檢錯(cuò)由于任一碼多項(xiàng)式由于任一碼多項(xiàng)式C(x)都應(yīng)能被生成多項(xiàng)式都應(yīng)能被生成多項(xiàng)式g(x)整除，整除， 因此因此在 接 收 端 可 以 將 接 收 碼 組在 接 收 端 可 以 將 接 收 碼 組 B ( x ) 用 生 成 多 項(xiàng) 式 去 除 ， 即用 生 成 多 項(xiàng) 式 去 除 ， 即。當(dāng)傳輸過程中沒有發(fā)生差錯(cuò)時(shí)，。當(dāng)傳輸過程中沒有發(fā)生差錯(cuò)時(shí)， 接收碼組與發(fā)送碼組相同接收碼組與發(fā)送碼組相同(C(x)=B(x)， 即接收碼組即接收碼組B(x)必定能被必定能被g(x)整除，即整除，即R(x)=0。 當(dāng)當(dāng)傳輸過程中發(fā)

48、生差錯(cuò)時(shí)，傳輸過程中發(fā)生差錯(cuò)時(shí)，C(x)B(x)， B(x)除以除以g(x)時(shí)必定除不盡時(shí)必定除不盡而有余項(xiàng)，即而有余項(xiàng)，即R(x)0。 因此，可以用余項(xiàng)因此，可以用余項(xiàng)R(x)是否為零來判定碼是否為零來判定碼組中是否有差錯(cuò)。組中是否有差錯(cuò)。 )()()()()(xgxRxQxgxB第第6 6章章 信道編碼信道編碼 2022-7-357應(yīng)當(dāng)注意，當(dāng)接收碼組中的錯(cuò)誤數(shù)量超出編碼的檢錯(cuò)能力應(yīng)當(dāng)注意，當(dāng)接收碼組中的錯(cuò)誤數(shù)量超出編碼的檢錯(cuò)能力時(shí)，有錯(cuò)誤的接收碼組也可能被時(shí)，有錯(cuò)誤的接收碼組也可能被g(x)整除。此時(shí)，差錯(cuò)就無法整除。此時(shí)，差錯(cuò)就無法檢出。這種錯(cuò)誤稱為不可檢錯(cuò)碼。檢出。這種錯(cuò)誤稱為不可檢

49、錯(cuò)碼。 【 例例 】 已 知 （已 知 （ 1 5 ， 7 ） 循 環(huán) 碼 的 生 成 多 項(xiàng) 式 為） 循 環(huán) 碼 的 生 成 多 項(xiàng) 式 為g(x)=x8+x7+x6+x4+1，試問接收碼組，試問接收碼組B(x)=x+x5+x+1是否有誤。是否有誤。 解解 因?yàn)橐驗(yàn)?01)(1111)()(36746783673564678514xxxxxRxxxxxxxxxxxxxxxxxxxgxB所以接收碼所以接收碼B(x)=x14+x5+x+1有誤。有誤。 第第6 6章章 信道編碼信道編碼 2022-7-3582. 循環(huán)碼的糾錯(cuò)循環(huán)碼的糾錯(cuò)在糾錯(cuò)時(shí)，譯碼方法比檢錯(cuò)時(shí)復(fù)雜。為了能糾錯(cuò)，要求每個(gè)在糾錯(cuò)時(shí)

50、，譯碼方法比檢錯(cuò)時(shí)復(fù)雜。為了能糾錯(cuò)，要求每個(gè)可糾正的錯(cuò)誤圖樣必須與一個(gè)特定的余式有一一對(duì)應(yīng)關(guān)系?？杉m正的錯(cuò)誤圖樣必須與一個(gè)特定的余式有一一對(duì)應(yīng)關(guān)系。 只有只有這樣才可能按此余式惟一地決定錯(cuò)誤圖樣，從而糾正錯(cuò)誤。這樣才可能按此余式惟一地決定錯(cuò)誤圖樣，從而糾正錯(cuò)誤。 循環(huán)循環(huán)碼的糾錯(cuò)譯碼方法如下：碼的糾錯(cuò)譯碼方法如下： (1) 用生成多項(xiàng)式用生成多項(xiàng)式g(x)除以接收碼組除以接收碼組B(x)，得到余式，得到余式R(x)。 (2) 按照余式按照余式R(x)， 用查表方法或計(jì)算校正子得出錯(cuò)誤圖樣用查表方法或計(jì)算校正子得出錯(cuò)誤圖樣E(x)， 就可以確定錯(cuò)碼的位置。就可以確定錯(cuò)碼的位置。 (3) 從從B(

51、x)中減去中減去E(x)，便得到已經(jīng)糾正錯(cuò)碼的原發(fā)送碼組，便得到已經(jīng)糾正錯(cuò)碼的原發(fā)送碼組C(x)。 常用的常用的循環(huán)碼譯碼循環(huán)碼譯碼方法主要有梅吉特譯碼、方法主要有梅吉特譯碼、 捕錯(cuò)譯碼和大數(shù)捕錯(cuò)譯碼和大數(shù)邏輯譯碼等。邏輯譯碼等。 第第6 6章章 信道編碼信道編碼 2022-7-359BCH碼碼BCH碼是一種非常重要的碼是一種非常重要的循環(huán)碼循環(huán)碼，它在編碼理論研究和實(shí)際，它在編碼理論研究和實(shí)際應(yīng)用上占有重要地位。應(yīng)用上占有重要地位。BCH碼的重要性體現(xiàn)在：碼的重要性體現(xiàn)在： 它有嚴(yán)密的代數(shù)結(jié)構(gòu)，是目前研究得它有嚴(yán)密的代數(shù)結(jié)構(gòu)，是目前研究得最透徹最透徹的一類碼；的一類碼； 它的它的生成多項(xiàng)式生

52、成多項(xiàng)式g(x)與最小碼距與最小碼距d0之間有密切的關(guān)系，人們之間有密切的關(guān)系，人們能根據(jù)所要求的糾錯(cuò)能力能根據(jù)所要求的糾錯(cuò)能力(對(duì)對(duì)d0的要求的要求)，很容易地構(gòu)造出，很容易地構(gòu)造出BCH碼；碼； BCH編編/譯碼比較簡(jiǎn)單，易于實(shí)現(xiàn)，是線性分組中應(yīng)用最為譯碼比較簡(jiǎn)單，易于實(shí)現(xiàn)，是線性分組中應(yīng)用最為普遍的一類碼。普遍的一類碼。 第第6 6章章 信道編碼信道編碼 2022-7-360首先引入首先引入本原多項(xiàng)式本原多項(xiàng)式的概念。如果一個(gè)的概念。如果一個(gè)m次多項(xiàng)式次多項(xiàng)式F(x)滿足滿足以下條件：以下條件： (1) F(x)是既約多項(xiàng)式是既約多項(xiàng)式(即不能分解因式的多項(xiàng)式即不能分解因式的多項(xiàng)式)。(

53、2) F(x)可整除可整除(xp+1)，p=2m1。 (3) F(x)除不盡除不盡(xq+1)，qp。則稱則稱F(x)是一個(gè)最高次數(shù)為是一個(gè)最高次數(shù)為m的本原多項(xiàng)式。的本原多項(xiàng)式。 例如當(dāng)例如當(dāng)m=3時(shí)，時(shí)， x2m-1+1=x7+1，此時(shí)最高次為，此時(shí)最高次為3的本原多項(xiàng)式為的本原多項(xiàng)式為x3+x2+1和和x3+x+1， 它們都能整除它們都能整除x7+1，但不能整除，但不能整除x6+1，x5+1等。等。 BCH碼可分為碼可分為本原本原BCH碼碼和和非本原非本原BCH碼碼。本原本原BCH碼是指碼是指在生成多項(xiàng)式在生成多項(xiàng)式g(x)中，含有最高次數(shù)為中，含有最高次數(shù)為m的一個(gè)本原多項(xiàng)式，且碼的一

54、個(gè)本原多項(xiàng)式，且碼長長n=2m1。而而非本原非本原BCH碼的生成多項(xiàng)式碼的生成多項(xiàng)式g(x)中不含有這種本原中不含有這種本原多項(xiàng)式，且碼長多項(xiàng)式，且碼長n是是2m1的一個(gè)因子，即碼長的一個(gè)因子，即碼長n一定能除盡一定能除盡2m1。第第6 6章章 信道編碼信道編碼 2022-7-361BCH碼的碼長碼的碼長n、監(jiān)督位、監(jiān)督位r和糾錯(cuò)能力和糾錯(cuò)能力t之間的關(guān)系如下之間的關(guān)系如下： 對(duì)于任意整數(shù)對(duì)于任意整數(shù)m(m3)和和tm/2，一定存在一個(gè)二進(jìn)制，一定存在一個(gè)二進(jìn)制BCH碼，碼，其碼長其碼長n=2m1，監(jiān)督位數(shù)，監(jiān)督位數(shù)r=nkmt，并能糾正所有不大于，并能糾正所有不大于t的的隨機(jī)錯(cuò)誤。隨機(jī)錯(cuò)誤。

55、 為了便于應(yīng)用，表為了便于應(yīng)用，表6-3-2 給出了碼長給出了碼長n63的本原的本原BCH碼，表碼，表 6-3-3給出了碼長給出了碼長n73的非本原的非本原BCH碼。其中碼。其中g(shù)(x)欄下的數(shù)字是八進(jìn)制欄下的數(shù)字是八進(jìn)制數(shù)，用于表示生成多項(xiàng)式數(shù)，用于表示生成多項(xiàng)式g(x)中的各項(xiàng)系數(shù)值。例如表中的各項(xiàng)系數(shù)值。例如表6-3-2中，于中，于八進(jìn)制數(shù)八進(jìn)制數(shù)“23”對(duì)應(yīng)的二進(jìn)制碼為對(duì)應(yīng)的二進(jìn)制碼為“010011”，故生成多項(xiàng)式，故生成多項(xiàng)式g(x)=x4+x+1。 第第6 6章章 信道編碼信道編碼 2022-7-362表表 6-3-2n63的本原的本原BCH碼碼 第第6 6章章 信道編碼信道編碼

56、2022-7-363表表6-3-3 部分非本原部分非本原BCH碼碼 在實(shí)際應(yīng)用中，如果要求在實(shí)際應(yīng)用中，如果要求BCH碼的碼長不是碼的碼長不是2m-1或它的因或它的因子，子， 則可采用縮短碼的方法來構(gòu)造縮短則可采用縮短碼的方法來構(gòu)造縮短BCH碼。碼。 第第6 6章章 信道編碼信道編碼 2022-7-364RS碼碼RS碼是里德碼是里德-索洛蒙索洛蒙(Reed-Solomon)碼的簡(jiǎn)稱。它是一種多進(jìn)碼的簡(jiǎn)稱。它是一種多進(jìn)制制BCH碼，具有很強(qiáng)的糾錯(cuò)能力，特別適合在衰落信道中糾正突發(fā)碼，具有很強(qiáng)的糾錯(cuò)能力，特別適合在衰落信道中糾正突發(fā)錯(cuò)誤。在錯(cuò)誤。在(n,k)RS碼中輸入信號(hào)分成碼中輸入信號(hào)分成km

57、比特比特一組，每組包括一組，每組包括k個(gè)個(gè)符符號(hào)，號(hào)， 每個(gè)符號(hào)由每個(gè)符號(hào)由m比特比特組成。一個(gè)能糾正組成。一個(gè)能糾正t個(gè)個(gè)符號(hào)錯(cuò)誤的符號(hào)錯(cuò)誤的RS碼，其碼，其主要參數(shù)如下：主要參數(shù)如下： (1) 碼長，碼長，n=2m1符號(hào)或符號(hào)或n=m(2m1)個(gè)比特。個(gè)比特。 (2) 信息段，信息段， k個(gè)符號(hào)或個(gè)符號(hào)或mk個(gè)比特。個(gè)比特。 (3) 監(jiān)督段，監(jiān)督段，r=nk=2t個(gè)符號(hào)或個(gè)符號(hào)或m2t個(gè)比特。個(gè)比特。 (4) 最小碼距，最小碼距，d0=2t+1個(gè)符號(hào)或個(gè)符號(hào)或m(2t+1)個(gè)比特。個(gè)比特。 對(duì)于一個(gè)長度為對(duì)于一個(gè)長度為n=2m1符號(hào)的符號(hào)的RS碼，每個(gè)符號(hào)都可以看成是碼，每個(gè)符號(hào)都可以看成

58、是有限域有限域GF(2m)中的一個(gè)元素。對(duì)于最小碼距為中的一個(gè)元素。對(duì)于最小碼距為d0符號(hào)符號(hào)的的RS碼，其碼，其生成多項(xiàng)式為生成多項(xiàng)式為 第第6 6章章 信道編碼信道編碼 2022-7-365)()()(120dxxxxg其中，其中，i是是GF(2m)域元素，域元素，i=1, 2, ，d01。 例如，構(gòu)造一個(gè)能糾正三個(gè)錯(cuò)誤符號(hào)，碼長為例如，構(gòu)造一個(gè)能糾正三個(gè)錯(cuò)誤符號(hào)，碼長為15，m=4的的RS碼，最小碼距為碼，最小碼距為d0=2t+1=23+1=7個(gè)符號(hào)，監(jiān)督段有個(gè)符號(hào)，監(jiān)督段有r=2t=23=6個(gè)符號(hào)，信息段有個(gè)符號(hào)，信息段有k=nr=156=9個(gè)符號(hào)，即個(gè)符號(hào)，即(15，9)RS碼。從二

59、碼。從二進(jìn)制的角度，這是一個(gè)進(jìn)制的角度，這是一個(gè)(60， 36)碼。碼。 則知，其生成多項(xiàng)式為則知，其生成多項(xiàng)式為g(x) =(x+)(x+2)(x+3)(x+4)(x+5)(x+6)=x6+10 x5+14x4+4x3+6x2+9x+6 第第6 6章章 信道編碼信道編碼 2022-7-366RS碼的編碼過程與碼的編碼過程與BCH碼的大體一樣，同樣可以用帶反碼的大體一樣，同樣可以用帶反饋的移位寄存器來實(shí)現(xiàn)。不同之處有：饋的移位寄存器來實(shí)現(xiàn)。不同之處有： 移位寄存器為移位寄存器為m級(jí)并聯(lián)工作；級(jí)并聯(lián)工作； 每個(gè)反饋連接必須乘以生成多項(xiàng)式每個(gè)反饋連接必須乘以生成多項(xiàng)式g(x)中相應(yīng)的系數(shù)。中相應(yīng)的

60、系數(shù)。 RS的譯碼過程也與的譯碼過程也與BCH碼的大體相同。不同的是：需要碼的大體相同。不同的是：需要在找到錯(cuò)誤位置后，求出錯(cuò)誤值，這是因?yàn)樵谡业藉e(cuò)誤位置后，求出錯(cuò)誤值，這是因?yàn)镽S譯碼有譯碼有2m1種種可能的取值?？赡艿娜≈怠?第第6 6章章 信道編碼信道編碼 2022-7-3676.3.7 擴(kuò)展碼擴(kuò)展碼 如果給每個(gè)碼字添加一位奇偶校驗(yàn)位如果給每個(gè)碼字添加一位奇偶校驗(yàn)位c校校，構(gòu)成（，構(gòu)成（n1，k）線性碼，稱為）線性碼，稱為擴(kuò)展碼擴(kuò)展碼。 cn-1, c1, c0 cn-1, c1, c0 , c校校 c n1 c1 c0 c 校校0 在二進(jìn)制在二進(jìn)制偶校驗(yàn)偶校驗(yàn)時(shí)：時(shí)： 原來碼字中原來碼