通信人家园

标题: 通信中的校验纠错 [查看完整版帖子] [打印本页]

时间: 2018-4-2 15:45

作者: Hu_JX_ID 标题: 通信中的校验纠错

CRC

CRC校验码位数 = 生成多项式 G(x) 位数 – 1 = R

假设使用的生成多项式为G(x) = X3 + X + 1转换成对应的二进制除数为1011 R=4-1=3

原码为1010

第一步：将原码左移三位得到1010_000

第二步：项式(1011)对信息码(1010)做模2除法【实现：1010_000与1011高位对齐做异或运算得到0001000，左移一位之后，高位为0则除以0000，得到001000，左移一位之后，高位为0则除以0000，得到01000，。。。。。得到1000，高位为1则除以1011，得到0011】得到R位余位011

第三步：得到最终编码1010_011

汉明

汉明（7，4）码中，全部码长是7位：C7C6C5C4C3C2C1，其中4位原始信息位D与3位奇偶效验位P通过如下方式组成：

C7	C6	C5	C4	C3	C2	C1	说明
D	D	D	P	D	P	P	信息位D与效验位P的排列形式
D		D		D		P	原始信息位C7C5C3与附加位C1组成偶效验
D	D			D	P		原始信息位C7C6C3与附加位C2组成偶效验
D	D	D	P				原始信息位C7C6C5与附加位C4组成偶效验

我们现在可以发现这样用3个附加位的好处了：如果由附加位C1组成的奇偶效验码C7C5C3C1发现错误，我们可以推断C7C5C3这三位中有一位出错；如果由附加位C2组成的奇偶效验码C7C6C3C2发现错误，我们可以推断C7C6C3中有一位出错；如果由附加位C4组成的奇偶效验码C7C6C5C4发现错误，我们则可以推断C7C6C5中有一位出错。

上叙规律用左图表示，根据1，2，4这三组奇偶效验码的指示，我们可以准确的知道原始信息位C7C6C5C3哪个出了错。比如1，2同时报错但4组无错，可以断定C3错了。

例如：原始信息码1101通过（7，4）码进行编码为：

C7	C6	C5	C4	C3	C2	C1	说明
1	1	0	P	1	P	P	信息位D与效验位P的排列形式
1		0		1		0	C1=0使得该组1的个数为2个
1	1			1	1		C2=1使得该组1的个数为4个
1	1	0	0				C4=1使得该组1的个数为2个
1	1	0	0	1	1	0	1100110为1101的（7，4）编码

编码后的1100110经过传输，假设因为线路噪音变为1110110

发送信息：1100110 ———> 接收到的信息：1110110

位：7654321 位：7654321

使用右图我们可以准确发现错误：

C1组C7C5C3C1=1110，3个1，该组有错误

C2组C7C6C3C2=1111，4个1，该组没错

C4组C7C6C5C4=1110，3个1，该组有错误

根据集合方式，由1，4组的圆，我们肯定C5C7有错，由2组的圆，得到C7没错，于是出错的肯定是C5。为了纠正它，将收到的C5=0改为C5=1即可。

实际使用中，汉明采用了数学上更好的形式，可以非常方便的通过清晰的矩阵运算得到纠错结果。汉明在提出（7，4）码的过程中，还建立了基础的编码理论。经过高伯（Goppa）和谢伐斯曼（Tsfasman）的发展，现代编码已经是计算机系统中最重要的技术之一。汉明码还有一个更绕口的名字加线性分组码。

奇偶校验

奇校验：如果以二进制数据中1的个数是奇数为依据，则是奇校验

偶校验：如果以二进制数据中1的个数是偶数为依据，则是偶校验

通信人家园 (https://www.txrjy.com/)