(15,7)循環(huán)碼的編譯碼方法

1、* 實踐教學(xué)* 蘭州理工大學(xué)計算機與通信學(xué)院2013年秋季學(xué)期計算機通信課程設(shè)計 題 目： （15，7） 循環(huán)碼的編譯碼方法 專業(yè)班級： 姓 名： 學(xué) 號： 指導(dǎo)教師： 成 績： 摘要提高信息傳輸?shù)挠行院涂煽啃允冀K是通信技術(shù)所追求的目標，而信道編碼能夠顯著的提升信息傳輸?shù)目煽啃?。此次課程設(shè)計題目是（15,7）循環(huán)碼的編譯碼方法，首先介紹了線性分組碼的編譯碼原理；其次在matlab平臺下，完成了任意碼的編碼和譯碼，并求出該碼的最小碼距以及其糾錯能力；最后分析了該碼在高斯信道下的誤碼性能。關(guān)鍵詞：循環(huán)碼；編碼；譯碼21目錄摘要1前言1一 基本原理21.1循環(huán)碼的定義21.1.1循環(huán)碼的多項式表示

2、21.1.2(n,k)循環(huán)碼的生成多項式31.1.3循環(huán)碼的生成矩陣和一致校驗矩陣41.2循環(huán)碼編碼原理51.3循環(huán)碼的糾錯原理6二 系統(tǒng)分析93.1循環(huán)碼的編碼流程93.2循環(huán)碼的譯碼流程9三 系統(tǒng)設(shè)計及調(diào)試113.1循環(huán)碼的編碼113.2（15，7）循環(huán)碼的譯碼113.3（15，7）循環(huán)碼的糾檢錯123.4（15,7）循環(huán)碼在高斯信道下的誤碼性能13總結(jié)14參考文獻15附錄16致謝21前言隨著社會經(jīng)濟的迅速發(fā)展和科學(xué)技術(shù)的全面進步，計算機事業(yè)的飛速發(fā)展，以計算機與通信技術(shù)為基礎(chǔ)的信息系統(tǒng)正處于蓬勃發(fā)展的時期。隨著經(jīng)濟文化水平的顯著提高，人們對生活質(zhì)量及工作軟件的要求也越來越高。在計算機通信

3、信息碼中循環(huán)碼是線性分組碼的一個重要子集，是目前研究得最成熟的一類碼。它有許多特殊的代數(shù)性質(zhì)，它使計算機通信以一種以數(shù)據(jù)通信形式出現(xiàn)，實現(xiàn)了在計算機與計算機之間或計算機與終端設(shè)備之間進行有效的與正確地信息傳遞，它使得現(xiàn)代通信的可靠性與有效性實現(xiàn)了質(zhì)的飛躍。它是現(xiàn)代計算機技術(shù)與通信技術(shù)飛速發(fā)展的產(chǎn)物，在日常生活通信領(lǐng)域、武器控制系統(tǒng)等領(lǐng)域都被廣泛應(yīng)用。數(shù)字信號在傳輸中往往由于各種原因，使得在傳送的數(shù)據(jù)流中產(chǎn)生誤碼，從而使接收端產(chǎn)生圖象跳躍、不連續(xù)、出現(xiàn)馬賽克等現(xiàn)象。所以通過信道編碼這一環(huán)節(jié)，對數(shù)碼流進行相應(yīng)的處理，使系統(tǒng)具有一定的糾錯能力和抗干擾能力，可極大地避免碼流傳送中誤碼的發(fā)生。誤碼的處理

4、技術(shù)有糾錯、交織、線性內(nèi)插等。提高數(shù)據(jù)傳輸效率，降低誤碼率是信道編碼的任務(wù)。信道編碼的本質(zhì)是增加通信的可靠性。此次課程設(shè)計題目是（15,7）循環(huán)碼的編譯碼方法，首先學(xué)習(xí)掌握了線性分組碼的編譯碼原理；其次在matlab平臺下，完成了任意碼的編碼和譯碼，并可求出該碼的最小碼距以及其糾錯能力；最后分析了該碼在高斯信道下的誤碼性能。一 基本原理1.1循環(huán)碼的定義循環(huán)碼是線性分組碼的一種，所以它具有線性分組碼的一般特性，此外還具有循環(huán)性。循環(huán)碼的編碼和解碼設(shè)備都不太復(fù)雜，且檢(糾)錯能力強。它不但可以檢測隨機的錯誤，還可以檢錯突發(fā)的錯誤。（n,k）循環(huán)碼可以檢測長為n-k或更短的任何突發(fā)錯誤，包括首尾相

5、接突發(fā)錯誤。 循環(huán)碼是一種無權(quán)碼，循環(huán)碼編排的特點是相鄰兩個數(shù)碼之間符合卡諾圖中的鄰接條件，即相鄰兩個數(shù)碼之間只有一位碼元不同，碼元就是組成數(shù)碼的單元。符合這個特點的有多種方案，但循環(huán)碼只能是表中的那種。循環(huán)碼的優(yōu)點是沒有瞬時錯誤，因為在數(shù)碼變換過程中，在速度上會有快有慢，中間經(jīng)過其它一些數(shù)碼形式，稱它們?yōu)樗矔r錯誤。這在某些數(shù)字系統(tǒng)中是不允許的，為此希望相鄰兩個數(shù)碼之間僅有一位碼元不同，即滿足鄰接條件，這樣就不會產(chǎn)生瞬時錯誤。循環(huán)碼就是這樣一種編碼，它可以在卡諾圖中依次循環(huán)得到。循環(huán)碼又稱格雷碼。循環(huán)碼最大的特點就是碼字的循環(huán)特性，所謂循環(huán)特性是指：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得到的

6、碼組仍然是許用碼組。若（ ）為一循環(huán)碼組，則（）、（）還是許用碼組。也就是說，不論是左移還是右移，也不論移多少位，仍然是許用的循環(huán)碼組。1.1.1循環(huán)碼的多項式表示設(shè)碼長為n的循環(huán)碼表示為（），其中為二進制數(shù)，通常把碼組中各碼元當做二進制的系數(shù)，即把上式中長為n的各個分量看做多項式（1-1）的各項系數(shù)。 （1-1)其中，各碼字與碼多項式一一對應(yīng)，這種多項式中，x僅表示碼元位置的標記,因此我們并不關(guān)心x的取值，這種多項式稱為碼多項式。1.1.2(n,k)循環(huán)碼的生成多項式(n,k)循環(huán)碼的生成多項式寫為g(x),它是(n,k)循環(huán)碼碼集中唯一的，冪次為n-k的碼多項式，則是一個冪次為n的碼多項式

7、。按模()運算，此時： (1-2) 即 （1-3）且因 g(x)也是n階冪，故Q(x)=1。由于它是循環(huán)碼，故按模()運算后的“余式”也是循環(huán)碼的一個碼字，它必能被g(x)整除，即： （1-4）由以上兩式可以得到： （1-5）和 （1-6）從上式中可以看出，生成多項式g(x)應(yīng)該是的一個因式，即循環(huán)碼多項式應(yīng)該是的一個n-k次因式。本課程設(shè)計要求完成任意（15,7）循環(huán)碼的編碼和譯碼，其中給出的生成多項式為：g(x)=x8+x7+x6+x4+1則生成矩陣G為: （1-7）對式（1-7）作線性變換，整理成典型形式的系統(tǒng)生成矩陣: （1-8）若信息碼元與式（1-8）相乘，得到的就是系統(tǒng)循環(huán)碼。1.

8、1.3循環(huán)碼的生成矩陣和一致校驗矩陣對所有的i=0,1,2,k-1，用生成多項式g(x)除，有： （1-9）式中是余式，表示為： （1-10）因此，是g(x)的倍式，即是碼多項式，由此得到系統(tǒng)形式的生成矩陣為： (1-11) 它是一個kn階的矩陣。同樣，由G=0可以得到系統(tǒng)形式的一致校驗矩陣為： （1-12）由于在本課程設(shè)計中，由于生成多項式為：g(x)=x8+x7+x6+x4+1，校驗多項式為 h(x)= xn +1/g(x)，因此可由長除法求得校驗多項式為h(x)=x7+x6+x4+1，所以校驗矩陣H為： （1-13）對式（1-13）作線性變換，整理成典型形式的系統(tǒng)生成矩陣: （1-14）

9、1.2循環(huán)碼編碼原理有信息碼構(gòu)成信息多項式，其中最高冪次為k-1；用乘以信息多項式m(x)，得到的，最高冪次為n-1，該過程相當于把信息碼（，）移位到了碼字德前k個信息位，其后是r個全為零的監(jiān)督位；用g(x)除得到余式r(x),其次數(shù)必小于g(x)的次數(shù)，即小于（n-k），將此r(x)加于信息位后做監(jiān)督位，即將r(x)于相加，得到的多項式必為一碼多項式。1.3循環(huán)碼的糾錯原理糾錯碼的譯碼是該編碼能否得到實際應(yīng)用的關(guān)鍵所在。譯碼器往往比編碼較難實現(xiàn)，對于糾錯能力強的糾錯碼更復(fù)雜。根據(jù)不同的糾錯或檢錯目的，循環(huán)碼譯碼器可分為用于糾錯目的和用于檢錯目的的循環(huán)碼譯碼器。 通常，將接收到的循環(huán)碼組進行除

10、法運算，如果除盡，則說明正確傳輸；如果未除盡，則在寄存器中的內(nèi)容就是錯誤圖樣，根據(jù)錯誤圖樣可以確定一種邏輯，來確定差錯的位置，從而達到糾錯的目的。用于糾錯目的的循環(huán)碼的譯碼算法比較復(fù)雜，感興趣的話可以參考一些參考書。而用于檢錯目的循環(huán)碼，一般使用ARQ通信方式。檢測過程也是將接受到的碼組進行除法運算，如果除盡，則說明傳輸無誤；如果未除盡，則表明傳輸出現(xiàn)差錯，要求發(fā)送端重發(fā)。用于這種目的的循環(huán)碼經(jīng)常被成為循環(huán)冗余校驗碼，即CRC校驗碼。CRC校驗碼由于編碼電路、檢錯電路簡單且易于實現(xiàn)，因此得到廣泛的應(yīng)用。在通過MODEM傳輸文件的協(xié)議如ZMODEM、XMODEM協(xié)議中均用到了CRC校驗技術(shù)。在磁

11、盤、光盤介質(zhì)存儲技術(shù)中也使用該方法。 當碼字c通過噪聲信道傳送時，會受到干擾而產(chǎn)生錯誤。如果信道產(chǎn)生的錯誤圖樣是e，譯碼器收到的n重接受矢量是y,則表示為： （1-15）上式也可以寫成多項式形式： （1-16）譯碼器的任務(wù)就是從y(x)中得到，然后求的估值碼字 （1-17） 并從中得到信息組。循環(huán)碼譯碼可按以下三個步驟進行： （1）有接收到的y(x)計算伴隨式s(x)； （2）根據(jù)伴隨式s(x)找出對應(yīng)的估值錯誤圖樣； （3）計算，得到估計碼字。若,則譯碼正確，否則，若，則譯碼錯誤。本課程設(shè)計中采用（15,7）循環(huán)碼由生成矩陣可得其最小碼距dmin為5；由最小碼距可得其糾檢錯能力可知其最多可檢

12、4位錯，可糾2位錯。其伴隨式如表1所示：表1 （15，7）循環(huán)碼錯誤圖樣表錯誤圖樣伴隨式糾錯e=0 0 0 0 0 0 0 0 0 0 0 0 0 0 0S=0 0 0 0 0 0 0 0無錯e=0 0 0 0 0 0 0 0 0 0 0 0 0 0 1S=1 0 0 0 0 0 0 0第一位錯e=0 0 0 0 0 0 0 0 0 0 0 0 0 1 0S=0,1,0,0,0,0,0,0第二位錯e=0 0 0 0 0 0 0 0 0 0 0 0 1 0 0S=0,0,1,0,0,0,0,0第三位錯e=0 0 0 0 0 0 0 0 0 0 0 1 0 0 0S=0,0,0,1,0,0,0,0

13、第四位錯e=0 0 0 0 0 0 0 0 0 0 1 0 0 0 0S=1,0,0,0,1,0,0,0第五位錯e=0 0 0 0 0 0 0 0 0 1 0 0 0 0 0S=0,1,0,0,0,1,0,0第六位錯e=0 0 0 0 0 0 0 0 1 0 0 0 0 0 0S=1,0,1,0,0,0,1,0第七位錯e=0 0 0 0 0 0 0 1 0 0 0 0 0 0 0S=1,1,0,1,0,0,0,1第八位錯e=0 0 0 0 0 0 1 0 0 0 0 0 0 0 0S=0,1,1,0,1,0,0,0第九位錯e=0 0 0 0 0 1 0 0 0 0 0 0 0 0 0S=0,0

14、,1,1,0,1,0,0第十位錯e=0 0 0 0 1 0 0 0 0 0 0 0 0 0 0S=0,0,0,1,1,0,1,0第十一位錯e=0 0 0 1 0 0 0 0 0 0 0 0 0 0 0S=0,0,0,0,1,1,0,1第十二位錯e=0 0 1 0 0 0 0 0 0 0 0 0 0 0 0S=0,0,0,0,0,1,1,0第十三位錯e=0 1 0 0 0 0 0 0 0 0 0 0 0 0 0S=0,0,0,0,0,0,1,1第十四位錯e=1 0 0 0 0 0 0 0 0 0 0 0 0 0 0S=0,0,0,0,0,0,0,1第十五位錯以上指出了系統(tǒng)循環(huán)碼的譯碼方法：將收到

15、的碼字R(x) 用g(x) 去除，如果除盡則無錯；否則有錯。如果有錯，可由余式S(x) 一一找出對應(yīng)圖樣，然后將錯誤圖樣E(x) 與R(x) 模2 和，即為所求碼字C(x) ，從而實現(xiàn)糾錯目的。二 系統(tǒng)分析本次課題是（15,7）循環(huán)碼的編譯碼方法，包括求出該碼的最小碼距以及其糾錯能力，并分析出該碼在高斯信道下的誤碼性能，則循環(huán)碼的編譯碼過程如下：編碼過程：第一步：將信息碼字表示為，其最高次冪為；第二步：將與求模得出相應(yīng)的余式；第三步：編碼結(jié)果為。3.1循環(huán)碼的編碼流程循環(huán)碼編碼的程序框圖如下圖2-1所示： 初始化確定余式r(x): 確定c(x): 存儲c(x)圖 2-1 編碼程序框圖3.2循環(huán)

16、碼的譯碼流程譯碼過程：第一步：由接收碼字與監(jiān)督矩陣相乘得出錯誤圖樣；第二步：判斷是否為零。若不為零，則出錯。在假定至多只有一位錯的情況下，可以有效地譯了相應(yīng)的信息碼字；第三步：在出錯的情況下，將與標準監(jiān)督矩陣對比，得出錯誤的比特位并進行更正得出前四位為信息碼字。循環(huán)碼譯碼的程序框圖如圖下圖2-2 所示：初始化圖2-2 譯碼程序框圖否存儲c(x)由S(x)確定錯誤圖樣E(x)S(x)=0，無誤碼誤碼由R(x)確定S(x)：糾錯三 系統(tǒng)設(shè)計及調(diào)試3.1循環(huán)碼的編碼任意輸入一組7位二進制循環(huán)碼序列，可對該二進制序列進行編碼，其實現(xiàn)結(jié)果如下圖3-1所示：圖3-1 （15,7）循環(huán)碼的編碼程序仿真結(jié)果圖

17、由圖3-1可得，本程序?qū)崿F(xiàn)了對任意輸入消息進行（15,7）循環(huán)碼的編碼。如圖所示輸入碼字a=1 1 1 0 1 0 1，編碼輸出b= 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1。3.2（15，7）循環(huán)碼的譯碼對上述圖3-1中所輸入循環(huán)碼字a=1 1 1 0 1 0 1的編碼結(jié)果b= 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1進行譯碼，其結(jié)果如下圖3-2所示：圖3-2 （15,7）循環(huán)碼的譯碼程序仿真結(jié)果圖由上圖3-2可得，用編出的碼字譯碼，沒有錯誤，正確譯出原碼。3.3（15，7）循環(huán)碼的糾檢錯將上圖3-2中所編出的碼字任意改變一位輸入譯碼程序，其糾檢錯圖如下圖

18、3-3所示：圖3-3 （15，7）循環(huán)碼糾檢錯一位碼字的仿真圖3.4 （15,7）循環(huán)碼在高斯信道下的誤碼性能 圖3-4 信源產(chǎn)生的序列及無噪輸出序列 圖3-5 循環(huán)碼在高斯信道下的誤碼率總結(jié)此次課程設(shè)計題目是（15,7）循環(huán)碼的編譯碼方法，首先學(xué)習(xí)掌握了線性分組碼的編譯碼原理；其次在matlab平臺下，完成了任意碼的編碼和譯碼，并求出該碼的最小碼距以及其糾錯能力；最后分析了該碼在高斯信道下的誤碼性能。但由于所學(xué)知識有限，在設(shè)計過程中困難有很多，其主要表現(xiàn)在不熟練軟件編程?？傊ㄟ^此次課程設(shè)計，我的收獲有以下幾點：首先，我掌握了（15,7）循環(huán)碼的編譯碼方法，并學(xué)會了如何求出該碼的最小碼距及

19、糾檢錯能力，同時通過觀察該碼通過高斯信道后的仿真結(jié)果，可發(fā)現(xiàn)循環(huán)碼糾檢錯能力強；其次，通過此次課程設(shè)計不僅加深了我對課程理論的了解，并更加熟悉了MATLAB語言，而且它讓我了解了學(xué)習(xí)知識不僅在課本上，可以是網(wǎng)絡(luò)、圖書館，甚至是老師同學(xué)。參考文獻1樊昌信，曹麗娜通信原理（第六版)北京：國防工業(yè)出版社20072徐明遠，邵玉斌MATLAB仿真在通信與電子工程中的應(yīng)用西安：西安電子科技大學(xué)學(xué)出版社20053唐向宏，岳恒立，鄭雪峰等 MATLAB及在電子信息類課程中的應(yīng)用(第二版) 北京：電子工業(yè)出版社，20094 沈保鎖等.現(xiàn)代通信原理.天津科學(xué)技術(shù)出版社.20005 李樂民等.數(shù)字通信傳輸系統(tǒng).人民

20、郵電出版社20066 惠高潮，王輝.論文基于單片機（7，4）循環(huán)碼編碼與譯碼的研究.南京工業(yè)大學(xué)2005附錄源程序代碼如下1.（15,7）循環(huán)碼的編碼clear;clc;a=input(請輸入消息矢量：);%高次項系數(shù)在前的生成多項式Gx=1 0 0 0 1 0 1 1 1;%將數(shù)組a的高位依次放在數(shù)組Data的低位 Data=zeros(1,15); Data(1)=a(7); Data(2)=a(6); Data(3)=a(5); Data(4)=a(4); Data(5)=a(3); Data(6)=a(2); Data(7)=a(1); %Data除以Gx得到余數(shù)Rx Qx,Rx=de

21、conv(Data,Gx); b=Rx+Data; %將數(shù)組b的高位放在后面 c=b(1); b(1)=b(15); b(15)=c; c=b(2); b(2)=b(14); b(14)=c; c=b(3); b(3)=b(13); b(13)=c; c=b(4); b(4)=b(12); b(12)=c; c=b(5); b(5)=b(11); b(11)=c; c=b(6); b(6)=b(10); b(10)=c; c=b(7); b(7)=b(9); b(9)=c; %將數(shù)組b校正for i=1:15 if rem(abs(b(i),2)=0 b(i)=0;end endfor i=1

22、:15 if rem(abs(b(i),2)=1 b(i)=1;endenddisp(輸入序列：);adisp(編碼輸出序列：);b2（15,7）循環(huán)碼的編碼clear;clc;r= 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0;h=1,0,0,0,0,0,0,0;1,1,0,0,0,0,0,0;0,1,1,0,0,0,0,0;1,0,1,1,0,0,0,0;0,1,0,1,1,0,0,0;0,0,1,0,1,1,0,0;0,0,0,1,0,1,1,0;1,0,0,0,1,0,1,1;0,1,0,0,0,1,0,1;0,0,1,0,0,0,1,0;0,0,0,1,0,0,0,1;

23、0,0,0,0,1,0,0,0;0,0,0,0,0,1,0,0;0,0,0,0,0,0,1,0;0,0,0,0,0,0,0,1;b=flipud(h);s=r*b;for i=1:8 if rem(abs(s(i),2)=0 s(i)=0;end endfor i=1:8 if rem(abs(s(i),2)=1 s(i)=1;endend if s=0 0 0 0 0 0 0 0 e=0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; elseif s=1 0 0 0 0 0 0 0 e=0 0 0 0 0 0 0 0 0 0 0 0 0 0 1; elseif s=1,1,0,0

24、,0,0,0,0 e=0 0 0 0 0 0 0 0 0 0 0 0 0 1 0; elseif s=0,1,1,0,0,0,0,0 e=0 0 0 0 0 0 0 0 0 0 0 0 1 0 0; elseif s=1,0,1,1,0,0,0,0 e=0 0 0 0 0 0 0 0 0 0 0 1 0 0 0; elseif s=0,1,0,1,1,0,0,0 e=0 0 0 0 0 0 0 0 0 0 1 0 0 0 0; elseif s=0,0,1,0,1,1,0,0 e=0 0 0 0 0 0 0 0 0 1 0 0 0 0 0; elseif s=0,0,0,1,0,1,1,0 e

25、=0 0 0 0 0 0 0 0 1 0 0 0 0 0 0; elseif s=1,0,0,0,1,0,1,1 e=0 0 0 0 0 0 0 1 0 0 0 0 0 0 0; elseif s=0,1,0,0,0,1,0,1 e=0 0 0 0 0 0 1 0 0 0 0 0 0 0 0; elseif s=0,0,1,0,0,0,1,0 e=0 0 0 0 0 1 0 0 0 0 0 0 0 0 0; elseif s=0,0,0,1,0,0,0,1 e=0 0 0 0 1 0 0 0 0 0 0 0 0 0 0; elseif s=0,0,0,0,1,0,0,0 e=0 0 0 1 0

26、 0 0 0 0 0 0 0 0 0 0; elseif s=0,0,0,0,0,1,0,0 e=0 0 1 0 0 0 0 0 0 0 0 0 0 0 0; elseif s=0,0,0,0,0,0,1,0 e=0 1 0 0 0 0 0 0 0 0 0 0 0 0 0; else s=0,0,0,0,0,0,0,1 e=1 0 0 0 0 0 0 0 0 0 0 0 0 0 0; endu=r+e;for i=1:15 if rem(abs(u(i),2)=0 u(i)=0;end endfor i=1:15 if rem(abs(u(i),2)=1 u(i)=1;endendData=z

27、eros(1,7); Data(1)=u(9); Data(2)=u(10); Data(3)=u(11); Data(4)=u(12); Data(5)=u(13); Data(6)=u(14); Data(7)=u(15);if e=0 0 0 0 0 0 0 0 0 0 0 0 0 0 0disp(沒有錯誤：)k=0,elsedisp(第幾位錯誤：) k=find(e) ;enddisp(接收碼字)rdisp(譯碼輸出序列：)Data3循環(huán)碼編碼與解碼Matlab源程序（實驗以（7，4）循環(huán)碼進行分析） n = 15; %定義碼長k = 7; %信息位長msg = randint(k*4

28、,1,2); %隨機提取信號，引起一致地分布的任意整數(shù)矩陣subplot(2,2,1)stem(msg)title(編碼器輸入信號)p=cyclpoly(n,k) %循環(huán)碼生成多項式，n=7，k=4code = encode(msg,n,k,cyclic,p); %編碼函數(shù)，對信號進行差錯編碼subplot(2,2,2)stem(code)title(編碼器輸出信號)recode=decode(code,n,k,cyclic,p) %對信號進行譯碼，對接收到的碼字進行譯碼，恢復(fù)出原始的信息，譯碼參數(shù)和方式必須和編碼時采用的嚴格相同subplot(2,2,3)stem(recode)title(譯碼器輸出信號)t=-1:0.01:1;x=recode; %將recode賦值給x，并進行長度與fft設(shè)定N=length(x);fx=