




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、第五章 糾錯編碼1第五章第五章 糾錯編碼糾錯編碼5.1 5.1 糾錯編碼的基本概念糾錯編碼的基本概念5.2 5.2 線性分組碼線性分組碼5.35.3 循環碼循環碼5.4 5.4 卷積碼卷積碼 25.1 糾錯編碼的基本概念糾錯編碼的基本概念5.1.1 5.1.1 糾錯編碼的任務糾錯編碼的任務5.1.2 5.1.2 糾錯編碼的分類糾錯編碼的分類5.1.35.1.3 譯碼準則譯碼準則5.1.4 5.1.4 香農第二定理香農第二定理345.1 信道編碼的任務信道編碼的任務5.1 信道編碼信道編碼5l信源編碼信源編碼l提高數字信號提高數字信號l將信源的模擬信號轉變為數字信號將信源的模擬信號轉變為數字信號
2、l降低數碼率降低數碼率,壓縮傳輸頻帶壓縮傳輸頻帶(數據壓縮數據壓縮)l信道編碼信道編碼l提高數字通信提高數字通信 數字信號在信道的傳輸過程中數字信號在信道的傳輸過程中,由于實際由于實際信道信道的的傳輸特性不理想傳輸特性不理想以及存在加性以及存在加性噪聲噪聲,在接收端往在接收端往往會產生往會產生誤碼誤碼。5.1 信道編碼的任務信道編碼的任務6 信道編碼信道編碼:就是按一定的規則給信源輸出序列增加:就是按一定的規則給信源輸出序列增加某些冗余符號,使其變成滿足一定數學規律的碼序列某些冗余符號,使其變成滿足一定數學規律的碼序列(或碼字),再經信道進行傳輸。(或碼字),再經信道進行傳輸。(提高傳輸的可靠
3、性)(提高傳輸的可靠性) 信道譯碼信道譯碼:就是按與編碼器同樣的數學規律去掉接:就是按與編碼器同樣的數學規律去掉接收序列中的冗余符號收序列中的冗余符號, , 恢復信源消息序列。恢復信源消息序列。 一般地說,所加的冗余符號越多,糾錯能力就越強,一般地說,所加的冗余符號越多,糾錯能力就越強,但傳輸效率降低。因此在信道編碼中明顯體現了傳輸有但傳輸效率降低。因此在信道編碼中明顯體現了傳輸有效性與可靠性的矛盾。效性與可靠性的矛盾。 編碼信道模型編碼信道模型7011011,0,1, , 0,1ninicc cccRr rrr消息消息cRm 信道編碼信道編碼 編碼信道編碼信道 信道譯碼信道譯碼 m碼字碼字接
4、收向量接收向量消息消息編碼信道模型R噪聲源噪聲源錯誤圖樣E編碼信道模型編碼信道模型8l消息序列m總以k個碼元為一組傳輸,稱k個碼元的碼組為信息碼組。l信道編碼器按一定規則對每個信息碼組附加一些多余的碼元,構成長為n個碼元的碼組c(信道編碼)。l附加的r=n-k個碼元稱為監督碼元錯誤圖樣錯誤圖樣9 為了定量描述信號的差錯,使用差錯圖樣表示發送和接收碼之“差”,設發送的碼為C,接收碼為R,對于M進制碼,差錯圖樣E為E=(CR)(modM)對于二進制碼而言,減法運算就是模2加法運算,于是有ECR例如:C=10000,E=01000,R=? R=(11000)105.1 信道編碼的任務信道編碼的任務1
5、0檢錯與糾錯原理檢錯與糾錯原理 l0:晴,1:雨l若10,01。收端無法發現錯誤00晴1001110011雨能發現一個錯誤禁用碼組 插入1位監督碼后具有檢出1位錯碼的能力,但不能予以糾正。115.1 信道編碼的任務信道編碼的任務11000晴010001111000111雨晴 在只有1位錯碼的情況下,可以判決哪位是錯碼并予以糾正,可以檢檢出2位或2位以下的錯碼。100011101110雨檢錯和糾錯方式檢錯和糾錯方式12l自動請求重發(ARQ):l發端發送檢錯碼,l收端譯碼器判斷當前碼字傳輸是否出錯;l當有錯時按某種協議通過一個反向信道請求發送端重傳已發送的碼字(全部或部分)。優點:優點: 編譯碼
6、設備比較簡單。 在一定的多余度碼元下,系統具有極強的糾錯能力。 能獲得極低的誤碼率。 由于檢錯碼的檢錯能力與信道干擾的變化基本無關,因此這種系統的適應性很強,特別適應于短波、 散射、 有線等干擾情況特別復雜的信道中。 ARQ缺點:缺點: 控制電路比較復雜。 傳送消息的連貫性和實時性較差。由于反饋重發的次數與信道干擾情況有關,若信道干擾很頻繁,則信道經常處于重發消息的狀態。ARQ檢錯和糾錯方式檢錯和糾錯方式l前向糾錯(FEC):l發送端的信道編碼器將信息碼組編成具有一定糾錯能力的碼。l接收端信道譯碼器對接收碼字進行譯碼,若傳輸中產生的差錯數目在碼的糾錯能力之內時,譯碼器對差錯進行定位并加以糾正。
7、優點:優點: 不需要反饋信道,能夠實現一對多的同步廣播通信,而且譯碼實時性好,控制電路也比ARQ簡單。隨著編碼理論的發展和大規模集成技術的發展,復雜算法的譯碼設備越來越簡單,成本越來越低,所以這種方式在實際中得到越來越廣泛的應用。FEC缺點:缺點: 這種工作方式是假設糾錯碼的糾錯能力足夠糾正信息序列傳輸中的錯誤,也就是糾錯碼與信道的干擾是相匹配的,所以對信道的適應性較差。 為了獲得合適的誤碼率,往往按照信道最差的情況設計糾錯碼,增加的冗余碼元比檢錯碼要多,編碼效率一般較低。 FEC檢錯和糾錯方式檢錯和糾錯方式l混合糾錯混合糾錯(HEC):l是是FEC與與ARQ方式的結合。方式的結合。l發端發送
8、同時具有自動糾錯和檢測能力的碼發端發送同時具有自動糾錯和檢測能力的碼組組,收端收到碼組后收端收到碼組后,檢查差錯情況檢查差錯情況,如果差錯在如果差錯在碼的糾錯能力以內碼的糾錯能力以內,則自動進行糾正。則自動進行糾正。l如果信道干擾很嚴重如果信道干擾很嚴重,錯誤很多錯誤很多,超過了碼的糾超過了碼的糾錯能力錯能力,但能檢測出來但能檢測出來,則經反饋信道請求發端則經反饋信道請求發端重發這組數據。重發這組數據。l信息反饋信息反饋(IRQ):l收端把收到的數據收端把收到的數據,原封不動地通過反饋信道原封不動地通過反饋信道送回到發端送回到發端,發端比較發的數據與反饋來的數發端比較發的數據與反饋來的數據據,
9、從而發現錯誤從而發現錯誤,并且把錯誤的消息再次傳送并且把錯誤的消息再次傳送,直到發端沒有發現錯誤為止。直到發端沒有發現錯誤為止。優點:優點:由于該方式避免了FEC要求的復雜設備和ARQ方式的信息連貫性差的缺點,并且可以達到較低的誤碼率,因此在實際中得到了廣泛應用。 HEC總結:信道編碼的概念l目的:降低錯誤的譯碼概率PEl對象:信息序列l方法:信息碼+附加碼元,收端按照一定譯碼準則檢糾錯。l實質:增加冗余度。205.1.2 信道(糾錯)編碼的分類l按照接收端工作狀態分為: 檢錯碼 糾錯碼 糾刪碼l根據糾正錯誤的類型 糾隨機錯誤碼 糾突發錯誤碼21225.1.2 信道(糾錯)編碼的分類22l隨機
10、差錯:l差錯是相互獨立的,不相關l存在這種差錯的信道是無記憶信道或隨機信道l突發差錯:l指成串出現的錯誤,錯誤與錯誤間有相關性,一個差錯往往要影響到后面一串字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突發長度= 4突發長度= 65.1.2 信道(糾錯)編碼的分類l按照發送端編碼方式分為:235.1.3譯碼準則245.1.3譯碼準則25),.,2 , 1;,.,2 , 1()(sjriabFij5.1.3譯碼準則26(1)對輸入符號集為X=a1,a2,ar,輸出符號集為Y= b1,b2,bs的信道來說,一共可構成rs種不同的譯碼規則。
11、不同的譯碼規則會引起不同的可靠程度。5.1.3譯碼準則27 最小錯誤譯碼準則(最小錯誤譯碼準則(MEPD) 最大后驗概率準則(最大后驗概率準則(MPPD) 最大聯合概率準則(最大聯合概率準則(MJPD) 最大似然概率準則(最大似然概率準則(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香農第二定理285.1.4香農第二定理29表述二:表述二:設離散無記憶信道的信道容量
12、為C,信息傳輸率為R,對于任意小的正數,當Rk) 碼字,其中 (nk) 個附加碼元是由信息碼元的線性運算產生的。l信息碼組長信息碼組長 k 位,有位,有 2k 個不同的信息碼組,則應該有個不同的信息碼組,則應該有 2k 個碼字與它們一一對應。個碼字與它們一一對應。5.2.1 線性分組碼的基本概念線性分組碼的基本概念5.2 線性分組碼325.2.1 線性分組碼的基本概念線性分組碼的基本概念l線性分組碼線性分組碼:通過預定的線性運算將長為:通過預定的線性運算將長為 k 位的信位的信息碼組變換成息碼組變換成 n 長的碼字長的碼字 ( nk )。由。由 2k 個信息碼組個信息碼組所編成的所編成的 2k
13、個碼字集合,稱為個碼字集合,稱為線性分組碼線性分組碼。l碼矢碼矢:一個:一個 n 長的碼字可以用矢量來表示長的碼字可以用矢量來表示C C = (Cn1,Cn2,C1,C0 ) 所以碼字又稱為碼矢。所以碼字又稱為碼矢。l( n, k ) 線性碼線性碼:信息位長為:信息位長為 k,碼長為,碼長為 n 的線性碼的線性碼l編碼效率編碼效率/編碼速率編碼速率/碼率:碼率:R=k /n。它說明了信道的。它說明了信道的利用效率,利用效率,R是衡量碼性能的一個重要參數是衡量碼性能的一個重要參數。5.2 線性分組碼335.2.1 線性分組碼的基本概念線性分組碼的基本概念線性體現在線性體現在:輸入輸出的關系為線性
14、映射關系輸入輸出的關系為線性映射關系碼元中每個碼字由信源做模二加運算得到碼元中每個碼字由信源做模二加運算得到線性分組碼的特點線性分組碼的特點:在碼集中存在全在碼集中存在全0碼字碼字滿足封閉性滿足封閉性5.2 線性分組碼345.2.1 線性分組碼的基本概念線性分組碼的基本概念定理定理:線性分組碼的最小距離等于最小非零碼字重量。:線性分組碼的最小距離等于最小非零碼字重量。定理中涉及到的基本概念定理中涉及到的基本概念漢明重量漢明重量:碼字中非:碼字中非0碼的個數。碼的個數。最小漢明重量最小漢明重量:碼集中非:碼集中非0碼字漢明重量的最小值。碼字漢明重量的最小值。漢明距離漢明距離:兩個等長碼:兩個等長
15、碼C和和C中,對應位碼元不同的取中,對應位碼元不同的取值個數。值個數。最小漢明距離最小漢明距離:碼集中所有碼字距離的最小值。:碼集中所有碼字距離的最小值。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標準生成矩陣:標準生成矩陣: 通過行初等變換,將 G 化為前 k 行和k 列是單位子陣的標準形式標準形式11121()21222()12()100010GIQ001n kn kk nkk rkkk n kqqqqqqqqq 5.2 線性分組碼375.2.2 線性分組碼的編碼線性分組碼的編碼二、編碼二、編碼l線性系統分組碼線性系統分組碼:用標準生成矩陣用標準生成矩陣 GGkn 編成的碼編成的碼字,前面字,前面 k 位為信息數字,后面位為信息數字,后面 r=nk 位為校驗位為校驗字,這種信息數字在前校驗數字在后的線性分組碼字,這種信息數字在前校驗
17、數字在后的線性分組碼稱為線性系統分組碼。稱為線性系統分組碼。l當生成矩陣當生成矩陣 G G 確定之后,確定之后,(n,k) 線性碼也就完全被線性碼也就完全被確定了,只要找到碼的生成矩陣,編碼問題也同樣確定了,只要找到碼的生成矩陣,編碼問題也同樣被解決了。被解決了。38舉例舉例: 已知一個已知一個 (7,4) 線性碼的生成矩陣線性碼的生成矩陣G如下圖示,當輸入信息碼元為如下圖示,當輸入信息碼元為1010時,試求輸出的碼字。時,試求輸出的碼字。n由矩陣乘法規則可知:由矩陣乘法規則可知: C C = = m m G G 的結果,就是矩陣的結果,就是矩陣 G G 中,與中,與 m m 中為中為“1 1
18、” ”的元素相對應的的元素相對應的行按位模行按位模 2 2 加的結果。加的結果。5.2.2 線性分組碼的編碼4 71 41 71 44 710001010100111G00101100001011m(1010)10001010100111CmG1010(1010011)00101100001011395.2.2 線性分組碼的編碼練習:練習: 已知某線性分組碼的生成矩陣為已知某線性分組碼的生成矩陣為l試問試問:l(1)n = ? k = ? , 該碼組集合中的碼字有多少?該碼組集合中的碼字有多少?l(2)若信息碼元若信息碼元 m 分別是分別是 1100 和和1111時時 , 寫出其對應的輸出碼字
19、。寫出其對應的輸出碼字。10000110100101G00101100001111405.2.3 線性分組碼的譯碼一、一致校驗矩陣一、一致校驗矩陣l推廣到一般情況:對推廣到一般情況:對 (n,k) 線性分組碼,每個碼字中的線性分組碼,每個碼字中的 r(r=nk) 個監督元與信息元之間的關系可由下面的線性個監督元與信息元之間的關系可由下面的線性方程組確定方程組確定000022110222212101212111ChChChChChChChChChrnnrnrnnnnnn415.2.3 線性分組碼的譯碼一、一致校驗矩陣一、一致校驗矩陣l令系數矩陣為令系數矩陣為 HH,碼字行陣列為,碼字行陣列為 C
20、 C矩陣。線性分組碼的一致監督為稱或則:),(H0HC0CHCH11110211212222111211knCCChhhhhhhhhrTrnnTrTnnrnnnrnrrnnnr425.2.3 線性分組碼的譯碼一、一致校驗矩陣特性一、一致校驗矩陣特性:l對對H H 各行實行初等變換,將后面各行實行初等變換,將后面 r 列化為單位子陣,于是列化為單位子陣,于是得到下面矩陣得到下面矩陣(行變換所得方程組與原方程組同解行變換所得方程組與原方程組同解)。l校驗矩陣校驗矩陣H H 的標準形式的標準形式:后面:后面 r 列是一單位子陣的校驗矩列是一單位子陣的校驗矩陣陣HH。lH H 陣的每一行都代表一個校驗
21、方程,它表示與該行中陣的每一行都代表一個校驗方程,它表示與該行中“1”相對應的碼元的模相對應的碼元的模2和為和為0。100010001H212222111211rnrrkknrppppppppp435.2.3 線性分組碼的譯碼 GIQHPI(P)G HIQPIIQ(P)Q0IGIQH(Q)ISkk rSr krTTTTr kSSkk rr krkk rr kk rk rrSkk rTSk rr生成矩陣與一致校驗矩陣的關系生成矩陣與一致校驗矩陣的關系:l由于生成矩陣由于生成矩陣GG的每一行都是一個碼字,所以的每一行都是一個碼字,所以G G 的每行都滿的每行都滿足足HHrnC CTn1=0 0Tr
22、1,則有,則有HHrnGGTnk=0 0Trk 或或 GGknHHTnr=0 0krl線性系統碼的監督矩陣線性系統碼的監督矩陣 H H 和生成矩陣和生成矩陣 G G 之間可以直接互換之間可以直接互換。445.2.3 線性分組碼的譯碼例例: 已知已知(7,4)線性系統碼的監督矩陣為線性系統碼的監督矩陣為1101000011010011100101010001G100101101011100010111H)4,7()4,7(陣可直接寫出它的生成矩455.2.3 線性分組碼的譯碼標準陣列譯碼l標準陣列構造方法標準陣列構造方法l先將先將 2k 個碼矢排成一行,作為個碼矢排成一行,作為標準陣列標準陣列的
23、第一行,并將的第一行,并將全全0碼矢碼矢C C1=(000)放在最左面的位置上;放在最左面的位置上;l然后在剩下的然后在剩下的 (2n2k) 個個 n 重中選取一個重量最輕的重中選取一個重量最輕的 n 重重 E E2 放在全放在全0碼矢碼矢 C C1 下面,再將下面,再將 E E2 分別和碼矢分別和碼矢 相加,放在對應碼矢下面,構成陣列第二行;相加,放在對應碼矢下面,構成陣列第二行;l在第二次剩下的在第二次剩下的 n 重中,選取重量最輕的重中,選取重量最輕的 n 重重 E E3,放在,放在 E E2 下面,并將下面,并將 E E3 分別加到第一行各碼矢上,得到第三分別加到第一行各碼矢上,得到第
24、三行;行;l,繼續這樣做下去,直到全部,繼續這樣做下去,直到全部 n 重用完為止。得到下重用完為止。得到下頁表格所示的頁表格所示的 (n,k) 線性碼的標準陣列。線性碼的標準陣列。46碼字 CC1(=0) (陪集首) CC2 CC E E2 CC2+ E E2 CCi + E E2 E E3 CC2+ E E3 CCi + E E3 禁 用 碼 組 5.2.3 線性分組碼的譯碼標準陣列譯碼475.2.3 線性分組碼的譯碼標準陣列譯碼標準陣列的特性:標準陣列的特性:定理定理:在標準陣列的同一行中沒有相同的矢量,而且:在標準陣列的同一行中沒有相同的矢量,而且 2n 個個 n 重中任一個重中任一個
25、n 重在陣列中出現一次且僅出現一次。重在陣列中出現一次且僅出現一次。L陪集陪集:標準陣列的每一行叫做碼的一個陪集。:標準陣列的每一行叫做碼的一個陪集。L陪集首陪集首:每個陪集的第一個元素叫做陪集首。:每個陪集的第一個元素叫做陪集首。485.2.3 線性分組碼的譯碼伴隨式譯碼伴隨式和錯誤檢測:伴隨式和錯誤檢測:l用監督矩陣譯碼用監督矩陣譯碼:接收到一個碼字:接收到一個碼字 R R 后,檢驗后,檢驗 HH R RT=0 0T 是否成立:是否成立:lHRT =0T是否成立是檢驗碼字出錯與否的依據。l若關系成立,則認為 R 是一個碼字;l否則判為碼字在傳輸中發生了錯誤;l伴隨式伴隨式/監督子監督子/校
26、驗子校驗子:S S=R R HHT或或S ST=HH R RT。l如何糾錯?如何糾錯?l設發送碼矢 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求接收碼字的伴隨式(接收碼字用監督矩陣進行檢驗)求接收碼字的伴隨式(接收碼字用監督矩陣進行檢驗) 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設設HH=(h h1,h h2,h hn),其中,其中h hi表示表示HH的列。代入上式得到的列。代入上式得到505.2.3 線性分組碼的譯碼伴隨式譯碼 總結總結:l伴隨式僅與錯誤圖樣有關,而與發送的具體碼字無關,即伴隨式僅與錯誤圖樣有關,而與發送的具體碼字無關,即伴隨式僅由錯誤圖樣決定;伴隨式僅由錯誤圖樣決定;l伴隨式是錯誤的判別式:伴隨式是錯誤的判別式:l若S=0,則判為沒有出錯,接收碼字是一個碼字;l若S0,則判為有錯。l不同的錯誤圖樣具有不同的伴隨式,它們是一一對
28、應的。不同的錯誤圖樣具有不同的伴隨式,它們是一一對應的。對二元碼,伴隨式對二元碼,伴隨式S是是H H 陣中與錯誤碼元對應列之和陣中與錯誤碼元對應列之和。51伴隨式譯碼舉例:伴隨式譯碼舉例: 某某(7,3) 線性系統碼線性系統碼l設發送碼字設發送碼字C C = 1010011,接收碼字,接收碼字R R 1010011,R R與與C C相同。相同。無錯。因此,譯碼器判接收字代入得和計算伴隨式,把根據接收字道就是發送的碼字,但接收端譯碼器并不知TTT0HRSRHRH10001100100011001011100011015.2.3 線性分組碼的譯碼伴隨式譯碼52l若接收碼字中有一位錯誤若接收碼字中有
29、一位錯誤正確。錯能力相符,所以譯碼中錯誤碼元數與碼的糾由于接收字的第二位是錯的。因此判定接收字的第二列,等于且碼是糾單個錯誤的碼,譯碼器判為有錯。由于伴隨式為接收碼字發送碼矢RRHS0SRHSRCTTTT)3 , 7(,111011001111000110010001100101110001101111001110100115.2.3 線性分組碼的譯碼伴隨式譯碼535.2.3 線性分組碼的譯碼伴隨式譯碼l當碼元錯誤多于1個時位上,只是發現有錯。無法判定錯誤出在哪些同,陣中的任何一列都不相但與,不等于是第一列和第四列之和由于伴隨式為接收碼字發送碼矢H0SRHSRCTTT0110110110010
30、0011001000110010111000110100110111010011545.2.3 線性分組碼的譯碼伴隨式譯碼以上定理是糾錯碼理論中最重要的基本定理之一,它說明了一個距離為d的線性分組碼,既可用來糾正個錯誤,又可用來檢測e d1個錯誤。 21dt定理定理 對于任一個(對于任一個(n,k)線性分組碼,若要在碼字內線性分組碼,若要在碼字內 檢測檢測e個錯誤,則要求碼的最小距離個錯誤,則要求碼的最小距離d e1; 糾正糾正t個錯誤,則要求碼的最小距離個錯誤,則要求碼的最小距離d 2t1; 糾正糾正t個錯誤同時檢測個錯誤同時檢測e( t)個錯誤,則要求個錯誤,則要求d te1。555.2.
31、4 漢明碼 對于給定的正整數m3,二進制漢明碼的信息位數量、 碼字長度與m之間滿足下列關系:k=2mm1 n=2n-k1所以漢明碼實際就是(2m1,2mm1)分組碼。 當m=3時,則為(7,4)碼。 二進制漢明碼的最小漢明距離為d0=3。 565.2.4 漢明碼 例例 構造構造m=3的漢明碼。的漢明碼。 解解 由于由于m=3,根據漢明碼的性質可知,根據漢明碼的性質可知k=2mm1=4 n=2m1=7所以所以m=3的漢明碼是的漢明碼是(7,4)分組碼。分組碼。 除了矢量除了矢量0之外的所有之外的所有排列為排列為(001),(010),(011),(100),(101),(110),(111),為
32、,為了產生系統碼,將了產生系統碼,將(100),(010),(001)放在矩陣的最后放在矩陣的最后3列,列,得到校驗矩陣為得到校驗矩陣為575.2.4 漢明碼011110010110101101001H于是得到生成矩陣為于是得到生成矩陣為1000011010010100101100001111G585.3 循環碼5.3.1 循環碼的基本概念循環碼的基本概念數學定義數學定義:設:設C為某為某( n, k )線性分組碼的碼組集合,如果對線性分組碼的碼組集合,如果對C中任中任意一個碼組意一個碼組c = ( an-1 an-2 a1 a0 ),它的循環移位,它的循環移位c(1) = ( an-2an-
33、3 a1 a0 an-1 )也屬于也屬于C,則稱該,則稱該( n, k )碼為循環碼碼為循環碼其中其中c(i )表示表示c碼組循環移位碼組循環移位i次。次。例如:某例如:某( 7, 4 )循環碼組集合中的一個碼組為循環碼組集合中的一個碼組為( 1000101 ),向左,向左循環移位一次后的碼組循環移位一次后的碼組( 0001011 )仍為碼組集合中第一個許用仍為碼組集合中第一個許用碼組碼組595.3 循環碼605.3 循環碼615.3.2 循環碼的描述循環碼的描述 1、循環碼多項式描述、循環碼多項式描述621、循環碼多項式描述、循環碼多項式描述碼多項式的模運算碼多項式的模運算正整數的模運算正整
34、數的模運算若一正整數若一正整數M除以正整數除以正整數N,所得到的商為,所得到的商為Q,余數為,余數為R,可表示為,可表示為其中其中Q為整數,則在模為整數,則在模N運算下,上式的結果為:運算下,上式的結果為:多項式的模運算與正整數的模運算相同,一般利用長除法計算商式和余式多項式的模運算與正整數的模運算相同,一般利用長除法計算商式和余式有兩個多項式有兩個多項式a(x)和和p(x),一定存在有唯一的多項式,一定存在有唯一的多項式Q(x)和和r(x),使得:,使得: 稱稱Q(x)是是a(x)除以除以p(x)的商式,的商式,r(x)是是a(x)除以除以p(x)的余式,在模的余式,在模p(x)運算下運算下
35、且有且有 即:除到余式的次數小于除式為止,當能整除時即:除到余式的次數小于除式為止,當能整除時次數為次數為00 MRQRNNN) mod,記模( NNRM為( )( ) ( )( )a xQ x p xr x)(mod )()(xpxrxa0deg ( )deg( ) r xp x63定理:對于( n, k )循環碼,若c(x)對應碼組c = (an-1an-2 a1a0 ), c(1)的一次循環移位c(1) = ( an-2an-3 a1a0 an-1 )及c(i )(x)對應的c碼循環移位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、循環碼多項式描述、循環碼多項式描述碼多項式的模運算碼多項式的模運算1、循環碼多項式描述、循環碼多項式描述碼多項式的模運算碼多項式的模運算例如例如:(7 , 4)循環碼的第循環碼的第12個碼組個碼組c12為:為:1011000,則其碼多
37、項,則其碼多項式為:式為: c(x)=x6 + x4 + x3 請寫出請寫出c12左循環移位左循環移位3次的碼組次的碼組解:解:i = 3,則,則 x3c(x) = x9 + x7 + x6 其對應碼組為:其對應碼組為:1000101,它是,它是( 7, 4 )循環碼中的第循環碼中的第4個碼組個碼組c47362mod1( )1xx c xxx279769276276211 1 1xxxxxxxxxxxxx651、循環碼多項式描述、循環碼多項式描述生成多項式生成多項式 定義定義:記:記C(x)為為( n, k )循環碼的所有碼組對應的多項式的集合循環碼的所有碼組對應的多項式的集合,若,若g(x)
38、是是C(x)中除中除0多項式以外次數最低的多項式,則稱多項式以外次數最低的多項式,則稱g(x)為這個循環碼的生成多項式為這個循環碼的生成多項式其一般形式為:其一般形式為: g(x) = xr + gr-1 xr-1 + + g1 x1 + 1 g(x)具有以下性質:具有以下性質: 1)g(x)的的0次項是次項是1; 2)循環碼的每一碼多項式)循環碼的每一碼多項式c(x)都是都是g(x)的倍式,且每一個小于的倍式,且每一個小于等于等于n-1次的次的g(x)的倍式一定是碼多項式;的倍式一定是碼多項式; 3)g(x)的最高次為的最高次為n-k,且是唯一的;,且是唯一的; 4)g(x)是是xn + 1
39、的一個因子的一個因子生成多項式66l例:求(7,4)循環碼的生成多項式。l解:生成多項式解:生成多項式g(x)g(x):r=n-k=7-4= r=n-k=7-4= 3 3次次首一首一多項式多項式l即將 因式分解:l選擇 或 任一均可作為(7,4)循環碼的生成多項式。17x)1)(1)(1 (13237xxxxxx31xx321xx 常數項為常數項為1 1,最高項為,最高項為3 3次次(n,k)循環碼的構造步驟:對(xn+1)做因式分解,找出其n-k次因式;以n-k次因式為生成多項式g(x),與信息多項式m(x)相乘,即得到碼多項式: C(x)=m(x)g(x) 因m(x)不高于(k-1)次,所
40、以C(x)的次數不會高于(k-1)+(n-k)=(n-1)次。2、循環碼的構造、循環碼的構造討論長度討論長度n=7的循環碼。的循環碼。 解解 多項式多項式x7+1可以分解為下列形式可以分解為下列形式:x7+1=(x+1)(x3+x2+1)(x3+x+1)為了產生為了產生(7,4)循環碼,可以取下列兩個多項式之一作為生循環碼,可以取下列兩個多項式之一作為生成多項式成多項式:g1(x)=x3+x2+1 g2(x)=x3+x+1其中,其中,g1(x)和和g2(x)產生的碼是等價的。產生的碼是等價的。2、循環碼的構造、循環碼的構造具體產生過程為:具體產生過程為: 假設假設4比特信息為比特信息為(000
41、1),對應的信,對應的信息多項式為息多項式為X1(x)=1,所以碼字多項式為,所以碼字多項式為C1(x)=m1(x)g1(x)=(x3+x2+1)對應碼字為對應碼字為C1=(0001101)當當4比特信息為比特信息為(0010)時,對應的信息多項式為時,對應的信息多項式為X2(x)=x,碼,碼字多項式為字多項式為C2(x)=m2(x)g1(x)=x(x3+x2+1)=x4+x3+x對應碼字為對應碼字為C2=(0011010)2、循環碼的構造、循環碼的構造 當當4比特信息為比特信息為(0011)時,對應的信息多項式為時,對應的信息多項式為m3(x)=x+1,碼字多項式為,碼字多項式為331324
42、332( )( )( ) (1)(1) ()(1)Cxmx gxxxxxxxxx 注意到二進制多項式加法為同階次項的系數進行半加注意到二進制多項式加法為同階次項的系數進行半加運算,所以運算,所以x3+x3=(1+1)x3=0 x3=0于是得到于是得到C3(x)=x4+x2+x+12、循環碼的構造、循環碼的構造對應碼字為對應碼字為C3=(0010111)以此類推,可以得到其他碼字。以此類推,可以得到其他碼字。 2、循環碼的構造、循環碼的構造多項式xn+1總是可以分解為兩個多項式之積:xn+1=g(x)h(x)其中,g(x)表示(n,k)循環碼的生成多項式,而h(x)則為校驗多項式,其階數為k。
43、所以使用h(x)可以產生相應的對偶碼。 定義h(x)的倒數多項式為:xkh(x-1)=xk(x-k+hk-1x-k+1+hk-2x-k+ + + 2h1x-1+1) =1+hk-1x+hk-2x2+h1xk-1+xk3、循環碼的生成矩陣、循環碼的生成矩陣l定理定理:(n(n,k)k)循環碼的生成矩陣循環碼的生成矩陣G G由由g(x)g(x)唯一確定,其唯一確定,其第一行對應于第一行對應于g(x)g(x)的系數,第二行對應于的系數,第二行對應于xg(x)xg(x)的系數的系數,第,第k k行對應于行對應于 的系數。的系數。lG Gk k* *n n:k k行行n n列,則列,則l生成的循環碼碼字
44、:生成的循環碼碼字:C=mGC=mG)(1xgxknkrrrggggggggG10010000000000k-1k-1個個r+1r+1個個1322102210.)(.)(rrrrxgxgxgxgxxgxgxgxggxg多項式xn+1總是可以分解為兩個多項式之積:xn+1=g(x)h(x)其中,g(x)表示(n,k)循環碼的生成多項式,而h(x)則為校驗多項式,其階數為k。 所以使用h(x)可以產生相應的對偶碼。 定義h(x)的倒數多項式為:xkh(x-1)=xk(x-k+hk-1x-k+1+hk-2x-k+ + + 2h1x-1+1) =1+hk-1x+hk-2x2+h1xk-1+xk3、循環
45、碼的生成矩陣、循環碼的生成矩陣例:求二進制例:求二進制(7(7,4)4)循環碼的循環碼的l(1)生成矩陣。l解解:(:(1 1)設選設選 ,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)循環碼的生成多項式,而h(x)則為校驗多項式,其階數為k。 所以使用h(x)可以產生相
46、應的對偶碼。 定義h(x)的倒數多項式為:xkh(x-1)=xk(x-k+hk-1x-k+1+hk-2x-k+ + + 2h1x-1+1) =1+hk-1x+hk-2x2+h1xk-1+xk3、循環碼的生成矩陣、循環碼的生成矩陣l(3)(3)若已知消息多項式若已知消息多項式m(x)=1+xm(x)=1+x3 3,求該(,求該(7 7,4 4)循環碼的輸出碼字:)循環碼的輸出碼字: 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例:求二進制例:求二進制(7(7,4)4)循環碼的循環碼的4、循環碼的校驗矩陣l循環碼的循環碼的校驗多項式校驗多項式h(x) h(x) l(n,k)(n,k)循環碼的校驗多項式循環碼的校驗多項式h(x)h(x)定義為:定義為: l由于循環碼是線性分組碼,因此滿足由于循環碼是線性分組碼,因此滿足CHCHT T=0=0l同理循環碼滿足:同理循環碼滿足:c(x)h(x)=0c(x)h(x)=0。 kkkrnxhxhhxhxxhxxgxgxxh10)(1)(1)()(/ ) 1()(記作,4、循環碼的校驗矩陣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 則它的校驗多項式為循環碼的生成多項式作為若選則它的校驗多項式為循環碼的生成多項式作為若選則它的校驗多項式為循環碼的生成多項式作為若選例:4、循環碼的校驗矩陣l校驗矩陣校驗矩陣H Hr r* *n n:將:將h(x)h(x)的系數按的系數按冪次的降序冪次的降序排列:作為矩
49、陣的第一行;將第一行向右移排列:作為矩陣的第一行;將第一行向右移一位作為一位作為G G的第二行;的第二行;。則。則l由于是循環碼是線性的,因此滿足:由于是循環碼是線性的,因此滿足:GHGHT T=0=00001000000000hhhhhhhHkkkknrr-1r-1個個k+1k+1個個1322102210.)(.)(kkkkxhxhxhxhxxhxhxhxhhxh4、循環碼的校驗矩陣l例:求二進制(7,4)循環碼的校驗矩陣73432101110001011100010111H11101)(1)(列行,對應的校驗矩陣為按降冪排列:選nrxhxxxxh5、系統循環碼l(n,k)循環碼為系統碼l已
50、知待發送的消息為:已知待發送的消息為:m=(mm=(m0 0m m1 1m mk-1k-1) ),則則l分析:系統循環碼分析:系統循環碼C=(C=(校驗位,信息位校驗位,信息位) ) l思路:將思路:將k k位信息位整體向右移位位信息位整體向右移位r r位,再加上位,再加上校驗位。校驗位。l按照以上思路可得按照以上思路可得系統循環碼的碼多項式系統循環碼的碼多項式為為1110)(kkxmxmmxm消息多項式:)(mod)()()()()(xgxmxxpxpxmxxcrr其中:80例:求輸入消息例:求輸入消息m=1001m=1001時的(時的(7 7,4 4)系)系統循環碼碼字統循環碼碼字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 系統循環碼其中:設選擇()循環碼的則系統循環碼碼字先將先將m右移右移r位位(此題此題r=3),再加上,再加上p(x)對對應的校驗碼應的校驗碼p注意校驗位的位注意校驗位的位數,不足的補數,不足的補0系統循環碼的生成矩陣81l系統循環碼碼字系統循環碼碼字的第二種求法:的第二種求法:c=mGc=mGs sl生成矩陣生成矩陣G Gs s 又有兩種求法:又有兩種求法
52、:l求法求法1 1:由:由g(x)g(x)GG 初等行變換初等行變換Gs Gs l求法求法2 2: 的系數:余式行:的第的系數:余式行:的第的系數:余式行:的第即,矩陣的各行:求余得的各位拆開分別對將)()(mod)()()(mod)(2)()(mod)(1)()(,1111110001110 xpxgxxxpkQxpxgxxxpQxpxgxxxpQQxgmxmxmmxmIQGkkrkrrkknkkrks82系統循環碼的一致校驗矩陣l系統循環碼的一致校驗矩陣Hsl例:已知二進制(7,4)循環碼,求l(1 1)求系統生成矩陣)求系統生成矩陣l(2 2)輸入消息)輸入消息m=1001m=1001時
53、的輸出的系統循環碼碼時的輸出的系統循環碼碼字字 l(3 3)求一致校驗矩陣)求一致校驗矩陣nrTrsQIH,l解:(解:(1 1)選)選g(x)=1+x+xg(x)=1+x+x3 3可得生成矩陣可得生成矩陣G:G: 由于是求系統循環碼的生成矩陣,則矩陣由于是求系統循環碼的生成矩陣,則矩陣中必含有中必含有I I4 4的單位陣,而直接求得的的單位陣,而直接求得的G G中不含單中不含單位陣,所以它不是系統循環碼的位陣,所以它不是系統循環碼的G G。 需求系統循環碼的需求系統循環碼的GsGs:101100001011000010110000101174G系統循環碼的一致校驗矩陣l通過初等行變換得系統循
54、環碼的生成矩陣通過初等行變換得系統循環碼的生成矩陣GsGs1000101010011100101100001011,ksIQG(2 2)因此:)因此: m m的系統循環碼為的系統循環碼為c=mGc=mGs s 代入代入m=1001m=1001得得 C=0111001C=0111001系統循環碼的一致校驗矩陣l(3 3)一致校驗矩陣)一致校驗矩陣111010001110101101001,3TTrsQIQIH系統循環碼的一致校驗矩陣l(4 4)生成的)生成的系統循環碼字系統循環碼字集合:集合: C=mGC=mGS SmC=mGS0001101000100101110010001101000110100011010001011100101111111111111000101010011100101100001011SG由由于于所所以以系統循環碼的一致校驗矩陣5.4 卷積碼概念圖(3,1,2)卷積碼編碼器 當輸入信息元為mi時, D0、D1中分別存放著此前輸入的mj1和mj2, 經運算可得到兩個校驗元p
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025-2030中國集裝箱稱重系統行業市場發展趨勢與前景展望戰略研究報告
- 2025-2030中國防火閥行業市場發展趨勢與前景展望戰略研究報告
- 2025-2030中國間苯二甲胺行業市場發展趨勢與前景展望戰略研究報告
- 2025-2030中國鈦基臺行業市場發展趨勢與前景展望戰略研究報告
- 2025-2030中國酒石酸依來司他酯原料藥行業市場發展趨勢與前景展望戰略研究報告
- 2025-2030中國軋鋼棒材行業市場發展趨勢與前景展望戰略研究報告
- 2025-2030中國超聲波角膜測厚儀行業市場發展趨勢與前景展望戰略研究報告
- 2025-2030中國調節血糖食品行業市場發展分析及競爭格局與投資前景研究報告
- 2025-2030中國角色扮演偵探游戲行業市場發展趨勢與前景展望戰略研究報告
- 2025-2030中國螺旋藻提取物行業市場發展趨勢與前景展望戰略研究報告
- 江蘇省南京市2021年中考道德與法治真題試卷(含答案解析)
- 科室業務學習計劃安排表
- 校舍抗震安全鑒定服務投標方案
- 2023年河南測繪職業學院單招考試職業適應性測試試題及答案解析
- Python自然語言處理-課件-第05章-詞向量與關鍵詞提取
- 五年級下冊綜合實踐活動教學設計-有趣的拉線偶人 全國通用
- 醫療廢物管理PPT演示課件
- 海康監控陣列不可用數據不保留處理
- 卓越密碼:如何成為專家
- 合肥經濟技術開發區公開招聘村(居)社區工作者模擬備考預測(共1000題含答案解析)綜合試卷
- 外派勞務人員基本情況表(勞工表)
評論
0/150
提交評論