信息編碼設(shè)計

1、吉林建筑大學(xué)電氣與電子信息工程學(xué)院信息理論與編碼課程設(shè)計報告設(shè)計題目：線性分組碼編碼的分析與實現(xiàn)專業(yè)班級： 電子信息工程 112 學(xué)生姓名： 王朝陽 學(xué) 號： 10211218 指導(dǎo)教師： 李紅 楊佳 設(shè)計時間： 2014.11.242014.12.5 教師評語：成績 評閱教師 日期 第1章 概述1.1設(shè)計的作用、目的信息論與編碼是一門理論與實踐密切結(jié)合的課程,課程設(shè)計是其實踐性教學(xué)環(huán)節(jié)之一。一方面，通過讓學(xué)生完成具體編碼算法的程序設(shè)計和調(diào)試工作，提高編程能力，深刻理解編碼理論和信息論中的基本概念，同時增強其邏輯思維能力，培養(yǎng)和提高學(xué)生的自學(xué)能力以及綜合運用所學(xué)理論知識去分析解決實際問題的能力

2、；另一方面是對課堂所學(xué)理論知識作一個總結(jié)和補充。1.2設(shè)計任務(wù)及要求設(shè)計一個（6, 3）線性分組碼的編譯碼程序：完成對任意序列的編碼，根據(jù)生成矩陣形成監(jiān)督矩陣，得到伴隨式，并根據(jù)其進(jìn)行譯碼，同時驗證工作的正確性。通過課程設(shè)計各環(huán)節(jié)的實踐，應(yīng)使學(xué)生達(dá)到如下要求：1. 理解無失真信源編碼的理論基礎(chǔ)，掌握無失真信源編碼的基本方法；2. 深刻理解信道編碼的基本思想與目的，理解線性分組碼的基本原理與編碼過程；3. 能夠使用MATLAB或其他語言進(jìn)行編程，編寫的函數(shù)要有通用性。1.3設(shè)計內(nèi)容已知一個（6,3）線性分組碼的校驗元與信息元有如下限定關(guān)系。設(shè)碼字為(c5, c4, c3, c2, c1, c0)

3、 求出標(biāo)準(zhǔn)校驗矩陣、Q矩陣、標(biāo)準(zhǔn)生成矩陣，完成對任意信息序列（個許用碼字）的編碼。當(dāng)接收碼字分別為(000000), (000001), (000010), (000100), (001000), (010000), (100000)時，寫出其伴隨式S，以表格形式寫出伴隨式與錯誤圖樣E的對應(yīng)關(guān)系，糾錯并正確譯碼，當(dāng)有兩位錯碼時，假定為位和位發(fā)生錯誤。 第2章 線性分組碼編碼的分析與實現(xiàn)2.1設(shè)計原理1. 線性分組碼的生成矩陣和校驗矩陣（1）線性分組碼具有如下性質(zhì)（n，k）的性質(zhì)：1、封閉性。任意兩個碼組的和還是許用的碼組。2、碼的最小距離等于非零碼的最小碼重。對于碼組長度為n、信息碼元為k位、

4、監(jiān)督碼元為rnk位的分組碼，常記作（n，k）碼，如果滿足2r1n，則有可能構(gòu)造出糾正一位或一位以上錯誤的線性碼。設(shè)分組碼（n，k）中，k = 3，為能糾正一位誤碼，要求r3?，F(xiàn)取r3，則nkr6。該例子中，信息組為C5 C4 C3,碼字為C5 C4 C3 C2 C1 C0.當(dāng)已知信息組時，按以下規(guī)則得到三個校 驗元，即 C2=C5+C4 C1=C3+C4 C0=C5+C3這組方程稱為校驗方程。 （6，3）線性分組碼有23（8）個許用碼字或合法碼字，另有26-23個禁用碼字。發(fā)送方發(fā)送的是許用碼字，若接收方收到的是禁用碼字，則說明傳輸中發(fā)生了錯誤。 為了深化對線性分組碼的理論分析，可將其與線性空

5、間聯(lián)系起來。由于每個碼字都是一個二進(jìn)制的n重，及二進(jìn)制n維線性空間中的一個矢量，因此碼字又稱為碼矢。線性分組碼的一個重要參數(shù)是碼率r=k/n,它說明在一個碼字中信息位所占的比重，r越大，說明信息位所占比重越大，碼的傳輸信息的有效性越高。由于(n,k)線性分組，線性分組碼的2k個碼字組成了n維線性空間的一個K維子空間。因此這2k個碼字完全可由k個線性無關(guān)的矢量所組成。（2）生成矩陣和校驗矩陣 線性分組碼碼空間是由個線性無關(guān)的基底，張成的維重子空間，碼空間的所有元素都可以寫成個基底的線性組合，即這種線性組合特性正是線性分組碼。為了深化對線性分組碼的理論分析，可將其與線性空間聯(lián)系起來。由于每個碼字都

6、是一個二進(jìn)制的n重，及二進(jìn)制n維線性空間Vn中的一個矢量，因此碼字又稱為碼矢。用表示第個基底并寫成矩陣形式再將個基底排列成行列的矩陣，得： = 由于個基底即的個行矢量線性無關(guān)，矩陣的秩一定等于，當(dāng)信息元確定后，碼字僅由矩陣決定，因此稱這矩陣為該線性分組碼的生成矩陣?；椎木€性組合等效于生成矩陣的行運算，可以產(chǎn)生一組新的基底。利用這點可使生成矩陣具有如下的“系統(tǒng)形式”： 與任何一個分組線性碼的碼空間相對應(yīng)，一定存在一個對偶空間。事實上，碼空間基底數(shù)只是維重空間全部個基底的一部分，若能找出另外個基底，也就找到了對偶空間。既然用個基底能產(chǎn)生一個分組線性碼，那么也就能用個基底產(chǎn)生包含個碼字的分組線性碼

7、，稱碼是碼的對偶碼。將空間的個基底排列起來可構(gòu)成一個矩陣，將這個矩陣稱為碼空間的校驗矩陣，而它正是對偶碼的生成矩陣，它的每一行是對偶碼的一個碼字。和的對偶是互相的，是的生成矩陣又是的校驗矩陣，而是的生成矩陣，又是的校驗矩陣。由于的基底和的基底正交，空間和空間也正交，它們互為零空間。因此，線性碼的任意碼字一定正交于其對偶碼的任意一個碼字，也必定正交于校驗矩陣的任意一個行矢量，即。由于生成矩陣的每個行矢量都是一個碼字，因此必有。對于生成矩陣符合“系統(tǒng)形式”的系統(tǒng)碼，其校驗矩陣也是規(guī)則的，必為： 上式中的負(fù)號在二進(jìn)制碼情況下可以省略，因為模2減法和模2加法是等同的。下面，介紹校驗矩陣的重要特性。（1

8、） 由H矩陣可以建立線性分組碼的線性方程組。H矩陣共有n-k行，其中每行代表一個線性方程組的系數(shù)，它表示求一個校驗位的線性方程。（2） H矩陣的每行與它的分組碼的每一個碼子的內(nèi)積為零。（3） 任何一個（n,k）線性分組碼，若要糾正小于等于t個錯誤，則其充要條件是H矩陣中2t列線性無關(guān)，由于最小距離d=2t+1.所以也相當(dāng)于要求H矩陣中任意（d-1）列線性無關(guān)。2. 線性分組碼的伴隨式與譯碼（1）碼的距離及檢錯能力兩個碼字之間，對應(yīng)位取之不同的個數(shù)，稱為漢明距離，用d表示。一個碼的最小距離定義為,兩個碼字之間的距離表示了它們之間差別的大小。距離越大，兩個碼字的差別越大，則傳送時從一個碼字錯成另一

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

10、找最輕碼字問題，含個碼字的碼集僅需計算次。（2）伴隨式與譯碼 碼字在傳輸過程中受到各種干擾，接收端收碼已不一定等于發(fā)碼，兩者間的差異就是差錯，差錯是多樣化的，我們定義差錯的式樣為差錯圖樣,即 對于二進(jìn)制碼，模2減等同模2加，因此有 利用碼字與校驗矩陣的正交性，可檢驗收碼是否錯誤,即 定義運算結(jié)果為伴隨式,即 可見，雖然本身與發(fā)碼有關(guān)，但乘以后的伴隨式 僅與差錯圖有關(guān)，只反映信道對碼字造成怎樣的干擾而與發(fā)什么碼無關(guān)了。于是可以先利用收碼和已知的算出的伴隨式；再利用算出差錯圖樣。在此過程中，和的計算都是確定性的，而從計算卻帶有隨機性。這是因為伴隨式是一個重失量，二進(jìn)制時只有種肯那個的組合，而差錯圖

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

12、之間是一一對應(yīng)的關(guān)系。找到了校正子，也就可以找到。而與發(fā)送的碼字無關(guān)。若，則；因此根據(jù)是否為0可進(jìn)行碼字的檢錯。如果接收碼字中只有一位碼元發(fā)生錯誤，又設(shè)錯誤在第位。即,其他的均為0。在后面的譯碼程序中，建立了一個校正子與錯誤圖樣對應(yīng)的表。也就是收到一個序列，就可以通過計算得到一個校正子，而每一個校正子都對應(yīng)著一個錯誤圖樣，再通過模爾加上，就可以得到正確的碼字。因為在不同的錯誤序列中，同一位碼元錯誤時對應(yīng)的是一樣的，所以可以利用000000這個正確的碼字讓它每位依次錯誤，來求得它的七個校正子。而這時的矩陣就是錯誤圖樣。2.2設(shè)計步驟1. 編碼過程監(jiān)督矩陣和生成矩陣的關(guān)系：由與的分塊表示的矩陣形式

13、，。則有或者 。 由Q=則可以求出生成矩陣=由 和可求出監(jiān)督矩陣為： H=有了生成矩陣后則可以根據(jù)輸入的四位信息位和生成矩陣相乘得到編碼矩陣，即MATLAB函數(shù)為： ，其中為編碼后的結(jié)果，為信息矩陣，為生成矩陣。可以得到信息序列為C = 2. 譯碼過程對于譯碼過程來說，由上面可知道監(jiān)督矩陣：矩陣與碼的任何一個許用碼字進(jìn)行相乘的結(jié)果必等于0，即若是任一碼字，則必有。若不屬于許用碼字，或有傳輸差錯，且差錯位數(shù)在碼糾錯能力內(nèi)，則運算結(jié)果將為非0值，此時，可以糾錯或檢錯重發(fā)。 假設(shè)c0c5 為第一位至第六位： (1)當(dāng)接收碼字為（000000）時：伴隨式所以此時接收編碼無錯誤。 （2）當(dāng)接收碼字為（0

14、00001）時：所以，此時接收編碼第一位發(fā)生錯誤，糾錯后的正確譯碼為（0000000）。（3）當(dāng)接受碼字為（000010）時：所以，此時接收編碼第二位發(fā)生錯誤，糾錯后的正確譯碼為（0000000）。（4）當(dāng)接收碼字為（000100）時：所以，此時接收編碼第三位發(fā)生錯誤，糾錯后的正確譯碼為（0000000）。（5）當(dāng)接受碼字為（001000）時：所以，此時接收編碼第四位發(fā)生錯誤，糾錯后的正確譯碼為（0000000）。（6）當(dāng)接收碼字為（010000）時：所以，此時接收編碼第五位發(fā)生錯誤，糾錯后的正確譯碼為（0000000）。（7）當(dāng)接收碼字為（100000）時：所以，此時接收編碼第六位發(fā)生錯誤，

15、糾錯后的正確譯碼為（0000000）。 （8）當(dāng)接收碼字為（100100）時： 所以，此時接收編碼第六位和第三位發(fā)生錯誤，糾錯后的正確譯碼為（0000000）。 因為伴隨式與差錯圖樣之間存在其中由上面的關(guān)系可知的關(guān)系。 當(dāng)編碼矩陣與生成矩陣的轉(zhuǎn)置矩陣相乘時，若當(dāng)其中的一位編碼或兩位出現(xiàn)差錯時會有八種情況，則這些情況列出錯碼矩陣如下表二：校正子S錯誤圖樣E000000000101000001110000010011000100100001000010010000 001100000表2 伴隨式與錯誤圖樣的對應(yīng)關(guān)系第3章 仿真程序及結(jié)果分析3.1 仿真程序 % G 生成矩陣% H 校驗矩陣% C

16、編碼矩陣% I 輸入信息序列% R 信道輸出碼% A 糾錯輸出碼序列% E 錯碼矩陣% S 校驗子矩陣% M 檢驗子的行的十進(jìn)制序列%信道編碼程序clear allclose allH=0 1 1 1 0 0;1 0 1 0 1 0;1 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=inp

17、ut(請輸入接收碼組B:);a,b=size(B);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);i=1;for i=1:1:a M(i,1)=S(i,1).*4+S(i,2).*2+S(i,3);endfor 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,:

18、); 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,:); endendfor i=1:1:a switch(M(i,1) case 0 disp(沒有出現(xiàn)錯誤); case 1 disp(第一位出現(xiàn)錯誤); case 2 disp(第二位出現(xiàn)錯誤); case 3 disp(第三位出現(xiàn)錯誤); case 4 disp(第四位出現(xiàn)錯誤); case 5 disp

19、(第五位出現(xiàn)錯誤); case 6 disp(第六位出現(xiàn)錯誤); case 7 disp(第六位和第三位出現(xiàn)錯誤); endend A=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） 在提示符后輸入：0 0 0 0 0 0，按下回車：圖1無錯誤輸入顯示圖這是輸出的結(jié)果，結(jié)果顯示沒有錯誤。（2）在提示符后輸入：0 0 0 0 0 0，按下回車： 圖2 有一位錯誤輸入時顯示圖 以上接收碼組的第一位發(fā)生了錯誤，經(jīng)程序糾

20、檢錯誤后改正了接收序列的錯誤，并且正確譯出了信息位?？梢姵绦虻募m錯功能也是可以實現(xiàn)的，以上結(jié)果進(jìn)一步證實了系統(tǒng)譯碼程序的正確性。（3）在提示符后輸入：1 0 0 1 0 0，按下回車：圖3 有兩位錯誤輸入時顯示圖 以上接收碼組的第六位和第三位發(fā)生了錯誤，經(jīng)程序糾檢錯誤后，改正了接收序列的錯誤，并且正確譯出了信息位?？梢姵绦虻募m錯功能也是可以實現(xiàn)的，以上結(jié)果進(jìn)一步證實了系統(tǒng)譯碼程序的正確性。3.3結(jié)果分析1. 由圖1 輸出編碼結(jié)果和正確輸入時顯示圖所示的結(jié)果可以看出編碼的結(jié)果的十六種情況和在推導(dǎo)過程中運算的結(jié)果是一致的，可以見得程序的編碼過程是正確的。對于譯1輸出編碼結(jié)果及輸入正確接收碼的譯碼結(jié)

21、果分析碼過程而言，當(dāng)界面顯示“請輸入接收碼組B：” ，然后從提示符后輸入： 0 0 0 0 0 0，由于輸入的接收碼組與編碼后的碼字一致，它提取了每個碼組的前四位，即信息位，由結(jié)果看出譯碼過程是正確的，并沒有出現(xiàn)錯譯的情況，可見程序的譯碼片段是正確的。2輸入一位錯誤時的結(jié)果分析對于糾錯過程而言，當(dāng)界面顯示“請輸入接收碼組B：” 。然后從提示符后輸入：0 0 0 0 0 1，由圖2有一位錯誤輸入時的顯示圖所知，接收碼組的第一位發(fā)生了錯誤，經(jīng)程序糾檢錯誤后改正了接收序列的錯誤，并且正確譯出了信息位?？梢姵绦虻募m錯功能也是可以實現(xiàn)的，以上結(jié)果進(jìn)一步證實了，系統(tǒng)譯碼程序的正確性。3輸入兩位特定位錯誤時

22、的結(jié)果分析 由圖3 有兩位特定位錯誤輸入時的顯示圖知，當(dāng)輸入R=1 0 0 1 0 0時，校正子是0011，錯誤圖樣是100100，所以結(jié)果顯示與理論相符。 第四章 總 結(jié)兩周的課程設(shè)計快要接近尾聲，我的設(shè)計任務(wù)也較順利地完成?；叵胛覄偨拥轿业脑O(shè)計題目時，腦海里沒有完整的設(shè)計計劃。通過去圖書館查閱資料，有了完整且可行的計劃。在把理論的知識弄懂后，我用MATLAB軟件仿真，MATLAB語言簡單，使用性好，剛開始對于它并不熟悉，通過這次課設(shè)，到處查資料，使我漸漸了解了MATLAB的很多函數(shù)用法，提高了我的編程能力。尤其當(dāng)我的編程所得到的結(jié)果與我理論推導(dǎo)的相一致時，我感到無比的欣慰?？傊?，此次課設(shè)使我學(xué)到很多東西，不僅提高了我的動手能力及自學(xué)能力，還知道了我的不足之處，今后應(yīng)加強。這次課設(shè)能進(jìn)展如此順利，多虧了老師們不辭辛苦，不厭其煩的耐心指導(dǎo)，同學(xué)們之間互相協(xié)作，還有我使用的參考書的編者們的幫助，在此我誠摯地感謝您們！為期一周的課程設(shè)計結(jié)束了，我在這段時間內(nèi)學(xué)到了很多東西。以前我們學(xué)的知識，因為有些知識比較難懂，自己在課后也沒有去查閱課外資料去理解、去弄懂。這次我有時間和精力去專心學(xué)習(xí)與這門課的更多知識，不再僅僅只局限于課本。在老師給我們布置自己的設(shè)計內(nèi)容后，我就去圖書館查閱資料，尋找與設(shè)計有關(guān)的書籍。我們找了專業(yè)課課本和一些與MATLAB有關(guān)的書。然后找到自己之前在MAT