海明碼校驗程序設計
1. 需求分析
1）海明碼編碼：
輸入：一串二進制數據串
輸出：插入海明碼後的二進制數據串
2）海明碼糾錯：
輸入：一串含海明碼的二進制數據串
輸出：通過海明碼校驗，檢查該二進制串是否有錯，若有錯誤，則對錯誤位進行糾錯，將糾錯後的二進制串輸出。
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) 即可。
3. 概要設計
基於以上原理，我們對軟件進行了初步的規劃和設計：
1） 為了提供友好的用戶界面，我們采用Visual C++的MFC框架構建應用程序，使用一個簡單的對話框程序，包含兩個部分，一部分為海明碼編碼部分，另一部分為海明碼糾錯部分。
2） 由於本程序僅僅是海明碼原理性的驗證性程序，故只設計了對最長8位數據的海明碼的編碼，以及最長12位的海明碼校驗。
3） 從上述原理可知，海明碼的編碼和糾錯可以使用如上所述的公式進行，故數據結構只需要采用一個vector容器存放相應的數據即可，不需要其他負責的數據結構。
4. 詳細設計
4.1 數據結構的設計
定義五個bool型的容器，vector<bool>，分別代表：輸入串寄存器、海明編碼寄存器、海明碼檢錯寄存器、海明碼檢錯數據寄存器、海明碼檢錯校驗值寄存器
其中：
輸入串寄存器：用於存放用戶輸入的二進制串
海明編碼寄存器：存放加入海明碼校驗碼後的二進制串
海明碼檢錯寄存器：存放需要糾錯的二進制串
海明碼檢錯數據寄存器：存放需要糾錯的二進制串的數據部分
海明碼檢錯校驗值寄存器：存放需要糾錯的二進制串的校驗碼部分
4.2 模塊劃分
模塊功能概述：
1）海明碼編碼
輸入模塊：獲取用戶的輸入二進制串，並判斷輸入的正確性
寄存器初始化模塊：將用戶的輸入字符串轉化成0、1形式的數字串存放到輸入串寄存器中，並且將數據依次存放到海明編碼寄存器，存放時將2的冪次的位置空出來置0）作為存放校驗碼。
校驗碼計算模塊：根據上面描述的編碼算法對校驗碼的值進行計算並存儲在對應的位置。
顯示模塊：將海明編碼寄存器中的二進制串轉化成字符串的形式以供輸出。
2）海明碼糾錯
輸入模塊：獲取用戶的輸入二進制串，並判斷輸入的正確性
寄存器初始化模塊：將用戶的輸入字符串轉化成0、1形式的數字串存放到檢錯寄存器中，根據當前位置是否為2的冪次將二進制串分為數據和校驗碼分別存放到檢錯數據寄存器和檢錯校驗值寄存器
海明碼糾錯模塊：根據上面描述的糾錯算法對數據進行校驗，並糾錯。
顯示模塊：將檢錯寄存器中正確的二進制碼轉化成字符串的形式以供輸出。
4.3 程序流程圖
5. 程序效果圖
本文出自 “對影成三人” 博客，請務必保留此出處http://ticktick.blog.51cto.com/823160/167482
