网校程序员辅导专题授课—计算机系统知识
内容简介:
1、 问:T循环冗余取决于K和R值,请问R值是怎么选择的?
T答:R值就是生成多项式的阶数,也就是生成多项式的次,比如生成多项式为:G(X)=T XP4P+XP3P+X+1 ,则R=4。
2、问:CRC求余方法和数学除法相同?x4-(X4+X3+X+1)=X3+X+1?有没有负数?
T答:TCRC求余方法和通常的数学除法不同,这里采用是的模2除法,即即以2为模,加减时不进位,不借位,和逻辑异或运算一致。那么x4-(X4+X3+X+1)=X3+X+1,照此规则就不会产生负数。(注意:前面表示的x4其实应是x的4次方,其它同理)
3、问:讲一讲海明码的奇校验和偶校验。
T答:对于海明码,我们了解下面这些就足够了TT。T要能纠正信息字中的单个错误,所需的最小距离为3。实现这种纠正的方法之一是海明码。海明码是一种多重(复式)奇偶检错系统。它将信息用逻辑形式编码,以便能够检错和纠错。用在海明码中的全部传输码字是由原来的信息和附加的奇偶校验位组成的。每一个这种奇偶位被编在传输码字的特定位置上。实现得合适时,这个系统对于错误的数位无论是原有信息位中的,还是附加校验位中的都能把它分离出来。 推求海明码时的一项基本考虑是确定所需最少的校验位数k。考虑长度为m位的信息,若附加了k个校验位,则所发送的总长度为m+k。满足条件:2PkP-1≥m+k 。从理论上讲,校验位可放在任何位置,但习惯上校验位被安排在1、2、4、8、…的位置上。图1列出了m=4,k=3时,信息位和校验位的分布情况。
码字位置
BB1B
BB2B
BB3B
BB4B
BB5B
BB6B
BB7B
校验位
x
x
x
信息位
x
x
x
x
复合码字
PB1B
PB2B
DB1B
PB3B
DB2B
DB3B
DB4B
图1 海明码中校验位和信息位的定位
海明码的码距应该是3,所以能纠正1位出错。而奇偶校验码的码距才是2,只能发现1位出错,但不能纠正(不知道那一位错)。无校验的码距是1,它出任何一位出错后还是合法代码,所以也就无法发现出错。
这是关于海明码的经典说法,即码距为3,可以发现2位,或者纠正1位错。应满足2PkP-1≥m+k。
海明码的校验位PBiB(i=1,2,3,…)在海明码的第2Pi-1P位置,数据位则依序从低到高占据汉明码中剩下的位置。我们来看看数据位与校验位在汉明码中的位置:
HB14B HB13B HB12B HB11B HB10B HB9B HB8B HB7B HB6B HB5B HB4B HB3B HB2B HB1B
DB9B DB8B DB7B DB6B DB5B DB4B PB4B DB3B DB2B DB1B PB3B DB0B PB2B PB1B
0条评论