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

1、吉林建筑大學(xué)電氣與電子信息工程學(xué)院信息理論與編碼課程設(shè)計報告設(shè)計題目：線性分組碼編碼的分析與實現(xiàn)專業(yè)班級： 電子信息工程101 學(xué)生姓名： 張 様 學(xué) 號： 10210122 指導(dǎo)教師： 呂卅 王超 設(shè)計時間： 2013.11.182013.11.29 教師評語：成績 評閱教師 日期 一、設(shè)計的作用、目的信息論與編碼是一門理論與實踐密切結(jié)合的課程,課程設(shè)計是其實踐性教學(xué)環(huán)節(jié)之一，同時也是對課堂所學(xué)理論知識的鞏固和補充。其主要目的是加深對理論知識的理解，掌握查閱有關(guān)資料的技能，提高實踐技能，培養(yǎng)獨立分析問題、解決問題及實際應(yīng)用的能力。 目前，絕大多數(shù)的數(shù)字計算機和數(shù)字通信系統(tǒng)中廣泛采用二進制形式

2、的碼。而線性分組碼具有編譯碼簡單，封閉性好等特點，采用差錯控制編碼技術(shù)是提高數(shù)字通信可靠性的有效方法，是目前較為流行的差錯控制編碼技術(shù)。通過完成具體編碼算法的程序設(shè)計和調(diào)試工作，提高編程能力，深刻理解信源編碼、信道編譯碼的基本思想和目的，掌握編碼的基本原理與編碼過程，增強邏輯思維能力，培養(yǎng)和提高自學(xué)能力以及綜合運用所學(xué)理論知識去分析解決實際問題的能力，逐步熟悉開展科學(xué)實踐的程序和方法。2、 設(shè)計任務(wù)及要求 設(shè)計一個（6，3）線性分組碼的編譯碼程序，最基本的是要具備對輸入的信息碼進行編碼，讓它具有抗干擾的能力。同時，還要讓它具有對接收到的整個碼組中提取信息碼組的功能。通過課程設(shè)計各環(huán)節(jié)的實踐，應(yīng)

3、使學(xué)生達到如下要求：1. 理解無失真信源編碼的理論基礎(chǔ)，掌握無失真信源編碼的基本方法；2. 掌握哈夫曼編碼/費諾編碼方法的基本步驟及優(yōu)缺點；3. 深刻理解信道編碼的基本思想與目的，理解線性分組碼的基本原理與編碼過程；4. 能夠使用MATLAB或其他語言進行編程，編寫的函數(shù)要有通用性。三、設(shè)計內(nèi)容已知一個（6,3）線性分組碼的Q矩陣：設(shè)碼字為(c5, c4, c3, c2, c1, c0) 求出標準生成矩陣和標準校驗矩陣，完成對任意信息序列（23個許用碼字）的編碼。當接收碼字R分別為(000000), (000001), (000010), (000100), (001000), (010000

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

5、碼組就可以對這個分組碼進行檢錯或糾錯。對于碼組長度為n、信息碼元為k位、監(jiān)督碼元為rnk位的分組碼，常記作（n，k）碼，如果滿足2r1n，則有可能構(gòu)造出糾正一位或一位以上錯誤的線性碼。4.1.2生成矩陣和校驗矩陣 線性分組碼碼空間是由個線性無關(guān)的基底，張成的維重子空間，碼空間的所有元素都可以寫成個基底的線性組合，即這種線性組合特性正是線性分組碼。為了深化對線性分組碼的理論分析，可將其與線性空間聯(lián)系起來。由于每個碼字都是一個二進制的n重，及二進制n維線性空間Vn中的一個矢量，因此碼字又稱為碼矢。用表示第個基底并寫成矩陣形式再將個基底排列成行列的矩陣，得： = 由于個基底即的個行矢量線性無關(guān)，矩陣

6、的秩一定等于，當信息元確定后，碼字僅由矩陣決定，因此稱這矩陣為該線性分組碼的生成矩陣?；椎木€性組合等效于生成矩陣的行運算，可以產(chǎn)生一組新的基底。利用這點可使生成矩陣具有如下的“系統(tǒng)形式”： 與任何一個分組線性碼的碼空間相對應(yīng)，一定存在一個對偶空間。事實上，碼空間基底數(shù)只是維重空間全部個基底的一部分，若能找出另外個基底，也就找到了對偶空間。既然用個基底能產(chǎn)生一個分組線性碼，那么也就能用個基底產(chǎn)生包含個碼字的分組線性碼，稱碼是碼的對偶碼。將空間的個基底排列起來可構(gòu)成一個矩陣，將這個矩陣稱為碼空間的校驗矩陣，而它正是對偶碼的生成矩陣，它的每一行是對偶碼的一個碼字。和的對偶是互相的，是的生成矩陣又是

7、的校驗矩陣，而是的生成矩陣，又是的校驗矩陣。由于的基底和的基底正交，空間和空間也正交，它們互為零空間。因此，線性碼的任意碼字一定正交于其對偶碼的任意一個碼字，也必定正交于校驗矩陣的任意一個行矢量，即。由于生成矩陣的每個行矢量都是一個碼字，因此必有。對于生成矩陣符合“系統(tǒng)形式”的系統(tǒng)碼，其校驗矩陣也是規(guī)則的，必為： 上式中的負號在二進制碼情況下可以省略，因為模2減法和模2加法是等同的。在本次課程設(shè)計中，要求設(shè)計（6,3）線性分組碼，因此其信息碼元及對應(yīng)碼字的關(guān)系如下表：信息碼元碼字系統(tǒng)碼字000000000000000001011101001011010110001010110011101100

8、011101100111010100111101100111101100110001011110001111010110111010 表4-1信息碼元及對應(yīng)碼字關(guān)系4.2線性分組碼的伴隨式與譯碼 4.2.1碼的距離及檢錯能力兩個碼字之間，對應(yīng)位取之不同的個數(shù)，稱為漢明距離，用d表示。一個碼的最小距離定義為,兩個碼字之間的距離表示了它們之間差別的大小。距離越大，兩個碼字的差別越大，則傳送時從一個碼字錯成另一碼字的可能性越小。碼的最小距離愈大，其抗干擾能力愈強。任何最小距離的線性分組碼，其檢錯能力為糾錯能力t為 最小距離表明碼集中各碼字差異的程度，差異越大越容易區(qū)分，抗干擾能力自然越強，因此成了衡

9、量分組碼性能最重要的指標之一。估算最小距離是糾錯碼設(shè)計的必要步驟，最原始的方法是逐一計算兩兩碼字間距離，找到其中最小者。含個碼字的碼集需計算個距離后才能找出，費時太多，實用中還有一些更好更快的方法。線性分組碼的最小距離等于碼集中時非零碼字的最小重量，即 這里利用了群的封閉性，由于分組碼是群碼，任意兩碼字之和仍是碼字，即。因此任意兩碼字間的漢明距離其實必是另一碼字的重量，表示為。于是可將最小距離問題轉(zhuǎn)化為尋找最輕碼字問題，含個碼字的碼集僅需計算次。4.2.2伴隨式與譯碼 假設(shè)接收端收到的碼字為，那么它和原來發(fā)送端發(fā)送的碼字之間就有可能存在著誤差。即在碼組中的任意一位就有可能出錯。這樣我們在接收端

10、接收到一個碼組是就有可能判斷錯發(fā)送端原來應(yīng)該要表達的意思。為了描述數(shù)據(jù)在傳輸信道中出現(xiàn)錯誤的情況，引入了錯誤圖樣，在錯誤圖樣中，0代表對應(yīng)位沒有傳錯，1代表傳輸錯誤。實際上錯誤圖樣就是收序列與發(fā)送序列的差。所以在譯碼中用接收到的碼字模爾加錯誤圖樣就可以得到發(fā)送端的正確碼字。因此譯碼的過程就是要找到錯誤圖樣E。 定義：校正子 因為是編得的正確碼字。根據(jù)前面所敘述，它和監(jiān)督矩陣的轉(zhuǎn)置相乘為0。顯然，僅與錯誤圖樣有關(guān)，它們之間是一一對應(yīng)的關(guān)系。找到了校正子，也就可以找到。而與發(fā)送的碼字無關(guān)。若，則；因此根據(jù)是否為0可進行碼字的檢錯。如果接收碼字中只有一位碼元發(fā)生錯誤，又設(shè)錯誤在第位。即,其他的均為0

11、。在后面的譯碼程序中，建立了一個校正子與錯誤圖樣對應(yīng)的表。也就是收到一個序列，就可以通過計算得到一個校正子，而每一個校正子都對應(yīng)著一個錯誤圖樣，再通過模爾加上，就可以得到正確的碼字。因為在不同的錯誤序列中，同一位碼元錯誤時對應(yīng)的是一樣的，所以可以利用0000000這個正確的碼字讓它每位依次錯誤，來求得它的八個校正子。而這時的矩陣就是錯誤圖樣。5、 設(shè)計步驟5.1編碼過程監(jiān)督矩陣和生成矩陣的關(guān)系：由與的分塊表示的矩陣形式，。則有或者 。已知給出的（6,3）線性分組碼的矩陣： 則可以根據(jù)求出生成矩陣：由 和可求出監(jiān)督矩陣為：有了生成矩陣后則可以根據(jù)輸入的四位信息位和生成矩陣相乘得到編碼矩陣，即MA

12、TLAB函數(shù)為： ，其中為編碼后的結(jié)果，為信息矩陣，為生成矩陣。則編碼的所有情況為： 編碼序列： 信息位 | 監(jiān)督位 5.2譯碼過程對于譯碼過程來說，同樣由上知道監(jiān)督矩陣：矩陣與碼的任何一個許用碼字進行相乘的結(jié)果必等于0，即若是任一碼字，則必有。若不屬于許用碼字，或有傳輸差錯，且差錯位數(shù)在碼糾錯能力內(nèi)，則運算結(jié)果將為非0值，此時，可以糾錯或檢錯重發(fā)。(1)當接受碼字為（00000000）時：伴隨式所以此時接受編碼無錯誤。（2） 當接受碼字為（00000001）時：伴隨式所以，此時接受編碼第一位發(fā)生錯誤，糾錯后的正確譯碼為（000000）。 （3）當接受碼字為（00000010）時：伴隨式所以，

13、此時接受編碼第二位發(fā)生錯誤，糾錯后的正確譯碼為（000000）。（4）當接受碼字為（00000100）時：伴隨式所以，此時接受編碼第三位發(fā)生錯誤，糾錯后的正確譯碼為（000000）。（5）當接受碼字為（00001000）時：伴隨式所以，此時接受編碼第四位發(fā)生錯誤，糾錯后的正確譯碼為（000000）。（6）當接受碼字為（00010000）時：伴隨式所以，此時接受編碼第五位發(fā)生錯誤，糾錯后的正確譯碼為（000000）。（7）當接受碼字為（00100000）時：伴隨式所以，此時接受編碼第六位發(fā)生錯誤，糾錯后的正確譯碼為（000000）。（8）當接受碼字為（100100）時：伴隨式所以，此時接受編碼第

14、五位和第二位發(fā)生錯誤，糾錯后的正確譯碼（110110）。當編碼矩陣與生成矩陣的轉(zhuǎn)置矩陣相乘時，若當其中的一位編碼或兩位出現(xiàn)差錯時會有八種情況，則這些情況列出錯碼矩陣如下：校正子S錯誤圖樣E000000000001000001010000010011000100100001000101010000110100000111010010表5.1 伴隨式與錯誤圖樣的對應(yīng)關(guān)系6、 仿真程序及結(jié)果分析 6.1 MATLAB簡介1 基本功能MATLAB是很實用的數(shù)學(xué)軟件它在數(shù)學(xué)類科技應(yīng)用軟件中在數(shù)值運算方面首屈一指。MATLAB可以進行運算、繪制函數(shù)和數(shù)據(jù)、實現(xiàn)算法、創(chuàng)建用戶界面、連接接其他編程語言的程序等

15、，主要應(yīng)用于工程計算、控制設(shè)計、信號處理與通訊、金融建模設(shè)計與分析等領(lǐng)域。 MATLAB的基本數(shù)據(jù)單位是矩陣，它的指令表達式與數(shù)學(xué)、工程中常用的形式十分相似，故用MATLAB來解算問題要比用C，F(xiàn)ORTRAN等語言完成相同的事情簡捷得多，并且mathwork也吸收了像Maple等軟件的優(yōu)點,使MATLAB成為一個強大的數(shù)學(xué)軟件。可以直接調(diào)用,用戶也可以將自己編寫的實用程序?qū)氲組ATLAB函數(shù)庫中方便自己以后調(diào)用，此外許多的MATLAB愛好者都編寫了一些經(jīng)典的程序，用戶可以直接進行下載就可以用。2 基本應(yīng)用MATLAB 產(chǎn)品族可以用來進行以下各種工作： 數(shù)值分析 數(shù)值和符號計算 工程與科學(xué)繪圖

16、 控制系統(tǒng)的設(shè)計與仿真 圖像處理技術(shù) 數(shù)字信號處理技術(shù) 通訊系統(tǒng)設(shè)計與仿真 2.1 特點此高級語言可用于技術(shù)計算 此開發(fā)環(huán)境可對代碼、文件和數(shù)據(jù)進行管理 交互式工具可以按迭代的方式探查、設(shè)計及求解問題 二維和三維圖形函數(shù)可用于可視化數(shù)據(jù) 各種工具可用于構(gòu)建自定義的圖形用戶界面 2.2優(yōu)勢（1）友好的工作平臺和編程環(huán)境MATLAB由一系列工具組成。這些工具方便用戶使用MATLAB的函數(shù)和文件，其中許多工具采用的是圖形用戶界面。包括MATLAB桌面和命令窗口、歷史命令窗口、編輯器和調(diào)試器、路徑搜索和用于用戶瀏覽幫助、工作空間、文件的瀏覽器。隨著MATLAB的商業(yè)化以及軟件本身的不斷升級，MATLA

17、B的用戶界面也越來越精致，更加接近Windows的標準界面，人機交互性更強，操作更簡單。而且新版本的MATLAB提供了完整的聯(lián)機查詢、幫助系統(tǒng)，極大的方便了用戶的使用。簡單的編程環(huán)境提供了比較完備的調(diào)試系統(tǒng)，程序不必經(jīng)過編譯就可以直接運行，而且能夠及時地報告出現(xiàn)的錯誤及進行出錯原因分析。 （2）簡單易用的程序語言MATLAB一個高級的矩陣/陣列語言，它包含控制語句、函數(shù)、數(shù)據(jù)結(jié)構(gòu)、輸入和輸出和面向?qū)ο缶幊烫攸c。用戶可以在命令窗口中將輸入語句與執(zhí)行命令同步，也可以先編寫好一個較大的復(fù)雜的應(yīng)用程序（M文件）后再一起運行。新版本的MATLAB語言是基于最為流行的C語言基礎(chǔ)上的，因此語法特征與C語言極

18、為相似，而且更加簡單，更加符合科技人員對數(shù)學(xué)表達式的書寫格式。使之更利于非計算機專業(yè)的科技人員使用。而且這種語言可移植性好、可拓展性極強，這也是MATLAB能夠深入到科學(xué)研究及工程計算各個領(lǐng)域的重要原因。 （3）強大的科學(xué)計算機數(shù)據(jù)處理能力MATLAB是一個包含大量計算算法的集合。其擁有600多個工程中要用到的數(shù)學(xué)運算函數(shù)，可以方便的實現(xiàn)用戶所需的各種計算功能。函數(shù)中所使用的算法都是科研和工程計算中的最新研究成果，而前經(jīng)過了各種優(yōu)化和容錯處理。在通常情況下，可以用它來代替底層編程語言，如C復(fù)數(shù)的各種運算、三角函數(shù)和其他初等數(shù)學(xué)運算、多維數(shù)組操作以及建模動態(tài)仿真等。 6.2 仿真程序% H 監(jiān)督

19、矩陣% G 生成矩陣 % C 編碼矩陣% I 輸入信息序列 % R 信道輸出碼 % A 糾錯輸出碼序列 % E 錯碼矩陣% S 校驗子矩陣% M 校驗子的行的十進制序列%信道編碼程序 clear all close all H=0 1 1 1 0 0; 1 0 1 0 1 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); %信道譯碼程序

20、 clear all; close all; H=0 1 1 1 0 0; 1 0 1 0 1 0; 1 1 0 0 0 1; %監(jiān)督矩陣H B=input(請輸入接收碼組B:); a,b=size(B); %返回數(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); %求校驗子S i=1; for i=1:1:a M(i,1)=S(i,1).*4+S(i,2).*2+S(i,3); %求校驗子所表示的十進制整

21、數(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 3 A(i,:)=B(i,:)+E(4,:); case 4 A(i,:)=B(i,:)+E(5,:); case 5 A(i,:)=B(i,:)+E(6,:); case 6 A(i,:)=B(i,:)+E(7,:); case 7 A(i,:)=B(i,:)+E(8,:); end endfor i=1:1:a switch(M(i,1) cas

22、e 0 disp(沒有出現(xiàn)錯誤！); case 1 disp(注意：第1位出現(xiàn)一個錯誤！請糾正！); case 2 disp(注意：第2位出現(xiàn)一個錯誤！請糾正！); case 3 disp(注意：第3位出現(xiàn)一個錯誤！請糾正！); case 4 disp(注意：第4位出現(xiàn)一個錯誤！請糾正！); case 5 disp(注意：第5位出現(xiàn)一個錯誤！請糾正！); case 6 disp(注意：第6位出現(xiàn)一個錯誤！請糾正！); case 7 disp(注意：第6位和第3位出現(xiàn)兩個錯誤！請糾正！); end endA=rem(A,2); %求出正確的編碼 disp(檢糾錯后的碼組A=); disp(A);

23、 %顯示正確的編碼 j=1; while j=3 %提取信息位 I(:,j)=A(:,j); j=j+1; end disp(譯出的信息序列I=); disp(I); %顯示原信息碼6.3 仿真結(jié)果圖6.1 輸出編碼結(jié)果和無錯誤輸入圖6.2 有一位錯誤輸入時顯示圖圖6.3 有兩位錯誤輸入時顯示圖6.4結(jié)果分析1輸出編碼結(jié)果及輸入正確接收碼的譯碼結(jié)果分析由圖6-1可以看出編碼的結(jié)果的八種情況和在推導(dǎo)過程中運算的結(jié)果是一致的，所以我們可以知道程序的編碼過程是正確的。對于譯碼過程而言，當界面顯示“請輸入接收碼組B：” ，然后從提示符后輸入：0 0 0 0 0 0，由于輸入的接收碼組與編碼后的碼字一致

24、，它提取了每個碼組的前四位，即信息位，由結(jié)果看出譯碼過程是正確的，并沒有出現(xiàn)錯譯的情況，可見程序的譯碼片段是正確的。2輸入一位錯誤時的結(jié)果分析由圖6-1可以看出，當界面顯示“請輸入接收碼組B：” 。然后從提示符后輸入：1 0 1 0 0 0，由圖6-2 有一位錯誤輸入時的顯示圖所知，接收碼組的第五位發(fā)生了錯誤，經(jīng)程序糾檢錯誤后改正了接收序列的錯誤，并且正確譯出了信息位。可見程序的糾錯功能也是可以實現(xiàn)的，以上結(jié)果進一步證實了，系統(tǒng)譯碼程序的正確性。3輸入兩位特定位錯誤時的結(jié)果分析由圖6-3 有兩位特定位錯誤輸入時的顯示圖知，當輸入B=1 0 0 1 0 0時，校正子是111，錯誤圖樣是10010

25、0，所以說明理論得以驗證。 7、 體會及建議 通過這次的課程設(shè)計，我學(xué)習(xí)到了很多東西，讓我對線性編碼有了一個全新的認識，對Matlab的掌握也進步了很多，為以后的學(xué)習(xí)中出現(xiàn)的可能問題做好了準備，鍛煉了自己的動手能力和設(shè)計能力，掌握了一種科技工具，豐富了自己的學(xué)習(xí)生活。整個實驗過程中我懂得了許多東西，在查找的過程中我們也知道了許多原來不知道的東西，對于源代碼的修改以及成功利用也樹立了對知識應(yīng)用的信心，相信會對今后的學(xué)習(xí)工作和生活有非常大的幫助，并且提高了自己的動手實踐操作能力，使自己充分體會到了在實驗過程中的成功喜悅。讓我對MATLAB軟件有了更深的了解，對MATLAB語言也有了更加深入的學(xué)習(xí)和理解。在本次的設(shè)計中，我了解了MATLAB中很多函數(shù)的用法，提高了我編程的能力，在軟件