汉明码（Hamming Code）原理及实现

偏执的太偏执、 2022-05-10 04:10 275阅读 0赞

### 汉明码（Hamming Code）原理及实现 ###

##### 汉明码实现原理 #####

汉明码（Hamming Code）是广泛用于内存和磁盘纠错的编码。汉明码不仅可以用来检测转移数据时发生的错误，还可以用来修正错误。（要注意的是，汉明码只能发现和修正一位错误，对于两位或者两位以上的错误无法正确和发现）。

设将要进行检测的二进制代码为n位，为使其具有纠错能力，需要再加上k位的检测位，组成n+k位的代码。那么，新增加的检测位数k应满足：

>  2 k − 1 ≥ n + k 2^k-1\\geq n+k 2k−1≥n\+k

这就是Hamming不等式，汉明吗规定，我们所得到的m位编码 2 k ( k ≥ 0 ∣ 2 k < n + k ) 2^k(k\\geq0\\mid 2^k<n+k) 2k(k≥0∣2k<n\+k)位上插入特殊的校验码，其余位把源码按顺序放置。

汉明码的编码规则如下：

*  在新的编码的2^(k-1)(k >= 0)位上填入0（即校验位）
 *  把新的编码的其余位把源码按原顺序填入
 *  校验位的编码方式为：第k位校验码从则从新的编码的第2^(k - 1)位开始，每计算2^(k - 1)位的异或，跳2^(k - 1)位，再计算下一组2^(k - 1)位的异或，填入2^(k - 1)位，比如：  
    第1位校验码位于新的编码的第1位(2 ^(1-1) == 1)（汉明码从1位开始），计算1,3,5,7,9,11,13,15,…位的异或，填入新的编码的第1位。  
    第2位校验码位于新的编码的第2位(2 ^(2-1) == 2)，计算2,3,6,7,10,11,14,15,…位的异或，填入新的编码的第2位。  
    第3位校验码位于新的编码的第4位(2 ^(3-1) == 4)，计算4,5,6,7,12,13,14,15,20,21,22,23,…位的异或，填入新的编码的第4位。  
    第4位校验码位于新的编码的第8位(2 ^(4-1) == 8)，计算8-15,24-31,40-47,…位的异或，填入新的编码的第8位。  
    第5位校验码位于新的编码的第16位(2 ^(5-1) == 16)，计算16-31,48-63,80-95,…位的异或，填入新的编码的第16位。

##### 汉明码编码实例 #####

以10101编码为例，创建一个汉明码编码的空间，并且把源码填入编码的对应位中中，\_ \_ 1 \_ 0 10 \_ 1，并留出校验码位（校验位先设为0）。（因为2^4 - 1>= 5+4 && 2^3 - 1 < 5+ 3所以需要4位校验码）

*  计算校验码的第1位（1,3,5,7,9进行异或）: 结果为0，所以汉明码第2^0位为0，结果为0 \_ 1 \_ 0 10 \_ 1
 *  计算校验码的第2位（2,3,6,7进行异或）: 结果为0，所以汉明码第2^1位为0，结果为001 \_ 0 10 \_ 1
 *  计算校验码的第3位（4,5,6,7进行异或）: 结果为1，所以汉明码第2^2位为0，结果为0011 0 10 \_ 1
 *  计算校验码的第4位（8, 9进行异或）: 结果为0，所以汉明码第2^3位为1，结果为0011 0101 1
 *  所以最终编码为001101011.

##### 汉明码校验错误实例 #####

我们以上面的编码为例，假设我们现在收到的编码为001101001，我们可以发现汉明码的第8位与原来的汉明码001101011不同，那我们怎么找出这个第8位的错误编码呢？

算法很简单，我们只要在算汉明码校验位的算法的上再算一遍，就得到了汉明码的校验方法，比如计算001101001对应的2^k位。

> 1,3,5,7,9进行异或，得到0  
> 2,3,6,7进行异或，得到0  
> 4,5,6,7进行异或，得到0  
> 8,9进行异或，得到1

我们把上述结果反着排列，得到1000，即十进制的8，根据汉明码的校验规则，编码出错的地方即在第8位，我们把第8位的0换成1，即可得原来的编码001101011。

上述的例子是出现在2k的校验位上的，如果出现在非2k位上，得到的结果也是一样的，比如：  
假设收到的编码为001100011，即第6位出了错误，我们根据规则

> 1,3,5,7,9进行异或，得到0  
> 2,3,6,7进行异或，得到1  
> 4,5,6,7进行异或，得到1  
> 8,9进行异或，得到0

我们把上述结果反着排列，得到0110，即十进制的6，根据汉明码的校验规则，编码出错的地方即在第6位，我们把第6位的0换成1，即可得原来的编码001101011。

##### 汉明码的编码和校验的C++实现 #####

通过原理，我们可以和简单地实现汉明码的编码和校验代码  
编码：

auto cal(size_t sz)->decltype(auto)
    {
        decltype(sz) k = 0;
        decltype(sz) cur = 1;
        while (cur - 1 < sz + k )
        {
            cur <<= 1;
            k++;
        }   
        return k;
    }
    
    bool encode(const string &s, string &d)
    {
        d.clear();
        auto k = cal(s.size());
        d.resize(s.size() + k);
        for (decltype(d.size()) i = 0, j = 0, p = 0; i!= d.size();i++)
        {
            if ((i + 1) == pow(2,p) && p < k)
            {
                d[i] = '0';
                p++;
            }
            else if (s[j] == '0' || s[j] == '1')
                d[i] = s[j++];
            else 
                return false;
        }
        for (auto i = 0; i != k;i++)
        {
            int count = 0 ,index = 1 << i;
            for (auto j = index - 1; j < d.size() ;j += index)
                for (auto k = 0; k!= index && j < d.size(); k++, j++)
                    count ^= d[j] - '0';
            d[index - 1] = '0' + count;
        }
        return true;
    }

解码与校验：

auto antiCal(size_t sz)->decltype(auto)
    {
        decltype(sz) k = 0;
        decltype(sz) cur = 1;
        while (cur < sz)
        {
            cur <<= 1;
            k++;
        }   
        return k;
    }
    
    auto decode(string &s, string &d)->decltype(auto)
    {
        s.clear();
        auto k = antiCal(d.size());
        s.resize(d.size() - k);
    
        decltype(d.size()) sum = 0;
        for (decltype(k) p = 0;p != k;p++)
        {
            int pAnti = 0;
            decltype(k) index = 1 << p;
            for (decltype(d.size()) i = index - 1;i < d.size(); i+=index)
            {
                for (auto j = 0; j < index && i < d.size(); i++, j++)
                    pAnti ^= d[i] - '0';
            }
            sum += pAnti << p;
        }
        if (sum != 0)
            d[sum - 1] = (1- (int)(d[sum - 1] - '0')) + '0';
    
        for (decltype(d.size()) i = 0, p = 0,j = 0; i != d.size(); i++)
        {
            if ((i + 1) == (1 << p) && p < k)
                p++;
            else
                s[j++] = d[i];
        }
    
        return sum;
    }

测试样例：

int main()
    {
        string source, dest;
        while (cin >> source)
        {
            if (encode(source,dest))
            {
                cout << "Source: " <<source << endl;
                cout << "Dest: " << dest << endl;
            }
            size_t index;
            cout << "----input error index : ";
            cin >> index;
            auto k = dest.size();
            if (index != 0 && index <= dest.size())
                dest[index - 1] = (1 - (int)(dest[index - 1] - '0')) + '0';
            cout << "Code " << dest <<endl;
            auto ret = decode(source,dest);
            if (ret == 0)
            {
                cout << "Source: " <<source << endl;
                cout << "Dest: " <<dest << endl;
            }   
            else
            {
                cout << "Error index "<< ret  << endl;
                cout << "Corret source: " <<source << endl;
                cout << "Corret dest: " <<dest << endl;
            }
            cout << endl;
        }
        return 0;
    }