第9章差錯(cuò)控制編碼

1、第第9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼9.1引 言9.2 糾錯(cuò)編碼的基本原理9.3 常用的簡(jiǎn)單編碼9.4 線性分組碼9.5循環(huán)碼9.6卷積碼9.7網(wǎng)格編碼調(diào)制返回主目錄 9.1 引言設(shè)計(jì)數(shù)字通信系統(tǒng)時(shí)，應(yīng)首先合理選擇調(diào)制、解調(diào)方法及發(fā)送功率。若不滿足要求，則考慮差錯(cuò)控制。 從差錯(cuò)控制角度看，信道可以分為三類：即隨機(jī)信道、突發(fā)信道和混合信道。隨機(jī)信道在隨機(jī)信道中、錯(cuò)碼的出現(xiàn)是隨機(jī)的，且錯(cuò)碼之間是統(tǒng)計(jì)獨(dú)立的。突發(fā)信道錯(cuò)碼是成串集中出現(xiàn)的?；旌闲诺来嬖陔S機(jī)和突發(fā)兩種錯(cuò)碼。常用的差錯(cuò)控制方法有以下幾種： 檢錯(cuò)重發(fā)法接收端在收到的信碼中檢測(cè)出(發(fā)現(xiàn))錯(cuò)碼時(shí)，即設(shè)法通知發(fā)送端重發(fā)，直到正確收到為止。前向糾錯(cuò)

2、法接收端不僅能發(fā)現(xiàn)錯(cuò)碼，還能夠確定錯(cuò)碼的位置，能夠糾正它。反饋校驗(yàn)法接收端將收到的信碼原封不動(dòng)地轉(zhuǎn)發(fā)回發(fā)送端與原信碼比較。若發(fā)現(xiàn)錯(cuò)誤則發(fā)端重發(fā)。三種差錯(cuò)控制方法可以結(jié)合使用。接收端根據(jù)什么來識(shí)別有無錯(cuò)碼由發(fā)送端的信道編碼器在信息碼元序列中增加一些監(jiān)督碼元。這些監(jiān)督碼和信碼之間有確定的關(guān)系，使接收端可以利用這種關(guān)系由信道譯碼器來發(fā)現(xiàn)或糾正可能存在的錯(cuò)碼。 在信息碼元序列中加入監(jiān)督碼元就稱為差錯(cuò)控制編碼，有時(shí)也稱為糾錯(cuò)編碼。差錯(cuò)控制編碼原則上是以降低信息傳輸速率為代價(jià)來?yè)Q取傳輸可靠性的提高。ARQ系統(tǒng)組成信源編碼器和緩沖存儲(chǔ)重發(fā)控制雙向信道譯碼器指令產(chǎn)生緩沖存儲(chǔ)收信者ARQ優(yōu)點(diǎn)：冗余碼元少、對(duì)信道

3、有自適應(yīng)能力、成本和復(fù)雜性低；ARQ缺點(diǎn)：需要反向信道、重發(fā)控制較復(fù)雜、干擾大通信效率低、實(shí)時(shí)性差。例：3位二進(jìn)制數(shù)字構(gòu)成的碼組，共有8種不同的組合。若將其全部利用來表示天氣，則可以表示8種不同的天氣。000(晴)，001(多云)，010(陰)，011(雨)，100(雪)， 101(霜)， 110(霧)， 111(雹)。任一碼組在傳輸中若發(fā)生一個(gè)或多個(gè)措碼則將變成另一信息碼組。這時(shí)接收端將無法發(fā)現(xiàn)錯(cuò)誤。 9. 2 糾錯(cuò)編碼的基本原理若：000=晴001 =不可用010 =不可用011=云100 =不可用101=陰110=雨111 =不可用則： 雖然只能傳送4種不同的天氣但是接收消卻有可能發(fā)現(xiàn)碼

4、組中的一個(gè)錯(cuò)碼。 例如，若000(晴)中錯(cuò)了一位，則接收碼組將變成100或010或001，這三種碼組都是不準(zhǔn)許使用的，稱為禁用碼組，故接收端在收到禁用碼組時(shí)，就認(rèn)為發(fā)現(xiàn)了錯(cuò)碼。但是這種碼不能發(fā)現(xiàn)兩個(gè)措碼，因?yàn)榘l(fā)生兩個(gè)錯(cuò)碼后產(chǎn)生的是許用碼組。上述碼只能檢測(cè)錯(cuò)誤，不能糾正錯(cuò)誤。例如，當(dāng)收到的碼組為禁用碼組100時(shí)，無法判斷是哪一位碼發(fā)生了錯(cuò)誤因?yàn)榍?、陰、雨三者錯(cuò)了一位都可以變成100。要想能糾正錯(cuò)誤，還要增加多余度。例如，苦規(guī)定許用碼組只有兩個(gè)：000(晴)、111(雨)、其余都是禁用碼組。這時(shí)，接收?qǐng)瞿軝z測(cè)兩個(gè)以下錯(cuò)碼，或能糾正一個(gè)錯(cuò)碼。分組碼的一般概念。為了傳輸4種不同的信息，用兩位二進(jìn)制碼組

5、就夠了，它們是：00、01、10、11。代表所傳信息的這些兩位碼，稱為信息位。前面使用3位碼，多出的一位稱為監(jiān)督位。信息碼分組，每組信碼附加若干監(jiān)督碼的編碼集合，稱為分組碼。例如分組碼的結(jié)構(gòu)符號(hào) (n，k)表示分組碼k信息碼元數(shù)n碼組長(zhǎng)度(碼長(zhǎng))n-k監(jiān)督碼元數(shù)an-1an-2arar-1a0k位信息位r位監(jiān)督位n=k+r時(shí)間碼重、碼距與碼的糾檢錯(cuò)能力碼重“1”的數(shù)量稱為碼組的重量碼距兩個(gè)碼組對(duì)應(yīng)位上數(shù)字不同的位數(shù)稱為碼組的距離，簡(jiǎn)稱碼距。又稱漢明(Hamming)距離。最小碼距某種編碼中各個(gè)碼組間距離的最小值稱為最小碼距(d0)。若記： d0 最小碼距； e檢錯(cuò)位數(shù)； t糾錯(cuò)位數(shù)；則有：（1

6、） e +1 d0，即碼的檢錯(cuò)能力e比最小碼距d0小1位；（2）2t+1 d0，即碼的糾錯(cuò)能力t的2倍比最小碼距d0小1位；（3） e +t+1 d0 ，即若碼同時(shí)糾t個(gè)錯(cuò)并檢出e個(gè)錯(cuò)誤，則e +t比最小碼距d0小1位。以下說明：（1） e +1 d0（2） 2t +1 d0（3） t +e+1 d0差錯(cuò)控制編碼的效用 假設(shè):發(fā)送“0”的錯(cuò)誤概率和發(fā)送“1”的錯(cuò)誤概率相等，都等于P，且P1，則在碼長(zhǎng)為n的碼組中恰好發(fā)生r個(gè)錯(cuò)碼的概率為rrnrrnnprnrnpprPC)!( !)1 ()(例如，當(dāng)碼長(zhǎng)n7時(shí)，p=10-3則有P7(1) 7p= 710-3 ；P7(2) 21p2=2.110-5

7、 ；P7(3) 35p3=3.510-8。可見，采用差錯(cuò)控制編碼，即使僅能糾正(或檢測(cè))這種碼組中12個(gè)錯(cuò)誤，也可以使誤碼率下降幾個(gè)數(shù)量級(jí)。這就表明，即使是較簡(jiǎn)單的差錯(cuò)控制編碼也具有較大實(shí)際應(yīng)用價(jià)值。 9. 3 常用的簡(jiǎn)單編碼1奇偶監(jiān)督碼奇偶監(jiān)督碼包括奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼。只有一位監(jiān)督位。在偶監(jiān)督碼中，監(jiān)督位使碼組中“l(fā)”的個(gè)數(shù)為偶數(shù)，即滿足下式條件在奇監(jiān)督碼中，監(jiān)督位使碼組中“l(fā)”的個(gè)數(shù)為奇數(shù)，即滿足下式條件0021aaann1021aaann2二維奇偶監(jiān)督碼又稱方陣碼。每一行是奇偶監(jiān)督碼的一個(gè)碼組，若干碼組再按列排列成矩陣，每列增加一位監(jiān)督位。二維奇偶監(jiān)督碼特點(diǎn)：l可檢測(cè)偶數(shù)個(gè)錯(cuò)誤l適于

8、檢測(cè)突發(fā)錯(cuò)碼。l不僅可檢錯(cuò)，還可糾一些錯(cuò)。l檢錯(cuò)能力強(qiáng)。3恒比碼每個(gè)碼組均含有相同數(shù)目的“1”(和“0”)。應(yīng)用：電傳機(jī)傳輸漢字，每個(gè)漢字用4位阿拉伯?dāng)?shù)字表示。每個(gè)阿拉伯?dāng)?shù)字又用5位二進(jìn)制符號(hào)構(gòu)成的碼組表示。每個(gè)碼組的長(zhǎng)度為5位，其中恒有3個(gè)1，稱為5中取3恒比碼?？赡芫幊傻牟煌a組數(shù)等于從5中取3組合數(shù)30。30種許用碼組恰好可用來表示10個(gè)阿拉伯?dāng)?shù)字。 4正反碼一種簡(jiǎn)單的能夠糾正錯(cuò)碼的編碼。其中的監(jiān)督位數(shù)與信息位數(shù)相同，監(jiān)督碼元與信息碼元相同(是信息碼的重復(fù))或者相反(是信息碼的反碼)。 由信息碼中“1”的個(gè)數(shù)而定。解碼方法：先將接收碼組中信息位和監(jiān)督值按位模2相加，產(chǎn)生校驗(yàn)碼組。最后，觀

9、察校驗(yàn)碼組中“1”的個(gè)數(shù)，按表93進(jìn)行判決及糾正可能發(fā)現(xiàn)的錯(cuò)碼。 9. 4 線性分組碼 從上節(jié)介紹的一些簡(jiǎn)單編碼可以看出，每種編碼所依據(jù)的原理各不相同，而且是大不相同，其中奇偶監(jiān)督碼的編碼原理利用了代數(shù)關(guān)系式。我們把這類建立在代數(shù)學(xué)基礎(chǔ)上的編碼稱為代數(shù)碼。在代數(shù)碼中，常見的是線性碼。線性碼中信息位和監(jiān)督位是由一些線性代數(shù)方程聯(lián)系著的，或者說，線性碼是按一組線性方程構(gòu)成的。本節(jié)將以漢明(Hamming)碼為例引入線性分組碼的一般原理。回顧奇偶監(jiān)督碼在接收端解碼時(shí)，實(shí)際上就是在計(jì)算若S0，認(rèn)為無錯(cuò)；若S1，認(rèn)為有錯(cuò)。上式稱為監(jiān)督關(guān)系式，S稱為校正子。S只有兩種取值，只能代表有、無錯(cuò)兩種信息，不能指

10、出錯(cuò)碼位置。如果監(jiān)督位增加一位，則增加一個(gè)監(jiān)督關(guān)系式。由于兩個(gè)校正子的可能值有4種組合：00，01，10，11，故能表示4種不同狀態(tài)。0021aaann021aaaSnn若用其一種表示無錯(cuò)，則其余3種就可能用來指示一位錯(cuò)碼的3種不同位置。同理r個(gè)監(jiān)督關(guān)系式能指示一位錯(cuò)碼的(2r-1)個(gè)可能位置。 一般地，若碼長(zhǎng)為n，信息位數(shù)為k，則監(jiān)督位數(shù)r=n-k。如果希望用r個(gè)監(jiān)督位構(gòu)造出r個(gè)監(jiān)督關(guān)系式來指示一位錯(cuò)碼的n種可能位置，則要求 2r-1 n，或者 2r r+k+1舉例說明如何構(gòu)造監(jiān)督關(guān)系式：設(shè)(n，k)分組碼中r=4。為了糾正一位錯(cuò)碼，要求監(jiān)督拉數(shù)r 3。若取r=3，則n=k+r=7。校正子與

11、錯(cuò)碼位置的對(duì)應(yīng)關(guān)系如表94規(guī)定(也可以另外規(guī)定) 。S1S2S3錯(cuò)碼位置S1S2S3錯(cuò)碼位置001A0101A4010A1110A5100A2111A6011A3000無錯(cuò)由表可見，當(dāng)一錯(cuò)碼在a2,a4，a5或a6時(shí)校正子S為1；否則S為0即構(gòu)成如下關(guān)系同理24561aaaaS13562aaaaS03463aaaaS在發(fā)送端編碼時(shí)，信息位a6a5a4a3的值決定于穩(wěn)入信號(hào)，因此它們是隨機(jī)的。監(jiān)督值a2a1ao應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系來確定即監(jiān)督位應(yīng)使上三式中的值為零(表示編成的碼組中應(yīng)無錯(cuò)碼)，由此得到方程組01356aaaa00346aaaa02456aaaa由此解出3561aaaa34

12、60aaaa4562aaaa給定信息位后，可直接按上式算出監(jiān)督位，其結(jié)果如表95所列。信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111 接收端收到每個(gè)碼組后，先按監(jiān)督方程計(jì)算出S1、S2、 S3 ，再按表94判斷錯(cuò)碼情況。例，接收0000011，可得：S1S2S3=011 。由表94可知在a3位有錯(cuò)碼。 (7，4)漢明碼：l最小碼距d0=3l

13、糾一個(gè)錯(cuò)碼或檢測(cè)兩個(gè)錯(cuò)碼。l編碼效率k/n=(2r-1-r)(2r-1)=I-rn。當(dāng)n很大時(shí)，則編碼效率接近1。線性分組碼的般原理。線性分組碼是指信息位和監(jiān)督位滿足一組線性方程的編碼。改寫為01356aaaa00346aaaa02456aaaa01356aaaa000101110123456aaaaaaa001010110123456aaaaaaa010011010123456aaaaaaa0001011001110101011101000123456aaaaaaa(模2)簡(jiǎn)記為 或TTHA00TAH101100111010101110100H稱為監(jiān)督矩陣IrPH00101010010111

14、1011110H矩陣的各個(gè)行是線性無關(guān)的行數(shù)=監(jiān)督位數(shù)，列數(shù)=碼字長(zhǎng)度典型陣3561aaaa3460aaaa4562aaaa345620111aaaaa345611011aaaaa345601101aaaaa3456012101111011110aaaaaaa Qaaaaaaaaaaa34563456012011101110111轉(zhuǎn)置得 Gaaaaaaaaaaaaaaa3456345601234560111011101110001001001001000QIGknk0111011101110001001001001000稱為生成矩陣GaaaaA3456生成矩陣G的每一行都是一個(gè)碼組。例如，（參

15、照前頁(yè)矩陣G）。利用生成矩陣，碼字TTHA0再由 得，0TTTMHGMGHMG0THG譯碼,若發(fā)送碼組為接收碼組為二者之差為其中E稱為錯(cuò)誤圖樣。021,aaaAnn021,bbbBnn021,eeeABEnniiiiibabae, 1, 0表示該位接收碼元無錯(cuò)；表示該位接收碼元有錯(cuò)。 接收端譯碼時(shí)計(jì)算當(dāng)接收碼組無錯(cuò)時(shí)S等于零有錯(cuò)但不超過檢錯(cuò)能力時(shí)， S不等于零。在錯(cuò)碼超過檢錯(cuò)能力時(shí)，B變?yōu)榱硪辉S用碼組，仍能成立S等于零。這樣的錯(cuò)碼是不可檢測(cè)的。S稱為校正子(伴隨式) 。S只與E有關(guān)，而與A無關(guān)，意味著S與E有的線性變換關(guān)系，能與E一一對(duì)應(yīng)，可指示錯(cuò)碼位置。SEHEHAHHEABHTTTTT)(

16、 線性碼重要性質(zhì)之一，是它具有封閉性。 若：A1和A2是線性碼中的兩個(gè)許用碼組，則：(A1+A2)仍為其中的一個(gè)碼組。由封閉性，兩個(gè)碼組之間的距離必是另一碼組的重量。故碼的最小距離即是碼的最小重量(除全“0”碼組外)。 線性碼又稱群碼，這是由于線性碼的各許用碼組構(gòu)成代數(shù)學(xué)中的群。 9. 5 循環(huán)碼9. 5 . 1 循環(huán)碼原理： 在線性分組碼中，有一種重要的碼稱為循環(huán)碼。循環(huán)碼除了具有線性碼的一般性質(zhì)外還具有循環(huán)性，即任一碼組循環(huán)一位(將最右端的碼元移至左端，或反之)以后，仍為該碼中的一個(gè)碼組。即若 是許用碼組，則 也是許用碼組。021,aaaAnn102,nnaaaA循環(huán)碼舉例(7,3)循環(huán)碼

17、碼組信息位監(jiān)督位碼組 信息位監(jiān)督位編號(hào)a6a5a4a3a2a1a0編號(hào)a6a5a4a3a2a1a00000000041001011100101115101110020101000611001013011100171110010碼組的多項(xiàng)式表示碼多項(xiàng)式。例如 A=1100101 A(x)=1x6+1x5+0 x4+0 x3+1x2+0 x1+1x0 =x6+x5+x2+1碼多項(xiàng)式表示具有線性的性質(zhì)021,aaaAnn0112211)(axaxaxaxAnnnn碼多項(xiàng)式的按模運(yùn)算循環(huán)移位對(duì)應(yīng)的碼多項(xiàng)式如果規(guī)定xn=x0，即規(guī)定xn+1=0，則有021,aaaAnn102,nnaaaA1102312

18、)( nnnnnaxaxaxaxA)()( xAxxA這種xn+1=0的規(guī)定，實(shí)質(zhì)上是一xn+1為模的運(yùn)算。對(duì)于整數(shù)m,若可以表示為則稱m=p(模n) ，或稱m與p是同余的。碼多項(xiàng)式也有類似的運(yùn)算。多項(xiàng)式F(x)被n次多項(xiàng)式N(x)除，得到商式q(x)和一個(gè)次數(shù)小于n的余式R(x)，即 F(x)q(x)N(x)+R(x)則寫為F(x)R(x) ( 模N(x) )npQnm碼多項(xiàng)式系數(shù)仍按模2運(yùn)算，即只取值0和1。例如于是，可以有由此可見為了使xn=1，只需做模xn+1的運(yùn)算即可。例如：x4+x2+1=x2+x+1 模x3+1111111133333xxxxx) 1(mod133xx由前面的分析

19、可知，若T(x)是碼多項(xiàng)式，則在模xn+1的運(yùn)算條件下， xiT(x)仍然是碼多項(xiàng)式。 2循環(huán)碼的生成矩陣G 若能找到k個(gè)線性無關(guān)的碼組,就能構(gòu)成矩陣G。在循環(huán)碼中，一個(gè)(n，k)碼有2k個(gè)不同碼組，若用g(x)表示其中前(k-1)位皆為0的碼組，即 g(x)=0 1x x k位 n-k位則g(x) 、xg(x)，x2g(x) ，xk-1g(x)都是碼組，而且這k個(gè)碼組是線性無關(guān)的。因此可以用來構(gòu)成循環(huán)碼的生成矩陣G。 例 表96的循環(huán)碼, 唯一的一個(gè)(n-k)次碼多項(xiàng)式代表的碼組是0010111，相對(duì)應(yīng)的碼多項(xiàng)式為)()()()(21xgxxgxgxxgxGkk一旦確定了g(x)，則整個(gè)(n

20、k)循環(huán)碼就被確定了。因此,循環(huán)碼的生成矩陣G可以寫成這個(gè)生成矩陣不是系統(tǒng)碼的生成矩陣，可以通過行變換，變換成系統(tǒng)碼的生成矩陣。001011101011101011100)()()(2xgxxgxgxG g(x)x4+x2+x+1將此g(x)代入上式，得到g(x)的性質(zhì)：lg(x)必須是一個(gè)常數(shù)項(xiàng)a0=1；l次數(shù)為(n-k)次；l唯一的(n-k)次多項(xiàng)式；l我們稱這唯一的g(x)為碼的生成多項(xiàng)式。lg(x)是xn+1的因式（見后面分析）。說明g(x)是xn+1的因式。因?yàn)槿未a多項(xiàng)式T(x)都是g(x)的倍式，所以有 T(x)=h(x)g(x)g(x)本身也是一個(gè)碼組，其次數(shù)為n-k次。把它循環(huán)

21、移位k次仍為一個(gè)碼組。所以xkg(x)是n次多項(xiàng)式，在模xn+1 運(yùn)算下，所以即) 1(mod),()(nkxxTxgx1)()(1)(nnkxxTxQxxgx因?yàn)閤kg(x)是n次的，所以Q(x)=1 。所以所以即 g(x)是xn+1的因式。 這樣就可以通過對(duì)xn+1的因式分解得到g(x).1)()(11)(11)(nnnkxxgxhxxTxxgx1)()(nkxxgxhx因?yàn)樗写a多項(xiàng)式T(x)都可被g(x)整除。所以非系統(tǒng)碼編碼：T(x)=m(x)g(x)系統(tǒng)碼編碼：l用xn-k乘m(x)，即把m(x)左移n-k位；l用xn-k除以g(x)，得余式r(x)；lT(x) =xn-km(x)

22、+ r(x)9.5.2 循環(huán)碼的編、解碼方法例：信息碼110，信息碼多項(xiàng)式m(x)=x2+x生成多項(xiàng)式g(x)=x4+x2+x+1即于是，編出碼字1100000+101=1100101硬件實(shí)現(xiàn)固定除式的多項(xiàng)式除法abcd信息碼元輸入移存器反饋輸出mabcddf0000001111011110011101010100010100000101100001000000011校驗(yàn)碼元2循環(huán)碼的解碼方法檢錯(cuò)解碼的要求有兩個(gè)：檢錯(cuò)和糾錯(cuò)。碼多項(xiàng)式T(x)應(yīng)能被生成多項(xiàng)式g(x)整除。若接收碼組與發(fā)送碼組相同，即R(x)=T(x)，則接收碼組R(x)必定能被g(x)整除；若碼組在傳輸中發(fā)生錯(cuò)誤，則R(x)除

23、以g(x) 時(shí)可能有余項(xiàng)，即有 R(x)/g(x)=Q(x)+r(x)/g(x)檢錯(cuò)電路見圖9-7(a)接收碼組緩沖移位寄存器除法電路反相與門重發(fā)指令輸出信息碼余式等于1 時(shí)輸出1余式等于0 時(shí)輸出02循環(huán)碼的解碼方法糾錯(cuò)前提：每個(gè)可糾正的錯(cuò)誤圖樣必須與伴隨式一一對(duì)應(yīng)。步驟：由接收多項(xiàng)式除以生成多項(xiàng)式得到余式r(x)；通過余式r(x)與錯(cuò)誤圖樣的關(guān)系得到錯(cuò)誤圖樣e(x)；從接收多項(xiàng)式中減去錯(cuò)誤圖樣村e(cuò)(x)。電路如下：圖9-7(b)假定接收碼組為10*O0101，其中右上角打*號(hào)者為錯(cuò)碼。此碼組進(jìn)入除法電路后，移位寄存器各級(jí)的狀態(tài)變化過程列于表97(b)。(見演示)輸入移存器 輸出fabcde

24、0000001111000*011100110100100001101000010101001000000110000009.5.3 縮短循環(huán)碼通過縮短循環(huán)碼，可以滿足系統(tǒng)設(shè)計(jì)中，碼長(zhǎng)、信息位和糾錯(cuò)能力的不同要求。對(duì)于(n,k)循環(huán)碼，使前i(0ik)個(gè)信息位為零可得到有2k-i個(gè)碼組的集合，然后從這些碼組中刪去這i個(gè)零信息位，得到一種新的(r-i，k-i)的線性碼，稱為縮短循環(huán)碼?？s短循環(huán)碼與產(chǎn)生該碼的原循環(huán)碼至少具有相同的糾錯(cuò)能力?？s短循環(huán)碼的編碼和譯碼可用原循環(huán)碼使用的電路完成。例：若要求構(gòu)造一個(gè)能夠糾正一位錯(cuò)誤的(13，9)碼，則可以由(15，11)漢明碼選出前面兩個(gè)信息位均為零的碼組

25、。然后在發(fā)送時(shí)，這兩個(gè)零信息不發(fā)送，即發(fā)送的是(13，9)縮短循環(huán)碼。因校驗(yàn)位數(shù)相同，(13，9)碼與(15，11)循環(huán)碼具有相同的糾錯(cuò)能力。9.5.4 BCH碼BCH碼是一類糾正多個(gè)隨機(jī)錯(cuò)誤的特殊的循環(huán)碼。特點(diǎn)是可以根據(jù)給定的糾錯(cuò)能力，找出生成多項(xiàng)式。 BCH碼分兩類：本原BCH碼和非本原BCH碼。本原BCH碼的碼長(zhǎng)為n=2m-1(M 3)，生成多項(xiàng)式g(x)中含有最高次數(shù)為m次的本原多項(xiàng)式；非本原BCH碼的碼長(zhǎng)n是2m-1的一個(gè)因子，它的生成多項(xiàng)式中不含有最高次數(shù)為m的本原多項(xiàng)式。對(duì)于正整數(shù)m(M3)和t(t 2)必存在有下列參數(shù)的二進(jìn)制BCH碼：碼長(zhǎng)n=2m-1，監(jiān)督位數(shù)rmt，能糾正所

26、有的小于或等于t個(gè)隨機(jī)錯(cuò)誤的BCH碼。BCH碼生成多項(xiàng)式 g(x)=LCMm1(x)，m2(x)， m2t-1(x)式中t可糾正的錯(cuò)誤個(gè)數(shù)；mi(x)最小多項(xiàng)式;LCM( )指取括號(hào)內(nèi)所有多項(xiàng)式的最小公倍式.查表法得到生成多項(xiàng)式，用八進(jìn)制數(shù)表示。例如當(dāng)n=7,k=4,t=1 g=(13)8意指 g=(001011)2 g(x)=x3+x+1 n=3 kt g(x)117 n=7kt g(x)41131377表98（部分）R-S碼是一類具有很強(qiáng)糾措能力的多進(jìn)制BCH碼。伽羅華域(即有限域) ：對(duì)于有限個(gè)符號(hào)，若符號(hào)的數(shù)目是一素?cái)?shù)的冪，可以定義有加法和乘法，則構(gòu)成符號(hào)域?yàn)橛邢抻?；若它?m個(gè)符號(hào)的

27、域則稱之為伽羅華域GF(2m) .例如，兩個(gè)符號(hào)0、1，定義有模2加法和模2乘法，即 0+0=0，0+1=1，1+1=0； 00=0，01=1，111，則稱之為二元域，也是伽羅華域。9.5.5 里德-索羅門碼（R-S碼）從兩個(gè)符號(hào)0和1及一個(gè)m次多項(xiàng)式p(x)開始，并引入一個(gè)新符號(hào) ，設(shè)p()=0。若適當(dāng)?shù)剡x擇p(x)就可得到的各次冪，一直到2m-2次冪，都不相同，并且m-1 =1。這樣一來， 構(gòu)成GF(2m)的所有元素。域中每個(gè)非零元素還可以用上面元素的和來表示。例如，m=4和p(x)=x4+x+1，則2242, 1 , 0m得到GF(24)的所有元素，詳見表9-10。01 2 3 4= +

28、1 5= (+1)=2+ 6=(2+)= 3+2 7=(3+ 2)= 3+2 = 3+1 8=(3+1)= 4+2 +1=2 +1 9=(2 +1)= 3+ 10=(3+)= 2 +1 11=(2 +1)= 3+ 2 + 12= (3+ 2 +)= 3+ 2 +1 13= (3+ 2 +1)= 3+ 2+1 14=(3+ 2+1)= 3 +1R-S碼是q進(jìn)制BCH碼的子類。具有如下的參數(shù)：碼長(zhǎng)：n=q-1符號(hào)監(jiān)督位數(shù)： r=2t符號(hào)糾錯(cuò)位數(shù)： t 符號(hào)生成多項(xiàng)式：每個(gè)碼元都是q進(jìn)制的，通常令q=2m，則每個(gè)q進(jìn)制碼元都可以表示為m位二進(jìn)制碼元，于是碼長(zhǎng)mn位，監(jiān)督位數(shù)mr位，信息位數(shù)： mn-

29、 mr位。)()()(22txxxxgR-S碼應(yīng)用：由于采用多進(jìn)制，所以對(duì)于多進(jìn)制調(diào)制是自然和方便的編碼手段;因?yàn)镽S碼能夠糾正t個(gè)q位二進(jìn)制碼，即對(duì)以糾t個(gè)連續(xù)的突發(fā)性二進(jìn)制錯(cuò)誤,所以適合衰落信道應(yīng)用;RS碼可應(yīng)用在計(jì)算機(jī)存儲(chǔ)系統(tǒng)中以克服系統(tǒng)的差錯(cuò)。卷積編碼則把k比特信息段編成n比特的碼組，但所編的n長(zhǎng)碼組不僅同當(dāng)前的k比特信息段有關(guān)聯(lián)，而且還同前面的(N-1)個(gè)信息段有關(guān)聯(lián)，人們常稱這N為該卷積碼的約束長(zhǎng)度。一般來說，對(duì)于卷積碼，k和n是較小的整數(shù), 常把卷積碼記作(n,k,N)卷積碼，它的編碼效率為R=k/n。 9. 6 卷積碼961 卷積碼的圖形描述(3,1,3)卷積碼編碼器編碼器的輸

30、入和輸出樹狀圖狀態(tài)圖狀態(tài)圖網(wǎng)格圖網(wǎng)格圖特點(diǎn)： 有2N-1種狀態(tài)；對(duì)于k個(gè)輸入信息比特，相應(yīng)出現(xiàn)有2k條支路；碼樹中的上支路用實(shí)線表示，下支路用虛線表示：支路上標(biāo)注的碼元為輸出比特；從第N個(gè)節(jié)點(diǎn)開始，圖形開始重復(fù)，且完全相同。 例9-1 (3,1,3)編碼器，起始狀態(tài)為a，輸入序列為1101011，求輸出序列和相應(yīng)狀態(tài)變化路徑。解：由卷積碼的網(wǎng)格圖，可找出編碼時(shí)網(wǎng)格圖中的編碼路徑如圖913所示，由此即可得到輸出序列。為9.6.2 卷積碼的解析描述1生成矩陣卷積碼是一種線性碼。一個(gè)線性碼完全由一個(gè)監(jiān)督矩陣H或生成矩陣G所確定。生成矩陣G 輸入第一個(gè)信息比特m1時(shí)，y1,1=m1； y21=m1 ；

31、y31=m1。 輸入第二個(gè)信息比特m2時(shí)，y1,2=m2； y22=m2 ；y32= m1 + m2。輸入第j個(gè)信息比特mj時(shí)， y1j=mj； y2j=mj +mj-2 ； y3j= mj +mj-1+mj-2上式可寫成矩陣形式 mj +mj-1+mj-2 A = y1j y2j y3j其中生成矩陣為在過渡時(shí)刻 m1 0 0 T1 = y11 y21 y31 m1 m2 0 T2 = y12 y22 y32其中111100110A0000001111T輸出矩陣與輸入矩陣的關(guān)系有 Y=MG0001111002TAAAATTG00000021 1 1 1 0 0 1 0 1 1 1 1 1 0

32、0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 上面矩陣空白處均為0元素。該生成矩陣是半無限矩陣。2 . 多項(xiàng)式描述例如：輸入序列1101110 可表示為 m(x)=1+x+x3+x4+x5+連接關(guān)系表示為 g1(x)=1 g2(x)= 1+x2 g3(x)= 1+x+x2編碼輸出為 y1(x)=m(x)g1(x)= 1+x+x3+x4+x5+ y2(x)=m(x)g2(x)=(1+x+x3+x4+x5+)(1+x2)=1+x+x3+x4+x5+ +x2+x3+x5+x7+ = 1+x +x

33、2 +x4 +x7 y3(x)= (1+x+x3+x4+x5+)(1+x+x2)= 1+x+x3+x4+x5+ x+x2+x4+x5+x6+ x2+x3+x5+x6+ x7+ =1+ x5 + x7+ 對(duì)應(yīng)的序列為 y1=1 1 0 1 1 1 0 0； y2=1 1 1 0 1 0 0 1 y3=1 0 0 0 0 1 0 1 總的輸出序列為 Y=y11,y21,y31,y12,y22,y32, = 1 1 1, 1 1 0, 0 1 0, 1 0 0, 1 1 0, 1 0 1, 0 0 0, 0 1 1, 結(jié)果與網(wǎng)格圖是一樣的。 卷積碼編碼器的一般結(jié)構(gòu)9.6.3 卷積碼譯碼卷積碼的譯碼方

34、法有兩類：一類是大數(shù)邏輯譯碼，又稱門限譯碼：另一類是概率譯碼。概率譯碼又分為維特比譯碼和序列譯碼兩種。門限譯碼方法是以分組碼理論為基礎(chǔ)的其譯碼設(shè)備簡(jiǎn)單，速度快，但其誤碼性能要比概率譯碼法差。下面只介紹維特比譯碼。9.6.3維特比譯碼維特比譯碼算法，簡(jiǎn)稱VB算法。維特比(viterbi)譯碼和序列譯碼都屬于概率譯碼。當(dāng)卷積碼的約束長(zhǎng)度不太大時(shí)，與序列譯碼相比，維持比譯碼器比較簡(jiǎn)單，計(jì)算速度更快。VB算法在前向糾錯(cuò)系統(tǒng)中用得較多，在衛(wèi)星通信中已被采用作為標(biāo)準(zhǔn)技術(shù)。概率譯碼的基本想法是：把已接收序列與所有可能的發(fā)送序列做比較，選擇其中碼距最小的一個(gè)序列作為發(fā)送序列。如果發(fā)送L組信息比特，對(duì)于(n,k

35、)卷積碼來說，可能發(fā)送的序列有2kL個(gè)，計(jì)算機(jī)或譯碼器需存儲(chǔ)這些序列并進(jìn)行比較，以找到碼距最小的那個(gè)序列。當(dāng)傳信率和信息組數(shù)人較大時(shí)，使得澤碼器難以實(shí)現(xiàn)。VB算法則對(duì)上述概率譯碼(又稱最大似然譯碼)做了簡(jiǎn)化，使其成為一種實(shí)用的譯碼算法。它并不是在網(wǎng)格圖上一次比較所有可能的2kL條路徑(序列)，而是接收一段，計(jì)算和比較一段，選擇一段有最大似然可能的碼段。從而達(dá)到整個(gè)碼序列是一個(gè)有最大似然值的序列。以下以（2,1,3)卷積碼為例說明：設(shè)輸入信息數(shù)目L=5，所以畫有L+N=8個(gè)時(shí)間單位。編碼器從a狀態(tài)開始工作。該網(wǎng)格圖的每一條路徑都對(duì)應(yīng)著不同的輸入信息序列。由于所有的可能輸入信息序列共有2kL=32

36、個(gè).設(shè)輸入編碼器的信息序列為(11011000)，則由編碼器輸出的序列 y(1101000010,11100)，編碼器的狀態(tài)轉(zhuǎn)移路線為abdcbdca。若收到的序列為R=0101011001011100，對(duì)照網(wǎng)格圖來說明維特比譯碼的方法。前3步輸入R=010101；根據(jù)不同輸入信息，編碼器的輸出序列以及它們與接收序列的距離見下表R=010101信息編碼路徑距離000000000 aaaa3001000011 aaab3010001110 aabc4011001101 aabd2100111011 abca4101111000 abcb4110110101 abdc1111110110 abdd

37、3前3步對(duì)應(yīng)網(wǎng)格圖幸存路徑，如下頁(yè)對(duì)應(yīng)4條幸存路徑的序列分別為： a-a-a-a000000 a-a-a-b000011 a-b-d-c110101 a-a-b-d001101.到第5步的幸存路徑和對(duì)應(yīng)的序列分別為： a-a-b-d-d-c001101 1001. a-b-d-c-a-a110101 1100 a-b-d-c-a-b110101 1111 a-b-d-c-b-d110101 1101到第8步的幸存路徑和對(duì)應(yīng)的序列分別為： a-b-d-c-b-d-c-a-a 11 01 01, 00 01 01 11 00對(duì)應(yīng)信息1 1 0 1 1 0 0 0與發(fā)送信息相同。對(duì)比接收0*1 01

38、 01 1*0 01 01 11 00糾正了兩個(gè)錯(cuò)誤?？偨Y(jié)與復(fù)習(xí)第一章第一章 緒論緒論通信系統(tǒng)的基本組成模型；模擬與數(shù)字通信系統(tǒng)組成；通信系統(tǒng)分類；數(shù)字通信系統(tǒng)優(yōu)點(diǎn)；模擬與數(shù)字通信系統(tǒng)的性能指標(biāo)；離散消息的信息量和平均信息量 ；例題：例1.4.1，習(xí)題2、4、6、7 第二章第二章 隨機(jī)信號(hào)分析隨機(jī)信號(hào)分析平穩(wěn)隨機(jī)過程的定義、性質(zhì)；什么是廣義平穩(wěn)隨機(jī)過程？平穩(wěn)隨機(jī)過程的自相關(guān)函數(shù)與功率譜密度如何定義，有何性質(zhì)？平穩(wěn)隨機(jī)過程通過線性系統(tǒng)后，均值、自相關(guān)與方差、功率譜密度有何關(guān)系？什么是高斯噪聲？什么是高斯白噪聲？什么是窄帶高斯噪聲？窄帶高斯噪聲的幅度和相位服從什么分布？窄帶高斯噪聲的同相分量和正交分量服從什么分布？習(xí)題1、2、3、7、8、12第三章第三章 信道信道信道分類：廣義信道與狹義信道、調(diào)制信道與編碼信道、恒參信道與變參信道；什么是幅頻畸變、什