文章目錄
- 校驗碼
- 術語
- 海明碼
- java實作
校驗碼
計算機系統運行時，為了確保資料在傳遞程序中正確無誤，一是提高硬體電路的可靠性，二是提高代碼的校驗能力，包括查錯與糾錯，通常使用校驗碼的方法來檢測傳送的資料是否出錯，其基本思想是把資料可能出現的編碼分為兩類：合法編碼與錯誤編碼，合法編碼用于傳送資料，錯誤編碼是不允許在資料中出現的編碼，合理的設計錯誤編碼以及編碼規則，使得資料在傳送中出現錯誤時會變為錯誤編碼，這樣就可以檢測出接收的資料是否有錯，
術語
碼字：是指編碼系統中的合法編碼稱為碼字，
碼距：是指編碼系統中任意兩個合法編碼之間至少有多少個二進制位不同，如：合法編碼為11、00，那么11與00之間至少有兩個二進制位不同，所以碼距為2，
海明碼
關于海明碼的知識，我還是認為只有《軟體設計師教程（第5版）》的海明碼講解簡單易懂，結合海明碼規則和關系表格來學習，很容易上手，最后的部分是用java實作的位元組陣列版本的海明碼編碼與解碼以及校驗，
以下內容摘自《軟體設計師教程（第5版）》：
海明碼(Hamming Code)是由貝爾實驗室的Richard Hamming設計的，是一種利用奇偶性來檢錯和糾錯的校驗方法，海明碼的構成方法是在資料位之間的特定位置上插入k個校驗位，通過擴大碼距來實作檢錯和糾錯，
設資料位是n位，校驗位是k位，則n和k必須滿足一下關系：
2
k
?
1
?
n
+
k
2^k-1 \geqslant n+k
2k?1?n+k
海明碼的編碼規則如下，
設k個校驗位為
P
k
,
P
k
?
1
,
.
.
.
,
P
1
P_k,P_{k-1},...,P_1
Pk?,Pk?1?,...,P1?，n個資料位為
D
n
?
1
,
D
2
,
.
.
.
,
D
1
,
D
0
D_{n-1},D_2,...,D_1,D_0
Dn?1?,D2?,...,D1?,D0?，對應的海明碼為
H
n
+
k
,
H
n
+
k
?
1
H_{n+k},H_{n+k-1}
Hn+k?,Hn+k?1?,那么:
- P i P_i Pi?在海明碼的第2i-1位置，即 H j = P i H_j=P_i Hj?=Pi?，且j=2i-1，資料位則依序從低到高占據海明碼中剩下的位置，
- 海明碼中的任何一位都是由螺桿個校驗位來校驗的，其對應關系如下：被校驗的海明位的下表等于所有參與校驗該位的下標只和，而校驗位由自身校驗，
對于8位的資料位，進行海明校驗需要4個校驗位(參考公式帶入計算)，令資料位為 D 7 , D 6 , D 5 , D 4 , D 3 , D 2 , D 1 , D 0 D_7,D_6,D_5,D_4,D_3,D_2,D_1,D_0 D7?,D6?,D5?,D4?,D3?,D2?,D1?,D0?,校驗位為 P 4 , P 3 , P 2 , P 1 P_4,P_3,P_2,P_1 P4?,P3?,P2?,P1?，形成海明碼為 H 12 , H 11 , . . . , H 2 , H 1 H_{12},H_{11},...,H_2,H_1 H12?,H11?,...,H2?,H1?，則編碼程序如下，
-
確定D與P在海明碼中的位置，如下所示：
-
確定校驗關系，如表:
若采用奇校驗，則將各校驗位的偶校驗值取反即可， -
檢測錯誤，對使用海明編碼的資料進行差錯檢測很簡單，只需做一下計算：
G 1 = P 1 ⊕ D 0 ⊕ D 1 ⊕ D 3 ⊕ D 4 ⊕ D 6 G_1=P_1⊕D_0⊕D_1⊕D_3⊕D_4⊕D_6 G1?=P1?⊕D0?⊕D1?⊕D3?⊕D4?⊕D6?
G 2 = P 2 ⊕ D 0 ⊕ D 2 ⊕ D 3 ⊕ D 5 ⊕ D 6 G_2=P_2⊕D_0⊕D_2⊕D_3⊕D_5⊕D_6 G2?=P2?⊕D0?⊕D2?⊕D3?⊕D5?⊕D6?
G 3 = P 3 ⊕ D 1 ⊕ D 2 ⊕ D 3 ⊕ D 7 G_3=P_3⊕D_1⊕D_2⊕D_3⊕D_7 G3?=P3?⊕D1?⊕D2?⊕D3?⊕D7?
G 4 = P 4 ⊕ D 4 ⊕ D 5 ⊕ D 6 ⊕ D 7 G_4=P_4⊕D_4⊕D_5⊕D_6⊕D_7 G4?=P4?⊕D4?⊕D5?⊕D6?⊕D7?
若采用偶校驗，則 G 4 G 3 G 2 G 1 G_4G_3G_2G_1 G4?G3?G2?G1?全為0時表示接收到的資料無錯誤，當 G 4 G 3 G 2 G 1 G_4G_3G_2G_1 G4?G3?G2?G1?有一個為1，則說明出了差錯，而且 G 4 G 3 G 2 G 1 G_4G_3G_2G_1 G4?G3?G2?G1?的十進制值指出了發生錯誤的位置，例如 G 4 G 3 G 2 G 1 G_4G_3G_2G_1 G4?G3?G2?G1?=1010，說明 H 10 ( D 5 ) H_{10}(D_5) H10?(D5?)出錯了，將其取反即可糾正錯誤，
java實作
該Java按照上述海明碼規則，實作了對位元組陣列的海明碼編碼與解碼以及海明碼校驗，
該海明碼實作基于位元組陣列，位元組陣列與其他任意物件之間的轉換，由呼叫方決定，
import java.util.*;
/**
* 公式：2^k-1≥n+k or 2^k≥n+1+k
* <p>
* 規則：
* 設k個校驗位為Pk,Pk-1,...,P1，N個資料位為Dn-1,Dn-2,...,D1,D0，對應的海明碼為Hk+n,Hk+n-1,...,H1，那么
* (1) Pi在海明碼的第2^i-1位置，即Hj=Pi，且j=2^i-1，資料位一次從低到高占據海明碼剩下的位置，
* (2) 海明碼中的任何一位都是由若干個校驗位來進行校驗，其對應關系如下：被校驗的海明位的下標是所有參與該位的校驗位的下標之和，而校驗位由自身校驗，
* <p>
* 對應位置參照：
* H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1
* D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1
* <p>
* 當前海明碼下標=當前資料位下標+當前校驗位數
* 當前資料位下標
* 計算當前海明碼下標對應的校驗位，并添加到table
* 最后將校驗位插入原始位元組陣列
* <p>
* 校驗關系：
* P1:P1,D6,D4,D3,D1,D0
* P2:P2,D6,D5,D3,D2,D0
* P3:P3,D7,D3,D2,D1
* P4:P4,D7,D6,D5,D4
* <p>
* 8 4 12
* 9 4 13
* 10 4 14
* 11 4 15
* 12 5 17
* <p>
* 反校驗，通過海明碼的位數來獲取最大的校驗位，如12個位元位的海明碼，12轉二進制->1100，
* 二進制位數即校驗碼的數量，按權展開獲取10進制即海明碼校驗位的下標
*
* <p>
* User: Bai Yang
* DateTime:2021/2/15 3:26 下午
*/
public class HammingCode {
public static final int BYTE_BIT_SIZE = 8;
public static final int LONG_BIT_SIZE = 64;
/**
* 對傳入的位元組陣列按照海明碼規則插入校驗位，
* 海明碼采用偶校驗，
*
* @param bytes 編碼位元組陣列，可以是任意物件轉的位元組陣列，如字串
* @return 按照海明碼規則插入校驗位之后的位元組陣列，長度=源陣列長度+校驗位所需位元組長度
*/
public static byte[] encode(byte[] bytes) {
//構造table
Map<Integer, List<Integer>> checkCodeTable = buildCheckBitTable(bytes);
//分配位元組陣列
int allocateSize = (trimLengthOf(bytes) + checkCodeTable.size() + BYTE_BIT_SIZE - 1) / BYTE_BIT_SIZE;
byte[] hmCodeBytes = new byte[allocateSize];
//將所有校驗位暫時置為1，便于后面的資料位填充的判斷
for (int ckBitPositionOfHm : checkCodeTable.keySet()) {
int byteIdx = allocateSize - (ckBitPositionOfHm + BYTE_BIT_SIZE - 1) / BYTE_BIT_SIZE;
hmCodeBytes[byteIdx] = (byte) (hmCodeBytes[byteIdx] | (1 << ((ckBitPositionOfHm - 1) % 8)));
}
//從右至左依次填充資料位
int currByteIdx = hmCodeBytes.length - 1;
int currBitOffset = -1;
for (int i = bytes.length - 1; i >= 0; i--) {
byte dataByte = bytes[i];
for (int j = 0; j < BYTE_BIT_SIZE; j++) {
int bitv = (dataByte >> j & 1);
hmCodeByteLoopFlag:
for (; currByteIdx >= 0; currByteIdx--) {
byte hmCodeByte = hmCodeBytes[currByteIdx];
for (currBitOffset++; currBitOffset < BYTE_BIT_SIZE; currBitOffset++) {
if ((hmCodeByte >> currBitOffset & 1) == 0) {
hmCodeBytes[currByteIdx] = (byte) (hmCodeByte | (bitv << currBitOffset));
break hmCodeByteLoopFlag;
}
}
currBitOffset = -1;
}
}
}
//設定校驗位值
for (Map.Entry<Integer, List<Integer>> item : checkCodeTable.entrySet()) {
Integer ckBitPositionOfHm = item.getKey();
List<Integer> bitValues = item.getValue();
int bitValue = bitValues.get(0);
for (int i = 1; i < bitValues.size(); i++) {
bitValue = bitValue ^ bitValues.get(i);
}
int byteIdx = allocateSize - (ckBitPositionOfHm + BYTE_BIT_SIZE - 1) / BYTE_BIT_SIZE;
if ((hmCodeBytes[byteIdx] & (1 << ((ckBitPositionOfHm - 1) % 8))) > 0) {
if (bitValue == 0) {
hmCodeBytes[byteIdx] = (byte) (hmCodeBytes[byteIdx] ^ 1 << ((ckBitPositionOfHm - 1) % 8));
}
} else if (bitValue != 0) {
hmCodeBytes[byteIdx] = (byte) (hmCodeBytes[byteIdx] & bitValue << ((ckBitPositionOfHm - 1) % 8));
}
}
return hmCodeBytes;
}
/**
* 構建校驗位Table
* key為校驗位對應的海明碼位置量，如:1,2,4,8...
* value為校驗位校驗的海明碼資料位的位置量，如D0被P1(1)和P2(2)校驗位校驗，則P1(1)和P2(2)都有該資料位的值
*
* @param bytes 源位元組陣列
* @return table
*/
private static Map<Integer, List<Integer>> buildCheckBitTable(byte[] bytes) {
Map<Integer, List<Integer>> checkBitTable = new HashMap<>();
int currDataPosition = 1; //當前資料位位置量(位置量從1算)
int currCKBitIdx = -1;//當前校驗位下標
int oneOfBitLen = trimLengthOf(bytes);
for (byte data : bytes) {
for (int j = 0; j < BYTE_BIT_SIZE && oneOfBitLen > 0; j++, oneOfBitLen--) {
int ckBitCount = calculateCheckBitPosition(currDataPosition, 0);
int newCKBitIdx = ckBitCount - 1;
for (int k = currCKBitIdx + 1; k <= newCKBitIdx/*轉成bit位下標*/; k++) { //新增最新計算出的校驗碼位置
int ckBitPositionOfHm = 1 << k; //獲取位置量為k的校驗碼對應的海明碼下標
checkBitTable.putIfAbsent(ckBitPositionOfHm, new ArrayList<>());
}
currCKBitIdx = newCKBitIdx;
int checkBitSize = checkBitTable.size(); //當前校驗碼數量
int hmIdx = checkBitSize + currDataPosition; //海明碼對應下標=校驗碼數量+當前資料位位置量(位置量從1算)
//根據海明碼的規則2：被校驗的海明位的下標是所有參與該位的校驗位的下標之和，而校驗位由自身校驗，
//來獲取當前資料位在海明碼位置量下，參與校驗的校驗碼位置量
List<Integer> checkBitPositions = getOneOfBitPosition(hmIdx);
for (Integer checkBitPosition : checkBitPositions) {
//新增校驗碼對應的被校驗位置的值(0/1),后續在計算校驗位值的時候直接異或所有串列值即可
checkBitTable.get(1 << (checkBitPosition - 1)).add((data >> j) & 1);
}
currDataPosition++;
}
}
return checkBitTable;
}
/**
* 計算資料位的offset所需的最大的校驗位位置量,如 offset=1,k=2，
* 參考海明碼公式：2^k-1≥n+k or 2^k≥n+1+k
*
* @param offset 資料位偏移量(也可以說需要計算的資料位的數量)
* @param k 當前計算出的校驗位數量，遞回傳入
* @return offset所需的校驗位數量
*/
private static int calculateCheckBitPosition(int offset, int k) {
if (Math.pow(2, k) >= offset + 1 + k) {
return k;
}
return calculateCheckBitPosition(offset, ++k);
}
/**
* 校驗編碼，
* 采用偶校驗
*
* @param bytes 海明碼位元組陣列
* @return 如果傳入的位元組陣列無法通過海明碼的校驗，則回傳false，否則回傳true，
*/
public static boolean checkCode(byte[] bytes) {
int bitLen = trimLengthOf(bytes); //位元組陣列拼接后的有效位數（從右到左）
Map<Integer, Integer> checkBitResultTable = new HashMap<>();
int currOffset = 0;
for (int i = bytes.length - 1; i >= 0; i--) {//從位元組陣列右到左遍歷
byte b = bytes[i];
for (int j = 0; j < BYTE_BIT_SIZE && currOffset < bitLen; j++) {
currOffset++;
List<Integer> oneOfBitPositions = getOneOfBitPosition(currOffset);
for (Integer oneOfBitPosition : oneOfBitPositions) {
int tableKey = 1 << oneOfBitPosition - 1;
int bitValue = (b >> j) & 1;
checkBitResultTable.merge(tableKey, bitValue, (a, b1) -> a ^ b1);
}
}
}
return !checkBitResultTable.containsValue(1);
}
/**
* 解碼，
* 對海明碼位元組陣列進行解碼，去除校驗位，獲取原始資料位元組陣列，
*
* @param bytes 海明碼位元組陣列
* @return 原始資料位元組陣列
*/
public static byte[] decode(byte[] bytes) {
int bitLen = trimLengthOf(bytes); //位元組陣列拼接后的有效位數（從右到左）
List<Integer> oneOfBitPositions = getOneOfBitPosition(bitLen); //根據當前海明碼最高位的位置量，獲取需要的校驗位有哪些
int ckBitCount = oneOfBitPositions.get(oneOfBitPositions.size() - 1);//獲取校驗位的數量
int dataBitLen = bitLen - ckBitCount;
int allocateSize = (dataBitLen + BYTE_BIT_SIZE - 1) / BYTE_BIT_SIZE;
byte[] dataBytes = new byte[allocateSize];
int currDataIdx = dataBytes.length - 1;
int currDataOffset = 0;
int currOffset = 0;
for (int i = bytes.length - 1; i >= 0; i--) {//從位元組陣列右到左遍歷
byte b = bytes[i];
for (int j = 0; j < BYTE_BIT_SIZE && currOffset < bitLen; j++) {
currOffset++;
oneOfBitPositions = getOneOfBitPosition(currOffset);
if (oneOfBitPositions.size() == 1) { //如果只有一個1的bit，那么表明當前的下標對應的是校驗位，跳過
continue;
}
byte dataByte = dataBytes[currDataIdx];
int bitValue = (b >> j) & 1;
dataBytes[currDataIdx] = (byte) (dataByte | bitValue << currDataOffset);
currDataOffset++;
if (currDataOffset > 7) {
currDataOffset = 0;
currDataIdx--;
}
}
}
return dataBytes;
}
/**
* 獲取傳入的數字對應的bit位為1的位置量，
* 位置量從1開始計數，從右往左依次獲取，
* 例如：num=10，那么10的二進制是1010，則bit位為1的位置量是2,4(從右往左)
*
* @return bit位為1的位置量串列
*/
public static List<Integer> getOneOfBitPosition(long num) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < LONG_BIT_SIZE; i++) {
if ((num >> i & 1) == 1) {
list.add(i + 1);
}
}
return list;
}
/**
* 獲取位元組陣列的bit位長度，去除了最左位元組的前導0的長度，
*
* @return 去除了最左位元組的前導0的長度
*/
public static int trimLengthOf(byte[] bytes) {
int bitLen = bytes.length * BYTE_BIT_SIZE;
for (int i = BYTE_BIT_SIZE - 1; i >= 0; i--) {
byte b = bytes[0];
if ((b & (1 << i)) != 0) {
break;
}
bitLen--;
}
return bitLen;
}
/**
* 回傳位元組陣列所有bit位字串
*/
public static String toBitStr(byte[] bytes) {
StringBuilder strBuilder = new StringBuilder();
for (byte b : bytes) {
for (int i = BYTE_BIT_SIZE - 1; i >= 0; i--) {
strBuilder.append(b >> i & 1);
}
}
return strBuilder.toString();
}
public static void main(String[] args) {
byte[] bytes = new byte[]{
(byte) Integer.parseInt("101101", 2),
};
System.out.printf("原始碼：%s%n", toBitStr(bytes));
System.out.println("=========");
byte[] hmBytes = encode(bytes);
Map<Integer, List<Integer>> integerListMap = buildCheckBitTable(bytes);
integerListMap.keySet().stream().sorted().forEach((key) -> {
int bitValue;
List<Integer> dataBitValues = integerListMap.get(key);
bitValue = dataBitValues.get(0);
for (int i = 1; i < dataBitValues.size(); i++) {
bitValue = bitValue ^ dataBitValues.get(i);
}
System.out.printf("海明校驗位%d,校驗海明位集：%s,%d%n", key, dataBitValues, bitValue);
});
System.out.println("=========");
System.out.printf("海明碼：%s%n", toBitStr(hmBytes));
System.out.printf("校驗：%s%n", checkCode(hmBytes));
System.out.printf("解碼：%s%n", toBitStr(decode(hmBytes)));
hmBytes[0] >>= 1;
System.out.println("改變海明碼其中一位之后的錯誤編碼:" + toBitStr(hmBytes));
System.out.printf("校驗錯誤編碼：%s%n", checkCode(hmBytes));
}
}
如果要使用該代碼，請充分測驗驗證，代碼僅供學習參考，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260407.html
標籤：其他
上一篇：C語言學習筆記(1) 了解C語言
下一篇：關于memset 初始化陣列