現(xiàn)代通信原理11第十一章差錯(cuò)控制編碼和線性分組碼

1、1現(xiàn)代通信原理第十一章 差錯(cuò)控制編碼和線性分組碼2單元概述單元概述 實(shí)際信道傳輸數(shù)字信號(hào)時(shí)，不可避免地會(huì)產(chǎn)生誤碼。差錯(cuò)控制編碼的目的是用信道編碼的方法檢測(cè)和糾正誤碼，降低誤比特率。在檢錯(cuò)重發(fā)控制編碼方式中，信道編碼只是為了檢測(cè)誤碼，而在前向糾錯(cuò)方式中，信道編碼用于糾正誤碼。 檢錯(cuò)和糾錯(cuò)能力是用信息冗余度即由附加附加在信息中的監(jiān)督碼元來實(shí)現(xiàn)的。信息碼元與監(jiān)督碼元之間建立某種檢驗(yàn)關(guān)系，根據(jù)建立檢驗(yàn)關(guān)系的方法不同，可以分為分組碼和卷積碼。線性分組碼中信息碼元和監(jiān)督碼元是用現(xiàn)行方程聯(lián)系起來的，卷積碼中它們是以卷積的方式聯(lián)系起來。碼距是確定糾錯(cuò)檢錯(cuò)能力的重要度量。3單元學(xué)習(xí)提綱單元學(xué)習(xí)提綱 （1）前向糾

2、錯(cuò)、檢錯(cuò)重發(fā)差錯(cuò)控制方法； （2）檢錯(cuò)和糾錯(cuò)的基本原理； （3）分組碼、卷積碼、線性碼、系統(tǒng)碼的定義； （4）碼距的定義，它與檢錯(cuò)、糾錯(cuò)能力的關(guān)系； （5）線性分組碼中監(jiān)督方程、監(jiān)督矩陣、生成方程、生成矩陣的含義；4（6）漢明碼的特點(diǎn)及構(gòu)造；（7）循環(huán)碼的特點(diǎn)及編碼方法；（8）糾正一位誤碼的循環(huán)碼的一種譯碼方法；（9）交織碼糾正突發(fā)錯(cuò)誤的原理；（10） 卷積碼的編碼方法，生成多項(xiàng)式與編碼器的構(gòu)造； 5 （11）卷積碼的樹狀圖、網(wǎng)格圖的表示；（12）卷積碼維持比譯碼的基本原理和譯碼過程；（13）糾錯(cuò)編碼誤比特率性能，編碼增益的含義；（14）糾錯(cuò)編碼在衛(wèi)星信道、移動(dòng)通信等實(shí)際通信系統(tǒng)中的應(yīng)用。6第

3、十一章 差錯(cuò)控制編碼和線性分組碼 1、概述： 數(shù)字通信系統(tǒng)是以電子方式傳輸信息的，接收方收到的數(shù)據(jù)應(yīng)當(dāng)就是發(fā)送方發(fā)送的數(shù)據(jù)，但這些電子信息都易受到干擾，太陽黑子活動(dòng)、電源抖動(dòng)或施工者用鋤頭對(duì)電纜的碰撞都會(huì)對(duì)傳輸產(chǎn)生不可預(yù)料的影響。 為保證傳輸數(shù)據(jù)的完整性，通常采用一定的措施，如利用均衡器糾正信道參數(shù)，加大發(fā)送功率、擴(kuò)展信道頻帶寬度等辦法來減少加性干擾。 采用上述方法仍難以滿足要求時(shí)，必須采用差錯(cuò)控制措施，即用來和。7 對(duì)于數(shù)據(jù)傳輸，人們主要關(guān)心的是信息碼元的差錯(cuò)概率，即誤碼率Pe，在中等傳輸速率（1200/2400波特）下，采用一般的調(diào)制方法，對(duì)于干線有線載波信道， Pe約為10-410-6的

4、數(shù)量級(jí)，對(duì)于無線短波通信， Pe只有10-210-3的數(shù)量級(jí)，對(duì)于傳輸速率更高的系統(tǒng)，誤碼性能還要差。 在數(shù)據(jù)通信中，如計(jì)算機(jī)與計(jì)算機(jī)之間的數(shù)據(jù)傳送，Pe要求低于10-9，這就需要加入糾錯(cuò)編碼。8從差錯(cuò)控制角度看，信道可以分為三類 1、。誤碼的出現(xiàn)是隨機(jī)的，誤碼之間是統(tǒng)計(jì)獨(dú)立的。如由正態(tài)分布白噪聲引起的誤碼（稱為）就具有這種性質(zhì)。 2、。誤碼是成串集中出現(xiàn)的，即在短促的時(shí)間區(qū)間存在大量誤碼，在較長(zhǎng)的時(shí)間區(qū)間無誤碼出現(xiàn)。產(chǎn)生的主要原因是脈沖干擾，信道中的衰落現(xiàn)象也是產(chǎn)生的主要原因。 3、。既存在又存在的信道稱為混合信道。911.1 差錯(cuò)控制編碼的基本概念 1、檢錯(cuò)重發(fā)方式（ARQ）。 2、前向糾

5、錯(cuò)方式（FEC）。 3、混合糾錯(cuò)檢錯(cuò)方式（HEC）。 4、反饋校驗(yàn)方式（IRQ）。 11.1.1 差錯(cuò)控制方式1011。 采用檢錯(cuò)重發(fā)方式，發(fā)端經(jīng)編碼后發(fā)出能夠發(fā)現(xiàn)錯(cuò)誤的碼，接收端收到后經(jīng)檢驗(yàn)如果發(fā)現(xiàn)傳輸中有錯(cuò)誤，則通過反向信道把這一判斷結(jié)果反饋給發(fā)送端。然后，發(fā)送端把信息重發(fā)一次，直到接收端確認(rèn)為止。采用這種差錯(cuò)控制方法，一般在計(jì)算機(jī)數(shù)據(jù)通信中應(yīng)用。檢錯(cuò)重發(fā)方式分為，如圖所示。圖中ACK是確認(rèn)信號(hào)，NAK是否認(rèn)信號(hào)。12 ，發(fā)對(duì)或發(fā)錯(cuò)，發(fā)送端均要等待接收端的回應(yīng)。特點(diǎn)是系統(tǒng)簡(jiǎn)單，時(shí)延長(zhǎng)。 ，無ACK信號(hào)，當(dāng)發(fā)送端收到NAK信號(hào)后，重發(fā)錯(cuò)誤碼組以后的所有碼組，特點(diǎn)是系統(tǒng)較為復(fù)雜，時(shí)延減小。 。

6、無ACK信號(hào)，當(dāng)發(fā)送端收到NAK信號(hào)后，重發(fā)錯(cuò)誤碼組，特點(diǎn)是系統(tǒng)復(fù)雜，時(shí)延最小。1314。 發(fā)送端經(jīng)編碼發(fā)出能糾正錯(cuò)誤的碼，接收端收到這些碼組后，通過譯碼能發(fā)現(xiàn)并糾正誤碼。前向糾錯(cuò)方式不需要反饋通道，特別適合只能提供單向信道的場(chǎng)合，特點(diǎn)是時(shí)延小，實(shí)時(shí)性好，但系統(tǒng)復(fù)雜。但隨著編碼理論和微電子技術(shù)的發(fā)展，編譯碼設(shè)備成本下降，加之有單向通信和控制電路簡(jiǎn)單的優(yōu)點(diǎn)，在實(shí)際應(yīng)用中日益增多。15。 混合糾錯(cuò)檢錯(cuò)方式是前向糾錯(cuò)方式和檢錯(cuò)重發(fā)方式的結(jié)合，發(fā)送端發(fā)出的碼不但有一定的糾錯(cuò)能力，對(duì)于超出糾錯(cuò)能力的錯(cuò)誤要具有檢錯(cuò)能力。這種方式在實(shí)時(shí)性和復(fù)雜性方面是前向糾錯(cuò)和檢錯(cuò)重發(fā)方式的折衷，因而在近年來，在數(shù)據(jù)通信系

7、統(tǒng)中采用較多。16 反饋校驗(yàn)方式（IRQ）又稱回程校驗(yàn)。收端把收到的數(shù)據(jù)序列全部由反向信道送回發(fā)送端，發(fā)送端比較發(fā)送數(shù)據(jù)與回送數(shù)據(jù)，從而發(fā)現(xiàn)是否有錯(cuò)誤，并把認(rèn)為錯(cuò)誤的數(shù)據(jù)重新發(fā)送，直到發(fā)送端沒有發(fā)現(xiàn)錯(cuò)誤為止。不需要糾錯(cuò)、檢錯(cuò)的編譯器，設(shè)備簡(jiǎn)單。需要反向信道；實(shí)時(shí)性差；發(fā)送端需要一定容量的存儲(chǔ)器。IRQ方式僅適用于傳輸速率較低、數(shù)據(jù)差錯(cuò)率較低的控制簡(jiǎn)單的系統(tǒng)中。1711.1.2 差錯(cuò)控制編碼的分類 1、按照差錯(cuò)控制編碼的不同功能，可以分為（僅能檢測(cè)誤碼）、糾錯(cuò)碼（僅可以糾正誤碼）和（兼有糾錯(cuò)和檢錯(cuò)功能）。 2、按照和附加的之間的檢驗(yàn)關(guān)系可以分為（信息碼元和監(jiān)督碼元滿足一組線性方程式）和18 3、

8、按照和之間的約束關(guān)系可以分為和。分組碼中，碼元序列每n位分成一組，其中k個(gè)是信息碼元，r=n-k個(gè)是監(jiān)督碼元，監(jiān)督碼元僅與本組的信息碼元有關(guān)。卷積碼中，編碼后序列也編為分組，但監(jiān)督碼元不僅與本組信息碼元有關(guān)，還與前面碼組的信息碼元有關(guān)。 4、按照糾正錯(cuò)誤的類型不同，可以分為和。19 5、按照構(gòu)成差錯(cuò)控制編碼的數(shù)學(xué)方法來分類，可以分為、和。其中代數(shù)碼建立在近代數(shù)學(xué)基礎(chǔ)上，是目前發(fā)展最為完善的編碼，其中線性碼是是代數(shù)碼的一個(gè)最重要的分支。 6、按照每個(gè)碼元的取值不同，可以分為和2011.1.4 檢錯(cuò)和糾錯(cuò)的基本原理 香農(nóng)著名的信道編碼定理指出：對(duì)于一個(gè)給定的有擾信道，若信道容量為C，只要發(fā)送端以低

9、于C的速率R發(fā)送信息，則一定存在一種編碼方法，使編碼錯(cuò)誤概率P隨著碼長(zhǎng)n的增加，按指數(shù)下降到任意小的值。 糾錯(cuò)編碼的的基本思想就是在被傳送的信息碼元中附加一些監(jiān)督碼元，在兩者之間建立某種校驗(yàn)關(guān)系，當(dāng)這種校驗(yàn)關(guān)系因傳輸錯(cuò)誤而受到破壞時(shí)，可以被發(fā)現(xiàn)并予以糾正。 21以一組二進(jìn)制碼為例 三位二進(jìn)制碼元有8個(gè)碼組，如果用來表示天氣的8種情況000（晴），001（雷），010（雹），011（陰），100（風(fēng)），101（云），110（雨），111（雪），如果有一個(gè)誤碼，接收端以為是另一條信息，這種編碼沒有檢錯(cuò)和糾錯(cuò)能力。 如果這8種碼組只用來傳送4條信息，即只準(zhǔn)使用其中的4種碼組000（晴），011（陰）

10、，101（云），110（雨），如果有一位誤碼，不會(huì)在接收端產(chǎn)生誤判，會(huì)檢出錯(cuò)誤。22 4個(gè)狀態(tài)只用2位二進(jìn)制碼就可以表達(dá)，所增加的第3位，就稱為監(jiān)督碼元。增加1位監(jiān)督碼元，只能檢出1位誤碼，對(duì)于上例，如果有2位誤碼，將發(fā)生誤判。如將000（晴）誤傳成101（云）。 要抗多位誤碼，就要增加監(jiān)督碼元的個(gè)數(shù)，即增加冗余度。23碼距與檢錯(cuò)和糾錯(cuò)能力 定義： 1、：碼組中非零碼元的個(gè)數(shù)。如001，碼重為1；011，碼重為2。 2、：兩個(gè)碼組中對(duì)應(yīng)碼位上具有的不同二進(jìn)制碼元的個(gè)數(shù)定義為兩個(gè)碼組的距離（漢明距，簡(jiǎn)稱碼距），如111和000，碼距為3，111和100碼距為2，111和110碼距為1。 3、：對(duì)

11、于許用的n個(gè)碼組，各碼組之間最小的碼距稱為最小碼距。2425 對(duì)于如圖所示的3位二進(jìn)制碼，如果8個(gè)碼組可用，（000，001，010，011，100，101，110，111），各點(diǎn)之間最小相差1個(gè)邊長(zhǎng)，最小碼距為1。 如果只有4個(gè)碼組可用，選（010，111，100，001）或（110，011，000，101），各點(diǎn)之間相差2個(gè)邊長(zhǎng)，最小碼距為2。 如果只有2個(gè)碼組可用，分別選（111，000）（100，011）（110，001）（101，010），各點(diǎn)之間相差3個(gè)邊長(zhǎng)，最小碼距為3。26碼距與檢錯(cuò)和糾錯(cuò)能力 如上所述，一種編碼的最小碼距直接關(guān)系到這種碼的檢錯(cuò)和糾錯(cuò)能力，因此最小碼距是信道編碼

12、的一個(gè)重要參數(shù)。在一般情況下，對(duì)于分組碼有如下結(jié)論： （1）在一個(gè)碼組內(nèi)檢測(cè)個(gè)e誤碼，要求最小碼距 dmin=e+1 （2）在一個(gè)碼組內(nèi)糾正個(gè)t誤碼，要求最小碼距 dmin=2t+1 （3）在一個(gè)碼組內(nèi)糾正t個(gè)誤碼，同時(shí)檢測(cè)e個(gè)(e=t)誤碼（當(dāng)誤碼數(shù)大于t時(shí)就不能糾錯(cuò)，只能檢測(cè)e個(gè)誤碼），要求最小碼距 dmin=t+e+12711.1.5 幾種實(shí)用的簡(jiǎn)單檢錯(cuò)碼 1、奇偶監(jiān)督碼 這是一種最簡(jiǎn)單的檢錯(cuò)碼，又稱奇偶校驗(yàn)碼，在計(jì)算機(jī)數(shù)據(jù)通信中得到廣泛應(yīng)用。七單位國際5層字母表、美國信息交換碼ASCII字母表中都用7比特碼組表示128種字符，如字符A的編碼為1000001。為了檢查字符傳輸過程中是否有

13、誤，常在7比特碼組后碼組后加1位作為奇偶校驗(yàn)位。使得8位碼組（一個(gè)字節(jié)）中的“1”的個(gè)數(shù)為奇數(shù)或偶數(shù)，如果為奇數(shù)，稱為奇校驗(yàn)碼；偶數(shù)時(shí)，稱為偶校驗(yàn)碼。 編碼規(guī)則是：首先將要傳送的信息分成組，然后將各位二進(jìn)制信息加監(jiān)督位用模2和。選擇正確的監(jiān)督位，使模2和為“0”（偶校驗(yàn)），為“1”（奇校驗(yàn)）。 28 2、水平奇偶監(jiān)督碼 將經(jīng)過奇偶監(jiān)督編碼的碼元按行排成方陣，但傳送時(shí)則按列進(jìn)行的順序傳送。接收端仍將碼元排成發(fā)送時(shí)的方形陣式，然后再進(jìn)行奇偶校驗(yàn)。如： 發(fā)送時(shí)按順序傳送11101110011000010101。以此來抗突發(fā)性錯(cuò)誤。29 3、水平垂直奇偶校驗(yàn)碼 在水平奇偶監(jiān)督碼的基礎(chǔ)上，對(duì)方陣中的每一

14、列也進(jìn)行奇偶校驗(yàn)。發(fā)送時(shí)按列序順次傳送，接收端恢復(fù)成方陣后進(jìn)行奇偶校驗(yàn)，如： 傳送順序?yàn)?11010110011100001101011，它能發(fā)現(xiàn)某一行或某一列上所有奇數(shù)個(gè)誤碼。30 4、群計(jì)數(shù)碼 監(jiān)督碼組中“1”的個(gè)數(shù)構(gòu)成所謂群計(jì)數(shù)碼。例如一個(gè)碼組的信息碼元為1010111，其中有5個(gè)“1”，用二進(jìn)制表示為101，將它作為監(jiān)督碼元附加在信息碼元之后，傳輸碼組為1010111101。 為了提高檢突發(fā)錯(cuò)誤的能力，也可以仿照水平奇偶方法，將信息排成方陣，按列發(fā)送。 31 5、恒比碼 在恒比碼中，每個(gè)碼組中“1”（或“0”）的個(gè)數(shù)相同，因而稱為等重碼。檢測(cè)時(shí)，只要計(jì)算每個(gè)碼組中“1”的數(shù)目是否對(duì)，就

15、能判斷有無錯(cuò)誤。 我國電傳機(jī)傳輸漢字電碼的通信中，廣泛采用五單位數(shù)字保護(hù)電碼。每個(gè)碼組長(zhǎng)度為5，共有25=32種組合，其中“1”的個(gè)數(shù)為3的編碼正好10個(gè)，分別代表阿拉伯?dāng)?shù)字（110）。1-01011；2-11001；3-10110；4-11010；5-00111；6-10101；7-11100；8-01110；9-10011；10-01101。 在國際ARQ電報(bào)通信系統(tǒng)中，它采用3個(gè)“1”、4個(gè)“0”的恒比碼，7中取3共有35個(gè)許用碼組，分別代表26個(gè)字母及其它符號(hào)。3211.2.5 漢明（Hamming)碼 漢明碼是1950年由美國貝爾實(shí)驗(yàn)室漢明提出來的，是第一個(gè)設(shè)計(jì)用來糾正錯(cuò)誤的線性分組

16、碼，漢明碼被廣泛用于數(shù)字通信和數(shù)據(jù)存儲(chǔ)系統(tǒng)中。 對(duì)于奇偶校驗(yàn)的偶校驗(yàn)，我們用下式作為作為021.aaaSnn 在接收端譯碼時(shí)，若S=0，就認(rèn)為無錯(cuò)。 若S=1，就認(rèn)為有錯(cuò)。 這里稱S為校正子（校驗(yàn)子），又稱伴隨式。 33漢明（Hamming)碼 在上例中，由于只有一位監(jiān)督碼元，一個(gè)監(jiān)督方程，所以只能檢錯(cuò)，無法糾錯(cuò)。 漢明碼（n,k)是一種可用于糾單個(gè)隨機(jī)錯(cuò)誤的循環(huán)編碼。一般漢明碼的參數(shù)如下： 碼長(zhǎng) n=2r-1 信息位 k=2r-1-r 監(jiān)督位 r=n-k，r是不小于3的任意正整數(shù)。 （因?yàn)橐mt位錯(cuò)誤，dmin大于2t+1) 最小漢明距離 d=3 下表是的一般漢明碼結(jié)構(gòu)。34碼字長(zhǎng)度n 信息

17、位k 校驗(yàn)位r74315114312656357635（7，4）漢明碼舉例 對(duì)于（7，4）漢明碼，碼元為a6,a5,a4,a3,a2,a1,a0 假設(shè)有三個(gè)相應(yīng)的監(jiān)督方程，在接收端根據(jù)校正子的能糾正某一位的錯(cuò)誤。034631356224561aaaaSaaaaSaaaaSS1 S2 S3 錯(cuò)碼位置001a0010a1100a2011a3101a4110a5111a6000無錯(cuò)36（7，4）漢明碼舉例 如果傳送a6,a5,a4,a3共4位數(shù)據(jù)，要求能自動(dòng)糾正單個(gè)誤碼，須增加3位監(jiān)督碼a2,a1,a0。監(jiān)督碼的計(jì)算方程見下式。346035614562aaaaaaaaaaaa 7位數(shù)據(jù)按a6,a5,

18、a1,a0的順序一起發(fā)送，在接收端按校正子（伴隨式）的組合來判斷在哪一位出現(xiàn)了錯(cuò)誤，并實(shí)時(shí)糾正（將相應(yīng)位取非）。37（7，4）漢明碼的編碼器和譯碼器（1）38（7，4）漢明碼的編碼器（2）+Z-1Z-1Z-1+1xx2x3s1s2（1）S1接通，S2擲向下端，輸出數(shù)據(jù)位a6,a5,a4,a3的同時(shí)，反饋移位寄存器串行接收數(shù)據(jù)，延時(shí)等待推出監(jiān)督位。（2）4位數(shù)據(jù)發(fā)完后，斷開S1，將S2擲向上端，開始送監(jiān)督位。（3）3位監(jiān)督位送完后，開關(guān)又?jǐn)S回原位。（4）設(shè)監(jiān)督位為n，反饋移位寄存器由n位的本原多項(xiàng)式設(shè)計(jì)。39（15，11）漢明碼舉例 對(duì)于（15，11）漢明碼，碼為a14,a13,a12.,a3,

19、a2,a1,a0 假設(shè)有四個(gè)相應(yīng)的監(jiān)督方程，在接收端根據(jù)校正子的能糾正某一位的錯(cuò)誤0457101112144146810111314325691012131423789111213141aaaaaaaaSaaaaaaaaSaaaaaaaaSaaaaaaaaSS1 S2 S3 s4錯(cuò)碼位置0001a00010a10100a21000a30011a40101a50110a61001a71010a81100a90111a101011a111101a121110a131111a140000無錯(cuò)40（15，11）漢明碼舉例 同理，如果傳送a14,a13.a5,a4共11位數(shù)據(jù)，要求能自動(dòng)糾正單個(gè)誤碼，須

20、增加4位監(jiān)督碼a3,a2,a1,a0。監(jiān)督碼的計(jì)算方程見下式。457101112140468101113141569101213142789111213143aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 15位數(shù)據(jù)按a14,a13,a1,a0的順序一起發(fā)送，在接收端按校正子（伴隨式）的組合來判斷在哪一位出現(xiàn)了錯(cuò)誤，并實(shí)時(shí)糾正（將相應(yīng)位取非）。4111.2 線性分組碼 線性分組碼定義：分組碼中和監(jiān)督碼元是用線性方程聯(lián)系起來的一種差錯(cuò)控制碼。 漢明碼是線性分組碼的一種，能糾一位誤碼。 線性分組碼有三個(gè)重要的運(yùn)算式：監(jiān)督矩陣、生成矩陣和校正子。 42(11.2.2) 1、 從上節(jié)

21、漢明碼的例子可以看出，線性分組碼的監(jiān)督方程可以用矩陣形式來表達(dá)（無誤碼時(shí)，下式成立）： 式中的系數(shù)矩陣稱為，用H表示。如果用虛線分為兩部分，左邊為P矩陣，是一個(gè)r*k階矩陣；右邊為Ir矩陣，是一個(gè)r*r階單位方陣。0000123456100110101010110010111aaaaaaa431、 設(shè)發(fā)送序列為A，則監(jiān)督方程也可以寫為：0000123456OaaaaaaaAOHAT其中44(11.2.3) 2、生成矩陣 已知監(jiān)督方程和信號(hào)碼元時(shí)可以按下式算出監(jiān)督碼元，式中用的是P矩陣。 或者用下式來計(jì)算，式中的矩陣是P的轉(zhuǎn)置矩陣，稱為Q矩陣。3456110110110111012aaaaaaa

22、1101010111113456012aaaaaaa452、生成矩陣 在Q的左邊加一個(gè)k*k階單位方陣，就生成一個(gè)新的矩陣G。1101000101010001100101110001G 這個(gè)新矩陣G稱為生成矩陣，因?yàn)榭捎伤a(chǎn)生整個(gè)碼組A。GaaaaA345646(11.2.4) 校正子 設(shè)發(fā)送碼組A為一n列的行矩陣，矩陣中n個(gè)元素就是碼組中的n個(gè)碼元。發(fā)送碼組在傳輸過程中出現(xiàn)了誤碼，接收端收到了B矩陣，也是一n列的行矩陣。 設(shè)收發(fā)碼組之差E=B-A（模2），稱為。校正子S可以根據(jù)接收序列和H矩陣來計(jì)算。TTTTTEHEHOEHAHHEABHS)( 可見校正子只與錯(cuò)誤圖樣有關(guān)，與發(fā)送序列無關(guān)，是

23、一個(gè)信道參數(shù)。47校正子 如果不出現(xiàn)誤碼，校正子S=0。 如果有誤碼，通過計(jì)算校正子S來指示誤碼的位置和糾正誤碼。設(shè)發(fā)送的序列A=0001011 錯(cuò)誤圖樣E=0001000 接收到的序列B=0000011，校正子可以由下式計(jì)算得到：1000100011101010111111100000THBS=(0 1 1)指示a3有錯(cuò)誤。 4811.3 循環(huán)碼 循環(huán)碼是線性分組碼中的一類，是以現(xiàn)代代數(shù)理論作為基礎(chǔ)建立起來的。 循環(huán)碼的編碼和譯碼設(shè)備相對(duì)簡(jiǎn)單 循環(huán)碼的檢錯(cuò)和糾錯(cuò)能力較強(qiáng)。49循環(huán)碼的循環(huán)特性 循環(huán)碼與其它線性分組碼一樣，設(shè)總長(zhǎng)度為n，前k位是信息位，后r位是監(jiān)督位。(r=n-k) 循環(huán)碼中任

24、意一許用碼組經(jīng)過循環(huán)移位后(將最右端的碼元移至左端)，所得到的碼組仍是許用碼組。如表所示。a6a5a4a3a2a1a01000000020010111301011104011100151001011610111007110010181110010碼組編號(hào)信息位監(jiān)督位50循環(huán)碼的循環(huán)特性一般來說，若（an-1,an-2,a0)是循環(huán)碼的碼組，則（an-2,an-3,a0,an-1)（an-3,an-4,an-1,an-2) （a0,an-1,a2,a1)也是該循環(huán)碼的碼組。51循環(huán)碼的循環(huán)特性 碼組（an-1,an-2,a1,a0)也可以用一個(gè)多項(xiàng)式來表示 A(X)=an-1xn-1+an-2x

25、n-2+a1x+a0 對(duì)于一個(gè)（7，3）循環(huán)碼，任一碼組可以表示為 A(X)=a6x6+a5x5+a4x4+a3x3+a2x2+a1x+a0 式中a6,a5,a1,a0是編碼，x只是碼元位置的標(biāo)記。52循環(huán)碼的循環(huán)特性 對(duì)于一個(gè)循環(huán)碼組，可以用下列碼多項(xiàng)式來分別表示。 A（X）=an-1xn-1+an-2xn-2+a1x+a0 A（X）=an-2xn-1+an-3xn-2+a1x2+a0 x+an-1 Ai（X）=an-i-1xn-1+an-i-2xn-2+a0 xi+an-1xi-1+an-i 我們來看下式：53循環(huán)碼的循環(huán)特性 式中采用模2加減，所以加法與減法是等效的。 若被除式是xA（X

26、）（許用碼組），除式是xn+1（已知多項(xiàng)式），余式是A（X）（循環(huán)移一位的許用碼組）。 若被除式是xiA（X）（許用碼組），除式是xn+1（已知多項(xiàng)式），余式是Ai（X）（循環(huán)移i位的許用碼組）。54循環(huán)碼的循環(huán)特性例如某循環(huán)碼1100101， 則A(X)=X6+X5+X2+1, XA(X)=X7+X6+X3+X,11113673677XXXXXXXXX余數(shù)余數(shù)構(gòu)成的碼是1001011，正好是循環(huán)一位的結(jié)果。55循環(huán)碼的循環(huán)特性例如某循環(huán)碼1100101， 則A(X)=X6+X5+X2+X1, X2A(X)=X8+X7+X4+X2,1111247247824787XXXXXXXXXXXXXXX

27、X余數(shù)構(gòu)成的碼是0010111，正好是循環(huán)兩位的結(jié)果。56由此得到一個(gè)重要結(jié)論 57首先要找到第一個(gè)許用碼組A（x） 在循環(huán)碼中，有一個(gè)許用碼組比較特殊，就是全0碼，即信息位全0時(shí)，監(jiān)督位也取全0，通過這一點(diǎn)可以找出另一個(gè)許用碼組。 結(jié)論： 假若第k位不為1，將造成信息位全為零，而監(jiān)督位不為0的情況， 若第n位不為1，右移一位后，將使信息位全為0，而監(jiān)督位不為0。58循環(huán)碼的生成多項(xiàng)式g（x） 這一個(gè)前k-1位為0，第k位和第n位為1的許用碼組可以用一個(gè)碼多項(xiàng)式g(x)來標(biāo)識(shí)，稱為循環(huán)碼的生成多項(xiàng)式。 （1）g(x)是一個(gè)能除盡xn+1的n-k階多項(xiàng)式。 （2）要尋找生成多項(xiàng)式，必須對(duì)xn+1

28、進(jìn)行因式分解，這需要計(jì)算機(jī)來完成。 （3）在一些參考書上有因式分解的表格可以選用。59循環(huán)碼的監(jiān)督多項(xiàng)式h（x） 設(shè)多項(xiàng)式h(x)滿足下式： h(x)g(x)=xn+1 就稱h(x)為監(jiān)督多項(xiàng)式。60X7+1因式分解構(gòu)成的循環(huán)碼生成多項(xiàng)式(n,k) dg(x)h(x)(7,6) 2x+1(x3+x+1)(x3+x2+x1)(7,4) 3x3+x2+1(x3+x+1)(x+1)(7,3) 4(x3+x+1)(x+1)x3+x2+1(7,1) 7(x3+x+1)(x3+x2+x1)x+1表中x3是x的三次方，x2是x的二次方。61由生成多項(xiàng)式得到生成矩陣根據(jù)生成多項(xiàng)式可以求出生成矩陣G（x）)()

29、(.)()()(21xgxgxxgxxgxXGkk62根據(jù)生成矩陣可以由信息碼組求出傳輸碼組)()(.)()().()(2100112211xgxgxxgxxgxxmxmxmxmxAkkkkkk63X7+1因式分解后構(gòu)成的循環(huán)碼特例 因式分解x7+1=(x+1)(x3+x+1)(x3+x2+1)。 （1）若取x+1為生成多項(xiàng)式，這是一種（7，6）碼，有6個(gè)信息位，1個(gè)糾錯(cuò)位，這是一種偶校驗(yàn)碼。 （2）若取(x3+x2+1)為生成多項(xiàng)式，這是由本原多項(xiàng)式構(gòu)成的（7，4）的漢明碼。（能糾1位錯(cuò)碼）。 （3）若取(x3+x+1)(x3+x2+1)為生成多項(xiàng)式，只有1位信息位，構(gòu)成的是全1碼或全0碼。

30、64例題一 對(duì)于一（7，3）循環(huán)碼，其 g(x)=(x3+x2+1)(x+1)=x4+x2+x+1 生成矩陣G（X）便可寫成1000000000)()()()(2423523462xxxxxxxxxxxxgxxgxgxXG65例題一111010001110100011101G 這不是典型的生成矩陣形式，若將第一列加上第三列，則如下生成矩陣形式。111010001110101101001G66例題一假設(shè)信息碼是111，生成序列為A（X）0100111111010001110101101001111)(XA假設(shè)信息碼是110，生成序列為A（X）101001111101000111010110100

31、1011)(XA和循環(huán)的結(jié)果一致。67例題一 其它信息碼的編碼結(jié)果見下表a6a5a4a3a2a1a01000000020010111301011104011100151001011610111007110010181110010碼組編號(hào)信息位監(jiān)督位68循環(huán)碼編碼器 循環(huán)碼的編碼電路，用硬件實(shí)現(xiàn)，可以采用除法電路。 對(duì)于生成多項(xiàng)式為g(x)=x4+x2+x+1的編碼器，其硬件電路如圖所示：69循環(huán)碼編碼器 （1）首先將xn+1（ x7+1）多項(xiàng)式展開，取最高冪為xn-k（ x4）的一個(gè)組合項(xiàng)為g(x)。 （2）對(duì)應(yīng)g(x)有4級(jí)移位寄存器D1，D2，D3，D4， g(x)多項(xiàng)式系數(shù)是1還是0表示該位上有無反饋線。 （3）當(dāng)信息位輸入時(shí)，控制器使Q1和Q3為正，Q2為0，開通門1和門3，此時(shí)電路除輸出信息碼之外，還送到除法電路進(jìn)行運(yùn)算。 （4）當(dāng)信息位傳完之后，控制電路將Q2為正，Q1、Q3為0，開通門2，使寄存器中的除法余項(xiàng)（監(jiān)督碼元）依此輸出。70反饋輸出D1D2D3D4FA000000011110111100111010101000