線性分組碼編碼的與實現(xiàn)

1、吉林建筑大學電氣與計算機學院信息理論與編碼課程設計報告 設計題目：線性分組碼編碼的分析與實現(xiàn) 專業(yè)班級： 電子信息工程 121 學生姓名： 學 號： 指導教師： 設計時間： 2016.1.112016.1.22 教師評語：成績 評閱教師 日期 第1章 概述1.1設計的作用、目的信息論與編碼是一門理論與實踐密切結合的課程,課程設計是其實踐性教學環(huán)節(jié)之一，同時也是對課堂所學理論知識的鞏固和補充。其主要目的是加深對理論知識的理解，掌握查閱有關資料的技能，提高實踐技能，培養(yǎng)獨立分析問題、解決問題及實際應用的能力。通過完成具體編碼算法的程序設計和調試工作，提高編程能力，深刻理解信源編碼、信道編譯碼的基本

2、思想和目的，掌握編碼的基本原理與編碼過程，增強邏輯思維能力，培養(yǎng)和提高自學能力以及綜合運用所學理論知識去分析解決實際問題的能力，逐步熟悉開展科學實踐的程序和方法。1.2設計任務及要求線性分組碼具有編譯碼簡單，封閉性好等特點，采用差錯控制編碼技術是提高數字通信可靠性的有效方法，是目前較為流行的差錯控制編碼技術。通過設計一組（7,3）線性分組碼，來完成對任意序列的編碼，根據生成矩陣形成監(jiān)督矩陣，得到伴隨式下，并根據其進行譯碼，同時驗證工作的正確性，最基本的是要具備對輸入的信息碼進行編碼，讓它具有抗干擾的能力。1. 理解無失真信源編碼的理論基礎，掌握無失真信源編碼的基本方法； 2. 掌握哈夫曼編碼/

3、費諾編碼方法的基本步驟及優(yōu)缺點；3. 深刻理解信道編碼思想與目的，理解線性分組碼的基本原理與編碼過程。 4. 能夠使用MATLAB或其他語言進行編程，編寫的函數要有通用性。1.3設計內容已知一個（7,3）線性分組碼的校驗元與信息元有如下限定關系。設碼字為(c6,c5, c4, c3, c2, c1,c0) 。 求出標準校驗矩陣、Q矩陣、標準生成矩陣，完成對任意信息序列（23個許用碼字）的編碼。當接收碼字分別為(0000000),(0000001),(0000010),(0000100),(0001000), (0010000),(0100000),(1000000),(0100100)時，寫出

4、其伴隨式S，以表格形式寫出伴隨式與錯誤圖樣E的對應關系，糾錯并正確譯碼，當有兩位錯碼時，假定為c5位和c2位發(fā)生錯誤。第2章 線性分組碼編碼的分析與實現(xiàn)2.1設計原理1. 線性分組碼的生成矩陣和校驗矩陣（1）線性分組碼的性質 線性分組碼的任意兩個碼組的和還是許用的碼組。碼的最小距離等于非零碼的最小碼重。對于長度為n的二進制線性分組碼，它有2n可能的碼組，從2n種碼組中，可以選擇M=2k個碼組（k<n）組成一種碼。這樣，一個k比特信息的線性分組碼可以映射到一個長度為n碼組上，該碼組是從M=2k個碼組構成的碼集中選出來的，這樣剩下的碼組就可以對這個分組碼進行檢錯或糾錯。對于碼組長度為n、信息

5、碼元為k位、監(jiān)督碼元為rnk位的分組碼，常記作（n，k）碼，如果滿足2r1n，則有可能構造出糾正一位或一位以上錯誤的線性碼。（2）生成矩陣和校驗矩陣 線性分組碼碼空間是由個線性無關的基底，張成的維重子空間，碼空間的所有元素(即碼字)都可以寫成個基底的線性組合，即 這種線性組合特性正是線性分組碼名稱的來歷。顯然，研究線性分組的關鍵是研究基底、子空間和映射規(guī)則，可把子空間和映射關系如圖2.1所示：k維k重信組空間m n維n重空間 n-k維n重對偶空間DGHk維n重碼空間C 圖2.1 碼空間與映射用表示第個基底并寫成矩陣形式，再將個基底排列成行列的矩陣，得： 由于個基底即的個行矢量線性無關，矩陣的秩

6、一定等于，當信息元確定后，碼字僅由矩陣決定，因此稱這矩陣為該線性分組碼的生成矩陣?；撞皇俏ㄒ坏?，生成矩陣也就不是唯一的。事實上，將個基底線性組合后產生另一組個矢量，只要滿足線性無關的條件，依然可以作為基底張成一個碼空間。不同的基地有可能生成同一個碼集，但因編碼涉及碼集和映射兩個因素，碼集一樣而映射方法不同也不能說是同樣的碼?；椎木€性組合等效于生成矩陣的行運算，可以產生一組新的基底。利用這點可使生成矩陣具有如下的“系統(tǒng)形式”： 這里是矩陣；是單位矩陣，從而保證了矩陣的秩是。與任何一個分組線性碼的碼空間相對應，一定存在一個對偶空間。事實上，碼空間基底數只是維重空間全部個基底的一部分，若能找出另

7、外個基底，也就找到了對偶空間。既然用個基底能產生一個分組線性碼，那么也就能用個基底產生包含個碼字的分組線性碼，稱碼是碼的對偶碼。將空間的個基底排列起來可構成一個矩陣，將這個矩陣稱為碼空間的校驗矩陣，而它正是對偶碼的生成矩陣，它的每一行是對偶碼的一個碼字。和的對偶是互相的，是的生成矩陣又是的校驗矩陣，而是的生成矩陣，又是的校驗矩陣。由于的基底和的基底正交，空間和空間也正交，它們互為零空間。因此，線性碼的任意碼字一定正交于其對偶碼的任意一個碼字，也必定正交于校驗矩陣的任意一個行矢量，即。由于生成矩陣的每個行矢量都是一個碼字，因此必有。對于生成矩陣符合“系統(tǒng)形式”的系統(tǒng)碼，其校驗矩陣也是規(guī)則的，必為

8、： 上式中的負號在二進制碼情況下可以省略，因為模二減法和模二加法是等同的。（3）信息碼元及對應碼字的關系（n，k）碼字中的任一碼字，均可以由這組基底的線性組合生成，即 式中的是個信息元組的信息組，因此其信息碼元及對應碼字的關系如表一所示：表2.1 信息碼元及對應碼字關系信息組碼字000000000000100111010100100111011011101010010011101011010011110110100111111101002. 線性分組碼的伴隨式與譯碼 （1）碼的距離及檢錯能力兩個碼字之間，對應位取之不同的個數，稱為漢明距離，用d表示。一個碼的最小距離定義為,兩個碼字之間的距離表

9、示了它們之間差別的大小。距離越大，兩個碼字的差別越大，則傳送時從一個碼字錯成另一碼字的可能性越小。碼的最小距離愈大，其抗干擾能力愈強。任何最小距離的線性分組碼，其檢錯能力為糾錯能力t為 最小距離表明碼集中各碼字差異的程度，差異越大越容易區(qū)分，抗干擾能力自然越強，因此成了衡量分組碼性能最重要的指標之一。估算最小距離是糾錯碼設計的必要步驟，最原始的方法是逐一計算兩兩碼字間距離，找到其中最小者。含個碼字的碼集需計算個距離后才能找出，費時太多，實用中還有一些更好更快的方法。線性分組碼的最小距離等于碼集中時非零碼字的最小重量，即 式中，符號 表示 重量（1的個數）。這里利用了群的封閉性，由于分組碼是群碼

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

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

12、 較大時，要得出碼重分布是非常困難的。 重量譜可以如下多項式來表示，稱為重量算子，即 式中的含義：在碼長的碼集里，包括重量為0的碼子個（線性碼一定包含一個重量為0的全0碼），碼重為1的碼字個，重量為n的碼字個。（2）伴隨式與譯碼 碼字在傳輸過程中受到各種干擾，接收端收碼已不一定等于發(fā)碼，兩者間的差異就是差錯，差錯是多樣化的，我們定義差錯的式樣為差錯圖樣,即 對于二進制碼，模2減等同模2加，因此有 利用碼字與校驗矩陣的正交性，可檢驗收碼是否錯誤,即 定義運算結果為伴隨式,即 可見，雖然本身與發(fā)碼有關，但乘以后的伴隨式 僅與差錯圖有關，只反映信道對碼字造成怎樣的干擾而與發(fā)什么碼無關了?？梢韵壤檬?/p>

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

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

15、可以利用0000000這個正確的碼字讓它每位依次錯誤和兩位特定錯誤，來求得它的八個校正子。而這時的矩陣就是錯誤圖樣。2.2設計步驟1. 編碼過程根據已知檢驗元與信息的關系，設碼字為（c6,c5, c4, c3, c2, c1,c0) 。由上式關系式移相可得如下的關系式： 由移相所得的關系式可以寫出監(jiān)督矩陣和生成矩陣。有了生成矩陣后可以根據輸入的四位信息位和生成矩陣相乘得到編碼矩陣，即MATLAB函數為：其中為編碼后的結果，為信息矩陣，為生成矩陣。則編碼所有情況為： 三位信息碼 四位監(jiān)督碼 2. 譯碼過程 對于譯碼過程來說，由求得的監(jiān)督矩陣： 本設計以（7，3）為例。任何一個碼字與監(jiān)督矩陣（7，

16、3）碼的轉置進行相乘的結果必等于0，即若是任一碼字，則必有。若不屬于許用碼字，或有傳輸差錯，且差錯位數在碼糾錯能力內，則運算結果將為非0值，說明有錯誤出現(xiàn)。在一定的糾錯能力內可以糾錯，當超過糾錯能力時，則不能糾錯。設接收的碼字（c6,c5, c4, c3, c2, c1,c0) ，則：(1) 當接收碼字為（0000000）時： 所以由伴隨矩陣知此時接收編碼無錯誤，糾錯后譯碼為（000000）。（2） 當接收碼字為（0000001）時： 所以由伴隨矩陣知此時接收編碼c0發(fā)生錯誤，糾錯后譯碼為（000000）。（3）當接收碼字為（0000010）時： 所以由伴隨矩陣知此時接收編碼c1發(fā)生錯誤，糾錯

17、后譯碼為（000000）。（4） 當接收碼字為（0000100）時： 所以由伴隨矩陣知此時接收編碼c2發(fā)生錯誤，糾錯后譯碼為（000000）。（5） 當接收碼字為（0001000）時： 所以由伴隨矩陣知此時接收編碼c3發(fā)生錯誤，糾錯后譯碼為（000000）。（6） 當接收碼字為（0010000）時： 所以由伴隨矩陣知此時接收編碼c4發(fā)生錯誤，糾錯后譯碼為（000000）。（7） 當接收碼字為（0100000）時： 所以由伴隨矩陣知此時接收編碼c5發(fā)生錯誤，糾錯后譯碼為（000000）。 （8）當接收碼字為（1000000）時： 所以由伴隨矩陣知此時接收編碼c6發(fā)生錯誤，糾錯后譯碼為（00000

18、0）。 （9）當接收碼字為（0100100）時：所以，此時接收編碼c5位和c2位發(fā)生錯誤，糾錯后的正確譯碼（0000000）。根據所發(fā)生的差錯情況，列出所有錯碼矩陣如下表2.2所示：表2.2 伴隨式與錯誤圖樣的對應關系校正子 差錯圖樣 000000000000001000000100100000010010000001001000000100011010010000011101000001110100000000110100100第3章 仿真程序及結果分析3.1 仿真程序% H 監(jiān)督矩陣% G 生成矩陣 % C 編碼矩陣% I 輸入信息序列 % B 信道輸出碼 % A 糾錯輸出碼序列 % E

19、錯碼矩陣% S 校驗子矩陣% M 校驗子的行的十進制序列%信道編碼程序 clear allclose 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,2); %求碼字C disp('所得的編碼結果為:C='); %顯示輸出碼字C disp(C); %信道譯碼程序 clear all; close all; H=1

20、 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); %返回數組R的維數 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 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

21、).*4+S(i,3).*2+S(i,4); %求校驗子所表示的十進制整數 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,:); case 13 A(i,:)=B(i,:)+E(6,:); case 7 A(i,:)=B(i,:)+E(7,:); case 14 A(i,:)=B(i,:)+E(8,:)

22、; end endfor i=1:1:a switch(M(i,1) case 0 disp('沒有出現(xiàn)錯誤！'); case 1 disp('注意：第c0位出現(xiàn)一個錯誤！請糾正！'); case 2 disp('注意：第c1位出現(xiàn)一個錯誤！請糾正！'); case 4 disp('注意：第c2位出現(xiàn)一個錯誤！請糾正！'); case 8 disp('注意：第c3位出現(xiàn)一個錯誤！請糾正！'); case 13 disp('注意：第c4位出現(xiàn)一個錯誤！請糾正！'); case 7 disp('

23、注意：第c5位出現(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('譯出的信息序列I='); disp(I); 3.2 仿真結果（1） 輸出編碼結果無錯誤輸入時顯示圖:圖3.1 沒有出現(xiàn)錯誤的仿真圖（2） 有一位錯誤輸入時顯示圖:圖3.2 第c

24、3位出現(xiàn)錯誤時的仿真圖（3） 有兩位錯誤輸入時顯示圖: 圖3.3 出現(xiàn)兩位錯誤時的仿真圖3.3 結果分析 當輸入沒有錯誤碼字時。仿真過程中，在MATLAB界面輸入：0 0 0 0 0 0 0矩陣，由于輸入的接收碼組與編碼后的碼字一致，它提取了每個碼組的前四位，即信息位，由結果看出譯碼過程是正確的，并沒有出現(xiàn)錯譯的情況，可見程序的譯碼片段是正確的。 當輸入一位錯誤碼字時，仿真過程中，在MATLAB界面輸入：0 1 0 0 0 0 0矩陣，仿真結果顯示有一位錯誤輸入時，可知接收碼組的第c5位發(fā)生了錯誤，經程序糾檢錯誤后改正了接收序列的錯誤，并且正確譯出了信息位?？梢姵绦虻募m錯功能也是可以實現(xiàn)的，以

25、上結果進一步證實了，系統(tǒng)譯碼程序的正確性。當輸入兩位特定位錯誤碼字時的結果分析同理由仿真結果可以看出，當輸入B=0 1 0 0 1 0 0矩陣時，校正子是0011，錯誤圖樣是0100100，所以可以得知接收碼組的第c5位和c2位發(fā)生了錯誤，說明理論得以驗證。可以得到仿真的經過與手算的經過是一致的，滿足了題設基本要求。 由仿真結果可以看出，編碼的結果與在推導過程中運算的結果是一致的，所以我們可以知道程序的編碼運行過程是正確的。實際在計算過程中，設接收碼字為（c6,c5, c4, c3, c2, c1,c0) 。以接收碼字（0000001）為例，在實際接收時，它的伴隨矩陣為（0001），在中在第一

26、行的位置，即第c0位出現(xiàn)錯誤。同時將碼字（0000001）輸入到MATLAB里進行雙向驗證，MATLAB輸出的界面顯示為有一位錯誤，并顯示：第c0位出現(xiàn)一個錯誤！請糾正！所以，我們從中可以看出，不管是實際計算結果，還是仿真結果都是一致的，雙向驗證的結果都是正確的，滿足了系統(tǒng)的基本要求。第4章 總結 這次為期二周的編碼課程設計，使我收獲了很多。線性分組碼是差錯控制編碼的重要一種。線性分組碼的編碼與譯碼糾錯能力較強，是實際應用中比較流行的差錯控制編碼方法之一。我們選擇MATLAB語言作為編程語言，因為MATLAB語言是比較容易實現(xiàn)，在實際應用過程中使用的非常廣泛，也是我們應該熟練掌握的語言。運用MATLAB語言進行編程，可以較明顯的知道編碼的過程和譯碼時出現(xiàn)的錯誤。線性分組碼具有編譯碼簡單，封閉性好等特點，采用差錯控制編碼技術是提高數字通信可靠性的有效方法，是目前較為流行的差錯控制編碼技術之一。通過課程設計我們可以學習到在書本上學不到的知識，可以了解在課堂上理解不了的概念，課程設計是一個學者從理論走向實踐必不可少的過程，對大學生來說試一次很有意義的鍛煉。設計過程中查閱了大量的有關線性分組碼設計的書籍，最后選擇了應用廣泛的（7,3）碼進行設計