欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2021-01-23--常见效验

程序员文章站 2022-05-01 16:36:20
...

常见效验

借鉴博客链接:

奇偶效验:
https://www.cnblogs.com/Mayfly-nymph/p/11098007.html
海明效验:
https://www.cnblogs.com/Mayfly-nymph/p/11098213.html
循环冗余效验:
https://www.cnblogs.com/Mayfly-nymph/p/11100021.html

奇偶效验

  • 奇效验:使完整编码(有效位和效验位)中的“1”的个数为奇数个
  • 偶效验:使完整编码(有效位和效验位)中的“1”的个数为偶数个

奇效验:
当有效信息的“1”为奇数个的时候,最后添0,反之添加1

偶效验:
当有效信息的“1”为奇数个的时候,最后添加1,反之添加0
举栗子:

有效信息 奇效验码 偶效验码
110011 1100111 1100110
101010 1010101 1010100

奇偶校验实际上就是对我们DnDn-1…D0进行异或运算(两两相同为0,不同为1),最后偶校验生成0,奇校验生成1,正确,反之错误。

第一个奇效验:
1⊕1⊕0⊕0⊕1⊕1⊕1=1(正确)

第一个偶效验:
1⊕1⊕0⊕0⊕1⊕1⊕0=0(正确)

第二个奇效验:
1⊕0⊕1⊕0⊕1⊕0⊕1=1(正确)

第二个偶效验:
1⊕0⊕1⊕0⊕1⊕0⊕0=0(正确)

海明效验

定义

海明码利用奇偶性来检错和纠错的效验方法。海明码的构成方法是在数据位之间的确定的位置插入k个效验位,通过扩大码距来实现检错和纠错。

对于数据位m的数据,加入k位的效验码,应该满足香农的第二定理:n=m+k<=2^k-1

说明:
这里的m就是待编有效信息的位数,例如110101就是m=6,然后代入m,6+k<=2^k-1得到m=6,k>=4(取最小值),这样组成10位海明效验码

例子
设数据为01101001,试采用校验位求其偶校验方式的海明码。
根据上面的公式得到,m=8,k≥4
(1)确定数据位D和效验位P在海明码中的位置:
由海明码编码规则可知:Pi在海明码的第2i-1,比如P4=2(4-1)=8,所以位于第8位

海明码 1 2 3 4 5 6 7 8 9 10 11 12
效验位 P1 P2 P3
数据位 D0 D1 D2 D3 D4 D5 D6 D7

(2)确定效验关系
这个难点在于如何确定效验位组
H3=D0,海明码下标为3,我们必须用已知的效验位(P1,P2,P3,P4)来表示3,这里的3等于1+2

海明码 海明码下标 效验位组
H1 1 P1
H2 2 P2
H3(D3) 3 = 1+2 P1,P2
H4 4 P3
H5(D1) 5 = 1+4 P1,P3
H6(D2) 6 = 2+4 P2,P3
H7(D3) 7 = 1+2+4 P1,P2,P3
H8 8 P4
H9(D4) 9 = 1+8 P1,P4
H10(D5) 10 = 2+8 P2,P4
H11(D6) 11 = 1+2+8 P1,P2,P4
H12(D7) 12 = 4+8 P3,P4

(3)故:P1效验:P1,D0,D1,D3,D4,D6

P1=D0⊕D1⊕D3⊕D4⊕D6=0⊕1⊕0⊕1⊕0=0
P2=D0⊕D2⊕D3⊕D5⊕D6=0⊕1⊕0⊕0⊕0=1
P3=D1⊕D2⊕D3⊕D7=1⊕1⊕0⊕1=1
P4=D4⊕D5⊕D6⊕D7=1⊕0⊕0⊕1=0

⊕符号:代表异或,相同则为0,不同则为1。只要仔细一定可以计算正确。

按照表格海明码的位置插入P1~P4到数据中,所以海明校验码:010111001001

(4)设置指错字G4,G3,G2,G1

G4=P4⊕D4⊕D5⊕D6⊕D7
G3=P3⊕D1⊕D2⊕D3⊕D7
G2=P2⊕D0⊕D2⊕D3⊕D5⊕D6
G1=P1⊕D1⊕D3⊕D4⊕D6

G1G2G3G4为0000,则数据传输没有错误。

以上面的数据传输为例子:
G4=0  G3=0  G2=0  G1=0

若数据传输之后变成010111001000

G4=P4⊕D4⊕D5⊕D6⊕D7=0⊕1⊕0⊕0⊕0=1
G3=P3⊕D1⊕D2⊕D3⊕D7=1⊕1⊕1⊕0⊕0=1
G2=P2⊕D0⊕D2⊕D3⊕D5⊕D6=1⊕0⊕1⊕0⊕0⊕0=0
G1=P1⊕D1⊕D3⊕D4⊕D6=0⊕0⊕1⊕0⊕1⊕0=0

G4G3G2G1组成的二进制数为:1100,也就是12,说明第12位出现的错误

(5)海明码效验缺点

  • (1)海明校验的每一步还是使用的奇偶校验,因此当G中同时出现两个错误时,G1G2G3G4依然为0000,例如D1,D2出错,010100001001

G4=P4⊕D4⊕D5⊕D6⊕D7=0⊕1⊕0⊕0⊕0⊕1=0
G3=P3⊕D1⊕D2⊕D3⊕D7=1⊕0⊕0⊕0⊕1=0
G2=P2⊕D0⊕D2⊕D3⊕D5⊕D6=1⊕0⊕0⊕0⊕0⊕0=1
G1=P1⊕D1⊕D3⊕D4⊕D6=0⊕0⊕0⊕1⊕0=1

  • (2)同时,G4G5G6G1=0000不一定数据传输过程中就没有错误,只有当只有一位发生错误时,才能检测出来。

G1G2G3G4=0011,也就是第3位出现错误,很明显这是不准确的。

循环冗余效验

冗余码

CRC和海明效验码类似,也就是有效信息(k位)+效验信息(r位),需要满足n=m+k<=2^k-1

生成多项式G(X)

定义

收发双方约定的一个(k+1)位二进制数,发送方利用G(X)对信息多项式做模2除运算,生成效验码。接收方利用G(X)对收到的编码多项式做模2除运算检测差及错误定位

满足条件:

  • 1.最高位和最低位必须为1
  • 2.当被传送信息(CRC码)任何一位发生错误时,被生成多项式做除后应该使余数不为0
  • 3.不同位数发生错误时,模2除运算后余数不同;
  • 4.对不为0余数继续进行模2除运算应使余数循环
G(X)多项式 G(X)
x3+x2 +x+1 1111
x3 +x+1 1011
x4+x2 +x+1 10111

下面举个栗子:
假设我们要传输的数据为:
11001100

我们约定一个G(X),但是在得出G(X)的长度之前,我们先要计算一下k的位数应该为多少。我们要传输的数据的位数是8位,那么根据n=m+k<=2^k-1,这个公式,我们可以得出:k应该为4
并且G(X)的最高位和最低位都应该是1,那么我们就约定一个:
10001
(或许有的人要问了,为啥是五位数呢?因为k是4,我们约定的位数应该比这个k多一位数字)

接着在11001100后面添加0000四个0

再用110011000000去和10001进行模2除运算。
运算的过程中,余数的开头为,那么就在上面添0,如果开头是1的话,那么就可以添加1

这个可以算出来结果是:
11000000
余数是:
0000
那么就表明正确的冗余码应该是:
0000
添加到后面就是:
110011000000
上面就是编码后的

相关标签: 2021

上一篇: 2021-01-18--闲谈

下一篇: JJWT工具类