Loading... ## 1、前言 汉明码是一种能够纠正1位错码且编码效率较高的线性分组码。本文将介绍汉明码的构造原理及其C++实现。 ## 2、汉明码编码 一般来说，若一码长为`n`，信息位为`k`，监督位为`r=n-k`。如果希望用`r`个监督位构造出`r`个关系式来指示一个错码的的`n`种可能位置，则$2^r - 1\ge n$，即$2^r\ge k+r+1$。（为什么是$2^r-1$？因为其中一种表示无错）。因此，对于（7，4）汉明码来说，`k=4`，`r=3`。 那么，n,k,r现在都有了，如何构造汉明码，也就是校验码应该放在哪的问题。接下来我将以四位信息码`1010`为例，来讲解汉明码的编码过程。 对于7位码长的汉明码，有7个位置编号（从1开始），然后计算的到对应的二进制。我们定义校验码的位置是位置编号的对应二进制只有一个1的位置，即1（001）、2（010）、4（100）。剩下的思维就是信息码的位置，我们只需按顺序填入即可。 **计算校验码**。规定：对于第一位校验码，其二进制中`1`的位置的包含最低位，将7个位置编号对应二进制码最低位为1的数分为一组，分别是1（001）、3（011）、5（101）、7（111）。对于第二位校验码，其二进制中`1`的位置的包含中间位，将7个位置编号对应二进制码中间位为1的数分为一组，分别是2（010）、3（011）、6（110）、7（111）。对于第三位校验码，其二进制中`1`的位置的包含最高位，将7个位置编号对应二进制码最高位为1的数分为一组，分别是4（100）、5（101）、6（110）、7（111）。 一般来说，汉明码默认采用偶校验，因此，如果没有错误（在编码的时候），S1、S2、S3都为0。即分组中的四个位置对应的码异或结果为0。据此，我们可以得到以下关系： $$ 0 = a_1\oplus a_3\oplus a_5\oplus a_7 $$ $$ 0 = a_2\oplus a_3\oplus a_6\oplus a_7 $$ $$ 0 = a_4\oplus a_5\oplus a_6\oplus a_7 $$ 因为是异或运算，我们可以将上式通过移相运算，解出监督位： $$ a_1 = a_3\oplus a_5\oplus a_7 $$ $$ a_2 = a_3\oplus a_6\oplus a_7 $$ $$ a_4=a_5\oplus a_6\oplus a_7 $$ 我们的信息序列为`1010`，解出监督位填入表格。 | 位置编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | ---------- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | 对应二进制 | 001 | 010 | 011 | 100 | 101 | 110 | 111 | | 信息码填充 | | | 1 | | 0 | 1 | 0 | | 监督位 | 1 | 0 | | 1 | | | | | 编码后序列 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | ## 3、汉明码解码 我们知道（7，4）汉明码可以纠1位错误。下面，我将以上面的信息序列`1010`以及它对应的编码序列`1011010`为例说明汉明码解码的过程。 假设，编码序列第一位在传输过程中出错，接收端收到的序列为`0011010`。然后我们根据上面编码部分提到的偶校验方法计算校验结果（对应序列位置分别是`[1357]`、`[2367]`、`[4567]`），校验结果是：100。即第一位校验结果出错。 我们规定`p`、`q`、`r`分别是当校验结果错误时对应位置序列集合的补集，即(2,4,6)、(1,4,5)、(1,2,3)。。`n_p`，`n_q`、`n_r`分别是当校验结果正确时对应位置序列的集合，即(1,3,5,7)、(2,3,6,7)、(4,5,6,7)。根据校验结果的对错，我们可以得到三组集合，然后通过求这三组集合的交集得到错误码元的位置。 在回到上面的校验结果，我们计算得到校验结果为100，即第一位校验错误。因此错误码元的位置： $$ pos = n\_p \cap q \cap r $$ $$ pos = (1,3,5,7)\cap(1,4,5)\cap(1,2,3)=1 $$ 然后将该位置的码元取反即可完成纠错。 再举一例，假设接收端收到的序列为`0111010`，校验结果为：110。计算错误码元的位置： $$ pos = n\_p \cap n\_q \cap r $$ $$ pos = (1,3,5,7)\cap(2,3,6,7)\cap(1,2,3)=3 $$ 结果错误。从而也说明汉明码无法纠正两位错误。 ## 4、C++实现 ```cpp #include <iostream> #include <set> #include <algorithm> using namespace std; //Hamming encode void hammingEnc(const int* input, int* output) { output[0] = input[0] ^ input[1] ^ input[3]; output[1] = input[0] ^ input[2] ^ input[3]; output[3] = input[1] ^ input[2] ^ input[3]; output[2] = input[0]; output[4] = input[1]; output[5] = input[2]; output[6] = input[3]; } //Hamming decode void hammingDec(const int* input, int* output) { int input_copy[7]; for (int i = 0; i < 7; i++) { input_copy[i] = input[i]; } std::set<int> set_p{ 1,3,5,7 }; std::set<int> set_not_p{ 2,4,6 }; std::set<int> set_q{ 2,3,6,7 }; std::set<int> set_not_q{ 1,4,5 }; std::set<int> set_r{ 4,5,6,7 }; std::set<int> set_not_r{ 1,2,3 }; int p = input[0] ^ input[2] ^ input[4] ^ input[6]; int q = input[1] ^ input[2] ^ input[5] ^ input[6]; int r = input[3] ^ input[4] ^ input[5] ^ input[6]; std::set<int> p_set; std::set<int> q_set; std::set<int> r_set; if (p == 1) p_set = set_p; else p_set = set_not_p; if (q == 1) q_set = set_q; else q_set = set_not_q; if (r == 1) r_set = set_r; else r_set = set_not_r; set<int> temp_set; set<int> intersection; set_intersection(p_set.begin(), p_set.end(), q_set.begin(), q_set.end(), std::inserter(temp_set, temp_set.begin())); set_intersection(temp_set.begin(), temp_set.end(), r_set.begin(), r_set.end(), std::inserter(intersection, intersection.begin())); if (intersection.size() > 0) { int error_pos = *intersection.begin(); if (input_copy[error_pos - 1] == 1) input_copy[error_pos - 1] = 0; else input_copy[error_pos - 1] = 1; } output[0] = input_copy[2]; output[1] = input_copy[4]; output[2] = input_copy[5]; output[3] = input_copy[6]; } void printVector(const int* v, int len) { for (int i = 0; i < len; i++) std::cout << *(v + i) << " "; std::cout << endl; } int main() { int input[4]; input[0] = 1; input[1] = 0; input[2] = 1; input[3] = 0; int enc_output[7]; int dec_output[4]; std::cout << "错1位：" << std::endl; std::cout << "信息序列: "; printVector(input, 4); hammingEnc(input, enc_output); std::cout << "编码序列: "; printVector(enc_output, 7); //错1位 if (enc_output[1] == 1) enc_output[1] = 0; else enc_output[1] = 1; ////错2位 //if (enc_output[2] == 1) // enc_output[2] = 0; //else // enc_output[2] = 1; std::cout << "误码序列: "; printVector(enc_output, 7); hammingDec(enc_output, dec_output); std::cout << "解码序列: "; printVector(dec_output, 4); return 0; } ```   Last modification：March 2nd, 2022 at 11:11 am © 允许规范转载
One comment
1