計算機(jī)網(wǎng)絡(luò)課程設(shè)計報告-海明碼實現(xiàn)

湖南涉外經(jīng)濟(jì)學(xué)院計算機(jī)科學(xué)與技術(shù)學(xué)部《計算機(jī)網(wǎng)絡(luò)原理與應(yīng)用》課程設(shè)計報告湖南涉外經(jīng)濟(jì)學(xué)院計算機(jī)網(wǎng)絡(luò)原理與應(yīng)用課程設(shè)計報告學(xué)部：計算機(jī)學(xué)部專業(yè)名稱：計算機(jī)科學(xué)與技術(shù)課程名稱：計算機(jī)網(wǎng)絡(luò)原理設(shè)計題目：海明碼的實現(xiàn)學(xué)生姓名：余文浩,付慶宇,陳杰指導(dǎo)教師：安瑩時間：題目海明碼的實現(xiàn)目錄一、課程設(shè)計目的 31.1海明碼的介紹 31.2海明碼的應(yīng)用 31.3算法實現(xiàn)的目的 3二、課程設(shè)計題目任務(wù)描述和要求 42.1任務(wù)描述 42.2要求 4三、設(shè)計方案 53.1需求分析 53.2海明碼校驗原理分析 53.2.1海明碼編碼的原理分析 53.2.2海明碼糾錯原理分析 73.3概要設(shè)計 73.4詳細(xì)設(shè)計 83.4.3程序流程圖 9四、心得體會 11五、參考資料 12(要求：給出一級目錄，宋體加粗，四號字,1.5倍行距。)一、課程設(shè)計目的（大標(biāo)題均為四號，黑體） 1.1海明碼的介紹 是在電信領(lǐng)域的一種線性調(diào)試碼，以發(fā)明者RichardHamming的名字命名。漢明碼在傳輸?shù)男畔⒘髦胁迦腧炞C碼，以偵測并更正單一比特錯誤。由于簡單的漢明編碼，它們被廣泛應(yīng)用于內(nèi)存(RAM)。其SECDED(singleerrorcorrection,doubleerrordetection)版本另外加入一檢測比特，可以偵測兩個以下同時發(fā)生的比特錯誤，并能夠更正單一比特的錯誤。因此，當(dāng)傳送端與接收端的比特樣式的漢明距離(Hammingdistance)小于或等于1時（僅有1bit發(fā)生錯誤），可實現(xiàn)可靠的通信。相對的，簡單的奇偶檢驗碼除了不能糾正錯誤之外，也只能偵測出奇數(shù)個的錯誤。1.2海明碼的應(yīng)用 海明碼主要應(yīng)用于計算機(jī)網(wǎng)絡(luò)中。在數(shù)據(jù)鏈路層中，數(shù)據(jù)的傳輸很容易出現(xiàn)錯誤，這時就需要糾錯機(jī)制來進(jìn)行糾錯，海明碼就是一種糾錯編碼方案。1.3算法實現(xiàn)的目的來實現(xiàn)海明碼生成和糾錯，可以使我們更加深刻的了解海明校驗機(jī)制的。二、課程設(shè)計題目任務(wù)描述和要求2.1任務(wù)描述用MicrosoftVisualC++6.0工具，VisualC++MFC編程實現(xiàn)海明碼的編碼和驗證過程。即，輸入給定長度的二進(jìn)制數(shù)據(jù)，輸出相應(yīng)的完整海明編碼形式；同時，輸入任意編碼能驗證其正確性，一位錯時，能顯示出錯的比特，并予以糾正2.2要求 輸入任意長度的二進(jìn)制數(shù)據(jù)串，通過算法是生成完整的海明碼，

三、設(shè)計方案3.1需求分析（1）海明碼編碼：

輸入：一串二進(jìn)制數(shù)據(jù)串

輸出：插入海明碼后的二進(jìn)制數(shù)據(jù)串（2）海明碼糾錯：

輸入：一串含海明碼的二進(jìn)制數(shù)據(jù)串

輸出：通過海明碼校驗，檢查該二進(jìn)制串是否有錯，若有錯誤，則對錯誤位進(jìn)行糾錯，將糾錯后的二進(jìn)制串輸出。(3)海明碼譯碼：輸入：一串以糾錯的二進(jìn)制數(shù)據(jù)傳輸出：源二進(jìn)制串?dāng)?shù)據(jù)3.2海明碼校驗原理分析這里我們僅從編程實現(xiàn)的角度分析海明碼的編碼及糾錯的實現(xiàn)算法，書本上采用的是矩陣相乘的方法，但矩陣相乘的方法程序執(zhí)行效率不高，故通過在網(wǎng)上的搜索及自己的總結(jié)，得出如下的程序?qū)崿F(xiàn)算法。3.2.1海明碼編碼的原理分析編碼步驟

（1）根據(jù)信息位數(shù)，確定校驗位數(shù)。

k—信息位數(shù)

r—校驗位數(shù)

求出滿足不等式的最小r，即為校驗位數(shù)。

（2）計算校驗位公式

特別注意：

校驗位rn所在位數(shù)為，其余由信息位填充。

位數(shù)和信息位由1起始，而校驗位由0起始。

將每個信息比特由位置對應(yīng)的位數(shù)寫成2的冪之和的形式。

例如I8對應(yīng)的第十二位12=2^3+2^2，I7對應(yīng)的第十一位11=2^3+2^1+2^0，I6對應(yīng)的第十位10=2^3+2^1，I5對應(yīng)的第九位9=2^3+2^0一直寫到對應(yīng)的第三位。

校驗位rn由前面位數(shù)寫成2的冪之和中包含2^n的位數(shù)對應(yīng)的信息為之和構(gòu)成

例如r3=I8+I7+I6+I5

（3）求校驗位。

根據(jù)計算公式求出各校驗位。

（4）求海明碼

根據(jù)上面的表格填充后，寫出海明碼。

例對一段信息1011，寫出海明碼。

根據(jù)上面步驟，解答如下

1、2^r≥4+r+1,確定校驗位位3位2^3≥4+3+1.

2、根據(jù)步驟

7=2^2+2^1+2^0,6=2^2+2^1,5=2^2+2^0,3=2^1+2^0,

r2=I4+I3+I2

r1=I4+I3+I1

r0=I4+I2+I1

3、根據(jù)公式的r2=0,r1=0,r0=1

4、添入表格

得海明碼10101013.2.2海明碼糾錯原理分析

(1)根據(jù)海明碼的信息位和校驗位的分布規(guī)則，找出接收到的數(shù)據(jù)的信息位以及校驗位。

如有已經(jīng)編碼的數(shù)據(jù)110010010111，則可以根據(jù)上表得到編碼的信息為：11000011;校驗位為：1011。

(2)接收端對校驗位進(jìn)行驗證

Sn=rn(校驗)+rn(接收)

(3)判斷校正因子是否有錯，并改正。

SnSn-1Sn-2……S0二進(jìn)制對應(yīng)的是那位就是那位出錯，將其改正完成糾錯。如1001為第九位，將第九位1變0(或0變1)即可。3.3概要設(shè)計基于以上原理，我們對軟件進(jìn)行了初步的規(guī)劃和設(shè)計：（1）為了提供友好的用戶界面，我們采用VisualC++的MFC框架構(gòu)建應(yīng)用程序，使用一個簡單的對話框程序，包含兩個部分，一部分為海明碼編碼部分，另一部分為海明碼糾錯部分。

（2）由于本程序僅僅是海明碼原理性的驗證性程序，故只設(shè)計了對最長8位數(shù)據(jù)的海明碼的編碼，以及最長12位的海明碼校驗。

（3）從上述原理可知，海明碼的編碼和糾錯可以使用如上所述的公式進(jìn)行，故數(shù)據(jù)結(jié)構(gòu)只需要采用一個vector容器存放相應(yīng)的數(shù)據(jù)即可，不需要其他負(fù)責(zé)的數(shù)據(jù)結(jié)構(gòu)。3.4詳細(xì)設(shè)計

3.4.1數(shù)據(jù)結(jié)構(gòu)的設(shè)計

定義五個bool型的容器，vector<bool>，分別代表：輸入串寄存器、海明編碼寄存器、海明碼檢錯寄存器、海明碼檢錯數(shù)據(jù)寄存器、海明碼檢錯校驗值寄存器

其中：

輸入串寄存器：用于存放用戶輸入的二進(jìn)制串

海明編碼寄存器：存放加入海明碼校驗碼后的二進(jìn)制串海明碼檢錯寄存器：存放需要糾錯的二進(jìn)制串

海明碼檢錯數(shù)據(jù)寄存器：存放需要糾錯的二進(jìn)制串的數(shù)據(jù)部分

海明碼檢錯校驗值寄存器：存放需要糾錯的二進(jìn)制串的校驗碼部分

3.4.2模塊劃分

模塊功能概述：

（1）海明碼編碼

輸入模塊：獲取用戶的輸入二進(jìn)制串，并判斷輸入的正確性

寄存器初始化模塊：將用戶的輸入字符串轉(zhuǎn)化成0、1形式的數(shù)字串存放到輸入串寄存器中，并且將數(shù)據(jù)依次存放到海明編碼寄存器，存放時將2的冪次的位置空出來（置0）作為存放校驗碼。

校驗碼計算模塊：根據(jù)上面描述的編碼算法對校驗碼的值進(jìn)行計算并存儲在對應(yīng)的位置。

顯示模塊：將海明編碼寄存器中的二進(jìn)制串轉(zhuǎn)化成字符串的形式以供輸出。

（2）海明碼糾錯

輸入模塊：獲取用戶的輸入二進(jìn)制串，并判斷輸入的正確性

寄存器初始化模塊：將用戶的輸入字符串轉(zhuǎn)化成0、1形式的數(shù)字串存放到檢錯寄存器中，根據(jù)當(dāng)前位置是否為2的冪次將二進(jìn)制串分為數(shù)據(jù)和校驗碼分別存放到檢錯數(shù)據(jù)寄存器和檢錯校驗值寄存器

海明碼糾錯模塊：根據(jù)上面描述的糾錯算法對數(shù)據(jù)進(jìn)行校驗，并糾錯。

顯示模塊：將檢錯寄存器中正確的二進(jìn)制碼轉(zhuǎn)化成字符串的形式以供輸出。3.4.3程序流程圖四、心得體會通過對這次課程設(shè)計讓我對計算機(jī)的組成原理有了更深層次的理解，把平時學(xué)習(xí)中學(xué)到的知識運用了到其中。同時也加深了我對平時學(xué)習(xí)中所沒有接觸過的知識的一個了解。從而提升了自己各方面的能力,特別是對數(shù)據(jù)在內(nèi)存單元以及寄存器中的存儲原理和操作數(shù)走向問題。并且讓我對海明碼有了認(rèn)識和了解，能夠更加熟練的運用海明碼。再次明白到各個學(xué)科緊密相關(guān)，組成原理與微機(jī)原理知識的相互應(yīng)用，硬件與編程之間密切聯(lián)系，程序最終依靠硬件實現(xiàn)，并依靠硬件編程，硬件為其提供一個平臺，二者缺一不可，通過這樣的學(xué)習(xí)加深理解，提供綜合能力。本次設(shè)計是使用C++語言做的，通過這次課程設(shè)計，也加深了我對C++的理解和熟練程度。最后，通過這次課程設(shè)計，不僅增長了我的知識，同時也鍛煉了我的動手能力，和解決問題的能力。……（正文部分一律用小四號字，宋體，1.