汉明码编解码原理及C++实现

汉明码是一种能够纠正1位错码且编码效率较高的线性分组码。本文将介绍汉明码的构造原理及其C++实现。

2、汉明码编码

一般来说，若一码长为n，信息位为k，监督位为r=n-k。如果希望用r个监督位构造出r个关系式来指示一个错码的的n种可能位置，则2r−1≥n，即2r≥k+r+1。（为什么是2r−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。据此，我们可以得到以下关系：

因为是异或运算，我们可以将上式通过移相运算，解出监督位：

我们的信息序列为1010，解出监督位填入表格。

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，即第一位校验错误。因此错误码元的位置：

然后将该位置的码元取反即可完成纠错。

再举一例，假设接收端收到的序列为0111010，校验结果为：110。计算错误码元的位置：

结果错误。从而也说明汉明码无法纠正两位错误。

4、C++实现

#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;
}