線性分組碼編碼分析與實現(xiàn)(共21頁)

1、精選優(yōu)質文檔-傾情為你奉上吉林建筑大學電氣與電子信息工程學院信息理論與編碼課程設計報告設計題目：線性分組碼編碼的分析與實現(xiàn)專業(yè)班級： 電子信息工程 111 學生姓名： 學 號： 指導教師： 設計時間： 2014.11.242014.12.5 教師評語：成績 評閱教師 日期 第1章 概述1.1設計的作用、目的1、通過完成具體編碼算法的程序設計和調試工作，提高編程能力，深刻理解信源編碼、信道編譯碼的基本思想。2、加深對理論知識的理解，提高實踐技能，培養(yǎng)獨立分析問題及解決問題的能力。3、掌握編碼的基本原理與編碼過程，增強邏輯思維能力。 4、使用MATLABH或其他語言進行編程及實現(xiàn)。1.2設計任務及

2、要求設計一個（7,3）線性分組碼的編譯碼程序，完成對任意序列的編碼，根據(jù)生成矩陣形成監(jiān)督矩陣，得到伴隨式下，并根據(jù)其進行譯碼，同時驗證工作的正確性，最基本的是要具備對輸入的信息碼進行編碼，讓它具有抗干擾的能力。1. 理解無失真信源編碼的理論基礎，掌握無失真信源編碼的基本方法； 2. 掌握哈夫曼編碼/費諾編碼方法的基本步驟及優(yōu)缺點；3. 深刻理解信道編碼的基本思想與目的，理解線性分組碼的基本原理與編 碼過程 4. 能夠使用MATLAB或其他語言進行編程，編寫的函數(shù)要有通用性。1.3設計內容已知一個（7,3）線性分組碼的校驗元與信息元有如下限定關系。設碼字為(c1,c2, c3, c4, c5,

3、c6,c7) 求出標準校驗矩陣、Q矩陣、標準生成矩陣，完成對任意信息序列（23個許用碼字）的編碼。當接收碼字分別為(), (), (), (), (), (), (), (), ()時，寫出其伴隨式S，以表格形式寫出伴隨式與錯誤圖樣E的對應關系，糾錯并正確譯碼，當有兩位錯碼時，假定為c5位和c2位發(fā)生錯誤。第2章 線性分組碼編碼分析與實現(xiàn)2.1設計原理1. 線性分組碼的生成矩陣和校驗矩陣（1）（n，k）線性分組碼的性質1、封閉性。任意兩個碼組的和還是許用的碼組。2、碼的最小距離等于非零碼的最小碼重。對于長度為n的二進制線性分組碼，它有種2n可能的碼組，從2n種碼組中，可以選擇M=2k個碼組（k

4、<n）組成一種碼。這樣，一個k比特信息的線性分組碼可以映射到一個長度為n碼組上，該碼組是從M=2k個碼組構成的碼集中選出來的，這樣剩下的碼組就可以對這個分組碼進行檢錯或糾錯。對于碼組長度為n、信息碼元為k位、監(jiān)督碼元為rnk位的分組碼，常記作（n，k）碼，如果滿足2r1n，則有可能構造出糾正一位或一位以上錯誤的線性碼。（2）生成矩陣和校驗矩陣 線性分組碼碼空間是由個線性無關的基底，張成的維重子空間，碼空間的所有元素(即碼字)都可以寫成個基底的線性組合，即 這種線性組合特性正是線性分組碼名稱的來歷。顯然，研究線性分組的關鍵是研究基底、子空間和映射規(guī)則，可把子空間和映射關系畫成如圖一所示的圖

5、形。k維k重信組空間mn維n重空間 n-k維n重對偶空間Dk維k重碼空間cGH 圖2.1 碼空間與映射用表示第個基底并寫成矩陣形式再將個基底排列成行列的矩陣，得： 由于個基底即的個行矢量線性無關，矩陣的秩一定等于，當信息元確定后，碼字僅由矩陣決定，因此稱這矩陣為該線性分組碼的生成矩陣?；撞皇俏ㄒ坏模删仃囈簿筒皇俏ㄒ坏?。事實上，將個基底線性組合后產(chǎn)生另一組個矢量，只要滿足線性無關的條件，依然可以作為基底張成一個碼空間。不同的基地有可能生成同一個碼集，但因編碼涉及碼集和映射兩個因素，碼集一樣而映射方法不同也不能說是同樣的碼。基底的線性組合等效于生成矩陣的行運算，可以產(chǎn)生一組新的基底。利用這點

6、可使生成矩陣具有如下的“系統(tǒng)形式”： 這里是矩陣；是單位矩陣，從而保證了矩陣的秩是。與任何一個分組線性碼的碼空間相對應，一定存在一個對偶空間。事實上，碼空間基底數(shù)只是維重空間全部個基底的一部分，若能找出另外個基底，也就找到了對偶空間。既然用個基底能產(chǎn)生一個分組線性碼，那么也就能用個基底產(chǎn)生包含個碼字的分組線性碼，稱碼是碼的對偶碼。將空間的個基底排列起來可構成一個矩陣，將這個矩陣稱為碼空間的校驗矩陣，而它正是對偶碼的生成矩陣，它的每一行是對偶碼的一個碼字。和的對偶是互相的，是的生成矩陣又是的校驗矩陣，而是的生成矩陣，又是的校驗矩陣。由于的基底和的基底正交，空間和空間也正交，它們互為零空間。因此，

7、線性碼的任意碼字一定正交于其對偶碼的任意一個碼字，也必定正交于校驗矩陣的任意一個行矢量，即。由于生成矩陣的每個行矢量都是一個碼字，因此必有。對于生成矩陣符合“系統(tǒng)形式”的系統(tǒng)碼，其校驗矩陣也是規(guī)則的，必為： 上式中的負號在二進制碼情況下可以省略，因為模2減法和模2加法是等同的。（3）信息碼元及對應碼字的關系（n，k）碼字中的任一碼字，均可以由這組基底的線性組合生成，即 式中的是個信息元組的信息組，因此其信息碼元及對應碼字的關系如表一所示：表2.1 信息碼元及對應碼字關系信息組碼字0000010100111001011101112. 線性分組碼的伴隨式與譯碼 （1）碼的距離及檢錯能力兩個碼字之間

8、，對應位取之不同的個數(shù)，稱為漢明距離，用d表示。一個碼的最小距離定義為,兩個碼字之間的距離表示了它們之間差別的大小。距離越大，兩個碼字的差別越大，則傳送時從一個碼字錯成另一碼字的可能性越小。碼的最小距離愈大，其抗干擾能力愈強。任何最小距離的線性分組碼，其檢錯能力為糾錯能力t為 最小距離表明碼集中各碼字差異的程度，差異越大越容易區(qū)分，抗干擾能力自然越強，因此成了衡量分組碼性能最重要的指標之一。估算最小距離是糾錯碼設計的必要步驟，最原始的方法是逐一計算兩兩碼字間距離，找到其中最小者。含個碼字的碼集需計算個距離后才能找出，費時太多，實用中還有一些更好更快的方法。線性分組碼的最小距離等于碼集中時非零碼

9、字的最小重量，即 式中，符號 表示 重量（1的個數(shù)）。這里利用了群的封閉性，由于分組碼是群碼，任意兩碼字之和仍是碼字，即。因此任意兩碼字間的漢明距離其實必是另一碼字的重量，表示為成下面公式形式。于是可將最小距離問題轉化為尋找最輕碼字問題，含個碼字的碼集僅需計算次。碼的檢錯能力取決于碼的最小距離，但還需說明的另一點是碼的總體檢錯能力不僅僅與有關。檢錯能力只是說明距離的差錯一定能糾，并非說距離大于的差錯一定不能糾。事實上，如果有個碼子，就存在 個距離，這并非相等的。比如最小距離 ，檢錯力 ，是由碼的距離決定，只要 朝 方向偏差大于1就會出現(xiàn)譯碼差錯；然而若朝方向偏差3，譯碼時仍可正確地判斷為而非。

10、可見，總體的、平均的糾錯能力不但與最小距離有關，而且與其余碼距離或者說與碼子的重量分布特性有關，把碼距（碼重）的分布特性稱為距離（重量）譜，其中最小的重量就是。正如信息論各符號等概時熵最大一樣，從概念上可以想象到:當所有碼距相等時是（重量譜為線譜）碼的性能應該最好；或者退一步說，當各碼距相當不大時（重量譜為窄譜）性能應該叫好。事實證明確實如此，在同樣的條件下，窄譜的碼一般比寬譜的碼更優(yōu)。糾錯重量譜的研究具有理論與現(xiàn)實意義，不僅僅是計算各種譯碼差錯概率的主要依據(jù)，也是研究碼的結構、改善碼集內部關系從而發(fā)現(xiàn)新的好碼的重要工具。但目前除了少數(shù)幾類碼如漢明碼、極長碼等的重量分布已知外，還有很多碼的重量

11、分布并不知道，距離分布與性能之間確切的定量關系對于大部分碼而言尚在進一步研究當中，特別當 和 較大時，要得出碼重分布是非常困難的。 重量譜可以如下多項式來表示，稱為重量算子，即 式中的含義：在碼長的碼集里，包括重量為0的碼子個（線性碼一定包含一個重量為0的全0碼），碼重為1的碼字個，重量為n的碼字個。（2）伴隨式與譯碼 碼字在傳輸過程中受到各種干擾，接收端收碼已不一定等于發(fā)碼，兩者間的差異就是差錯，差錯是多樣化的，我們定義差錯的式樣為差錯圖樣,即 對于二進制碼，模2減等同模2加，因此有 利用碼字與校驗矩陣的正交性，可檢驗收碼是否錯誤,即 定義運算結果為伴隨式,即 可見，雖然本身與發(fā)碼有關，但乘

12、以后的伴隨式 僅與差錯圖有關，只反映信道對碼字造成怎樣的干擾而與發(fā)什么碼無關了。于是可以先利用收碼和已知的算出的伴隨式；再利用算出差錯圖樣。這種思路下的編譯碼過程如圖所示。在此過程中，和的計算都是確定性的，而從計算卻帶有隨機性。這是因為伴隨式是一個重失量，二進制時只有種肯那個的組合，而差錯圖樣是重失量，有種可能的組合，因此與不存在一一對應關系。假設接收端收到的碼字為，那么它和原來發(fā)送端發(fā)送的碼字之間就有可能存在著誤差。即在碼組中的任意一位就有可能出錯。這樣我們在接收端接收到一個碼組是就有可能判斷錯發(fā)送端原來應該要表達的意思。為了描述數(shù)據(jù)在傳輸信道中出現(xiàn)錯誤的情況，引入了錯誤圖樣，在錯誤圖樣中，

13、0代表對應位沒有傳錯，1代表傳輸錯誤。實際上錯誤圖樣就是收序列與發(fā)送序列的差。所以在譯碼中用接收到的碼字模爾加錯誤圖樣就可以得到發(fā)送端的正確碼字。因此譯碼的過程就是要找到錯誤圖樣E。 定義：校正子 因為是編得的正確碼字。根據(jù)前面所敘述，它和監(jiān)督矩陣的轉置相乘為0。顯然，僅與錯誤圖樣有關，它們之間是一一對應的關系。找到了校正子，也就可以找到。而與發(fā)送的碼字無關。若，則；因此根據(jù)是否為0可進行碼字的檢錯。如果接收碼字中只有一位碼元發(fā)生錯誤，又設錯誤在第位。即,其他的均為0。在后面的譯碼程序中，建立了一個校正子與錯誤圖樣對應的表。也就是收到一個序列，就可以通過計算得到一個校正子，而每一個校正子都對應

14、著一個錯誤圖樣，再通過模爾加上，就可以得到正確的碼字。因為在不同的錯誤序列中，同一位碼元錯誤時對應的是一樣的，所以可以利用這個正確的碼字讓它每位依次錯誤，來求得它的八個校正子。而這時的矩陣就是錯誤圖樣。2.2設計步驟1. 編碼過程根據(jù)已知檢驗元與信息的關系，設碼字為(c1,c2, c3, c4, c5, c6,c7) 在由監(jiān)督矩陣和生成矩陣的關系如下： 由與的分塊的矩陣形式，,。可以求出生成矩陣和監(jiān)督矩陣。 有了生成矩陣后可以根據(jù)輸入的四位信息位和生成矩陣相乘得到編碼矩陣，即MATLAB函數(shù)為：其中為編碼后的結果，為信息矩陣，為生成矩陣。則編碼所有情況為：編碼序列： 信息位 | 監(jiān)督位 2.

15、譯碼過程對于譯碼過程來說，由上面可知道監(jiān)督矩陣：矩陣與碼的任何一個許用碼字進行相乘的結果必等于0，即若是任一碼字，則必有。若不屬于許用碼字，或有傳輸差錯，且差錯位數(shù)在碼糾錯能力內，則運算結果將為非0值，此時，可以糾錯或檢錯重發(fā)。 設接收的碼字(c1,c2,c3,c4,c5,c6,c7)，c1為第七位，c7為第一位，則：(1)當接收碼字為（）時：所以此時接收編碼無錯誤。（2） 當接收碼字為（）時：所以，此時接收編碼第一位發(fā)生錯誤，糾錯后的正確譯碼為（）。 （3）當接收碼字為（）時：所以，此時接收編碼第二位發(fā)生錯誤，糾錯后的正確譯碼為（）。（4）當接收碼字為（）時：所以，此時接收編碼第三位發(fā)生錯誤

16、，糾錯后的正確譯碼為（）。（5）當接收碼字為（）時：所以，此時接收編碼第四位發(fā)生錯誤，糾錯后的正確譯碼為（）。（6）當接收碼字為（）時： 所以，此時接收編碼第五位發(fā)生錯誤，糾錯后的正確譯碼為（）。（7）當接收碼字為（）時：所以，此時接收編碼第六位發(fā)生錯誤，糾錯后的正確譯碼為（）。（8）當接收碼字為（）時：所以，此時接收編碼c5位和c2位發(fā)生錯誤，糾錯后的正確譯碼（）。當編碼矩陣與生成矩陣的轉置矩陣相乘時，若當其中的一位編碼或兩位出現(xiàn)差錯時會有八種情況，則這些情況列出錯碼矩陣如下表二：表2.2 伴隨式與錯誤圖樣的對應關系校正子 差錯圖樣 00000001001001001000110101111

17、1100011第3章 仿真程序及結果分析3.1 仿真程序% H 監(jiān)督矩陣% G 生成矩陣 % C 編碼矩陣% I 輸入信息序列 % B 信道輸出碼 % A 糾錯輸出碼序列 % E 錯碼矩陣% S 校驗子矩陣% M 校驗子的行的十進制序列%信道編碼程序 clear all close all H=1 0 1 1 0 0 0; 1 1 1 0 1 0 0; 1 1 0 0 0 1 0; 0 1 1 0 0 0 1; %監(jiān)督矩陣H G=gen2par(H); %求H陣的生成矩陣G 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

18、,2); %求碼字C disp('所得的編碼結果為:C='); %顯示輸出碼字C disp(C); %信道譯碼程序 clear all; close all; H=1 0 1 1 0 0 0; 1 1 1 0 1 0 0; 1 1 0 0 0 1 0; 0 1 1 0 0 0 1; %監(jiān)督矩陣H B=input('請輸入接收碼組B:'); a,b=size(B); %返回數(shù)組R的維數(shù) E=0 0 0 0 0 0 0;0 0 0 0 0 0 1;0 0 0 0 0 1 0;0 0 0 0 1 0 0; 0 0 0 1 0 0 0; 0 0 1 0 0 0 0;0

19、1 0 0 0 0 0;0 1 0 0 1 0 0; S=rem(B*H',2); %求校驗子Si=1; for i=1:1:a M(i,1)=S(i,1).*8+S(i,2).*4+S(i,3).*2+S(i,4); %求校驗子所表示的十進制整數(shù) end for i=1:1:a switch(M(i,1) case 0 A(i,:)=B(i,:)+E(1,:); case 1 A(i,:)=B(i,:)+E(2,:); case 2 A(i,:)=B(i,:)+E(3,:); case 4 A(i,:)=B(i,:)+E(4,:); case 8 A(i,:)=B(i,:)+E(5,

20、:); case 13 A(i,:)=B(i,:)+E(6,:); case 7 A(i,:)=B(i,:)+E(7,:); case 14 A(i,:)=B(i,:)+E(8,:); end endfor i=1:1:a switch(M(i,1) case 0 disp('沒有出現(xiàn)錯誤！'); case 1 disp('注意：第1位出現(xiàn)一個錯誤！請糾正！'); case 2 disp('注意：第2位出現(xiàn)一個錯誤！請糾正！'); case 4 disp('注意：第3位出現(xiàn)一個錯誤！請糾正！'); case 8 disp('

21、;注意：第4位出現(xiàn)一個錯誤！請糾正！'); case 13 disp('注意：第5位出現(xiàn)一個錯誤！請糾正！'); case 7 disp('注意：第6位出現(xiàn)一個錯誤！請糾正！'); case 14 disp('注意：c2位和c5位出現(xiàn)兩個錯誤！請糾正！'); end endA=rem(A,2); %求出正確的編碼 disp('檢糾錯后的碼組A='); disp(A); %顯示正確的編碼 j=1; while j<=3 %提取信息位 I(:,j)=A(:,j); j=j+1; end disp('譯出的信息序列

22、I='); disp(I);3.2 仿真結果（1） 輸出編碼結果和無錯誤輸入時顯示圖:圖3.1 沒有出現(xiàn)錯誤是的仿真圖（2） 有一位錯誤輸入時顯示圖:圖3.2 第4位出現(xiàn)錯誤時的仿真圖圖3.3 第3位出現(xiàn)錯誤時的仿真圖（3） 有兩位錯誤輸入時顯示圖: 圖3.4出現(xiàn)兩位錯誤時的仿真圖3.3結果分析1輸出編碼結果及輸入正確接收碼的譯碼結果分析由圖可以看出編碼的結果的八種情況和在推導過程中運算的結果是一致的，所以我們可以知道程序的編碼過程是正確的。對于譯碼過程而言，當界面顯示“請輸入接收碼組B：”，然后從提示符后輸入：0 0 0 0 0 0 0，由于輸入的接收碼組與編碼后的碼字一致，它提取了

23、每個碼組的前四位，即信息位，由結果看出譯碼過程是正確的，并沒有出現(xiàn)錯譯的情況，可見程序的譯碼片段是正確的。2輸入一位錯誤時的結果分析由圖可以看出，當界面顯示“請輸入接收碼組B：” 。然后從提示符后輸入：1 0 1 0 0 0，由圖有一位錯誤輸入時的顯示圖所知，接收碼組的第五位發(fā)生了錯誤，經(jīng)程序糾檢錯誤后改正了接收序列的錯誤，并且正確譯出了信息位?？梢姵绦虻募m錯功能也是可以實現(xiàn)的，以上結果進一步證實了，系統(tǒng)譯碼程序的正確性。3輸入兩位特定位錯誤時的結果分析由圖有兩位特定位錯誤輸入時的顯示圖知，當輸入B=0 1 0 0 1 0 0時，校正子是0011，錯誤圖樣是，所以說明理論得以驗證。 第4章 總

24、結通過這次的課程設計，我學習到了很多東西，讓我對線性編碼有了一個全新的認識，對MATLAB的掌握也進步了解很多，為以后的學習中出現(xiàn)的可能問題做好了準備，鍛煉了自己的動手能力和設計能力，掌握了一種科技工具，豐富了自己的學習生活。整個實驗過程中我懂得了許多東西，在查找的過程中我們也知道了許多原來不知道的東西，對于源代碼的修改以及成功利用也樹立了對知識應用的信心，相信會對今后的學習工作和生活有非常大的幫助，并且提高了自己的動手實踐操作能力，使自己充分體會到了在實驗過程中的成功喜悅。讓我對MATLAB軟件有了更深的了解，對MATLAB語言也有了更加深入的學習和理解。在本次的設計中，我了解了MATLAB中很多函數(shù)的用法，提高了我編程的能力，在軟件仿真上，提高了自己的動手能力和學習能力，為以后的學習打下了良好的基礎。通過對線性分組碼中的線性分組碼的編譯碼編程實現(xiàn)，了解到線性分組碼的構成方式是把信息序列分成每k個碼元一段，并由這k個碼元按一定規(guī)則產(chǎn)生r 個校驗位，組成長度為n=k+r的碼字，用(n，k)表示。信息碼元與校驗位之間為線性關系。并且知道了線性分組碼的編碼過程信息碼元與校驗位之間的線性關系實現(xiàn)起來是十分簡單的.對于碼組長