線性分組碼糾錯(cuò)能力的分析,通信汪冰倫

摘要近年來，隨著計(jì)算機(jī)、衛(wèi)星通信及高速數(shù)據(jù)網(wǎng)的飛速發(fā)展，數(shù)據(jù)的交換、處理和存儲(chǔ)技術(shù)得到了廣泛的應(yīng)用，人們對(duì)數(shù)據(jù)傳輸和存儲(chǔ)系統(tǒng)的可靠性提出了越來越高的要求。因此，如何控制差錯(cuò)、提高數(shù)據(jù)傳輸和存儲(chǔ)的可靠性，成為現(xiàn)代數(shù)字通信系統(tǒng)設(shè)計(jì)工作者面臨的重要課題。目前，幾乎所有得到實(shí)際應(yīng)用的糾錯(cuò)碼都是線性的。線性分組碼的應(yīng)用上越來越廣泛，首先介紹有關(guān)糾錯(cuò)碼的基本概念，然后重點(diǎn)論述線性分組碼的定義及其編譯碼理論。再運(yùn)用仿真軟件CCS平臺(tái)對(duì)其糾錯(cuò)能力進(jìn)行仿真。關(guān)鍵詞：糾錯(cuò)；線性分組碼；CSS仿真目錄1. 課題描述 12. 設(shè)計(jì)原理 12.1. 線性分組碼的基本原理 12.2. 線性分組碼編碼過程 23. 設(shè)計(jì)過程 53.1. 設(shè)計(jì)思路 53.2. 設(shè)計(jì)內(nèi)容 63.3. 關(guān)于程序中最小距離及糾檢錯(cuò)能力的分析 83.3.1. 線性分組碼的生成矩陣和校驗(yàn)矩陣 83.3.2. 最小距離、糾錯(cuò)能力的分析 8總結(jié) 10參考文獻(xiàn) 11PAGE11第頁共11頁課題描述要設(shè)計(jì)一個(gè)線性分組碼的碼字集合程序，最基本的是要具備對(duì)輸入的信息碼進(jìn)行編碼，讓它具有抗干擾的能力。同時(shí)，還要讓它具有對(duì)接收到的整個(gè)碼組中提取信息碼組的功能。但是，在實(shí)際的通信系統(tǒng)中，由于信道傳輸特性不理想以及加性噪聲的影響，接收到的信息中不可避免地會(huì)發(fā)生錯(cuò)誤，影響通信系統(tǒng)的傳輸可靠性，因而，本設(shè)計(jì)還要讓該程序具有糾正錯(cuò)誤的能力，當(dāng)接收到的碼組中有一位碼，發(fā)生錯(cuò)誤時(shí)可以檢測(cè)到這一位錯(cuò)碼，并且可以糾正這一位錯(cuò)碼，并且讓系統(tǒng)從糾正后的碼組中提取正確的信息碼組。本課題主要是對(duì)給定碼字集合，編程求其最小距離，并分析糾檢錯(cuò)能力設(shè)計(jì)原理線性分組碼的基本原理1、在長為n的二元序列集中選出與消息序列數(shù)2k相同數(shù)目的碼元序列，并使兩者一一對(duì)應(yīng)。幾個(gè)概念：碼字：對(duì)應(yīng)于消息的長n的2k個(gè)碼元序列，用表示。選出的2k個(gè)碼元序列稱為許用碼組，另外的2n-2k個(gè)為禁用碼組。碼：所有碼字的集合，用C表示。字：所有長為n的二元序列。消息：長為k的二元碼元序列，用表示。2、消息與碼字的映射關(guān)系（函數(shù)關(guān)系）線性分組碼與呈線性關(guān)系（fi為線性函數(shù)）。編碼規(guī)則：對(duì)于如下的線性分組碼k=1，故為（n，1）碼，稱（n，1）重復(fù)碼。碼率：R=1/n。線性分組碼編碼過程線性分組碼是一類奇偶校驗(yàn)碼，它可以由（n，k）形式表示。編碼器將一個(gè)k比特信息分組（信息矢量）轉(zhuǎn)變?yōu)橐粋€(gè)更長的由給定元素符號(hào)集組成的n比特編碼分組。當(dāng)這個(gè)符號(hào)集包含兩個(gè)元素（0和1），與二進(jìn)制相對(duì)，稱為二進(jìn)制編碼。分組碼是對(duì)每段k位長的信息組，以一定規(guī)則增加r=n-k個(gè)檢驗(yàn)元，組成長為n的序列：(cn-1,cn-2,...,c1,c0)，稱這個(gè)序列為碼字。在二進(jìn)制情況下，信息組總共有2k個(gè)(q進(jìn)制為qk個(gè))，因此通過編碼器后，相應(yīng)的碼字也有2^k個(gè)。稱這2^k個(gè)碼字集合為(n,k)分組碼。n長序列的可能排列總共有2^n種。稱被選取的2^k個(gè)n重為許用碼組，其余2^n-2^k個(gè)為禁用碼組。稱R=k/n為碼率.對(duì)于長度為n的二進(jìn)制分組碼，可以表示成（n，k），通常用于前向糾錯(cuò)。在分組碼中，監(jiān)督位加到信息位之后，形成新碼，在編碼中，k個(gè)信息位，被編為n位長度，（n-k）個(gè)監(jiān)督碼的作用是實(shí)現(xiàn)檢錯(cuò)和糾錯(cuò)。k比特信息形成2^k個(gè)不同的信息序列，稱為k元組（k比特序列），同樣，n比特可以形成2^n個(gè)序列，稱為n元組。編碼過程就是將每個(gè)k元組映射到2^n個(gè)n元組中的一個(gè)。分組碼是一一對(duì)應(yīng)的編碼，即2^k個(gè)k元組唯一映射到2^k個(gè)2元組，映射可以通過一個(gè)查詢表實(shí)現(xiàn)。對(duì)于線性碼，映射當(dāng)然是線性的。信源所給出的二元信息序列首先分成等長的各個(gè)信息組，每組的信息位長度為k，記為：m=(m7m6)。由上可知，信息組m可能有22種取值。編碼器按一定規(guī)則，將輸入的信息組編制成長為8的碼字，記為：c=(c7c6c5c4c3c2c1c0)。碼字的前2位為信息元，分別與信息組的2個(gè)信息元依此一一對(duì)應(yīng)相等；碼字的后8-2=6個(gè)碼元為校驗(yàn)元。如果各校驗(yàn)元與前2個(gè)信息元之間的關(guān)系是線性的（即可用一次方程描述），則稱這樣的碼為(8,2)線性分組碼。表給出了一個(gè)（8,2）線性分組碼的例子。該例子中，信息組為（c7c6），碼組為(c7c6c5c4c3c2c1c0)，當(dāng)已知信息組時(shí)，按以下規(guī)則得到六個(gè)校驗(yàn)元，即：cc5=c7c4=c6c3=c7+c6c2=c7c1=c6c0=c7+c6（2-1）該組方程稱為校驗(yàn)方程，由該方程組可知校驗(yà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所示的線性分組碼的所有4個(gè)碼字：信息組碼字c7c6c7c6c5c4c3c2c1c00000000000010101101110101011011111110110從表中可知該線形分組碼有22（4）個(gè)許用碼字或合法瑪字，另有28—22個(gè)禁用碼字。發(fā)送方發(fā)送的是許用碼字，若接收方收到的是禁用碼字，則說明傳輸中發(fā)生了錯(cuò)誤。(n,k)線性分組碼中每個(gè)碼字都是一個(gè)二進(jìn)制的n重，即二進(jìn)制n維線性空間中的一個(gè)矢量該線性分組碼的編碼就是從8維線性空間V8中，找出滿足一定要求的，由22個(gè)2維線性子空間；或者說在滿足一定條件下，如何根據(jù)已知的2個(gè)信息元求得8－2個(gè)校驗(yàn)元。而組成2維線性子空間的22個(gè)碼字可由2個(gè)線性無關(guān)的矢量所組成的基底所張成[3]。對(duì)于(8,2)線性分組碼，可將式改寫為：cc7=c7c6=c6c5=c7c4=c6c3=c7+c6c2=c7c1=c6c0=c7+c6（2-2）寫成矩陣形式：101011011010110101011011[c7c6c5c4c3c2c1c0]=[c7c6]·（2-3）表中所示的該線性分組碼的6個(gè)校驗(yàn)元是由式所示的線性方程組決定的。把式移項(xiàng)，可得：（2-4）c（2-4）c7+c5=0c6+c4=0c7+c6+c3=0c7+c2=0c6+c1=0c7+c6+c0=0由上述可得該線性分組碼的生成矩陣G和校驗(yàn)矩陣H分別為：GG＝1010110101011011101000000101000011001000100001000100001011000001H＝因此，當(dāng)信息組m=(m7m6m5m4)時(shí)，相應(yīng)的碼字c為:c＝m·G＝(c7c6c5c4c3c2c1c0)設(shè)計(jì)過程設(shè)計(jì)思路設(shè)發(fā)送端送入信道的長為n的碼字序列：c=(cn-1cn-2…c1c0)。通過信道傳輸，到譯碼器輸入端的接收序列為：y=(yn-1yn-2…y1y0)。由于信道中噪聲的影響，y序列中的某些碼元可能與c序列中對(duì)應(yīng)碼元的值不同，即傳輸中產(chǎn)生了錯(cuò)誤。在二進(jìn)制序列中，錯(cuò)誤為1錯(cuò)成0或者0錯(cuò)成1。因此，信道中的干擾可以用二進(jìn)制序列e=(en-1en-2…e1e0)表示，相應(yīng)于有錯(cuò)的各位ei，取值為1，無錯(cuò)的各位ei，取值為0，則有y=c+e，并稱e為信道的錯(cuò)誤圖樣。當(dāng)e=0(即ei=0,i=n-1,n-2,…，0)時(shí)，y=c，表示譯碼器接收序列y無錯(cuò)；否則，當(dāng)e≠0時(shí)，y≠c，表示接收序列y有錯(cuò)。當(dāng)c序列長為n時(shí)，信道可能產(chǎn)生的錯(cuò)誤圖樣共有2n種。而譯碼器的任務(wù)就是要從收到的序列y中得到c的估值碼字和e的估值錯(cuò)誤圖樣。若估值碼字與c相等，則譯碼正確，否則錯(cuò)誤。(n,k)碼的任一碼字，均滿足ci·HT=0(i=n-1,n-2,…，0;HT為校驗(yàn)矩陣的轉(zhuǎn)置矩陣),因此可將接收碼字y用上式檢驗(yàn),可得：y·HT=(c+e)·HT=c·HT+e·HT=e·HT若e=0,則y·HT=0；若e≠0，則y·HT≠0。因此，y·HT僅與錯(cuò)誤圖樣有關(guān)，而與發(fā)送的是哪一個(gè)碼字無關(guān)。令s=y·HT=e·HT，稱為接受序列的伴隨式或校正子。設(shè)計(jì)內(nèi)容某（8，2）漢明碼的生成矩陣為H，用仿真軟件CCS平臺(tái)編碼過程。其中H為

1

0

00

11

1

0

1

0

0

1

1

00

0

1

0

1

01

0

00

10

11

H=[101000000101000011001000100001000100001011000001]主程序如下所示：title "cyclencode" .mmregs .def_c_int00STACK.usect"STACK",10H .bssM_BUFF,2;輸入2比特?cái)?shù) .bssO_BUFF,8;輸出8比特?cái)?shù) .bssP_BUFF,16;存放生成矩陣 .dataP_MATRIX.word1,0;存放生成矩陣的具體內(nèi)容，同時(shí)以列的方式進(jìn)行排序.word0,1.word1,0.word0,1.word1,1.word1,0.word0,1.word1,1 .text_c_int00:STM#0,SWWSR STM#STACK+10H,SP STM#P_BUFF,AR1 RPT#15;設(shè)定一組源碼與生成矩陣中各個(gè)元素相乘的次數(shù)為16次 MVPDP_MATRIX,*AR1+ START:NOP;加入輸入顯示 STM#O_BUFF,AR2STM#P_BUFF,AR5STM#7,AR6;設(shè)定輸出為8個(gè)碼字LOOP: STM#M_BUFF,AR3CALLSUM BANZLOOP,*AR6- NOP;加入輸出顯示BSTARTSUM:RPTZA,#1;設(shè)定datain文件中源碼的讀取方式為每次兩個(gè)MAC*AR3+,*AR5+,AAND#0001H,ASTLA,*AR2+RET end程序運(yùn)行結(jié)果如下:圖3.1輸入（8,2）漢明碼的序列圖形圖3-2編碼后的（8,2）輸出波形波形分析：在程序運(yùn)行過程中，當(dāng)輸入為10時(shí)，輸出圖形中可看出編碼為10101101；當(dāng)輸入為01時(shí)，編碼為01011011，同樣，當(dāng)輸入為00和11時(shí)，也可得到表中對(duì)應(yīng)的碼字，而在圖3－9所示的波形中，也可找到信源與編碼正確的對(duì)應(yīng)結(jié)果。由此可見，編碼器能夠正確地進(jìn)行編碼，所設(shè)計(jì)的（8，2）線性分組碼編碼器正確，程序運(yùn)行結(jié)果符合要求。關(guān)于程序中最小距離及糾檢錯(cuò)能力的分析線性分組碼的生成矩陣和校驗(yàn)矩陣線性分組碼碼空間C是由k個(gè)線性無關(guān)的基底gk-1,...,g1,g0張成的k維n重子空間，碼空間的所有元素（即碼字）都可以寫成k個(gè)基底的線性組合，即c=mk-1gk-1+…+m1g1+m0go,這種線性組合特征正是線性分組碼名稱的來歷。最小距離、糾錯(cuò)能力的分析任何最小距離的線性分組碼，其檢錯(cuò)能力為（-1），糾錯(cuò)能力t為最小距離表明碼集中各碼字差異的程度，差異越大越容易區(qū)分，抗干擾能力自然越強(qiáng)，因此成了衡量分組碼性能最重要指標(biāo)之一。估算最小距離的糾檢錯(cuò)設(shè)計(jì)的必要步驟，最原始的方法是逐一計(jì)算兩兩碼字之間距離，找出其中最小者。線性分組碼的最小距離等于碼集中時(shí)非零碼字的最小重量，即=min{w(ci)}Ci∈及Ci≠0式中，符號(hào)w(ci)表示Ci重量（１的個(gè)數(shù)）。這里利用了群的封閉性，由于分組碼是群碼，任意兩碼字之