./*******************實踐教學*******************XX理工大學計算機與通信學院2012年秋季學期計算機通信課程設計題目：〔7,4漢明碼編譯碼軟件設計專業班級：姓名：學號：指導教師：成績：摘要漢明碼是一種能自動檢錯并糾正一位錯碼的線性糾錯碼,用于信道編碼與譯碼中,高通信系統抗干擾的能力。本次課設主要是〔7,4漢明碼的編譯碼軟件設計,該軟件可以對輸入的多個四位信息碼進行編碼,對于接收的多個七位信息碼可以進行譯碼,從而譯出四位信息位.當接收到的信息碼有一位錯誤時,可以糾正這一位錯碼,進而譯出正確的信息碼組,整個程序使用C語言編寫.關鍵詞：漢明碼、編碼、譯碼、檢錯、糾錯.目錄一、C語言簡介11.1什么是C語言11.2C語言的特點11.3運行C程序的步驟與方法2二、漢明碼編碼42.1漢明碼編碼原理42.2監督矩陣62.3生成矩陣7三、漢明碼糾錯檢錯93.1漢明距離93.2漢明碼糾錯原理9四、漢明碼編譯碼的實現過程104.1編碼過程104.2譯碼過程10五、軟件設計及測試分析125.1程序流程圖125.1.2編碼程序流程圖125.1.3譯碼程序流程圖135.2軟件運行分析15主程序運行分析155.2.2編碼運行分析175.2.3譯碼運行分析185.3軟件分析19總結20參考文獻21附錄22.一、C語言簡介1.1什么是C語言C語言是一種計算機程序設計語言。它既具有高級語言的特點,又具有匯編語言的特點。它由美國貝爾研究所的D.M.Ritchie于1972年推出。1978后,C語言已先后被移植到大、中、小及微型機上。它可以作為工作系統設計語言,編寫系統應用程序,也可以作為應用程序設計語言,編寫不依賴計算機硬件的應用程序。它的應用范圍廣泛,具備很強的數據處理能力,不僅僅是在軟件開發上,而且各類科研都需要用到C語言,適于編寫系統軟件,三維,二維圖形和動畫。具體應用比如單片機以及嵌入式系統開發。1.2C語言的特點一種語言之所以能存在和發展,并具有較強的生命力,總是有不同于其他語言的特點。主要的優缺點介紹如下。優點簡潔緊湊、靈活方便。C語言一共只有32個關鍵字,9種控制語句,程序書寫形式自由,區分大小寫。把高級語言的基本結構和語句與低級語言的實用性結合起來。C語言可以像匯編語言一樣對位、字節和地址進行操作,而這三者是計算機最基本的工作單元。運算符豐富。C語言的運算符包含的范圍很廣泛,共有34種運算符。C語言把括號、賦值。強制類型轉換等都作為運算符處理。從而使C語言的運算類型極其豐富,表達式類型多樣化。靈活使用各種運算符可以實現在其它高級語言中難以實現的運算。數據類型豐富。C語言的數據類型有：整型、實型、字符型、數組類型、指針類型、結構體類型、共用體類型等。能用來實現各種復雜的數據結構運算。并引入了指針概念,使程序效率更高。另外C語言具有強大的圖形功能,支持多種顯示器和驅動器。且計算功能、邏輯判斷功能強大。C是結構式語言。結構式語言的顯著特點是代碼及數據的分隔化,即程序的各個部分除了必要的信息交流外彼此獨立。這種結構化方式可使程序層次清晰,便于使用、維護以及調試。C語言是以函數形式提供給用戶的,這些函數可方便的調用,并具有多種循環、條件語句控制程序流向,從而使程序完全結構化。語法限制不太嚴格,程序設計自由度大。雖然C語言也是強類型語言,但它的語法比較靈活,允許程序編寫者有較大的自由度。允許直接訪問物理地址,對硬件進行操作。由于C語言允許直接訪問物理地址,可以直接對硬件進行操作,因此它既具有高級語言的功能,又具有低級語言的許多功能,能夠像匯編語言一樣對位、字節和地址進行操作,而這三者是計算機最基本的工作單元,可用來寫系統軟件。生成目標代碼質量高,程序執行效率高。一般只比匯編程序生成的目標代碼效率低10へ20%。適用范圍大,可移植性好。C語言有一個突出的優點就是適合于多種操作系統,如DOS、UNIX、windows98．windowsNT；也適用于多種機型。C語言具有強大的繪圖能力,可移植性好,并具備很強的數據處理能力,因此適于編寫系統軟件,三維,二維圖形和動畫,它也是數值計算的高級語言。缺點C語言的缺點主要表現在數據的封裝性上,這一點使得C在數據的安全性上有很大缺陷,這也是C和C++的一大區別。C語言的語法限制不太嚴格,對變量的類型約束不嚴格,影響程序的安全性,對數組下標越界不作檢查等。從應用的角度,C語言比其他高級語言較難掌握。1.3運行C程序的步驟與方法為了使計算機能按照人的意志進行工作,必須根據問題的要求,編寫出相應的程序。為了使計算機能執行高級語言源程序,必須先用一種稱為"編譯程序"的軟件,把源程序翻譯成二進制形式的"目標程序",然后再將該目標程序與系統的函數庫以及其他目標程序連接起來,形成可執行的目標程序。在編好一個C源程序后如何上機運行呢？在紙上寫好一個程序后,要經過這樣幾個步驟：上機輸入與編輯源程序對源程序進行編譯與庫函數連接運行目標程序。以上過程如圖2所示。圖中實線表示操作流程,虛線表示文件的輸入輸出。例如,編輯后得到源程序文件f.c,然后在進行編譯時再將源程序文件f.c輸入,經過編譯得到目標程序文件f.obj,再將目標程序f.obj輸入內存,與系統提供的庫函數等連接,得到可執行的目標程序f.exe,最后把f.exe調入內存再使之運行。圖1C語言運行流程圖二、漢明碼編碼2.1漢明碼編碼原理Hamming碼中文稱作漢明碼。漢明碼是由漢明于1950年提出的,具有糾正一位錯誤能力的線性分組碼它的突出特點是：編譯碼電路簡單,易于硬件實現；用軟件實現編譯碼算法時,軟件效率高；而且性能比較好.一般來說,若漢明碼長為n,信息位數為k,則監督位數r=n-k。若希望用r個監督位構造出r個監督關系式來指示一位錯碼的n種可能位置,則要求或〔1下面以〔7,4漢明碼為例說明原理：設漢明碼〔n,k中k=4,為了糾正一位錯碼,由式〔1可知,要求監督位數r≥3。若取r=3,則n=k+r=7。我們用來表示這7個碼元,用的值表示3個監督關系式中的校正子,則的值與錯誤碼元位置的對應關系可以規定如表1所列。表1校正子和錯碼位置的關系錯碼位置錯碼位置001101010110100111011000無錯碼則由表1可得監督關系式：<2><3><4>在發送端編碼時,信息位的值決定于輸入信號,因此它們是隨機的。監督位、、應根據信息位的取值按監督關系來確定,即監督位應使式〔2-式〔4中、、的值6為0〔表示編成的碼組中應無錯碼〔5式〔5經過移項運算,接觸監督位〔6由上面方程可得到表2所示的16個許用碼組。在接收端收到每個碼組后,計算出、、,如果不全為0,則表示存在錯誤,可以由表1確定錯誤位置并予以糾正。舉個例子,假設收到碼組為0000011,可算出,由表1可知在上有一誤碼。通過觀察可以看出,上述〔7,4碼的最小碼距為,糾正一個誤碼或檢測兩個誤碼。如果超出糾錯能力則反而會因"亂糾"出現新的誤碼.表2〔7,4漢明碼的許用碼組信息位監督位信息位監督位0000000100100011010001010110011100001110111011010101100010001001101010111100110111101111111100010001001010100111式〔5其等價形式為：〔7式〔6還可以簡記為或〔8其中所以有〔9式〔6等價于〔10其中Q為P的轉置,即〔11式〔10表示,信息位給定后,用信息位的行矩陣乘矩陣Q就產生出監督位。我們將Q的左邊加上一個k×k階單位方陣,就構成一個矩陣G〔12G稱為生成矩陣,因為由它可以產生整個碼組,即有〔13或者〔14式<13>即漢明碼的編碼原理2.2監督矩陣上面有提到過,線性碼是指信息位和監督位滿足一組線性代數方程的碼:〔15我們可以將式〔15表示成如下的矩陣形式〔16式〔16還可以簡記為或,其中,上角"T"表示將矩陣轉置。例如HT是H的轉置,即的第一行為H的第一列,第二行為第二列。我們將H稱為監督矩陣<parity—checkmatrix>.只要監督矩陣H給定,編碼時監督位和信息位的關系就完全確定了。由〔15和<16>都可以看出,H的行數就是監督關系式的數目r,H的每一行中的"1”〔17式中：P為階矩陣；Ir為階單位方陣。2.3生成矩陣由代數理論可知,H矩陣的的各行應該是線性無關的,否則將得不到r個線性無關的監督關系式,從而也得不到r個獨立的監督位。若一矩陣可以寫成的矩陣形式,則其各行一定是線性無關的。因為容易驗證Ir的各行是線性無關的,故的各行也是線性無關的。類似于式〔5改成式〔16那樣,式〔6可以改寫成〔18或者〔19其中,Q為一個階矩陣,它為P的轉置,即〔20式〔19表示,在信息位給定后,用信息位的行矩陣乘矩陣Q就產生出監督位。我們將Q的左邊加上一個階單位方陣,就構成一個矩陣G〔21G稱為生成矩陣〔generatormatrix,因為由它可產生整個碼組,即有〔22因此,如果找到了碼的生成矩陣G,則編碼的方法就完全確定。具有形式的生成矩陣稱為典型生成矩陣。由典型生成矩陣得出的碼組A中,信息位不變,監督位附加于其后,這種碼稱為系統碼。與H矩陣相似,也要求G矩陣的各行是線性無關的。因為由式〔22可以看出,任一碼組A都是G的各行的線性組合。G共有K行,若它們線性無關,則可組合出種不同的碼組A,它恰是有k為信息位的全部碼組；若G的各行有線性相關的,則不可能由G生成種不同碼組了。實際上,G的各行本身就是一個碼組。因此,如果已有k個線性無關的碼組,則可以用其作為生成矩陣G,并由它生成其余的碼組。三、漢明碼糾錯檢錯3.1漢明距離兩個碼字之間,對應位取之不同的個數,稱為漢明距離,用表示。一個碼的最小距離定義為,兩個碼字之間的距離表示了它們之間差別的大小。3.2漢明碼糾錯原理一般來說接收碼組與A不一定相同。若設接收碼組為一n列的行矩陣B,即〔23則發送碼組和接收碼組之差為〔24E就是傳輸中產生的錯碼行矩陣〔25若,表示接收碼元無錯誤,若,則表示該接收碼元有錯。式〔24可改寫成〔26若E=0,即接收碼組無錯,則,將它代人式〔8,該是仍成立,即有〔27當接收碼組有錯時,,將B帶入式〔26后,該式不一定成立。在未超過檢錯能力時,式〔27不成立。假設此時式〔26的右端為S,即〔28將代入式〔28,可得由式〔8可知,所以<29此處S與前面的有著一一對應關系,則S能代表錯碼位置。因此,糾錯原理即,接收端收到碼組后按式〔28計算出S,再根據表1判斷錯碼情況,進行差錯糾正。四、漢明碼編譯碼的實現過程4.1編碼過程由與的分塊表示的矩陣形式<31>〔32〔33〔34則有或〔35已知生成矩陣:根據以上幾式可求出監督矩陣:〔36最后可以根據輸入的四位信息位和生成矩陣相乘得到編碼矩陣。即〔37所有的編碼情況如表1所示。4.2譯碼過程對于譯碼過程來說,同樣由上知道監督矩陣H：根據監督矩陣,將矩陣的行和列調換,可求出監督矩陣的轉置矩陣:再根據式〔28即求出伴隨式,由伴隨式式可以知道錯碼的位置及及糾正錯碼,具體的錯碼位置如表1所示。糾正了接收碼后可以提取出其中的四位信息位.五、軟件設計及測試分析5.1程序流程圖主程序流程圖主程序一開始就有歡迎界面,并對該編譯器做了簡單的介紹,同時為方便用戶使用,對用戶的操作也進行了補充說明,接著給用戶顯示出了選擇提示語句,可以選擇編碼器、譯碼器、退出。當用戶做出選擇后便會進入各自的子程序,執行相應的功能,如果用戶輸入錯誤,還會給出錯誤提示。主程序的流程圖如圖3所示。圖2主程序流程圖編碼程序流程圖在程序進入編碼子程序時,它首先提示用戶輸入需要編碼的碼組個數,根據用戶選擇的個數接著要求用戶輸入編碼的信息碼組,信息碼組與生成矩陣相乘便會得到相應的編碼,其流程圖如圖4所示圖3編碼程序流程圖譯碼程序流程圖對于譯碼程序,因為信息在傳輸過程中會遇到噪聲干擾,所以接收碼組會出現錯碼、丟碼或多碼現象。又因為很難判斷丟碼或多碼的具體位置,所以這兩種情況處理起來比較復雜,在這暫不進行譯碼,只做出判斷。對于錯碼,可以糾正一位錯誤,發現兩位錯誤。在譯碼的過程中,要用到監督矩陣的轉置矩陣,所以先求生成矩陣對應的監督矩陣,再進行轉置,然后提示輸入接收碼組,輸入的接收碼組中有可能丟失碼位,故而先判斷,再進行糾檢錯,輸出正確的碼組,最后提取出正確的信息組。其流程圖如圖5所示。圖4譯碼程序流程圖5.2軟件運行分析主程序運行分析圖5主界面運行圖從程序一開始就運行主界面,主界面有對該軟件的簡單介紹,接著就給出了選擇功能。用戶輸入不同的序號可以執行不同的功能,主界面仿真結果如圖5所示。輸入"1"后按回車鍵執行編碼功能,如圖6所示；輸入"2"后按回車鍵執行譯碼功能,如圖7所示；輸入"3"后按回車鍵執行退出如圖8所示；輸入其它系統會顯示錯誤提示信息,如圖9所示。圖6選擇編碼功能圖7選擇譯碼功能圖8執行退出功能圖9輸入錯誤時錯誤提示編碼運行分析10和圖11所示。圖10輸入信息組數后系統界面圖11編碼后的系統界面由運行的界面可知,軟件還可以持續操作,當用戶再做出選擇,可以執行相應的功能,整個體系就是按照這個思想聯系在一起的。譯碼運行分析2所示；如果接收碼組沒有丟碼,系統可以糾正一位錯碼,發現兩位錯碼,例如輸入上面編碼后的4個接收碼組,并故意輸錯第二個碼組的位和第四個碼組的位和3所示。為了體現軟件的持續操作,我們從編碼結束后再選擇譯碼。圖12輸入有丟碼的接收碼組時系統運行界面圖13譯碼運行界面5.3軟件分析根據軟件運行情況分析來看,該軟件最終實現的功能有：〔1對數量不等的信息組編碼；〔2對數量不等的接收碼組糾正一位錯誤,發現兩位錯誤；〔3對輸入的接收碼組判斷是否有丟碼；〔4循環使用編碼器和譯碼器；〔5對操作失誤做出提示。與最初的設計目標相比,該軟件的不足方面有：〔1使用編碼器的時候,如果輸入有誤,系統沒有給出明確提示；〔2當接收碼組中有丟失位時,不能譯碼；〔3顯示界面不夠人性化。總之,軟件在可靠性方面已做出驗證,達到了要求。C語言比起其它語言要難學,更穩定,C程序的穩定性就證明了該軟件具有很好的穩定性。實用性方面,由于該軟件只對四位信息組編碼,編碼后有七位；對七位接收碼組譯碼,提取信息位后是四位。其它碼并不適應該軟件,所以它的適用范圍受到了限制。總結通過這次為期兩周的計算機通信課程設計,我的題目是〔7,4漢明碼的編譯碼軟件設計。漢明碼是差錯控制編碼的重要一種。漢明碼的編碼與譯碼糾錯能力較強,是實際應用中比較流行的差錯控制編碼方法之一。雖然課設剛開始我就要去實習,但是每天晚上回到宿舍我就開始做課設,因從我很及時的完成了課設,在這期間我查閱了許多的書籍以及網上的資料,通過這次課設,鞏固了以前所學過的知識,而且學到了很多在書本上所沒有學到過的知識。通過這次課程設計使我懂得了理論與實際相結合的必要性,只有理論知識是遠遠不夠的,只有把所學的理論知識與實踐相結合起來,從理論中得出結論,才能真正為社會服務,從而提高自己的實際動手能力和獨立思考的能力。在設計中也得到很多見識,獲得或理解知識時的欣喜與在一個問題上的糾結都是很寶貴的,在這種情緒的反復中,認識到學習就是這樣一個過程。不管過程怎樣,以小見大的反射出以后學習的態度。互相交流可以加深學習,找出問題,相互彌補不足,在資料的采集方面提高了不少效率,也提高的每個個體的興奮度,真切體會集體學習給我們帶來的益處,學習是快樂的。這次課程設計帶給我的不僅僅是學識上的精進還有個人能力素養的提升,也督促培養了個人獨立思考、善于查閱并應用相關資料書籍的能力。經過這次課程設計,我收獲很多。我會在以后的學習生活中繼續保持這種求真務實的精神,努力學好理論知識,更好的為實踐服務。參考文獻[1]潘新民編·計算機通信技術·電子工業出版社·2003,7[2]吳玲達、李國輝、楊冰等編·計算機通信原理與技術·國防科技大學出版社·2003,3[3]曹志剛、錢壓生編·現代通信原理·清華大學出版社·1992,2[4]樊昌興、通信原理[1]孫麗華編·信息論與糾錯編碼·電子工業出版社·2005,3編·國防工業出版社·1999,10[5]唐朝京著·信息論與編碼基礎·國防科技大學出版社·2003,1[6]宋祖順著·現代通信原理[M]·電子工業出版·2001,2[7]傅祖蕓著·信息論--基礎理論與應用[M]·電子工業出版社·2002[8]譚浩強著·C程序設計〔第二版·清華大學出版社·1999,12[9]王連相著·C/C++程序設計教程·中國鐵道出版社·2006,8附錄〔7,4碼編譯器整體程序：#include<stdio.h>#include<math.h>intmain<> { /*G：生成矩陣H：監督矩陣HT：監督矩陣對應的轉置矩陣*/ /*M：輸入信息序列C：編碼輸出序列Input：輸入接收碼序列B：譯碼輸出序列S：伴隨式*/ intQ,N;/*定義開始*/ inti,j,s,r,k,t,p,u,m;intG[4][7]={{1,0,0,0,1,1,1},{0,1,0,0,1,1,0},{0,0,1,0,1,0,1},{0,0,0,1,0,1,1}}; intIR[3][3]={{1,0,0,},{0,1,0},{0,0,1}}; intH[3][7],C[10][7],M[10][4],B[20][7],Input[100],HT[7][3],P[10],S[100][3];/*定義結束*/ printf<"\n您好！歡迎使用漢明碼編譯器！\n">; printf<"\n\n本編譯器針對〔7,4碼,所采用的生成矩陣G=\n">; for<i=0;i<4;i++> { for<j=0;j<7;j++> printf<"%d",G[i][j]>; printf<"\n">; } printf<"編譯碼過程都是針對二進制碼組,除了系統要求選擇功能,其他情況下禁止輸入除0,1以外的數。請在使用的過程中嚴格按照編譯器要求的格式輸入數據。\n\n">; printf<"現在請輸入您所選擇的編譯器所對應的序號,按回車鍵繼續:\n">; printf<"\n1.編碼器2.譯碼器3.退出\n">; printf<"\n我選擇：">; scanf<"%d",&Q>; if<Q==0> Q+=4; while<Q> { if<Q==1||Q==2||Q==3>break; else { printf<"對不起,您輸入有誤,請重新輸入">; scanf<"%d",&Q>; } } while<Q==1||Q==2||Q==3> { if<Q==1>/*編碼程序*/ {printf<"\n請輸入您需要編碼的信息組數">; scanf<"%d",&N>; printf<"\n\n請輸入您需要編碼的%d組四位二進制信息組,碼組間用空格分開,按回車鍵確認。\n",N>;/*輸入信息碼*/ printf<"\n信息組m=">; for<i=0;i<N;i++> scanf<"%1d%1d%1d%1d",&M[i][3],&M[i][2],&M[i][1],&M[i][0]>;/*求監督碼*/ for<i=0;i<N;i++> { C[i][2]=M[i][3]^M[i][2]^M[i][1]; C[i][1]=M[i][3]^M[i][2]^M[i][0]; C[i][0]=M[i][3]^M[i][1]^M[i][0]; } for<j=0;j<N;j++> for<i=6;i>2;i-->/*輸出編碼結果*/ C[j][i]=M[j][i-3]; printf<"\n您所輸入的信息組編碼結果c=">; for<j=0;j<N;j++> for<i=6;i>=0;i--> printf<"%d",C[j][i]>; printf<"\n\n">; printf<"\n接下來您想：\n\n">;/*選擇功能*/ printf<"1.用編碼器2.用譯碼器3.退出\n\n">; printf<"我想：">; scanf<"%d",&Q>; } elseif<Q==2>/*譯碼程序*/ { for<i=0;i<3;i++>/*求監督矩陣*/ { for<j=0;j<4;j++> H[i][j]=G[j][i+4]; for<j=4;j<7;j++> H[i][j]=IR[i][j-4]; } printf<"\n監督矩陣H=\n">;/*輸出監督矩陣*/ for<i=0;i<3;i++> { for<j=0;j<7;j++> printf<"%d",H[i][j]>; printf<"\n">; } t=1; while<t!=2>/*輸入接收碼組*/ { p=1; printf<"\n請輸入總位數為7的倍數的接收碼組,每位用空格隔開,每組位數為7的倍數,以十進制2作為結束標志!按回車鍵確認\n">; while<p> { for<i=0;;i++> { scanf<"%d",&Input[i]>; if<Input[i]==2>break; } k=i%7; if<k==0>{p=0;t=2;} else { p=1; k=-k+7; printf<"您接收到的碼組丟失了%d位,系統不能判斷丟失位的具體位置,請重新輸入\n",k>; } } } u=i/7; i=0; for<r=0;r<u;r++> { for<j=6;j>=0;j--,i++> B[r][j]=Input[i]; } printf<"\n將接收碼組每七位分為一個碼組,如下：\n">; for<i=0;i<u;i++> { for<j=0;j<7;j++> printf<"%1d",B[i][6-j]>; printf<"\n">; } for<i=0;i<3;i++>/*求監督矩陣H的轉置矩陣*/ for<j=0;j<7;j++> HT[j][i]=H[i][j]; for<i=0;i<u;i++> { for<m=0;m<3;m++> { for<j=0;j<7;j++> { s+=<B[i][6-j]*HT[j][m]>; } if<s%2==1>s=1; else s=0; S[i][2-m]=s; s=0; } } printf<"\n\n伴隨式S=\n">;/*輸出伴隨式*/ for<j=0;j<u;j++> {for<i=2;i>=0;i--> printf<"%1d",S[j][i]>; printf<"\n">;} printf<"\n">; for<i=0;i<u;i++> { P[i]=4*S[i][2]+2*S[i][1]+S[i][0]+1; switch<P[i]>/*根據伴隨式判斷接收碼,并譯碼*/ { case1: { printf<"\n\n您所接收的第%d個碼組正確,它是：",++i>; i--; for<j=6;j>=0;j--> printf<"%1d",B[i][j]>; printf<"請您再次確認！">; printf<"譯出的信息序列為：">; for<j=6;j>2;j--> printf<"%d",B[i][j]>;break; } case2: { B[i][0]=1^B[i][0]; printf<"\n\n您接收的第%d個碼組有錯誤,正確的碼組應為：",++i>; i--; for<j=6;j>=0;j--> printf<"%1d",B[i][j]>; printf<"譯出的信息序列為：">; for<j=6;j>2;j--> printf<"%d",B[i][j]>;break; } case3: { B[i][1]=1^B[i][1]; printf<"\n\n您接收的第%d個碼組有錯誤,正確的碼組應為：",++i>; i--; for<j=6;j>=0;j--> printf<"%1d",B[i][j]>; printf<"譯出的信息序列為：">; for<j=6;j>2;j--> printf<"%d",B[i][j]>;break; } case4: { B[i][3]=1^B[i][3]; printf<"\n\n您接收的第%d個碼組有錯誤,正確的碼組應為：",++i>; i--; for<j=6;j>=0;j--> printf<"%1d",B[i][j]>; printf<"譯出的信息序列為：">; for<j=6;j>2;j--> printf<"%d",B[i][j]>;break; } case5: { B[i][2]=1^B[i][2]; printf<"\n\n您接收的第%d個碼組有錯誤,正確的