第五章糾錯(cuò)編碼

1、第五章 糾錯(cuò)編碼1第五章第五章 糾錯(cuò)編碼糾錯(cuò)編碼5.1 5.1 糾錯(cuò)編碼的基本概念糾錯(cuò)編碼的基本概念5.2 5.2 線性分組碼線性分組碼5.35.3 循環(huán)碼循環(huán)碼5.4 5.4 卷積碼卷積碼 25.1 糾錯(cuò)編碼的基本概念糾錯(cuò)編碼的基本概念5.1.1 5.1.1 糾錯(cuò)編碼的任務(wù)糾錯(cuò)編碼的任務(wù)5.1.2 5.1.2 糾錯(cuò)編碼的分類糾錯(cuò)編碼的分類5.1.35.1.3 譯碼準(zhǔn)則譯碼準(zhǔn)則5.1.4 5.1.4 香農(nóng)第二定理香農(nóng)第二定理345.1 信道編碼的任務(wù)信道編碼的任務(wù)5.1 信道編碼信道編碼5l信源編碼信源編碼l提高數(shù)字信號(hào)提高數(shù)字信號(hào)l將信源的模擬信號(hào)轉(zhuǎn)變?yōu)閿?shù)字信號(hào)將信源的模擬信號(hào)轉(zhuǎn)變?yōu)閿?shù)字信號(hào)

2、l降低數(shù)碼率降低數(shù)碼率,壓縮傳輸頻帶壓縮傳輸頻帶(數(shù)據(jù)壓縮數(shù)據(jù)壓縮)l信道編碼信道編碼l提高數(shù)字通信提高數(shù)字通信 數(shù)字信號(hào)在信道的傳輸過程中數(shù)字信號(hào)在信道的傳輸過程中,由于實(shí)際由于實(shí)際信道信道的的傳輸特性不理想傳輸特性不理想以及存在加性以及存在加性噪聲噪聲,在接收端往在接收端往往會(huì)產(chǎn)生往會(huì)產(chǎn)生誤碼誤碼。5.1 信道編碼的任務(wù)信道編碼的任務(wù)6 信道編碼信道編碼：就是按一定的規(guī)則給信源輸出序列增加：就是按一定的規(guī)則給信源輸出序列增加某些冗余符號(hào)，使其變成滿足一定數(shù)學(xué)規(guī)律的碼序列某些冗余符號(hào)，使其變成滿足一定數(shù)學(xué)規(guī)律的碼序列（或碼字），再經(jīng)信道進(jìn)行傳輸。（或碼字），再經(jīng)信道進(jìn)行傳輸。（提高傳輸?shù)目煽?/p>

3、性）（提高傳輸?shù)目煽啃裕?信道譯碼信道譯碼：就是按與編碼器同樣的數(shù)學(xué)規(guī)律去掉接：就是按與編碼器同樣的數(shù)學(xué)規(guī)律去掉接收序列中的冗余符號(hào)收序列中的冗余符號(hào), , 恢復(fù)信源消息序列?；謴?fù)信源消息序列。 一般地說，所加的冗余符號(hào)越多，糾錯(cuò)能力就越強(qiáng)，一般地說，所加的冗余符號(hào)越多，糾錯(cuò)能力就越強(qiáng)，但傳輸效率降低。因此在信道編碼中明顯體現(xiàn)了傳輸有但傳輸效率降低。因此在信道編碼中明顯體現(xiàn)了傳輸有效性與可靠性的矛盾。效性與可靠性的矛盾。 編碼信道模型編碼信道模型7011011,0,1, , 0,1ninicc cccRr rrr消息消息cRm 信道編碼信道編碼 編碼信道編碼信道 信道譯碼信道譯碼 m碼字碼字接

4、收向量接收向量消息消息編碼信道模型R噪聲源噪聲源錯(cuò)誤圖樣E編碼信道模型編碼信道模型8l消息序列m總以k個(gè)碼元為一組傳輸，稱k個(gè)碼元的碼組為信息碼組。l信道編碼器按一定規(guī)則對(duì)每個(gè)信息碼組附加一些多余的碼元，構(gòu)成長(zhǎng)為n個(gè)碼元的碼組c（信道編碼）。l附加的r=n-k個(gè)碼元稱為監(jiān)督碼元錯(cuò)誤圖樣錯(cuò)誤圖樣9 為了定量描述信號(hào)的差錯(cuò)，使用差錯(cuò)圖樣表示發(fā)送和接收碼之“差”，設(shè)發(fā)送的碼為C，接收碼為R，對(duì)于M進(jìn)制碼，差錯(cuò)圖樣E為E=(CR)(modM)對(duì)于二進(jìn)制碼而言，減法運(yùn)算就是模2加法運(yùn)算，于是有ECR例如:C=10000,E=01000,R=? R=(11000)105.1 信道編碼的任務(wù)信道編碼的任務(wù)1

5、0檢錯(cuò)與糾錯(cuò)原理檢錯(cuò)與糾錯(cuò)原理 l0:晴,1:雨l若10,01。收端無法發(fā)現(xiàn)錯(cuò)誤00晴1001110011雨能發(fā)現(xiàn)一個(gè)錯(cuò)誤禁用碼組 插入1位監(jiān)督碼后具有檢出1位錯(cuò)碼的能力,但不能予以糾正。115.1 信道編碼的任務(wù)信道編碼的任務(wù)11000晴010001111000111雨晴 在只有1位錯(cuò)碼的情況下,可以判決哪位是錯(cuò)碼并予以糾正,可以檢檢出2位或2位以下的錯(cuò)碼。100011101110雨檢錯(cuò)和糾錯(cuò)方式檢錯(cuò)和糾錯(cuò)方式12l自動(dòng)請(qǐng)求重發(fā)(ARQ)：l發(fā)端發(fā)送檢錯(cuò)碼，l收端譯碼器判斷當(dāng)前碼字傳輸是否出錯(cuò)；l當(dāng)有錯(cuò)時(shí)按某種協(xié)議通過一個(gè)反向信道請(qǐng)求發(fā)送端重傳已發(fā)送的碼字(全部或部分)。優(yōu)點(diǎn)：優(yōu)點(diǎn)： 編譯碼

6、設(shè)備比較簡(jiǎn)單。 在一定的多余度碼元下，系統(tǒng)具有極強(qiáng)的糾錯(cuò)能力。 能獲得極低的誤碼率。 由于檢錯(cuò)碼的檢錯(cuò)能力與信道干擾的變化基本無關(guān)，因此這種系統(tǒng)的適應(yīng)性很強(qiáng)，特別適應(yīng)于短波、 散射、 有線等干擾情況特別復(fù)雜的信道中。 ARQ缺點(diǎn)：缺點(diǎn)： 控制電路比較復(fù)雜。 傳送消息的連貫性和實(shí)時(shí)性較差。由于反饋重發(fā)的次數(shù)與信道干擾情況有關(guān)，若信道干擾很頻繁，則信道經(jīng)常處于重發(fā)消息的狀態(tài)。ARQ檢錯(cuò)和糾錯(cuò)方式檢錯(cuò)和糾錯(cuò)方式l前向糾錯(cuò)(FEC)：l發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯(cuò)能力的碼。l接收端信道譯碼器對(duì)接收碼字進(jìn)行譯碼,若傳輸中產(chǎn)生的差錯(cuò)數(shù)目在碼的糾錯(cuò)能力之內(nèi)時(shí),譯碼器對(duì)差錯(cuò)進(jìn)行定位并加以糾正。

7、優(yōu)點(diǎn)：優(yōu)點(diǎn)： 不需要反饋信道，能夠?qū)崿F(xiàn)一對(duì)多的同步廣播通信，而且譯碼實(shí)時(shí)性好，控制電路也比ARQ簡(jiǎn)單。隨著編碼理論的發(fā)展和大規(guī)模集成技術(shù)的發(fā)展，復(fù)雜算法的譯碼設(shè)備越來越簡(jiǎn)單，成本越來越低，所以這種方式在實(shí)際中得到越來越廣泛的應(yīng)用。FEC缺點(diǎn)：缺點(diǎn)： 這種工作方式是假設(shè)糾錯(cuò)碼的糾錯(cuò)能力足夠糾正信息序列傳輸中的錯(cuò)誤，也就是糾錯(cuò)碼與信道的干擾是相匹配的，所以對(duì)信道的適應(yīng)性較差。 為了獲得合適的誤碼率，往往按照信道最差的情況設(shè)計(jì)糾錯(cuò)碼，增加的冗余碼元比檢錯(cuò)碼要多，編碼效率一般較低。 FEC檢錯(cuò)和糾錯(cuò)方式檢錯(cuò)和糾錯(cuò)方式l混合糾錯(cuò)混合糾錯(cuò)(HEC)：l是是FEC與與ARQ方式的結(jié)合。方式的結(jié)合。l發(fā)端發(fā)送

8、同時(shí)具有自動(dòng)糾錯(cuò)和檢測(cè)能力的碼發(fā)端發(fā)送同時(shí)具有自動(dòng)糾錯(cuò)和檢測(cè)能力的碼組組,收端收到碼組后收端收到碼組后,檢查差錯(cuò)情況檢查差錯(cuò)情況,如果差錯(cuò)在如果差錯(cuò)在碼的糾錯(cuò)能力以內(nèi)碼的糾錯(cuò)能力以內(nèi),則自動(dòng)進(jìn)行糾正。則自動(dòng)進(jìn)行糾正。l如果信道干擾很嚴(yán)重如果信道干擾很嚴(yán)重,錯(cuò)誤很多錯(cuò)誤很多,超過了碼的糾超過了碼的糾錯(cuò)能力錯(cuò)能力,但能檢測(cè)出來但能檢測(cè)出來,則經(jīng)反饋信道請(qǐng)求發(fā)端則經(jīng)反饋信道請(qǐng)求發(fā)端重發(fā)這組數(shù)據(jù)。重發(fā)這組數(shù)據(jù)。l信息反饋信息反饋(IRQ)：l收端把收到的數(shù)據(jù)收端把收到的數(shù)據(jù),原封不動(dòng)地通過反饋信道原封不動(dòng)地通過反饋信道送回到發(fā)端送回到發(fā)端,發(fā)端比較發(fā)的數(shù)據(jù)與反饋來的數(shù)發(fā)端比較發(fā)的數(shù)據(jù)與反饋來的數(shù)據(jù)據(jù),

9、從而發(fā)現(xiàn)錯(cuò)誤從而發(fā)現(xiàn)錯(cuò)誤,并且把錯(cuò)誤的消息再次傳送并且把錯(cuò)誤的消息再次傳送,直到發(fā)端沒有發(fā)現(xiàn)錯(cuò)誤為止。直到發(fā)端沒有發(fā)現(xiàn)錯(cuò)誤為止。優(yōu)點(diǎn)：優(yōu)點(diǎn)：由于該方式避免了FEC要求的復(fù)雜設(shè)備和ARQ方式的信息連貫性差的缺點(diǎn)，并且可以達(dá)到較低的誤碼率，因此在實(shí)際中得到了廣泛應(yīng)用。 HEC總結(jié)：信道編碼的概念l目的：降低錯(cuò)誤的譯碼概率PEl對(duì)象：信息序列l(wèi)方法：信息碼+附加碼元，收端按照一定譯碼準(zhǔn)則檢糾錯(cuò)。l實(shí)質(zhì)：增加冗余度。205.1.2 信道（糾錯(cuò)）編碼的分類l按照接收端工作狀態(tài)分為： 檢錯(cuò)碼 糾錯(cuò)碼 糾刪碼l根據(jù)糾正錯(cuò)誤的類型 糾隨機(jī)錯(cuò)誤碼 糾突發(fā)錯(cuò)誤碼21225.1.2 信道（糾錯(cuò)）編碼的分類22l隨機(jī)

10、差錯(cuò)：l差錯(cuò)是相互獨(dú)立的,不相關(guān)l存在這種差錯(cuò)的信道是無記憶信道或隨機(jī)信道l突發(fā)差錯(cuò)：l指成串出現(xiàn)的錯(cuò)誤,錯(cuò)誤與錯(cuò)誤間有相關(guān)性,一個(gè)差錯(cuò)往往要影響到后面一串字lE: 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0突發(fā)長(zhǎng)度= 4突發(fā)長(zhǎng)度= 65.1.2 信道（糾錯(cuò)）編碼的分類l按照發(fā)送端編碼方式分為：235.1.3譯碼準(zhǔn)則245.1.3譯碼準(zhǔn)則25),.,2 , 1;,.,2 , 1()(sjriabFij5.1.3譯碼準(zhǔn)則26（1）對(duì)輸入符號(hào)集為X=a1,a2,ar，輸出符號(hào)集為Y= b1,b2,bs的信道來說，一共可構(gòu)成rs種不同的譯碼規(guī)則。

11、不同的譯碼規(guī)則會(huì)引起不同的可靠程度。5.1.3譯碼準(zhǔn)則27 最小錯(cuò)誤譯碼準(zhǔn)則（最小錯(cuò)誤譯碼準(zhǔn)則（MEPD） 最大后驗(yàn)概率準(zhǔn)則（最大后驗(yàn)概率準(zhǔn)則（MPPD） 最大聯(lián)合概率準(zhǔn)則（最大聯(lián)合概率準(zhǔn)則（MJPD） 最大似然概率準(zhǔn)則（最大似然概率準(zhǔn)則（MLD）()()()ijjjiF bap b ap b a，（ =1.r）()()()ijjijF bap a bp ab，（ =1.r）()()()ijjijF bap a bp a b，（ =1.r）()minjEF baP，信道輸入等概時(shí)，MLD和MJPD等價(jià)5.1.4香農(nóng)第二定理285.1.4香農(nóng)第二定理29表述二：表述二：設(shè)離散無記憶信道的信道容量

12、為C，信息傳輸率為R，對(duì)于任意小的正數(shù)，當(dāng)Rk) 碼字，其中 (nk) 個(gè)附加碼元是由信息碼元的線性運(yùn)算產(chǎn)生的。l信息碼組長(zhǎng)信息碼組長(zhǎng) k 位，有位，有 2k 個(gè)不同的信息碼組，則應(yīng)該有個(gè)不同的信息碼組，則應(yīng)該有 2k 個(gè)碼字與它們一一對(duì)應(yīng)。個(gè)碼字與它們一一對(duì)應(yīng)。5.2.1 線性分組碼的基本概念線性分組碼的基本概念5.2 線性分組碼325.2.1 線性分組碼的基本概念線性分組碼的基本概念l線性分組碼線性分組碼：通過預(yù)定的線性運(yùn)算將長(zhǎng)為：通過預(yù)定的線性運(yùn)算將長(zhǎng)為 k 位的信位的信息碼組變換成息碼組變換成 n 長(zhǎng)的碼字長(zhǎng)的碼字 ( nk )。由。由 2k 個(gè)信息碼組個(gè)信息碼組所編成的所編成的 2k

13、個(gè)碼字集合，稱為個(gè)碼字集合，稱為線性分組碼線性分組碼。l碼矢碼矢：一個(gè)：一個(gè) n 長(zhǎng)的碼字可以用矢量來表示長(zhǎng)的碼字可以用矢量來表示C C = (Cn1,Cn2,C1,C0 ) 所以碼字又稱為碼矢。所以碼字又稱為碼矢。l( n, k ) 線性碼線性碼：信息位長(zhǎng)為：信息位長(zhǎng)為 k，碼長(zhǎng)為，碼長(zhǎng)為 n 的線性碼的線性碼l編碼效率編碼效率/編碼速率編碼速率/碼率：碼率：R=k /n。它說明了信道的。它說明了信道的利用效率，利用效率，R是衡量碼性能的一個(gè)重要參數(shù)是衡量碼性能的一個(gè)重要參數(shù)。5.2 線性分組碼335.2.1 線性分組碼的基本概念線性分組碼的基本概念線性體現(xiàn)在線性體現(xiàn)在：輸入輸出的關(guān)系為線性

14、映射關(guān)系輸入輸出的關(guān)系為線性映射關(guān)系碼元中每個(gè)碼字由信源做模二加運(yùn)算得到碼元中每個(gè)碼字由信源做模二加運(yùn)算得到線性分組碼的特點(diǎn)線性分組碼的特點(diǎn)：在碼集中存在全在碼集中存在全0碼字碼字滿足封閉性滿足封閉性5.2 線性分組碼345.2.1 線性分組碼的基本概念線性分組碼的基本概念定理定理：線性分組碼的最小距離等于最小非零碼字重量。：線性分組碼的最小距離等于最小非零碼字重量。定理中涉及到的基本概念定理中涉及到的基本概念漢明重量漢明重量：碼字中非：碼字中非0碼的個(gè)數(shù)。碼的個(gè)數(shù)。最小漢明重量最小漢明重量：碼集中非：碼集中非0碼字漢明重量的最小值。碼字漢明重量的最小值。漢明距離漢明距離：兩個(gè)等長(zhǎng)碼：兩個(gè)等長(zhǎng)

15、碼C和和C中，對(duì)應(yīng)位碼元不同的取中，對(duì)應(yīng)位碼元不同的取值個(gè)數(shù)。值個(gè)數(shù)。最小漢明距離最小漢明距離：碼集中所有碼字距離的最小值。：碼集中所有碼字距離的最小值。0min( )dw c5.2 線性分組碼355.2.2 線性分組碼的編碼線性分組碼的編碼一、生成矩陣一、生成矩陣 G 中每一行 gi = ( gi 1, gi 2, , gi n ) 都是一個(gè)碼字；l生成矩陣的定義生成矩陣的定義：由于矩陣 G 生成了 (n,k) 線性碼中的任何一個(gè)碼字，稱矩陣 G 為 (n,k) 線性碼的生成矩陣。l(n,k) 線性碼的每一個(gè)碼字都是生成矩陣 G 的行的線性組合。cmG5.2 線性分組碼365.2.2 線性分

16、組碼的編碼線性分組碼的編碼一、生成矩陣一、生成矩陣l標(biāo)準(zhǔn)生成矩陣：標(biāo)準(zhǔn)生成矩陣： 通過行初等變換，將 G 化為前 k 行和k 列是單位子陣的標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式11121()21222()12()100010GIQ001n kn kk nkk rkkk n kqqqqqqqqq 5.2 線性分組碼375.2.2 線性分組碼的編碼線性分組碼的編碼二、編碼二、編碼l線性系統(tǒng)分組碼線性系統(tǒng)分組碼：用標(biāo)準(zhǔn)生成矩陣用標(biāo)準(zhǔn)生成矩陣 GGkn 編成的碼編成的碼字，前面字，前面 k 位為信息數(shù)字，后面位為信息數(shù)字，后面 r=nk 位為校驗(yàn)位為校驗(yàn)字，這種信息數(shù)字在前校驗(yàn)數(shù)字在后的線性分組碼字，這種信息數(shù)字在前校驗(yàn)

17、數(shù)字在后的線性分組碼稱為線性系統(tǒng)分組碼。稱為線性系統(tǒng)分組碼。l當(dāng)生成矩陣當(dāng)生成矩陣 G G 確定之后，確定之后，(n,k) 線性碼也就完全被線性碼也就完全被確定了，只要找到碼的生成矩陣，編碼問題也同樣確定了，只要找到碼的生成矩陣，編碼問題也同樣被解決了。被解決了。38舉例舉例： 已知一個(gè)已知一個(gè) (7,4) 線性碼的生成矩陣線性碼的生成矩陣G如下圖示，當(dāng)輸入信息碼元為如下圖示，當(dāng)輸入信息碼元為1010時(shí)，試求輸出的碼字。時(shí)，試求輸出的碼字。n由矩陣乘法規(guī)則可知：由矩陣乘法規(guī)則可知： C C = = m m G G 的結(jié)果，就是矩陣的結(jié)果，就是矩陣 G G 中，與中，與 m m 中為中為“1 1

18、” ”的元素相對(duì)應(yīng)的的元素相對(duì)應(yīng)的行按位模行按位模 2 2 加的結(jié)果。加的結(jié)果。5.2.2 線性分組碼的編碼4 71 41 71 44 710001010100111G00101100001011m(1010)10001010100111CmG1010(1010011)00101100001011395.2.2 線性分組碼的編碼練習(xí)：練習(xí)： 已知某線性分組碼的生成矩陣為已知某線性分組碼的生成矩陣為l試問試問：l（1）n = ? k = ? , 該碼組集合中的碼字有多少？該碼組集合中的碼字有多少？l（2）若信息碼元若信息碼元 m 分別是分別是 1100 和和1111時(shí)時(shí) , 寫出其對(duì)應(yīng)的輸出碼字

19、。寫出其對(duì)應(yīng)的輸出碼字。10000110100101G00101100001111405.2.3 線性分組碼的譯碼一、一致校驗(yàn)矩陣一、一致校驗(yàn)矩陣l推廣到一般情況：對(duì)推廣到一般情況：對(duì) (n,k) 線性分組碼，每個(gè)碼字中的線性分組碼，每個(gè)碼字中的 r(r=nk) 個(gè)監(jiān)督元與信息元之間的關(guān)系可由下面的線性個(gè)監(jiān)督元與信息元之間的關(guān)系可由下面的線性方程組確定方程組確定000022110222212101212111ChChChChChChChChChrnnrnrnnnnnn415.2.3 線性分組碼的譯碼一、一致校驗(yàn)矩陣一、一致校驗(yàn)矩陣l令系數(shù)矩陣為令系數(shù)矩陣為 HH，碼字行陣列為，碼字行陣列為 C

20、 C矩陣。線性分組碼的一致監(jiān)督為稱或則：),(H0HC0CHCH11110211212222111211knCCChhhhhhhhhrTrnnTrTnnrnnnrnrrnnnr425.2.3 線性分組碼的譯碼一、一致校驗(yàn)矩陣特性一、一致校驗(yàn)矩陣特性:l對(duì)對(duì)H H 各行實(shí)行初等變換，將后面各行實(shí)行初等變換，將后面 r 列化為單位子陣，于是列化為單位子陣，于是得到下面矩陣得到下面矩陣(行變換所得方程組與原方程組同解行變換所得方程組與原方程組同解)。l校驗(yàn)矩陣校驗(yàn)矩陣H H 的標(biāo)準(zhǔn)形式的標(biāo)準(zhǔn)形式：后面：后面 r 列是一單位子陣的校驗(yàn)矩列是一單位子陣的校驗(yàn)矩陣陣HH。lH H 陣的每一行都代表一個(gè)校驗(yàn)

21、方程，它表示與該行中陣的每一行都代表一個(gè)校驗(yàn)方程，它表示與該行中“1”相對(duì)應(yīng)的碼元的模相對(duì)應(yīng)的碼元的模2和為和為0。100010001H212222111211rnrrkknrppppppppp435.2.3 線性分組碼的譯碼 GIQHPI(P)G HIQPIIQ(P)Q0IGIQH(Q)ISkk rSr krTTTTr kSSkk rr krkk rr kk rk rrSkk rTSk rr生成矩陣與一致校驗(yàn)矩陣的關(guān)系生成矩陣與一致校驗(yàn)矩陣的關(guān)系:l由于生成矩陣由于生成矩陣GG的每一行都是一個(gè)碼字，所以的每一行都是一個(gè)碼字，所以G G 的每行都滿的每行都滿足足HHrnC CTn1=0 0Tr

22、1，則有，則有HHrnGGTnk=0 0Trk 或或 GGknHHTnr=0 0krl線性系統(tǒng)碼的監(jiān)督矩陣線性系統(tǒng)碼的監(jiān)督矩陣 H H 和生成矩陣和生成矩陣 G G 之間可以直接互換之間可以直接互換。445.2.3 線性分組碼的譯碼例例: 已知已知(7,4)線性系統(tǒng)碼的監(jiān)督矩陣為線性系統(tǒng)碼的監(jiān)督矩陣為1101000011010011100101010001G100101101011100010111H)4,7()4,7(陣可直接寫出它的生成矩455.2.3 線性分組碼的譯碼標(biāo)準(zhǔn)陣列譯碼l標(biāo)準(zhǔn)陣列構(gòu)造方法標(biāo)準(zhǔn)陣列構(gòu)造方法l先將先將 2k 個(gè)碼矢排成一行，作為個(gè)碼矢排成一行，作為標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列的

23、第一行，并將的第一行，并將全全0碼矢碼矢C C1=(000)放在最左面的位置上；放在最左面的位置上；l然后在剩下的然后在剩下的 (2n2k) 個(gè)個(gè) n 重中選取一個(gè)重量最輕的重中選取一個(gè)重量最輕的 n 重重 E E2 放在全放在全0碼矢碼矢 C C1 下面，再將下面，再將 E E2 分別和碼矢分別和碼矢 相加，放在對(duì)應(yīng)碼矢下面，構(gòu)成陣列第二行；相加，放在對(duì)應(yīng)碼矢下面，構(gòu)成陣列第二行；l在第二次剩下的在第二次剩下的 n 重中，選取重量最輕的重中，選取重量最輕的 n 重重 E E3，放在，放在 E E2 下面，并將下面，并將 E E3 分別加到第一行各碼矢上，得到第三分別加到第一行各碼矢上，得到第

24、三行；行；l，繼續(xù)這樣做下去，直到全部，繼續(xù)這樣做下去，直到全部 n 重用完為止。得到下重用完為止。得到下頁表格所示的頁表格所示的 (n,k) 線性碼的標(biāo)準(zhǔn)陣列。線性碼的標(biāo)準(zhǔn)陣列。46碼字 CC1(=0) (陪集首) CC2 CC E E2 CC2+ E E2 CCi + E E2 E E3 CC2+ E E3 CCi + E E3 禁 用 碼 組 5.2.3 線性分組碼的譯碼標(biāo)準(zhǔn)陣列譯碼475.2.3 線性分組碼的譯碼標(biāo)準(zhǔn)陣列譯碼標(biāo)準(zhǔn)陣列的特性：標(biāo)準(zhǔn)陣列的特性：定理定理：在標(biāo)準(zhǔn)陣列的同一行中沒有相同的矢量，而且：在標(biāo)準(zhǔn)陣列的同一行中沒有相同的矢量，而且 2n 個(gè)個(gè) n 重中任一個(gè)重中任一個(gè)

25、n 重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。L陪集陪集：標(biāo)準(zhǔn)陣列的每一行叫做碼的一個(gè)陪集。：標(biāo)準(zhǔn)陣列的每一行叫做碼的一個(gè)陪集。L陪集首陪集首：每個(gè)陪集的第一個(gè)元素叫做陪集首。：每個(gè)陪集的第一個(gè)元素叫做陪集首。485.2.3 線性分組碼的譯碼伴隨式譯碼伴隨式和錯(cuò)誤檢測(cè)：伴隨式和錯(cuò)誤檢測(cè)：l用監(jiān)督矩陣譯碼用監(jiān)督矩陣譯碼：接收到一個(gè)碼字：接收到一個(gè)碼字 R R 后，檢驗(yàn)后，檢驗(yàn) HH R RT=0 0T 是否成立：是否成立：lHRT =0T是否成立是檢驗(yàn)碼字出錯(cuò)與否的依據(jù)。l若關(guān)系成立，則認(rèn)為 R 是一個(gè)碼字；l否則判為碼字在傳輸中發(fā)生了錯(cuò)誤；l伴隨式伴隨式/監(jiān)督子監(jiān)督子/校

26、驗(yàn)子校驗(yàn)子：S S=R R HHT或或S ST=HH R RT。l如何糾錯(cuò)？如何糾錯(cuò)？l設(shè)發(fā)送碼矢 C=(Cn1,Cn2,C0)l信道錯(cuò)誤圖樣為 E=(En1,En2,E0) ，l其中其中Ei=0，表示第，表示第i位無錯(cuò)；位無錯(cuò)；lEi=1，表示第，表示第i位有錯(cuò)。位有錯(cuò)。i=n1,n2,0。495.2.3 線性分組碼的譯碼伴隨式譯碼l接收碼字接收碼字 R R =(Rn1,Rn2,R0)=C C+E E =(Cn1+En1, Cn2+En2, , C0 +E0)l求接收碼字的伴隨式（接收碼字用監(jiān)督矩陣進(jìn)行檢驗(yàn)）求接收碼字的伴隨式（接收碼字用監(jiān)督矩陣進(jìn)行檢驗(yàn)） S ST=HH R RT=HH (

27、C C+E E)T=HH C CT+HH E ETl由于由于HH C CT=0 0T，所以，所以 S ST=HH E ETl設(shè)設(shè)HH=(h h1,h h2,h hn)，其中，其中h hi表示表示HH的列。代入上式得到的列。代入上式得到505.2.3 線性分組碼的譯碼伴隨式譯碼 總結(jié)總結(jié)：l伴隨式僅與錯(cuò)誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅與錯(cuò)誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅由錯(cuò)誤圖樣決定；伴隨式僅由錯(cuò)誤圖樣決定；l伴隨式是錯(cuò)誤的判別式：伴隨式是錯(cuò)誤的判別式：l若S=0，則判為沒有出錯(cuò)，接收碼字是一個(gè)碼字；l若S0，則判為有錯(cuò)。l不同的錯(cuò)誤圖樣具有不同的伴隨式，它們是一一對(duì)

28、應(yīng)的。不同的錯(cuò)誤圖樣具有不同的伴隨式，它們是一一對(duì)應(yīng)的。對(duì)二元碼，伴隨式對(duì)二元碼，伴隨式S是是H H 陣中與錯(cuò)誤碼元對(duì)應(yīng)列之和陣中與錯(cuò)誤碼元對(duì)應(yīng)列之和。51伴隨式譯碼舉例：伴隨式譯碼舉例： 某某(7,3) 線性系統(tǒng)碼線性系統(tǒng)碼l設(shè)發(fā)送碼字設(shè)發(fā)送碼字C C = 1010011，接收碼字，接收碼字R R 1010011，R R與與C C相同。相同。無錯(cuò)。因此，譯碼器判接收字代入得和計(jì)算伴隨式，把根據(jù)接收字道就是發(fā)送的碼字，但接收端譯碼器并不知TTT0HRSRHRH10001100100011001011100011015.2.3 線性分組碼的譯碼伴隨式譯碼52l若接收碼字中有一位錯(cuò)誤若接收碼字中有

29、一位錯(cuò)誤正確。錯(cuò)能力相符，所以譯碼中錯(cuò)誤碼元數(shù)與碼的糾由于接收字的第二位是錯(cuò)的。因此判定接收字的第二列，等于且碼是糾單個(gè)錯(cuò)誤的碼，譯碼器判為有錯(cuò)。由于伴隨式為接收碼字發(fā)送碼矢RRHS0SRHSRCTTTT)3 , 7(,111011001111000110010001100101110001101111001110100115.2.3 線性分組碼的譯碼伴隨式譯碼535.2.3 線性分組碼的譯碼伴隨式譯碼l當(dāng)碼元錯(cuò)誤多于1個(gè)時(shí)位上，只是發(fā)現(xiàn)有錯(cuò)。無法判定錯(cuò)誤出在哪些同，陣中的任何一列都不相但與，不等于是第一列和第四列之和由于伴隨式為接收碼字發(fā)送碼矢H0SRHSRCTTT0110110110010

30、0011001000110010111000110100110111010011545.2.3 線性分組碼的譯碼伴隨式譯碼以上定理是糾錯(cuò)碼理論中最重要的基本定理之一，它說明了一個(gè)距離為d的線性分組碼，既可用來糾正個(gè)錯(cuò)誤，又可用來檢測(cè)e d1個(gè)錯(cuò)誤。 21dt定理定理 對(duì)于任一個(gè)（對(duì)于任一個(gè)（n，k）線性分組碼，若要在碼字內(nèi)線性分組碼，若要在碼字內(nèi) 檢測(cè)檢測(cè)e個(gè)錯(cuò)誤，則要求碼的最小距離個(gè)錯(cuò)誤，則要求碼的最小距離d e1； 糾正糾正t個(gè)錯(cuò)誤，則要求碼的最小距離個(gè)錯(cuò)誤，則要求碼的最小距離d 2t1； 糾正糾正t個(gè)錯(cuò)誤同時(shí)檢測(cè)個(gè)錯(cuò)誤同時(shí)檢測(cè)e（ t）個(gè)錯(cuò)誤，則要求個(gè)錯(cuò)誤，則要求d te1。555.2.

31、4 漢明碼 對(duì)于給定的正整數(shù)m3，二進(jìn)制漢明碼的信息位數(shù)量、 碼字長(zhǎng)度與m之間滿足下列關(guān)系:k=2mm1 n=2n-k1所以漢明碼實(shí)際就是(2m1，2mm1)分組碼。 當(dāng)m=3時(shí)，則為(7，4)碼。 二進(jìn)制漢明碼的最小漢明距離為d0=3。 565.2.4 漢明碼 例例 構(gòu)造構(gòu)造m=3的漢明碼。的漢明碼。 解解 由于由于m=3，根據(jù)漢明碼的性質(zhì)可知，根據(jù)漢明碼的性質(zhì)可知k=2mm1=4 n=2m1=7所以所以m=3的漢明碼是的漢明碼是(7，4)分組碼。分組碼。 除了矢量除了矢量0之外的所有之外的所有排列為排列為(001)，(010)，(011)，(100)，(101)，(110)，(111)，為

32、，為了產(chǎn)生系統(tǒng)碼，將了產(chǎn)生系統(tǒng)碼，將(100)，(010)，(001)放在矩陣的最后放在矩陣的最后3列，列，得到校驗(yàn)矩陣為得到校驗(yàn)矩陣為575.2.4 漢明碼011110010110101101001H于是得到生成矩陣為于是得到生成矩陣為1000011010010100101100001111G585.3 循環(huán)碼5.3.1 循環(huán)碼的基本概念循環(huán)碼的基本概念數(shù)學(xué)定義數(shù)學(xué)定義：設(shè)：設(shè)C為某為某( n, k )線性分組碼的碼組集合，如果對(duì)線性分組碼的碼組集合，如果對(duì)C中任中任意一個(gè)碼組意一個(gè)碼組c = ( an-1 an-2 a1 a0 )，它的循環(huán)移位，它的循環(huán)移位c(1) = ( an-2an-

33、3 a1 a0 an-1 )也屬于也屬于C，則稱該，則稱該( n, k )碼為循環(huán)碼碼為循環(huán)碼其中其中c(i )表示表示c碼組循環(huán)移位碼組循環(huán)移位i次。次。例如：某例如：某( 7, 4 )循環(huán)碼組集合中的一個(gè)碼組為循環(huán)碼組集合中的一個(gè)碼組為( 1000101 )，向左，向左循環(huán)移位一次后的碼組循環(huán)移位一次后的碼組( 0001011 )仍為碼組集合中第一個(gè)許用仍為碼組集合中第一個(gè)許用碼組碼組595.3 循環(huán)碼605.3 循環(huán)碼615.3.2 循環(huán)碼的描述循環(huán)碼的描述 1、循環(huán)碼多項(xiàng)式描述、循環(huán)碼多項(xiàng)式描述621、循環(huán)碼多項(xiàng)式描述、循環(huán)碼多項(xiàng)式描述碼多項(xiàng)式的模運(yùn)算碼多項(xiàng)式的模運(yùn)算正整數(shù)的模運(yùn)算正整

34、數(shù)的模運(yùn)算若一正整數(shù)若一正整數(shù)M除以正整數(shù)除以正整數(shù)N，所得到的商為，所得到的商為Q，余數(shù)為，余數(shù)為R，可表示為，可表示為其中其中Q為整數(shù)，則在模為整數(shù)，則在模N運(yùn)算下，上式的結(jié)果為：運(yùn)算下，上式的結(jié)果為：多項(xiàng)式的模運(yùn)算與正整數(shù)的模運(yùn)算相同，一般利用長(zhǎng)除法計(jì)算商式和余式多項(xiàng)式的模運(yùn)算與正整數(shù)的模運(yùn)算相同，一般利用長(zhǎng)除法計(jì)算商式和余式有兩個(gè)多項(xiàng)式有兩個(gè)多項(xiàng)式a(x)和和p(x)，一定存在有唯一的多項(xiàng)式，一定存在有唯一的多項(xiàng)式Q(x)和和r(x)，使得：，使得： 稱稱Q(x)是是a(x)除以除以p(x)的商式，的商式，r(x)是是a(x)除以除以p(x)的余式，在模的余式，在模p(x)運(yùn)算下運(yùn)算下

35、且有且有 即：除到余式的次數(shù)小于除式為止，當(dāng)能整除時(shí)即：除到余式的次數(shù)小于除式為止，當(dāng)能整除時(shí)次數(shù)為次數(shù)為00 MRQRNNN) mod，記模( NNRM為( )( ) ( )( )a xQ x p xr x)(mod )()(xpxrxa0deg ( )deg( ) r xp x63定理：對(duì)于( n, k )循環(huán)碼，若c(x)對(duì)應(yīng)碼組c = (an-1an-2 a1a0 )， c(1)的一次循環(huán)移位c(1) = ( an-2an-3 a1a0 an-1 )及c(i )(x)對(duì)應(yīng)的c碼循環(huán)移位i次c(i )，則有：證明：碼組c的多項(xiàng)式為：則有：(1)( )mod(1)mod(1)( )( ),

36、( )( ) nniixxcxxc xcxx c x-1-21210( )() nnnnc xaxaxa xa-121-2-121-1-210-1-1101)1-1(-( )(1)( )nnnnnnnnnnnnxc xaxaxa xa xaxaaxcaaxxxxaa (1)1mod(1)mod(1)(1)( )(1)( )( )nnnnxxxc xaxcxcx1、循環(huán)碼多項(xiàng)式描述、循環(huán)碼多項(xiàng)式描述碼多項(xiàng)式的模運(yùn)算碼多項(xiàng)式的模運(yùn)算1、循環(huán)碼多項(xiàng)式描述、循環(huán)碼多項(xiàng)式描述碼多項(xiàng)式的模運(yùn)算碼多項(xiàng)式的模運(yùn)算例如例如：(7 , 4)循環(huán)碼的第循環(huán)碼的第12個(gè)碼組個(gè)碼組c12為：為：1011000，則其碼多

37、項(xiàng)，則其碼多項(xiàng)式為：式為： c(x)=x6 + x4 + x3 請(qǐng)寫出請(qǐng)寫出c12左循環(huán)移位左循環(huán)移位3次的碼組次的碼組解：解：i = 3，則，則 x3c(x) = x9 + x7 + x6 其對(duì)應(yīng)碼組為：其對(duì)應(yīng)碼組為：1000101，它是，它是( 7, 4 )循環(huán)碼中的第循環(huán)碼中的第4個(gè)碼組個(gè)碼組c47362mod1( )1xx c xxx279769276276211 1 1xxxxxxxxxxxxx651、循環(huán)碼多項(xiàng)式描述、循環(huán)碼多項(xiàng)式描述生成多項(xiàng)式生成多項(xiàng)式 定義定義：記：記C(x)為為( n, k )循環(huán)碼的所有碼組對(duì)應(yīng)的多項(xiàng)式的集合循環(huán)碼的所有碼組對(duì)應(yīng)的多項(xiàng)式的集合，若，若g(x)

38、是是C(x)中除中除0多項(xiàng)式以外次數(shù)最低的多項(xiàng)式，則稱多項(xiàng)式以外次數(shù)最低的多項(xiàng)式，則稱g(x)為這個(gè)循環(huán)碼的生成多項(xiàng)式為這個(gè)循環(huán)碼的生成多項(xiàng)式其一般形式為：其一般形式為： g(x) = xr + gr-1 xr-1 + + g1 x1 + 1 g(x)具有以下性質(zhì)：具有以下性質(zhì)： 1）g(x)的的0次項(xiàng)是次項(xiàng)是1； 2）循環(huán)碼的每一碼多項(xiàng)式）循環(huán)碼的每一碼多項(xiàng)式c(x)都是都是g(x)的倍式，且每一個(gè)小于的倍式，且每一個(gè)小于等于等于n-1次的次的g(x)的倍式一定是碼多項(xiàng)式；的倍式一定是碼多項(xiàng)式； 3）g(x)的最高次為的最高次為n-k，且是唯一的；，且是唯一的； 4）g(x)是是xn + 1

39、的一個(gè)因子的一個(gè)因子生成多項(xiàng)式66l例：求(7，4)循環(huán)碼的生成多項(xiàng)式。l解：生成多項(xiàng)式解：生成多項(xiàng)式g(x)g(x)：r=n-k=7-4= r=n-k=7-4= 3 3次次首一首一多項(xiàng)式多項(xiàng)式l即將 因式分解：l選擇 或 任一均可作為（7，4）循環(huán)碼的生成多項(xiàng)式。17x)1)(1)(1 (13237xxxxxx31xx321xx 常數(shù)項(xiàng)為常數(shù)項(xiàng)為1 1，最高項(xiàng)為，最高項(xiàng)為3 3次次（n，k）循環(huán)碼的構(gòu)造步驟：對(duì)（xn+1）做因式分解，找出其n-k次因式；以n-k次因式為生成多項(xiàng)式g(x),與信息多項(xiàng)式m(x)相乘，即得到碼多項(xiàng)式： C(x)=m(x)g(x) 因m(x)不高于（k-1）次，所

40、以C(x)的次數(shù)不會(huì)高于（k-1）+（n-k）=（n-1）次。2、循環(huán)碼的構(gòu)造、循環(huán)碼的構(gòu)造討論長(zhǎng)度討論長(zhǎng)度n=7的循環(huán)碼。的循環(huán)碼。 解解 多項(xiàng)式多項(xiàng)式x7+1可以分解為下列形式可以分解為下列形式:x7+1=(x+1)(x3+x2+1)(x3+x+1)為了產(chǎn)生為了產(chǎn)生(7，4)循環(huán)碼，可以取下列兩個(gè)多項(xiàng)式之一作為生循環(huán)碼，可以取下列兩個(gè)多項(xiàng)式之一作為生成多項(xiàng)式成多項(xiàng)式:g1(x)=x3+x2+1 g2(x)=x3+x+1其中，其中，g1(x)和和g2(x)產(chǎn)生的碼是等價(jià)的。產(chǎn)生的碼是等價(jià)的。2、循環(huán)碼的構(gòu)造、循環(huán)碼的構(gòu)造具體產(chǎn)生過程為：具體產(chǎn)生過程為： 假設(shè)假設(shè)4比特信息為比特信息為(000

41、1)，對(duì)應(yīng)的信，對(duì)應(yīng)的信息多項(xiàng)式為息多項(xiàng)式為X1(x)=1，所以碼字多項(xiàng)式為，所以碼字多項(xiàng)式為C1(x)=m1(x)g1(x)=(x3+x2+1)對(duì)應(yīng)碼字為對(duì)應(yīng)碼字為C1=(0001101)當(dāng)當(dāng)4比特信息為比特信息為(0010)時(shí)，對(duì)應(yīng)的信息多項(xiàng)式為時(shí)，對(duì)應(yīng)的信息多項(xiàng)式為X2(x)=x，碼，碼字多項(xiàng)式為字多項(xiàng)式為C2(x)=m2(x)g1(x)=x(x3+x2+1)=x4+x3+x對(duì)應(yīng)碼字為對(duì)應(yīng)碼字為C2=(0011010)2、循環(huán)碼的構(gòu)造、循環(huán)碼的構(gòu)造 當(dāng)當(dāng)4比特信息為比特信息為(0011)時(shí)，對(duì)應(yīng)的信息多項(xiàng)式為時(shí)，對(duì)應(yīng)的信息多項(xiàng)式為m3(x)=x+1，碼字多項(xiàng)式為，碼字多項(xiàng)式為331324

42、332( )( )( ) (1)(1) ()(1)Cxmx gxxxxxxxxx 注意到二進(jìn)制多項(xiàng)式加法為同階次項(xiàng)的系數(shù)進(jìn)行半加注意到二進(jìn)制多項(xiàng)式加法為同階次項(xiàng)的系數(shù)進(jìn)行半加運(yùn)算，所以運(yùn)算，所以x3+x3=(1+1)x3=0 x3=0于是得到于是得到C3(x)=x4+x2+x+12、循環(huán)碼的構(gòu)造、循環(huán)碼的構(gòu)造對(duì)應(yīng)碼字為對(duì)應(yīng)碼字為C3=(0010111)以此類推，可以得到其他碼字。以此類推，可以得到其他碼字。 2、循環(huán)碼的構(gòu)造、循環(huán)碼的構(gòu)造多項(xiàng)式xn+1總是可以分解為兩個(gè)多項(xiàng)式之積:xn+1=g(x)h(x)其中，g(x)表示(n，k)循環(huán)碼的生成多項(xiàng)式，而h(x)則為校驗(yàn)多項(xiàng)式，其階數(shù)為k。

43、所以使用h(x)可以產(chǎn)生相應(yīng)的對(duì)偶碼。 定義h(x)的倒數(shù)多項(xiàng)式為：xkh(x-1)=xk(x-k+hk-1x-k+1+hk-2x-k+ + + 2h1x-1+1) =1+hk-1x+hk-2x2+h1xk-1+xk3、循環(huán)碼的生成矩陣、循環(huán)碼的生成矩陣l定理定理：(n(n，k)k)循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣G G由由g(x)g(x)唯一確定，其唯一確定，其第一行對(duì)應(yīng)于第一行對(duì)應(yīng)于g(x)g(x)的系數(shù)，第二行對(duì)應(yīng)于的系數(shù)，第二行對(duì)應(yīng)于xg(x)xg(x)的系數(shù)的系數(shù)，第，第k k行對(duì)應(yīng)于行對(duì)應(yīng)于 的系數(shù)。的系數(shù)。lG Gk k* *n n：k k行行n n列，則列，則l生成的循環(huán)碼碼字

44、：生成的循環(huán)碼碼字：C=mGC=mG)(1xgxknkrrrggggggggG10010000000000k-1k-1個(gè)個(gè)r+1r+1個(gè)個(gè)1322102210.)(.)(rrrrxgxgxgxgxxgxgxgxggxg多項(xiàng)式xn+1總是可以分解為兩個(gè)多項(xiàng)式之積:xn+1=g(x)h(x)其中，g(x)表示(n，k)循環(huán)碼的生成多項(xiàng)式，而h(x)則為校驗(yàn)多項(xiàng)式，其階數(shù)為k。 所以使用h(x)可以產(chǎn)生相應(yīng)的對(duì)偶碼。 定義h(x)的倒數(shù)多項(xiàng)式為：xkh(x-1)=xk(x-k+hk-1x-k+1+hk-2x-k+ + + 2h1x-1+1) =1+hk-1x+hk-2x2+h1xk-1+xk3、循環(huán)

45、碼的生成矩陣、循環(huán)碼的生成矩陣?yán)呵蠖M(jìn)制例：求二進(jìn)制(7(7，4)4)循環(huán)碼的循環(huán)碼的l（1）生成矩陣。l解解：（：（1 1）設(shè)選設(shè)選 ，g(x)g(x)按升冪按升冪排列：則排列：則G Gk k* *n n=G=G4 4* *7 7為為l（2 2）求輸入消息）求輸入消息m=1001m=1001時(shí)的輸出碼字時(shí)的輸出碼字: : 解：解：C=mG C=mG 代入得代入得c=1010011c=1010011 321)(xxxg110100001101000011010000110174G其中，g(x)表示(n，k)循環(huán)碼的生成多項(xiàng)式，而h(x)則為校驗(yàn)多項(xiàng)式，其階數(shù)為k。 所以使用h(x)可以產(chǎn)生相

46、應(yīng)的對(duì)偶碼。 定義h(x)的倒數(shù)多項(xiàng)式為：xkh(x-1)=xk(x-k+hk-1x-k+1+hk-2x-k+ + + 2h1x-1+1) =1+hk-1x+hk-2x2+h1xk-1+xk3、循環(huán)碼的生成矩陣、循環(huán)碼的生成矩陣l(3)(3)若已知消息多項(xiàng)式若已知消息多項(xiàng)式m(x)=1+xm(x)=1+x3 3，求該（，求該（7 7，4 4）循環(huán)碼的輸出碼字：）循環(huán)碼的輸出碼字： c(x)= m(x)g(x)c(x)= m(x)g(x) 得得c(x)=(1+xc(x)=(1+x3 3)(1+x)(1+x2 2+x+x3 3) ) =1+x =1+x2 2+x+x5 5+x+x6 6 所以所以c

47、=1010011c=1010011例：求二進(jìn)制例：求二進(jìn)制(7(7，4)4)循環(huán)碼的循環(huán)碼的4、循環(huán)碼的校驗(yàn)矩陣l循環(huán)碼的循環(huán)碼的校驗(yàn)多項(xiàng)式校驗(yàn)多項(xiàng)式h(x) h(x) l(n,k)(n,k)循環(huán)碼的校驗(yàn)多項(xiàng)式循環(huán)碼的校驗(yàn)多項(xiàng)式h(x)h(x)定義為：定義為： l由于循環(huán)碼是線性分組碼，因此滿足由于循環(huán)碼是線性分組碼，因此滿足CHCHT T=0=0l同理循環(huán)碼滿足：同理循環(huán)碼滿足：c(x)h(x)=0c(x)h(x)=0。 kkkrnxhxhhxhxxhxxgxgxxh10)(1)(1)()(/ ) 1()(記作，4、循環(huán)碼的校驗(yàn)矩陣654326534332323432423332424332

48、323323711)1)(1 ()()6 , 7()1 ()()3(11)1)(1 ()()4 , 7()1 ()()2(11)1)(1 ()()4 , 7()1 ()() 1 ()1)(1)(1 (1xxxxxxxxxxxxxxxxxxxhxxgxxxxxxxxxxxxhxxxgxxxxxxxxxxxxhxxxgxxxxxx 則它的校驗(yàn)多項(xiàng)式為循環(huán)碼的生成多項(xiàng)式作為若選則它的校驗(yàn)多項(xiàng)式為循環(huán)碼的生成多項(xiàng)式作為若選則它的校驗(yàn)多項(xiàng)式為循環(huán)碼的生成多項(xiàng)式作為若選例：4、循環(huán)碼的校驗(yàn)矩陣l校驗(yàn)矩陣校驗(yàn)矩陣H Hr r* *n n：將：將h(x)h(x)的系數(shù)按的系數(shù)按冪次的降序冪次的降序排列：作為矩

49、陣的第一行；將第一行向右移排列：作為矩陣的第一行；將第一行向右移一位作為一位作為G G的第二行；的第二行；。則。則l由于是循環(huán)碼是線性的，因此滿足：由于是循環(huán)碼是線性的，因此滿足：GHGHT T=0=00001000000000hhhhhhhHkkkknrr-1r-1個(gè)個(gè)k+1k+1個(gè)個(gè)1322102210.)(.)(kkkkxhxhxhxhxxhxhxhxhhxh4、循環(huán)碼的校驗(yàn)矩陣l例：求二進(jìn)制（7，4）循環(huán)碼的校驗(yàn)矩陣73432101110001011100010111H11101)(1)(列行，對(duì)應(yīng)的校驗(yàn)矩陣為按降冪排列：選nrxhxxxxh5、系統(tǒng)循環(huán)碼l（n,k）循環(huán)碼為系統(tǒng)碼l已

50、知待發(fā)送的消息為：已知待發(fā)送的消息為：m=(mm=(m0 0m m1 1m mk-1k-1) )，則則l分析：系統(tǒng)循環(huán)碼分析：系統(tǒng)循環(huán)碼C=(C=(校驗(yàn)位，信息位校驗(yàn)位，信息位) ) l思路：將思路：將k k位信息位整體向右移位位信息位整體向右移位r r位，再加上位，再加上校驗(yàn)位。校驗(yàn)位。l按照以上思路可得按照以上思路可得系統(tǒng)循環(huán)碼的碼多項(xiàng)式系統(tǒng)循環(huán)碼的碼多項(xiàng)式為為1110)(kkxmxmmxm消息多項(xiàng)式：)(mod)()()()()(xgxmxxpxpxmxxcrr其中：80例：求輸入消息例：求輸入消息m=1001m=1001時(shí)的（時(shí)的（7 7，4 4）系）系統(tǒng)循環(huán)碼碼字統(tǒng)循環(huán)碼碼字l解：3

51、1)(xxm消息多項(xiàng)式：233323( )( )( )( )( )mod ( )7,4( )1( )(1)mod(1)11100001001 1101101001rrc xx m xp xp xx m xg xg xxxp xxxxxxpc 系統(tǒng)循環(huán)碼其中：設(shè)選擇（）循環(huán)碼的則系統(tǒng)循環(huán)碼碼字先將先將m右移右移r位位(此題此題r=3)，再加上，再加上p(x)對(duì)對(duì)應(yīng)的校驗(yàn)碼應(yīng)的校驗(yàn)碼p注意校驗(yàn)位的位注意校驗(yàn)位的位數(shù)，不足的補(bǔ)數(shù)，不足的補(bǔ)0系統(tǒng)循環(huán)碼的生成矩陣81l系統(tǒng)循環(huán)碼碼字系統(tǒng)循環(huán)碼碼字的第二種求法：的第二種求法：c=mGc=mGs sl生成矩陣生成矩陣G Gs s 又有兩種求法：又有兩種求法

52、：l求法求法1 1：由：由g(x)g(x)GG 初等行變換初等行變換Gs Gs l求法求法2 2： 的系數(shù)：余式行：的第的系數(shù)：余式行：的第的系數(shù)：余式行：的第即，矩陣的各行：求余得的各位拆開分別對(duì)將)()(mod)()()(mod)(2)()(mod)(1)()(,1111110001110 xpxgxxxpkQxpxgxxxpQxpxgxxxpQQxgmxmxmmxmIQGkkrkrrkknkkrks82系統(tǒng)循環(huán)碼的一致校驗(yàn)矩陣l系統(tǒng)循環(huán)碼的一致校驗(yàn)矩陣Hsl例：已知二進(jìn)制（7，4）循環(huán)碼，求l（1 1）求系統(tǒng)生成矩陣）求系統(tǒng)生成矩陣l（2 2）輸入消息）輸入消息m=1001m=1001時(shí)

53、的輸出的系統(tǒng)循環(huán)碼碼時(shí)的輸出的系統(tǒng)循環(huán)碼碼字字 l（3 3）求一致校驗(yàn)矩陣）求一致校驗(yàn)矩陣nrTrsQIH,l解：（解：（1 1）選）選g(x)=1+x+xg(x)=1+x+x3 3可得生成矩陣可得生成矩陣G:G: 由于是求系統(tǒng)循環(huán)碼的生成矩陣，則矩陣由于是求系統(tǒng)循環(huán)碼的生成矩陣，則矩陣中必含有中必含有I I4 4的單位陣，而直接求得的的單位陣，而直接求得的G G中不含單中不含單位陣，所以它不是系統(tǒng)循環(huán)碼的位陣，所以它不是系統(tǒng)循環(huán)碼的G G。 需求系統(tǒng)循環(huán)碼的需求系統(tǒng)循環(huán)碼的GsGs：101100001011000010110000101174G系統(tǒng)循環(huán)碼的一致校驗(yàn)矩陣l通過初等行變換得系統(tǒng)循

54、環(huán)碼的生成矩陣通過初等行變換得系統(tǒng)循環(huán)碼的生成矩陣GsGs1000101010011100101100001011,ksIQG（2 2）因此：）因此： m m的系統(tǒng)循環(huán)碼為的系統(tǒng)循環(huán)碼為c=mGc=mGs s 代入代入m=1001m=1001得得 C=0111001C=0111001系統(tǒng)循環(huán)碼的一致校驗(yàn)矩陣l（3 3）一致校驗(yàn)矩陣）一致校驗(yàn)矩陣111010001110101101001,3TTrsQIQIH系統(tǒng)循環(huán)碼的一致校驗(yàn)矩陣l（4 4）生成的）生成的系統(tǒng)循環(huán)碼字系統(tǒng)循環(huán)碼字集合：集合： C=mGC=mGS SmC=mGS0001101000100101110010001101000110100011010001011100101111111111111000101010011100101100001011SG由由于于所所以以系統(tǒng)循環(huán)碼的一致校驗(yàn)矩陣5.4 卷積碼概念圖（3，1，2）卷積碼編碼器 當(dāng)輸入信息元為mi時(shí)， D0、D1中分別存放著此前輸入的mj1和mj2， 經(jīng)運(yùn)算可得到兩個(gè)校驗(yàn)元p