1、第三章第三章 差错控制差错控制 本章首先讨论差错控制的基本概念及原本章首先讨论差错控制的基本概念及原理，介绍简单的差错控制协议，然后详细介绍理，介绍简单的差错控制协议，然后详细介绍几种简单的差错控制编码、汉明码、循环码，几种简单的差错控制编码、汉明码、循环码，并具体分析了线性分组码的一般特性，最后探并具体分析了线性分组码的一般特性，最后探讨了卷积码的相关内容。讨了卷积码的相关内容。3.1 差错控制的基本概念及原理差错控制的基本概念及原理3.1.1 3.1.1 差错控制的基本概念差错控制的基本概念1.差错分类差错分类:随机差错、突发差错随机差错、突发差错 随机差错又称独立差错，它是指那些独立地、
2、随机差错又称独立差错，它是指那些独立地、稀疏地和互不相关地发生的差错。稀疏地和互不相关地发生的差错。突发差错是指一串串，甚至是成片出现的差错，突发差错是指一串串，甚至是成片出现的差错，差错之间有相关性，差错出现是密集的。差错之间有相关性，差错出现是密集的。例：数据序列例：数据序列 1 0 1 1 0 0 0 1 1 1 0 1 这一串为突发差错（中间可能有不错的码）这一串为突发差错（中间可能有不错的码）例例1发送数据序列：发送数据序列：1 0 0 1 0 1 1 1 0 0 1接收数据序列：接收数据序列：1 1 1 1 1 0 0 1 1 1 0差错序列：差错序列：0 1 1 0 1 1 1
3、0 1 1 1“0”表示没错；表示没错；“1”表示有错表示有错2.差错控制的基本思路差错控制的基本思路差错控制的基本思路是：差错控制的基本思路是：在发送端被传送的信在发送端被传送的信息码序列（本身无规律）的基础上，按照一息码序列（本身无规律）的基础上，按照一定的规则加入若干监督码元后进行传输，这定的规则加入若干监督码元后进行传输，这些加入的码元与原来的信息码序列之间存在些加入的码元与原来的信息码序列之间存在着某种确定的约束关系。在接收数据时，检着某种确定的约束关系。在接收数据时，检验信息码元与监督码元之间的既定的约束关验信息码元与监督码元之间的既定的约束关系，如该关系遭到破坏，则收端可以发现传
4、系，如该关系遭到破坏，则收端可以发现传输中的错误，乃至纠正错误。输中的错误，乃至纠正错误。此过程叫此过程叫信息码信息码+监督码监督码=码组码组 r +k =n差错控制编码差错控制编码或纠错编码或或纠错编码或信道编码信道编码3.差错控制方式差错控制方式检错重发检错重发ARQ前向纠错前向纠错FEC混合纠错检错混合纠错检错HEC信息反馈信息反馈IRQ（1）检错重发）检错重发(ARQ)（自动重发请求）（自动重发请求）ARQ的思路的思路ARQ是在发送端对数据序列进行分组编码，加入一定是在发送端对数据序列进行分组编码，加入一定监督码元使之具有一定的检错能力，成为能够发现监督码元使之具有一定的检错能力，成为
5、能够发现错误的码组。接收端收到码组后，按一定规则对其错误的码组。接收端收到码组后，按一定规则对其进行有无错误的判别，并把判决结果进行有无错误的判别，并把判决结果(应答信号应答信号)通通过反向信道送回发送端。如有错误，发送端把前面过反向信道送回发送端。如有错误，发送端把前面发出的信息重新传送一次，直到接收端认为已正确发出的信息重新传送一次，直到接收端认为已正确接收到信息为止。接收到信息为止。ARQ的重发方式的重发方式ARQ有有3种重发方式，即停发等候重发，返回重发和种重发方式，即停发等候重发，返回重发和选择重发。选择重发。三种重发方式三种重发方式a.停止等待协议停止等待协议 当重发方式采用停发等
6、候重发时，应该遵循停止等待当重发方式采用停发等候重发时，应该遵循停止等待协议。协议。停止等待协议规定：停止等待协议规定：发送端每发送一个数据帧（对应一个码组）就暂停下发送端每发送一个数据帧（对应一个码组）就暂停下来，等待接收端的应答。接收端收到数据帧进行差错检测，来，等待接收端的应答。接收端收到数据帧进行差错检测，若数据帧没错，就向发送端返回一个确认帧若数据帧没错，就向发送端返回一个确认帧ACK，发送端再，发送端再发送下一个数据帧；若接收端检验出数据帧有错，就向发送发送下一个数据帧；若接收端检验出数据帧有错，就向发送端返回一个否认帧端返回一个否认帧NAK，发送端重发刚才所发数据帧，直到，发送端
7、重发刚才所发数据帧，直到没错为止。没错为止。b.连续连续ARQ协议协议 连续连续ARQ协议的重发方式是返回重发，即发送端从出协议的重发方式是返回重发，即发送端从出错数据帧及以后的各帧都要重发。错数据帧及以后的各帧都要重发。c.选择重发选择重发ARQ协议协议 选择重发选择重发ARQ协议的重发方式是选择重发，即发送端协议的重发方式是选择重发，即发送端只重发出错数据帧。只重发出错数据帧。停止等待停止等待(协议算法协议算法)重发重发数据帧在实际链路上传输有四种情况，如图所示。数据帧在实际链路上传输有四种情况，如图所示。ARQ的优缺点的优缺点u需反向信道，实时性差需反向信道，实时性差u编码效率较高编码效
8、率较高u译码设备较简单译码设备较简单（2）前向纠错（）前向纠错（FEC）（自动纠错）（自动纠错）FEC的思路的思路前向纠错系统中，发送端的信道编码器将输入前向纠错系统中，发送端的信道编码器将输入数据序列变换成能够纠正错误的码，接收端数据序列变换成能够纠正错误的码，接收端的译码器根据编码规律检验出错误的位置并的译码器根据编码规律检验出错误的位置并自动纠正。自动纠正。FEC的优缺点的优缺点不需要反向信道，实时性好。不需要反向信道，实时性好。缺点是所选择的纠错码必须与信道的错码特缺点是所选择的纠错码必须与信道的错码特性密切配合，否则很难达到降低错码率的要性密切配合，否则很难达到降低错码率的要求；求；
9、译码设备复杂；而要求附加的监督码也较多，译码设备复杂；而要求附加的监督码也较多，传输效率就低。传输效率就低。(3)混合纠错检错（混合纠错检错（HEC）HEC的思路的思路混合纠错检错方式是前向纠错方式和检错重发混合纠错检错方式是前向纠错方式和检错重发方式的结合。在这种系统中，发送端发出同方式的结合。在这种系统中，发送端发出同时具有检错和纠错能力的码，接收端收到码时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力，后，检查错误情况，如果错误少于纠错能力，则自行纠正；如果干扰严重，错误很多，超则自行纠正；如果干扰严重，错误很多，超出纠正能力，但能检测出来，则经反向信道出纠正
10、能力，但能检测出来，则经反向信道要求发端重发。要求发端重发。HEC的优缺点的优缺点混合纠错检错方式在实时性和译码复杂性方面混合纠错检错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷，因而近是前向纠错和检错重发方式的折衷，因而近年来，在数据通信系统中采用较多。年来，在数据通信系统中采用较多。(4)信息反馈（信息反馈（IRQ）IRQ的思路的思路信息反馈方式信息反馈方式(IRQ)在发送端不进行纠错编码，接收在发送端不进行纠错编码，接收端把收到的数据序列端把收到的数据序列全部全部由反向信道送回发端，发由反向信道送回发端，发端自己比较发送的数据序列与送回的数据序列，从端自己比较发送的数据序列
11、与送回的数据序列，从而发现是否有错误，并把认为错误的数据序列的原而发现是否有错误，并把认为错误的数据序列的原数据再次传送，直到发端没有发现错误为止。数据再次传送，直到发端没有发现错误为止。IRQ的优缺点的优缺点这种方式的优点是不需要纠错、检错的编译器，设这种方式的优点是不需要纠错、检错的编译器，设备简单。备简单。缺点是需要和前向信道相同的反向信道，实时性差。缺点是需要和前向信道相同的反向信道，实时性差。发送端需要一定容量的存储器以存储发送码组，环发送端需要一定容量的存储器以存储发送码组，环路时延越大，数据速率越高，所需存储容量越大。路时延越大，数据速率越高，所需存储容量越大。练习练习差错控制方
12、式中差错控制方式中 不需反向信道的是不需反向信道的是 实时性最好的是实时性最好的是 不需信道编译码器的是不需信道编译码器的是 用得最多的是用得最多的是 前向纠错前向纠错FEC 前向纠错前向纠错FEC 信息反馈信息反馈IRQ 混合纠错检错混合纠错检错HEC3.1.2 3.1.2 差错控制的基本原理差错控制的基本原理1.差错控制的原理差错控制的原理传两个消息传两个消息（1）发）发1位码位码 10 01无纠检错能力（2）发）发2位码位码 1110 0001可检错可检错1位位（3）发）发3位码位码 1 1 1 0 0 0可纠错可纠错1位位可检错可检错2位位收发两端约定，收发两端约定，当收到两个以上的当
13、收到两个以上的1时，认为发的是时，认为发的是111；当收到两个以上的当收到两个以上的0时，认为发的是时，认为发的是000。1 1 1 110 0 0 0 001若无以上约定，若无以上约定，111000110l 纠错编码之所以具有检错和纠错能力，纠错编码之所以具有检错和纠错能力，是因为在信息码之外附加了监督码，即码的是因为在信息码之外附加了监督码，即码的检错和纠错能力是用信息量的冗余度来换取检错和纠错能力是用信息量的冗余度来换取的。的。l 加入监督码越多，码的检错、纠错能力加入监督码越多，码的检错、纠错能力越强，但信息传输效率下降也越多。越强，但信息传输效率下降也越多。l 在纠错编码中将信息传输
14、效率也称为编在纠错编码中将信息传输效率也称为编码效率，定义为码效率，定义为nkR（3-1）2.汉明距离与检错和纠错能力的关系汉明距离与检错和纠错能力的关系（1）几个概念）几个概念码组的重量码组的重量码组中非零码元的数目为码组码组中非零码元的数目为码组的重量，简称码重。的重量，简称码重。码距码距把两个码组中对应码位上具有不同二把两个码组中对应码位上具有不同二进制码元的个数定义为两码进制码元的个数定义为两码 组的距离，简称码组的距离，简称码距。距。例：例：11010 10001 码距是码距是3汉明距离汉明距离在一种编码中，任意两个许用码在一种编码中，任意两个许用码组间距离的最小值，称为这一编码的汉
15、明距离，组间距离的最小值，称为这一编码的汉明距离，以以 表示。表示。mind例：一码组集合例：一码组集合min5,4,3,6,?detmin2d 1 0 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 03334223.纠错编码的分类纠错编码的分类(1)按码组的功能分，有检错码和纠错码两类。按码组的功能分，有检错码和纠错码两类。(2)按码组中监督码元与信息码元之间的关系分，按码组中监督码元与信息码元之间的关系分，有线性码和非线性码两类。有线性码和非线性码两类。(3)按照信息码元与监督码元的约束关系，又可按照信息码元与监督码元的约束关系，又可分为分组码和卷积码两类。分为分组码
16、和卷积码两类。(4)按照信息码元在编码前后是否保持原来的形按照信息码元在编码前后是否保持原来的形式不变，可划分为系统码和非系统码。式不变，可划分为系统码和非系统码。(5)按纠正差错的类型可分为纠正随机错误的码按纠正差错的类型可分为纠正随机错误的码和纠正突发错误的码。和纠正突发错误的码。(6)按照每个码元取值来分，可分为二进制码与按照每个码元取值来分，可分为二进制码与多进制码。多进制码。3.2 简单的差错控制编码简单的差错控制编码3.2.1 3.2.1 奇偶监督码奇偶监督码(编码规则)设码组长度为设码组长度为n，表示为，表示为 ()，其中前其中前n-1位为信息码元，第位为信息码元，第n位为监督位
17、位为监督位a0。0121,aaaann2、监督方程、监督方程0110 naaa1110 naaa偶检验的监督关系（偶监督方程）偶检验的监督关系（偶监督方程）在奇校验的监督关系在奇校验的监督关系（奇监督方程奇监督方程）1、概念概念偶监督码偶监督码-信息码与监督码合在一起信息码与监督码合在一起“1”的的个数是偶数个数是偶数奇监督码奇监督码-信息码与监督码合在一起信息码与监督码合在一起“1”的的个数是奇数个数是奇数只能发现单个或奇数个错误，只能发现单个或奇数个错误，不能检测出偶数个错误不能检测出偶数个错误3.2.1 3.2.1 水平奇偶监督码水平奇偶监督码 水平奇偶监督码的水平奇偶监督码的构成思路构
18、成思路是：将信息码序列是：将信息码序列按行排成方阵，每行后面加一个奇或偶监督编码，按行排成方阵，每行后面加一个奇或偶监督编码，即每行为一个奇偶监督码组即每行为一个奇偶监督码组(见表见表3-2，以偶监督为，以偶监督为例例)，但发送时则按列的顺序传输：，但发送时则按列的顺序传输：11101110011000010101，接收端仍将码元排成，接收端仍将码元排成与发送端一样的方阵形式，然后按行进行奇偶校验。与发送端一样的方阵形式，然后按行进行奇偶校验。表表3-2 水平偶监督码水平偶监督码 信信 息息 码码 元元 监督码元监督码元 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1
19、0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 10101*检错能力检错能力（1）可发现某一行上所有奇数个错误）可发现某一行上所有奇数个错误（2）能检测出所有长度不大于方阵中行数的）能检测出所有长度不大于方阵中行数的突发错误突发错误讨论：讨论：水平奇偶监督码是检错码，属于线性分组水平奇偶监督码是检错码，属于线性分组码。码。3.2.2 3.2.2 二维奇偶监督码二维奇偶监督码 二维奇偶监督码是将水平奇偶监督码推广而得，二维奇偶监督码是将水平奇偶监督码推广而得，又称水平垂直奇偶监督码、行列监督码和方阵码。又称水平垂直奇
20、偶监督码、行列监督码和方阵码。它的方法是在水平监督基础上对表它的方法是在水平监督基础上对表3-2方阵中每一方阵中每一列再进行奇偶校验，就可得表列再进行奇偶校验，就可得表3-3（以偶监督为例）（以偶监督为例）所示的方阵。发送是按列或按行的顺序传输。接收所示的方阵。发送是按列或按行的顺序传输。接收端重新将码元排成发送时方阵形式，然后每行、每端重新将码元排成发送时方阵形式，然后每行、每列都进行奇偶校验。列都进行奇偶校验。表表3-3 二维偶监督码二维偶监督码 信信 息息 码码 元元 监督码元监督码元 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1
21、 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 监督码元监督码元 101010 1 1 0 1 1 0 0 0 11*检错能力检错能力（1）可发现某行或某列上奇数个错误。）可发现某行或某列上奇数个错误。（2）能检测出所有长度不大于方阵中行数）能检测出所有长度不大于方阵中行数（或列数）的突发错误（或列数）的突发错误（3）能检测出偶数个错误。但若偶数个错误）能检测出偶数个错误。但若偶数个错误恰好分布在矩阵的四个顶点上时，这样的偶恰好分布在矩阵的四个顶点上时，这样的偶数个错误是检测不出来的。数个错误是检测不出来的。（4）可以纠正某些错误，当某行某列均
22、不满）可以纠正某些错误，当某行某列均不满足监督关系，可判定该行该列交叉位置的码足监督关系，可判定该行该列交叉位置的码元有错，从而纠正这一位上的错误。元有错，从而纠正这一位上的错误。讨论：二维奇偶监督码是检错码或纠错码，讨论：二维奇偶监督码是检错码或纠错码，属于线性分组码。属于线性分组码。3.3 汉明码及线性分组码汉明码及线性分组码 3.3.1 3.3.1 汉明码汉明码1、（n,k）汉明码）汉明码 r与与n的关系为的关系为2121rrnkr 或例题例题（2）纠检错）纠检错方法方法-接收端收到（接收端收到（7，4）汉明码，由下述）汉明码，由下述方程计算校正子，然后查表方程计算校正子，然后查表3-4
23、可知此码组是否可知此码组是否有错以及差错的确切位置有错以及差错的确切位置 s1 s2 s3 s1 s2 s3 错码位置错码位置 0 0 0 0 0 0 无错无错 0 0 1 0 0 1 a0 a0 0 1 0 0 1 0 a1 a1 1 0 0 1 0 0 a2 a2 0 1 1 0 1 1 a3 a3 1 0 1 1 0 1 a4 a4 1 1 0 1 1 0 a5 a5 1 1 1 1 1 1 a6 a6 表表3-4 较正子与错码位置较正子与错码位置*例：接收端收到某（例：接收端收到某（7，4）汉明码为）汉明码为1001010，此（此（7，4）汉明码是否有错？错码位置如何？）汉明码是否有错
24、？错码位置如何？讨论讨论 汉明距离汉明距离 编码效率编码效率3.3.2 3.3.2 线性分组码线性分组码2.线性分组码的主要性质线性分组码的主要性质 (1)封闭性封闭性 所谓封闭性，是指一种线性分组码中的所谓封闭性，是指一种线性分组码中的任意两个码组之逐位模任意两个码组之逐位模2和仍为这种码中的另和仍为这种码中的另一个许用码组。一个许用码组。线性码是指信息位和监督位满足一组线性方程线性码是指信息位和监督位满足一组线性方程的码，分组码是监督码仅对本码组起监督作用，的码，分组码是监督码仅对本码组起监督作用，既是线性码又是分组码称为线性分组码。既是线性码又是分组码称为线性分组码。(2)码的最小距离等
25、于非零码的最小重量（除了码的最小距离等于非零码的最小重量（除了全全0码组之外）码组之外）因为线性分组码具有封闭性，因而两个码组因为线性分组码具有封闭性，因而两个码组之间的距离必是另一码组的重量。之间的距离必是另一码组的重量。循环码是线性分组码中一类重要的码。循环码是线性分组码中一类重要的码。3.4.1 3.4.1 循环码的循环特性循环码的循环特性 循环码的循环性是指循环码中任一许用码组经循环码的循环性是指循环码中任一许用码组经过循环移位后过循环移位后(将最右端的码元移至左端，或反之将最右端的码元移至左端，或反之)所得到的码组仍为它的一个许用码组。所得到的码组仍为它的一个许用码组。表表3-6给出
26、一种给出一种(7，3)循环码的全部码组，由循环码的全部码组，由此表可直观看出这种码的循环性。例如，表中的第此表可直观看出这种码的循环性。例如，表中的第2码组向右循环移一位即得到第码组向右循环移一位即得到第5码组，第码组，第2码组向码组向左循环移一位即得到第左循环移一位即得到第3码组。码组。3.4 循环码循环码表表3-6 （7，3）循环码的码组）循环码的码组456aaa0123aaaa456aaa 码组码组编号编号 信息位信息位 监督位监督位 码组码组编号编号 信息位信息位 监督位监督位 1 1 2 2 3 3 4 4 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0
27、1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 0 1 5 5 6 6 7 7 8 8 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0123aaaa0123aaaa1.码的多项式码的多项式若码组若码组 ，则相应的多项式表示为则相应的多项式表示为 ),(0121aaaaAnn00112211)(xaxaxaxaxAnnnn3.4
28、.2 循环码的生成多项式和生成矩阵循环码的生成多项式和生成矩阵例例1：A=10110116432()1A xxxxx例例2：已知：已知 ，写出对应，写出对应的码组的码组(n=7)。653()1A xxxx解：解：A=1101001 循环码的循环码的2 k个码组中，有一个码组前个码组中，有一个码组前k-1位码元位码元均为均为0，第，第k位码元为位码元为1，第，第n位（最后一位）码元位（最后一位）码元为为1，此码组对应的多项式。，此码组对应的多项式。例：求表例：求表3-6（7，3）循环码的生成多项式。）循环码的生成多项式。表表3-6（7，3）循环码对应生成多项式的码组为）循环码对应生成多项式的码组
29、为第第3个码组个码组0010111，生成多项式为，生成多项式为42()1g xxxx2、循环码的生成多项式、循环码的生成多项式3.生成矩阵生成矩阵G由循环码的生成多项式由循环码的生成多项式g(x)可得到生成矩阵可得到生成矩阵G(x)，为，为)()()()()(21xgxxgxgxxgxxGkk转换后，典型的生成矩阵为转换后，典型的生成矩阵为QIGk生成矩阵生成矩阵可以通过线性变换将非典型的生成矩阵可以通过线性变换将非典型的生成矩阵转换为典型的生成矩阵，具体方法是：转换为典型的生成矩阵，具体方法是：任意几行模二加取代某一行。任意几行模二加取代某一行。例例将三位信息码将三位信息码 （000、001
30、、010、011111）与典型的生成矩阵）与典型的生成矩阵G相乘便可得到全相乘便可得到全部码组，即表部码组，即表3-6所示。所示。456aaa 信息字段为信息字段为K位，校验字段为位，校验字段为R位，位，码字长度码字长度为为N(N=K+R)位位 V(x)=xR m(x)+r(x)m(x)为为K次信息多项式，次信息多项式，r(x)为为R次校验多项式次校验多项式例如：信息字段代码为例如：信息字段代码为:1011001 :1011001 对应对应 m(xm(x)=x)=x6 6+x+x4 4+x+x3 3+1+1 g(xg(x)=x)=x4 4+x+x3 3+1+1 为生成多项式为生成多项式 g(x
31、g(x)的代码为的代码为:11001:11001校验码生成的另一种方法校验码生成的另一种方法 信息字段移位信息字段移位：x x4 4 m(x)=x m(x)=x1010+x+x8 8+x+x7 7+x+x4 4 1011001 101100100000000校验字段形成：（二进制除）校验字段形成：（二进制除）取余数取余数 11001 10110010000 11001 10110010000 得：得：10101010传输字段：传输字段：1011001101100110101010校验校验：接收字段接收字段/相同的生成码（二进制除），相同的生成码（二进制除），除尽（正确），除尽（正确），否则（错
32、）否则（错）Binary Division常用的常用的CRC生成多项式生成多项式g(x)为为:CRC16=x16+x15+x2+1 R=16，IBM专用专用 CRC16=x16+x12+x5+1 R=16，CCITT专用专用 CRC32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 R=32,LAN中常用中常用3.5 卷积码卷积码1.卷积码的概念卷积码的概念在分组码中，任何一段规定时间内编码器产生的在分组码中，任何一段规定时间内编码器产生的n个个码元的一个码组，其监督位完全决定于这段时间中码元的一个码组，其监督位完全决定于这段时间中输入的
33、输入的k个信息位，这个码组中的个信息位，这个码组中的n-k个监督位仅对个监督位仅对本码组起监督作用。本码组起监督作用。卷积码则不然，编码器在任何一段规定时间内产生的卷积码则不然，编码器在任何一段规定时间内产生的n个码元，其监督位不仅取决于这段时间中的个码元，其监督位不仅取决于这段时间中的k个信个信息位，而且还取决于前息位，而且还取决于前N-1段规定时间内的信息位。段规定时间内的信息位。换句话说，监督位不仅对本码组起监督作用，还对换句话说，监督位不仅对本码组起监督作用，还对前前N-1个码组也起监督作用。个码组也起监督作用。这段这段N时间内的码元数目时间内的码元数目nN称为这种卷积码的约束长称为这
34、种卷积码的约束长度。通常把卷积码记作度。通常把卷积码记作(n,k,N)，其编码效率，其编码效率 卷积码的基本概念卷积码的基本概念2 卷积码的编码卷积码的编码简单例子：由简单例子：由2个移位寄存器和个移位寄存器和1个模个模2加电路加电路构成（构成（2，1，2）卷积码编码器）卷积码编码器D1D2+m1m2m3m4m5m6tm1 c1 m2 c2 m3 c3 m4 c4 m5 c5 m6 c6tmcmi.m1.0.m2.m1.m3.m2.mi-1ci+1=mi+m(i+1)2 卷积码的解码卷积码的解码D1D2+D3与与门门.m1.c1 0S0.mi+10.m2.c2.m1.S1S0.m3.m2.c3
35、.S2S1.mi.ci+1SiSi-1S0=0 +m1+c1S1=m1+m2+c2S2=m2+m3+c3S3=m3+m4+c4校正子校正子Si=mi+m(i+1)+ci+1此为门限解码，属于代数解码，此为门限解码，属于代数解码，适于约束长度较短的卷积码；另一类为概率解码适于约束长度较短的卷积码；另一类为概率解码（2，1，3）卷积码编码器）卷积码编码器m1m2m3+.c1 c2C1=m1+m2+m3C2=m1+m3输入输入比特比特状态比状态比特特输入序列输入序列输出序列输出序列.m2m3=00(左左)输入输入m1=000移位后移位后10001001110010(左左)输入输入m1=1011100
36、10011100100111001001110010011100100111卷积码的树状图卷积码的树状图（2，1，3）卷积）卷积码的树状图码的树状图.a(m3m2)(左左)输入输入m1=0a.c1c2=00 ba b c da b(左左)输入输入m1=1 c d a b c da b c d a b c d a b cda b c d0000001111111111101010010111000110当输入序列当输入序列为为11010时，输出时，输出码元序列？码元序列？11 01 01 00 10输入为输入为0110时，时，输出码元输出码元序列？序列？000 111 101 011（2，1，3
37、）卷积码的网格图（篱笆图）卷积码的网格图（篱笆图）a b c d（2，1，3）卷积码的状态图）卷积码的状态图0，实线；，实线；1，虚线，虚线00=a 01=b10=c 11=d00=a 01=b 10=c 11=d0011111001100100卷积码的译码方法卷积码的译码方法代数译码利用编码本身得代数结构进行解码，代数译码利用编码本身得代数结构进行解码，并不考虑信道的统计特性。其主要特点是算并不考虑信道的统计特性。其主要特点是算法简单，易于实现，但是它的误码性能要比法简单，易于实现，但是它的误码性能要比概率译码差。其译码方法是从线性码的监督概率译码差。其译码方法是从线性码的监督子出发，找到一
38、组特殊的能够检查信息位置子出发，找到一组特殊的能够检查信息位置是否发生错误的方程组，从而实现纠错译码。是否发生错误的方程组，从而实现纠错译码。概率译码的基本思想是：把已经接收到的序列概率译码的基本思想是：把已经接收到的序列与所有可能的发送序列相比较，选择其中汉与所有可能的发送序列相比较，选择其中汉明距离最小的一个序列作为发送序列。维特明距离最小的一个序列作为发送序列。维特比译码是目前用得较多的一种译码方法。比译码是目前用得较多的一种译码方法。举例说明维特比译码工作原理举例说明维特比译码工作原理维特比提出了一种算法：译码器不是在篱笆图上一次就维特比提出了一种算法：译码器不是在篱笆图上一次就计算和
39、比较计算和比较 2Lk 条路径，而是接收一段，就计算、比条路径，而是接收一段，就计算、比较一段，从而在每个状态时，选择进入该状态的最可较一段，从而在每个状态时，选择进入该状态的最可能的分支。能的分支。维特比译码的基本思想：将接收序列维特比译码的基本思想：将接收序列 R R 与篱笆图上的与篱笆图上的路径逐分支地比较，比较的长度一般取路径逐分支地比较，比较的长度一般取(56)mn，然然后留下与后留下与 R R 距离最小的路径，称为幸存路径，而去掉距离最小的路径，称为幸存路径，而去掉其余可能的路径，并将这些幸存路径逐分支地延长并其余可能的路径，并将这些幸存路径逐分支地延长并存储起来。存储起来。幸存路
40、径的数目等于状态数：幸存路径的数目等于状态数：2km 以以(2,1,2)非系统码为例说明维特比译码的基本思想：非系统码为例说明维特比译码的基本思想：设发送序列设发送序列 C C 为全为全0；接收序列接收序列 R R=10,00,01,00,00,00,00,维特比译码的基本原理维特比译码的基本原理假设译码器的初始状态为全假设译码器的初始状态为全0；第0个时刻：接收序列的第接收序列的第0个分支个分支 R R0=10 进入译码器。进入译码器。从从 S0 状态有两个分支，它们是状态有两个分支，它们是 00 和和 11，R R0与这两与这两个分支比较，比较的结果和到达的状态如表个分支比较，比较的结果和
41、到达的状态如表 9.2 所示：所示：每个状态每个状态/节点都有两个存储器：节点都有两个存储器：路径存储器：存储该状态的部分路径；路径存储器：存储该状态的部分路径；路径值存储器：存储达到该状态的部分路径值路径值存储器：存储达到该状态的部分路径值(累加累加距离距离)。维特比译码的基本原理维特比译码的基本原理表9.2 幸 存 路 径 第0 分 支 的 距 离 到 达 状 态 0 0 11 1 1 S0 S1 第一个时刻：进入译码器的接收码组进入译码器的接收码组 R R1=00 和此时刻和此时刻出发的的四条分支比较，比较结果和达到状态如表四条分支比较，比较结果和达到状态如表9.3所示：所示：从第一个时
42、刻到第二个时刻：共有四条路径，到达共有四条路径，到达S0,S1,S2和和S3。在第二个时刻以前译码器不做任何选择和判决。在第二个时刻以前译码器不做任何选择和判决。每个状态的路径存储器存储下此时刻的幸存路径：存储下此时刻的幸存路径：0000,0011,1110,1101；每个状态的路径值存储器存储了此时刻到达该状态的幸存存储了此时刻到达该状态的幸存路径累加值路径累加值(累加距离累加距离)。维特比译码的基本原理维特比译码的基本原理表 9.3 上次距离 幸存路径 延长分支 本分支距离 累加距离 到达状态 1 3 2 2 0000 0011 1110 1101 00 11 10 01 11 00 01
43、 10 1 1 2 0 1 1 0 2 2 2 5 3 3 3 2 4 S0 S1 S2 S3 S0 S1 S2 S3 从第二个时刻起：第二个接收码组第二个接收码组 R R2=01 进入译码器，从篱进入译码器，从篱笆图上可见，从第二个时刻到第三个时刻，进入每个状态笆图上可见，从第二个时刻到第三个时刻，进入每个状态的分支有两个（或者说在第三个时刻，进入每个状态的路的分支有两个（或者说在第三个时刻，进入每个状态的路径有两条）。译码器将接收码组径有两条）。译码器将接收码组 R R2 与进入每个状态的两个与进入每个状态的两个分支进行比较和判决，选择一个累加距离（部分路径值）分支进行比较和判决，选择一个
44、累加距离（部分路径值）最小的路径作为进入该状态的幸存路径。这样的幸存路径最小的路径作为进入该状态的幸存路径。这样的幸存路径共四条，比较和判决的过程如下：共四条，比较和判决的过程如下：维特比译码的基本原理维特比译码的基本原理经过比较后选择：部分路径部分路径 000000为到达为到达 S0 状态的幸存路径；状态的幸存路径；部分路径部分路径 000011为到达为到达 S1 状态的幸存路径；状态的幸存路径；部分路径部分路径 110101为到达为到达 S2 状态的幸存路径；状态的幸存路径；部分路径部分路径 001101为到达为到达 S3 状态的幸存路径。状态的幸存路径。按照上述方法，接收序列的诸码组依次
45、进入译码器，按照上述方法，接收序列的诸码组依次进入译码器，每个时刻进入一个码组，沿着篱笆图对每个状态按部每个时刻进入一个码组，沿着篱笆图对每个状态按部分路径值（累加距离）的大小，选择一条幸存路径。分路径值（累加距离）的大小，选择一条幸存路径。在每个状态上进行判决时，可能出现进入这一状态的在每个状态上进行判决时，可能出现进入这一状态的两条路径的距离值相同，这时可以任选其一，因为对两条路径的距离值相同，这时可以任选其一，因为对以后的判决而言，无论选择那一条路径，累加距离是以后的判决而言，无论选择那一条路径，累加距离是相同的。相同的。对本例而言，按上述算法进行到对本例而言，按上述算法进行到第十一个分
46、支后，四条路分支后，四条路径的前面分支都合并在一起。所以，只要译码深度足够，径的前面分支都合并在一起。所以，只要译码深度足够，就可达到较低的错误概率。一般，约为就可达到较低的错误概率。一般，约为(56)mn，所以所以，维特比译码的延时可达，维特比译码的延时可达(56)m 个单位时刻（每个单位个单位时刻（每个单位时刻为时刻为 n 个码元长度）就可以对第个码元长度）就可以对第0个接收码组的信息元个接收码组的信息元进行判决。依此类推，对接收序列中的诸码组进行译码。进行判决。依此类推，对接收序列中的诸码组进行译码。维特比译码的一次运算：维特比译码的一次运算：计算每个输入分支的度量值（分支距离、累加距离
47、）；计算每个输入分支的度量值（分支距离、累加距离）；比较各部分路径的度量值，选择一条作为幸存路径。比较各部分路径的度量值，选择一条作为幸存路径。篱笆图中共有篱笆图中共有 2km 个状态，因此，维特比译码的计算量与编个状态，因此，维特比译码的计算量与编码存储码存储 m 成指数关系变化，所以采用维特比算法译码的卷成指数关系变化，所以采用维特比算法译码的卷积码，其积码，其 m 不能选的太大。不能选的太大。维特比译码的基本原理维特比译码的基本原理 维特比译码的基本原理维特比译码的基本原理 维特比译码的基本原理维特比译码的基本原理7.6 维特比译码的基本原理维特比译码的基本原理7.6 维特比译码的基本原
48、理维特比译码的基本原理 维特比译码的基本原理维特比译码的基本原理 总结维特比算法的步骤总结维特比算法的步骤在第在第 j(j=m)个时刻以前，译码器计算所有的长为个时刻以前，译码器计算所有的长为 m 个分支的部个分支的部分路径值，对进入分路径值，对进入 2km 个状态的每一条部分路径都保留。个状态的每一条部分路径都保留。第第 m 个时刻开始，对进入每一个状态的部分路径进行计算，这个时刻开始，对进入每一个状态的部分路径进行计算，这样的路径有样的路径有 2k 条，挑选具有最大部分路径值的部分路径为幸条，挑选具有最大部分路径值的部分路径为幸存路径，删去进入该状态的其它路径，然后，幸存路径向前延存路径，
49、删去进入该状态的其它路径，然后，幸存路径向前延长一个分支。长一个分支。重复第二步的计算、比较和判决过程。若输入接收序列长为重复第二步的计算、比较和判决过程。若输入接收序列长为(L+m)k，其中，后其中，后 m 段是人为加入的全段是人为加入的全0段，则译码一直进段，则译码一直进行到行到(L+m)个时刻为止。个时刻为止。若进入某个状态的部分路径中，有两条的部分路径值相等，则可若进入某个状态的部分路径中，有两条的部分路径值相等，则可任选其一作为幸存路径。任选其一作为幸存路径。维特比译码的基本原理维特比译码的基本原理小结小结R=k/n第三节第三节 简单的差错控制编码简单的差错控制编码奇偶监督码、水平奇
50、偶监督码、二维奇偶监督奇偶监督码、水平奇偶监督码、二维奇偶监督码的构成思路、检错能力码的构成思路、检错能力第四节第四节 汉明码及线性分组码汉明码及线性分组码1 汉明码汉明码 r与与n的关系的关系 （7，4）汉明码（监督方程、纠检错方法、）汉明码（监督方程、纠检错方法、几个要点）几个要点）2 线性分组码的概念、主要性质线性分组码的概念、主要性质 第五节第五节 循环码循环码 码组码组A码的多项式码的多项式 循环特性循环特性生成多项式（最高幂次）概念、求法生成多项式（最高幂次）概念、求法 生成矩阵生成矩阵 第六节第六节 卷积码卷积码 基本概念、约束长度、编码效率基本概念、约束长度、编码效率作业作业P
