線性分組碼的編譯碼講解

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

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

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

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

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

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

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

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

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

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

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

12、。是一種計算機(jī)程序設(shè)計語言。它既具有高級語言的特點，又具有匯編語言的特點。它可以作為工作系統(tǒng)設(shè)計語言，編寫系統(tǒng)應(yīng)用程序，也可以作為應(yīng)用程序設(shè)計語言，編寫不依賴計算機(jī)硬件的應(yīng)用程序。各類科研都需要用到C語言，具體應(yīng)用比如單片機(jī)以及嵌入式系統(tǒng)開發(fā)。其語言特點如下： （1）C是中級語言。它把高級語言的基本結(jié)構(gòu)和語句與低級語言的實用性結(jié)合起來。C 語言可以像匯編語言一樣對位、字節(jié)和地址進(jìn)行操作， 而這三者是計算機(jī)最基本的工作單元。 （2）C是結(jié)構(gòu)式語言。結(jié)構(gòu)式語言的顯著特點是代碼及數(shù)據(jù)的分隔化，即程序的各個部分除了必要的信息交流外彼此獨立。這種結(jié)構(gòu)化方式可使程序?qū)哟吻逦阌谑褂?、維護(hù)以及調(diào)試。C 語

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

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

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

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

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

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

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

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

21、(n);printf( - 輸入c代表編碼函數(shù)Code -);printf(n); printf(n);printf( - 輸入d代表譯碼函數(shù)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(編碼結(jié)果為: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、監(jiān)督矩陣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的轉(zhuǎn)置矩陣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