(完整版)線性分組碼編碼的分析與實現(xiàn)

1、課程設(shè)計任務(wù)書20112012學(xué)年第一學(xué)期專業(yè)： 通信工程學(xué)號: 080110501 姓名： 李瓊課程設(shè)計名稱：信息論與編碼課程設(shè)計設(shè)計題目：線性分組碼編碼的分析與實現(xiàn)完成期限：自2011年12月19 日至2011年12月25日共1周1、深刻理解信道編碼的基本思想與目的；2、理解線性分組碼的基本原理與編碼過程；3、提高綜合運用所學(xué)理論知識獨立分析和解決問題的能力；4、使用MATLAB或其他語言進行編程。二.設(shè)計內(nèi)容給定消息組M及生成矩陣G,編程求解其線性分組碼碼字。三.設(shè)計要求編寫的函數(shù)要有通用性。四.設(shè)計條件計算機、MATLAB或其他語言環(huán)境五.參考資料1曹雪虹，張宗橙.信息論與編碼.北京：

2、清華大學(xué)出版社，2007.2王慧琴.數(shù)字圖像處理.北京：北京郵電大學(xué)出版社，2007.指導(dǎo)教師（簽字）： 教研室主任（簽字）： 批準(zhǔn)日期：年 月 日摘要該系統(tǒng)是（6， 3）線性分組碼的編碼的實現(xiàn)，它可以對輸入的三位的信息碼進行線性分組碼編碼。當(dāng)接收到的六位碼字中有一位發(fā)生錯誤時，可以糾正這一位錯碼；當(dāng)接收到的碼字有兩位發(fā)生錯誤時，只能糾正一位錯誤，但同時能檢測出另一位錯誤不能糾正。 只有特定位有兩位錯誤時，才能糾正兩位錯誤。這樣就譯出正確的信息碼組，整個過程是用MATLAB 語言實現(xiàn)的。關(guān)鍵詞： 編碼； MA TLAB ；糾錯目錄1 課程描述0.2 設(shè)計原理1.2.1 線性分組碼的編碼1.2.

3、1.1 生成矩陣1.2.1.2 校驗矩陣3.2.2 伴隨式與譯碼4.2.2.1 碼的距離及糾檢錯能力4.2.2.2 伴隨式與譯碼4.3 設(shè)計過程5.3.1 編碼過程5.3.2 仿真程序7.3.4 結(jié)果分析11總 結(jié) 1.3.致謝 1.4.參考文獻1.5.1課程描述線性分組碼具有編譯碼簡單，封閉性好等特點，采用差錯控制編碼技術(shù)是提 高數(shù)字通信可靠性的有效方法，是目前較為流行的差錯控制編碼技術(shù)。對線性分組碼的討論都在有限域 GF（2）上進行，域中元素為0,1,域中元素 計算為模二加法和模二乘法。分組碼是一組固定長度的碼組，可表示為（ n , k）, 通常它用于前向糾錯。在分組碼中，監(jiān)督位被加到信息

4、位之后，形成新的碼。在 編碼時，k個信息位被編為n位碼組長度，而n-k個監(jiān)督位的作用就是實現(xiàn)檢錯 與糾錯。對于長度為n的二進制線性分組碼，它有種 2n可能的碼組，從2n種碼組 中，可以選擇M=2k個碼組（k<n）組成一種碼。這樣，一個k比特信息的線性 分組碼可以映射到一個長度為 n碼組上，該碼組是從 M=2k個碼組構(gòu)成的碼集 中選出來的，這樣剩下的碼組就可以對這個分組碼進行檢錯或糾錯。要設(shè)計一個（6, 3）線性分組碼的編譯碼程序，最基本的是要具備對輸入的 信息碼進行編碼，讓它具有抗干擾的能力。同時，還要讓它具有對接收到的整個 碼組中提取信息碼組的功能。但是，在實際的通信系統(tǒng)中，由于信道傳

5、輸特性不 理想以及加性噪聲的影響，接收到的信息中不可避免地會發(fā)生錯誤， 影響通信系 統(tǒng)的傳輸可靠性，因而，本設(shè)計還要讓該程序具有糾正錯誤的能力， 當(dāng)接收到的 碼組中有一位碼，發(fā)生錯誤時可以檢測到這一位錯碼，并且可以糾正這一位錯碼， 并且讓系統(tǒng)從糾正后的碼組中提取正確的信息碼組。針對給定的矩陣Q二0 1 11 0 11 1 0k J完成如下的工作:1完成對任意信息序列的編碼2根據(jù)生成矩陣，形成監(jiān)督矩陣；3根據(jù)得到的監(jiān)督矩陣，得到伴隨式，并根據(jù)它進行譯碼;4驗證工作的正確性。2設(shè)計原理2.1 線性分組碼的編碼2.1.1 生成矩陣線性分組碼（n, k）中許用碼字（組）為2k個。定義線性分組碼的加法為

6、 模二加法，乘法為二進制乘法。即 1+1=0、1+0=1、0+1=1、0+0=0; 1X1=1、1X0=0、 0>0=0、0X=0。且碼字孰=Si / i,八）與碼"% =（小，”口用的運算 在各個相應(yīng)比特位上符合上述二進制加法運算規(guī)則。線性分組碼具有如下性質(zhì)（n, k）的性質(zhì)：1、封閉性。任意兩個碼組的和還是許用的碼組。2、碼的最小距離等于非零碼的最小碼重。對于碼組長度為n、信息碼元為k位、監(jiān)督碼元為r=n-k位的分組碼，常 記作（n, k）碼，如果滿足2r-1>則有可能構(gòu)造出糾正一位或一位以上錯誤 的線性碼。下面我們通過（7, 3）分組碼的例子來說明如何具體構(gòu)造這種線

7、性碼。設(shè)分 組碼（n, k）中，k = 3,為能糾正一位誤碼，要求r現(xiàn)取r=4,則n=k+r =7。該例子中，信息組為（c6c5c4）,碼字為（c6c5c4c3c2C1C0）.當(dāng)已知信息組時，按 以下規(guī)則得到四個校驗元，即03=c6+c4c2=c6+c5+c4（2-1）j G=c6+c5 c0=c5+c4 這組方程稱為校驗方程。'（7, 3）線性分組碼有23 （8）個許用碼字或合法碼字，另有 27-23個禁用 碼字。發(fā)送方發(fā)送的是許用碼字，若接收方收到的是禁用碼字，則說明傳輸中發(fā) 生了錯誤。為了深化對線性分組碼的理論分析， 可將其與線性空間聯(lián)系起來。由于每個 碼字都是一個二進制的n重，

8、及二進制n維線性空間Vn中的一個矢量，因此碼 字又稱為碼矢。線性分組碼的一個重要參數(shù)是碼率 r=k/n,它說明在一個碼字中信息位所占的比重，r越大，說明信息位所占比重越大，碼的傳輸信息的有效性越高。由于(n,k)線性分組，線性分組碼的2k個碼字組成了 n維線性空間Vn的一個K維子空間。因此這2k個碼字完全可由k個線性無關(guān)的矢量所組成。設(shè)此k個矢量為？,0,或,有生成矩陣形式為C1C2G=(2-2),Ck< J(n,k)碼字中的任一碼字q,均可由這組基底的線性組合生成，即 c=mi , G=m-i mn-2 mn-k , G式中，mi=mn-i mn-2 mn-k 是k個信息元組成的信息組

9、。表2-1(7, 3)線性分組碼信息組碼字0000000000001001110101001001110110111010100100110101101001111011010011111110100對于表2-1給出的(7, 3)線性分組碼，可將寫成矩陣形式5 0 0 1 1 1 9C6 C5 C4 C3 C2 C1 Co=C6 C5 C4 - 0 1 0 0 1 1 10 0 1 110 1<J故（7, 3）碼的生成矩陣為001110、G= 01001110 0 1110 1<J可以看到，從（7,3）碼的8個碼字中，挑選出k=3個線性無關(guān)的碼字（100111。（010011D,

10、（0011110D作為碼的一組基底，用 C=mG計算得碼字。一個系統(tǒng)碼的生成矩陣G,其左邊k行k列應(yīng)是一個k階單位方陣Ik,因此生成矩陣G表示為G=IkP（2-3）式中，P是一個kx（n-k）階矩陣。2.1.2校驗矩陣表2-1所示的（7, 3）線性分組碼的四個校驗元由式（2-1）所示的線性方 程組決定的。把（2-1）移相，有<c6+c4+c3=0(2-4)0-000c6+c5+c4+c2=0 c6+c1+c5=0c5+c4+c0=0上式的矩陣形式為c61 00 10 00 0C5c4c3c2c1C0j這里的四行七列矩陣稱為（7, 3）碼的一致校驗矩陣，用H表示，即H=0111110110

11、0001000010(2-5)由H矩陣得到(n,k)線性分組碼的每一碼字Ci,(i=1,2,2k),都必須滿足由H矩陣各行所確定的線性方程組，即 G HT=0. (7, 3)碼的生成矩陣G中每一行及其線 性組合都是(n,k)碼的碼字，所以有G - HT =00由G和H構(gòu)成的行生成的空 間互為零空間，即G和H彼此正交。H=PT Ir其右邊r行r列組成一個單位方陣。2.2伴隨式與譯碼2.2.1 碼的距離及糾檢錯能力1 .碼的距離兩個碼字之間，對應(yīng)位取之不同的個數(shù)，稱為漢明距離，用 d表示。一個嗎 的最小距離dmin定義為dmin=mind(ci,c),i Wj,ci,c (n,k),兩個碼字之間的

12、距離表 示了它們之間差別的大小。距離越大，兩個碼字的差別越大，則傳送時從一個碼 字錯成另一碼字的可能性越小。碼的最小距離愈大，其抗干擾能力愈強。2 .線性碼的糾檢錯能力對于任一個(n,k)線性分組碼，若要在碼字內(nèi)(1)檢測出e個錯誤，則要 求碼的最小距離d>e+1;(2)糾正t個錯誤，則要求碼的最小距離d>2t+1;(3)糾正 t個錯誤同時檢測e(> t)個錯誤，則要求d>t+e+1；2.2.2 伴隨式與譯碼假設(shè)接收端收到的碼字為B,那么它和原來發(fā)送端發(fā)送的碼字 A之間就有可能 存在著誤差。即在碼組 a= a6 a a4 % &日汝中的任意一位就有可能出錯。這

13、樣我們在接收端接收到一個碼組是就有可能判斷錯發(fā)送端原來應(yīng)該要表達的意 思。為了描述數(shù)據(jù)在傳輸信道中出現(xiàn)錯誤的情況，引入了錯誤圖樣E,在錯誤圖 樣中，0代表對應(yīng)位沒有傳錯，1代表傳輸錯誤。實際上錯誤圖樣 E就是收序列 與發(fā)送序列的差。所以在譯碼中用接收到的碼字 B模爾加錯誤圖樣E就可以得 到發(fā)送端的正確碼字A。因此譯碼的過程就是要找到錯誤圖樣 E。定義：校正子SS = B * H T = ( A + E ) * HT=A * H T+ E * H T=E * H T因為A是編得的正確碼字。根據(jù)前面所敘述，它和監(jiān)督矩陣的轉(zhuǎn)置相乘為 00 顯然，S僅與錯誤圖樣有關(guān)，它們之間是一一對應(yīng)的關(guān)系。找到了校

14、正子 S,也 就可以找到E。而與發(fā)送的碼字無關(guān)。若 E=0,則S=0;因此根據(jù)S是否為0可 進行碼字的檢錯。如果接收碼字B中只有一位碼元發(fā)生錯誤，又設(shè)錯誤在第 i位。即Ei-i=1，其他 的Ei均為0。在后面的譯碼程序中，建立了一個校正子S與錯誤圖樣E對應(yīng)的表。 也就是收到一個B序列，就可以通過計算得到一個校正子，而每一個校正子都 對應(yīng)著一個錯誤圖樣E,再通過B模爾加上E,就可以得到正確的碼字 Ao因為在不同的錯誤序列B中，同一位碼元錯誤時對應(yīng)的 E是一樣的，所以可 以利用0000000這個正確的碼字讓它每位依次錯誤， 來求得它的八個校正子。而 這時的矩陣B就是錯誤圖樣Eo這樣就算得了 8個校

15、正子So而這時的錯誤序列B,就是錯誤圖樣E,所以有： E與S都已經(jīng)得到，這時就可以建立一個表來將它們一一對應(yīng)起來。3設(shè)計過程3.1編碼過程監(jiān)督矩陣H與生成矩陣G的關(guān)系：由H與G的分塊表示的矩陣形式H =P I n-k(3-1 )(3-1)G=I k Q(3-2 ) (3-2)p=Qt(3-3 )(3-3)(3-4)(3-5)則有GHT=0或 H - 6=0已知給出的(6, 3)碼的Q矩陣(3-9)Q=r0 i ii o ii i oIJ(3-6)則可以根據(jù)G=I k Q求出生成矩陣I 0 0 0 1 1、G= 0 10 10 10 0 11101 J由 P = Q和H =P I n-k可求出監(jiān)

16、督矩陣H為(3-7)H=01110 010 1 0 1 011 0 0 0 1<J有了生成矩陣后則可以根據(jù)輸入的四位信息位和生成矩陣相乘得到編碼矩陣,MATLA就數(shù)為:C=rem(I*G,2);其中C為編碼后的結(jié)果，I為信息矩陣，G為生成矩陣。 則編碼的所有情況為：(3-8)編碼序列:信息位| 監(jiān)督位C=0000010100111001011101110001101010110111011100003.2 仿真程序% H 監(jiān)督矩陣% G 生成矩陣% C 編碼矩陣% I 輸入信息序列% R 信道輸出碼% A 糾錯輸出碼序列% E 錯碼矩陣% S 校驗子矩陣% M 校驗子的行的十進制序列%信

17、道編碼程序clear allclose allH=0 1 1 1 0 0;1 0 1 0 1 0;% 監(jiān)督矩陣H%求 H 陣的生成矩陣G1 1 0 0 0 1;G=gen2par(H);I=0 0 0;0 0 1;0 1 0;0 1 1;1 0 0;1 0 1;1 1 0;1 1 1;C=rem(I*G,2);disp('所得的編碼結(jié)果為：C=');disp(C);%信道譯碼程序clear all;close all;H=0 1 1 1 0 0;1 0 1 0 1 0;1 1 0 0 0 1;B=input('請輸入接收碼組B:');a,b=size(B);%求

18、碼字C%顯示輸出碼字C%監(jiān)督矩陣H%返回數(shù)組B 的維數(shù)E=0 0 0 0 0 0;0 0 0 0 0 1;0 0 0 0 1 0;0 0 0 1 0 0;0 0 1 0 0 0;0 1 0 0 0 0;1 0 0 0 0 0;1 0 0 1 0 0;S=rem(B*H',2);%求校驗子Si=1;for i=1:1:aM(i,1)=S(i,1).*4+S(i,2).*2+S(i,3);%求校驗子所表示的十進制整數(shù)endfor i=1:1:aswitch(M(i,1)case 0A(i,:)=B(i,:)+E(1,:);case 1A(i,:)=B(i,:)+E(2,:);case 2A

19、(i,:)=B(i,:)+E(3,:);case 3A(i,:)=B(i,:)+E(4,:);case 4A(i,:)=B(i,:)+E(5,:);case 5A(i,:)=B(i,:)+E(6,:);case 6A(i,:)=B(i,:)+E(7,:);case 7A(i,:)=B(i,:)+E(8,:);endendfor i=1:1:aswitch（M（i,1）case 0disp（沒有出現(xiàn)錯誤?。籧ase 1disp（注意：第1位出現(xiàn)一個錯誤！請糾正?。?；case 2disp（注意：第2位出現(xiàn)一個錯誤！請糾正！）case 3disp（注意：第3位出現(xiàn)一個錯誤！請糾正！）；case 4

20、disp（注意：第4位出現(xiàn)一個錯誤！請糾正?。?；case 5disp（注意：第5位出現(xiàn)一個錯誤！請糾正?。籧ase 6disp（注意：第6位出現(xiàn)一個錯誤！請糾正?。籧ase 7case 8 ：第6位和第3位出現(xiàn)兩個錯誤！請糾正?。?endendA=rem（A,2）;%求出正確的編碼disp（檢糾錯后的碼組A='）;disp（A）;%顯示正確的編碼j=1;while j<=3%提取信息位I（:,j）=A（:,j）;j=j+1;enddisp（'譯出的信息序列I='）;%顯示原信息碼disp(I);3.3 仿真結(jié)果圖1 輸出編碼結(jié)果及輸入正確接收碼的譯碼結(jié)果,根據(jù)

21、仿真程序得出仿真結(jié)果如下圖所示：3-1 輸出編碼結(jié)果和正確輸入時顯示圖2輸入一位錯誤時的結(jié)果顯示圖3-2 有一位錯誤輸入時的顯示圖3輸入兩位特定位錯誤時的結(jié)果顯示不 所得的碗的結(jié)果的;c=00a000Q01110010101011Q1110001110110110110111D00請輸入接收碼鈿B:1 0 1 00注意：第6位將第3位出現(xiàn)兩個槽誤，諳到正，檢糾錯后的同組后0000譯出的信息序列工二 000»圖3-3有兩位特定位錯誤輸入時的顯示圖3.4 結(jié)果分析1 .輸出編碼結(jié)果及輸入正確接收碼的譯碼結(jié)果分析由圖3-1輸出編碼結(jié)果和正確輸入時顯示圖所示的結(jié)果可以看出編碼的結(jié)果 的八種情

22、況和在推導(dǎo)過程中運算的結(jié)果是一致的，可以見得程序的編碼過程是正確的。對于譯碼過程而言，當(dāng)界面顯示“請輸入接收碼組B:" ，然后從提示符后輸入：0 0 0 1 0 0,由于輸入的接收碼組與編碼后的碼字一致，它提取了每個 碼組的前四位，即信息位，由結(jié)果看出譯碼過程是正確的，并沒有出現(xiàn)錯譯的情 況，可見程序的譯碼片段是正確的。2 .輸入一位錯誤時的結(jié)果分析對于糾錯過程而言，當(dāng)界面顯示“請輸入接收碼組 B:" 。然后從提示符后輸 入：1 1 1 1 1 0,由圖3-2有一位錯誤輸入時的顯示圖所知， 接收碼組的第五位 發(fā)生了錯誤，經(jīng)程序糾檢錯誤后改正了接收序列的錯誤，并且正確譯出了信

23、息位。 可見程序的糾錯功能也是可以實現(xiàn)的， 以上結(jié)果進一步證實了，系統(tǒng)譯碼程序的 正確性。3 .輸入兩位特定位錯誤時的結(jié)果分析3-3 有兩位特定位錯誤輸入時的顯示圖知，當(dāng)輸入B=1 0 0 1 0 0時，校正111，錯誤圖樣是100100，所以結(jié)果顯示與理論相符。總結(jié)通過對線性分組碼中的線性分組碼的編碼編程實現(xiàn)，了解到線性分組碼的構(gòu)成方式是把信息序列分成每k 個碼元一段，并由這 k 個碼元按一定規(guī)則產(chǎn)生r 個校驗位，組成長度為n=k+r 的碼字，用（n ， k） 表示。信息碼元與校驗位之間為線性關(guān)系。 并且知道了線性分組碼的編碼過程信息碼元與校驗位之間的線性關(guān)系實現(xiàn)起來是十分簡單的.對于碼組長度為n、信息碼元為k位、監(jiān)督碼元為r = n-k位的分組碼，如 果滿足2r-1>n,則有可能構(gòu)造出糾正一位或一位以上錯誤的線性碼。就像本 設(shè)計的（6, 3）分組碼的（n, k）中，n=6, k = 3, r>3能糾正一位誤碼，檢測 到兩位誤碼。運用 MATLAB 語言進行編程