设信息位是8位，用海明码来发现并纠正1位出错的情况，则校验位的位数至少为( )。..

第3题

知识点：海明码

关键词：海明码校验位

设信息位是8位，用海明码来发现并纠正1位出错的情况，则校验位的位数至少为( )。

A. 1

B. 2

C. 4

D. 8

海明码

海明码用于多位并行数据检错纠错处理。

实现：为k个数据位设r个校验位，使k+r位的码字（即海明码）能发现k位中任何一位出错且可以纠正。

其数据位k和校验位r必须满足如下关系式：

2^r≥k+r+I

1）海明码的编码规则

设r个校验位P_rP_r_-1…P₁,k个数据位D_k_-1D_k_-2…D₀，产生的海明码为H_r₊_k,H_r₊_k_-1…H₁，则有如下规则。

规则1：Pi在海明码的2ⁱ-1位置，即H_j=P_i,j=2ⁱ-l；数据位则依序从低至高占据海明码中其他的位置。

规则2：海明码中的任意位都是由若干校验位来校验的。其对应关系是：被校验的海明位的下标等于所有参与校验该位的校验位的下标之和，而校验位则是由其自身来校验的。

2）海明码校验

下面以k=8对纠1位错的海明码的编码及校验原理给予说明。

（1）确定r的位数。

当r=4时，有2⁴≥8+4+1，可以满足2^r≥k+r+1。

（2）确定海明码的位置。

由规则1，P_i对应H_j的位置。

如：确定P₄的位置，因j=2^i-1=2^4-1=8，则有P₄在H₈的位置。同理得到以下位置的对应关系：

H₁₂H₁₁H₁₀H₉H₈H₇H₆H₅H₄H₃H₂H₁

D₇D₆D₅D₄P₄D₃D₂D₁P₃D₀P₂P₁

（3）确定编码方案。

由规则2，编码方案如下：

形成H_i与P₁相关的数据位有：S₁=D₀十D₁十D₃十D₄十D₆。

形成H_i与P₂相关的数据位有：S₂=D₀十D₂十D₃十D₅十D₆。

形成H_i与P₃相关的数据位有：S₃=D₁十D₂十D₃十D₇。

形成H_i与P₄相关的数据位有：D₇十D₆十D₅十D₄。

得校验关系：S₄=D₄十D₅十D₆十D₇。

（4）确定纠错译码方案。

设G₁=S₁十P₁；G₂=S₂十P₂；G₃=S₃十P₃；G₄=S₄十P₄。若采用偶校验则G₄~G₁的值全为0时数据正确，反之有错。用对出错位取反的方法即可实现纠错。

例如，G₄~G₁=0111，其值为7，对应于H₇（D₃的位置）。将D₃的值取反就实现了纠错。

题号导航 2023年上半年数据库系统工程师上午试卷综合知识