通信原理差错控制编码-课件

本章内容第11章差错控制编码

基本概念—差控方式编码原理

码距

码率

性能简单实用码—奇偶监督恒比码

线性分组码—汉明码监督矩阵H、生成矩阵G

循环码—生成多项式编译方法BCH码RS码卷积码—编译原理代数表述几何表述本章内容第11章差错控制编码基本概念—差§11.1

概述§11.1概述开销。这就好像我们运送一批玻璃杯一样，为了保证运送途中不出现打烂玻璃杯的情况，我们通常都用一些泡沫或海棉等物将玻璃杯包装起来，这种包装使玻璃杯所占的容积变大，原来一部车能装5000个玻璃杯的，包装后就只能装4000个了，显然包装的代价使运送玻璃杯的有效个数减少了。为保证运送途中不出现打碎灯泡的情况——有效性——可靠性开销。这就好像我们运送一批玻璃杯一样，为了保证运送途中不出现

通信中的情况：开销。这就好像我们运送一批玻璃杯一样，为了保证运送途中不出现打烂玻璃杯的情况，我们通常都用一些泡沫或海棉等物将玻璃杯包装起来，这种包装使玻璃杯所占的容积变大，原来一部车能装5000个玻璃杯的，包装后就只能装4000个了，显然包装的代价使运送玻璃杯的有效个数减少了。针对乘性干扰针对加性干扰合理选择调制/解调方法，增大发射功率—采用均衡等措施通信中的情况：开销。这就好像我们运送一批玻璃杯一样，为了保

差错控制编码差错控制编码

信道类型——根据错码的不同分布规律分为：

差错控制方式：

差错控制方式（ARQ）（FEC）——

——自动请求重发信道类型——根据错码的不同分布规律分为：差错控制方式

缺点：工作在半双工状态，传输效率较低。

3种自动要求重发(ARQ)系统（1）停止等待ARQ系统缺点：工作在半双工状态，传输效率较低。3种自动要求重系统需要双工信道。（2）拉后ARQ系统第5组传输速率比第（1）种高。系统需要双工信道。（2）拉后ARQ系统第5组传输速（3）选择重发ARQ系统（3）选择重发ARQ系统ARQ的主要缺点：码率较高。∵用较少的监督码元就能使误码率降到很低；检错的计算复杂度较低；检错用的编码方法和加性干扰的统计特性基本无关，能适应不同特性的信道。需双向信道来重发，不适用单向信道和一点到多点的通信系统。重发使得ARQ系统的传输效率降低。信道干扰严重时，将发生因反复重发而造成事实上的通信中断。不适用于要求实时通信的场合，例如电话通信。ARQ的主要优点：与前向纠错（FEC）方法相比ARQ的主要缺点：码率较高。∵用较少的监督码元就能使误码率ARQ系统的原理方框图ARQ系统的原理方框图通信原理差错控制编码-课件§11.2

纠错编码的基本原理§11.2纠错编码的基本原理规则：使码组中“1”的个数为偶数情形1：没有冗余——不能发现错误情形2：加入冗余

——可以发现错误

冗余⤎另外4个码组许用码组禁用码组规则：使码组中情形1：没有冗余——不能发现错误情形2例许用码组禁用码组也不能纠正

错误。（奇数个错码）例许用码组禁用码组也不能纠正错误。（奇数个错码）这时，能够发现2个以下错码，或者纠正

1位

错码。例这时，能够发现2个以下错码，或者纠正1位错码。例综上所述：---信息码元位数---编码后码字位数综上所述：---信息码元位数---编码后码字位数不同的编码方法，检错或纠错能力也不同。不同的编码方法，检错或纠错能力也不同。分组码和系统码编码后的每组长度为n

=

k+r就是分组码前面的例子：信息位与监督位关系：分组码和系统码编码后的每组长度为n

=

k+r就是分组码分组码的符号：分组码的结构：

（n，k）

分组码的符号：分组码的结构：（n，k）

码长

(n)：码组（码字）中的码元个数。

码重(W)：码组中“1”的数目。“

011011”

的距离为

3例

码重和码距

码重为

3码长(n)：码组（码字）中的码元个数。码重(W)：码组对于3位的编码组，可用3维空间来说明（4个许用码组之间）各顶点之间沿立方体各边行走的几何距离——码距=2

码距的几何意义：对于3位的编码组，可用3维空间来说明（4个许用码组之间）各顶对于（n，k）分组码，有以下结论：最小码距d0

和检纠错能力的关系检ｅ个错码，要求：纠ｔ个错码，要求：纠

t

个错码,同时检

e个错码，要求：对于（n，k）分组码，有以下结论：最小码距d0和检纠错证明：证明：§11.3

纠错编码的性能§11.3纠错编码的性能系统带宽和信噪比的矛盾系统带宽和信噪比的矛盾右图所示的某种编码性能可见：不增大发送功率,就能降低误码率约一个半数量级。A点B点例10-610-510-410-310-210-1编码后Pe

CD

A

B编码前信噪比

(dB)2PSK调制右图所示的某种编码性能可见：不增大发送功率,就能A可见：能节省功率2dB

——称为编码增益D点10-610-510-410-310-210-1编码后Pe

CD

A

B编码前信噪比(dB)2PSK调制C点可见：能节省功率2dBD点10-610-510-410-

因此，纠错码主要应用于功率受限而带宽不太受限的信道中。——付出的代价是带宽增大。——付出的代价是带宽增大。设编码前系统工作在图中C点，提高速率后Pe由C点升到E点。传输速率RB

和信噪比Eb/n0的关系若希望提高RB，则必使Eb/n0下降，误码率Pe增大。这时付出的代价仍是带宽增大。10-610-510-410-310-210-1编码后

CDEAB编码前信噪比

(dB)但采用纠错编码后，Pe仍可降到D点。设编码前系统工作在图中C点，传输速率RB和信噪比Eb/§11.4

简单的实用编码§11.4简单的实用编码11.4.1

奇偶监督码偶监督码奇监督码

适用：检测随机出现的零星差错。编码规则：只一位监督码元（∵不知错码位置）很高（只有一位监督位）。

码率：11.4.1奇偶监督码偶监督码奇监督码适用：检编出的码字应为

：

若收到10011，检测结果为：根据偶数监督规则：---有错若收到00011，检测结果为：奇偶监督码不能检出偶数个错例解---认为无错11011编出的码字应为：若收到10011，检测结果为：11.4.2二维奇偶监督码编码规则：（方阵码）11.4.2二维奇偶监督码编码规则：（方阵码）检测方法：计算接收码组中“1”的数目，可知是否有错。11.4.3恒比码适用：用于电报传输系统或其他键盘设备产生的字母和符号。编码规则：(等重码)例个许用码组，可分别用来代表26个英文字母及其他符号。检测方法：计算接收码组中“1”的数目，可知是否有错。11.411.4.4正反码编码规则：

设码长n=10，即信息位k=5，监督位r=5。例监督位数与信息位数相同；能纠错。编码效率低：50%。11.4.4正反码编码规则：设码长n=10，即译码方法：

=

00000译码方法：=00000校验码组和错码的关系：无错∵信息位中有奇数个“1”，∴校验码组=00000校验码组和错码的关系：无错∵信息位中有奇数个“1”，∴校验码发送码组为1100111001纠检能力：发送码组为1100111001纠检能力：（n,k）线性分组码§11.5

（n,k）线性分组码§11.5线性码：按照一组线性方程构成的代数码。

即每个码字的监督码元是信息码元的线性组合。基本概念代数码：建立在代数学基础上的编码。线性码：按照一组线性方程构成的代数码。基本概念代数码：建立在正反码，效率50%，太低。纠正1位错，最少增加多少监督位？构造出以最小多余度代价换取最大抗干扰能力的好码纠错编码任务：汉明码：能纠正1位错，编码效率较高正反码，效率50%，太低。构造出以最小多余度代价换取最大抗干---监督关系式若S=0，认为无错（偶监督时）；若S=1，认为有错。若要构造具有纠错能力的（n，k）码，则需增加督码元的数目。当“=”成立时，构造的线性分组码称为汉明码校正子构造原理只有一位监督元---检错汉明码的——能纠1位错码的高效

线性分组码---监督关系式若S=0，认为无错（偶监督时）；若S=1例(7,4)汉明码可以其他假设例(7,4)汉明码可以其他假设由表可见:仅当一位错码的位置在a2

、a4、a5或a6

时，

校正子S1为1；否则S1为

0。同理：由表可见:仅当一位错码的位置在a2、a4、a5同理：(A)移项运算解出监督位(A)移项运算(A)(A)例接收端译码——检错纠错过程以上构造的线性分组码，称为汉明码。例接收端译码——检错纠错过程以上构造的线性分组码，称为汉明最小码距：当n很大

r很小时，Rc≈

1。

编码效率：汉明码特点:式中的等号成立，即:d0=3（纠1或检2）r

是不小于3的任意正整数最小码距：当n很大r很小时，Rc≈1。编码效率：答：最小码距:故能纠1或检2d0=3答：最小码距:故能纠1或检2d0=3线性分组码的一般原理将前面(7,4)汉明码的监督方程：改写为：表示成如下矩阵形式：H

---监督矩阵

线性分组码的一般原理将前面(7,4)汉明码的监督方程：改写简记为H

A=[a6

a5

a4

a3

a2

a1

a0]0=[000]监督矩阵

或转置转置“T”简记为HA=[a6a5a4a3a2a1ar

n=[PIr]r

k阶矩阵r

r阶方阵——典型监督矩阵H

矩阵的性质

①H

的行数等于监督位的数目r

。H的每行中“1”的位置表示相应码元之间存在的监督关系。(7，4)码r=3

②

H的各行应该是线性无关的，否则得不到r个线性无关的监督关系式。若一矩阵能写成典型阵形式[PIr]，则其各行一定是线性无关的。rn=[PIr]rk阶rr阶——将上面汉明码例子中的监督位公式：改写成矩阵形式：G

---生成矩阵

或者写成：P阵将上面汉明码例子中的监督位公式：改写成矩阵形式：G---式中，Q为一个k

r阶矩阵，它为P的转置，即:

Q=PTP阵Q阵式中，Q为一个kr阶矩阵，它为P的转置，即:Q将Q的左边加上1个k

k阶单位方阵，就构成矩阵:生成矩阵，或者因此，若找到了码的G，则编码的方法就完全确定了。具有[IkQ]形式的称为典型生成矩阵。由典型G得到的码称为系统码。称为典型生成矩阵信息位不变，监督位在后。∵由它可以产生整个码组，即有:k

n将Q的左边加上1个kk阶单位方阵，就构成矩阵:生成G

矩阵的性质

①

G矩阵的各行是线性无关的。∵由式可看出:任一码组A都是G的各行的线性组合。G共有k行，若它们线性无关，则可以组合出2k种不同的码组A。它恰是有k位信息位的全部码组。G矩阵的性质①G矩阵的各行是线性无关的。∵由式可G和H

的关系

G和H的关系

校正子与错误图样设发送码组为一个n列的行矩阵A，

接收码组的行矩阵B错码矩阵（错误图样）(模2)校正子与错误图样设发送码组为一个n列的行矩阵A，A=B+E例在接收端，若能求出错误图样E就能恢复出发送码组A

，即∵任一发送码组A

都应满足式：∴对于接收码组B，可通过计算:来进行检测。A=B+E例在接收端，若能求出错误图样E就能恢将B=A+E代入上式，可得 0若,

则S为0，否则S不为0。因此，可根据S

是否为0判断接收码组是否出错!由以上分析可知，（n,k)线性分组码译码的三个步骤：将B=A+E代入上式，可得 0若,则S为0，2)由S找到错误图样E；3)由公式A=B+E

得到译码器译出的码组。（n,k)线性分组码译码的三个步骤：2)由S找到错误图样E；3)由公式A=B+

①封闭性A1和A2(A1+A2)证明：若A1和A2是两个码组，则有A1

HT=0和A2

HT=0，将两式相加，有A1

HT+A2

HT=(A1+A2)HT=0②

最小距离（证毕）线性分组码的性质①封闭性A1和A2(A1+A2)证明：若A1和A2是两个根据性质②线性分组码计算最小码距，只需找最小码重，无需两两码组比较③完备性：汉明码中，伴随式的非零形式与错误图样一一对应，且伴随式的图样除全0外为个，正好等于码长，最充分利用了监督位所提供的信息。根据性质②③完备性：汉明码中，伴随式的非零形式与错误图样一循环码西安电子科技大学通信工程学院

课件制作：曹丽娜它除了具有线性分组码的一般性质外，还具有循环性。§11.6

循环码西安电子科技大学通信工程学院表中的第2

码组向右移一位即得到第

5码组；(7,3)循环码11.6.1

循环码原理表中的第6

码组向右移一位即得到第3码组。表中的第2码组向右移一位即得到第5码组；(7,3注意：注意：码字（）的多项式可表示为：

码多项式多项式的系数就是码组中的各码元，x

仅是码元位置标记。n=7时

例——码字（码组）的多项式表示码字（）的多项式可表示为：码多项式多项式的系数1.码多项式的按模运算一般说来，若一个整数m可以表示为

（Q

为整数）

m

p

(模n)则在模n

运算下，有1.码多项式的按模运算一般说来，若一个整数m可以表示为

码多项式的按模运算：

或则码多项式系数之间的加法和乘法：按模2运算。例码多项式的按模运算： 或则码多项式解运算过程：即有则有余式解运算过程：即有则有余式因为，A

(x)是A(x)代表的码组向左循环移位i次的结果。循环码的码多项式

则余式A

(x)也是该编码中的一个许用码组。

例循环码组，码长n=7。i=3时，有因为，A(x)是A(x)代表的码组向左循环移位i左移i位3

由上述分析可见:左移i位3由上述分析可见:2.

循环码的生成矩阵G

生成矩阵

G可由k

个线性无关的码组构成。引思：如何寻找这k个线性无关的码组？因此，用这ｋ个线性无关的码组可构成该循环码的生成矩阵G

，即2.循环码的生成矩阵G生成矩阵

G可由k个线性无关的码生成多项式生成多项式⑶g(x)是xn+1的因式g(x)的性质：⑴g(x)必有一常数项a0＝1⑵g(x)的次数为n-k次，且唯一否则，循环右移1位出现k连0,线性分组码不可能信息位全0，监督位不全为0若2个，由封闭性得两者和为码组，连0个数至少多出2位：a0、an-k线性分组码不可能后面说明⑶g(x)是xn+1的因式g(x)的性质：⑴g(x)必有r=n-k=7-3=4，解例码组中唯一一个4次码多项式代表的或此循环码多项式A(x):r=n-k=7-3=4，解例码组中唯一一个4次码多(n-k)+(k-1)=n-1(n-k)+(k-1)=n-1∵任一循环码多项式A(x)

都是g(x)的倍式，∴可以写成 而生成多项式g(x)本身也是一个码组，即有A

(x)=g(x)A(x)

=h(x)

g(x)∵码组A

(x)是一个(n–k)次多项式，故xkA

(x)是一个n次多项式。xkA

(x)在模(xn+1)运算下也是一个码组，故可写成∵任一循环码多项式A(x)都是g(x)的倍式，∴可以左端分子和分母都是n次多项式，故Q(x)=1：将和代入上式，化简后得到A

(x)=g(x)A(x)

=h(x)

g(x)左端分子和分母都是n次多项式，故Q(x)=1：将求(7,3)循环码的生成多项式g(x)。例将(x7+1)进行因式分解：解：n–k即有或求(7,3)循环码的生成多项式g(x)。11.6.2循环码的编解码方法1.循环码的编码设

信息码(an-1

an-2…an-k)的多项式为：

m(x)=an-1xk-1+an-2

xk-2+⋯+an-k——其最高次数为k-1则循环码的多项式为：A(x)=

11.6.2循环码的编解码方法1.循环码的编码设信息A(x)=m(x)g(x)即（1）xn-k乘m(x)，得

xn-k

m(x)

（2）xn-k

m(x)除以g(x)： ——将信元左移（n–k）位，附上（n–k）个0，预留给监督码元。——得到余式

r(x)，作为监督码元

——即得循环码的码多项式。系统循环码的编码步骤：（3）作A(x)

=

xn-k

m(x)+r(x)——通常是非系统码（n–k）+（k-1）（n–1）-（k-1）=r（n–1）最高次数A(x)=m(x)g(x)即（1）xn-k乘m(例可见例可见2.循环码的解码目的：检错和纠错。若能除尽，则无错；若除不尽而有余项，则表示在传输中发生错误。检错：2.循环码的解码目的：检错和纠错。若能除尽，则无错；若纠错：纠错：11.6.3截短循环码例：构造一个能够纠正1位错码的(13,9)码。可由(15,11)循环码的码组中选出前两信息位均为“0”的码组，构成一个新的码组集合。在发送时不发送这两位“0”。于是发送码组成为(13,9)截短循环码。截短目的：在设计纠错编码方案时，若找不到合适的码长n及信息位k

时，可以把循环码的码长截短以得到符合要求的编码。截短方法：设给定一个(n,k)循环码，它共有2k种码组，现使其前i

(0<i<k)个信息位全为“0”，于是它变成仅有2k-

i

种码组。然后从中删去这i位全“0”的信息位，最终得到一个(n

–i

,k

–i)的线性码——截短循环码。截短循环码性能：循环码截短前后至少具有相同的纠错能力，并且编解码方法仍和截短前的方法一样。11.6.3截短循环码例：构造一个能够纠正1位错码的(111.6.4BCH码——解决了生成多项式与纠错能力的关系问题，可以在给定纠错能力要求的条件下寻找到码的生成多项式。BCH码的重要性:BCH码的分类：多个11.6.4BCH码——解决了生成多项式与纠错能力的关系汉明码是能够纠正单个随机错误的码。可以证明，具有循环性质的汉明码就是能纠正单个随机错误的本原BCH码。BCH码的性能：码长n

与监督位、纠错个数t之间的关系：

对于正整数m(m

3)和正整数t

<m/2，必定存在一个码长为

n=2m–1，监督位为n–k

mt，能纠正所有不多于t个随机错误的BCH码。若码长n=(2m-1)/i（i>1，且除得尽(2m-1)），则为非本原BCH码。汉明码是能够纠正单个随机错误的码。可以证明，具有循环性质的汉BCH码的设计：在工程设计中，一般不需要用计算方法去寻找生成多项式g(x)。因为前人早已将寻找到的g(x)列成表，故可以用查表法找到所需的生成多项式。教材348/353页的表11-7给出了码长n

127的二进制本原BCH码生成多项式。n=(2m-1)n=(2m-1)BCH码的设计：在工程设计中，一般不需要用计算方法去寻找生BCH码的长度都为奇数。为得到偶数长度的码，并增大检错能力，在BCH码生成多项式中乘因式(x+1)，得扩展BCH码(n+1,k)。扩展BCH码相当于在原BCH码上增加了一个校验位，因此码距比原BCH码增加1。扩展BCH码已经不再具有循环性。例如，广泛实用的扩展戈莱码(24,12)，其最小码距为8，码率为1/2，能够纠3个错码和检4个错码。它比汉明码的纠错能力强很多。代价：解码更复杂，码率也比汉明码低。不再是循环码。扩展BCH码：BCH码的长度都为奇数。扩展BCH码：11.6.5RS码——一类具有很强纠错能力的多进制BCH码。——由里德和索洛蒙(Reed–Solomon)提出。

一个能够纠t个错误符号的m进制的RS码有如下参数：最小码距：d0=2t+1个符号，或q（2t+1）比特码组长度：n=m–1=2q–1个符号，督元长度：

r=n-k=2t

个符号，或

2tq

比特信元长度：

k

个符号，或kq个比特参数或q(2q–1)个比特11.6.5RS码——一类具有很强纠错能力的多进制BCH∵RS码能够纠正t个m进制错码，即能纠正码组中t个不超过q位连续的二进制错码，∴RS码特别适用于存在突发错误的信道，例如，移动通信网等衰落信道中。∵它是多进制纠错编码，∴特别适合用于多进制调制的场合。RS码的生成多项式：g(x)=(x+

)(x+

2)…(x+

2t)式中，

是伽罗华域GF(2q

)中的本原元素。应用∵RS码能够纠正t个m进制错码，即能纠正码组中t个不超过q位卷积码——一种非分组码§11.7

卷积码——一种非分组码§11.7非分组码概念：分组码:——每个码组中的监督码元仅与本码组中的k个信元有约束关系。

非分组码:即一个码组中的监督码元监督着N个信息段。卷积码的符号:

(n,k,N

)N

---

编码约束度，表示编码过程中互相约束的码段个数；nN

---

编码约束长度，表示编码过程中互相约束的码元个数。卷积码的码率:

R=k/n(n,1,N

)

简单,常用N

或nN也反映了卷积码编码器的复杂度。

将k比特信息段编成n比特码组非分组码概念：分组码:——每个码组中的监督码元仅与本码组一般，k，n较小，N较大；随着N增大，误码率呈指数下降；更适用于前向纠错，性能优于分组码，运算简单。GSM（2,1,5）IS-95（2,1,9）CDMA2000（2,1,9)……一般，k，n较小，N较大；GSM（2,1,5）11.7.1卷积码的基本原理编码器原理方框图存储以前的k(N-1)个信息码当前

K个共有N

段移存器，每段k

级

11.7.1卷积码的基本原理编码器原理方框图存储以前的k如图所示的(n,k,N)=

(3,1,3)卷积码编码器。例共有3

段移存器，每段1

级（存储1个信元）

每次输入1b，输出3b

分析：信息位---如图所示的(n,k,N)=(3,1,3)设移存器初始是全零状态，当输入信息序列

：则编码器输出序列：结果为系统码形式。设移存器初始是全零状态，当输入信息序列：则编码器输出序列：ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi－1bitt输入输出信息位bi的监督位和各信息位之间的约束关系如下图中虚线所示：（编码约束度N=3，约束长度nN=3×3=9）ci-2di-2ei-2ci-1di-1ei-1cidiei卷积码的表述方法：卷积码的表述方法：11.7.2卷积码的代数表述上式：表示的卷积码也是一种线性码。——可完全由H

或G

所确定。监督矩阵生成矩阵11.7.2卷积码的代数表述上式：表示的卷积码也是一种线分类：代数解码：——利用编码本身的代数结构进行解码，不考虑信道的统计特性。概率解码（最大似然解码）：——基于信道的统计特性和卷积码的特点进行计算。11.7.3卷积码的解码如：大数逻辑解码（门限解码），适用nN较短的卷积码。

序贯解码:适用无记忆信道维特比算法：当码的nN较短时，效率更高、速度更快约束长度分类：代数解码：概率解码（最大似然解码）：11.7.3卷2

卷积码的几何表述 —维特比解码算法的基础1）码树图以前面(3,1,3)

卷积码为例：并设M1，M2和M3的初始状态000(n,k,N)2卷积码的几何表述1）码树图以前面(3,1,3)卷(3,1,3)

码树图：观察1规定(3,1,3)码树图：观察1规定

每条树枝上标注的码元为输出比特，每个节点为移存器的状态abcd若信息位

1 1 0 1编码输出111110

010100

(3,1,3)

码树图：观察2若信息位1 M1M2M3110011101100M3M20111100100状态11011101M1M2M3110011101100M3M201111001(3,1,3)

码树图：观察3(3,1,3)码树图：观察3若信息位

1 1 0 1编码输出111110

010100

码树图原则上还可用于解码。发送序列⟵010110不实用基础若信息位1 1 0 2）状态图码树图

状态图由(3,1,3)编码器结构可知：2）状态图码树图状态图由(3,1,3)编码器结构可知：

前一状态a只能转到下一状态a或b；前一状态b只能转到下一状态c或d，等等。按照表中的规律画出的状态图：由表看出：abcd000111101110010011100001前一状态a只能转按照表中的规律由表看出：abcd000abcd000111101110010011100001利用状态图可方便地从输入序列得到输出序列。例如：输入信息位

1 1 0

1编码输出111110

010100

111110010100abcd000111101110010011100001利用第4时隙后完全是第3时隙的重复，因（3,1,3）码约束长度为3。3）网格图将状态图在时间上展开

网格图5个时隙abcd000111101110010011100001第4时隙后完全是第3时隙的重复，因（3,1,3）码约束长度为当输入信息位为11010时，在网格图中的编码路径：这时的输出编码序列：111110010100011…。基于上面的状态图和网格图，讨论维特比解码算法。当