海明碼校驗程式設計
(1)海明碼編碼:
輸入:一串二進制資料串
輸出:插入海明碼後的二進制資料串
(2)海明碼糾錯:
輸入:一串含海明碼的二進制資料串
輸出:通過海明碼校驗,檢查該二進制串是否有錯,若有錯誤,則對錯誤位進行糾錯,将糾錯後的二進制串輸出。
這裡我們僅從程式設計實作的角度分析海明碼的編碼及糾錯的實作算法,書本上采用的是矩陣相乘的方法,但矩陣相乘的方法程式執行效率不高,故通過在網上的搜尋及自己的總結,得出如下的程式實作算法。
2.1 海明碼編碼的原理分析
編碼步驟
(1) 根據資訊位數,确定校驗位數。
k—資訊位數
r—校驗位數
求出滿足不等式的最小r,即為校驗位數。
(2)計算校驗位公式
特别注意:
校驗位 r n所在位數為 2^n ,其餘由資訊位填充。
位數和資訊位由1起始,而校驗位由0起始。
将每個資訊比特由位置對應的位數寫成2的幂之和的形式。
例如I8對應的第十二位12=2^3+2^2 ,I7對應的第十一位11=2^3+2^1+2^0 ,I6對應的第十位10=2^3+2^1,I5對應的第九位9=2^3+2^0 一直寫到對應的第三位。
校驗位r n由前面位數寫成2的幂之和中包含2 ^n的位數對應的資訊為之和構成
例如r3=I8+I7+I6+I5
(3)求校驗位。
根據計算公式求出各校驗位。
(4) 求海明碼
根據上面的表格填充後,寫出海明碼。
例 對一段資訊1011,寫出海明碼。
根據上面步驟,解答如下
1、 2^r≥4+r+1,确定校驗位位3位2^3≥4+3+1.
2、 根據步驟
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、 根據公式的r2 = 0, r1 =0, r0 =1
4、 添入表格
得海明碼1010101
2.2 海明碼糾錯原理分析
(1)根據海明碼的資訊位和校驗位的分布規則,找出接收到的資料的資訊位以及校驗位。
如有已經編碼的資料 1100 1001 0111,則可以根據上表得到編碼的資訊為:1100 0011;校驗位為:1011。
(2)接收端對校驗位進行驗證
Sn= rn ( 校驗)+ rn (接收)
(3)判斷校正因子是否有錯,并改正。
Sn Sn-1 Sn-2……S0二進制對應的是那位就是那位出錯,将其改正完成糾錯。如1001為第九位,将第九位1變0 (或0變1) 即可。
基于以上原理,我們對軟體進行了初步的規劃和設計:
(1) 為了提供友好的使用者界面,我們采用Visual C++的MFC架構建構應用程式,使用一個簡單的對話框程式,包含兩個部分,一部分為海明碼編碼部分,另一部分為海明碼糾錯部分。
(2) 由于本程式僅僅是海明碼原理性的驗證性程式,故隻設計了對最長8位資料的海明碼的編碼,以及最長12位的海明碼校驗。
(3) 從上述原理可知,海明碼的編碼和糾錯可以使用如上所述的公式進行,故資料結構隻需要采用一個vector容器存放相應的資料即可,不需要其他負責的資料結構。
4.1 資料結構的設計
定義五個bool型的容器,vector<bool>,分别代表:輸入串寄存器、海明編碼寄存器、海明碼檢錯寄存器、海明碼檢錯資料寄存器、海明碼檢錯校驗值寄存器
其中:
輸入串寄存器:用于存放使用者輸入的二進制串
海明編碼寄存器:存放加入海明碼校驗碼後的二進制串
海明碼檢錯寄存器:存放需要糾錯的二進制串
海明碼檢錯資料寄存器:存放需要糾錯的二進制串的資料部分
海明碼檢錯校驗值寄存器:存放需要糾錯的二進制串的校驗碼部分
4.2 子產品劃分
子產品功能概述:
(1)海明碼編碼
輸入子產品:擷取使用者的輸入二進制串,并判斷輸入的正确性
寄存器初始化子產品:将使用者的輸入字元串轉化成0、1形式的數字串存放到輸入串寄存器中,并且将資料依次存放到海明編碼寄存器,存放時将2的幂次的位置空出來(置0)作為存放校驗碼。
校驗碼計算子產品:根據上面描述的編碼算法對校驗碼的值進行計算并存儲在對應的位置。
顯示子產品:将海明編碼寄存器中的二進制串轉化成字元串的形式以供輸出。
(2)海明碼糾錯
寄存器初始化子產品:将使用者的輸入字元串轉化成0、1形式的數字串存放到檢錯寄存器中,根據目前位置是否為2的幂次将二進制串分為資料和校驗碼分别存放到檢錯資料寄存器和檢錯校驗值寄存器
海明碼糾錯子產品:根據上面描述的糾錯算法對資料進行校驗,并糾錯。
顯示子產品:将檢錯寄存器中正确的二進制碼轉化成字元串的形式以供輸出。
4.3 程式流程圖