第9章 差错控制编码1

通信原理电子教案

第9章差错控制编码西北工业大学（2012.5）2/5/20231干扰乘性：均衡加性：调制解调体制、发送功率、最佳接收9.1引言

一、编码问题的提出

由于数字信号在传输过程中必不可免的受到干扰的影响，使码元波形变坏，故传输到接收端后可能发生错判。信道译码检/纠错编码若还不行，则需－－差错控制编码。目的：在数字通信系统中，为了提高数字通信的可靠性而采取的编码称为信道编码。差错可控之前：为了提高数字信号传输的有效性而采取的编码称为信源编码。如：PCM二、方法/模型2/5/20232研究问题：9.1引言9.2差错控制编码的基本概念

9.3常用的简单检错码

9.4线性分组码9.5循环码

9.6检测和纠正突发错误的分组码——交织码

9.7卷积码

9.8网格编码调制(TCM)

2/5/202331.随机性差错：差错是随机的且相互之间独立—单个错。通常由高斯白噪声引起。突发性差错：错误之间有相关性----成串错。由脉冲性干扰引起，在短暂的时间内出现连续的差错，而这些短暂时间之后却又存在较长的无误码区间。9.2.1差错类型9.2

纠错编码的基本概念3.混合性差错：既存在随机差错又有突发性差错。以上两种错误性质不同，可分别处理。2/5/20234可以用来检测一位错误可纠正一位错误或检测两位错误AB

许用码组禁用码组

00

01

11

10

采用2位二进制码许用码组禁用码组

000

001010100

111

101110

011采用3位二进制码采用1位二进制码019.2.2差错控制的基本方法

在信息序列之后附加一些监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联，接收端按照既定的规则检验出关联关系，如这种规则受到破坏，将会发现错误，乃至纠正错误。例：2/5/20235检错与纠错能力与最小码距d0

的关系(c)为了同时检测e个错误，纠正t个错误d0

≧

e＋t＋1，e>t(b)为了纠正t个错误d0

≧2t＋1(a)为了检测e个错误，d0

≧

e＋1码距：两个码组对应位上不同的数目。码重：码组中“1”的数目。结论：最小码距决定检错和纠错能力。2/5/202369.2.3差错控制方式2.前向纠错（FEC）

可纠错的码

发

收3.混和纠错（HEC）

可以发现和纠正错误

发

收

应答信号

比较：译码复杂性、实时性和占用传输链路(单向还是双向)。1.检错重发（ARQ）

可检错的码

发收

应答信号ARQ：自动重复请求发送接收端所识别到的错误超过了自身的纠错能力时，就请求发送端重发。2/5/202379.2.4差错控制编码的效用

假设在随机信道中发“0”和发“1”的概率相同，在码长为n的码组中恰好发生r个错误的概率为：(p为误码率)当码长n＝7，误码率时，则有：结论：采用差错控制编码，即使仅能纠正（或检测）1～2个错误，就能使误码率下降几个数量级。（9.2-4）2/5/202389.2.5纠错码的分类1.分组码与卷积码分组码：将信息码分组，为每组信息码后面附加若干位监督码元，且

监督码元仅监督本码组中的信息位。卷积码：将信息序列分组，后面附加监督位，但监督位不但与本码组的信息位有关，还与前面码组的信息位有关，或者说监督位不仅监督本码组的信息位还监督其它码组的信息位。2.系统码与非系统码系统码：

就是信息位在前，监督位在后的码字。非系统码:信息位与监督位之间无特定的位置关系。编码效率：k/n（n，k）码

2/5/202399.3常用的简单纠错码9.3.1

奇偶校验构成：n-1位信息位、1位监督位。n位编码构成以下约束关系接收端计算校正子（偶监督）检错能力：所有奇数个错误。一半！应用非常广泛。编码效率：2/5/2023109.3.2纵向奇偶校验（LRC）－用于检测突发错误1110011111011101001110011010100111100111110111010011100110101001纵向排列原始数据1110011111011101001110011010100110101010突发错误接收方检验是否满足LRCLRC

10101010监督码元交织编码：针对突发性错误n位的LRC可以检测一个n位突发错误。2/5/202311

信息

码

元

0101101100010101001000110000111100011100001111111100010011111110110000监督码元

0011100001

0监督码元

10010119.3.3水平垂直奇偶校验（二维）●它能发现某一行或某一列上所有奇数个错误以及长度不大于行数（或列数）的突发错误。●可检某些偶数个错误。

●具有一定的纠错能力。2/5/2023129.3.4群计数码111001100信息位监督位功能：发现所有奇数个错误，以及一些偶数个错误，除“0”变“1”，和“1”变“0”成对出现。规则：信息码元分组后计算“1”的个数，然后将这个数目的二进制码元表示作为监督码元附加在信息码元之后。2/5/2023139.3.5等重码（恒比码）功能：检测所有奇数个错误，以及一些偶数个错误，除“0”变“1”，和“1”变“0”成对出现。数字电码数字电码

001101500111101011610101211001711100310110801110411010910011表9-3电传五中取三码许用码组:C35=10禁用码组:25-10=22编码效率：等重码是从特定码长的码组中，选取固定个数的“1”作为码组的许用码组，这种码de码重相同，或“1”与“0”之比保持恒定。例：我国电传汉字电码，每个汉字用4位阿拉伯数字表示，每个阿拉伯数字又用5位二进制符号表示，其中3个“1”，码重为3。2/5/2023149.4

线性分组码定义：信息位和监督位之间的关系由线性方程组约束的分组码称作线性分组码。特征：督元由信元的线性组合而产生。奇偶校验码就是一种效率很高的线性分组码。这里S称为校正子：若S＝0，表示无错，S＝1表示有错。

●因仅用了1位监督位a0，所计算的1个校正子只能表示有错与无错。

●若监督位增加到2位，就可增加一个监督方程式，便可获得2个校正子S1、S2，于是：2/5/202315推广：显然：要求2r-1≥n（n=k+r），则可指示（仅一位错时）任一错码的位置－－包括信元、督元。 或： 2r≥k+r+1对于二进制编码，知道了错误的位置，就可以实现纠错了。2/5/202316●一般说来对于(n，k)码。要想指出一位错码的所有可能位置，则要求：对于纠正t个错误，需满足：（纠正1个错误）2/5/2023179.4.1线性分组码的构成例：构造k＝4的汉明码（能纠一位错的线性分组码）。（1）确定r

由得r≧3，取r＝3，则n＝7。（7,4）码！（2）写出校正子的编码表2/5/202318表9-4校正子表

S1S2S3误码位置

S1S2S3

误码位置

001

a0101a4

010a1110a5

100a2111a6

011a3000无错因此接收端计算下面3个校验关系，可确定误码的位置:校正子表不是唯一的!这里的“+”代表模2和

（2）写出校正子的编码表----r=3共有3个校正子2/5/202319发送端构成偶校验方程→可得督--信方程（线性组合）表9-516个许用码组！信息位监督位信息位监督位

0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111（3）生成全部许用码组2/5/2023209.4.2线性分组码的监督矩阵和生成矩阵1.

监督矩阵－从校验方程入手记为或有2/5/202321其中：----监督矩阵

----码组的行矩阵

----零矩阵

可见：H一旦确定，督元和信元之间的关系也就确定了。若:----则称H为典型阵。由线性代数理论：典型阵各行一定是线性无关的；非典型阵可通过矩阵的初等变换化为典型阵。2/5/2023222.生成矩阵矩阵形式:－－从督信方程入手由2/5/202323写成行阵形式:其中Q=PT。上式表明：信息位给定后，就产生了监督位！进一步，令生成矩阵

G=[IkQ]则，码组行阵 A=[a6a5a4a3]G

Q能生成督元G才生成线性分组码如何装配：信元＋督元？2/5/202324例：生成矩阵讨论：●由信息位与生成矩阵G相乘可得到全部码字A。●具有[IkQ]形式的生成矩阵称为典型生成阵。●由典型生成矩阵得出的码组为系统码。码组行阵：督元由相应的信息位决定！2/5/202325一般形式:

A=[an-1an-2…ar]G

3.G和H的关系由Q=PT或P=QT

则:H=[P·Ir

]

G=[Ik·Q]综上：线性分组码的编码，就是根据其监督阵H或生成阵G将长为k的信息码编成长为n的码组。2/5/2023264.线性分组码的性质（1）封闭性

设：

A1、A2分别为一线性分组码的任意两个许用码组。则：A1+A2

仍为该线性分组码的许用码组。证：由假设知 A1HT=0、A2HT=0

所以 A1HT+A2HT=（A1+A2）HT＝0

即A1+A2也是一个码组。结论：线性码组中任意两个码字之和，仍为该线性码组之码字。（2）线性分组码的最小距离等于非零码的最小重量。即

: d0=Wmin（除全0码组）证：由封闭性得，两个码组之间的距离（之差），必是另一码组的重量。故最小码距即是码的最小重量！2/5/2023279.4.3线性分组码的伴随式译码设：发送码组为A，接收码组为R。则：

R-A＝E（模2）

为错误行阵或错误图样。对于前面（7，4）码的例子，一位错误图样为：(1000000),(0100000)，(0010000)，(0001000)，(0000100)，(0000001),(0000001)计算校正子或伴随式：结论：校正子S仅与错误图案有关，与发送码组无关。2/5/202328伴随式与纠错：结论：校正子S只与E有关，若接收码字R中第i位有错，那么导出的伴随式恰好同于监督矩阵H的第i列。例：对于前面（7，4）码例子，一位错误图样为：(1000000),(0100000)，(0010000)，(0001000)，(0000100)，(0000001),(0000001)，分别计算当错误图样为上面七种形式之一时的伴随式值。2/5/202329结论：利用伴随式不仅可以判决接收码字中是否有错，而且可以指出差错的位置。2/5/202330例：若接收的码组为1001101，请指出错误位置并译码。解：计算伴随式

最后一位有错，译码得：1001100。2/5/2023319.5.1循环码的概念

定义：是一种具有循环移位特性的线性分组码。

特点：编译码设备简单；检纠错能力强。

9.5

循环码

构成原理：

具有线性分组码的所有性质之外，还具有循环性：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。2/5/202332码多项式定义：

为了利用代数理论研究循环码，可以将码组用代数多项是来表示，这个多项式被称为码多项式。设：许用循环码A=(an-1

an-2…a1

a0)则：它的码多项式表示为：其中：xi仅是码元位置的标记。码字与码多项式一一对应！2/5/202333表9-6(7，3)循环码反之，由码多项式易得出码组。2/5/2023342.码多项式的按模运算1）整数的按模运算若一个整数m可以表示为:则在模n运算下，有m≡p（模n）。例：同样对于多项式而言，也有类似按模运算。2/5/202335其中：商Q(x)为多项式，余数R(x)的幂次低于N(x)的幂次。例:求

x4+x2+1按模

x3+1运算的余式R(x)2）码多项式的按模运算 若则2/5/202336

3）循环性可以证明：在循环码中，若A(x)是一个长为n的许用码组，则xiA(x)在按模xn+1运算下，亦是许用码组。即若有则A'(x)也是一个许用码组。例:前述（7，3）码：A(x)=x6+x5+x4+x2（1110100）－－前码组循环左移1位！多项式除法：余式2/5/2023379.5.2循环码的生成多项式g(x)（1）存在性(n，k)循环码中有且仅有一个g(x)，为

g(x)=xn-k+……+1特点:最高的次数为n-k=r；常数项系数必为1。在循环码中，除了全0码组外，再也没有连续k位均为0的码组。即连0长度最多为k-1位！这唯一的n-k次多项式称为生成多项式，记为g(x)！2/5/202338（2）生成多项式g(x)与生成矩阵G(x)的关系A=[an-1…ar

]GG=[IkQ]∵生成矩阵G的每一行都是一个码组；G是k行n列矩阵。∴只要找到k个已知码组，就能构成生成矩阵G！生成多项式确定后，则g(x)、x

g(x)、……、xk-1

g(x)都是码组，且这k个码组信息无关，因此可以用来构成生成矩阵。g(x)确定了→G(x)也就确定了→整个码组即确定！2/5/202339例:

(7，3)循环码，g(x)=x4+x2+x+1求典型生成矩阵解:可方便地直接写成码组形式典型阵:2/5/202340（3）生成多项式g(x)与码多项式A(x)的关系－－（7，3）表明：所有A(x)都可以被g(x)整除，而且任一次数不大于(k-1)的多项式乘以g(x)都是码多项式。

A(x)∣模g(x)=0。h(x)为不大于(k-1)的多项式！2/5/202341结论:

g(x)是xn+1的一个(n-k)次的因子，且常数项不为零。证明：任一循环多项式A(x)都是g(x)的倍式，即而生成多项式g(x)本身也是一个码组，即有由于码组A'(x)为一（n-k）次多项式，故xkA'(x) 为一n次多项式。由知，xkA'

(x)在模（xn+1）的运算下，亦为一码组，故可写成（4）如何寻找g(x)2/5/202342上式左端分子和分母都是n次多项式，故商Q(x)＝1，因此上式可化成即将A(x)=h(x)g(x)、A'(x)=g(x)代入，并整理，得表明:

g(x)应该是xn+1的一个因式！证得:

g(x)是xn+1的一个(n-k)次的因子，且常数项不为零。2/5/202343例：如(x7+1)=(x+1)(x3+x2+1)(x3+x+1)则有g(x)：（7，4）：x3+x2+1、x3+x+1（7，3）：(x+1)(x3+x2+1)、(x+1)(x3+x+1)（7，6）：x+12/5/202344例:

（7，3）循环码有多项式如下，找出（7，3）码的生成多项式g(x)。（1）x4+x3+x （2）x3+x2+1（3）x+1（4）x4+x2+x+1（5）x4+x+1解:依据r=7-3=4，常数项不为零，有

（4）x4+x2+x+1（5）x4+x+1还须证其是不是xn+1=x7+1的因子?x7+1=(x4+x2+x+1)(x3+x+1)+0x7+1=(x4+x+1)(x3+1)+

(x2+x)故:仅有x4+x2+x+1为生成多项式g(x)。2/5/202345表9-7(7,k)循环码结论：循环码完全由其码组长度n及生成多项式g(x)决定。表中：h(x)称为监督多项式。2/5/202346例9.5.1

一个(7，4)循环码的生成多项式为确定该循环码的典型化的生成矩阵和监督矩阵。解：由g(x)构成的生成矩阵为：典型生成矩阵：典型监督矩阵：2/5/2023479.5.3系统循环码的编码实现系统码组中的最左边的k位是信息码元，随后是n-k位的监督码元，即码多项式为：因此：

有：结论（编码步骤）：m(x)xn-k/g(x)除法求余得到r

(x)；

m(x)xn-k+r(x)求得A(x)。m(x)—信息多项式r(x)—监督多项式2/5/202348例9.5.2已知(7，4)循环码的生成多项式为若信息码为1001

，求编码码字。因此：解：

即：编码码组为：1001011或：直接由信息码元1001+监督码元011拼接而成！2/5/202349上述编码过程，在硬件实现时，可以利用除法电路（曹志刚p344－348）来实现。编码的电路2/5/202350工作过程：信息输入时，开关合2：输入码一方面输入除法器，另一方面直接输出，在信息位全部进入除法器后－－开关合1：输出端接到移位寄存器，将移位寄存器中存储的余项依次输出，同时切断反馈线。系统码！2/5/202351循环码的译码可以分三步进行：（1）由接收到的码多项式R(x)计算校正子（伴随式）多项式S(x)；（2）由校正子S(x)确定错误图样E(x)；（3）将错误图样E(x)与B(x)相加，纠正错误。9.5.4循环码的译码2/5/2023529.6交织码，9.7卷积码，9.8TCM为选讲内容可根据课时情况选择讲授2/5/202353前面介绍的线性分组码和循环码都是用来纠正随机错误的，交织码是一种纠正和检测突发错误的分组码。在纵向奇偶校验码中，按列进行检验，就可以检测出每一行上不超过列数的突发性错误，这种方法同样可以用于纠正突发性错误，由此构造的纠错码称为交织码。

*9.6纠正和检测突发错误的分组码---交织码2/5/202354（1）若将能纠正t个随机错误的码作为方阵的行码，m个行码组构成一个方阵，这种交织码保证可以纠正t个突发长度为m的突发错误。（2）但若将能纠正b个突发错误的码作为行码，则m个行码组构成的方阵，可以保证纠正长度为b·m个突发错误。m行、n列交织度m2/5/202355

编码器输出时，按列的顺序自左至右读出，这时的序列为:在接收端，将上述过程逆向重复，即把收到的序列按列写入存储器再按行读出，这时就仍然恢复成原来的(n,k)分组码交织码实际上是一种时间扩散技术，当交织度足够大时，就把突发错误离散成随机错误，从而被分组码所纠正,但是m受到传输时延的限制。2/5/202356因而(m

n,m

k)也是循环码，(n,

k)码中每一个码组在(m

n,m

k)码中对应有一个码组，它们有相同的码重只是各码元相隔

m位。

采用循环码构造交织码时，不必用n×m阵列就能实现编码，假设交织码每行为(n,k)循环码，其生成多项式为g(x)，则g(x)必定能除尽xn+1。交织度为m的交织码(m

n,m

k)，其生成多项式为，它的物理意义是在g(x)的各项之间插入(m-1)个0，显然能除尽

。2/5/202357

例：用生成多项式为的（7，4）线性分组码，构成交织度为3的（21，12）交织码，求交织码的生成多项式及监督矩阵。＋＋输入(7,4)码编码器＋＋输入(21，12)码编码器交织码译码时，必须将码元排列成n×m阵列，然后分别独立的对其进行译码。2/5/202358*9.7卷积码(n，k，N)卷积码通常用（n,k,N)来表示，它是把k个信息比特编成n个编码比特，其中N定义为编码约束长度，说明编码过程中互相约束的码段个数。

卷积码的编码器具有记忆性，任意时刻输出的n个比特，不仅与当前输入的k比特有关系，还与前N-1个k比特输入有关。因此，编码过程中相互关联的码元就有nN个。定义ηc=k/n为卷积码的编码效率，ηc和N是衡量卷积码性能的两个重要参数。由于卷积码的编码过程充分利用了各码组的相关性，且n和k也较小，因此，在与分组码相同的编码效率下，卷积码的性能更优。在相似的纠错能力下，卷积码的实现通常比分组码更加简单。

2/5/202359图9-15卷积编码器的一般形式9.7.1

卷积码的基本原理

注：模2加法器输入端的数目不一定相同。2/5/202360图9-16(3,1,3)卷积码编码器(3,1,3)卷积编码器的输入与输出逻辑关系为：(9.7-1)

例：以一个简单的(3,1,3)卷积码为例来简述卷积码的编码过程，此时最高的编码效率为ηc=1/3。

2/5/202361图9-17(3,1,3)卷积码树状图

(每输入0或1时输出状态)9.7.2卷积码的图解表示2/5/202362图9-21闭合型状态图a,b,c,d

为移位寄存器状态图9-19(3,1,3)卷积码网格图输入码：10101状态：1001100110输出码：111001100001100

2/5/2023639.7.3卷积码的解析表示生成多项式(9.7-