简单介绍
海明码是一种纠错编码,也就是发送海明码给接收端后,如果传输过程出错,接收端根据收到的码的特征,可以判断出是否出错,并且知道如何纠正出错的位(bit)。
接下来介绍给出一段信息码后,如何计算出它的海明码。
海明码计算
假设信息码为 1010
分 4 个步骤计算其海明码
1、计算需要几位校验码
根据公式 \(n + k \le 2^k -1\) 计算,其中【k】为校验码位数(k取满足公式的最小值),【n】为信息码的位数。
因此1010
对应的校验码的位数 k=3,则海明码总共 4+3 = 7 bit
可以假设最后计算结果海明码为 \(H_7H_6H_5H_4H_3H_2H_1\)
2、计算校验码放的位置
也就是说,得到校验码的位数后,该放在第几位,第一位、第二位、还是第三位...
假设用 \(P_3P_2P_1\)代表 3bit 的校验码,\(D_4D_3D_2D_1\)代表 4bit 的信息码
则\(P_i\)的位置为 \(2^{i-1}\),也就是:
- P1位于第1位(H1所在位置)
- P2位于第2位(H2所在位置)
- P3位于第4位(H4所在位置)
然后信息位按从高到低位的顺序填补剩余空位,因此海明码的结构:
H7 | H6 | H5 | H4 | H3 | H2 | H1 |
---|---|---|---|---|---|---|
D4 | D3 | D2 | P3 | D1 | P2 | P1 |
3、确定每个信息位分别由哪几个校验位负责校验
为了确保信息位中每一位都能得到“照顾”,需要为每一个信息位都分配几个校验位来校验,该信息位出错后可以根据对应的校验位推测出原来是什么。
- D1 位于第三位(从低位往高位数,H3位置),3的二进制是
011
,二进制3中的1
位于哪几位,就由哪几位P负责,因此D1是由【P2P1】负责校验 - D2 位于第5位,5的二进制是
101
,因此D2由【P3P1】负责校验 - D3 位于第6位,6的二进制是
110
,因此D3由【P3P2】负责校验 - D4 位于第7位,7的二进制是
111
,因此D3由【P3P2P1】负责校验
注意:只需要计算信息位的校验码,校验位不需要再计算校验码,传输过程假设校验位
4、计算校验位的具体值
即确定P3、P2、P1具体是1还是0
信息码不用确定:
D4 D3 D2 D1 = 1 0 1 0
- P1:看P1用于哪几个信息位的校验(看第3步),发现是D1、D2、D4,因此 \(P_1=D_1\oplus D_2\oplus D_4 = 0\oplus 1\oplus 1=0\),其中\(\oplus\)表示【异或】
- P2:\(P_2=D_1\oplus D_3\oplus D_4 = 0\oplus 0\oplus 1=1\)
- P3:\(P_3=D_2\oplus D_3\oplus D_4 = 1\oplus 0\oplus 1=0\)
因此,最终的汉明码为 D4 D3 D2 P3 D1 P2 P1
= 1010010
汉明码校验原理
每个校验组分别利用校验位和参与形成该校验位的信息位进行【奇偶校验】构成k个方程:
\[\left\{\begin{matrix} S_1 & = & P_1\oplus D_1\oplus D_2\oplus D_4\\ S_2 & = & P_2\oplus D_1\oplus D_3\oplus D_4\\ S_3 & = & P_3\oplus D_2\oplus D_3\oplus D_4\\ \end{matrix}\right. \]如果 S3 S2 S1 = 000
时说明无差错,否则说明出错,出错的位就是 S3 S2 S1
表示的值。
如 001
表示第一位(即H1)出错,110
是第6位(H6)出错,纠正只需要把错的位取反(0变1,1变0)即可
C++实现海明码编码与校验功能
运行截图
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
bool hasElem(vector<int> arr, int a); //判断数组arr中是否含有元素a
void test(); // 测试函数
int getRandom(int a, int b); // 返回[a, b)之间的随机数
class Sender
{
public:
int msgInput;
int n, k;
int hammingCode;
bool tranErr;
Sender(int msgInput);
int getK();
int getHammingCode();
bool transmit(); // 返回传输过程是否出错
void clear();
~Sender();
};
class Receiver
{
public:
int n; // 信息码位数,提前协商好
int msgRecv;
int msgRecvRect; // 检测到错误修正后的数据
int msgDecode; // 解码后返回的数据, 即发送者输入的值(未编码的值)
bool checkErr; // 是否检测到传输发生的错误
Receiver(int msgRecv, int n);
void clear();
bool recvCheck();
};
Sender::Sender(int msgInput)
{
this->msgInput = msgInput;
this->tranErr = 0;
this->n = 0;
this->k = 0;
this->hammingCode = 0;
}
Receiver::Receiver(int msgRecv, int n)
{
this->msgRecv = msgRecv;
this->msgRecvRect = 0;
this->msgDecode = 0;
this->n = n;
this->checkErr = 0;
}
int main()
{
srand(unsigned(time(NULL)));
test();
return 0;
}
void test()
{
int msg = 1;
Sender *sender = new Sender(0);
Receiver *receiver = new Receiver(0, 0);
// scanf("%d", &msg);
for (int i = 0; i < 10; i++)
{
printf("\n\e[1;34m==============START[%d]===============\e[0m\nInput Data: ", i);
msg = getRandom(1, 1000);
sender->msgInput = msg;
printf("%d\n", sender->msgInput);
sender->getK();
sender->getHammingCode();
printf("[The hamming code is: %d]\n", sender->hammingCode);
sender->transmit();
if (sender->tranErr)
printf("\e[1;31m[Found an error when transmit...]\e[0m\n");
else
printf("\e[1;32m[No error when transmit...]\e[0m\n");
receiver->msgRecv = sender->hammingCode;
receiver->n = sender->n;
receiver->recvCheck();
if (receiver->checkErr)
printf("\e[1;31m[Check an error...]\e[0m\n");
else
printf("\e[1;32m[Checking not find errors]\e[0m\n");
printf("Msg receive before rectify is: %d \n", receiver->msgRecv);
printf("Msg receive after rectify is: %d \n", receiver->msgRecvRect);
printf("Msg receive after decode is: %d \n", receiver->msgDecode);
printf("\e[1;34m===============END[%d]===============\e[0m\n", i);
sender->clear();
receiver->clear();
// delete sender;
// delete receiver;
}
}
bool hasElem(vector<int> arr, int a)
{
for (int i = 0; i < arr.size(); i++)
{
if (arr[i] == a)
return true;
}
return false;
}
int getRandom(int a, int b)
{
int r = a + rand() % (b - a);
return r;
}
// step1,求k,参数是需要传输的信息(十进制即可)
int Sender::getK()
{
int msg = msgInput;
while (msg)
{
msg >>= 1;
n++;
}
while (n + k > ((1 << k) - 1))
{
k++;
}
}
// step2/3/4, 求校验码
// 参数是msg以及上一步的k
int Sender::getHammingCode()
{
int msg = msgInput;
int ans = 0; // 存放最终结果
vector<int> p; // 存放校验码位置,左低右高
vector<int> d; // 存放信息码位置,左低右高
for (int i = 0; i < k; i++)
{
p.push_back(1 << i);
}
for (int i = 1; i <= n + k; i++)
{
if (!hasElem(p, i))
{
d.push_back(i);
}
}
for (int i = 0; i < d.size(); i++)
{
// printf("%d ", d[i]);
ans += (msg & 1) << (d[i] - 1);
msg >>= 1;
}
for (int i = 0; i < p.size(); i++)
{
int x = 0;
for (int j = 0; j < d.size(); j++)
{
if ((d[j] >> i) & 1 != 0)
x = x ^ ((ans >> (d[j] - 1)) & 1);
}
if (x == 1)
ans += (1 << (p[i] - 1));
}
hammingCode = ans;
return ans;
}
// 传输过程某一位出错,海明码只能校验一位出错情况,x为传输位数
bool Sender::transmit()
{
int msgSend = hammingCode;
bool f = 0; //某次传输是(1)否(0)出错
int mistakeBit = 0; // 出错的位,从0开始
f = rand() & 1; // 某一时刻是否出错
if (f)
{
mistakeBit = rand() % (n + k);
msgSend ^= (1 << mistakeBit); // 出错位与1异或(出错位是1,则变为0;0则变为1)
// printf("===the bit error is: %d \n", mistakeBit+1);
}
// printf("TEST------>msg: %d========\n", msgSend);
tranErr = f;
hammingCode = msgSend;
return f;
}
// n是收发双方约定的位数
bool Receiver::recvCheck()
{
int msgR = msgRecv;
int k = 0; // 接收方计算k
while (n + k > ((1 << k) - 1))
k++;
vector<int> p; // 存放校验码位置,左低右高
vector<int> d; // 存放信息码位置,左低右高
int s = 0; // 校验子,用于表示哪1位出错了,0表示没有出错
checkErr = 0;
for (int i = 0; i < k; i++)
{
p.push_back(1 << i);
}
for (int i = 1; i <= n + k; i++)
{
if (!hasElem(p, i))
{
d.push_back(i);
}
}
for (int i = 0; i < k; i++)
{
int x = (msgR >> (p[i] - 1)) & 1;
for (int j = 0; j < n; j++)
{
if ((d[j] >> i) & 1)
x ^= ((msgR >> (d[j] - 1)) & 1);
}
s += (x << i);
}
// 下面进行错误位纠正
if (s != 0)
{
msgRecvRect = msgR ^ (1 << (s - 1));
checkErr = 1;
}
else
{
msgRecvRect = msgR;
}
int tmp = msgRecvRect, tt = 0;
for (int i = 1; i <= n + k; i++)
{
if (hasElem(p, i))
{
tmp >>= 1;
tt++;
}
else
{
msgDecode += ((tmp >> (i - tt - 1) & 1) << (i - tt - 1));
}
}
return checkErr;
}
void Sender::clear(){
this->hammingCode=0;
this->k = 0;
this->msgInput = 0;
this->n = 0;
this->tranErr = 0;
}
void Receiver::clear() {
this->msgRecv = 0;
this->n = 0;
this->msgRecvRect = 0;
this->msgDecode = 0;
this->checkErr = 0;
}
标签:sender,int,明码,校验,printf,oplus,纠错
From: https://www.cnblogs.com/ajream/p/16772670.html