第7章-差错控制原理

1、第10章 差错控制原理信道编码，按一定的规则加入冗信道编码，按一定的规则加入冗余度。（信源编码是去掉信源的余度。（信源编码是去掉信源的冗余度。）冗余度。）关于差错控制关于差错控制tt信道干扰 d(t)f (t)f (t)d(t)模拟信号(a) 模拟系统干扰示意图tt信道干扰 d(t)f (t)f (t)d(t)数字信号(b) 数字系统干扰示意图OOOO关于差错控制关于差错控制 常用差错控制方式常用差错控制方式差错控制基本思想及方案差错控制基本思想及方案l差错控制编码的基本思想：差错控制编码的基本思想：在信息码元中加入在信息码元中加入一些冗余码元一些冗余码元监督码元，这些冗余码元不监督码元，这些

2、冗余码元不含任何通信信息，但是在编码过程中，用来监含任何通信信息，但是在编码过程中，用来监督信息码元，译码时利用特定的规律来鉴别传督信息码元，译码时利用特定的规律来鉴别传输是否发生错误，或者纠正错误，从而降低误输是否发生错误，或者纠正错误，从而降低误码率。码率。l差错控制两种方案：差错控制两种方案：发现错误发现错误检错编码；检错编码；纠正错误纠正错误纠错编码。纠错编码。 差错控制中常用名词差错控制中常用名词（1）码字码字：由若干个码元组成由若干个码元组成，如，如10001100。（2）码长码长：码字中码元的数目。码字中码元的数目。（3）码组码组：多个码字构成的集合，如：多个码字构成的集合，如

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

4、力。 编码二：编码二： 消息消息A-“00A-“00”；消息；消息B-“11B-“11”（加了一位监督位）；（加了一位监督位）；最小码距最小码距 = 2= 2；若传输中产生一位错码，则变成若传输中产生一位错码，则变成“0101”或或“1010”，因，因“0101”和和“1010”为禁用码组，为禁用码组，收端译码时可以检测出该码有错收端译码时可以检测出该码有错，但无法确定错码，但无法确定错码位置，不能纠正。位置，不能纠正。编码三：编码三：消息消息A-“000A-“000”；消息；消息B-“111B-“111”（增加两位监督位）；（增加两位监督位）；最小码距最小码距 = 3= 3；传输中产生一位或

5、两位错码，都将变成禁用码组，收端判决传输有错。传输中产生一位或两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力；该编码具有检出两位错码的能力；该编码具有纠正一位错码的能该编码具有纠正一位错码的能力。力。例如收到例如收到110110，认为是，认为是111111。（大数法则）。（大数法则）分组码分组码l分组码：将k个信息码元划分为一组，然后由这k个码元按照一定的规则产生r个监督码元，从而构成长度nkr的码组的集合。l分组码表示：（n，k）。l最小码距：一个码组集合中，任何两个码组间汉明距离的最小值称为该集合的最小码距。记为d0。例:11101与10011之间的码距d=3。

6、l码组的最小距离越大，差错控制能力就越强。l码组集合（000，001，010，011，100，101，110，111）d0=1l码组集合（000， 011，101，110）d0=2l码组集合（000，111）d0=3常用差错控制编码（1 1）奇偶校验码）奇偶校验码（2 2）恒比码）恒比码（3 3）正反码）正反码（4 4）循环冗余校验码）循环冗余校验码（5 5）卷积码）卷积码原理原理：奇偶校验编码中，无论信息位有多少位，奇偶校验编码中，无论信息位有多少位， 校验位只有一位。校验位只有一位。码组中码组中“1”的个数为奇的个数为奇 数或偶数。数或偶数。奇校验编码，要满足关系式：奇校验编码，要满足关系

7、式：偶校验编码，要满足关系式：偶校验编码，要满足关系式：1021aaann0021aaann（1）奇偶校验校验位模2加l恒比码中“1”的个数与“0”的个数保持不变。l接收端译码时只需计算接收码组中接收端译码时只需计算接收码组中“1”的个数，的个数，就可以知就可以知道传输过程中是否出现了错误。道传输过程中是否出现了错误。l可以可以检测所有奇数个错误和部分偶数个错误。检测所有奇数个错误和部分偶数个错误。l5中取3恒比码如表。l优点：简单，实现容易。字符字符恒比码恒比码字符字符恒比码恒比码10101161010121100171110031011080111041101091001150011100

8、1101（2）恒比码l正反码监督码元取决于信息码组中正反码监督码元取决于信息码组中“1”的数目的数目，或或者与信息码元相同（正码），者与信息码元相同（正码），或者与信息码元相反或者与信息码元相反（反码）。（反码）。l以以博多码博多码为例，为例，编码规则：编码规则：信息码组中有奇数个信息码组中有奇数个“1”时，监督码与信息码相同；信息码有偶数个时，监督码与信息码相同；信息码有偶数个“1”时监督码是信息码的反码。时监督码是信息码的反码。l例如，信息码为例如，信息码为11001，有奇数个，有奇数个“1”，则监督码亦为，则监督码亦为11001，发送码组为，发送码组为1100111001；信息码为；信息

9、码为11101，有偶数，有偶数个个“1”，则监督码为信息码的反码，则监督码为信息码的反码00010，发送码组为，发送码组为1100100010。（3）正反码l译码规则：译码规则：接收端将接收码组中的信息码与监督码接收端将接收码组中的信息码与监督码模模2 2加，得到一个加，得到一个5 5bitbit的合成码组，由其产生校验的合成码组，由其产生校验码组。码组。l接收码组中的信息码有奇数个接收码组中的信息码有奇数个“1”1”，合成码组就是校验，合成码组就是校验码组；接收码组中的信息码有偶数个码组；接收码组中的信息码有偶数个“1”1”，合成码组取，合成码组取反为校验码组。根据校验码组中反为校验码组。根

10、据校验码组中“1”1”的数目按下表进行的数目按下表进行译码判决。译码判决。类型类型校验码组形式校验码组形式译码判决译码判决1全全“0”传输正确传输正确24个个“1”，1个个“0”校验码中校验码中“0”对应位置的对应位置的1位信息码出错位信息码出错34个个“0”，1个个“1”校验码中校验码中“1”对应位置的对应位置的1位监督码出错位监督码出错4其他其他大于大于1位的传输错误位的传输错误这种编码方式能纠正这种编码方式能纠正1位错误。位错误。【例例】 接收码组：接收码组：0110101101、0101010111、0111010110，判断传输是否有错。，判断传输是否有错。 解：解： 1)1) 接收

11、码组接收码组01101011010110101101，信息码中，信息码中“1”1”个数为奇数（个数为奇数（3 3个），个），合成码组为合成码组为0000000000，校验码组亦为，符，校验码组亦为，符0000000000合表中第合表中第1 1种类种类型情况，传输正确。型情况，传输正确。2)2) 接收码组接收码组01010010101011110111，信息码中，信息码中“1”1”个数为偶数（个数为偶数（2 2个），个），合成码组为合成码组为1110111101，合成码组取反，得校验码组，合成码组取反，得校验码组0001000010，符，符合表中第合表中第3 3种类型情况，第种类型情况，第4 4

12、个监督码位出错。个监督码位出错。 3 3）接收码组）接收码组01110101100111010110，信息码中，信息码中“1”1”个数为奇数（个数为奇数（3 3个），个），合成码组为合成码组为1100011000，校验码组亦为，校验码组亦为1100011000，符合表中第，符合表中第4 4种类种类型情况，传输产生了多位错误。型情况，传输产生了多位错误。 （4）循环冗余码）循环冗余码l从数学的角度讲，所有的数都可以用多项式来表从数学的角度讲，所有的数都可以用多项式来表示，例如：示，例如： 125=1125=110102 2 + 2+ 210101 1 + 5+ 510100 0长度为长度为n n

13、的码组可用一个的码组可用一个x x的的n-1n-1次多项式表示，码组次多项式表示，码组中每位码的数值就是中每位码的数值就是n-1n-1次次多项式中相应的系数值，多项式中相应的系数值，这个对应多项式称为这个对应多项式称为数据数据多项式多项式。CRC原理：原理：l将将发送数据比特序列作为多项式发送数据比特序列作为多项式T T( (x x) )的系数，的系数，选选一一k k次幂生成多项式次幂生成多项式G G( (x x) )。l用用x xk k乘乘T T( (x x) )，得得T T( (x x) )x x k k。l然后用然后用G G( (x x) )去除去除T T( (x x) )x x k k

14、 , ,得一个余数多项式得一个余数多项式R R( (x x) )。l将余数多项式加到数据多项式将余数多项式加到数据多项式T T( (x x) )之后，作为发之后，作为发送序列。送序列。l收端用同一收端用同一G G( (x x) )去除接收序列多项式去除接收序列多项式T T(x x) )x xk k ，得计算余数多项式得计算余数多项式R R(x x) )。l若若R R(x x) )与与R R( (x x) )相同，传输无错；否则传输有错。相同，传输无错；否则传输有错。l校验过程校验过程：（：（发端）发端） a. T(xa. T(x) )乘以乘以x xk k . . 意味着将意味着将T(x)T(x

15、)对应的数据比特序对应的数据比特序列左移列左移k k位。位。 b. T(x)xb. T(x)xk k 除以除以G(x),G(x), Q(xQ(x) )商，商，R(x)R(x)余数多项式。余数多项式。 c. c. 将将T(x)xT(x)xk k + R(x) + R(x)所对应的比特序列作为一个整所对应的比特序列作为一个整体发送发送。体发送发送。)()()()()(xGxRxQxGxxTkl校验过程校验过程：（：（收端收端）d. d. 对接收序列所对应的多项式对接收序列所对应的多项式T(x)xT(x)xk k 进行运算。进行运算。R(x)= R(xR(x)= R(x) )，传输正确；，传输正确；

16、R(x)R(xR(x)R(x), ), 传输有错。传输有错。)()( )()()( xGxRxQxGxxTk实际的实际的CRCCRC校验码生成采用二进制模校验码生成采用二进制模2 2算法得算法得到。加法不进位，减法不借位，即异或操作。到。加法不进位，减法不借位，即异或操作。例例:a. 发送数据序列发送数据序列 110011；b. G(x)=x4+x3+1，k=4, 对应的序列对应的序列 11001；c. 发送数据序列左移发送数据序列左移4位为位为 1100110000；d. 做除法做除法 e. 带有校验的发送序列带有校验的发送序列 ： 110011 1001 发序列发序列 校验序列校验序列f.

17、 校验校验 ，若没有发生差错，接收端收序列能被同一生，若没有发生差错，接收端收序列能被同一生成多项序列整除。成多项序列整除。l l 1 0 0 0 0 1l 1 1 0 1）1 1 0 0 1 1 1 0 0 1l 1 1 0 0 1l 1 1 0 0 1l 1 1 0 0 1l 0（5 5）卷积码）卷积码（1）编码）编码卷积码卷积码符号符号(n,k,m(n,k,m) )：n n为码长为码长，k k为码组中信息位长为码组中信息位长度，度，m m为相互关联的码组个数为相互关联的码组个数。信息位监督位(2,1,6)卷积码卷积码（2) 卷积码的图解表示卷积码的图解表示1) 1) 树状图树状图（2，1

18、，3）卷积码）卷积码m m1 1，m m2 2为移位寄存器，起始状为移位寄存器，起始状态均为态均为0 0，即，即b b1 1b b2 2b b3 3为为000000。 c1 b1b2 b3 c2 b1b3 b111010000b3b20001111001100000 c1c2 11 01 01 00 10 11 00 00状态状态 a b d c b c a an为码长，k为码组中信息位长度，m为相互关联的码组个数。 2 2） 网格图网格图 l网格图把树状图中相同的节点合并在一起，输入比特输入比特0，用实线表示；用实线表示；输入比特1，用虚线表示。支路上标注的码元为输出比特，自上而下4行节点分别表示a，b，c，d四种状态。 【例【例】（2，1，3）卷积码编码器，起始状态为）卷积码编码器，起始状态为a，输入比特，输入比特序列为序列为110100，求输出序列和状态变化路径。，求输出序列和状态变化路径。 l解：由（解：由（2 2，1 1，3 3）卷积码网格图，找出编码时网格图中）卷积码网格图，找出编码时网格图中的路径，可得到输出序列和状态变化路径。的路径，可得到输出序列和状态变化路径。 （3）译码）译码 l方法：方法：代数解码和概率解码。代数解码和