第7章-差错控制原理

第7章-差错控制原理第一页，共29页。关于差错控制第二页，共29页。关于差错控制第三页，共29页。常用差错控制方式第四页，共29页。差错控制基本思想及方案差错控制编码的基本思想：在信息码元中加入一些冗余码元——监督码元，这些冗余码元不含任何通信信息，但是在编码过程中，用来监督信息码元，译码时利用特定的规律来鉴别传输是否发生错误，或者纠正错误，从而降低误码率。差错控制两种方案：

①发现错误——检错编码；

②纠正错误——纠错编码。

第五页，共29页。差错控制中常用名词（1）码字：由若干个码元组成，如。（2）码长：码字中码元的数目。（3）码组：多个码字构成的集合，如

{0000,0001,0010,0100,1000}。（4）码距：两个等长码字之间的对应位不同的个数，二进制的最小码距也称为汉明距离。（5）码重：码字中“1”码元的个数，用W表示，例如码字11001的码重W=3。第六页，共29页。编码一： 消息A----“0”；消息B----“1”； 最小码距=1；若传输中产生错码（“0”错成“1”或“1”错成“0”），收端无法发现，该编码无检错纠错能力。

编码二：

消息A----“00”；消息B----“11”（加了一位监督位）；最小码距=2；若传输中产生一位错码，则变成“01”或“10”，因“01”和“10”为禁用码组，收端译码时可以检测出该码有错，但无法确定错码位置，不能纠正。编码三： 消息A----“000”；消息B----“111”（增加两位监督位）； 最小码距=3；传输中产生一位或两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力；该编码具有纠正一位错码的能力。例如收到110，认为是111。（大数法则）第七页，共29页。分组码分组码：将k个信息码元划分为一组，然后由这k个码元按照一定的规则产生r个监督码元，从而构成长度n＝k＋r的码组的集合。分组码表示：（n，k）。最小码距：一个码组集合中，任何两个码组间汉明距离的最小值称为该集合的最小码距。记为d0。例:11101与10011之间的码距d=3。码组的最小距离越大，差错控制能力就越强。码组集合（000，001，010，011，100，101，110，111） d0=1码组集合（000，

011，101，110）

d0=2码组集合（000，111）

d0=3第八页，共29页。常用差错控制编码（1）奇偶校验码（2）恒比码（3）正反码（4）循环冗余校验码（5）卷积码第九页，共29页。原理：奇偶校验编码中，无论信息位有多少位，校验位只有一位。码组中“1”的个数为奇数或偶数。奇校验编码，要满足关系式：偶校验编码，要满足关系式：（1）奇偶校验校验位模2加第十页，共29页。恒比码中“1”的个数与“0”的个数保持不变。接收端译码时只需计算接收码组中“1”的个数，就可以知道传输过程中是否出现了错误。可以检测所有奇数个错误和部分偶数个错误。5中取3恒比码如表。优点：简单，实现容易。字符恒比码字符恒比码101011610101211001711100310110801110411010910011500111001101（2）恒比码第十一页，共29页。正反码监督码元取决于信息码组中“1”的数目，或者与信息码元相同（正码），或者与信息码元相反（反码）。以博多码为例，编码规则：信息码组中有奇数个“1”时，监督码与信息码相同；信息码有偶数个“1”时监督码是信息码的反码。例如，信息码为11001，有奇数个“1”，则监督码亦为11001，发送码组为1100111001；信息码为11101，有偶数个“1”，则监督码为信息码的反码00010，发送码组为1100100010。（3）正反码第十二页，共29页。译码规则：接收端将接收码组中的信息码与监督码模2加，得到一个5bit的合成码组，由其产生校验码组。接收码组中的信息码有奇数个“1”，合成码组就是校验码组；接收码组中的信息码有偶数个“1”，合成码组取反为校验码组。根据校验码组中“1”的数目按下表进行译码判决。类型校验码组形式译码判决1全“0”传输正确24个“1”，1个“0”校验码中“0”对应位置的1位信息码出错34个“0”，1个“1”校验码中“1”对应位置的1位监督码出错4其他大于1位的传输错误这种编码方式能纠正1位错误。第十三页，共29页。【例】

接收码组：0110101101、0101010111、0111010110，判断传输是否有错。

解：

1)接收码组0110101101，信息码中“1”个数为奇数（3个），合成码组为00000，校验码组亦为，符00000合表中第1种类型情况，传输正确。2)接收码组0101010111，信息码中“1”个数为偶数（2个），合成码组为11101，合成码组取反，得校验码组00010，符合表中第3种类型情况，第4个监督码位出错。3）接收码组0111010110，信息码中“1”个数为奇数（3个），合成码组为11000，校验码组亦为11000，符合表中第4种类型情况，传输产生了多位错误。

第十四页，共29页。（4）循环冗余码从数学的角度讲，所有的数都可以用多项式来表示，例如：125=1×102+2×101+5×100长度为n的码组可用一个x的n-1次多项式表示，码组中每位码的数值就是n-1次多项式中相应的系数值，这个对应多项式称为数据多项式。第十五页，共29页。CRC原理：将发送数据比特序列作为多项式T(x)的系数，选一k次幂生成多项式G(x)。用xk乘T(x)，得T(x)xk。然后用G(x)去除T(x)xk,得一个余数多项式R(x)。将余数多项式加到数据多项式T(x)之后，作为发送序列。收端用同一G(x)去除接收序列多项式Tˊ(x)xk，得计算余数多项式Rˊ(x)。若Rˊ(x)与R(x)相同，传输无错；否则传输有错。第十六页，共29页。校验过程：（发端）

a.T(x)乘以xk.意味着将T(x)对应的数据比特序列左移k位。

b.T(x)xk

除以G(x),

Q(x)－商，R(x)－余数多项式。

c.将T(x)xk+R(x)所对应的比特序列作为一个整体发送发送。第十七页，共29页。校验过程：（收端）d.对接收序列所对应的多项式Tˊ(x)xk

进行运算。

Rˊ(x)=R(x)，传输正确；

Rˊ(x)≠R(x),传输有错。实际的CRC校验码生成采用二进制模2算法得到。加法不进位，减法不借位，即异或操作。第十八页，共29页。例:a.

发送数据序列110011；b.

G(x)=x4+x3+1，k=4,对应的序列11001；c.

发送数据序列左移4位为1100110000；d.

做除法第十九页，共29页。e.

带有校验的发送序列

：

1100111001

发序列校验序列f.

校验，若没有发生差错，接收端收序列能被同一生成多项序列整除。第二十页，共29页。

1000011101）11001110011100111001110010第二十一页，共29页。（5）卷积码卷积码是一种非分组码，编码器产生的n个码元，不仅取决于这k位信息码元，而且还取决于前m－1个码组。编码器的输出可以看成是输入信息比特与编码器响应函数的卷积，故称为卷积码。卷积码构造简单，性能优越，主要应用于前向纠错（FEC）。第二十二页，共29页。（1）编码

卷积码符号(n,k,m)：n为码长，k为码组中信息位长度，m为相互关联的码组个数。信息位监督位(2,1,6)卷积码第二十三页，共29页。（2)卷积码的图解表示

1)树状图（2，1，3）卷积码m1，m2为移位寄存器，起始状态均为0，即b1b2b3为000。c1

＝b1＋b2＋b3c2＝b1＋b3

b111010000b3b20001111001100000c1c21101010010110000状态abdcb

caan为码长，k为码组中信息位长度，m为相互关联的码组个数。第二十四页，共29页。

2）网格图

网格图把树状图中相同的节点合并在一起，输入比特0，用实线表示；输入比特1，用虚线表示。支路上标注的码元为输出比特，自上而下4行节点分别表示a，b，c，d四种状态。

第二十五页，共29页。【例】（2，1，3）卷积码编码器，起始状态为a，输入比特序列为110100，求输出序列和状态变化路径。

解：由（2，1，3）卷积码网格图，找出编码时网格图中的路径，可得到输出序列和状态变化路径。