信息編碼設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、編碼矩陣% I 輸入信息序列% R 信道輸出碼% A 糾錯(cuò)輸出碼序列% E 錯(cuò)碼矩陣% S 校驗(yàn)子矩陣% M 檢驗(yàn)子的行的十進(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(請(qǐng)輸入接收碼組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)錯(cuò)誤); case 1 disp(第一位出現(xiàn)錯(cuò)誤); case 2 disp(第二位出現(xiàn)錯(cuò)誤); case 3 disp(第三位出現(xiàn)錯(cuò)誤); case 4 disp(第四位出現(xiàn)錯(cuò)誤); case 5 disp

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

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

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

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