線(xiàn)性分組碼糾錯(cuò)能力的分析.doc

課程設(shè)計(jì)摘 要近年來(lái)，隨著計(jì)算機(jī)、衛(wèi)星通信及高速數(shù)據(jù)網(wǎng)的飛速發(fā)展，數(shù)據(jù)的交換、處理和存儲(chǔ)技術(shù)得到了廣泛的應(yīng)用，人們對(duì)數(shù)據(jù)傳輸和存儲(chǔ)系統(tǒng)的可靠性提出了越來(lái)越高的要求。因此，如何控制差錯(cuò)、提高數(shù)據(jù)傳輸和存儲(chǔ)的可靠性，成為現(xiàn)代數(shù)字通信系統(tǒng)設(shè)計(jì)工作者面臨的重要課題。目前，幾乎所有得到實(shí)際應(yīng)用的糾錯(cuò)碼都是線(xiàn)性的。線(xiàn)性分組碼的應(yīng)用上越來(lái)越廣泛，首先介紹有關(guān)糾錯(cuò)碼的基本概念，然后重點(diǎn)論述線(xiàn)性分組碼的定義及其編譯碼理論。再編制MATLAB程序?qū)ζ浼m錯(cuò)能力進(jìn)行仿真。關(guān)鍵詞： 糾錯(cuò)；線(xiàn)性分組碼；MATLAB2目 錄1 課題描述12設(shè)計(jì)原理12.1 線(xiàn)性分組碼的基本原理12.2 線(xiàn)性分組碼編碼過(guò)程23設(shè)計(jì)過(guò)程53.1設(shè)計(jì)思路53.2設(shè)計(jì)內(nèi)容6總 結(jié)8參考文獻(xiàn)91 課題描述數(shù)字通信最主要的優(yōu)點(diǎn)之一是抗干擾能力強(qiáng) ,采用各種差錯(cuò)控制編碼進(jìn)一步改善傳輸質(zhì)量 ,因此差錯(cuò)控制編碼是對(duì)數(shù)字信號(hào)進(jìn)行抗干擾編碼 ,目的是提高數(shù)字通信的可靠性.隨著差錯(cuò)控制編碼理論和數(shù)字技術(shù)的發(fā)展 ,差錯(cuò)控制編碼在各種通信系統(tǒng)中得到了廣泛的應(yīng)用.差錯(cuò)控制編碼的方法很多 ,線(xiàn)性分組碼是其中的一種重要方法.線(xiàn)性分組碼的檢錯(cuò)和糾錯(cuò)能力由檢錯(cuò)和糾錯(cuò)定理給出.現(xiàn)有的教科書(shū)在證明該定理時(shí)直接把一個(gè)碼字看成一個(gè)點(diǎn) ,這在邏輯上是不成立的.在分組碼中 ,把兩個(gè)碼組對(duì)應(yīng)位上數(shù)字不同的位數(shù)稱(chēng)為碼組的距離 ,簡(jiǎn)稱(chēng)碼距 ,又稱(chēng)漢明 (Ham2ming)碼距.一種編碼的最小碼距 dmin的大小直接關(guān)系著這種編碼的檢錯(cuò)和糾錯(cuò)能力 ,因而最小碼距是信道編碼的一個(gè)重要參數(shù) ,在一般情況下 ,對(duì)于分組可以通過(guò)檢錯(cuò)編碼定理進(jìn)行計(jì)算，同樣可以編寫(xiě)matlab程序進(jìn)行仿真。2設(shè)計(jì)原理2.1 線(xiàn)性分組碼的基本原理1、在長(zhǎng)為n的二元序列集中 選出與消息序列數(shù)2k相同數(shù)目的碼元序列，并使兩者一一對(duì)應(yīng)。 幾個(gè)概念：碼字：對(duì)應(yīng)于消息的長(zhǎng)n的2k個(gè)碼元序列，用 表示。 選出的2k個(gè)碼元序列稱(chēng)為許用碼組，另外的2n - 2k個(gè)為禁用碼組。 碼：所有碼字的集合，用C表示。 字：所有長(zhǎng)為n的二元序列。 消息：長(zhǎng)為k的二元碼元序列，用 表示。 2、消息 與碼字 的映射關(guān)系（函數(shù)關(guān)系） 線(xiàn)性分組碼與 呈線(xiàn)性關(guān)系（fi為線(xiàn)性函數(shù)） 。 編碼規(guī)則：對(duì)于如下的線(xiàn)性分組碼 k = 1，故為（n，1）碼，稱(chēng)（n，1）重復(fù)碼。碼率：R = 1/n 。2.2 線(xiàn)性分組碼編碼過(guò)程線(xiàn)性分組碼是一類(lèi)奇偶校驗(yàn)碼，它可以由（n，k）形式表示。編碼器將一個(gè)k比特信息分組（信息矢量）轉(zhuǎn)變?yōu)橐粋€(gè)更長(zhǎng)的由給定元素符號(hào)集組成的n比特編碼分組。當(dāng)這個(gè)符號(hào)集包含兩個(gè)元素（0和1），與二進(jìn)制相對(duì)，稱(chēng)為二進(jìn)制編碼。 分組碼是對(duì)每段k 位長(zhǎng)的信息組，以一定規(guī)則增加 r = n - k個(gè)檢驗(yàn)元，組成長(zhǎng)為n 的 序列：( cn-1,cn-2, . . . , c1,c 0) ，稱(chēng)這個(gè)序列為碼字。在二進(jìn)制情況下，信息組總共有2 k 個(gè)( q 進(jìn)制為q k個(gè)) ，因此通過(guò)編碼器后，相應(yīng)的碼字也有2k 個(gè)。稱(chēng)這2k 個(gè)碼字集合為( n , k) 分組碼。n長(zhǎng)序列的可能排列總共有 2n 種。稱(chēng)被選取的2k 個(gè) n重為許用碼組，其余 2n - 2k 個(gè)為禁用碼組。稱(chēng)R = k / n為碼率. 對(duì)于長(zhǎng)度為n的二進(jìn)制分組碼，可以表示成（n，k），通常用于前向糾錯(cuò)。在分組碼中，監(jiān)督位加到信息位之后，形成新碼，在編碼中，k個(gè)信息位，被編為n位長(zhǎng)度，（n-k）個(gè)監(jiān)督碼的作用是實(shí)現(xiàn)檢錯(cuò)和糾錯(cuò)。 k 比特信息形成2k個(gè)不同的信息序列，稱(chēng)為k元組（k比特序列），同樣，n比特可以形成2n個(gè)序列，稱(chēng)為n元組。編碼過(guò)程就是將每個(gè)k元組映射到2n個(gè)n元組中的一個(gè)。分組碼是一一對(duì)應(yīng)的編碼，即2k個(gè)k元組唯一映射到2k個(gè)2元組，映射可以通過(guò)一個(gè)查詢(xún)表實(shí)現(xiàn)。對(duì)于線(xiàn)性碼，映射當(dāng)然是線(xiàn)性的。信源所給出的二元信息序列首先分成等長(zhǎng)的各個(gè)信息組，每組的信息位長(zhǎng)度為k，記為：m=( m7 m6)。由上可知，信息組m可能有22種取值。編碼器按一定規(guī)則，將輸入的信息組編制成長(zhǎng)為8的碼字，記為：c=(c7 c6 c5 c4 c3 c2 c1 c0)。碼字的前2位為信息元，分別與信息組的2個(gè)信息元依此一一對(duì)應(yīng)相等；碼字的后8-2=6個(gè)碼元為校驗(yàn)元。如果各校驗(yàn)元與前2個(gè)信息元之間的關(guān)系是線(xiàn)性的（即可用一次方程描述），則稱(chēng)這樣的碼為(8,2)線(xiàn)性分組碼。表給出了一個(gè)（8,2）線(xiàn)性分組碼的例子。該例子中，信息組為（c7 c6），碼組為(c7 c6 c5 c4 c3 c2 c1 c0)，當(dāng)已知信息組時(shí)，按以下規(guī)則得到六個(gè)校驗(yàn)元，即：c5=c7c4=c6c3=c7+c6c2=c7c1=c6c0=c7+c6（2-1）該組方程稱(chēng)為校驗(yàn)方程，由該方程組可知校驗(yàn)元與信息元之間的線(xiàn)性關(guān)系，且校驗(yàn)元具有重復(fù)特性：第一位校驗(yàn)元與第四位校驗(yàn)元相同，第二位校驗(yàn)元與第五位校驗(yàn)元相同，第三位校驗(yàn)元與第六位校驗(yàn)元相同。同時(shí)，第一位校驗(yàn)元、第四位校驗(yàn)元與信息組第一位相同，第二位校驗(yàn)元、第五位校驗(yàn)元與信息組第二位相同，第三位、第六位校驗(yàn)元均為信息組兩位碼元作模二和得到的結(jié)果。信息組的取值不同，得到的校驗(yàn)元也不相同，從而得到不同的編碼組合。當(dāng)信息元分別取值為：00、01、10、11時(shí)，可得如表2-1所示的線(xiàn)性分組碼的所有4個(gè)碼字：信息組碼字c7c6c7c6c5c4c3c2c1c00000000000010101101110101011011111110110 表2-1 線(xiàn)性分組碼從表2-1中可知該線(xiàn)形分組碼有22（4）個(gè)許用碼字或合法瑪字，另有2822個(gè)禁用碼字。發(fā)送方發(fā)送的是許用碼字，若接收方收到的是禁用碼字，則說(shuō)明傳輸中發(fā)生了錯(cuò)誤。(n,k)線(xiàn)性分組碼中每個(gè)碼字都是一個(gè)二進(jìn)制的n重，即二進(jìn)制n維線(xiàn)性空間中的一個(gè)矢量該線(xiàn)性分組碼的編碼就是從8維線(xiàn)性空間V8中，找出滿(mǎn)足一定要求的，由22個(gè)2維線(xiàn)性子空間；或者說(shuō)在滿(mǎn)足一定條件下，如何根據(jù)已知的2個(gè)信息元求得82個(gè)校驗(yàn)元。而組成2維線(xiàn)性子空間的22個(gè)碼字可由2個(gè)線(xiàn)性無(wú)關(guān)的矢量所組成的基底所張成3。對(duì)于(8,2)線(xiàn)性分組碼，可將式改寫(xiě)為：c7=c7c6=c6c5=c7c4=c6c3=c7+c6c2=c7c1=c6c0=c7+c6（2-2）寫(xiě)成矩陣形式：1 0 1 0 1 1 0 10 1 0 1 1 0 1 1c7 c6 c5 c4 c3 c2 c1 c0= c7 c6（2-3）表中所示的該線(xiàn)性分組碼的6個(gè)校驗(yàn)元是由式所示的線(xiàn)性方程組決定的。把式移項(xiàng)，可得：（2-4）c7+c5=0c6+c4=0c7+c6+c3=0c7+c2=0c6+c1=0c7+c6+c0= 0由上述可得該線(xiàn)性分組碼的生成矩陣G和校驗(yàn)矩陣H分別為：G1 0 1 0 1 1 0 10 1 0 1 1 0 1 11 0 1 0 0 0 0 00 1 0 1 0 0 0 01 1 0 0 1 0 0 01 0 0 0 0 1 0 00 1 0 0 0 0 1 01 1 0 0 0 0 0 1H 因此，當(dāng)信息組m=(m7 m6 m5 m4)時(shí)，相應(yīng)的碼字c為:cmG(c7 c6 c5 c4 c3 c2 c1 c0)3設(shè)計(jì)過(guò)程3.1設(shè)計(jì)思路設(shè)發(fā)送端送入信道的長(zhǎng)為n的碼字序列：c =(cn-1 cn-2 c1 c0)。通過(guò)信道傳輸，到譯碼器輸入端的接收序列為：y =(yn-1 yn-2 y1 y0)。由于信道中噪聲的影響，y 序列中的某些碼元可能與c 序列中對(duì)應(yīng)碼元的值不同，即傳輸中產(chǎn)生了錯(cuò)誤。在二進(jìn)制序列中，錯(cuò)誤為1錯(cuò)成0或者0錯(cuò)成1。因此，信道中的干擾可以用二進(jìn)制序列e =(en-1 en-2 e1 e0)表示，相應(yīng)于有錯(cuò)的各位ei ，取值為1，無(wú)錯(cuò)的各位ei ，取值為0，則有y=c+e，并稱(chēng)e為信道的錯(cuò)誤圖樣。當(dāng)e = 0(即ei=0,i=n-1,n-2,，0)時(shí)，y=c，表示譯碼器接收序列y無(wú)錯(cuò)；否則，當(dāng)e0時(shí)，yc，表示接收序列y有錯(cuò)。當(dāng) c序列長(zhǎng)為n時(shí)，信道可能產(chǎn)生的錯(cuò)誤圖樣共有2n種。而譯碼器的任務(wù)就是要從收到的序列y中得到c的估值碼字和e的估值錯(cuò)誤圖樣。若估值碼字與c相等，則譯碼正確，否則錯(cuò)誤。(n,k)碼的任一碼字，均滿(mǎn)足ciHT=0(i=n-1,n-2,，0;HT為校驗(yàn)矩陣的轉(zhuǎn)置矩陣),因此可將接收碼字y用上式檢驗(yàn),可得：yHT=( c+e ) HT=cHT+ eHT= eHT若e =0,則yHT=0；若e 0，則yHT0。因此，yHT僅與錯(cuò)誤圖樣有關(guān)，而與發(fā)送的是哪一個(gè)碼字無(wú)關(guān)。令s = yHT= eHT，稱(chēng)為接受序列的伴隨式或校正子。3.2設(shè)計(jì)內(nèi)容某（7，4）漢明碼的生成矩陣為G，用MATLAB仿真編碼過(guò)程。其中G為 100011101001100010101000101 1：G=1 0 0 0 1 1 1; 0 1 0 0 1 1 0; 0 0 1 0 1 0 1;0 0 0 1 0 1 1主程序如下所示：G=1 0 0 0 1 1 1; 0 1 0 0 1 1 0; 0 0 1 0 1 0 1; 0 0 0 1 0 1 1;%十進(jìn)制生成矩陣m=1 0 0 0;%十進(jìn)制數(shù)信息組result = groupCoding(m,G)%對(duì)信息組進(jìn)行編碼，得到的結(jié)果為二進(jìn)制數(shù)其中g(shù)roupCoding函數(shù)如下：function c = groupCoding(m,G) %m為信息組，G為生成矩陣，均為十進(jìn)制row,col = size(G);%G的行數(shù)為k,;列數(shù)為nif length(m)= row disp(信息組尺寸與生成矩陣不一致);return;endr=mod(m*G,2);% m*G得到m的碼字%將碼字轉(zhuǎn)化為二進(jìn)制tempSum = 0;for i=1:length(r) if r(i) = 1 tempSum = tempSum +2(length(r)-i); endendc = dec2bin(tempSum);程序運(yùn)行結(jié)果如下: 圖3 原始序列及得到的相應(yīng)編碼分析結(jié)果：在程序運(yùn)行過(guò)程中，當(dāng)輸入為10時(shí)，輸出圖形中可看出編碼為10101101；當(dāng)輸入為01時(shí)，編碼為01011011，同樣，當(dāng)輸入為00和11時(shí)，也可得到表中對(duì)應(yīng)的碼字，而在圖39所示的波形中，也可找到信源與編碼正確的對(duì)應(yīng)結(jié)果。由此可見(jiàn)，編碼器能夠正確地進(jìn)行編碼，所設(shè)計(jì)的(7,4)線(xiàn)性分組碼編碼器正確，程序運(yùn)行結(jié)果符合要求?？?結(jié)每一次課程設(shè)計(jì)都是一種自我學(xué)習(xí)的過(guò)程，因?yàn)樵谝郧暗膶W(xué)習(xí)中，我們往往可以對(duì)自己所學(xué)得的知識(shí)得到擴(kuò)展和鞏固，同時(shí)對(duì)使用軟件的熟悉讓我們可以較快完成任務(wù)。但是這一次的課程設(shè)計(jì)，尤其是是陌生的軟件和并不熟悉的編程語(yǔ)言讓我們一時(shí)無(wú)從下手。課程設(shè)計(jì)的初期，對(duì)我來(lái)說(shuō)，似乎大部分時(shí)間都在荒廢而課題上未能有絲毫進(jìn)展。由于第一次開(kāi)設(shè)數(shù)字信號(hào)處理課程設(shè)計(jì)，同時(shí)對(duì)匯編語(yǔ)言沒(méi)有更深的學(xué)習(xí)，我對(duì)自己的任務(wù)倍感艱辛。在網(wǎng)上和書(shū)中大面積的搜索源代碼及相關(guān)知識(shí)無(wú)果后，我開(kāi)始專(zhuān)心研究線(xiàn)性分組碼編碼理論并且逐步重溫匯編語(yǔ)言的語(yǔ)法特性與指令功能，經(jīng)過(guò)一個(gè)星期的摸索，我可以較為系統(tǒng)地描述(8,2)線(xiàn)性分組碼的編譯碼原理和特性，論文也得以展開(kāi)。但是，理論的獲得對(duì)我來(lái)說(shuō)是不夠的，之前所做的只是準(zhǔn)備工作，將理論轉(zhuǎn)化為具有可行性的過(guò)程才是我的目的所在。經(jīng)過(guò)老師的幫助，我們明白了線(xiàn)性分組碼的編碼過(guò)程其實(shí)就是矩陣相乘的結(jié)果，而在程序體現(xiàn)最多則是模二加運(yùn)算。有了明確的思路，我可以編出看似功能符合要求的程序。很顯然，對(duì)于信息論編碼書(shū)中很多關(guān)于線(xiàn)性編組碼的糾錯(cuò)方面上經(jīng)歷了許多坎坷。為此，我多次向老師咨詢(xún)，同時(shí)與其他同學(xué)加強(qiáng)在此方面的交流，并且借鑒了與課題內(nèi)容具有共同之處的源代碼，在老師的耐心的教導(dǎo)和同學(xué)們熱性的幫助下，我的程序每一次經(jīng)過(guò)調(diào)試之后都會(huì)離要求更進(jìn)一步，在為數(shù)不多的幾次修改之后，我的程序可