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

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