海明校验码(Hamming Code) Java海明码实现(字节数组版本)

墨蓝 2022-10-29 13:24 492阅读 0赞

### 文章目录 ###

*   *   *   *  校验码
             *  术语
             *  海明码
             *  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,那么:

1.   P i P\_i Pi在海明码的第2i-1位置，即 H j = P i H\_j=P\_i Hj=Pi，且j=2i-1，数据位则依序从低到高占据海明码中剩下的位置。
2.  海明码中的任何一位都是由螺杆个校验位来校验的。其对应关系如下：被校验的海明位的下表等于所有参与校验该位的下标只和，而校验位由自身校验。

对于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，则编码过程如下。

1.  确定D与P在海明码中的位置，如下所示：  
    ![在这里插入图片描述][20210216212110804.png]
2.  确定校验关系，如表:  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU_size_16_color_FFFFFF_t_70]  
    若采用奇校验，则将各校验位的偶校验值取反即可。
3.  检测错误。对使用海明编码的数据进行差错检测很简单，只需做一下计算：  
     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 G4G3G2G1全为0时表示接收到的数据无错误。当 G 4 G 3 G 2 G 1 G\_4G\_3G\_2G\_1 G4G3G2G1有一个为1，则说明出了差错。而且 G 4 G 3 G 2 G 1 G\_4G\_3G\_2G\_1 G4G3G2G1的十进制值指出了发生错误的位置，例如 G 4 G 3 G 2 G 1 G\_4G\_3G\_2G\_1 G4G3G2G1=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 * * 规则： * 设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) 海明码中的任何一位都是由若干个校验位来进行校验。其对应关系如下：被校验的海明位的下标是所有参与该位的校验位的下标之和，而校验位由自身校验。 * * 对应位置参照： * H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1 * D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1 * * 当前海明码下标=当前数据位下标+当前校验位数 * 当前数据位下标 * 计算当前海明码下标对应的校验位，并添加到table * 最后将校验位插入原始字节数组 * * 校验关系： * 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 * * 8 4 12 * 9 4 13 * 10 4 14 * 11 4 15 * 12 5 17 * * 反校验，通过海明码的位数来获取最大的校验位，如12个比特位的海明码，12转二进制->1100， * 二进制位数即校验码的数量，按权展开获取10进制即海明码校验位的下标 * * * 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));
 
 }
 }

如果要使用该代码，请充分测试验证，代码仅供学习参考。

[20210216212110804.png]: /images/20221024/7ea9ad4334a2445b8e7fc5d4d8bea8a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU_size_16_color_FFFFFF_t_70]: /images/20221024/44bc08931853446fa7a58992b7b0cdda.png