第五章糾錯編碼

1、第五章 糾錯編碼1第五章第五章 糾錯編碼糾錯編碼5.1 5.1 糾錯編碼的基本概念糾錯編碼的基本概念5.2 5.2 線性分組碼線性分組碼5.35.3 循環(huán)碼循環(huán)碼5.4 5.4 卷積碼卷積碼 25.1 糾錯編碼的基本概念糾錯編碼的基本概念5.1.1 5.1.1 糾錯編碼的任務(wù)糾錯編碼的任務(wù)5.1.2 5.1.2 糾錯編碼的分類糾錯編碼的分類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ù)字信號提高數(shù)字信號l將信源的模擬信號轉(zhuǎn)變?yōu)閿?shù)字信號將信源的模擬信號轉(zhuǎn)變?yōu)閿?shù)字信號

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

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

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

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

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

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

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

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

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

11、不同的譯碼規(guī)則會引起不同的可靠程度。5.1.3譯碼準(zhǔn)則27 最小錯誤譯碼準(zhǔn)則（最小錯誤譯碼準(zhǔn)則（MEPD） 最大后驗概率準(zhǔ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，信道輸入等概時，MLD和MJPD等價5.1.4香農(nóng)第二定理285.1.4香農(nóng)第二定理29表述二：表述二：設(shè)離散無記憶信道的信道容量

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

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

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

15、碼C和和C中，對應(yīng)位碼元不同的取中，對應(yīng)位碼元不同的取值個數(shù)。值個數(shù)。最小漢明距離最小漢明距離：碼集中所有碼字距離的最小值。：碼集中所有碼字距離的最小值。0min( )dw c5.2 線性分組碼355.2.2 線性分組碼的編碼線性分組碼的編碼一、生成矩陣一、生成矩陣 G 中每一行 gi = ( gi 1, gi 2, , gi n ) 都是一個碼字；l生成矩陣的定義生成矩陣的定義：由于矩陣 G 生成了 (n,k) 線性碼中的任何一個碼字，稱矩陣 G 為 (n,k) 線性碼的生成矩陣。l(n,k) 線性碼的每一個碼字都是生成矩陣 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 位為校驗位為校驗字，這種信息數(shù)字在前校驗數(shù)字在后的線性分組碼字，這種信息數(shù)字在前校驗

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

18、” ”的元素相對應(yīng)的的元素相對應(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時時 , 寫出其對應(yīng)的輸出碼字

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

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

21、方程，它表示與該行中陣的每一行都代表一個校驗方程，它表示與該行中“1”相對應(yīng)的碼元的模相對應(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生成矩陣與一致校驗矩陣的關(guān)系生成矩陣與一致校驗矩陣的關(guān)系:l由于生成矩陣由于生成矩陣GG的每一行都是一個碼字，所以的每一行都是一個碼字，所以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 個碼矢排成一行，作為個碼矢排成一行，作為標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列的

23、第一行，并將的第一行，并將全全0碼矢碼矢C C1=(000)放在最左面的位置上；放在最左面的位置上；l然后在剩下的然后在剩下的 (2n2k) 個個 n 重中選取一個重量最輕的重中選取一個重量最輕的 n 重重 E E2 放在全放在全0碼矢碼矢 C C1 下面，再將下面，再將 E E2 分別和碼矢分別和碼矢 相加，放在對應(yīng)碼矢下面，構(gòu)成陣列第二行；相加，放在對應(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 個個 n 重中任一個重中任一個

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

26、驗子校驗子：S S=R R HHT或或S ST=HH R RT。l如何糾錯？如何糾錯？l設(shè)發(fā)送碼矢 C=(Cn1,Cn2,C0)l信道錯誤圖樣為 E=(En1,En2,E0) ，l其中其中Ei=0，表示第，表示第i位無錯；位無錯；lEi=1，表示第，表示第i位有錯。位有錯。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)行檢驗）求接收碼字的伴隨式（接收碼字用監(jiān)督矩陣進(jì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伴隨式僅與錯誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅與錯誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅由錯誤圖樣決定；伴隨式僅由錯誤圖樣決定；l伴隨式是錯誤的判別式：伴隨式是錯誤的判別式：l若S=0，則判為沒有出錯，接收碼字是一個碼字；l若S0，則判為有錯。l不同的錯誤圖樣具有不同的伴隨式，它們是一一對

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

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

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

31、4 漢明碼 對于給定的正整數(shù)m3，二進(jìn)制漢明碼的信息位數(shù)量、 碼字長度與m之間滿足下列關(guān)系:k=2mm1 n=2n-k1所以漢明碼實際就是(2m1，2mm1)分組碼。 當(dāng)m=3時，則為(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列，列，得到校驗矩陣為得到校驗矩陣為575.2.4 漢明碼011110010110101101001H于是得到生成矩陣為于是得到生成矩陣為1000011010010100101100001111G585.3 循環(huán)碼5.3.1 循環(huán)碼的基本概念循環(huán)碼的基本概念數(shù)學(xué)定義數(shù)學(xué)定義：設(shè)：設(shè)C為某為某( n, k )線性分組碼的碼組集合，如果對線性分組碼的碼組集合，如果對C中任中任意一個碼組意一個碼組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)碼組集合中的一個碼組為循環(huán)碼組集合中的一個碼組為( 1000101 )，向左，向左循環(huán)移位一次后的碼組循環(huán)移位一次后的碼組( 0001011 )仍為碼組集合中第一個許用仍為碼組集合中第一個許用碼組碼組595.3 循環(huán)碼605.3 循環(huán)碼615.3.2 循環(huán)碼的描述循環(huán)碼的描述 1、循環(huán)碼多項式描述、循環(huán)碼多項式描述621、循環(huán)碼多項式描述、循環(huán)碼多項式描述碼多項式的模運算碼多項式的模運算正整數(shù)的模運算正整

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

35、且有且有 即：除到余式的次數(shù)小于除式為止，當(dāng)能整除時即：除到余式的次數(shù)小于除式為止，當(dāng)能整除時次數(shù)為次數(shù)為00 MRQRNNN) mod，記模( NNRM為( )( ) ( )( )a xQ x p xr x)(mod )()(xpxrxa0deg ( )deg( ) r xp x63定理：對于( n, k )循環(huán)碼，若c(x)對應(yīng)碼組c = (an-1an-2 a1a0 )， c(1)的一次循環(huán)移位c(1) = ( an-2an-3 a1a0 an-1 )及c(i )(x)對應(yīng)的c碼循環(huán)移位i次c(i )，則有：證明：碼組c的多項式為：則有：(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)碼多項式描述、循環(huán)碼多項式描述碼多項式的模運算碼多項式的模運算1、循環(huán)碼多項式描述、循環(huán)碼多項式描述碼多項式的模運算碼多項式的模運算例如例如：(7 , 4)循環(huán)碼的第循環(huán)碼的第12個碼組個碼組c12為：為：1011000，則其碼多

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

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

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

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

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

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

43、所以使用h(x)可以產(chǎn)生相應(yīng)的對偶碼。 定義h(x)的倒數(shù)多項式為：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)唯一確定，其唯一確定，其第一行對應(yīng)于第一行對應(yīng)于g(x)g(x)的系數(shù)，第二行對應(yīng)于的系數(shù)，第二行對應(yīng)于xg(x)xg(x)的系數(shù)的系數(shù)，第，第k k行對應(yīng)于行對應(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個個r+1r+1個個1322102210.)(.)(rrrrxgxgxgxgxxgxgxgxggxg多項式xn+1總是可以分解為兩個多項式之積:xn+1=g(x)h(x)其中，g(x)表示(n，k)循環(huán)碼的生成多項式，而h(x)則為校驗多項式，其階數(shù)為k。 所以使用h(x)可以產(chǎn)生相應(yīng)的對偶碼。 定義h(x)的倒數(shù)多項式為：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時的輸出碼字時的輸出碼字: : 解：解：C=mG C=mG 代入得代入得c=1010011c=1010011 321)(xxxg110100001101000011010000110174G其中，g(x)表示(n，k)循環(huán)碼的生成多項式，而h(x)則為校驗多項式，其階數(shù)為k。 所以使用h(x)可以產(chǎn)生相

46、應(yīng)的對偶碼。 定義h(x)的倒數(shù)多項式為：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)若已知消息多項式若已知消息多項式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)碼的校驗矩陣l循環(huán)碼的循環(huán)碼的校驗多項式校驗多項式h(x) h(x) l(n,k)(n,k)循環(huán)碼的校驗多項式循環(huán)碼的校驗多項式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)碼的校驗矩陣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 則它的校驗多項式為循環(huán)碼的生成多項式作為若選則它的校驗多項式為循環(huán)碼的生成多項式作為若選則它的校驗多項式為循環(huán)碼的生成多項式作為若選例：4、循環(huán)碼的校驗矩陣l校驗矩陣校驗矩陣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個個k+1k+1個個1322102210.)(.)(kkkkxhxhxhxhxxhxhxhxhhxh4、循環(huán)碼的校驗矩陣l例：求二進(jìn)制（7，4）循環(huán)碼的校驗矩陣73432101110001011100010111H11101)(1)(列行，對應(yīng)的校驗矩陣為按降冪排列：選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=(校驗位，信息位校驗位，信息位) ) l思路：將思路：將k k位信息位整體向右移位位信息位整體向右移位r r位，再加上位，再加上校驗位。校驗位。l按照以上思路可得按照以上思路可得系統(tǒng)循環(huán)碼的碼多項式系統(tǒng)循環(huán)碼的碼多項式為為1110)(kkxmxmmxm消息多項式：)(mod)()()()()(xgxmxxpxpxmxxcrr其中：80例：求輸入消息例：求輸入消息m=1001m=1001時的（時的（7 7，4 4）系）系統(tǒng)循環(huán)碼碼字統(tǒng)循環(huán)碼碼字l解：3

51、1)(xxm消息多項式：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)對對應(yīng)的校驗碼應(yīng)的校驗碼p注意校驗位的位注意校驗位的位數(shù)，不足的補數(shù)，不足的補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ù)：余式行：的第即，矩陣的各行：求余得的各位拆開分別對將)()(mod)()()(mod)(2)()(mod)(1)()(,1111110001110 xpxgxxxpkQxpxgxxxpQxpxgxxxpQQxgmxmxmmxmIQGkkrkrrkknkkrks82系統(tǒng)循環(huán)碼的一致校驗矩陣l系統(tǒng)循環(huán)碼的一致校驗矩陣Hsl例：已知二進(jìn)制（7，4）循環(huán)碼，求l（1 1）求系統(tǒng)生成矩陣）求系統(tǒng)生成矩陣l（2 2）輸入消息）輸入消息m=1001m=1001時

53、的輸出的系統(tǒng)循環(huán)碼碼時的輸出的系統(tǒng)循環(huán)碼碼字字 l（3 3）求一致校驗矩陣）求一致校驗矩陣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)碼的一致校驗矩陣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)碼的一致校驗矩陣l（3 3）一致校驗矩陣）一致校驗矩陣111010001110101101001,3TTrsQIQIH系統(tǒng)循環(huán)碼的一致校驗矩陣l（4 4）生成的）生成的系統(tǒng)循環(huán)碼字系統(tǒng)循環(huán)碼字集合：集合： C=mGC=mGS SmC=mGS0001101000100101110010001101000110100011010001011100101111111111111000101010011100101100001011SG由由于于所所以以系統(tǒng)循環(huán)碼的一致校驗矩陣5.4 卷積碼概念圖（3，1，2）卷積碼編碼器 當(dāng)輸入信息元為mi時， D0、D1中分別存放著此前輸入的mj1和mj2， 經(jīng)運算可得到兩個校驗元p