简单的差错控制编码
简单的差错控简单的差错控简单的差错控简单的差错控制编码制编码制编码制编码数字通信技术数字通信技术 简单的差错控制编码简单的差错控制编码1.1 奇偶监督码奇偶监督码 奇偶监督码是一种最简单的检错码,又称奇偶校验码,在计算机数据传输中得到了广泛的应用。在ISO和CCITT提出的七单位国际5层字母表、美国信息交换码ASCII字母表及我国的七单位字符编码标准中都采用7比特码组表示128种字符,如字符A的编码表示为1000001。一般情况下奇偶监督码的编码规则是:首先将要传输的信息分成组,然后将各位二元信息及附加监督位用模2和相加,选择正确的监督位,保证模2和的结果为0(偶校验)或1(奇校验)。这种监督关系可以用公式表示。设码组长度为n,表示为(an-1 an-2 an-3 a0),其中前n-1位(an-2 an-3 a0)为信息,第n位(an-1)为校验位,则偶校验时有:监督码元a0即为 (7-4)奇校验时有 监督码元a0为 (7-5)这种奇偶校验只能发现单个或奇数个错误,而不能检测出偶数个错误,因而它的检错能力不高,但这并不表明它对随机奇数个错误的检错率和偶数个错误的漏检率相同。对于随机差错,出现错一位码的概率比错两位码的概率大得多、错三位码的概率比错四位码的概率大得多,因此绝大多数随机差错都能用简单奇偶校验查出,这正是这种方法被广泛用于以随机错误为主的计算机通信系统的原因,但这种方法难于对付突发差错,所以在突发错误很多的信道中不能单独使用。奇偶校验码码组间最小距离dmin2。证明(以偶校验为例):因为 an-1an-2a1a00 所以当码组中任一位aj发生错误时:an-1an-2/aja1a01 至少可检出一位误码,故dmin大于或等于2。当有两位ai,aj发生误码时 an-1an-2/ai/aja1a00 所以不能检出两位误码,故小于或等于2。综上,dmin2。1.2 水平奇偶监督码水平奇偶监督码 针对上述奇偶监督码检错能力不高,特别是不能检测突发错误的缺点,可以将经过奇偶监督编码的码元序列按行排列成方阵,每行为一组奇偶监督码(如表7-1所示),但发送时则按列的顺序传输:1110111001100000101000001101011110101100000110110110101,接收端仍然将码元排成发送时的方阵形式,然后按行进行奇偶校验。由于按行进行奇偶校验,因此称其为水平奇偶监督码或行奇偶监督码。信息码元监督码元1110011000111010011010100001110110001000010011001110111表7-1 奇偶监督码 可以看出,由于发端是按列发送码元而不是按码组发送码元,因此把本来可能集中发生在某一个码组的突发错误分散在了方阵的各个码组中,因此可得到整个方阵的行监督。这样,采用这种方法可以发现某一行上所有奇数个错误以及所有长度不大于方阵中行数的突发错误。在未增加监督位的条件下,检错能力为原来的m倍,这是香农信道编码定理应用的一个例子。比如,上式我们假想1110111001100000101000001101011110101100000110110110101这个序列的第6-10位出错。那么当按照行分组,按列发送时,则连续突发错误被分散到不同的行当中,见表7-2斜体处,(本为11001的错误后变成00110。)信息码元监督码元1010011000110010011010110001110110101000010010001110111表7-2 奇偶监督码 由上表可以看出。突发连续错误被分散到每行,当收端按行监督检验时,则可检测出有错。然而,由于该编解码在检错过程中需要对所有数据进行重组,所以需要的缓存空间较大,并且在数据的处理方面延时增大。这也时可靠性和有效性矛盾的一个表现。1.3 水平垂直奇偶监督码水平垂直奇偶监督码 水平垂直奇偶监督码是将水平奇偶监督码推广到二维奇偶监督码,又称为行列监督码和方阵码,是在水平奇偶监督码的基础上增加列的奇偶效验,可得到如表7-3的方阵,发送时按列序顺次传输。信息码元监督码元1110011000111010011010100001110110001000010011001110111监督码元01101100011表7-3水平垂直奇偶监督码 显然,这种码比水平奇偶监督码有更强的检错能力,它能发现任一行和任一列的所有奇数个错误,及长度不大于行数(按列发)或不大于列数(按行发)的突发错误;这种码还有可能检测出偶数个错码,因为如果每行的监督位不能在本行检出偶数个错误时,则在列的方向上有可能检出。当然,在偶数个错误恰好分布在矩型的四个顶点上时,这样的偶数个错误是检测不出来的。此外,这种码还可以纠正一些错误,例如当某行某列均不满足监督关系而判定该行该列交叉位置的码元有错。从而纠正这一位上的错误。这种码由于检错能力强,又具有一定的纠错能力,且实现容易因而得到广泛的应用。谢谢观看!谢谢观看!谢谢观看!谢谢观看!数字通信技术数字通信技术