第五章糾錯編碼

1、第五章 糾錯編碼 1 第五章第五章 糾錯編碼糾錯編碼 5.1 5.1 糾錯編碼的基本概念糾錯編碼的基本概念 5.2 5.2 線性分組碼線性分組碼 5.35.3 循環(huán)碼循環(huán)碼 5.4 5.4 卷積碼卷積碼 2 5.1 糾錯編碼的基本概念糾錯編碼的基本概念 5.1.1 5.1.1 糾錯編碼的任務糾錯編碼的任務 5.1.2 5.1.2 糾錯編碼的分類糾錯編碼的分類 5.1.35.1.3 譯碼準則譯碼準則 5.1.4 5.1.4 香農(nóng)第二定理香農(nóng)第二定理 3 4 5.1 信道編碼的任務信道編碼的任務 5.1 信道編碼信道編碼 5 l信源編碼信源編碼 l提高數(shù)字信號提高數(shù)字信號 l將信源的模擬信號轉變?yōu)?/p>

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

3、進行傳輸。（或碼字），再經(jīng)信道進行傳輸。（提高傳輸?shù)目煽啃裕ㄌ岣邆鬏數(shù)目煽啃裕?信道譯碼信道譯碼：就是按與編碼器同樣的數(shù)學規(guī)律去掉接：就是按與編碼器同樣的數(shù)學規(guī)律去掉接 收序列中的冗余符號收序列中的冗余符號, , 恢復信源消息序列?；謴托旁聪⑿蛄?。 一般地說，所加的冗余符號越多，糾錯能力就越強，一般地說，所加的冗余符號越多，糾錯能力就越強， 但傳輸效率降低。因此在信道編碼中明顯體現(xiàn)了傳輸有但傳輸效率降低。因此在信道編碼中明顯體現(xiàn)了傳輸有 效性與可靠性的矛盾。效性與可靠性的矛盾。 編碼信道模型編碼信道模型 7 011 011 ,0,1 , , 0,1 ni ni cc ccc Rr rrr

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

5、法運算， 于是有 ECR 例如:C=10000,E=01000,R=? R=(11000) 10 5.1 信道編碼的任務信道編碼的任務 10 檢錯與糾錯原理檢錯與糾錯原理 l0:晴,1:雨 l若10,01。收端無法發(fā)現(xiàn)錯誤 00晴 10 01 11 00 11雨 能發(fā)現(xiàn) 一個錯誤 禁用碼組 插入1位監(jiān)督碼后具有檢出1位錯碼的能 力,但不能予以糾正。 11 5.1 信道編碼的任務信道編碼的任務 11 000晴 010 001 111 000 111雨 晴 在只有1位錯碼的情況下,可以判決哪位是錯碼 并予以糾正,可以檢檢出2位或2位以下的錯碼。 100 011 101 110 雨 檢錯和糾錯方式檢

6、錯和糾錯方式 12 l自動請求重發(fā)(ARQ)： l發(fā)端發(fā)送檢錯碼， l收端譯碼器判斷當前碼字傳輸是否出錯； l當有錯時按某種協(xié)議通過一個反向信道請求 發(fā)送端重傳已發(fā)送的碼字(全部或部分)。 優(yōu)點：優(yōu)點： 編譯碼設備比較簡單。 在一定的多余度碼元下，系統(tǒng)具有極強的糾 錯能力。 能獲得極低的誤碼率。 由于檢錯碼的檢錯能 力與信道干擾的變化基本無關，因此這種系統(tǒng)的適 應性很強，特別適應于短波、 散射、 有線等干擾 情況特別復雜的信道中。 ARQ 缺點：缺點： 控制電路比較復雜。 傳送消息的連貫性和實時性較差。由于反饋 重發(fā)的次數(shù)與信道干擾情況有關，若信道干擾很 頻繁，則信道經(jīng)常處于重發(fā)消息的狀態(tài)。

7、ARQ 檢錯和糾錯方式檢錯和糾錯方式 l前向糾錯(FEC)： l發(fā)送端的信道編碼器將信息碼組編成具有一 定糾錯能力的碼。 l接收端信道譯碼器對接收碼字進行譯碼,若傳 輸中產(chǎn)生的差錯數(shù)目在碼的糾錯能力之內(nèi)時, 譯碼器對差錯進行定位并加以糾正。 優(yōu)點：優(yōu)點： 不需要反饋信道，能夠?qū)崿F(xiàn)一對多的同步廣播 通信，而且譯碼實時性好，控制電路也比ARQ簡單。 隨著編碼理論的發(fā)展和大規(guī)模集成技術的發(fā)展，復 雜算法的譯碼設備越來越簡單，成本越來越低，所 以這種方式在實際中得到越來越廣泛的應用。 FEC 缺點：缺點： 這種工作方式是假設糾錯碼的糾錯能力足夠糾 正信息序列傳輸中的錯誤，也就是糾錯碼與信道的 干擾是相

8、匹配的，所以對信道的適應性較差。 為了 獲得合適的誤碼率，往往按照信道最差的情況設計 糾錯碼，增加的冗余碼元比檢錯碼要多，編碼效率 一般較低。 FEC 檢錯和糾錯方式檢錯和糾錯方式 l混合糾錯混合糾錯(HEC)： l是是FEC與與ARQ方式的結合。方式的結合。 l發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼 組組,收端收到碼組后收端收到碼組后,檢查差錯情況檢查差錯情況,如果差錯在如果差錯在 碼的糾錯能力以內(nèi)碼的糾錯能力以內(nèi),則自動進行糾正。則自動進行糾正。 l如果信道干擾很嚴重如果信道干擾很嚴重,錯誤很多錯誤很多,超過了碼的糾超過了碼的糾 錯能力錯能力,但能檢測

9、出來但能檢測出來,則經(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ù),從而發(fā)現(xiàn)錯誤從而發(fā)現(xiàn)錯誤,并且把錯誤的消息再次傳送并且把錯誤的消息再次傳送, 直到發(fā)端沒有發(fā)現(xiàn)錯誤為止。直到發(fā)端沒有發(fā)現(xiàn)錯誤為止。 優(yōu)點：優(yōu)點： 由于該方式避免了FEC要求的復雜設備和ARQ 方式的信息連貫性差的缺點，并且可以達到較低的 誤碼率，因此在實際中得到了廣泛應用。 HEC 總結：信道編碼的概念 l目

10、的：降低錯誤的譯碼概率PE l對象：信息序列 l方法：信息碼+附加碼元，收端按照一定 譯碼準則檢糾錯。 l實質(zhì)：增加冗余度。 20 5.1.2 信道（糾錯）編碼的分類 l按照接收端工作狀態(tài)分為： 檢錯碼 糾錯碼 糾刪碼 l根據(jù)糾正錯誤的類型 糾隨機錯誤碼 糾突發(fā)錯誤碼 21 22 5.1.2 信道（糾錯）編碼的分類 22 l隨機差錯： l差錯是相互獨立的,不相關 l存在這種差錯的信道是無記憶信道或隨機信道 l突發(fā)差錯： l指成串出現(xià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

11、0 突發(fā)長度= 4 突發(fā)長度= 6 5.1.2 信道（糾錯）編碼的分類 l按照發(fā)送端編碼方式分為： 23 5.1.3譯碼準則 24 5.1.3譯碼準則 25 ),.,2 , 1;,.,2 , 1()(sjriabF ij 5.1.3譯碼準則 26 （1）對輸入符號集為X=a1,a2,ar，輸出符號集 為Y= b1,b2,bs的信道來說，一共可構成rs種不 同的譯碼規(guī)則。 不同的譯碼規(guī)則會引起不同的可靠程度。 5.1.3譯碼準則 27 最小錯誤譯碼準則（最小錯誤譯碼準則（MEPD） 最大后驗概率準則（最大后驗概率準則（MPPD） 最大聯(lián)合概率準則（最大聯(lián)合概率準則（MJPD） 最大似然概率準則（

12、最大似然概率準則（MLD） ()()()i jjji F bap b ap b a ，（ =1.r） ()()()i jjij F bap a bp ab ，（ =1.r） ()()()i jjij F bap a bp a b ，（ =1.r） ()min jE F baP， 信道輸入等概時，MLD和MJPD 等價 5.1.4香農(nóng)第二定理 28 5.1.4香農(nóng)第二定理 29 表述二：表述二：設離散無記憶信道的信道容量為C， 信息傳輸率為R，對于任意小的正數(shù)，當Rk) 碼字，其中 (nk) 個附加碼元 是由信息碼元的線性運算產(chǎn)生的。 l信息碼組長信息碼組長 k 位，有位，有 2k 個不同的信息

13、碼組，則應該有個不同的信息碼組，則應該有 2k 個碼字與它們一一對應。個碼字與它們一一對應。 5.2.1 線性分組碼的基本概念線性分組碼的基本概念 5.2 線性分組碼 32 5.2.1 線性分組碼的基本概念線性分組碼的基本概念 l線性分組碼線性分組碼：通過預定的線性運算將長為：通過預定的線性運算將長為 k 位的信位的信 息碼組變換成息碼組變換成 n 長的碼字長的碼字 ( nk )。由。由 2k 個信息碼組個信息碼組 所編成的所編成的 2k個碼字集合，稱為個碼字集合，稱為線性分組碼線性分組碼。 l碼矢碼矢：一個：一個 n 長的碼字可以用矢量來表示長的碼字可以用矢量來表示 C C = (Cn 1,

14、Cn2,C1,C0 ) 所以碼字又稱為碼矢。所以碼字又稱為碼矢。 l( n, k ) 線性碼線性碼：信息位長為：信息位長為 k，碼長為，碼長為 n 的線性碼的線性碼 l編碼效率編碼效率/編碼速率編碼速率/碼率：碼率：R=k /n。它說明了信道的。它說明了信道的 利用效率，利用效率，R是衡量碼性能的一個重要參數(shù)是衡量碼性能的一個重要參數(shù)。 5.2 線性分組碼 33 5.2.1 線性分組碼的基本概念線性分組碼的基本概念 線性體現(xiàn)在線性體現(xiàn)在： 輸入輸出的關系為線性映射關系輸入輸出的關系為線性映射關系 碼元中每個碼字由信源做模二加運算得到碼元中每個碼字由信源做模二加運算得到 線性分組碼的特點線性分組

15、碼的特點： 在碼集中存在全在碼集中存在全0碼字碼字 滿足封閉性滿足封閉性 5.2 線性分組碼 34 5.2.1 線性分組碼的基本概念線性分組碼的基本概念 定理定理：線性分組碼的最小距離等于最小非零碼字重量。：線性分組碼的最小距離等于最小非零碼字重量。 定理中涉及到的基本概念定理中涉及到的基本概念 漢明重量漢明重量：碼字中非：碼字中非0碼的個數(shù)。碼的個數(shù)。 最小漢明重量最小漢明重量：碼集中非：碼集中非0碼字漢明重量的最小值。碼字漢明重量的最小值。 漢明距離漢明距離：兩個等長碼：兩個等長碼C和和C中，對應位碼元不同的取中，對應位碼元不同的取 值個數(shù)。值個數(shù)。 最小漢明距離最小漢明距離：碼集中所有碼

16、字距離的最小值。：碼集中所有碼字距離的最小值。 0 min( )dw c 5.2 線性分組碼 35 5.2.2 線性分組碼的編碼線性分組碼的編碼 一、生成矩陣一、生成矩陣 G 中每一行 gi = ( gi 1, gi 2, , gi n ) 都是一個碼字； l生成矩陣的定義生成矩陣的定義：由于矩陣 G 生成了 (n,k) 線性碼中的 任何一個碼字，稱矩陣 G 為 (n,k) 線性碼的生成矩陣。 l(n,k) 線性碼的每一個碼字都是生成矩陣 G 的行的線性 組合。 cmG 5.2 線性分組碼 36 5.2.2 線性分組碼的編碼線性分組碼的編碼 一、生成矩陣一、生成矩陣 l標準生成矩陣：標準生成矩

17、陣： 通過行初等變換，將 G 化為前 k 行和k 列是單位子 陣的標準形式標準形式 11121() 21222() 12() 100 010 GIQ 001 n k n k k nkk r kkk n k qqq qqq qqq 5.2 線性分組碼 37 5.2.2 線性分組碼的編碼線性分組碼的編碼 二、編碼二、編碼 l線性系統(tǒng)分組碼線性系統(tǒng)分組碼：用標準生成矩陣用標準生成矩陣 GGk n 編成的碼 編成的碼 字，前面字，前面 k 位為信息數(shù)字，后面位為信息數(shù)字，后面 r=nk 位為校驗位為校驗 字，這種信息數(shù)字在前校驗數(shù)字在后的線性分組碼字，這種信息數(shù)字在前校驗數(shù)字在后的線性分組碼 稱為線性

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

19、對應的的元素相對應的 行按位模行按位模 2 2 加的結果。加的結果。 5.2.2 線性分組碼的編碼 4 7 1 4 1 71 44 7 1000101 0100111 G 0010110 0001011 m(1010) 1000101 0100111 CmG1010(1010011) 0010110 0001011 39 5.2.2 線性分組碼的編碼 練習：練習： 已知某線性分組碼的生成矩陣為已知某線性分組碼的生成矩陣為 l試問試問： l（1）n = ? k = ? , 該碼組集合中的碼字有多少？該碼組集合中的碼字有多少？ l（2）若信息碼元若信息碼元 m 分別是分別是 1100 和和1111

20、時時 , 寫出其對應的輸出碼字。寫出其對應的輸出碼字。 1000011 0100101 G 0010110 0001111 40 5.2.3 線性分組碼的譯碼 一、一致校驗矩陣一、一致校驗矩陣 l推廣到一般情況：對推廣到一般情況：對 (n,k) 線性分組碼，每個碼字中的線性分組碼，每個碼字中的 r(r=nk) 個監(jiān)督元與信息元之間的關系可由下面的線性個監(jiān)督元與信息元之間的關系可由下面的線性 方程組確定方程組確定 0 0 0 02211 02222121 01212111 ChChCh ChChCh ChChCh rnnrnr nnn nnn 41 5.2.3 線性分組碼的譯碼 一、一致校驗矩陣

21、一、一致校驗矩陣 l令系數(shù)矩陣為令系數(shù)矩陣為 HH，碼字行陣列為，碼字行陣列為 C C 矩陣。線性分組碼的一致監(jiān)督為稱 或 則： ),(H 0HC0CH C H 1111 0211 21 22221 11211 kn CCC hhh hhh hhh r T rnn T r T nnr nnn rnrr n n nr 42 5.2.3 線性分組碼的譯碼 一、一致校驗矩陣特性一、一致校驗矩陣特性: l對對H H 各行實行初等變換，將后面各行實行初等變換，將后面 r 列化為單位子陣，于是列化為單位子陣，于是 得到下面矩陣得到下面矩陣(行變換所得方程組與原方程組同解行變換所得方程組與原方程組同解)。

22、l校驗矩陣校驗矩陣H H 的標準形式的標準形式：后面：后面 r 列是一單位子陣的校驗矩列是一單位子陣的校驗矩 陣陣HH。 lH H 陣的每一行都代表一個校驗方程，它表示與該行中陣的每一行都代表一個校驗方程，它表示與該行中“1” 相對應的碼元的模相對應的碼元的模2和為和為0。 100 010 001 H 21 22221 11211 rnrr k k nr ppp ppp ppp 43 5.2.3 線性分組碼的譯碼 GIQHPI (P) G HIQPIIQ(P)Q0 I GIQ H(Q)I Skk rSr kr T T TTr k SSkk rr krkk rr kk rk r r Skk r

23、T Sk rr 生成矩陣與一致校驗矩陣的關系生成矩陣與一致校驗矩陣的關系: l由于生成矩陣由于生成矩陣GG的每一行都是一個碼字，所以的每一行都是一個碼字，所以G G 的每行都滿的每行都滿 足足HHr nC CTn1=0 0Tr1，則有 ，則有 HHr nG GTn k=0 0Trk 或 或 GGk nH HTn r=0 0kr l線性系統(tǒng)碼的監(jiān)督矩陣線性系統(tǒng)碼的監(jiān)督矩陣 H H 和生成矩陣和生成矩陣 G G 之間可以直接互換之間可以直接互換 。 44 5.2.3 線性分組碼的譯碼 例例: 已知已知(7,4)線性系統(tǒng)碼的監(jiān)督矩陣為線性系統(tǒng)碼的監(jiān)督矩陣為 1101000 0110100 11100

24、10 1010001 G 1001011 0101110 0010111 H )4,7( )4,7( 陣可直接寫出它的生成矩 45 5.2.3 線性分組碼的譯碼標準陣列譯碼 l標準陣列構造方法標準陣列構造方法 l先將先將 2k 個碼矢排成一行，作為個碼矢排成一行，作為標準陣列標準陣列的第一行，并將的第一行，并將 全全0碼矢碼矢C C1=(000)放在最左面的位置上；放在最左面的位置上； l然后在剩下的然后在剩下的 (2n2k) 個個 n 重中選取一個重量最輕的重中選取一個重量最輕的 n 重重 E E2 放在全放在全0碼矢碼矢 C C1 下面，再將下面，再將 E E2 分別和碼矢分別和碼矢 相加

25、，放在對應碼矢下面，構成陣列第二行；相加，放在對應碼矢下面，構成陣列第二行； l在第二次剩下的在第二次剩下的 n 重中，選取重量最輕的重中，選取重量最輕的 n 重重 E E3，放在，放在 E E2 下面，并將下面，并將 E E3 分別加到第一行各碼矢上，得到第三分別加到第一行各碼矢上，得到第三 行；行； l，繼續(xù)這樣做下去，直到全部，繼續(xù)這樣做下去，直到全部 n 重用完為止。得到下重用完為止。得到下 頁表格所示的頁表格所示的 (n,k) 線性碼的標準陣列。線性碼的標準陣列。 46 碼 字 CC1(=0) (陪集 首) CC2 CC E E2 CC2+ E E2 CCi + E E2 E E3

26、CC2+ E E3 CCi + E E3 禁 用 碼 組 5.2.3 線性分組碼的譯碼標準陣列譯碼 47 5.2.3 線性分組碼的譯碼標準陣列譯碼 標準陣列的特性：標準陣列的特性： 定理定理：在標準陣列的同一行中沒有相同的矢量，而且：在標準陣列的同一行中沒有相同的矢量，而且 2n 個個 n 重中任一個重中任一個 n 重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。 L陪集陪集：標準陣列的每一行叫做碼的一個陪集。：標準陣列的每一行叫做碼的一個陪集。 L陪集首陪集首：每個陪集的第一個元素叫做陪集首。：每個陪集的第一個元素叫做陪集首。 48 5.2.3 線性分組碼的譯碼伴隨式譯碼 伴

27、隨式和錯誤檢測：伴隨式和錯誤檢測： l用監(jiān)督矩陣譯碼用監(jiān)督矩陣譯碼：接收到一個碼字：接收到一個碼字 R R 后，檢驗后，檢驗 HH R RT=0 0T 是否成立：是否成立： lHRT =0T是否成立是檢驗碼字出錯與否的依據(jù)。 l若關系成立，則認為 R 是一個碼字； l否則判為碼字在傳輸中發(fā)生了錯誤； l伴隨式伴隨式/監(jiān)督子監(jiān)督子/校驗子校驗子：S S=R R HHT或或S ST=HH R RT。 l如何糾錯？如何糾錯？ l設發(fā)送碼矢 C=(Cn1,Cn2,C0) l信道錯誤圖樣為 E=(En1,En2,E0) ， l其中其中Ei=0，表示第，表示第i位無錯；位無錯； lEi=1，表示第，表示第

28、i位有錯。位有錯。i=n1,n2,0。 49 5.2.3 線性分組碼的譯碼伴隨式譯碼 l接收碼字接收碼字 R R =(Rn 1,Rn2,R0)=C C+E E =(Cn1+En1, Cn2+En2, , C0 +E0) l求接收碼字的伴隨式（接收碼字用監(jiān)督矩陣進行檢驗）求接收碼字的伴隨式（接收碼字用監(jiān)督矩陣進行檢驗） S ST=HH R RT=HH (C C+E E)T=HH C CT+HH E ET l由于由于HH C CT=0 0T，所以，所以 S ST=HH E ET l設設HH=(h h1,h h2,h hn)，其中，其中h hi表示表示HH的列。代入上式得到的列。代入上式得到 50

29、5.2.3 線性分組碼的譯碼伴隨式譯碼 總結總結： l伴隨式僅與錯誤圖樣有關，而與發(fā)送的具體碼字無關，即伴隨式僅與錯誤圖樣有關，而與發(fā)送的具體碼字無關，即 伴隨式僅由錯誤圖樣決定；伴隨式僅由錯誤圖樣決定； l伴隨式是錯誤的判別式：伴隨式是錯誤的判別式： l若S=0，則判為沒有出錯，接收碼字是一個碼字； l若S0，則判為有錯。 l不同的錯誤圖樣具有不同的伴隨式，它們是一一對應的。不同的錯誤圖樣具有不同的伴隨式，它們是一一對應的。 對二元碼，伴隨式對二元碼，伴隨式S是是H H 陣中與錯誤碼元對應列之和陣中與錯誤碼元對應列之和。 51 伴隨式譯碼舉例：伴隨式譯碼舉例： 某某(7,3) 線性系統(tǒng)碼線性

30、系統(tǒng)碼 l設發(fā)送碼字設發(fā)送碼字C C = 1010011，接收碼字，接收碼字R R 1010011 ，R R與與C C相同。相同。 無錯。因此，譯碼器判接收字 代入得和計算伴隨式，把根據(jù)接收字 道就是發(fā)送的碼字，但接收端譯碼器并不知 TTT 0HRS RHR H 1000110 0100011 0010111 0001101 5.2.3 線性分組碼的譯碼伴隨式譯碼 52 l若接收碼字中有一位錯誤若接收碼字中有一位錯誤 正確。錯能力相符，所以譯碼中錯誤碼元數(shù)與碼的糾由于接收字 的第二位是錯的。因此判定接收字 的第二列，等于且碼是糾單個錯誤的碼， 譯碼器判為有錯。由于 伴隨式為 接收碼字發(fā)送碼矢

31、R R HS 0S RHS RC T T TT )3 , 7( , 1 1 1 0 1 1 0 0 1 1 1 1000110 0100011 0010111 0001101 11100111010011 5.2.3 線性分組碼的譯碼伴隨式譯碼 53 5.2.3 線性分組碼的譯碼伴隨式譯碼 l當碼元錯誤多于1個時 位上，只是發(fā)現(xiàn)有錯。無法判定錯誤出在哪些 同，陣中的任何一列都不相但與 ，不等于是第一列和第四列之和由于 伴隨式為 接收碼字發(fā)送碼矢 H 0S RHS RC T TT 0 1 1 0 1 1 0 1 1 0 0 1000110 0100011 0010111 0001101 0011

32、0111010011 54 5.2.3 線性分組碼的譯碼伴隨式譯碼 以上定理是糾錯碼理論中最重要的基本定理之一，它說明了一個距離為d的線 性分組碼，既可用來糾正 個錯誤，又可用來檢測e d1個錯誤。 2 1d t 定理定理 對于任一個（對于任一個（n，k）線性分組碼，若要在碼字內(nèi)線性分組碼，若要在碼字內(nèi) 檢測檢測e個錯誤，則要求碼的最小距離個錯誤，則要求碼的最小距離d e1； 糾正糾正t個錯誤，則要求碼的最小距離個錯誤，則要求碼的最小距離d 2t1； 糾正糾正t個錯誤同時檢測個錯誤同時檢測e（ t）個錯誤，則要求個錯誤，則要求d te1。 55 5.2.4 漢明碼 對于給定的正整數(shù)m3，二進制

33、漢明碼的信息 位數(shù)量、 碼字長度與m之間滿足下列關系: k=2mm1 n=2n-k1 所以漢明碼實際就是(2m1，2mm1)分組碼。 當m=3時，則為(7，4)碼。 二進制漢明碼的最小漢明距離為d0=3。 56 5.2.4 漢明碼 例例 構造構造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)，為，為 了產(chǎn)生系統(tǒng)碼，將了產(chǎn)

34、生系統(tǒng)碼，將(100)，(010)，(001)放在矩陣的最后放在矩陣的最后3列，列， 得到校驗矩陣為得到校驗矩陣為 57 5.2.4 漢明碼 0111100 1011010 1101001 H 于是得到生成矩陣為于是得到生成矩陣為 1000011 0100101 0010110 0001111 G 58 5.3 循環(huán)碼 5.3.1 循環(huán)碼的基本概念循環(huán)碼的基本概念 數(shù)學定義數(shù)學定義：設：設C為某為某( n, k )線性分組碼的碼組集合，如果對線性分組碼的碼組集合，如果對C中任中任 意一個碼組意一個碼組c = ( an-1 an-2 a1 a0 )，它的循環(huán)移位，它的循環(huán)移位c(1) = ( a

35、n-2an-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 )仍為碼組集合中第一個許用仍為碼組集合中第一個許用 碼組碼組 59 5.3 循環(huán)碼 60 5.3 循環(huán)碼 61 5.3.2 循環(huán)碼的描述循環(huán)碼的描述 1、循環(huán)碼多項式描述、循環(huán)碼多項式描述 62 1、循環(huán)碼多項式描述、循環(huán)碼多項式描述碼多項式的模運

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

37、)的余式，在模的余式，在模p(x)運算下運算下 且有且有 即：除到余式的次數(shù)小于除式為止，當能整除時即：除到余式的次數(shù)小于除式為止，當能整除時 次數(shù)為次數(shù)為0 0 MR QRN NN ) mod，記模( NNRM為 ( )( ) ( )( )a xQ x p xr x )(mod )()(xpxrxa 0deg ( )deg( ) r xp x 63 定理：對于( n, k )循環(huán)碼，若c(x)對應碼組c = (an-1an-2 a1a0 )， c(1)的一次 循環(huán)移位c(1) = ( an-2an-3 a1a0 an-1 )及c(i )(x)對應的c碼循環(huán)移位i次c(i )， 則有： 證明：

38、碼組c的多項式為： 則有： (1)( ) mod(1)mod(1) ( )( ),( )( ) nn ii xx cxxc xcxx c x -1-2 1210 ( )() nn nn c xaxaxa xa -121 -2 -121 -1-210 -1-110 1) 1 -1 ( - ( ) (1)( ) n nn nn n n nnn n n xc xaxaxa xa x axa axc aax x xxaa (1) 1 mod(1)mod(1) (1) ( )(1)( ) ( ) nn n n xx xc xaxcx cx 1、循環(huán)碼多項式描述、循環(huán)碼多項式描述碼多項式的模運算碼多項式的

39、模運算 1、循環(huán)碼多項式描述、循環(huán)碼多項式描述碼多項式的模運算碼多項式的模運算 例如例如：(7 , 4)循環(huán)碼的第循環(huán)碼的第12個碼組個碼組c12為：為：1011000，則其碼多項，則其碼多項 式為：式為： c(x)=x6 + x4 + x3 請寫出請寫出c12左循環(huán)移位左循環(huán)移位3次的碼組次的碼組 解：解：i = 3，則，則 x3c(x) = x9 + x7 + x6 其對應碼組為：其對應碼組為：1000101，它是，它是( 7, 4 )循環(huán)碼中的第循環(huán)碼中的第4個碼組個碼組c4 7 362 mod1 ( )1 x x c xxx 2 7976 92 762 7 62 1 1 1 1 x x

40、xxx xx xxx x xx 65 1、循環(huán)碼多項式描述、循環(huán)碼多項式描述生成多項式生成多項式 定義定義：記：記C(x)為為( n, k )循環(huán)碼的所有碼組對應的多項式的集合循環(huán)碼的所有碼組對應的多項式的集合 ，若，若g(x)是是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(

41、x)都是都是g(x)的倍式，且每一個小于的倍式，且每一個小于 等于等于n-1次的次的g(x)的倍式一定是碼多項式；的倍式一定是碼多項式； 3）g(x)的最高次為的最高次為n-k，且是唯一的；，且是唯一的； 4）g(x)是是xn + 1的一個因子的一個因子 生成多項式 66 l例：求(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)碼的生成多項式。 1 7 x )1)(1)(1 (1 3237 xxxxxx 3 1xx 32 1x

42、x 常數(shù)項為常數(shù)項為1 1，最高項為，最高項為3 3次次 （n，k）循環(huán)碼的構造步驟： 對（xn+1）做因式分解，找出其n-k次因式； 以n-k次因式為生成多項式g(x),與信息多項式m(x) 相乘，即得到碼多項式： C(x)=m(x)g(x) 因m(x)不高于（k-1）次，所以C(x)的次數(shù)不 會高于（k-1）+（n-k）=（n-1）次。 2、循環(huán)碼的構造、循環(huán)碼的構造 討論長度討論長度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)碼，可以取下列兩個多項式之一

43、作為生循環(huán)碼，可以取下列兩個多項式之一作為生 成多項式成多項式: g1(x)=x3+x2+1 g2(x)=x3+x+1 其中，其中，g1(x)和和g2(x)產(chǎn)生的碼是等價的。產(chǎn)生的碼是等價的。 2、循環(huán)碼的構造、循環(huán)碼的構造 具體產(chǎn)生過程為：具體產(chǎn)生過程為： 假設假設4比特信息為比特信息為(0001)，對應的信，對應的信 息多項式為息多項式為X1(x)=1，所以碼字多項式為，所以碼字多項式為 C1(x)=m1(x)g1(x)=(x3+x2+1) 對應碼字為對應碼字為 C1=(0001101) 當當4比特信息為比特信息為(0010)時，對應的信息多項式為時，對應的信息多項式為X2(x)=x，碼，

44、碼 字多項式為字多項式為 C2(x)=m2(x)g1(x)=x(x3+x2+1)=x4+x3+x 對應碼字為對應碼字為 C2=(0011010) 2、循環(huán)碼的構造、循環(huán)碼的構造 當當4比特信息為比特信息為(0011)時，對應的信息多項式為時，對應的信息多項式為 m3(x)=x+1，碼字多項式為，碼字多項式為 331 32 4332 ( )( )( ) (1)(1) ()(1) Cxmx gx xxx xxxxx 注意到二進制多項式加法為同階次項的系數(shù)進行半加注意到二進制多項式加法為同階次項的系數(shù)進行半加 運算，所以運算，所以 x3+x3=(1+1)x3=0 x3=0 于是得到于是得到 C3(x

45、)=x4+x2+x+1 2、循環(huán)碼的構造、循環(huán)碼的構造 對應碼字為對應碼字為 C3=(0010111) 以此類推，可以得到其他碼字。以此類推，可以得到其他碼字。 2、循環(huán)碼的構造、循環(huán)碼的構造 多項式xn+1總是可以分解為兩個多項式之積: xn+1=g(x)h(x) 其中，g(x)表示(n，k)循環(huán)碼的生成多項式，而h(x)則 為校驗多項式，其階數(shù)為k。 所以使用h(x)可以產(chǎn)生 相應的對偶碼。 定義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+xk 3、循環(huán)碼的生成矩陣

46、、循環(huán)碼的生成矩陣 l定理定理：(n(n，k)k)循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣G G由由g(x)g(x)唯一確定，其唯一確定，其 第一行對應于第一行對應于g(x)g(x)的系數(shù)，第二行對應于的系數(shù)，第二行對應于xg(x)xg(x)的系數(shù)的系數(shù) ，第，第k k行對應于行對應于 的系數(shù)。的系數(shù)。 lG Gk k* *n n：k k行行n n列，則列，則 l生成的循環(huán)碼碼字：生成的循環(huán)碼碼字：C=mGC=mG )( 1 xgx k nk r r r ggg gg ggg G 10 0 10 000 000 000 k-1k-1個個 r+1r+1個個 13 2 2 10 2 210 .)( .)(

47、 r r r r xgxgxgxgxxg xgxgxggxg 多項式xn+1總是可以分解為兩個多項式之積: xn+1=g(x)h(x) 其中，g(x)表示(n，k)循環(huán)碼的生成多項式，而h(x)則 為校驗多項式，其階數(shù)為k。 所以使用h(x)可以產(chǎn)生 相應的對偶碼。 定義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+xk 3、循環(huán)碼的生成矩陣、循環(huán)碼的生成矩陣 例：求二進制例：求二進制(7(7，4)4)循環(huán)碼的循環(huán)碼的 l（1）生成矩陣。 l解解：（：（1 1）設選設選

48、，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 32 1)(xxxg 1101000 0110100 0011010 0001101 74 G 其中，g(x)表示(n，k)循環(huán)碼的生成多項式，而h(x)則 為校驗多項式，其階數(shù)為k。 所以使用h(x)可以產(chǎn)生 相應的對偶碼。 定義h(x)的倒數(shù)多項式為： xkh(x-1)=xk(x-k+hk-1x-k+1+hk-2x-k+

49、+ + 2h1x-1+1) =1+hk-1x+hk-2x2+h1xk-1+xk 3、循環(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=1010011c=1010011 例：求二進制例：求二進制(7(7，4)4)循環(huán)碼的循環(huán)碼的 4、循環(huán)碼

50、的校驗矩陣 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=0 l同理循環(huán)碼滿足：同理循環(huán)碼滿足：c(x)h(x)=0c(x)h(x)=0。 k k k r n xhxhhxh xxh xxg xgxxh 10 )( 1)( 1)( )(/ ) 1()( 記作 ， 4、循環(huán)碼的校驗矩陣 65432 6534332 323 432 423 3 32 42 4332 32 3 3237 1 1 )1)(1 ()(

51、 )6 , 7()1 ()()3( 1 1 )1)(1 ()( )4 , 7()1 ()()2( 1 1 )1)(1 ()( )4 , 7()1 ()() 1 ( )1)(1)(1 (1 xxxxxx xxxxxxxx xxxxxh xxg xxx xxxxx xxxxh xxxg xxx xxxxx xxxxh xxxg xxxxxx 則它的校驗多項式為 循環(huán)碼的生成多項式作為若選 則它的校驗多項式為 循環(huán)碼的生成多項式作為若選 則它的校驗多項式為 循環(huán)碼的生成多項式作為若選 例： 4、循環(huán)碼的校驗矩陣 l校驗矩陣校驗矩陣H Hr r* *n n：將：將h(x)h(x)的系數(shù)按的系數(shù)按冪次的

52、降序冪次的降序 排列：作為矩陣的第一行；將第一行向右移排列：作為矩陣的第一行；將第一行向右移 一位作為一位作為G G的第二行；的第二行；。則。則 l由于是循環(huán)碼是線性的，因此滿足：由于是循環(huán)碼是線性的，因此滿足：GHGHT T=0=0 0 0 01 000 000 000 hh hh hhh H k k kk nr r-1r-1個個 k+1k+1個個 13 2 2 10 2 210 .)( .)( k k k k xhxhxhxhxxh xhxhxhhxh 4、循環(huán)碼的校驗矩陣 l例：求二進制（7，4）循環(huán)碼的校驗矩陣 73 432 1011100 0101110 0010111 H 1110

53、1)( 1)( 列行，對應的校驗矩陣為 按降冪排列： 選 nr xh xxxxh 5、系統(tǒng)循環(huán)碼 l（n,k）循環(huán)碼為系統(tǒng)碼 l已知待發(fā)送的消息為：已知待發(fā)送的消息為：m=(mm=(m0 0m m1 1m mk-1 k-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)碼的碼多項式為為 1 110 )( k k xmxmmxm消息多項式： )(mod)()( )()()(

54、 xgxmxxp xpxmxxc r r 其中： 80 例：求輸入消息例：求輸入消息m=1001m=1001時的（時的（7 7，4 4）系）系 統(tǒng)循環(huán)碼碼字統(tǒng)循環(huán)碼碼字 l解： 3 1)(xxm消息多項式： 23 3323 ( )( )( ) ( )( )mod ( ) 7,4( )1 ( )(1)mod(1) 1 110 0001001 110 1101001 r r c xx m xp x p xx m xg x g xxx p xxxxx x p c 系統(tǒng)循環(huán)碼 其中： 設選擇（）循環(huán)碼的 則 系統(tǒng)循環(huán)碼碼字 先將先將m右移右移r位位(此題此題 r=3)，再加上，再加上p(x)對對 應的

55、校驗碼應的校驗碼p 注意校驗位的位注意校驗位的位 數(shù)，不足的補數(shù)，不足的補0 系統(tǒng)循環(huán)碼的生成矩陣 81 l系統(tǒng)循環(huán)碼碼字系統(tǒng)循環(huán)碼碼字的第二種求法：的第二種求法：c=mGc=mGs s l生成矩陣生成矩陣G Gs s 又有兩種求法：又有兩種求法： l求法求法1 1：由：由g(x)g(x)GG 初等行變換初等行變換Gs Gs l求法求法2 2： 的系數(shù)：余式行：的第 的系數(shù)：余式行：的第 的系數(shù)：余式行：的第 即， 矩陣的各行：求余得的各位拆開分別對將 )()(mod)( )()(mod)(2 )()(mod)(1 )( )( , 1 1 1 1 1 1 0 0 0 1 110 xpxgxxx

56、pkQ xpxgxxxpQ xpxgxxxpQ Qxgm xmxmmxm IQG k kr k r r k k nkkrks 82 系統(tǒng)循環(huán)碼的一致校驗矩陣 l系統(tǒng)循環(huán)碼的一致校驗矩陣Hs l例：已知二進制（7，4）循環(huán)碼，求 l（1 1）求系統(tǒng)生成矩陣）求系統(tǒng)生成矩陣 l（2 2）輸入消息）輸入消息m=1001m=1001時的輸出的系統(tǒng)循環(huán)碼碼時的輸出的系統(tǒng)循環(huán)碼碼 字字 l（3 3）求一致校驗矩陣）求一致校驗矩陣 nr T rs QIH , l解：（解：（1 1）選）選g(x)=1+x+xg(x)=1+x+x3 3可得生成矩陣可得生成矩陣G:G: 由于是求系統(tǒng)循環(huán)碼的生成矩陣，則矩陣由于是

57、求系統(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： 1011000 0101100 0010110 0001011 74 G 系統(tǒng)循環(huán)碼的一致校驗矩陣 l通過初等行變換得系統(tǒng)循環(huán)碼的生成矩陣通過初等行變換得系統(tǒng)循環(huán)碼的生成矩陣GsGs 1000101 0100111 0010110 0001011 , ks IQG （2 2）因此：）因此： m m的系統(tǒng)循環(huán)碼為的系統(tǒng)循環(huán)碼為c=mGc=mGs s 代入代入m=

58、1001m=1001得得 C=0111001C=0111001 系統(tǒng)循環(huán)碼的一致校驗矩陣 l（3 3）一致校驗矩陣）一致校驗矩陣 1110100 0111010 1101001 , , 3 T T rs QI QIH 系統(tǒng)循環(huán)碼的一致校驗矩陣 l（4 4）生成的）生成的系統(tǒng)循環(huán)碼字系統(tǒng)循環(huán)碼字集合：集合： C=mGC=mGS S mC=mGS 00011010001 00101110010 00110100011 01000110100 01011100101 11111111111 1000101 0100111 0010110 0001011 S G 由由 于于 所所 以以 系統(tǒng)循環(huán)碼的一致校驗矩陣 5.4 卷積碼概念 圖（3，1，2）卷積碼編碼器 當輸入信息元為mi時， D0、D1中分別存放著此前輸入的 mj1和mj2， 經(jīng)運算可得到兩個校驗元pj，1和pj，2，即 pj，1mjmj1 pj，2mjmj2 5.4