北邮通信原理课件A-11差错控制

北邮通信原理课件A-11差错控制第一页，共99页。11.1概述数字信道上误码原因——信道传输特性不理想；信道加性噪声的影响。解决办法1——针对信道特性不理想合理设计基带信号的码型和波形，消除码间串扰。采用时域、频域均衡，修正信道特性。解决办法2——针对信道加性噪声的影响加大发射功率，提高信噪比选择恰当的调制解调方式。解决办法3——差错控制编码误码率仍不能满足要求，则采用信道编码（即差错控制编码），发现差错，进行修正，进一步降低误码率。代价：增加冗余编码，编码效率下降第二页，共99页。概述一、差错控制编码二、信源编码与信道编码三、信道的分类四、差错控制方法五、纠错码、检错码举例六、差错控制编码分类第三页，共99页。一、差错控制编码在信息码元中按一定规则增加一些监督码元，并利用信息码元与监督码元间的关系来发现、纠正误码的方法。监督位越多，检（纠）错能力越强，但传输速率越高，要求带宽越大。编成

n个比特的码

字k个信息比

特编码效率R

第四页，共99页。二、信源编码与信道编码信源编码1、其码型要适合于在信道中传输2、尽量减少信源的冗余度。尽可能用最少的信息比特来表示信源，提高通信系统的有效性。3、如哈夫曼编码、话音PCM编码、话音图象压缩编码等。信道编码1、通过对传输信息加入冗余信息的方式来达到差错控制的目的，从而提高通信系统的可靠性。2、如奇偶校验码、循环校验码、卷积码等。第五页，共99页。三、信道的分类根据加性干扰引起错码分布规律的不同，将信道分为三类随机信道：错码随机出现，错码间相互独立，一般由信道的加性随机噪声引起。突发信道：误码集中出现，如信道上有脉冲干扰，信道衰落，光盘上的一条划痕。混合信道：既有突发错误又有随机差错。不同类型的信道，应采用不同的差错控制。第六页，共99页。四、差错控制方法发送端差错控制编码：在信息序列上附加上一些监督码元，利用这些冗余的码元，使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号。例如奇偶校验。接收端差错控制译码：利用这些规律性来鉴别传输过程是否发生错误，从而抛弃错误信息，或进而纠正错误。第七页，共99页。差错控制方法（续）1.

前向纠错方式（FEC）信源

编码器

正向信道(纠错)解码器

收信者发送端将信息序列编码成能够纠正错误的码，接收端根据编码规则进行检查，如果有错自动纠正特点：使用纠错编码，难度大，但实时性好，适于随机信道；只需要正向信道，可用于单工和广播通信中。例如：移动蜂窝电话系统。第八页，共99页。差错控制方法(续)2.检错重发方式（ARQ）信源解码器(检错)收信者缓存指令产生器正错确误输删出除重发控制反向信道编码器 缓存 正向信道正错确误删重除发收端在接收到的信码中发现错码时，通知发端重发，直到正确接收为止。特点：使用检错编码，易实现，但实时性差，适于突发信道；还需要反向信道，只能用于点对点通信中；信道质量差时，会陷入“重发陷阱”。第九页，共99页。确认/重传机制举例接收码组ACK ACKNAKACKACKNAKt1 2 3345534556ACK

t有错码组有错码组停止等待ARQ系统发送码组1 2 3拉后ARQ系统接收数据有错码组有错码组10111212345675678991011ACK1NAK5NAK9ACK5发送数据12345675678910119101112重发码组重发码组第十页，共99页。差错控制方法(续)ARQ方式优点：（1）只需少量的附加码元即可获得较低的输出误码率。（2）适应信道统计差错特性强。（3）结构较纠错编解码器简单。ARQ方式缺点：（1）需要反向信道。（2）信道干扰大时，需要不断重发，通信效率低。（3）不太适合实时性较强系统第十一页，共99页。差错控制方法(续)3.反馈检验方式信源正向信道收信者缓存缓存输出指令比较器 反向信道收端把收到的数据序列全部送回发端，发端比较发出和送回的数据序列，从而发现是否错误，如果有错，发端重发数据序列，直到发端没有发现错误。特点：不用差错控制编码，但效率低。第十二页，共99页。差错控制方法(续)4.混合方式（HEC）信源正向信道收信者反向信道ARQ发 FEC

发FEC

收ARQ收特点：内层使用FEC，纠正随机差错，减少重发次数；外层使用ARQ，重发无法纠正的突发差错。需要纠检结合的编码第十三页，共99页。差错控制方法(续)FEC与ARQ的结合发端发出同时具有检错和纠错能力的码，收端收到后，检查错误情况：如果错误在纠错能力之内，则自动纠正；若超出纠错能力，但在检错能力之内，则经反向信道要求重发。在实时性和译码复杂性方面是FEC和ARQ的折衷。第十四页，共99页。五、纠错码、检错码举例例：信源信息为通过/不通过，信源编码为通过（0）/不通过（1），无纠检错能力

信道编码：通过（00）/不通过（11），有检错能力

信道编码：通过（000）/不通过（111），有纠1位错，或检2位错能力结论：增加码的冗余度（监督码位数），可以增加纠错编码的纠错能力。第十五页，共99页。六、差错控制编码分类按功能分：检错码和纠错码按监督码元与信息码元关系分：线性码与非线性码按信息码元与监督码元之间的约束关系不同分：分组码与卷积码按信息码元在编码后是否保持原来的信号形式分：系统码与非系统码按纠正差错的类型分：纠正随机错误的码与纠正突发错误的码按码元的取值分：二进制码与多进制码第十六页，共99页。11.2纠错编码的基本原理一、分组码结构二、纠（检）错能力三、编码效率四、纠检错编码的性能举例第十七页，共99页。一、分组码结构(n,

k)分组码（系统码结构）一个码字

n位(n=k

+r) an-1 an-2ar-1… ar …a0信息码元

k位 监督码元r位监督码元又称监督位，分组码的监督码元只监督本码组中的信息码元第十八页，共99页。分组码结构(续)码长：码字中码元的数目码间距离（d）：两个码组，对应位的码元不同的个数,又称汉明距离。用于表示两个码组的差异。码重：分组码中，1的数目称为码组的重量两个码组的距离为其模2和码组的码重an-1 an-2… arar-1…a0第十九页，共99页。分组码结构(续)最小距离（d0）：一种编码中，各个码组间距离的最小值。ni1j,kd0

Min

(aji

aki)aji表示第j个码组的第i位码元。汉明距离是度量一种编码检错和纠错能力的一种测度纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。an-1 an-2ar-1… ar …a0第二十页，共99页。分组码结构(续)码距的几何意义（n=3）8个码组间最小码距d0=14个码组000、011、101、110间最小码距d0=22个码组000、111间最小码距d0=3(0,0,0)(1,0,1)(1,0,0)(0,0,1)(0,1,0)(1,1,1)(1,1,0)(0,1,1)第二十一页，共99页。举例说明：传送A（通过）、B（不通过）两个消息编码一：消息A----“0”；消息B----“1”最小码距1若传输中产生错码（“0”错成“1”或“1”错成“0”）收端无法发现，该编码无检错纠错能力。分组码结构(续)第二十二页，共99页。编码二：消息A----“00”；消息B----“11”最小码距2若传输中产生一位错码，则变成“01”或“10”，收端判决为有错（因“01”“10”为禁用码组），但无法确定错码位置，不能纠正，该编码具有检出一位错码的能力。这表明增加一位冗余码元后码具有检出一位错码的能力分组码结构(续)第二十三页，共99页。编码三：消息A----“000”；消息B----“111”最小码距3传输中产生一位或两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力。在产生一位错码（错1位概率远远大于错2位、3位概率）情况下，收端可根据“大数”法则进行正确判决，能够纠正这一位错码。该编码具有纠正一位错码的能力。例如收到110，认为是111。这表明增加两位冗余码元后码具有检出两位错码或纠正一位错码的能力。第二十四页，共99页。二、纠（检）错能力一种编码的最小距离直接影响编码的纠错、检错能力。一种编码，若其最小距离为d0能检测e个错误时，e+1

d0能纠正t个错误时，2t+1

d0能纠正t

个错误，并同时检测出e个错误时，e+t+

1

d0

(e>

t

)第二十五页，共99页。纠（检）错能力（续）为了检测e个错误，要求最小码距dmin

e

10 1 2 3ABedminA、B都为许用码；A发生e个错；B不能在半径为e的环内，否则收到B无法判断是否为错码；第二十六页，共99页。纠（检）错能力（续）为了纠正t个错误，要求最小码距

d

min

2

t

10 1 2 34 5ABtd

mintA,B都为许用码A,B都发生t个错A,B的纠错范围不相交第二十七页，共99页。纠（检）错能力（续）tte1AB为了纠正t个错误，同时检测e个错误，要求最小码距d

min

e

t

1

(

e

t

)第二十八页，共99页。例

d0=7检错方式 e=?纠错方式 t=?纠检结合方式e=?,

t=?第二十九页，共99页。三、编码效率kn k

rR

k

第三十页，共99页。四、纠检错编码的性能举例假设在随机信道中发送“0‖/‖1‖时的错误概率都等于p，且p<<1，则在码长为n的码组中恰好发生r个错码的概率为：p

rn!r!(n

r)!p (r

)

C

r

p

r

(1

p)n

r n n例如，当码长n=7时，p=10-3则有2

5p7(2)

21p

2.1

10

3p7(1)

7p7

10 ;3

8p7(3)

35

p 3.5

10

结论：随机信道中，纠正或检测码组中1-2个错误，可使误码率下降几个数量级。代价是带宽加大第三十一页，共99页。11.3常用的简单编码奇偶校验码——监督位只有一位奇校验——编码后该码组中1的个数为奇数偶校验——编码后该码组中1的个数为偶数只能发现奇数个错误，不能检测偶数个错误。最小码距为2用于随机信道二维奇偶校验码（方阵码）可以发现某一行或某一列上的所有奇数个错误可以发现长度不大于行数（或列数）的突发错误。用于突发信道第三十二页，共99页。常用的简单编码（续）恒比码每个码组中均含有相同数目的“1”码和“0”码例：用5个比特码字表示10个阿拉伯数字。从32个可能码字中挑出10个“1‖的个数为3个的码字编码能检测出所有1个和奇数个错误，并能部分检测出偶数个错误（成对交换错则检测不出）用在电传、电报阿拉伯数字编码阿拉伯数字编码101011610101211001711100310110801110411010910011500111001101第三十三页，共99页。常用的简单编码（续）正反码编码规则：信息位有奇数个1，监督位=信息位信息位有偶数个1，监督位=信息位举例信息位为11001，码组为1100111001信息位为10001，码组为1000101110第三十四页，共99页。11.4线性分组码一、基本概念二、线性码的校验三、汉明码四、线性分组码一般原理第三十五页，共99页。一、几个基本概念代数码：建立在代数学基础上的编码称为代数码。例如奇偶校验码。分组码：先将信息码分组，然后给每组信码附加若干监督码的编码称为分组码，用(n,k)表示，k是信息码的位数，n是编码组总位数，又称为码长，r=n-k为监督位数。线性码：线性码中信息位和监督位是按一组线性方程构成的。线性码是一种代数码。奇偶监督码是最简单的线性码。线性分组码：信息码分组后，附加的监督码和信息码由一些线性代数方程联系着的编码称为线性分组码。第三十六页，共99页。二、线性码的校验线性分组码：监督码与信息码间用线性方程联系运算规则——加法为模2加，乘法为二进制乘法；码组间运算是各个相应比特位上的运算

1+1=0、1+0=1、0+1=1、0+0=0

1x1=1,1x0=0, 0x0=0,0x1=0第三十七页，共99页。线性码的校验（续）码的监督（校验）方法例：对于偶校验码的监督关系：

...

a

0S

an1

an

2如果S=1，则认为传输时出错；S=0，则认为无误传输。上式称为监督关系，S称为校验子。问题：为了能纠一位错，k位信息至少需要多少位的监督信息，如何设计？第三十八页，共99页。线性码的校验（续）r个监督位对应r个监督关系式可以有r个校验子能指示一位错码的

2r-1个可能位置。若码长为n，信息位数为k，则监督位数r=n-k。用r个监督位表示一位错码的n种可能位置条件是：如果取k=4，则可以确定r>=3，n=k+r=7。因此，可以用3个校验子来确定传输的7个位置是否出错。2r

1

n或

2r

k

r

1第三十九页，共99页。三、汉明码能够纠正一位错码且编码效率较高的线性分组码条件：对于(n,k)码，要求2r–1n。

例如:(7,4),(15,11),(31,26)码第四十页，共99页。汉明码(续)

例：(7,4)

汉明码1.设计校验子的错误图样校验子S1S2S3000 001 010 011100 101 110 111错码位 无置 错a0 a1 a3a2a45a a6(a6a5a4a3a2a1a0

)0346313562S

a

a

a

a 0S1

a6

a5

a4

a2

0于是有S

a

a

a

a

0,第四十一页，共99页。汉明码(续)2.监督关系式03462 6 5 3 1

3

a

a

a

a

0S

a

a

a

a 0,SS1

a6

a5

a4

a2

034603561

a

a

aaa

a

a

a3.编码规则a2

a6

a5

a4第四十二页，共99页。汉明码(续)（7，4）码的所有码组。a6a5a4a3a2a1a0a6a5a4a3a2a1a000000001000111000101110011000010101101001000111101011001010011011000010101101110101001100111110100011100011111114 3603561

a

a

aaa

a

a

aa2

a6

a5

a4第四十三页，共99页。汉明码(续)4.解码和纠错根据接受码组计算校验子，按错误图样纠错后，取前k位信息位。最小距离d0

=3，可纠1位错，检2位错，不能同时纠检错。编码效率k/n

(2r

1

r)/(2r1)

1

r/(2r1)

1

r/n当

n

很大

时，编码速率接近1。第四十四页，共99页。四、线性分组码的一般原理1.

监督关系式监督矩阵线性码是指信息位和监督位满足一组线性方程的码，由校验关系式，可得一组线性方程1

a6

1

a51

a4

0

a3

1

a2

0

a1

0

a0

01

a6

1

a5

0

a4

1

a30

a2

1

a1

0

a0 01

a6

0

a5

1

a4

1

a3

0

a2

0

a1

1

a0

03 6 4 3 02 6 5 3 1

a

a

a

a

0S

a

a

a

a

0,SS1

a6

a5

a4

a20第四十五页，共99页。写成矩阵的形式：

00111 1 1 0

1

01 0 1 0 10 1 1 0 03

5

a1

a

1a2

0a

00a4

a a6

HAT

0T 或 AHT

0即PIrH（监督矩阵） ·

0

AT=OTH中每行1的位置表示相应码元之间的监督关系。只要监督矩阵确定，信息位与监督位的关系就确定。线性分组码的设计就是设计监督矩阵(即错误图样)。第四十六页，共99页。线性分组码的一般原理（续）监督矩阵H的特点r×n阶矩阵监督矩阵H确定了编码时监督码元与信息码元的关系把具有[P·Ir]形式的H矩阵称为典型形式的监督矩阵，其中P为r

×k阶矩阵,

Ir为r

×r阶单位方阵H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关第四十七页，共99页。线性分组码的一般原理（续）2.生成矩阵——将监督位与信息位的关系写成另一种矩阵形式

3

4

5

0

1

2

1111 1 11 00 1

aa

a

0 a6

a

a

1a111001

1 11 101a2

a1a0

a6

a5a4a3或者2 6 5 4a1

a6

a5

a3a0

a6

a4

a3a

a

a

a第四十八页，共99页。101001100011010011[a6

a5a4a3a2

a1a0

]

a6a5a4a3

G称为码的生成矩阵。由生成矩阵同样可以确定编码的码组。线性分组码的一般原理（续）0 1 0 1 00 0 1 0 1IkQA = M·G（生成矩阵）第四十九页，共99页。线性分组码的一般原理（续）生成矩阵G特点k ×n阶矩阵编码方法完全由生成矩阵G确定把具有[Ik·Q]形式的G矩阵称为典型形式的生成矩阵，其中，Ik为k×k阶单位方阵，Q为k×r阶矩阵由典型生成矩阵产生的分组码一定是系统码G矩阵的各行应线性无关，各行本身就是一个码组,

任一码组都是G的各行的线性组合第五十页，共99页。生成矩阵G与监督矩阵H的关系若H=[PIr]，称为典型监督矩阵。若G=[IkQ]，称为典型生成矩阵。由典型生成矩阵得到的码称为系统码。则Q=PT计算系统码的方法？线性分组码的一般原理（续）第五十一页，共99页。3.

错码矩阵（错误图样）假设发送码组为A，接收码组为B，则发送码组和接收码组之差为B-A=E它就是传输中产生的错码行矩阵，E=[en-1en-2…e0]其中错码矩阵E称为错误图样。接收时B=A+Eie

=i iO 当b=a1 当b≠ai i例如发送码组A=00110101错码矩阵E=00100000则 接收码组B=00010101线性分组码的一般原理（续）第五十二页，共99页。4.

接收判决接收到B后，计算校正子S=B·HT。T T若B=A（无误码），则S=B·H =A·H =O；若B≠A（有误码），则S=B·HT=(A+E)·HT=E·HT

，S?=OS为校正子，与错误图样E有线性关系。若S与E一一对应，则由S可以确定错误位置。如何根据H计算错误图样，实现纠错？根据S=E·HT

，可以用E去算S—E对应表线性分组码的一般原理（续）第五十三页，共99页。性质：封闭性：任意两许用码组之和（逐位模2和）仍为一许用码组。证明：设A，B为任意两个许用码组，H为监督矩阵则：AHT=0，BHT=0所以 （A+B）HT=0所以 （A+B）也是许用码组码的最小距离等于非零码的最小码重。证明：设A，B为任意两个许用码组由码距定义，A，B的距离=（A+B）的重量由封闭性，

（A+B）也是许用码组所以，最小码距=最小码重（非0码）线性分组码的一般原理（续）第五十四页，共99页。举例例1：线性分组码(7,3),已知典型生成矩阵G:100111001001110011101C6C5C4C3C2C1C0码重0000000000111014010011140111010410011104101001141101001411101004列出编码表方法1：3位信息位，000-111，用生成矩阵算检验位方法2：生成矩阵行运算最小码距=4，纠检错能力？第五十五页，共99页。

0 1100 0当信息位为0001时，（1）试求其后的监督位。（2）监督矩阵H（3）最小码距和纠、检错能力00011100110101000101举例例2：设（7,4）线性码的生成矩阵G为：1 1第五十六页，共99页。a4 a3

G解：（1）

A

a6 a51010A

000

1

[0001011]001100011100110101000101第五十七页，共99页。（2）监督矩阵HG=[Ik·Q]，H=[P·Ir]其中P=QT，可得监督矩阵H为：111110100101010011001101根据生成矩阵和监督矩阵的关系：0001000111001101010001011第五十八页，共99页。e=d0

-1=2t=d0-1

12e

t

1

d0 e

t该码可以检2位错该码可以纠1位错该码不能同时用于检错与纠错（3）d0 3第五十九页，共99页。11.5循环码满足封闭循环特性的线性分组码若(an-1,an-2…,a1,a0)是一(n,k)循环码的码组，则(an-2,an-3,…,a1,a0,an-1)…(a0,an-1,an-2,an-3,……,a2

,a1)也都是该循环码的码组。例：(7,3)循环码码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010第六十页，共99页。循环码一、循环码的表示方法二、生成矩阵和生成多项式第六十一页，共99页。一、循环码的表示方法码多项式长为n的码组

(an-1an-2…a2a1a0)可由码多项式T(x)=an-1xn-1+an-2xn-2+…+a2x2+a1x+a0表示。x表示码元的位置，系数ai对应码元的值。码多项式的按模运算：

F(x)≡R(x) （模N(x)）系数间运算服从模2规则，以“+‖代替“-‖。Nx

Nx

Fx

Qx

Rx第六十二页，共99页。码多项式按模运算举例码多项式系数按模2运算，即系数只取0和1。例如，x3被(x3+1)除，得到余项1。所以有同理

1 （模(x3

1)）x3x4

x21

x2

x

1x x3

+

1 x4x4+x2 +

1+

xx2+x

+1（模(x3

1)）在模2运算中，用加法代替减法，故余项不是x2

–x+1，而是x2+x+

1。第六十三页，共99页。循环码的表示方法(续)循环码特点码字左移一位，相当于乘x(以xn+1为模

)T(x)是一个许用码组，若xiT(x)≡T’(x)(模xn+1)，则T’(x)

也是许用码组，且为T(x)码组向左循环移位i次的结果。结论：N位循环码的码组必是按照模xn+1运算的一个余式第六十四页，共99页。二、生成矩阵和生成多项式生成矩阵的每一行都是一个码组，且是K行n列矩阵，因此，若能找到K个线性不相关的已知码组，就能构成生成矩阵G。用g(x)表示（n，k）循环码中前K-1位都为“0‖的码组，则g(x)，

xg(x),x2

g(x),xk-1

g(x)都是码组，并且这K个码组是线性无关的，他们就可以用来构成此循环码的生成矩阵G。定义这个n-k次多项式g(x)为码的生成多项式第六十五页，共99页。生成矩阵和生成多项式(续)g(x)满足：4.生成矩阵G为：5.G是非典型阵g(x)G(x)

xk

2g(x)1．g(x)|T(x)2．g(x)=xr+…+1，最高次幂r=n–k3．g(x)是

xn+1的因式

xk

1

g(x)第六十六页，共99页。解：对（7,3）循环码，n=7，k=3, r=4第一步：对x7+1进行因式分解得：.....(1)x7+1=(x+1)(x3+x2+1)(x3+x+1)第二步：构造r次生成多项式g(x)。要从式（1）中找到r=n-k=4次的因子,这样的因子有两个：(x+1)(x3+x2+1)=x4+x2+x+1……………(a)(x+1)(x3+x+1)=x4+x3+x2+1……………(b)第三步：若按(a)构成生成多项式:生成多项式为：g(x)=x4+x2+x+1[例]求（7，3）循环码的生成多项式和生成矩阵。第六十七页，共99页。将第1行与第3行模2加作为第1行，则有

101110001011100010111G

x4

x2

x

1 x6

x4

x3

x2

g(x) x2

g(x)G(

X)

xg(x)

x5

x3

x2

xTh成矩阵为：为典型Th成矩阵101G

100101010111001011第六十八页，共99页。若按(b)构成Th成多项式:

111010 0011101 0001110 1G

x4

x3

x21

g(x) Th成多项式为：g(x)=

x4+x3+x2+1Th成矩阵为：x2

g(x)

x6

x5

x4

x2

G(X

)

xg

(x)

x5

x4

x3

x

100111001001110011101G

进行线性变换，得典型Th成矩阵为：第六十九页，共99页。[例]已知（7，4）循环码的全部码组为：试写出该循环码的生成多项式g(x)和生成矩阵G，并将G化成典型矩阵。第七十页，共99页。解：n=7，k=4，n-k=33上述码组中的(n-k)=3次码多项式为第2组，它所对应的码多项式g(x)即为生成多项式：g(x)=x3+x+1。生成矩阵为：x3g(x)

x6

x4

x3

x2g(x)

x5

x3

x2

G(x)

x1g(x)

x4

x2

x

g(x)x

x

1

101100010001010101100

0

100111001011000101100 001011000101 1第七十一页，共99页。三、循环码的编码根据(n,k)值从xn+1的因式中选定一个r次多项式做为生成多项式g(x)。设信息码的多项式为m(x),最高次幂k–1,做xn-

km(x)。3. 运算,Q(x)为商式，r(x)为余式。4. 则T(x)=xn-km(x)+

r(x)=

Q(x)g(x)为循环码多项式，即以余式r(x)为监督位。可用除法器（带反馈的线性移位寄存器）来实现。Q(x)g(x)

g(x)r(x)xnkm(x)第七十二页，共99页。x2

1x 1)(x2

x4

x2

x

1 x4

x2

x

1x6

x5g(x)xnkm(x)

即余式r(x)=x2+1于是，对应码组T(x)=xn-km(x)+r(x）=x6+x5+

x2+1编码为1100101[例]设（7，3）循环码的生成多项式为g(x)=x4+x2+x+1，待编码信息位为110，求对应循环码码组。解：m(x)=x2+x，xn-k

m(x)=x4(x2+x)=x6+x5第七十三页，共99页。四、循环码的解码和纠检错1.解码无误码时，前k位为信息位。第七十四页，共99页。循环码的解码和纠检错(续)检错判决：S(x)=0，无差错；S(x)

0，有差错。2.

检错设：接收码多项式为R(x)

T(x)

E(x)

Q(x)g(x)

E(x)余式余式

g(x)

g(x)记：校验子S(x)

E(x)

R(x)

第七十五页，共99页。循环码的解码和纠检错(续)3.纠错当监督位足够长时，循环码也可纠错。例：g(x)=x3+x2+1的(7,4)循环码可纠正一位错码，错误图样为：校验子S(x) x2+x x+1 x2+x+1 x2+1x2x 1 0错码位置E(x)X6 x5 x4 x3 x2 x11 无错误图样的计算方法：给定E(x)，S(x)=E(x)

/g(x) 的余式第七十六页，共99页。11.6卷积码一、卷积码原理二、卷积码编码器三、卷积码的图形描述四、

卷积码的译码——维特比译码第七十七页，共99页。一、卷积码原理<-----------------------N*k---------------------->码组1 码组2 码组N12…k12..k1..12..k输入m输入移位寄存器

加法器输出移位寄存器输出Y123…n卷积码编码器结构（n，k，N）卷积码第七十八页，共99页。卷积码原理(续)编码约束度：N称为编码约束度编码约束长度：

nN称为编码约束长度。编码效率：Rc=

k/n第七十九页，共99页。二、卷积码编码器

以（3，1，3）卷积码为例初态000输入mj…mj…m2m1 mjmj-1mj-2输出yj…y1jy2jy3j… 123M1M2M3第八十页，共99页。卷积码编码器(续)输出与输入的关系是：21

111

1

y31

m1

y

m

y

m1232222212y

m

m

m

yy

mj

2j

1j3jj1j

m

m

m

y

mj

mj

2

y2j

m

y(j

3)输入mj

输出yjj…m…m

m2 11j2j3j…y y y …321M1mjM2mj-1M3mj-2第八十一页，共99页。三、卷积码的图形描述1、树状图——最直接的表示法由树状图可以看出，该编码存在4种状态：状态M2M3a b c d00 10 01 11第八十二页，共99页。000111001110011000111001110011100010101y y y142434100111011001101010y13y23y33000000001110y y y1222

32信息位1101ba起点信息位111y11y21y31000abcdabcdabcdabcd上半部下半部10a状态M2M30

010c 0

1d 11abcdabcdac100b010110d101↑0↓1↓1↑0↑0↓1

111 输入mj

输出yjmjj…m

…m2m1…y y y1j2j3j…321M1 M2 M3mj-1 mj-2第八十三页，共99页。卷积码的图形描述(续)2、状态图——最简单的表示法取出已达到稳定状态的一节树图，得到状态图a(00)b(10)c(01)d(11)当前状态 下一状态000001011010101100110111acdb000001010101110100111011abcd―0‖;―1‖输入mj

输出yjmjj…m

…m2m1…y1jy2jy3j…321M1

M2 M3mj-1 mj-2第八十四页，共99页。卷积码的图形描述(续)3、网格图（格状图、篱笆图）

——用于解码把状态图在时间上展开，得到网格图。输入信息位为1101…时输出编码序列是：111110010100

…acdb000001010101110100111011110110110010010101101001abcd000111000111000111011100001000111011100001第八十五页，共99页。卷积码的图形描述(续)N*k个0输入信息位为1101（000）时输出编码序列111110010100(001011

000)acd4、为保证输入的信息位完全通过移存器，需补b000010101100 001111 110011110110110010010101101110010101001abcdabcd000111000111000111011100001000111011100001000111011100001第八十六页，共99页。四、维特比译码门限译码大数逻辑译码维特比译码概率译码序列译码卷积码的译码第八十七页，共99页。维特比译码(续)1、最大似然算法译码把已接收序列与所有可能的发送序列比较，选择码距最小的作为发送序列。第八十八页，共99页。维特比译码(续)2、维特比译码（VB算法译码）思路：不是一次将全部码组收齐后一起比较，而是收一段，比较一段，选择一段有最大似然可能的码段，从而达到整个码序列是一个有最大似然值的序列。第八十九页，共99页。维特比译码(续)(n,k,N)码，共有2k(N-1)种状态，每个状态节点有2k条入支路，2k条出支路。将汇集在第N级每节点上的两条路径表示的序列与接收序列比较，保留码距小的，丢弃码距大的，保证在第N级节点上只留下2N-1条幸存路径。在以后的各级上，采用同样的方法比较—选择，保留2N-1条幸存路径。（当两条路径的码距相同时，任意选择一条）当发送序列接收完毕后，在网格图的终结处加上N个已知信息（一般用0）作为结束信息，从而确定最终的幸存路径。第九十页，共99页。维特比译码(续)

例：（3，1，3）卷积码发送信息位为1101为使移存器中的信息位全部移出，在信息位后面加入了3个“0‖