• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

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

互联网 diligentman 1周前 (02-17) 7次浏览

文章目录

        • 校验码
        • 术语
        • 海明码
        • java实现

校验码

计算机系统运行时,为了确保数据在传递过程中正确无误,一是提高硬件电路的可靠性,二是提高代码的校验能力,包括查错与纠错。通常使用校验码的方法来检测传送的数据是否出错。其基本思想是把数据可能出现的编码分为两类:合法编码与错误编码。合法编码用于传送数据,错误编码是不允许在数据中出现的编码。合理的设计错误编码以及编码规则,使得数据在传送中出现错误时会变为错误编码,这样就可以检测出接收的数据是否有错。

术语

码字:是指编码系统中的合法编码称为码字。
码距:是指编码系统中任意两个合法编码之间至少有多少个二进制位不同。如:合法编码为11、00,那么11与00之间至少有两个二进制位不同,所以码距为2。

海明码

关于海明码的知识,我还是认为只有《软件设计师教程(第5版)》的海明码讲解简单易懂,结合海明码规则和关系表格来学习,很容易上手。最后的部分是用java实现的字节数组版本的海明码编码与解码以及校验。

以下内容摘自《软件设计师教程(第5版)》:

海明码(Hamming Code)是由贝尔实验室的Richard Hamming设计的,是一种利用奇偶性来检错和纠错的校验方法。海明码的构成方法是在数据位之间的特定位置上插入k个校验位,通过扩大码距来实现检错和纠错。

设数据位是n位,校验位是k位,则nk必须满足一下关系:

2

k

1

n

+

k

2^k-1 geqslant n+k

2k1n+k
海明码的编码规则如下。
k个校验位为

P

k

,

P

k

1

,

.

.

.

,

P

1

P_k,P_{k-1},…,P_1

Pk,Pk1,...,P1n个数据位为

D

n

1

,

D

2

,

.

.

.

,

D

1

,

D

0

D_{n-1},D_2,…,D_1,D_0

Dn1,D2,...,D1,D0,对应的海明码为

H

n

+

k

,

H

n

+

k

1

H_{n+k},H_{n+k-1}

Hn+k,Hn+k1,那么:

  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在海明码中的位置,如下所示:
    海明校验码(Hamming Code) Java海明码实现(字节数组版本)

  2. 确定校验关系,如表:
    海明校验码(Hamming Code) Java海明码实现(字节数组版本)
    若采用奇校验,则将各校验位的偶校验值取反即可。

  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=P1D0D1D3D4D6

    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=P2D0D2D3D5D6

    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=P3D1D2D3D7

    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=P4D4D5D6D7
    若采用偶校验,则

    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
 * <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));

    }
}

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


程序员灯塔
转载请注明原文链接:海明校验码(Hamming Code) Java海明码实现(字节数组版本)
喜欢 (0)