武汉大学通信原理第9章 差错控制编码

1、通信原理简明教程（第通信原理简明教程（第2版）版）2007年12月12007年12月2 信源编码，目的是实现模拟信号数字化信源编码，目的是实现模拟信号数字化 信道编码，目的是提高数字通信的可靠性信道编码，目的是提高数字通信的可靠性 差错率是信噪比的函数差错率是信噪比的函数 信道编码，差错控制编码，抗干扰编码信道编码，差错控制编码，抗干扰编码 信道编码过程：信道编码过程： 信息码元序列监督码元信息码元序列监督码元编码码组编码码组 信道译码过程：信道译码过程： 编码码组编码码组检错或纠错检错或纠错信息码元序列信息码元序列2007年12月3 9.1差错控制编码的基本概念差错控制编码的基本概念 9.2

2、线性分组码线性分组码 9.3循环码循环码 9.4卷积码卷积码 9.5 差错控制编码对系统性能的改善差错控制编码对系统性能的改善 9.6 数字通信系统的应用举例数字通信系统的应用举例 2007年12月4 9.1.1差错控制方式差错控制方式 9.1.2差错控制编码分类差错控制编码分类 9.1.3几种简单的检错码几种简单的检错码 9.1.4检错和纠错的基本原理检错和纠错的基本原理2007年12月5 常用的差错控制方式有三种：常用的差错控制方式有三种： 前向纠错（前向纠错（FEC:forward error correction） 发送能纠错的码，在译码时自动发现并纠正传输中的错误发送能纠错的码，在译

3、码时自动发现并纠正传输中的错误 只需正向信道，实时性好只需正向信道，实时性好 编译码设备复杂，适合单向信道和一发多收系统编译码设备复杂，适合单向信道和一发多收系统 检错重发（检错重发（ARQ:automatic repeat request） 发送端发出能够检错的码，接收端检验，接收端发出反馈应答信号，发送端发出能够检错的码，接收端检验，接收端发出反馈应答信号，发送端重新传输发送端重新传输 直到正确接收为止直到正确接收为止 工作原理简单，正向信道工作原理简单，正向信道+反向信道，传输效率低反向信道，传输效率低 混合纠错（混合纠错（HEC:hybrid error correction） 前向纠

4、错方式和检错重发方式的结合与折衷前向纠错方式和检错重发方式的结合与折衷 外层先采用前向纠错，当前向纠错不能解决问题时，内层再采用检错外层先采用前向纠错，当前向纠错不能解决问题时，内层再采用检错重发重发。2007年12月6 （a） FEC方式方式 （b）ARQ方式方式 （c） HEC方式方式2007年12月7 检检 错错 重重 发发 的的 三三 种种 方方 式式 停发等候重发停发等候重发返回重发返回重发选择重发选择重发2007年12月89.1.2 9.1.2 差错控制编码分类差错控制编码分类在编码前先把信息序列分为在编码前先把信息序列分为k位一组（称为位一组（称为信息信息码码），然后附加），然后

5、附加m位位监督码监督码，形成，形成n = k + m位的码组。位的码组。1、按信息码和附加监督码间的检验关系、按信息码和附加监督码间的检验关系 线性码：监督码是信息码的线性组合线性码：监督码是信息码的线性组合 非线性码：监督码是信息码的非线性组合非线性码：监督码是信息码的非线性组合2、按信息码和监督码间的约束方式、按信息码和监督码间的约束方式 分组码：监督码仅与本码组的信息码有关分组码：监督码仅与本码组的信息码有关 卷积码：监督码与之前的若干个信息码组的码元有约束关系卷积码：监督码与之前的若干个信息码组的码元有约束关系2007年12月91. 奇偶监督码奇偶监督码 编码方法编码方法 把信息码元先

6、分组，在每组最后加一位监督码元，使把信息码元先分组，在每组最后加一位监督码元，使该码组中该码组中1的数目为奇数或偶数的数目为奇数或偶数 奇数时称为奇校验码奇数时称为奇校验码 偶数时称为偶校验码偶数时称为偶校验码 偶校验码偶校验码 许用码组为许用码组为000，011，101，110 禁用码组为禁用码组为001，010，100，111 奇校验码奇校验码 禁用码组为禁用码组为000，011，101，110 许用码组为许用码组为001，010，100，1112007年12月10一般情况下：一般情况下： 设码组长为设码组长为n，且为：，且为： 则偶校验时有：则偶校验时有： 奇校验时有：奇校验时有： 译码

7、方法译码方法(与编码方法相对应与编码方法相对应) 不满足校验关系，传输一定错误！不满足校验关系，传输一定错误！ 奇偶校验只能发现奇数个奇偶校验只能发现奇数个(单个单个)错误，不能检测出错误，不能检测出偶数个错误。偶数个错误。 编码方法简单且实用性强，适用于检测随机零星错码编码方法简单且实用性强，适用于检测随机零星错码 满足校验关系，传输一定准确吗？满足校验关系，传输一定准确吗？0321aaaannn0 110naaa1 110naaa2007年12月112. 二维奇偶监督码二维奇偶监督码 将奇偶校验码的若干码组排列成矩阵将奇偶校验码的若干码组排列成矩阵 每一码组写成一行每一码组写成一行 m个码

8、组个码组m行行 m个监督位构成了一监督位列个监督位构成了一监督位列 按列的方向增加第二维校验位按列的方向增加第二维校验位 n个监督位构成了一监督位行个监督位构成了一监督位行maaa02010 021cccnn012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn检错能力检错能力 检出所有行和列中的奇数个检出所有行和列中的奇数个差错差错 能检出大多数偶数个差错能检出大多数偶数个差错 检测突发错码也有一定的适检测突发错码也有一定的适应能力应能力方阵码，交织码方阵码，交织码2007年12月123. 重复码重复码 重复码是在每位信息码元之后，再简单重复

9、多次的编码；重复码是在每位信息码元之后，再简单重复多次的编码；接收端译码时采用多数表决法接收端译码时采用多数表决法 。4. 恒比码恒比码 从固定码长的码组中选择那些从固定码长的码组中选择那些1和和0的比例恒定的码组作的比例恒定的码组作为许用码组，如五单位保护电码等。为许用码组，如五单位保护电码等。5. ISBN国际统一图书编号国际统一图书编号2007年作了修改年作了修改2007年12月139.1.4 9.1.4 检错与纠错的基本原理检错与纠错的基本原理 差错编码的基本思想是在被传输的信息中附加差错编码的基本思想是在被传输的信息中附加监督码，用监督码，用信息的冗余度信息的冗余度来实现检错和纠错。

10、来实现检错和纠错。 例如：例如：000000、001001、010010、011011、100100、101101、110110、111111用来传递信息，则无法检错；用来传递信息，则无法检错； 000000、011011、101101、110110用来传递信息可以检一位错，用来传递信息可以检一位错，但无法纠错；但无法纠错； 000000、111111用来传递信息可以检一位或两位错码，还用来传递信息可以检一位或两位错码，还可以纠一位错码。可以纠一位错码。 可见，码组间的差异与纠检错能力十分重要。可见，码组间的差异与纠检错能力十分重要。2007年12月14 定义定义1：码组中非零码元的数目称为码

11、组的重量，简称码组中非零码元的数目称为码组的重量，简称码重。码重。 定义定义2：两码组中对应码位上具有不同码元的数目称为两码组中对应码位上具有不同码元的数目称为两码组的距离，简称码距，又叫汉明距。两码组的距离，简称码距，又叫汉明距。 最小汉明距离最小汉明距离dmin决定纠检错能力决定纠检错能力 例例 8种码组种码组000000、001001、010010、011011、100100、101101、110110、111111均均为许用码组时，最小码距为为许用码组时，最小码距为1 在选在选4种码组种码组000000、011011、101101、110110为许用码组情况下，最为许用码组情况下，最小

12、码距为小码距为2 采用采用2种许用码组种许用码组000000、111111时，最小码距为时，最小码距为32007年12月15下图为码距的几何解释下图为码距的几何解释三种编码组合，其汉明距分别为三种编码组合，其汉明距分别为1，2，3。2007年12月16 对于分组码，一般有如下结论：对于分组码，一般有如下结论： (1) (1) 在一个码组内检测在一个码组内检测e e个误码，要求个误码，要求 ； (2) (2) 在一个码组内纠正在一个码组内纠正t t个误码，要求个误码，要求 ； (3) (3) 在一个码组内纠正在一个码组内纠正t t个误码，同时检测个误码，同时检测 个误个误码，要求码，要求 。 差

13、错控制编码提高了通信系统的可靠性，也降低了有效差错控制编码提高了通信系统的可靠性，也降低了有效性。性。 为衡量有效性，定义编码效率为衡量有效性，定义编码效率 。k k是编码前码组中的码元数，即信息码元数是编码前码组中的码元数，即信息码元数；n n是编码后码组中的码元数，它包含了校验码元是编码后码组中的码元数，它包含了校验码元。 1min ed12min td)(tee1minetdnkR/c2007年12月179.2 9.2 线性分组码线性分组码 线性码组中的监督码是信息码元的线性组合。线性码组中的监督码是信息码元的线性组合。 线性码具有封闭性，即任意两个许用码组之和（模线性码具有封闭性，即任

14、意两个许用码组之和（模2加），结果仍为一许用码组。加），结果仍为一许用码组。 设设n位分组码用位分组码用 表示，表示，k位信息码用位信息码用 表示，记该码组为表示，记该码组为(n , k)码。码。 将码组和信息码组用行矩阵表示出来，则有：将码组和信息码组用行矩阵表示出来，则有： nccc,21kddd,21nccc,21Ckddd,21D2007年12月18 kmkmmnkkkkkkkkdhdhdhcdhdhdhcdhdhdhcdcdcdc 221122221212121211112211n=k+m，n：编码以后的位数：编码以后的位数k：编码以前的位数，即：编码以前的位数，即信息码信息码m=n

15、-k：监督位或校验位：监督位或校验位2007年12月19 写成矩阵形式，有写成矩阵形式，有 ，G为生成矩阵为生成矩阵(k*n)，且：，且： 设设 则则GDCmkkkmmhhhhhhhhh212221212111100000100001G100000100001kImkkkmmhhhhhhhhh212221212111P mkkCDDPDDPDIPIDC , , , ,k行行k+m =n列列2007年12月20 与监督位或校验位相对应与监督位或校验位相对应 编码的根据编码的根据 译码的根据，检纠错的根据译码的根据，检纠错的根据矩阵矩阵P如何选择？如何选择？ 编码前信息码组有编码前信息码组有k位码

16、元，位码元，k位码元共有位码元共有 种组合种组合 编码后码组有编码后码组有n位码元，位码元，n位码元共有位码元共有 种组合，种组合， 矩阵矩阵P可有多种选择可有多种选择 较强的检错或纠错能力较强的检错或纠错能力 实现方法尽可能简单且编码效率高实现方法尽可能简单且编码效率高 在数学上已经证明在数学上已经证明 线性码的最小码距正好等于非零码的最小码重线性码的最小码距正好等于非零码的最小码重 为了估算线性码的差错控制能力应首先求出码组的最为了估算线性码的差错控制能力应首先求出码组的最小码距小码距k22nkn22 2007年12月21例例9-19-1已知已知(6,3)(6,3)码的生成矩阵为码的生成矩

17、阵为G G，试求：，试求：(1) (1) 编码码组编码码组和各码组的码重；和各码组的码重；(2) (2) 最小码距最小码距 及其差错控制及其差错控制能力。能力。 解解(1) (1) 由由3 3位码组成的信息码组矩阵为位码组成的信息码组矩阵为D D：011100110010101001Gmind111011101001110010100000D2007年12月22 由式由式 ，得码组矩阵为：，得码组矩阵为： 信息码组、编码码组及码重如下表所示：信息码组、编码码组及码重如下表所示：信息码组信息码组 编码码组编码码组 码重码重W 信息码组信息码组 编码码组编码码组 码重码重W0 0 0 0 0 0

18、0 0 0 0 1 0 0 1 0 0 1 0 1 30 0 1 0 0 1 1 1 0 3 1 0 1 1 0 1 0 1 1 40 1 0 0 1 0 0 1 1 3 1 1 0 1 1 0 1 1 0 40 1 1 0 1 1 1 0 1 4 1 1 1 1 1 1 0 0 0 3GDC000 011 110 101 101 110 011 000 111011101001110010100000011100110010101001 111011101001110010100000C2007年12月23 由前表可知，非零码组的最小码重为：由前表可知，非零码组的最小码重为： 所以最小码距为

19、：所以最小码距为： 因此，该码有纠因此，该码有纠1 1错，或检错，或检2 2错，或纠一错同时检一错错，或纠一错同时检一错的能力。的能力。 3minW3mind2007年12月24译码原理译码原理 由由 可知，可知， 或写成或写成 设设 ，则有，则有 。 任何线性分组码码组都应该满足上述关系任何线性分组码码组都应该满足上述关系 信息码与监督码间的校验关系完全取决于信息码与监督码间的校验关系完全取决于H H矩阵称为矩阵称为校验矩阵校验矩阵或或监督矩阵，是译码的关键！监督矩阵，是译码的关键！ mkkCDDPDDPDIPIDC , , , ,mm 0DPCDPC, mm0PDCITm，HPIT 0CH

20、2007年12月25 设接收码组为设接收码组为R，它可分解为，它可分解为 。 其中，其中，C为正确码组，为正确码组，E为错误码组（差错图案）为错误码组（差错图案） 当无错接收时，当无错接收时，E为为0，当有错接收时，当有错接收时，E为非零矢量为非零矢量。 再设伴随矩阵为：再设伴随矩阵为： ， 则有：则有： 当出现错码时，当出现错码时，S为非零矢量，则根据上式可求得为非零矢量，则根据上式可求得E，然后再经过计算然后再经过计算 ，便可得到正确的码组了。，便可得到正确的码组了。ECR+=TRHS TTTEHEHCHSERC只与只与E有关，而与发送有关，而与发送的码字的码字C无关。只反映无关。只反映信

21、道对码字的干扰信道对码字的干扰RHT=S - E - C=R+E2007年12月26 由于信息码组有由于信息码组有 个，由于由个，由于由S计算出来的计算出来的E不唯一，不唯一，纠正后的纠正后的C就不同，这时，使用就不同，这时，使用最大似然比准则最大似然比准则，选择，选择与与R最接近的最接近的C作为正确的接收码组。方法是：作为正确的接收码组。方法是：在在 E中选择码重最中选择码重最 小的小的E，即表示，即表示 选择与选择与R最接近最接近 的的C。 右图是查表法译右图是查表法译 码器原理图。码器原理图。 k22007年12月27例例9-2 9-2 按照例按照例9-19-1生成矩阵生成矩阵G G，列

22、出，列出S S与与E E的对照表。当收到的对照表。当收到码组码组R=1 1 1 0 1 1R=1 1 1 0 1 1时，解出对应的信息码组时，解出对应的信息码组D D。解：已知生成矩阵为：解：已知生成矩阵为： 又因为又因为 故故100010001011110101TmIPHTm，HPI2007年12月28 为为6 6X X3 3的矩阵，由式的矩阵，由式 可知，共有可知，共有 种形式，种形式，相应的码重最小矢量有相应的码重最小矢量有8 8种，见下表。由表可知，种，见下表。由表可知，(6,3)(6,3)码具有码具有纠纠1 1错能力。虽然错能力。虽然S S111111时对应一种双错图案，但除此以外的

23、时对应一种双错图案，但除此以外的双错却不能得到纠正。双错却不能得到纠正。 E S E SE S E S 0 0 0 0 0 0 000 0 0 0 0 0 0 0 0 0 000 0 0 0 1 1 0 0 100 0 0 100 1 1 0 0 0 0 0 101 0 0 0 0 0 0 0 0 0 101 0 0 0 0 1 1 0 010 0 010 0 0 1 1 0 0 0 0 011 0 0 0 0 0 0 0 0 0 011 0 0 0 0 0 1 1 001 001 0 0 0 0 1 1 0 0 0 110 0 0 0 110 1 1 0 0 0 0 0 0 1 1 0 11

24、1 0 111THTEHS 322007年12月29 将码组矢量将码组矢量R=1 1 1 0 1 1代入代入 ，可得，可得S(如下如下)。 查查E-S对照表，可找到差错矢量为：对照表，可找到差错矢量为： 由式由式 ，可得到正确码组，即，可得到正确码组，即 所以信息码组为：所以信息码组为：TRHS 110100010001011110101 110111T RHS000010E110101ERC101DERC2007年12月30 汉明码：汉明码：能纠正单个错码的称为汉明码。能纠正单个错码的称为汉明码。 为能指出所有单错位置和无错情况，线性码组码长为能指出所有单错位置和无错情况，线性码组码长n、信

25、息位信息位k和监督位和监督位m间应满足下述关系：间应满足下述关系： 上式取等号时为汉明码，此时有：上式取等号时为汉明码，此时有： 由于由于m = nk， 所以，所以，12 nm1212mmnknmm)()(1log1log22nknnkn2007年12月31 上式表明：若信息码组长为上式表明：若信息码组长为k，则能纠正单个错码所需，则能纠正单个错码所需的最小码组长度的最小码组长度n。此时有。此时有 。 由上式可求得有由上式可求得有(3 , 1)(3 , 1)码，码，(7 , 4)(7 , 4)码，码，(15 , 11)(15 , 11)码，码，(31 , 26)(31 , 26)码等。码等。

26、汉明码的编码效率为：汉明码的编码效率为： 一般地，若码组有纠一般地，若码组有纠t t个差错的能力，则应能指出无个差错的能力，则应能指出无错、单错到错、单错到t t个差错所有可能情况，此时校验位数个差错所有可能情况，此时校验位数m m应满应满足：足： 上式称为汉明界。它给出了纠上式称为汉明界。它给出了纠t t个错的必要条件个错的必要条件。3mind1211212cmmmmmnkRtjjnmC022007年12月329.3 9.3 循环码循环码9.3.1 循环码的特点及表达式循环码的特点及表达式 循环码是一种系统分组码，前循环码是一种系统分组码，前k位是信息码，后位是信息码，后r位是监位是监督码。

27、不仅具有督码。不仅具有封闭性封闭性，还具有，还具有循环性循环性，即一许用码组，即一许用码组经循环移位后得到另一个许用码组。经循环移位后得到另一个许用码组。 设设 是一个循环码组，则可将之表示为：是一个循环码组，则可将之表示为： 上式称为码多项式。上式称为码多项式。nccc,21Cnnncxcxcxc 2211)(2007年12月33 码组码组C移位移位1次得到的仍是码组，它可写成：次得到的仍是码组，它可写成： 不难验证：不难验证： 类似地，码组类似地，码组C经经i次移位后，得到的新的码组次移位后，得到的新的码组 是是 除以除以 的余式。的余式。 也就是说，在模也就是说，在模 意义下，意义下，若

28、若c(x)是码多是码多项式，则项式，则 都是码多项式。都是码多项式。 循环码的编码过程也可用多项式来描述循环码的编码过程也可用多项式来描述。123121 cxcxcxcxcnnn)()()()()()(xcxcxcxcxcxcxnnnn111211 )()(xci)(xcxi)(1nx)(1nx)(xcxi2007年12月34 一个一个k位信息码组位信息码组 用信息多项式表述出来，用信息多项式表述出来，则有：则有： 编码问题就是求解码组多项式编码问题就是求解码组多项式c(x) 的问题。的问题。 设设 ，这里这里g(x)是是 的的nk次因式，次因式，称为生成多项式。称为生成多项式。 所以有所以有

29、： 由于由于 而前已证明：而前已证明： 显然，显然， ，d1(x)对应某个信息码组对应某个信息码组kddd,21Dkkkdxdxdxd 2211)()()()(xgxdxc)(1nx)()()()(xgdxgxdxgxdxckkk 2211)()()(xgxdxxcx)()()()(xcxcxcxn111 )()()()(xgxdxc112007年12月35 上式表明：上式表明： 对应某个信息码组，就是说对应某个信息码组，就是说c(x) 一定是一定是循环码组。或者说，循环码完全由其码组长度循环码组。或者说，循环码完全由其码组长度n及生成及生成多项式多项式g(x)所决定。由于所决定。由于g g(

30、 (x x) )是一个能除尽是一个能除尽 的的n nk k次多项式，所以对次多项式，所以对 进行因式分解，便可得进行因式分解，便可得到相应的到相应的g g( (x x) )。 通常，由信息码组通常，由信息码组D和生成多项式求出的码组不是系统和生成多项式求出的码组不是系统码。根据系统码的定义，码组的前码。根据系统码的定义，码组的前k位是信息码，后位是信息码，后m位是校验码。位是校验码。 用多项式表示为：用多项式表示为：)(xd1)(1nx)(1nx)()()(xRxdxxckn2007年12月36 又因为又因为 ，所以，有：，所以，有： 或写成：或写成： 因此，有：因此，有： 可见，可见， 。)

31、()()(xgxdxc1)()()()(xgxdxRxdxkn1)()()()(xRxgxdxdxkn1)()()()()(xgxRxdxgxdxkn1)()()(xgxdxxRknremremainder 余数，余式，余项余数，余式，余项 2007年12月37例例9-3 9-3 求求(7 , 4)(7 , 4)循环码的生成多项式循环码的生成多项式g g( (x x) )。当信息码组当信息码组D=1 0 1 0 D=1 0 1 0 时，求输出码组时，求输出码组C C。解：由已知条件可知解：由已知条件可知n n = 7= 7，k k = 4= 4，m m = 3= 3，g g( (x x) )

32、应为应为 的的3 3次因式。而次因式。而 得到得到2 2个个g g( (x x) )分别为：分别为： 和和 由由 可计算输出码组。计算过程如下：可计算输出码组。计算过程如下： 多项式运算时遵循模多项式运算时遵循模2 2规则，即规则，即 。 )(17x)()(11112337xxxxxx131xxxg)(1232xxxg)(333632111332654222( )()( )( )( )()(1)10 01110( )( )( )()(1)1110 010d xxxc xd x g xxx xxxxxxcxd x gxxx xxxxxxCC0iixx)()()(xgxdxc2007年12月38例

33、例9-4 9-4 用例用例9-39-3的生成多项式的生成多项式g g( (x x) )求系统循环码的码组，求系统循环码的码组，已知已知D=1 0 1 0D=1 0 1 0。解：当解：当 时，信息多项式和升位后的多项式时，信息多项式和升位后的多项式分别为：分别为：求余式求余式R R( (x x) )的竖式为：的竖式为：131xxxg)(4633473xxxxxxdxxxxd)()()(3136464333 1( )1 1 1( )xd xxxxxxxxxxxxR x 2007年12月39 余式和码组多项式分别为：余式和码组多项式分别为： 可得系统循环码码组可得系统循环码码组C C为：为： 当当

34、时，用同样方法可得：时，用同样方法可得： 由以上结果可以看出，用不同的生成多项式，都可以由以上结果可以看出，用不同的生成多项式，都可以得到系统循环码。得到系统循环码。 11461xxxxcxxR)()(11 0 1 0 0 1 1C1232xxxg)(6422( )1( )11 0 1 0 0 0 1R xc xxxC2007年12月409.3.2 循环码的编码和译码循环码的编码和译码 循环码的优点是其编译码电路都可用移位寄存器和模循环码的优点是其编译码电路都可用移位寄存器和模2 2加构成的线性时序网络来实现。编码的关键是求出校验加构成的线性时序网络来实现。编码的关键是求出校验位多项式位多项式

35、R R( (x x) )，而，而R R( (x x) )可通过式可通过式 求解。求解。 多项式除法可用带反馈的线性移位寄存器来实现。多项式除法可用带反馈的线性移位寄存器来实现。g g( (x x) )与移位寄存器的反馈逻辑相对应，与移位寄存器的反馈逻辑相对应， 是初始预置状态，随着码元的节拍就可以进行求解余式是初始预置状态，随着码元的节拍就可以进行求解余式的运算。的运算。 )()()(xgxdxxRknrem)(xdxkn2007年12月41 (7,4)循环码编码电路如下图所示。循环码编码电路如下图所示。 由于发送码组由于发送码组c(x) 是是g g( (x x) ) 的倍式。如果经信道传输后

36、的倍式。如果经信道传输后发生错误，收到码组多项式发生错误，收到码组多项式r r( (x x) ) 不再是不再是g g( (x x) ) 的倍式，的倍式，可表示为可表示为 或写成：或写成：)()()()()(xgxsxmxgxr1)(/ )()(xgxrxsrem2007年12月42 s s( (x x) ) 是是r r( (x x) ) 除以除以g g( (x x) ) 的余式，是不大于的余式，是不大于m m1 1次的码次的码组多项式，称为伴随多项式或校正子多项式。组多项式，称为伴随多项式或校正子多项式。 接收码组接收码组r r( (x x) )可表示为发送码组与差错多项式之和，可表示为发送码

37、组与差错多项式之和，即即 r r( (x x) = ) = c c( (x x) + ) + e e( (x x) ) 。 所以，有：所以，有： 由此，可以通过由此，可以通过s s( (x x) )确定确定e e( (x x) )。 对于一个对于一个s s( (x x) )，可以有多个，可以有多个e e( (x x) )，依照最大似然比准，依照最大似然比准则，取最小码重的则，取最小码重的e e( (x x) )，于是，可得所接收到的码组为：，于是，可得所接收到的码组为：c c( (x x) = ) = r r( (x x) +) + e e( (x x) ) )()()()(xgxexcxsr

38、em)(/ )(xgxerem2007年12月43 右图是循环码译码器的一种。校正子计算电路计算出右图是循环码译码器的一种。校正子计算电路计算出相应的相应的s(x)， 错误图样识别器错误图样识别器 可通过查表法找可通过查表法找 到到e e( (x x) )，模，模2 2和用和用 来计算正确的译来计算正确的译 码输出码输出c c( (x x) = ) = r r( (x x) +) + e e( (x x) ) 。例例9-59-52007年12月44例例9-5 9-5 已知纠单错已知纠单错(7, 4)(7, 4)系统循环码的生成多项式为系统循环码的生成多项式为 ，试构成译码表。，试构成译码表。若

39、接收码组若接收码组R= 1 0 0 0 1 0 1R= 1 0 0 0 1 0 1，求发送码组。，求发送码组。解：根据书中式解：根据书中式(9-38)(9-38)，对码重为，对码重为1 1的差错多项式的差错多项式e e( (x x) )，求出相应的伴随多项式求出相应的伴随多项式s s( (x x) )，将其对应结果列成译码表，将其对应结果列成译码表，如下表所示。如下表所示。 e e( (x x) ) ：s s( (x x) ) ：123xxxg)(6x5x4x3x2xxxx 21x12 xx12x2xx2007年12月45 当接收码组无错误时，当接收码组无错误时，e e( (x x) = 0)

40、 = 0，则，则s s( (x x) = 0) = 0。本题。本题给出的接收码组为：给出的接收码组为： 由此可写出接收码组多项式：由此可写出接收码组多项式： 由由 可计算出伴随多项式：可计算出伴随多项式： 查表得到：查表得到： 由由r r( (x x) ) 和和e e( (x x) ) 可得到译码码组多项式可得到译码码组多项式 ：1000101R126xxxr)()(/ )()(xgxrxsrem111rem2326xxxxxxs)(5xxe)(1256xxxxexrxc)()()(2007年12月46 相应的码组为：相应的码组为： 由于是系统循环码，所以信息码组为：由于是系统循环码，所以信息

41、码组为： 据此分析构成的一种译码器如下图所示。图中伴随式据此分析构成的一种译码器如下图所示。图中伴随式计算电路对接收到的码多项式计算出相应的计算电路对接收到的码多项式计算出相应的s(x)s(x)。错误。错误图样识别器是一个具有图样识别器是一个具有n nk k个输入端的逻辑电路，原则个输入端的逻辑电路，原则上可采用查表方法，根据上可采用查表方法，根据 伴随式找到错误图样。伴随式找到错误图样。 缓存器用于存储缓存器用于存储k k位信位信 息码元。模息码元。模2 2和电路用和电路用 于纠正错误。于纠正错误。1100101C1100D2007年12月47引引 言言 卷积码是非分组码。卷积码是非分组码。

42、 它充分利用了各组之间的相关性，信息码的码它充分利用了各组之间的相关性，信息码的码长长 k和卷积码的码长和卷积码的码长n 都比较小。都比较小。 卷积码的性能在许多实际应用情况下优于分组卷积码的性能在许多实际应用情况下优于分组码，而且设备也较简单。码，而且设备也较简单。 通常它更适用于前向纠错，在高质量的通信设通常它更适用于前向纠错，在高质量的通信设备中已得到广泛应用。备中已得到广泛应用。 2007年12月481编码方法编码方法 由由N 段输入移位寄存器，段输入移位寄存器，n 个模个模2加法器和加法器和n 级输级输出移位寄存器三部分组成。出移位寄存器三部分组成。 N 段输入移位寄存器每段均为段输

43、入移位寄存器每段均为k 位，这样共有位，这样共有Nk 位输入移位寄存器。位输入移位寄存器。 编码器每输入编码器每输入k 位信息比特，输出移位寄存器输位信息比特，输出移位寄存器输出出n 位比特的编码。位比特的编码。 2007年12月49 由图可知，由图可知，n 位输出比特不但与当前的位输出比特不但与当前的k个输入信息比特个输入信息比特有关，而且与以前的有关，而且与以前的(N1)k 个输入信息比特有关。个输入信息比特有关。 通常把通常把N 称为编码约束长度，把卷积码记作（称为编码约束长度，把卷积码记作（n，k，N），），编码效率。编码效率。 在有的文献中将在有的文献中将N1或或nN 称为约束长度。

44、称为约束长度。 2007年12月50 输出移位寄存器用转换开关代替。输出移位寄存器用转换开关代替。 每个时隙中，只有每个时隙中，只有1bit输入信息进入移位寄存器，并且移位寄输入信息进入移位寄存器，并且移位寄存器暂存的内容向右移存器暂存的内容向右移1位，开关旋转一周输出位，开关旋转一周输出2比特。比特。 bi 是当前输入信息位，是当前输入信息位，bi-1 为为bi 前面第一个信息位，前面第一个信息位， bi-2 为为bi 前前面第二个信息位。面第二个信息位。每输入一个信息比特，经编码器产生每输入一个信息比特，经编码器产生2个输出比特个输出比特c1和和c2 。2007年12月51c1和c2与与b

45、i、bi-1、bi-2的关系为的关系为22211iiiiibbcbbbc设起始状态使所有级清零，即设起始状态使所有级清零，即bi bi-1 bi-2 =000，当第当第1位数据为位数据为1时，即时，即bi=1，bi-2 bi-1=00，输出码组，输出码组c1 c2=11。当第当第2位数据为位数据为1时，即时，即bi=1，bi-2 bi-1=01，输出码组，输出码组c1 c2=01。依此类推，可求出所有输入数据输入后的输出码组。依此类推，可求出所有输入数据输入后的输出码组。 2007年12月52若输入数据为若输入数据为11010，编码器的状态如下表所示，编码器的状态如下表所示 表表9-6 图图9

46、-11编码器的状态编码器的状态为保证全部数据通过移位寄存器，还必须在数据后加为保证全部数据通过移位寄存器，还必须在数据后加3个个0。 当第当第4位数据输入时，第位数据输入时，第1位数据移出移位寄存器而消失。位数据移出移位寄存器而消失。 每一位数据影响每一位数据影响3个输出码组，即（个输出码组，即（2，1，3）卷积码的约束度）卷积码的约束度为为3。 bi11010000 bi-2bi-10001111001100000 c1c21101010010110000状态状态abdcbcaa2007年12月53 图解法图解法 用图示的方法描述卷积码的状态和输入输出情用图示的方法描述卷积码的状态和输入输出

47、情况。图解法描述编码过程比较直观。况。图解法描述编码过程比较直观。 树状图树状图 状态图状态图 网格图网格图 解析法解析法 用编码的生成多项式或者生成矩阵描述卷积码用编码的生成多项式或者生成矩阵描述卷积码的状态和输入输出情况。的状态和输入输出情况。 生成多项式生成多项式 生成矩阵生成矩阵2007年12月54 描述在任何数据序列输入时，码组所有可能的输出。描述在任何数据序列输入时，码组所有可能的输出。 对应上面的（对应上面的（2，1，3）卷积码编码器，树状图如下）卷积码编码器，树状图如下把树状图的起始节点放把树状图的起始节点放在最左边。在最左边。 以以bi=0，bi-2 bi-1=00作为起作为

48、起点，用点，用a、b、c和和d表示表示bi-2 bi-1的四种可能状态的四种可能状态00、01、10、11。当第当第1位输入位输入bi=0时，输出时，输出码组码组c1 c2=00。若。若bi=1，则，则c1c2=00。因此从因此从a点出发有两条支路点出发有两条支路（树叉）可供选择。（树叉）可供选择。bi=0时取上支路，时取上支路，bi=1时取下时取下支路。支路。 2007年12月55 输入第输入第2位比特时，移位寄存器状态右移一位，上支路移位寄位比特时，移位寄存器状态右移一位，上支路移位寄存器状态仍为存器状态仍为00，下支路的状态则为，下支路的状态则为01，即状态，即状态b。 新的一位输入比特

49、到来时，随着移位寄存器状态和输入比特的新的一位输入比特到来时，随着移位寄存器状态和输入比特的不同，树状图继续分叉成不同，树状图继续分叉成4条支路，条支路，2条向上，条向上，2条向下。条向下。 如此，即可得到上图所示的二叉树图形。如此，即可得到上图所示的二叉树图形。 树状图中，每条树叉上所标注的是输出比特，每个节点上标注树状图中，每条树叉上所标注的是输出比特，每个节点上标注的为移位寄存器的状态。的为移位寄存器的状态。 由图可以看出，从第三条支路开始，树状图呈现出重复性，即由图可以看出，从第三条支路开始，树状图呈现出重复性，即图中表明的上半部与下半部完全相同，这意味着从第图中表明的上半部与下半部完

50、全相同，这意味着从第4位数据位数据开始，输出码组已与第一位数据无关，这也解释了前述编码约开始，输出码组已与第一位数据无关，这也解释了前述编码约束度为束度为3的含义。的含义。 当输入数据为当输入数据为11010时，沿树状图可得到输出序列为，其路径时，沿树状图可得到输出序列为，其路径如图中虚线所示。如图中虚线所示。 2007年12月56 生成多项式表示生成多项式表示 编码器中输入移位寄存器与模编码器中输入移位寄存器与模2加法器的连接关系以及输加法器的连接关系以及输入、输出序列都可表示为延时算子入、输出序列都可表示为延时算子D的多项式。的多项式。 例如输入序列为例如输入序列为11010的表达式为的表

51、达式为31)(DDDB式中式中D的幂次等于时间起点的单位延时数，一般选择第一个比的幂次等于时间起点的单位延时数，一般选择第一个比特作为时间起点。特作为时间起点。 通常把表示移位寄存器与模通常把表示移位寄存器与模2加法器之间的连接关系多项式称加法器之间的连接关系多项式称为生成多项式。为生成多项式。因为由它们可以用多项式相乘计算出输出序因为由它们可以用多项式相乘计算出输出序列。列。 2007年12月57 若某级寄存器与某个模若某级寄存器与某个模2加法器相连接，则生成多项式相应系加法器相连接，则生成多项式相应系数取数取1，否则取，否则取0。 上面提到的（上面提到的（2，1，3）卷积码的编码器结构可以

52、用以下两个）卷积码的编码器结构可以用以下两个生成多项式描述：生成多项式描述： 211)(DDDG221)(DDG仍以输入数据仍以输入数据11010为例，可得为例，可得5432111)1)(1 ()()()(DDDDDDDBDGDC5232221)1)(1 ()()()(DDDDDDDBDGDC2007年12月582个模个模2和的输出序列分别为和的输出序列分别为 1000111c1110012c输出序列为输出序列为11110101001021cc这个结果和树状图法得到的结果是相同的。这个结果和树状图法得到的结果是相同的。为了方便，可以用二进制数或八进制数来表示生成多项式的系为了方便，可以用二进制

53、数或八进制数来表示生成多项式的系数数82121)7()111(1)(gDDDG82222)5()101(1)(gDDG2007年12月59 代数译码代数译码 利用编码本身的代数结构进行译码，而不考虑信道的统利用编码本身的代数结构进行译码，而不考虑信道的统计特性。计特性。 硬件实现简单，但性能较差。硬件实现简单，但性能较差。 门限译码：从线性译码的校正子出发，找到一组特殊的能够检门限译码：从线性译码的校正子出发，找到一组特殊的能够检查信息位置是否发生错误的方程组，实现纠错译码。查信息位置是否发生错误的方程组，实现纠错译码。 概率译码概率译码 建立在最大似然准则的基础上，在计算时用到了信道的建立在

54、最大似然准则的基础上，在计算时用到了信道的统计特性。统计特性。 提高了译码性能，但同时增加了硬件的复杂性。提高了译码性能，但同时增加了硬件的复杂性。 维特比译码译码：把已经接收到的序列与所有可能的发送序列维特比译码译码：把已经接收到的序列与所有可能的发送序列相比较，选择其中汉明距离最小的一个发送序列作为译码输出。相比较，选择其中汉明距离最小的一个发送序列作为译码输出。 序列译码：在硬件和性能方面介于门限译码和维特比译码之间，序列译码：在硬件和性能方面介于门限译码和维特比译码之间，适用于约束长度很大的卷积码。适用于约束长度很大的卷积码。 2007年12月609.5 9.5 差错控制编码对系统性能

55、的改善差错控制编码对系统性能的改善 这里仅讨论信号功率相同和信道条件相同条件下，纠这里仅讨论信号功率相同和信道条件相同条件下，纠t个差错的情况。个差错的情况。 设在设在T时间内传送时间内传送k位信息码元，对无编码系统，编码位信息码元，对无编码系统，编码前信息传送速率前信息传送速率 与信道传送的信息速率与信道传送的信息速率 相同，即相同，即 但对编码系统，则有但对编码系统，则有 其信息速率比无编码系统高其信息速率比无编码系统高n/k倍。倍。 bRbcRbbc/(bit/s)RRk TbbcRknknTkTnR)/()/)(/(/2007年12月61 传输带宽大传输带宽大n/k倍，信噪比低倍，信噪

56、比低n/k倍，也就导致了误比特倍，也就导致了误比特率高于无编码系统。但译码后的误码组率却明显降低了！率高于无编码系统。但译码后的误码组率却明显降低了！ 对无编码系统，设码组有对无编码系统，设码组有k位码元，则其误码组率为：位码元，则其误码组率为： 通常，有通常，有 ，所以，所以， 。 对编码系统，由于能纠对编码系统，由于能纠t个错，设此时误比特率为个错，设此时误比特率为 ，在在n n位码的码组中有位码的码组中有t t个以上差错时，码组才会出错。在个以上差错时，码组才会出错。在n n位码中错位码中错i i位码的概率为：位码的概率为：kPP)(ew111ePewkPP ecPiniinPPCniP

57、)(),(ecec12007年12月62 由此得误码组率为：由此得误码组率为： 当当 时，时，出现出现t t+1+1个差错的概率远大于出现个差错的概率远大于出现t t+1+1个个以上差错的概率，于是有以上差错的概率，于是有： 设系统采用设系统采用2PSK传输，信息传输速率为传输，信息传输速率为 ，信道白，信道白噪声功率谱密度为噪声功率谱密度为 ，并设，并设 ， 为信号平均功率。则对无编码系统，有：为信号平均功率。则对无编码系统，有： ， ， 。inintiinPPCP)(ecec1wc11ecP1ec1wcttnPCPbR20/nb0iRnS /iSbcbRR 2eQP 2wkQP 2007年

58、12月63 而对编码系统，则而对编码系统，则有有 ， ， 当当n=7，k=4，t=1时，时， 有有 有无纠错时误码组率比较：节省有无纠错时误码组率比较：节省1 dB.bbcRknR)/()/(nkQP2ec11wc2ttnnkQCP)/(24wQP 2wc14121.QP2007年12月649.6 9.6 数字通信系统应用举例数字通信系统应用举例9.6.1 用于市话网的用于市话网的PCM终端设备终端设备 下图是局间交换机使用模拟交换机的情况。其弊端是绳下图是局间交换机使用模拟交换机的情况。其弊端是绳路有限，交换机容量受限，市话网的电缆容量也有限。路有限，交换机容量受限，市话网的电缆容量也有限。

59、2007年12月65 下图是局间直接数字中继传输的情况。下图是局间直接数字中继传输的情况。 两模拟交换机间通过各自的两模拟交换机间通过各自的PCM终端机完成中继，以终端机完成中继，以二次群为例，使用二次群为例，使用2对线，可以替代模拟中继的对线，可以替代模拟中继的120对线。对线。2007年12月66 下图是光纤数字传输系统连接方式图。下图是光纤数字传输系统连接方式图。 1616端端PCMPCM基群单元由基群单元由A A局中继输出，经局中继输出，经2 2、3 3、4 4次群复接次群复接成成140 Mbit/s140 Mbit/s四次群信号。四次群信号经光端机进行光四次群信号。四次群信号经光端机

60、进行光调制，光信号经光缆传输到达光接收端机，经光电检测调制，光信号经光缆传输到达光接收端机，经光电检测器变换，再经分接器分接为器变换，再经分接器分接为1616端端PCMPCM基群信号，接入基群信号，接入B B局局中继入线。中继入线。 2007年12月67 移动通信是指通信的双方至少有一方是移动的。移动通信是指通信的双方至少有一方是移动的。 20世纪世纪80年代发展起来的模拟蜂窝移动通信系统被称为第年代发展起来的模拟蜂窝移动通信系统被称为第一代（一代（1G）移动通信系统。）移动通信系统。 主要技术：模拟调频、码分多址主要技术：模拟调频、码分多址 主要业务：电话主要业务：电话 主要缺点：容量小、干