1、 *實踐教學* 蘭州理工大學計算機與通信學院2013年秋季學期計算機通信 課程設計 題 目： 線性分組碼（7,3）碼的編譯碼仿真設計 專業班級： 通信工程三班 姓 名： 彭佳峰 學 號： 10250302 指導教師： 彭 鐸 成 績： 摘要 本課題是應用C語言對（7,3）線性分組碼的編譯碼的軟件設計。主要做了一下幾項工作：對三位正確的信息碼進行編碼；若輸入的三位信息碼有錯，系統輸出提醒，可以重新輸入；對七位接收到的碼字判斷是否有錯，并在無錯和有一位錯誤時進行譯碼，在有多位錯誤時輸出提醒，可以選擇重新輸入。 關鍵字：線性分組碼 編碼 譯碼 C語言目錄前言11 基本原理21.1線性分組碼的基本概念

2、21.2差錯控制原理21.3線性分組碼的糾檢錯能力32線性分組碼的編碼42.1監督矩陣42.2生成矩陣53線性分組碼的譯碼74設計與仿真94.1 C語言平臺簡介94.2整體流程圖94.3編碼流程圖104.4譯碼流程圖10 5 仿真結果及分析11設計總結17參考文獻18致謝19附錄20前言近年來，隨著計算機、衛星通信及高速數據網的飛速發展，數據的交換、處理和存儲技術得到了廣泛應用，人們對數據傳輸和存儲系統的可靠性提出了越來越高的要求。因此，如何控制差錯、提高數據傳輸和存儲的可靠性，成為現代數字通信系統設計工作者所面臨的重要課題。香農第二定理指出，當信息傳輸率低于信道容量時，通過某種編譯碼方法，就

3、能使錯誤率為任意小。差錯控制編碼在此定理指導下迅速發展起來，它使得傳輸數據本身帶有規律性，利用規律性來減少錯誤。線性分組碼是差錯控制編碼的重要一種。它的規律性在于局限在一個碼組之內，編碼后長為n的一個碼組中含有k位信息元和n-k位監督元，監督元是隨所傳輸的信息元而改變的。接收端正式通過監督元和信息元之間的規律性來發現并糾正錯誤的。1 基本原理1.1線性分組碼的基本概念 （1）線性分組碼線性分組碼是一組固定長度的碼組，可表示（n，k），通常它用于前向糾錯。在分組碼中，監督位被加到信息位之后，形成新的碼。在編碼時，k個信息位被編為n位碼組長度，而n-k個監督位的作用就是實現檢錯與糾錯。當分組碼的信

4、息碼元與監督碼元之間的關系為線性關系時，這種分組碼就稱為線性分組碼。對于長度為n的二進制線性分組碼，它有種可能的碼組，從碼組中，可以選擇個碼組（kn)組成一種碼，稱為許用碼組。這樣，一個k比特信息的線性分組碼可以映射到一個長度為n的碼組上，該碼組是從碼組構成的碼集中選出來的，這樣剩下的碼組就可以對個分組碼進行檢錯或糾錯。（2） 碼重（漢明重量） 把碼組中非零位的數量定義為碼重。（3）碼距（漢明距離）兩個碼組對應位上數字不同的個數稱為碼組的距離，簡稱碼距。原則是，讓選擇的這些碼字的碼距越長越好。1.2差錯控制原理 將信息碼分組，并為每個信息組附加若干監督的編碼，稱為“分組碼”。在分組碼中，監督碼

5、元僅監督本組碼中的信息碼元。分組碼一般用符號（n）、（k）表示，其中k是每組碼二進制信息碼元的數目。n是碼組的總位數，又稱為碼組的長度。r=n-k為每個碼組中的監督碼元數目，或稱監督位數目。 k位二進制數構成的碼組集合為種不同的碼組，若組都為有用碼組，其中任意碼組出現錯誤都將變成另一碼組，則接收端無法檢測識別哪一組出錯。若只取部分碼組為有用碼組，則在傳輸過程中如接收端接收到的碼組為非許用碼組即禁用碼組時，則可知傳輸錯誤。以3位二進制數構成的碼組為例，它有8種不同的可能組合，若將其全部用來表示天氣，則可以表示8種不同天氣，例如：000晴、001云、010陰、011雨、100血、101霜、110霧

6、、111雹。其中任一碼組在傳輸中若發生一個或多個錯誤，則將變成另一個信息碼組。這時接收端無法發現錯誤。若在上述8種碼組中次序使用4種來傳達天氣，例如：000晴、011云、101陰、110雨。這時，雖然只能傳達4種不同天氣，但是接收端卻可能發現碼組中的一個錯碼。如000錯碼一位，則接收碼組將變成100或011，這三種碼組都為禁用碼組，故接收端認為接收碼錯誤。要想能夠糾正錯誤，需增加冗余度。1.3線性分組碼的糾檢錯能力 最小碼距與碼的抗干擾能力之間的關系，通過證明（不給出詳細的證明過程），可以得到如下的結論，具體如下：若一種碼的最小距離為，則它能檢查傳輸差錯個數（稱為檢錯能力）e應滿足；若一種碼的

7、最小距離為，則它能糾正傳輸差錯個數t應滿足；若一種碼的最小距離為，則能檢查e個錯誤，同時又能糾正t個一下錯誤的條件是。2線性分組碼的編碼2.1監督矩陣 （n,k)碼中有n-k個監督元，例如（7,3）碼，以序列表示碼組，前面三位為信息元。監督元根據以下四個線性方程求得： （2.1） 通常稱這四個線性方程為（7,3）碼的一致監督關系或一致監督方程組。表一 信息碼與許用碼組對應表 一致監督關系是從個n重矢量中挑選出來的，具有封閉性。把這種結構形式的線性分組碼稱為線性系統分組碼。信息組碼組信息組碼組0000000000100100111000100111011011010011010010011111

8、0110100101101110101111110100 將一致的監督方程組移動并記成矩陣形式：（2.2） 或者記成以下形式： （2.3） （2.4）式中P是階矩陣，是r階單位方陣。稱具有這種子形式的H矩陣為典型陣。上式可以簡寫成： 一致監督矩陣H完全確定了線性分組碼的規律性，找到了H矩陣也就確定了線性分組碼的構造。2.2生成矩陣生成矩陣反映了信息元和監督元之間的直接關系。對于上例，可將編碼方程改寫為： （2.5） 式中 （2.6）稱為（7,3）碼的生成矩陣。系統碼的生成矩陣具有的形式，稱為典型生成矩陣。通常，二進制（n,k)線性系統碼的生成矩陣G具有如下形式： （2.7）G矩陣的每行都是一個

9、碼字。有了G矩陣或H矩陣，線性分組碼的構造就確定了，根據C=IG，就可計算出該碼組的全部碼元。 比較P矩陣和Q矩陣，便知,或。這就是說，P的第一行就是Q的第一列，P的第二行就是Q的第二列.因此，H一定，Q也就確定，反之亦然。 （2.8） （2.9）3線性分組碼的譯碼為了描述數據在傳輸信道中出現差錯的情況，引入了錯誤圖樣的概念。錯誤圖樣：錯誤圖樣是接收序列和發送序列之間的差，用表示。在錯誤圖樣中，表示對應位沒有傳錯，表示傳輸有錯。例如：發送序列,接收序列，則錯誤圖樣。可見，在譯碼時，只要設法從中找到錯誤圖樣，就可恢復發送端發送的碼字,。因此，譯碼的任務就是要找到。首先，我們假定:發送碼組為,接收

10、碼組為,錯誤圖樣。若，說明與不同，碼字的位發生了錯誤。由于每個碼字必須滿足矩陣每行所確定的線性方程，因而收到后，可用矩陣檢查，若等于則認為是碼字，沒有錯誤；否則就認為不是碼字，產生了錯誤。定義:，將稱為接收向量的伴隨式。顯然僅與錯誤圖樣有關，而與發送的碼字無關。若,則；若，則。因此根據是否可為可進行碼字的檢查。假如接收碼字中只有一位碼元發送錯誤，又設錯誤在第為，即，其它的均為，則為的第行，為的第列。 （3.1） (3.2) (3.3) (3.4)接收端根據這個結果便可判斷出接收碼的第位發生錯誤，從而實現糾錯。如果接收碼組中有多位碼元同時發生錯誤，設錯誤在，位，即，其余的，同理可知： （3.5）

11、這說明相當于H矩陣的第，列的線性組合，假設這個線性組合為0，即伴隨式序列，則在接收端是不能判斷出接收碼組中中有錯（此時的錯誤稱不可檢錯誤）。假設這個線性組合恰好相當于矩陣的某一列，在接收端根據這個結果來糾錯，則會做出錯誤的糾正；假設這個線性組合的結果與矩陣中的任一列都不相當，則根據這個結果只能檢測出中有錯，而不能進行糾正。綜上所述，一個（n,k)碼要能糾正所有單個錯，則由所有單個錯誤圖樣確定的均不相同且不等于。若要能糾正個錯誤，顯然要求個錯的所有可能組合的錯誤模式都必須有不同的伴隨式與之對應。4設計與仿真4.1 C語言平臺簡介C語言是Combined Language（組合語言）的中英混合簡稱

12、。是一種計算機程序設計語言。它既具有高級語言的特點，又具有匯編語言的特點。它可以作為工作系統設計語言，編寫系統應用程序，也可以作為應用程序設計語言，編寫不依賴計算機硬件的應用程序。各類科研都需要用到C語言，具體應用比如單片機以及嵌入式系統開發。其語言特點如下： （1）C是中級語言。它把高級語言的基本結構和語句與低級語言的實用性結合起來。C 語言可以像匯編語言一樣對位、字節和地址進行操作， 而這三者是計算機最基本的工作單元。 （2）C是結構式語言。結構式語言的顯著特點是代碼及數據的分隔化，即程序的各個部分除了必要的信息交流外彼此獨立。這種結構化方式可使程序層次清晰，便于使用、維護以及調試。C 語

13、言是以函數形式提供給用戶的，這些函數可方便的調用，并具有多種循環、條件語句控制程序流向，從而使程序完全結構化。 （3）C語言功能齊全。具有各種各樣的數據類型，并引入了指針概念，可使程序效率更高。另外C語言也具有強大的圖形功能，支持多種顯示器和驅動器。 （4）C語言適用范圍大。適合于多種操作系統，如Windows、DOS、UNIX等等；也適用于多種機型。 （5）C語言對編寫需要硬件進行操作的場合，明顯優于其它解釋型高級語言，有一些大型應用軟件也是用C語言編寫的。 開始 結束編碼函數解碼函數 選擇函數4.2整體流程圖 圖4.1 整體流程圖 4.3編碼流程圖 初始化輸入信息碼C13并代 入編碼方程

14、存儲并輸出編碼結果 C27 返回 圖4.2 編碼流程圖 4.4譯碼流程圖 初始化輸入接收到的碼字R17輸入生成矩陣G37，計算出監督矩陣H47其轉置矩陣HT74計算出伴隨式S4圖4.3 譯碼流程圖 S4=0000 S4=HT74的 第i行接收端認為傳輸有錯，但不能糾正錯誤圖樣E7=0000000接收端認為傳輸無錯輸出譯碼結果R2i=R1i+Ei 返回接收端認為傳輸中有一個錯誤，此時錯誤圖樣Ei=1 5 仿真結果及分析(1) 初始化界面設置 圖5.1 初始化界面的設置 通過初始化界面，可以選擇編碼或者譯碼。（2） 編碼的結果圖5.2 輸入信息碼為111時的編碼結果 圖5.3 輸入信息碼為010和

15、110時的編碼結果 圖5.4 輸入信息碼為101和011時的編碼結果 三位信息碼有八種情況，即000,001,010,011,100,101,110,111.通過編碼程序的編碼結果來看，與表1對比，發現編碼結果與理論值相一致，表明程序正確。（3）輸入信息碼中有非二進制碼是的處理結果 圖5.5 輸入信息碼有錯誤時的提醒示意圖(4) 譯碼的結果 圖5.6 監督矩陣及轉置矩陣的計算示意圖 （5）正確譯碼時的運行結果圖5.7 譯碼正確時的示意圖 （6） 運行錯誤時的結果 圖5.8 運行有一個錯誤時的結果示意圖圖5.9 運行有兩位錯碼時的結果示意圖設計總結 此次課程設計主要針對線性分組碼編碼譯碼提出自己

16、的設計方案，并利用C語言來實現自己的軟件設計。設計中用到了很多計算機通信課程中學到的知識，例如：差錯控制技術等。由于對所學概念掌握的不準確，原理不是很清晰，雖然條條框框的理論知識一大推，但由于沒有經過實踐的檢驗，當正式用時卻不知道怎么用，更不知道該往哪用，從而導致在設計的過程中不能抓住重點，不清楚到底該怎么做，使得在設計過程中繞了許多彎路，做了許多的無用功。設計過程中查閱了大量的有關線性分組碼編碼與譯碼的書籍，鞏固了以前所學過的知識，而且學到了很多在書本上所沒有學到過的知識。通過這次課程設計使我懂得了理論與實際相結合的必要性，只有理論知識是遠遠不夠的，它更多的只是用來應付考試，而當正真實際操作

17、時卻是困難重重，所以只有把所學的理論知識與實踐相結合起來，并從理論中得出結論，才能真正為社會服務，從而提高自己的實際動手能力和獨立思考的能力。在設計過程中遇到的問題，可以說得是很多，例如剛開始時，對線性分組碼的理解不是很透徹，不知道其編碼與譯碼的方法；后來剛熟悉了原理，卻因為對C語言知識掌握不扎實，編寫不出來正確的程序，以致又花費了好多時間繼續學習C語言 編程和上網查找相關資料，導致惡性循環，待編好程序時已費了很多功夫，這畢竟跟平時的理論知識有著很大的關聯，故在以后的學習中一定要穩扎穩打，深刻理解理論知識，為今后的實踐性活動打下堅實的基礎，以免到時又像這次一樣再費周折；同時在設計的過程中發現了

18、自己的不足之處，對以前所學過的知識理解得不夠深刻，掌握得不夠牢固。總之，通過這次課程設計之后，我發現自己的不足之處還很多，我下去以后一定把以前所學過的知識重新溫故。對我而言，知識上的收獲重要，精神上的豐收更加可喜。讓我知道了學無止境的道理。我們每一個人永遠不能滿足于現有的成就，人生就像在爬山，一座山峰的后面還有更高的山峰在等著你。挫折是一份財富，經歷是一份擁有。這次課程設計必將成為我人生旅途上一個非常美好的回憶！參考文獻1 吳玲達，李國輝，楊冰 等著. 計算機通信原理與技術M. 國防科技大 學出版，2003,32 潘新民 著. 計算機通信技術M. 電子工業出版社，2003,73 孫麗華 著.

19、信息論與糾錯編碼M. 電子工業出版社，2005,34 Proakis 著. 張力軍 譯. 數字通信（第四版）M. 電子工業出版社，2004,75 龐振平，韓松洋，崔樹林 著. 計算機程序設計基礎M.華南理工大學出版社， 2007,2致謝這次課程設計得以順利完成，要感謝的人實在太多了。首先我要衷心感謝我的指導老師彭老師，您嚴謹的治學態度，開闊的思維，循循善誘的指導一直給我很大的幫助。在做課程設計的過程中遇到了很多困難。但是每次彭老師都給我耐心的指導，我從中學到了很多知識。彭老師教學的態度和對學術一絲不茍的精神，是我一生要學習的榜樣，這將對我以后的生活和學習產生積極的影響。同時我還要感謝在這次課程

20、設計中給與我幫助的同學，是你們在我有困難時伸出援助之手，給我講解，幫忙調試電路，正是你們的幫助與支持，我才能克服一個個困難，才能順利地完成這次課程設計,謝謝你們。附錄/*這是（7,3）線性分組碼的編譯碼及驗證程序*/#include#include#include/*函數聲明*/void Begin();void Code();void Decoding();/*主函數*/main()printf(n這是（7,3）線性分組碼的編譯碼及驗證的軟件設計：n);printf(n);Begin();void Begin()char ch;fflush(stdin);printf( -n);printf

21、(n);printf( - 輸入c代表編碼函數Code -);printf(n); printf(n);printf( - 輸入d代表譯碼函數Decoding -);printf(n);printf(n);printf( -n);ch=getchar();if(ch=c)Code(); else if(ch=d)Decoding();void Code()int C13,C27;int i;printf(輸入三位信息碼:n);for(i=0;i3;i+)scanf( %d,&C1i);for(i=0;i3;i+)if(C1i!=0&C1i!=1)printf(輸入的信息碼有錯，請檢查后重新選擇

22、輸入n); Begin();for(i=0;i3;i+)C2i=C1i;C23=C10+C12;C24=C10+C11+C12;C25=C10+C11;C26=C11+C12;for(i=0;i7;i+)if(C2i=2)C2i=0;else if(C2i=3)C2i=1;printf(編碼結果為:n);for(i=0;i7;i+)printf( %d,C2i);printf(n);printf(_n); Begin();void Decoding()int G37,P34,Q43,R17,HT73,R27,C3;int H47=0,S4=0,E7=0;int i,j,n,k,t=0;prin

23、tf(n輸入生成矩陣G:n);for(i=0;i3;i+)for(j=0;j7;j+)scanf( %d,&Gij);printf(n計算出矩陣P:n);for(i=0;i3;i+)for(j=3;j7;j+)Pij-3=Gij; for(i=0;i3;i+)for(j=0;j4;j+)printf(%20d,Pij);printf(n);printf(計算出矩陣Q:n);for(i=0;i3;i+)for(j=0;j4;j+)Qji=Pij;for(i=0;i4;i+)for(j=0;j3;j+) printf(%26d,Qij); printf( );printf(n);printf(計算

24、監督矩陣H:n);for(i=0;i4;i+)for(j=0;j3;j+)Hij=Qij;for(i=0;i4;i+)j=3;Hii+j=1;for(i=0;i4;i+)for(j=0;j7;j+)printf(%11d,Hij);printf( );printf(n);printf(計算H的轉置矩陣HT:n);for(i=0;i4;i+)for(j=0;j7;j+)HTji=Hij;for(i=0;i7;i+)for(j=0;j4;j+)printf(%20d,HTij);printf(n);printf(輸入接收到的碼字R1:n);for(i=0;i7;i+)scanf( %d,&R1i);printf(計算伴隨式S:n);for(i=0;i4;i+)for(j=0;j7;j+)Si=S