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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、0）。 （9）當(dāng)接收碼字為（0100100）時：所以，此時接收編碼c5位和c2位發(fā)生錯誤，糾錯后的正確譯碼（0000000）。根據(jù)所發(fā)生的差錯情況，列出所有錯碼矩陣如下表2.2所示：表2.2 伴隨式與錯誤圖樣的對應(yīng)關(guān)系校正子 差錯圖樣 000000000000001000000100100000010010000001001000000100011010010000011101000001110100000000110100100第3章 仿真程序及結(jié)果分析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('所得的編碼結(jié)果為: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); %返回數(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 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); %求校驗子所表示的十進制整數(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,:); 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 仿真結(jié)果（1） 輸出編碼結(jié)果無錯誤輸入時顯示圖:圖3.1 沒有出現(xiàn)錯誤的仿真圖（2） 有一位錯誤輸入時顯示圖:圖3.2 第c

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

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

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