Work 版 (精华区)
发信人: goodday (我要灌水), 信区: Work
标 题: Re： intel 北京笔试题-纠错编码方式简介
发信站: 哈工大紫丁香 (2002年11月21日10:33:43 星期四), 转信
2.1 奇偶监督码
奇偶校验码也称奇偶监督码，它是一种最简单的线性分组检错编码方式。其方法是首先
把信 源编码后的信息数据流分成等长码组 ，在每一信息码组之后加入一位(1比特)监督码
元作为 奇偶检验位，使得总码长n(包括信息位k和监督位1)中的码重为偶数(称为偶校验码
)或为奇 数 (称为奇校验码)。如果在传输过程中任何一个码组发生一位(或奇数位)错误，
则收到的 码组必然不再符合奇偶校验的规律，因此可以发现误码。奇校验和偶校验两者具
有完全相 同的工作原理和检错能力，原则上采用任一种都是可以的。
由于每两个1的模2相加为0，故利用模2加法可以判断一个码组中码重是奇数或是偶数。
模2 加法等同于“异或”运算。现以偶监督为例。
对于偶校验，应满足
故监督位码元a0可由下式求出：
(2－2)
不难理解，这种奇偶校验编码只能检出单个或奇数个误码，而无法检知偶数个误码，对
于连续多位的突发性误码也不能检知，故检错能力有限，另外，该编码后码组的最小码距
为 =2，故没有纠错码能力。
奇偶监督码常用于反馈纠错法。
2.2 行列监督码
行列监督码是二维的奇偶监督码，又称为矩阵码，这种码可以克服奇偶监督码不能发现
偶数 个差错的缺点，并且是一种用以纠正突发差错的简单纠正编码。
其基本原理与简单的奇偶监督码相似，不同的是每个码元要受到纵和横的两次监督。具
体编 码方法如下：将若干个所要传送的码组编成一个矩阵，矩阵中每一行为一码组，每行
的最后 加上 一个监督码元，进行奇偶监督，矩阵中的每一列则由不同码组相同位置的码
元组成，在每列 最后也加上一个监督码元，进行奇偶监督。如果用×表示信息位，用表
示监督位，由矩阵 码 的结构可如图6－5所示，这样，它的一致监督关系按行及列组成 。
每一行每一列都是一个 奇偶 监督码，当某一行(或某一列)出现偶数个差错时，该行(或该
列)虽不能发现，但只要差错所 在的列(或行)，没有同时出现偶数个差错，则这种差错仍
然可以被发现。矩阵码不能发现 的差错只有这样一类：差错数正好为4倍数，而且差错位
置正好构成矩形的四个角，如图6－ 5中所示有的差错情况。因此，矩阵码发现错码的能力
是十分强的，它的 编码效率当然比奇偶监督码要低。
2.3 恒比码
恒比码又称为定比码。在恒比码中，每个码组“1”和“0”都保持固定的比例，故得此
名。 这种码在检测时，只要计算接收到的码组中“1”的数目是否对就知道有无错误。
在我国用电传机传输汉字时，只使用阿拉伯数字代表汉字。这时采用的所谓“保护电码”
就 是“3∶2”或称“5中取3”的恒比码，即每个码组的长度为5，其中“1”的个数总是3
，而 “0”的个数总是2。如表6－2所示。
表 6－2 数字字符 普通的五单位码 恒比码
1
2
3
4
5 11101
11001
10000
01010
00001 01011
11001
10110
11010
00111
6
7
8
9
0 10101
11100
01100
00011
01101 10101
11100
01110
10011
01101
本来以5位码元组成的码组总共可以有25=32种，而恒比码规定只有确切地含有3个“1
”， 2个“0”的那些码组为准用码组，而有3个“1”，2个“0”的5位码组共有多少?这是
“5中 取3”求组合的算法，组合数为，一般情况下， 从“n中取m”(m＜n)恒比码的码组
数为：
由此可以看出，恒比码实际上是n个码元传送比特信息，例如上述“3∶2”即 “5中取2
”恒比码，用5位码只传10种信息。每个码组的信息量为，有5-3.3=1.7bit作为代价付出。
恒比码适用于传输字母和符号。
2.4 汉明码
汉明码属于线性分组编码方式，大多数分组码属于线性编码，其基本原理是，使信息码
元与 监督码元通过线性方程式联系起来。线性码建立在代数学群论的基础上，各许用码组
的集合 构成代数学中的群，故又称为群码。
(1)校验子和监督关系式
我们先回顾一下按式(2－2)条件构成的偶数监督码。由于我们使用了一位监督码C0，它
就 能和信息码一起构成一个代数式，在接收端解码时，我们实际上是在计算 ，
若S=0，就认为无错码。若S=1，就认为有错码。上式就是一致监督关系式。S称为“校
验子 ”。由于校验子S的取值只有这样两种，它就只能代表有错和无错两种信息，而不能
指出错 码的位置。我们不难推想，如监督位增加一位，变成两位，则能增加一个类似于式
(2－3)的 监督关系式。两个校验子的可能值有4种组合00，01，10，11。故能表示4种不同
的信息，其 中一种表示无错，其余三种就有可能用来指示一位错码的3种不同位置。同理
，r个监督关系 式能指示一位错码的()个可能位置。
一般说来，若码长为n，信息码为k，则监督码数r=n-k。若希望用r个监督码构造出r个
监督 关系式来指示一位错码的n种可能位置，则要求：
下面通过一个例子来说明如何具体构造这些监督关系式。
设分组码(n、k)中k=4，为了能纠正一位错码，按式(2－4)可知，要求监督码数r≥3，现取
r =3，则n=k+r=4+3=7，这是一种(7、4)分组码。我们用表示这7个码 元，，表示三个监督
关系式中的校验子，则的值与错码位置 的对应关系可以规定如表6－3，(当然也可以规定
成另一种对应关系，这不影响讨论一般性 )。
按表6－3的规定，仅当有一个错码位置在时，校验子S1为1 ，否则S1为0，这就意味着
四个码元构成偶数监督关系：
错码位置 错码位置
001 101
010 110
100 111
011 000 无错码
同理，构成偶数监督关系：
以及构成偶数监督关系：
(2)监督码的确定
在发送端编码时，信息码的值决定于输入信号，是随机的。而监督 码则应根据信息码
的取值按监督关系式决定。即监督码的取值应使上三式 中的值为0，表示编成的码组中无
错码：
由上式移项解出监督码：(在模2加法中，移项后没有负号)
已知信息码后，直接按上式可算出监督码，计算结果得出16个码组列于表6－4中。
信息码 监督码 信息码 监督码
0000 000 1000 111
0001 011 1001 100
0010 101 1010 010
0011 110 1011 001
0100 110 1100 001
0101 101 1101 010
0110 011 1110 100
0111 000 1111 111
(3)解码过程
接收端收到每个码组后，按下述顺序解码。先按式(2-4)～(2－6)计算出再按表6－3判
断错误情况。例如，若接收码组为0000011，按式(2－4)～(2－6)计算得： ， 由于，
查表6－3可知有一错码为a3。 (4)汉明码的效率 汉明码的编码效率 η=1-r/n 当
n很大时，效率是很高的。
2.5 循环码(CRC)
(1)循环码是一种重要的线性码，它有三个主要数学特征：
①循环码具有循环性，即循环码中任一码组循环一位(将最右端的码移至左端)以后，仍
为 该码中的一个码组。
②循环码组中任两个码组之和(模2)必定为该码组集合中的一个码组。
③循环码每个码组中，各码元之间还存在一个循环依赖关系，b代表码元，则有
(2)用多项式码作为检验码的编解码过程
用多项式码作为检验码时，发送器和接收器必须具有相同的生成多项式(Generator Pol
ynom ial)G(x)，其最高、最低项系数必须为1。CRC编码过程是将要发送的二进制序列看作
是多项 式的系数，除以生成多项式，然后把余数挂在原多项式之后。CRC译码过程是接收
方用同一 生成多项式除以接收到的CRC编码，若余数为零，则传输无错。
编码译码方法：
①令r为生成多项式G(x)的阶，将r个“0”附加在信息(数据)元的低端，使其长度变为k
+r 位，相应于多项式；
②，得余数；
③与余数对应位异或，得编码信息T(x)。
例 数据信息
数据信息 1101011011 M(X)
生成式 10011 G(X),R=4
加4个“0”之后 11010110110000
/G(X) 1110 余数
待发送的编码 11010110111110 T(X)
④接收器收到发来的编码信息后，用同一个生成多项式G(x)除以编码信息，若余数为零，
则表示接收到正确的编码信息，否则有错。
⑤把收到的正确编码信息T(x)去掉尾部r位，即得数据信息M(x)。
(3)多项式码检错能力及生成多项式G(x)的选择原则
设接收到的信息不是发送的编码信息T(x)，而是T(x)+E(x)。
例 有差错的编码信息为
1001001011 T(x)-E(x)=T(x)+E(x)
其中，1101011011 为T(x)
0100010000 为E(x)
若接收到的有差错的编码信息为T(x)+E(x)，用G(x)除以T(x)+E(x)，则得余数为E(x)/G
(x) 的余数，因为T(x)/G(x)余数为零，所以
［T(x)+E(x)］/G(x)E(x)/G(x)
这时应该有余数，若无余数则检不出错。
有r位校验位的多项式码将能检测所有≤r位的突发错，故只要k-1＜r，就能检测出所有
突发 错，这是一个很有用的结论。
生成多项式G(x)的国际标准有：
CRC－12
CRC－16
CRC－CCITT
CRC－16和CRC－CCITT两种生成多项式生成的CRC码可以捕捉一位错、二位错、具有奇数个
错 的全部错误，可以捕捉突发错长度小于16的全部错误、长度为17的突发错的9999 8%
、长度为18以上的突发错的99997%。CRC－16和CRC－CCITT可以用硬件实现。
(4)CRC编码硬件电路的实现
设 数据1010
多项式
生成多项式系数1011
多项式
系数1010000
多项式
余式系数011
多项式k(X)=X+1
CRC编码
1010 001
信息 监督
信息组从高位端输入的CRC编码电路，如图6－6所示，其工作原理是：首先门1关闭，门2开
通，依次输入的信息元1010一面经或门H直接输出，同时送往除法电路进行除法运算。4次
移 位后除法电路完成了运算，得余式系数为“011”，即为监督元。第5个移位脉冲开始门
1 开通，门2关闭，断开了反馈，移位3次把移位寄存器中的3位余项作为监督元附在信息元
后 面，发出的码字就是1010011，最后门1关闭，门2开通，对下一信息组再行编码。有关
工作 过程见表6－5
表6－5 图6－6所示电路的工作过程
移动脉冲 输入 输出 注
(初始状态) 000 } 门1关闭
1 1 011 门2打开
2 0 110
3 1 100 } 门1打开
4 0 011
5 0 110 门2关闭
6 0 100
7 0 000
2.6 RS码(Reed－Solomon－里德－索罗门码)
RS码是一种重要的线性分组编码方式。它对突发性错误有较强的纠错能力，被DVB标准
采用 。
(1)在RS编码过程中，各符号不是直接出现，而是每个符号要乘以某个基本元素的幂次
方后 再模2加，如图6－7所示。
(2)在循环码中欲检查是否有错是用码字除一个多项式，而在RS码中，欲检 出一系列误码
则需要用码字除一定数量的一次多项式。如果要纠正七个错误，那么码字必须 被2t个不同
的一次多项式整除，例如被x+an的一次多项式整除，这里的n取值直到2t的所 有整数值
，a是基本元素，例如a为010，输入5个符号，每个符号3比特，与相应的元素相乘 后直接
模2加输出，因为有两种系数，所以得到二个校检子，两个校验式为：
(3)下面举一个简单例子说明纠错过程在无差错时，S0=0，S1=0，有如下关系：
码字 A 101 式中
B 100
C 010
D 100
E 111
P 100
Q 100
= 000
当接收到的符号有错时通过计算也可以得到与符号有关的错误图形，这时有错的 码加撇，
是错误图形，真正的D=D′+=101+001=100。但错误的位置将由S1决定 ，这要利用的关系
。
A 101
B 100
C 010
D 101
E 111
P 100
Q 100
= 001
校验子的增加导致纠错能力的加强，通过的运算可以确定差错 的位子，并予以纠正。
尽管都是同一个错误的不同图形，但因次方的各接收符号模2加得 到的，而的k恰好是乘的
那一个符号。
(4)RS码的生成多项式
从上面的例子可以看出，为了纠正一个符号错，要2个符号的检测码，一个用来确定位
置， 一个用来纠错。一般来说纠t个错误需要2t个检验符，这时要计算2t个等式，确定t个
位置和 纠t个错。能纠t个符号的RS码生成多项式为
按照DVB的CATV标准
RS码生成多项式为：
RS码为： RS(204，188，8)
即分组码符号长度为204个，188个信息符号，可纠错8个。
2.7 连环码(卷积码)
连环码是一种非分组码，通常它更适用于前向纠错法，因为其性能对于许多实际情
况常优于 分组码，而且设备简单。 这种连环码在它的信码元中也有插入的监督码元但并
不实行分组监督，每一个监督码元都要 对前后的信息单元起监督作用，整个编解码过程也
是一环扣一环，连锁地进行下去。这种码 提出至今还不到三十年，但是近十余年的发展表
明，连环码的纠错能力不亚于甚至优于分组 码。这一小节只介绍一种最简单的连环码，以
便了解连环码的基本概念。 图6－8是连环码的一种最简单的编码器。它由两个移位寄存
器，一个模2加法器及一个电 子开关组成。工作过程是：移位寄存器按信息码的速度工作
，输入一位信息码，电子开关倒 换一次，即前半拍接通a端，后半拍接通b端。因此，若输
入信息为，则 输出连环码为…，其中“b”为监督码元。按图6－8 结构可得：
}模2
可见，这个连环码的结构是：“信息码元某、监督码元、信息码元、监督码元…。”一个
信息 码与一个监督码组成一组，但每组中的监督码除了与本组信息码有关外，还跟上一组
的信息 码有关，或者用另一种说法，每个信息码除有本组监督码外，还有下一组的监督码
与它有关 系。因此，这种编码就像一根链条，一环扣一环，连环码即由此得名。 在解
码过程中，首先将接收到的信息码与监督码分离。由接收到的信息码再生监督码，这个 过
程与编码器相同，再将此再生监督码与接收到的监督码比较，判断有无差错。分布在相 邻
的三组码内可纠正一位差错。
2.8 交织法
交织法的原理见图6－9。在发送端，编码序列在送入信道传输之前先通过一个“交织寄
存器矩阵。”将输入序列逐行(即按的次 序)存入寄存器矩阵，存满以后，按列的次序(即
)取出 ，再送入传输信道。接收端收到后先将序列存到一个与发端相同的交织寄存器矩阵
，但按 列的次序存入，存满以后，按行的次序取出然后送进解码器。由于收发端存取的程
序正好相 反，因此，送进解码器的序列与编码器输出的序列次序完全相同，解码器丝毫感
觉不出交织 矩阵的存在与否。
假设交织矩阵每行的寄存器数目N正好等于分组码的码长，传输过程中产生的成群差错长度
，亦正好等于交织矩阵每列寄存器的数目M。图6－10表明，由于交织措施，送入解码器的
差错被分解开了，每组只分配到一个。因此，如果所采用的分组码能纠正一差错；那么长
度 为M的成群差错就可全部纠正，可见，交织法结合纠正离散差错的简单编码就可完成纠
正群 差错的任务。
�
� 在 yixueren ( 伊豆*不再*逃避) 的大作中提到: 】: 呵呵！~: 又有人要临阵磨枪了！~
: 祝福！~
: 【 在 ape (Never never never never give up.) 的大作中提到: 】
: : 发信人: darcy (野雀安无巢,游子为谁骄), 信区: Career
: : 标 题: Intel笔试主要内容
: : 发信站: BBS 水木清华站 (Mon Dec 3 13:02:33 2001)
: : 考的题目大致上是这样的：
: : CS考题：大约三四题涉及体系结构，诸如pipeline，缓存的hit-ratio之类
: : 考了一些C/C++的知识
--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.19]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：4.812毫秒