線性分組碼的編碼與譯碼

實(shí)踐教學(xué)大學(xué)計(jì)算機(jī)與通信學(xué)院2014年秋季學(xué)期計(jì)算機(jī)通信課程設(shè)計(jì)題目：線性分組碼(9,4)碼的編譯碼仿真設(shè)計(jì)專業(yè)班級(jí)：姓名：學(xué)號(hào)：指導(dǎo)教師：成績：摘要該系統(tǒng)是（9,4）線性分組碼的編碼和譯碼的實(shí)現(xiàn)，它可以對(duì)輸入的四位的信息碼進(jìn)行線性分組碼編碼，對(duì)于接收到的九位碼字可以進(jìn)行譯碼，從而譯出四位信息碼。當(dāng)接收到的九位碼字中有一位發(fā)生錯(cuò)誤時(shí)，可以糾正這一位錯(cuò)碼；當(dāng)接收到的碼字有兩位發(fā)生錯(cuò)誤時(shí)，只能糾正一位錯(cuò)誤，但同時(shí)能檢測(cè)出另一位錯(cuò)誤不能糾正。只有特定位有兩位錯(cuò)誤時(shí)，才能糾正兩位錯(cuò)誤。這樣就譯出正確的信息碼組，整個(gè)過程是用MATLAB語言實(shí)現(xiàn)的。關(guān)鍵詞：編碼；譯碼；糾錯(cuò)目錄TOC\o"1-5"\h\z摘要1\o"CurrentDocument"目錄2\o"CurrentDocument"信道編碼概述2\o"CurrentDocument"1.1信道模型2\o"CurrentDocument"1.2抗干擾信道編碼定理及逆定理3\o"CurrentDocument"1.3檢錯(cuò)與糾錯(cuò)的基本原理4\o"CurrentDocument"1.4限失真編碼定理5\o"CurrentDocument"線性分組碼的編碼6\o"CurrentDocument"2.1生成矩陣6\o"CurrentDocument"2.2校驗(yàn)矩陣9\o"CurrentDocument"2.3伴隨式與譯碼10\o"CurrentDocument"線性分組碼編碼的Matlab仿真12\o"CurrentDocument"3.1程序流程圖12\o"CurrentDocument"3.2程序執(zhí)行結(jié)果12\o"CurrentDocument"3.2線性分組碼譯碼的Matlab仿真13\o"CurrentDocument"3.3結(jié)果分析15\o"CurrentDocument"參考文獻(xiàn)16\o"CurrentDocument"總結(jié)17\o"CurrentDocument"致謝18附錄19前言由于計(jì)算機(jī)、衛(wèi)星通信及高速數(shù)據(jù)網(wǎng)的飛速發(fā)展，數(shù)據(jù)的交換、處理和存儲(chǔ)技術(shù)得到了廣泛的應(yīng)用，數(shù)字信號(hào)在傳輸中往往由于各種原因，使得在傳送的數(shù)據(jù)流中產(chǎn)生誤碼，從而使接收端產(chǎn)生圖象跳躍、不連續(xù)、出現(xiàn)馬賽克等現(xiàn)象，人們對(duì)數(shù)據(jù)傳輸和存儲(chǔ)系統(tǒng)的可靠性提出來了越來越高的要求，經(jīng)過長時(shí)間的努力，通過編譯碼來控制差錯(cuò)、提高可靠性的方式在信道傳輸中得到了大量的使用和發(fā)展，并形成了一門新的技術(shù)叫做糾錯(cuò)編碼技術(shù)，糾錯(cuò)編碼按其碼字結(jié)構(gòu)形式和對(duì)信息序列處理方式的不同分為兩大類：分組碼和卷積碼。目前，絕大多數(shù)的數(shù)字計(jì)算機(jī)和數(shù)字通信系統(tǒng)中廣泛采用二進(jìn)制形式的碼。而線性分組碼具有編譯碼簡單，封閉性好等特點(diǎn)，采用差錯(cuò)控制編碼技術(shù)是提高數(shù)字通信可靠性的有效方法，是目前較為流行的差錯(cuò)控制編碼技術(shù)。對(duì)線性分組碼的討論都在有限域GF（2）上進(jìn)行，域中元素為{0,1},域中元素計(jì)算為模二加法和模二乘法。分組碼是一組固定長度的碼組，可表示為（n,k）,通常它用于前向糾錯(cuò)。在分組碼中，監(jiān)督位被加到信息位之后，形成新的碼。在編碼時(shí)，k個(gè)信息位被編為n位碼組長度，而n-k個(gè)監(jiān)督位的作用就是實(shí)現(xiàn)檢錯(cuò)與糾錯(cuò)。對(duì)于長度為n的二進(jìn)制線性分組碼，它有種2n可能的碼組，從2n種碼組中，可以選擇M=2k個(gè)碼組（k<n）組成一種碼。這樣，一個(gè)k比特信息的線性分組碼可以映射到一個(gè)長度為n碼組上，該碼組是從M=2k個(gè)碼組構(gòu)成的碼集中選出來的，這樣剩下的碼組就可以對(duì)這個(gè)分組碼進(jìn)行檢錯(cuò)或糾錯(cuò)。信道編碼概述1.1信道模型信息必須首先轉(zhuǎn)換成能在信道中傳輸或存儲(chǔ)的信息后才能通過信道傳送給收信者。在信息傳輸過程中，噪聲或干擾主要是從信道引入的，它使信息通過信道傳輸后產(chǎn)生錯(cuò)誤和失真。因此信道的輸入和輸出之間一般不是確定的函數(shù)關(guān)系，而是統(tǒng)計(jì)依賴的關(guān)系。只要知道信道的輸入信號(hào)、輸出信號(hào)以及它們之間的統(tǒng)計(jì)依賴關(guān)系，就可以確定信道的全部特性。信道的種類很多，這里只研究無反饋、固定參數(shù)的單用戶離散信道。離散信道的數(shù)學(xué)模型離散信道的數(shù)學(xué)模型一般如圖6.1所示。圖中輸入和輸出信號(hào)用隨機(jī)矢量表示，輸入信號(hào)為X=*X2，…,XN),輸出信號(hào)為Y=(*,Y2，…,Yn);每個(gè)隨機(jī)變量Xj和Yj又分別取值于符號(hào)集A={a1Za2,…,ar}和B={b1Zb2,…,bs}，其中r不一定等于s;條件概率P(y|x)描述了輸入信號(hào)和輸出信號(hào)之間的統(tǒng)計(jì)依賴關(guān)系，反映了信道的統(tǒng)計(jì)特性。X信道kYX=(X,X,...,X)P(yIx)Y=(Y,Y,...,Y)12N12N￡P(guān)(yIx)=1圖1.1離散信道模型根據(jù)信道的統(tǒng)計(jì)特性即條件概率P(y|x)的不同，離散信道可以分為三種情況：(1)無干擾信道。信道中沒有隨機(jī)干擾或干擾很小，輸出信號(hào)Y與輸入信號(hào)X之間有確定的一一對(duì)應(yīng)的關(guān)系。有干擾無記憶信道。實(shí)際信道中常有干擾，即輸出符號(hào)與輸入符號(hào)之間沒有確定的對(duì)應(yīng)關(guān)系。若信道任一時(shí)刻的輸出符號(hào)只統(tǒng)計(jì)依賴于對(duì)應(yīng)時(shí)刻的輸入符號(hào)，而與非對(duì)應(yīng)時(shí)刻的輸入符號(hào)及其他任何時(shí)刻的輸出符號(hào)無關(guān)，則這種信道稱為無記憶信道。有干擾有記憶信道。這是更一般的情況，既有干擾又有記憶，實(shí)際信道往往是這種類型。在這一類信道中某一瞬間的輸出符號(hào)不但與對(duì)應(yīng)時(shí)刻的輸入符號(hào)有關(guān)，而且與此前其他時(shí)刻信道的輸入符號(hào)及輸出符號(hào)有關(guān)，這樣的信道稱為有記憶信道。單符號(hào)離散信道的數(shù)學(xué)模型單符號(hào)離散信道的輸入變量為x，取值于{a],a2,…,ar},輸出變量為y，取值于他,

b2,…,bs｝，并有條件概率P(y|x)=P(y=b^|x=a.)=P(b.|a.)(i=12...,r;j=12...,s)這一組條件概率稱為信道的傳遞概率或轉(zhuǎn)移概率。因?yàn)樾诺乐杏懈蓴_(噪聲)存在，信道輸入為x=a.時(shí)，輸出是哪一個(gè)符號(hào)尸，事先無法確定。但信道輸出一定是外,b2,…,bs中的一個(gè)，即有丈p(b,I氣)=1(i=12...,r)(1-1)jT由于信道的干擾使輸入符號(hào)x在傳輸中發(fā)生錯(cuò)誤，所以可以用傳遞概率P(bj|ai)(i=1,2,A,r;］加以3f描述。另外，也可以用圖來描述，如圖1.2所示。M外j=1,2,A,s)來描述干擾影響的大小。因此，一般簡單的單符號(hào)離散信道的數(shù)學(xué)模型可以用概率空間［x］加以3f描述。另外，也可以用圖來描述，如圖1.2所示。M外定義1.1已知發(fā)送符號(hào)為a.，通過信道傳輸接收到的符號(hào)為bj的概率P(bj|a.)稱為航向概率。已知信道輸出端接收到的符號(hào)為bj，而發(fā)送符號(hào)為^的概率P(ajbj),稱為后向概率。有時(shí)，也把P(a.)稱為輸入符號(hào)的先驗(yàn)概率(即在接收到一個(gè)輸出符號(hào)以前輸入符號(hào)的概率)，而對(duì)應(yīng)地把P(ajbj)稱為輸入符號(hào)的后驗(yàn)概率(在接收到一個(gè)輸出符號(hào)以后輸入符號(hào)的概率)。為了討論方便，下面列出本章討論中常用的一些關(guān)于聯(lián)合概率和條件概率的關(guān)系:(1)設(shè)輸入和輸出符號(hào)的聯(lián)合概率為P(x=a.,y=bj)=P(aibj),則有P(ab)=P(a)P(bIa)=P(b)P(aIb)

ijijijijP(b.)=區(qū)P(a,)P(b,Ia,)(j=1,A,s)。根據(jù)貝葉斯定律，可得后驗(yàn)概率與先驗(yàn)概率之間的關(guān)系P(aIb)=P(aPj)(P(b)豐0)i'P".風(fēng))'(i=1,2,A,r;j=1,2,A,s)1.2抗干擾信道編碼定Pja逆定理i=1定理1.1有噪信道編碼定理設(shè)離散無記憶信道［X,P(y|x),Y］,P(y|x)為信道傳遞概率，其信道容量為C。當(dāng)信息傳輸率R<C時(shí)，只要碼長n足夠長，總可以在輸入的符號(hào)集中找到2nR個(gè)碼字組成的一組碼和相應(yīng)的譯碼規(guī)則，使譯碼的錯(cuò)誤概率任意小(PET0)。在定理6.1中，信道容量C是平均互信息量的最大值C=maxI(X,Y)其單位是“bit/符號(hào)”。"⑴定理1.2有噪信道編碼逆定理(定理6.1的逆定理)設(shè)離散無記憶信道[X,P(y|x),Y]，其信道容量為C。當(dāng)信息傳輸率R>C時(shí)，則無論碼長n多長，均找不到一種編碼2nR，使譯碼錯(cuò)誤概率任意小。定理1.1和定理1.2統(tǒng)稱為申農(nóng)第二定理，它是一個(gè)關(guān)于有效編碼的存在性定理，它具有根本性的重要意義，它說明錯(cuò)誤概率趨于零的好碼是存在的。它有助于指導(dǎo)各種通信系統(tǒng)的設(shè)計(jì)，有助于評(píng)價(jià)各種通信系統(tǒng)及編碼的效率。申農(nóng)1948年發(fā)表申農(nóng)第二定理后，科學(xué)家就致力于研究信道中的各種易于實(shí)現(xiàn)的實(shí)際編碼方法，賦予碼以各種形式的代數(shù)結(jié)構(gòu)，出現(xiàn)了各種形式的代數(shù)編碼、卷積碼、循環(huán)碼等。1.3檢錯(cuò)與糾錯(cuò)的基本原理在申農(nóng)第二定理發(fā)表后，很長一段時(shí)間內(nèi)人們都在探尋能夠簡單、有效地編碼和譯碼的好碼。由此形成了一整套糾錯(cuò)碼理論。在此只簡單地介紹檢錯(cuò)和糾錯(cuò)的一些基本概念及基本原理。在信息處理過程中，為了保持?jǐn)?shù)據(jù)的正確性應(yīng)對(duì)信息進(jìn)行編碼使其具有檢錯(cuò)糾錯(cuò)能力，這種編碼稱為語法信息編碼。它的基本思想是引入剩余度，在傳輸?shù)男畔⒋a元后增加一些多余的碼元，以使信息損失或錯(cuò)誤后仍能在接收端恢復(fù)。通常將要處理的信息稱為原信息，將原信息轉(zhuǎn)化為數(shù)字信息后再進(jìn)行存儲(chǔ)、傳輸?shù)忍幚磉^程稱為傳送。工程上最容易實(shí)現(xiàn)的是二元數(shù)字信息(或二元碼信息)的傳送。所謂二元數(shù)字信息就是由二元數(shù)域F2={0,1}中的數(shù)字0與1組成的數(shù)組或向量。定義1.3設(shè)乂=*x2,...,xn)，Y=(y1Zy2,...,yn)，xieF2，yieF2，i=1,...,n，稱X和Y對(duì)應(yīng)分量不相等的分量個(gè)數(shù)為X和Y的漢明(Hamming)距離，記為d(X,Y)。記d(X,,)=]0丁吃則nm[a>0X豐yd(X,Y)=d(xpyj+d(x2,y2)+...+d(xn,yn)容易證明以下定理。定理1.4設(shè)X和Y是長為n的二元碼字，則(1)0<d(X,Y)<n(非負(fù)且有界性)

(2)d(X,Y)=0當(dāng)且僅當(dāng)X=Y(自反性)d(X,Y)=d(Y,X)(對(duì)稱性)d(X,Z)<d(X,Y)+d(Y,Z)(三角不等式)1.4限失真編碼定理申農(nóng)第一定理和申農(nóng)第二定理指明：無論是無噪聲信道還是有噪聲信道，只要信道的信息傳輸率R小于信道容量C，總能找到一種編碼，在信道上以任意小的錯(cuò)誤概率和任意接近信道容量的信息傳輸率傳輸信息。反之，若信道信息傳輸率R大于信道容量C，一定不能使傳輸錯(cuò)誤概率任意小，傳輸必然失真。實(shí)際上，人們并不需要完全無失真地恢復(fù)信息，只是要求在一定保真度下，近似恢復(fù)信源輸出的信息。比如，人類主要是通過視覺和聽覺獲取信息，人的視覺大多數(shù)情況下對(duì)于25幀以上的圖像就認(rèn)為是連續(xù)的，通常人們只需傳送每秒25幀的圖像就能滿足通過視覺感知信息的要求，而不必占用更大的信息傳輸率。而大多數(shù)人只能聽到幾千赫茲到十幾千赫茲，即便是訓(xùn)練有素的音樂家，一般也不過能聽到20千赫茲的聲音。所以，在實(shí)際生活中，通常只是要求在保證一定質(zhì)量的前提下在信宿近似地再現(xiàn)信源輸出的信息，或者說在保真度準(zhǔn)則下，允許信源輸出的信息到達(dá)信宿時(shí)有一定的失真。對(duì)于給定的信源，在允許的失真條件下，信源熵所能壓縮的極限理論值是多少？申農(nóng)(Shannon)的重要論文〃保真度準(zhǔn)則下的離散信源編碼定理”論述了在限定范圍內(nèi)的信源編碼定理。限失真信源編碼的信息率失真理論是信號(hào)量化、模數(shù)轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮的理論基礎(chǔ)，在圖像處理、數(shù)字通信等領(lǐng)域得到廣泛的應(yīng)用。所謂信道產(chǎn)生的失真d(xn,ym)是指：當(dāng)信道輸入為xn時(shí)，輸出得到的是ym，其差異或損失，稱為譯碼失真，可描述為而平均譯碼失真則是，y而平均譯碼失真則是，ym)=ymymMzp(xm=1d=￡n=1如果要求平均譯碼失真小于某個(gè)給定值D，即d=習(xí)￡p(x)p(yIx)d(xn=1m=1也就是對(duì)P(Y|X)施加一定的限制。把滿足上式的那些P(Y|X)記為PD，在集合PD中尋找一個(gè)P(Y|X)使I(Y|X)極小，把這個(gè)極小值稱為在d<d的條件下所必須傳送的信息速率，并記為R(D)，即R(D)=min(X;Y)RD稱R(D)為信息率失真函數(shù)。它表示信息率與失真量之間的關(guān)系。上式表明，在集合PD中，任意一個(gè)I(Y|X)值所對(duì)應(yīng)的平均失真都小于或等于D。也就是說，在集合PD內(nèi)，只要I(Y|X)zR(D)，就可以達(dá)到d<d；但是如果I(Y|X)<R(D)，就意味著P(Y|X)不在集合PD內(nèi)，因而不能滿足d<DMzp(xm=1定理1.5(離散無記憶信源的限失真編碼定理)設(shè)R(D)是某離散無記憶信源的信息率失真函數(shù)，只要滿足信息率R>R(D)，對(duì)于任意小的&>0，允許失真值D>0，以及任意足夠長的碼字長度n，則一定存在一種編碼方法，使其平均譯碼失真d<d+￡；反之，若R<R(D)，則無論采用什么樣的編碼方法，都不可能使譯碼的失真小于或等于D+￡。離散無記憶信源的限失真編碼定理也稱為申農(nóng)第三編碼定理，它表明：在允許失真值D給定后，總存在一種編碼方法，使編碼后的信源輸出信息率R大于R(D)，但可任意地接近于R(D)，而平均失真d小于或無限接近于允許失真值d；反之，若R>R(D)，則編碼后的平均失真9將大于d。如果用二進(jìn)制碼符號(hào)來進(jìn)行編碼的話，那么在允許失真為D的情況下，平均每個(gè)信源符號(hào)所需二進(jìn)制碼符號(hào)數(shù)的下限值在數(shù)量上等于R(D)。在不允許失真的情況下，平均每個(gè)信源符號(hào)所需二進(jìn)制碼符號(hào)數(shù)的下限值在數(shù)量上等于H(S)。一般情況下，有R(D)<H(S)，因此，在滿足保真度準(zhǔn)則d<d的條件下，信源所需輸出數(shù)據(jù)就可以達(dá)到壓縮。信息傳輸?shù)哪繕?biāo)是高效率、高質(zhì)量地傳輸信息，而高效率和高質(zhì)量又常常相矛盾。本章分析的幾個(gè)編碼定理表明：通過適當(dāng)?shù)木幋a可以把高效率(傳輸信息的速率無限接近于信道容量)和高質(zhì)量(傳輸信息的差錯(cuò)無限接近于零或者失真低于規(guī)定的允許值)完美地結(jié)合起來。線性分組碼的編碼2.1生成矩陣線性分組碼(n，k)中許用碼字(組)為2k個(gè)。定義線性分組碼的加法為模二加法，乘法為二進(jìn)制乘法。即1+1=0、1+0=1、0+1=1、0+0=0;1x1=1、1x0=0、0x0=0、0x1=0。且碼字%=…5與碼字烏的運(yùn)算在各個(gè)相應(yīng)比特位上符合上述二進(jìn)制加法運(yùn)算規(guī)則。線性分組碼具有如下性質(zhì)(n,k)的性質(zhì)：1、封閉性。任意兩個(gè)碼組的和還是許用的碼組。2、碼的最小距離等于非零碼的最小碼重。對(duì)于碼組長度為n、信息碼元為k位、監(jiān)督碼元為r=n-k位的分組碼，常記作(門，k)碼，如果滿足2r-1>n，則有可能構(gòu)造出糾正一位或一位以上錯(cuò)誤的線性碼。下面我們通過(9,4)分組碼的例子來說明如何具體構(gòu)造這種線性碼。設(shè)分組碼(n,k)中，k=4,為能糾正一位誤碼，要求r>5?，F(xiàn)取r=5,則門*+「二9。該例子中，信息組為(C5c6c7c8),碼字為(c8c7c6c5c4c3c2c1c0).當(dāng)已知信息組時(shí)，按以下規(guī)則得到四個(gè)校驗(yàn)元，即_C4=c5+c6C3=c7+c8C2=c4+c6+c8(式2.1)C1=c5+c7C0=c5+c6+c7+c8這組方程稱為校驗(yàn)方程。(9,4)線性分組碼有24(16)個(gè)許用碼字或合法碼字，另有29-24個(gè)禁用碼字。發(fā)送方發(fā)送的是許用碼字，若接收方收到的是禁用碼字，則說明傳輸中發(fā)生了錯(cuò)誤。為了深化對(duì)線性分組碼的理論分析，可將其與線性空間聯(lián)系起來。由于每個(gè)碼字都是一個(gè)二進(jìn)制的n重及二進(jìn)制n維線性空間Vn中的一個(gè)矢量，因此碼字又稱為碼矢。線性分組碼的一個(gè)重要參數(shù)是碼率r=k/n,它說明在一個(gè)碼字中信息位所占的比重，r越大，說明信息位所占比重越大，碼的傳輸信息的有效性越高。由于(n,k)線性分組，線性分組碼的2k個(gè)碼字組成了n維線性空間Vn的一個(gè)K維子空間。因此這2k個(gè)碼字完全可由k個(gè)線性無關(guān)的矢量所組成。設(shè)此k個(gè)矢量為c1/c2,^,ck/有生成矩陣形式為C1C2(3-2)ck(n,k)碼字中的任一碼字ci，均可由這組基底的線性組合生成，即ci=m.-G=[mn-1mn-2...mn_k]-G式中，mi=[mn-1mn-2.mn-k]是k個(gè)信息元組成的信息組。表3-1(9,4)線性分組碼信息組0000000100100011010001010110011110001001101010111100110111101111碼字0000000000001000110010101010011111000100010100101110101101000101110000110001001010010110111010010111101111100110001010110100011111011110111111111對(duì)于表3-1給出的（9,4）線性分組碼，可將寫成矩陣形式f001115[c8c7c6c5c4c3c2c1]=[c8c7c6c5]-01001111110110、111101故（9,4）碼的生成矩陣為00廠1001G=01000011可以看到，從（9,4）碼的碼字中，挑選出k=4個(gè)線性無關(guān)的碼字作為碼的一組基底，用1110110、111101—個(gè)系統(tǒng)碼的生成矩陣G,其左邊k行k列應(yīng)是一個(gè)k階單位方陣Ik,因此生成矩陣G表示為G=[IkP]（3-3）式中，P是一個(gè)kx（n-k）階矩陣。2.2校驗(yàn)矩陣表3-1所示的（9,4）線性分組碼的四個(gè)校驗(yàn)元由式（3-1）所示的線性方程組決定的。把（3-1）移相，有C4+c5+c6=0C3+c7+c8=0aC2+c4+c6+c8=0C1+c5+c7=0(C8C7C6C5C4C3C2C1C0J<C0+c5+c6+c7+c8=0[001110000「110001000010100010111100001J上式的矩陣形式為這里的四行七列矩陣稱為(9,4)碼的一致校驗(yàn)矩陣，用H表示，即(C8C7C6C5C4C3C2C1C0J10111100100°DH=1100011(3-5)0V11000由H矩陣得到(n,k)線性分組碼的每一碼字c.#=12...,2k),都必須滿足由H矩陣各行所確定的線性方程組，即c*Ht0。(9,3」)碼的生成矩陣G中每一行及其線性組合都是(n,k)碼的碼字，所以有G-Ht=0。由G和H構(gòu)成的行生成的空間互為零空間，即G和H彼此正交。H=[PTlr]其右邊r行r列組成一個(gè)單位方陣。2.3伴隨式與譯碼2.3.1碼的距離及糾檢錯(cuò)能力1?碼的距離兩個(gè)碼字之間，對(duì)應(yīng)位取之不同的個(gè)數(shù)，稱為漢明距離，用d表示。一個(gè)嗎的最小距離dmin定義為dmin=min{d(ci/cj),i/j/cj/cje(n/k)},兩個(gè)碼字之間的距離表示了它們之間差別的大小。距離越大，兩個(gè)碼字的差別越大，則傳送時(shí)從一個(gè)碼字錯(cuò)成另一碼字的可能性越小。碼的最小距離愈大，其抗干擾能力愈強(qiáng)。2.線性碼的糾檢錯(cuò)能力對(duì)于任一個(gè)(n,k)線性分組碼，(1)若要在碼字內(nèi)檢測(cè)出e個(gè)錯(cuò)誤，則要求碼的最小距離d>e+1;(2)糾正t個(gè)錯(cuò)誤，則要求碼的最小距離d>2t+1;(3)糾正t個(gè)錯(cuò)誤同時(shí)檢測(cè)e(>t)個(gè)錯(cuò)誤，則要求d>t+e+1;2.3.2伴隨式與譯碼假設(shè)接收端收到的碼字為B，那么它和原來發(fā)送端發(fā)送的碼字A之間就有可能存在著誤差。即在碼組A={a6a5a4a3a2a1a。}中的任意一位就有可能出錯(cuò)。這樣我們?cè)诮邮斩私邮盏揭粋€(gè)碼組是就有可能判斷錯(cuò)發(fā)送端原來應(yīng)該要表達(dá)的意思。為了描述數(shù)據(jù)在傳輸信道中出現(xiàn)錯(cuò)誤的情況，引入了錯(cuò)誤圖樣E,在錯(cuò)誤圖樣中，0代表對(duì)應(yīng)位沒有傳錯(cuò)，1代表傳輸錯(cuò)誤。實(shí)際上錯(cuò)誤圖樣E就是收序列與發(fā)送序列的差。所以在譯碼中用接收到的碼字B模爾加錯(cuò)誤圖樣E就可以得到發(fā)送端的正確碼字A。因此譯碼的過程就是要找到錯(cuò)誤圖樣E。定義：校正子SS=B*HT=(A+E)*HT=A*Ht+E*Ht=E*Ht因?yàn)锳是編得的正確碼字。根據(jù)前面所敘述，它和監(jiān)督矩陣的轉(zhuǎn)置相乘為0。顯然，S僅與錯(cuò)誤圖樣有關(guān)，它們之間是一一對(duì)應(yīng)的關(guān)系。找到了校正子S,也就可以找到E。而與發(fā)送的碼字無關(guān)。若E=0，則S=0；因此根據(jù)S是否為0可進(jìn)行碼字的檢錯(cuò)。如果接收碼字B中只有一位碼元發(fā)生錯(cuò)誤，又設(shè)錯(cuò)誤在第i位即E._1=1,其他的弓均為0。在后面的譯碼程序中，建立了一個(gè)校正子S與錯(cuò)誤圖樣E對(duì)應(yīng)的表。也就是收到一個(gè)B序列，就可以通過計(jì)算得到一個(gè)校正子，而每一個(gè)校正子都對(duì)應(yīng)著一個(gè)錯(cuò)誤圖樣E,再通過B模爾加上E,就可以得到正確的碼字A。因?yàn)樵诓煌腻e(cuò)誤序列B中，同一位碼元錯(cuò)誤時(shí)對(duì)應(yīng)的E是一樣的，所以可以利用0000000這個(gè)正確的碼字讓它每位依次錯(cuò)誤，來求得它的八個(gè)校正子。而這時(shí)的矩陣B就是錯(cuò)誤圖樣E。這樣就算得了8個(gè)校正子S。而這時(shí)的錯(cuò)誤序列B,就是錯(cuò)誤圖樣E,所以有：E與S都已經(jīng)得到，這時(shí)就可以建立一個(gè)表來將它們一一對(duì)應(yīng)起來。3.線性分組碼編碼的Matlab仿真3.1程序流程圖線性分組碼編碼的Matlab仿真程序流程圖如下：［開始；初始化k,r,k=4,r=5得到生成矩陣Q,為4行5列I根據(jù)生成矩陣Q得到校驗(yàn)矩陣H計(jì)算所有的可用碼組"結(jié)束J圖5-1-1線性分組碼編碼的Matlab仿真程序流程圖3.2程序執(zhí)行結(jié)果形成Q矩陣的程序執(zhí)行結(jié)果如下：線性:好組碼信■忠碼柱度女=己誠性分￡且碼監(jiān)菁位長直L際足否自動(dòng)］生感校正子？Y/M-N的人一個(gè)柱正子，EL檢迎虻8位的錮碼拓位）11001始入一嚇校正子，以檢S'JCTfc的錨馮E位.）11010桐i人一個(gè)柱正子，以檢迎虻弓位的錮碼拓位）01100短入一十校正子>以檢珈UE位的錨袒E位】QQ1H校正子與錯(cuò)碼位擊的對(duì)應(yīng)關(guān)系Q_char=TOC\o"1-5"\h\z11001>C0811010>CQ701100>C06□O111>C05loooo>cod0100Q>CQ300100>C02擺巖二二旗：：圖5-1-2形成Q矩陣的程序執(zhí)行結(jié)果生成可用碼組的程序執(zhí)行結(jié)果如下：^Lid_cc-de5=00a0Daa0D0Q0L0(J]L1QQ]QDi]0Q0D]LD]aL101001i以L0010L1i]0101]0La]LD01jLLg001L0001]Q01L□aLL]]LDla]0La]CI.LQ]L100LQL1a0DaaL1L1aLDa]0DL1]00i]L1L1]LDi00Q量:小陽蝠」f=最小瑪距N■21113—圖3-1-3生成可用碼組的程序執(zhí)行結(jié)果3.2線性分組碼譯碼的Matlab仿真3.2.1程序流程圖線性分組碼譯碼的Matlab仿真程序流程圖如下:圖3-2-1線性分組碼譯碼的Matlab仿真程序流程圖3.2.2程序執(zhí)行結(jié)果是否自動(dòng)生成要核驗(yàn)的碼字？加:N清輸A.要勉的碼部位）：ooooooooo做驗(yàn)子為:00000errors=無錯(cuò)圖3-2-2輸出無錯(cuò)時(shí)顯示圖有一位錯(cuò)誤輸入時(shí)的顯示圖如下：是否自就生應(yīng)要咬溫的四字？r/N：n語輸，要楨驗(yàn)的禺寶廈位）:00000000]得出校驗(yàn)子力：S=00001errors=鐺日立置：CO,原■應(yīng)為:modifyode=ooooooooo圖3-2-3有一位錯(cuò)誤輸入時(shí)的顯示圖有兩位錯(cuò)誤輸入時(shí)的顯示圖如下:是否自動(dòng)生成要楨驗(yàn)的碼字？請(qǐng)輸入要校驗(yàn)的碼字（9位）；001000010得出校驗(yàn)子為：S二errors=校則不出錯(cuò)誤r圖3-2-4有兩位錯(cuò)誤輸入時(shí)的顯示圖3.3結(jié)果分析.輸入無錯(cuò)時(shí)的結(jié)果分析由圖5-1輸出編碼結(jié)果和正確輸入時(shí)顯示圖所示的結(jié)果可以看出編碼的結(jié)果的八種情況和在推導(dǎo)過程中運(yùn)算的結(jié)果是一致的，可以見得程序的編碼過程是正確的。對(duì)于譯碼過程而言，當(dāng)界面顯示〃請(qǐng)輸入要校驗(yàn)的碼字（9位）:”，然后從提示符后輸入：000000000，由于輸入的接收碼組與編碼后的碼字一致，它提取了每個(gè)碼組的前四位，即信息位，由結(jié)果看出譯碼過程是正確的，并沒有出現(xiàn)錯(cuò)譯的情況，可見程序的譯碼片段是正確的。.輸入一位錯(cuò)誤時(shí)的結(jié)果分析對(duì)于糾錯(cuò)過程而言，當(dāng)界面顯示〃請(qǐng)輸入要校驗(yàn)的碼字（9位）:”。然后從提示符后輸入：000000001，由圖5-2有一位錯(cuò)誤輸入時(shí)的顯示圖所知，接收碼組的第五位發(fā)生了錯(cuò)誤，經(jīng)程序糾檢錯(cuò)誤后改正了接收序列的錯(cuò)誤，并且正確譯出了信息位?？梢姵绦虻募m錯(cuò)功能也是可以實(shí)現(xiàn)的，以上結(jié)果進(jìn)一步證實(shí)了，系統(tǒng)譯碼程序的正確性。.輸入錯(cuò)誤時(shí)的結(jié)果分析當(dāng)輸入B=001000010時(shí)，校正子是01110，檢測(cè)不出錯(cuò)誤。參考文獻(xiàn)孫麗華編.信息論與糾錯(cuò)編碼.電子工業(yè)出版社.2005,3郭文彬桑林編.通信原理-基于MATLAB的計(jì)算機(jī)仿真.北京郵電大學(xué)出版社.2006.2蘇金明阮沈勇編.MATLAB實(shí)用教程（第二版）.電子工業(yè)出版社.2008.2徐東艷孟曉剛編.MATLAB函數(shù)庫查詢?cè)~典.中國鐵道出版社.2006.4潘新民編.計(jì)算機(jī)通信技術(shù).電子工業(yè)出版社.2003.7吳玲達(dá)李國輝楊冰等編.計(jì)算機(jī)通信原理與技術(shù).國防科技大學(xué)出版社.2003.3總結(jié)通過對(duì)線性分組碼中的線性分組碼的編譯碼編程實(shí)現(xiàn)，了解到線性分組碼的構(gòu)成方式是把信息序列分成每k個(gè)碼元一段，并由這k個(gè)碼元按一定規(guī)則產(chǎn)生r個(gè)校驗(yàn)位，組成長度為n=k+r的碼字，用（n,k）表示。信息碼元與校驗(yàn)位之間為線性關(guān)系。并且知道了線性分組碼的編碼過程信息碼元與校驗(yàn)位之間的線性關(guān)系實(shí)現(xiàn)起來是十分簡單的.對(duì)于碼組長度為n、信息碼元為k位、監(jiān)督碼元為r=n-k位的分組碼，如果滿足2r-1>n，則有可能構(gòu)造出糾正一位或一位以上錯(cuò)誤的線性碼。就像本設(shè)計(jì)的（9,4）分組碼的（n,k）中，n=9,k=4,r>4能糾正一位誤碼，檢測(cè)到兩位誤碼。運(yùn)用MATLAB語言進(jìn)行編程，可以較明顯的知道編碼的過程和譯碼時(shí)出現(xiàn)的錯(cuò)誤，碼字的最小距離是3時(shí)，可以糾正一位錯(cuò)誤，當(dāng)輸入特定的兩位錯(cuò)誤時(shí)，該碼字還可以糾正這兩位錯(cuò)誤，這種情況在編程結(jié)果的命令窗口中可以明顯看到。線性分組碼具有編譯碼簡單，封閉性好等特點(diǎn)，采用差錯(cuò)控制編碼技術(shù)是提高數(shù)字通信可靠性的有效方法，是目前較為流行的差錯(cuò)控制編碼技術(shù)之一。致謝這里，我要鄭重地感謝我們的課程設(shè)計(jì)指導(dǎo)老師。正是他的耐心指導(dǎo)才讓我們能夠順利的完成此次課程設(shè)計(jì)，在此說聲謝謝！在此，我也要感謝我們的小組成員，以及所有幫助我完成嵌入式程序設(shè)計(jì)論文的同學(xué)們。在這次的線性分組碼課程設(shè)計(jì)中，老師和同學(xué)們?cè)谠O(shè)計(jì)思路和設(shè)計(jì)步驟上給了我很大的幫助，幫我解答疑難問題，給我提供資料，給我提供查閱資料的信息，引導(dǎo)我該如何去思考問題，教會(huì)我解決問題的方法。同時(shí)又鼓勵(lì)我自己學(xué)習(xí)，老師給我的不僅是知識(shí)，是幫助，更是學(xué)習(xí)的信心和智慧，在這里衷心感謝老師的耐心細(xì)心和一絲不茍的幫助。同時(shí)也感謝和我一起課設(shè)的同學(xué)，這是我們共同努力的結(jié)果，衷心的感謝大家對(duì)我的幫助和支持。希望在以后的學(xué)習(xí)中我們共同學(xué)習(xí)與成長。is%;_咨?、siia^H^棄—f_ag」nnl_%?>淤棄亦a、、illws>^wnwh=e(f-ag」n)kH4;rH5;K(2>TlvHk+r)f-ag」rl3endend次:■s§^、田濟(jì)商皿豈時(shí)m煤4HS?>:■Q—yesorNOll.npuu福洲皿S時(shí)m^ZEW7Y、N;--s-)；if(QlyesorNOHH-Y-)QlrandFU-Trandperm(2>r—l)；QlrandcheckHzerospk)一苛&懸ffiBQQnzeros(kJ)；eh-1;%濟(jì)任田丑3)5爵^(十sf?l)wz-eTnk)flnfsss、淅涕漏*尚帛毋湖動(dòng)4^苒勃港>=1懸滯1248:.forH0^^.if(QlrandFU=uTH2>n)endend51—*51)％—棗跚?-7|(纏Wf_ag—dal)、業(yè)炳MMSQ—randcheckQlrandcheck(TQlrandFU--u)；H-j+lii]!.+l;e_se%洲匡、Hisses、ss—■>萍H-j+liendendQICharAndec2b5'(Qlrandcheck)_%恭+序萍皤斗旃海甘nsfSJ淅涕K斗fomkforH-llr%恭留旃有普黑羅ffiBQ(LjTsir2doub-e(QlcharA(cz:))；endende-se%^?fNk苛rgusffiBQnzeros(kJ)；Q、甘k苛r浬fomk%ffl好甘爵>出苒、iss?s^iQlcharAaTmpuKSPz.nss^—T^IE^、WB渲C%dKFsm?(％dKF)-、k+ms-)；forH-llr%恭留旃有普黑羅ffiBQ(LjTsir2doub-e(QlcharA(cz:))；endendend%%---生成完全的校正子與錯(cuò)碼位置之間的對(duì)應(yīng)關(guān)系---%生成單位矩陣(字符型)，以補(bǔ)齊校正子fori=r-1:-1:0Qr(r-i)=2Ai;endQ_charB=dec2bin(Qr);%將十進(jìn)數(shù)格式轉(zhuǎn)換為二進(jìn)制表示方式%生成校正子與錯(cuò)碼位置的對(duì)應(yīng)關(guān)系Q_charC(1:k,:)=Q_charA;Q_charC(k+1:k+r,:)=Q_charB;Q_charD=reshape(sprintf('——>C%02d',k+r-1:-1:0),8,k+r)';disp('校正子與錯(cuò)碼位置的對(duì)應(yīng)關(guān)系');Q_char=[Q_charCQ_charD]%%---線性分組碼內(nèi)部的函數(shù)關(guān)系及計(jì)算---Ik=eye(k);%生成k*k的單位矩陣，與Q合成為生成矩陣GG=[IkQ];%生成矩陣P=Q';Ir=eye(r);%生成r*r的單位矩陣，與P合成為監(jiān)督矩陣HH=[PIr];%監(jiān)督矩陣%%---計(jì)算所有的可用碼組---valid_yesOrNo=input('是否要顯示所有可用碼組?Y/N:','s');if(valid_yesOrNo=='Y')%初始化2Ak行k+r列，與1行k列的矩陣valid_codes=zeros(2Ak,k+r);valid_buffer=zer