数字通信基础 差错控制编码

1、差错控制编码差错控制编码1 概述概述 2 常用的几种简单分组码常用的几种简单分组码 3 线性分组码线性分组码 4 循环码循环码 5 卷积码卷积码 差错控制编码差错控制编码一一 概概 述述1.1 信道编码信道编码 在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率， 提高数字通信的可靠性而采取的编码。 数字信号在传输过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。1.2

2、差错控制方式差错控制方式 图 1 差错控制方式 发端纠错码收端前向纠错FEC发端检错码收端检错重发ARQ判决信号发端检错和纠错码收端混合纠错HEC判决信号 1. 检错重发方式检错重发方式 检错重发又称自动请求重传方式，记作ARQ(Automatic Repeat Request)。 由发端送出能够发现错误的码，由收端判决传输中无错误产生，如果发现错误，则通过反向信道把这一判决结果反馈给发端，然后，发端把收端认为错误的信息再次重发，从而达到正确传输的目的。其特点是需要反馈信道，译码设备简单，对突发错误和信道干扰较严重时有效， 但实时性差，主要在计算机数据通信中得到应用。 2. 前向纠错方式前向纠

3、错方式 前向纠错方式记作FEC(Forword ErrorCorrection)。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。其特点是单向传输，实时性好，但译码设备较复杂。 3. 混合纠错方式混合纠错方式 混合纠错方式记作HEC(Hybrid ErrorCorrection)是FEC和ARQ方式的结合。发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力， 但能检测出来，则经过反馈信道请求发端重发。这种方式具有自动纠错和检错重发的优点，可达到较低的误码率，因此， 近年来得到广泛应用。 另外

4、，按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。具有脉冲干扰的信道是典型的突发信道， 错误是成串成群出现的，即在短时间内出现大量错误。短波信道和对流层散射信道是混合信道的典型例子，随机错误和成串错误都占有相当比例。对于不同类型的信道，应采用不同的差错控制方式。 1.3 纠错码的分类纠错码的分类 (1) 根据纠错码各码组信息元和监督元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。 (2) 根据上述关系涉及的范围，可分为分

5、组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关， 而且还与前面若干组的信息元有关。 (3) 根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。 1.4 纠错编码的基本原理纠错编码的基本原理 1. 分组码分组码 分组码一般可用(n,k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元， 组成长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2

6、k个不同的码字，称为许用码组。其余 2n-2k个码字未被选用，称为禁用码组。 在分组码中，非零码元的数目称为码字的汉明重量， 简称码重。例如，码字 10110，码重w=3。 两个等长码组之间相应位取值不同的数目称为这两个码组的汉明(Hamming)距离， 简称码距。例如 11000 与 10011之间的距离d=3。码组集中任意两个码字之间距离的最小值称为码的最小距离，用d0表示。最小码距是码的一个重要参数， 它是衡量码检错、纠错能力的依据。 2. 检错和纠错能力检错和纠错能力 若分组码码字中的监督元在信息元之后，而且是信息元的简单重复， 则称该分组码为重复码。它是一种简单实用的检错码， 并有一

7、定的纠错能力。例如(2,1)重复码，两个许用码组是 00 与 11，d0=2，收端译码，出现 01、10 禁用码组时，可以发现传输中的一位错误。如果是(3,1)重复码，两个许用码组是 000 与111, d0=3; 当收端出现两个或三个 1 时，判为 1，否则判为 0。此时，可以纠正单个错误，或者该码可以检出两个错误。 码的最小距离d0直接关系着码的检错和纠错能力；任一(n,k)分组码，若要在码字内: (1) 检测e个随机错误，则要求码的最小距离d0e+1; (2) 纠正t个随机错误， 则要求码的最小距离d02t+1; (3) 纠正t个同时检测e(t)个随机错误，则要求码的最小距离d0t+e+

8、1。 3. 编码效率编码效率 用差错控制编码提高通信系统的可靠性， 是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性:R=k/n其中, k是信息元的个数，n为码长。 对纠错码的基本要求是: 检错和纠错能力尽量强； 编码效率尽量高；编码规律尽量简单。 实际中要根据具体指标要求，保证有一定纠、 检错能力和编码效率，并且易于实现。 二二 常用的几种简单分组码常用的几种简单分组码2.1 奇偶监督码奇偶监督码 奇偶监督码是在原信息码后面附加一个监督元， 使得码组中“1”的个数是奇数或偶数。或者说，它是含一个监督元，码重为奇数或偶数的(n,n-1)系统分组码。奇偶监督码又分为奇监督码和偶监督码。

9、设码字A=an-1,an-2,a1,a0，对偶监督码有 00121aaaann 奇监督码情况相似， 只是码组中“1”的数目为奇数， 即满足条件 1021aaann而检错能力与偶监督码相同。 奇偶监督码的编码效率R为 nnR/ ) 1( 检错能力为能够检测出奇数位错。 2.2 行列监督码行列监督码 图 2 (66,50)行列监督码 特殊情况下（一行一列）具有纠错能力，同行（列）有偶数错无法纠错，方阵四个顶角有错时无法检测出来。 1100101000001000011010011110000111001110000010101010101110001111001 11 10 00 01 10 01

10、 10 00 00 01 10 01 10 00 00 00 01 11 10 01 10 00 01 11 11 11 10 00 00 00 01 10 01 10 00 01 11 11 10 00 00 00 00 01 10 01 10 01 10 01 10 01 10 01 11 10 01 10 01 11 11 10 01 10 00 02.3 恒比码恒比码 码字中 1 的数目与 0 的数目保持恒定比例的码称为恒比码。 由于恒比码中，每个码组均含有相同数目的 1 和 0，因此恒比码又称等重码，定 1 码。这种码在检测时，只要计算接收码元中 1 的数目是否正确，就知道有无错误。

11、 目前我国电传通信中普遍采用 3 2 码，又称“5 中取 3”的恒比码，即每个码组的长度为 5，其中 3 个“1”。这时可能编成的不同码组数目等于从 5 中取 3 的组合数 10，这 10 个许用码组恰好可表示 10 个阿拉伯数字，如表 9 - 1 所示。而每个汉字又是以四位十进制数来代表的。实践证明，采用这种码后，我国汉字电报的差错率大为降低。 表表 1 3 2 恒比码恒比码 三三 线线 性性 分分 组组 码码 3.1 现以(7,4)分组码为例来说明线性分组码的特点。设其码字为A=a6 a5 a4 a3 a2 a1 a0，其中前 4 位是信息元，后 3 位是监督元， 可用下列线性方程组来描述

12、该分组码，产生监督元。346035614562aaaaaaaaaaaa表表 2 (7,4)码的码字表码的码字表 码字码字序序号号序序号号码字码字信息元信息元监督元监督元信息元信息元监督元监督元0 00 0 0 00 0 0 00 0 00 0 08 81 0 0 01 0 0 01 1 11 1 11 10 0 0 10 0 0 10 1 10 1 19 91 0 0 11 0 0 11 0 01 0 02 20 0 1 00 0 1 01 0 11 0 11 10 01 0 1 01 0 1 00 1 00 1 03 30 0 1 10 0 1 11 1 01 1 01 11 11 0 1

13、11 0 1 10 0 10 0 14 40 1 0 00 1 0 01 1 01 1 01 12 21 1 0 01 1 0 00 0 10 0 15 50 1 0 10 1 0 11 0 11 0 11 13 31 1 0 11 1 0 10 1 00 1 06 60 1 1 00 1 1 00 1 10 1 11 14 41 1 1 01 1 1 01 0 01 0 07 70 1 1 10 1 1 10 0 00 0 01 15 51 1 1 11 1 1 11 1 11 1 13.2 监督矩阵监督矩阵H和生成矩阵和生成矩阵G（7，4）码的）码的3个监督方程式个监督方程式 为为线性方程

14、可用矩阵形式表示为线性方程可用矩阵形式表示为010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa0001001101010101100101110123456aaaaaaa并简记为其中， AT是A的转置，OT是O=0 0 0的转置，HT是H的转置。OAHOHATTT或100110101010110010111HH称为监督矩阵，一旦H给定，信息位和监督位之间的关系也就确定，简称H矩阵，H矩阵每行之间是彼此线性无关的。式（97）所示的H矩阵可以表示为rIPH100110101010110010111 其中,P为rk阶矩

15、阵，Ir为rr阶单位矩阵。可以写成H=P Ir形式的矩阵称为典型监督矩阵。 HAT=0T，说明H矩阵与码字的转置乘积必为零，可以用来作为判断接收码字A是否出错的依据。 若把监督方程补充为下列方程 0123456aaaaaaa6a5a4a3a456aaa56aa 6a3a34aa 可改写为矩阵形式 345601234561101101101111000010000100001aaaaaaaaaaa3456aaaaGATT3456aaaaGA1101000101010001100101110001GQIGkTPQ1101010111113.3 伴随式伴随式(校正子校正子)S 设发送码组A=an-1

16、,an-2,a1,a0，在传输过程中可能发生误码，设接收码组B=bn-1,bn-2,b1,b0，则收发码组之差定义为错误图样E， 也称为误差矢量， 即 ABE其中E=en-1,en-2,e1,e0，且 10ie当bi=ai 当biai (9 - 15) 式(9 - 15)也可写作 EAB令S=BHT，称为伴随式或校正子。 TTTEHHEABHS)(OAHT因为 表表 3 ( 7,4)码码S与与E的对应关系的对应关系 线性分组码具有封闭性：在一组线性码中，任意两个线性分组码具有封闭性：在一组线性码中，任意两个码组之和仍为该种码中的一个码组。码的最小距离也是码码组之和仍为该种码中的一个码组。码的最

17、小距离也是码的最小重量。的最小重量。 由于线性码具有封闭性，当由于线性码具有封闭性，当E=A时，时，S=0，认为无错，认为无错码，即不能检测错码，需要计算出不能检错的概率。码，即不能检测错码，需要计算出不能检错的概率。设（设（n,k）线性分组码最大能检错位数为）线性分组码最大能检错位数为D，发送，发送“0”、“1”等概，信道误码率为等概，信道误码率为Pe，则不能检错的概率为，则不能检错的概率为ineienDiiuppWP)1 (1其中其中Wi为重量为为重量为i的许用码组数。的许用码组数。 4 循循 环环 码码表表 4 (7,3)循环码循环码 在代数理论中，为了便于计算，常用码多项式表示码字。(

18、n,k)循环码的码字，其码多项式(以降幂顺序排列)为 012211)(axaxaxaxAnnnn其中幂的次数对应2进制数的权重位，乘x表示左移一位。4.1 生成多项式及生成矩阵生成多项式及生成矩阵 如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。在(n,k)循环码中任意码多项式A(x)都是最低次码多项式的倍式。如表 9-4 的(7,3)循环码中， 1)()(2341xxxxAxg)()()()()() 1()()(0)(27320 xgxxAxgxxAxgxxAxgxA其它码多项式都是g(x)的倍式， 即 循环码的生成矩阵常用多项式的形式来表示 1)(111x

19、gxgxxgrrr)()()()()(21xgxxgxgxxgxxGkk例如(7,3)循环码，n=7, k=3, r=4, 其生成多项式及生成矩阵分别为 生成多项式转换成的生成矩阵，还要利用初等行变换转换成典型生成矩阵G=IkQ形式，才能按线性分组码的方法计算编码结果和计算校正子进行检错与纠错。101110011100100111001G1000110010001100101110001101H4.2 监督多项式及监督矩阵监督多项式及监督矩阵 为了便于对循环码编译码，通常还定义监督多项式， 令 1)(1)(111xhxhxxgxxhkkkn其中g(x)是常数项为 1 的r次多项式，是生成多项式

20、；h(x)是常数项为 1 的k次多项式，称为监督多项式。同理，可得监督矩阵H )(*)(*)(*)(1xhxxhxhxxHkn是h(x)的逆多项式。例如(7，3)循环码，g(x)=x4+x3+x2+1，则 其中 1)(*12211xhxhxhxxhkkkk1)(*1)(1)(3237xxxhxxxgxxh1)(324235346xxxxxxxxxxxxH1101000011010000110100001101H1000110010001100101110001101H利用初等行变换转换成典型生成矩阵H=P Ir形式4.3 编码方法和电路编码方法和电路 在编码时，首先要根据给定的(n,k)值选定

21、生成多项式g(x)，即应在xn+1的因式中选一r=n-k次多项式作为g(x)。设编码前的信息多项式m(x)为 12321)(kkxaxaxaaxm循环码（系统码）的码多项式可表示为 )()()(xrxmxxAr)()()()()(xgxrxNxgxmxr 编码时将m(x)左移r位（到最左侧），被生成多项式除，余式就是r(x)，放在m(x)之后。图 9-3 (7,3)循环码编码电路 D0D1D2D3门1门2输入信息组输出码字11)(234xxxxg100001001011000101000101000100010100111000110100110123ODDDDFA表表 9-5 (7,3)循环

22、码的编码过程循环码的编码过程 9.4.4 译码方法和电路译码方法和电路 图 4 (7,3)循环码译码电路 D0D1D2D37级缓存器接收码组B输出码组A& 译码时B(x) 被生成多项式g(x)除，余式就是r(x)，计算或查表得到S(x)不为0则检测出错误，能与E(x)对应则可纠错。+1000000000000001000000000100001000000000000011011011011001111000101000010000010010110123ADDDDFB11011000001000010010100001000010111111110000000001011111011

23、111011011001001000000000010011110123ADDDDFB11100001000000001010010000100011000010111100000001111001111001010101000011000000000010010010123ADDDDFB10111101110001011010001000010010100011000000000000101010101010010010001110000100000010010100123ADDDDFB卷积码卷积码(n,k,N)表示码组长度为表示码组长度为n，信息元为，信息元为k位，与位，与N个信息段个信息

24、段（包括当前信息段）的信息元有关。（包括当前信息段）的信息元有关。图 5 卷积码(2,1,3)编码器5.1 基本概念基本概念 m1m2数据输入码字输出S1S2S3C1C2五五 卷卷 积积 码码 起始状态，各级移位寄存器清零，即S1S2S3为000。S1等于当前输入数据，而移位寄存器状态S2S3存储以前的数据，输出码字C由下式确定 3123211SSCSSSC表 6 (2,1,3)编码器的工作过程 5.2 卷积码的描述卷积码的描述 1. 树图树图 图图 6 (2,1,2)码的树图码的树图 a1100abb0110cdc0011abd1001cd0010a1101ba0011a1100abb011

25、0cdc0011abd1001cd1101c0010db1001a1100数码起点状态a00b01c10d11上半部下半部数码1101S3S2为状态标记为状态标记 S1只能为只能为0、1 2. 状态图状态图 图 7 (2,1,3)码的状态图 a00b01c10d11cbad01011111001000103. 格图格图 图 8 (2,1,3)码的格图 a00起点aaaaaabbbccccbbcbddddd0000000000000000001001010101010101101010101111111111111010101001015.3 卷积码的译码卷积码的译码 卷积码的译码分为两大类：大

26、逻辑数译码，又称门限译码；卷积码的译码分为两大类：大逻辑数译码，又称门限译码；概率译码，如维特比译码、序列译码。概率译码，如维特比译码、序列译码。1. 大逻辑数译码大逻辑数译码设设(2,1,6)卷积码编码规则：卷积码编码规则：b为信息元，为信息元， c 为卷积码的监督元。为卷积码的监督元。665544332211cbcbcbcbcbcb 译码时，将译码时，将b移位寄存并再编码得移位寄存并再编码得c，与，与c比较得误差比较得误差e，列，列出校正子约束方程。根据正交于出校正子约束方程。根据正交于e11错误元的一致校验和式错误元的一致校验和式Si表达表达式可知，连续式可知，连续12位中如错误样图位中

27、如错误样图E中错误位数不多于中错误位数不多于2位，且其位，且其中一位发生在中一位发生在e11，则，则Si 3；如果如果E中错误位数不多于中错误位数不多于2位，且位，且 e11位上未发生错误，则位上未发生错误，则Si2。因此进行大数判决，决定是否对因此进行大数判决，决定是否对e11进行纠正。进行纠正。12366bbbbc 将最大似然算法加以简化，得到维特比译码。将最大似然算法加以简化，得到维特比译码。 其方法为：所已接收到的码序列与所有可能的发送序列做比其方法为：所已接收到的码序列与所有可能的发送序列做比较，选择其中码距最小的序列作为判决（发送）序列。较，选择其中码距最小的序列作为判决（发送）序

28、列。 设发送为设发送为L组组k位的序列，则共有位的序列，则共有2kL种排列方法，将这些序种排列方法，将这些序列存储并与接收序列进行比较，找到码距最小的序列作为判决序列存储并与接收序列进行比较，找到码距最小的序列作为判决序列，即最大似然解码。维特比译码对此做了简化，即分段比较选列，即最大似然解码。维特比译码对此做了简化，即分段比较选择，最终达到整个序列是一个最大似然序列，成为实用算法。择，最终达到整个序列是一个最大似然序列，成为实用算法。2. 维特比译码维特比译码 图图 9 维特比译码格图维特比译码格图 图79起点d80100(4)cba700(3)6500(3)4300(3)200(2)10 00(1)级11(1)11(3)11(3)11(3)10(2)10(4)00(3)01(3)01(3)10(3)10(3)10(3)01(1)01(1)01(5)00(2)11(2)收码01011010010001解码11010000 上下支路均保留，封闭时再去掉。上下支路均保留，封闭时再去掉。 3. 序列译码序列译码 当m很大时，可以采用序列译码法。 其过程如下： 译码先从码树的起始节点开始，把接