2 .奇偶校验
奇偶校验码是增加二进制传输系统最小距离的简单且被广泛采用的方法。 例如,单个奇偶校验将代码的最小距离从1增加到2。
在二进制码字中,如果该符号有奇数个1,则称为有奇性。 例如,码字“10110101”有五个1。 因此,该码字具有奇性。 类似地,具有偶数个1的偶数码字。 请注意,奇性检测相当于所有符号的模2加法,可通过所有符号的异或运算来确定。 对于一个n比特字,奇性由以下公式给出:
性=A0a1a2an
可以将奇偶校验描述为向每个码字添加奇偶校验位,并使用该奇偶校验构成奇性或偶性校验。 例如,在图8-2中,就是这样做的。 可知附加符号d2是为了简单地对每个单词偶性。 因此,如果一个符号错误,奇偶校验是奇性的,所以可以进行识别。 奇偶校验编码通过将奇偶校验位增加1位而使代码中的一个个数为奇数(奇校验)或偶数,使代码间距离为2。 因为这是以代码中1的个数的奇偶校验为根据来利用的,所以无法发现偶数位的错误。
并且,以数字0的7位ASCII代码(0110000 )为例,如果传输后右边的第1位发生错误,则0为1。 接收方还认为是合法代码0110001 (数字1的ASCII代码)。 如果在最左边添加奇偶校验位,则代码为10110000,发送后右数位错误则为10110000,1的个数为偶数时,则不是合法的奇偶校验位。 但是,如果有2位(假设第1、2位)的错误的话就会变成10110011,1的个数是5还是奇数。 接收方还认为是合法代码(数字3的ASCII代码)。 所以不能发现奇偶校验。
奇偶校验可以由硬件电路(异或门)或软件生成。
奇偶校验位
an=A0a1a2an-1,奇偶校验位
an=not (A0a1a2. an-1 )。
在典型的系统中,在传输之前,奇偶校验发生器向每个字添加奇偶校验。 原始信息中的数字被接收器检测到,
如果没有出现正确的奇、偶性,该信息被识别为错误,该系统将丢弃错误的字或请求重传。
在实际工作中,还经常采用分组奇偶校验,这是一种纵横添加奇偶校验的编码系统。
考虑一下系统吧,
传输一些长度为m位的信息。 如果将所有这些信息组织成每组n个信息组,则在这些不同的信息之间也能够与各个信息同样地进行奇偶校验。 图4中的n个信息的一个组排列成矩形的图案,以横奇偶校验位(HP )和纵奇偶校验位(VP )的形式编辑奇偶校验位。
m位数字
横向奇偶校验
n
个
代码
字
a1
a2
.
am-1
自动取款机
HP1
b1
b2
.
bm-1
bm
HP2
c1
c2
.
cm-1
广告
HP3
.
.
.
.
.
.
n1
n2
.
nm-1
纳米
HPn
VP1
VP2
.
VPm-1
VPm
HPn 1
纵向奇偶校验
图4
使用邮件横向奇偶校验的分组奇偶校验码
观察图4可知,分组奇偶校验码不仅能够检测许多形式的错误。 另外,当给定的行或列中发生孤立的错误时,也可以修正该错误。
在初级程序员问题(早期也出现在程序员问题中)中,经常存在邮件横向奇偶校验问题。 一般的解法是,首先要寻找一行或一列的已知数据完整,然后决定该行(或列)是奇校验还是偶校验。 并且,假设行和列采用同一类型的检查(该假设是否正确,在全部结束后可以验证)。 然后,寻找只有一个未知数的行和列,根据检查的性质确定该未知数。 如果你继续这样做,你就可以求出所有的未知数。
【例】2001年初级程序员问题
6位7位ASCII
码数组和水平和垂直奇偶校验相加,构成以下矩阵(最后一列为水平奇偶校验,最后一行为垂直奇偶校验) :
文字
7位
ASCII代码
惠普
3
0
X1
X2
0
0
1
1
0
Y1
1
0
0
1
0
0
X3
1
X4
1
0
1
0
1
1
0
Y2
0
1
X5
X6
1
1
1
1
d
1
/p>0
0
X7
1
0
X8
0
=
0
X9
1
1
1
X10
1
1
VP
0
0
1
1
1
X11
1
X12
则 X1 X2 X3
X4 处的比特分别为 __(36)__ ;
X5
X6 X7 X8 处的比特分别为 ____
;
X9
X10 XI1 X12 处的比特分别为
__(38)__ ;Y1 和 Y2 处的字符分别为 __(39)__
和 __(40)__ 。
[解]
从ASCII码左起第5列可知垂直为偶校验。则:
从第1列可知X4=0;从第3行可知水平也是偶校验。
从第2行可知X3=1;从第7列可知X8=0;从第8列可知X12=1;
从第7行可知X11=1;从第6列可知X10=0;从第6行可知X9=1;从第2列可知X1=1;
从第1行可知X2=1;从第3列可知X5=1;从第4行可知X6=0;
从第4列(或第5行)可知X7=0;整理一下:
(36)
X1X2X3X4 =
1110
(37)
X5X6X7X8 =
1000
(38)
X9X10X11X12 =
1011
(39)
由字符Y1的ASCII码1001001=49H知道,Y1即是“I”(由“D”的ASCII码是1000100=44H推得)
(40)
由字符Y2的ASCII码0110111=37H知道,Y2即是“7”(由“3”的ASCII码是0110011=33H推得)
假如你能记住“0”的ASCII码是0110000=30H;“A”的ASCII码是1000001=41H,则解起来就更方便了。