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

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

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

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

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

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

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

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

k—信息位數(shù)

r—校驗(yàn)位數(shù)

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

（2）計(jì)算校驗(yàn)位公式

特別注意：

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

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

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

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

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

例如r3=I8+I7+I6+I5

（3）求校驗(yàn)位。

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

（4）求海明碼

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

例對(duì)一段信息1011，寫(xiě)出海明碼。

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

1、2^r≥4+r+1,確定校驗(yàn)位位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海明碼糾錯(cuò)原理分析

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

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

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

Sn=rn(校驗(yàn))+rn(接收)

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

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

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

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

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

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

其中：

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

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

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

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

3.4.2模塊劃分

模塊功能概述：

（1）海明碼編碼

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

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

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

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

（2）海明碼糾錯(cuò)

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

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

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

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