通信原理(第7版)第11章差错控制编码ppt课件.ppt

《通信原理(第7版)第11章差错控制编码ppt课件.ppt》由会员分享，可在线阅读，更多相关《通信原理(第7版)第11章差错控制编码ppt课件.ppt（165页珍藏版）》请在三一办公上搜索。

1、,美工设计：陈英 技术支持：张嘉等人,课 件,差错控制编码,通信原理（第7版）,第11章,樊昌信 曹丽娜 编著,本章内容,第11章 差错控制编码,基本概念 差控方式 编码原理 码距 码率 性能简单实用码 奇偶监督 恒比码 正反码 线性分组码 汉明码 监督矩阵H、生成矩阵G 循环码 生成多项式 编译方法 BCH码 RS码卷积码 编译原理 代数表述 几何表述Turbo码 低密度奇偶校验码网格编码调制 TCM信号的产生与解调,11.1,概 述,开销。这就好像我们运送一批玻璃杯一样，为了保证运送途中不出现打烂玻璃杯的情况，我们通常都用一些泡沫或海棉等物将玻璃杯包装起来，这种包装使玻璃杯所占的容积变大，

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

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

4、信。,ARQ的主要优点：与前向纠错（FEC）方法相比,ARQ系统的原理方框图,11.2,纠错编码的基本原理,规则：使码组中“1”的个数为偶数,情形1：没有冗余 不能发现错误,情形2：加入冗余 可以发现错误,冗余, 另外4个码组,许用码组,禁用码组,也不能 纠正 错误 。,（奇数个错码）,这时，能够发现 2个以下错码，或者纠正 1位 错码 。,综上所述：,- 信息码元位数,- 编码后码字位数,不同的编码方法，检错 或 纠错 能力也不同 。,分组码和系统码,编码后的每组长度为 n=k+r,就是分组码,前面的例子：,信息位与监督位关系：,分组码 的 符号：,分组码 的 结构：,（n，k）,码长 (n

5、)：码组（码字）中的码元个数。,码重(W)：码组中“1”的数目。,“ 0 1 1 0 1 1” 的距离为 3,码重和码距,码重为 3,对于3位的编码组，可用3维空间来说明,（4个许用码组之间）,各顶点之间沿立方体各边行走的几何距离 码距=2,码距的几何意义：,对于（n，k）分组码，有以下结论：,最小码距d0 和检纠错能力的关系,检个错码，要求：,纠个错码，要求：,纠 t 个错码,同时检 e 个错码，要求：,证明：,11.3,纠错编码的性能,系统带宽和信噪比的矛盾,右图所示的某种编码性能,可见：不增大发送功率, 就能 降低误码率约一个半数量级。,A点,B点,2PSK调制,可见：能节省功率 2 d

6、B 称为编码增益,D点,2PSK调制,C点,因此，纠错码主要应用于功率受限而带宽不太受限的信道中。, 付出的代价是带宽增大。,设编码前 系统工作在图中C点， 提高速率后Pe由C点升到E点。,传输速率RB 和 信噪比Eb/n0的关系,若希望提高RB，则必使Eb/n0下降，误码率Pe增大。,这时付出的代价仍是带宽增大。,但采用纠错编码后，Pe仍可降到 D点。,11.4,简单的实用编码,11.4.1 奇偶监督码,偶数监督,奇数监督,适用： 检测随机出现的零星差错。,编码规则：,只有一位监督元,（不知错码位置）,很高 （因为只有一位监督位）。,码率：,编出的码字应为 ：,若收到 10011，检测结果为

7、：,根据偶数监督规则：,-存在错码,若收到 00011，检测结果为：,可见，奇偶监督码 不能 检出 偶数 个错码。,解,-认为无错,1 1 0 1 1,11.4.2 二维奇偶监督码,编码规则：,（方阵码）,检测方法：计算接收码组中“1”的数目，就可知是否有错。,11.4.3 恒比码,适用：用于电报传输系统或其他键盘设备产生的字母和符号。,编码规则：,(等重码),个许用码组，可分别用来代表26个英文字母 及 其他符号。,11.4.4 正反码,编码规则：,设码长n = 10，其中信息位 k = 5，监督位 r = 5。其编码规则为：, 一种能够纠错的编码。,译码方法：,= 00000,校验码组和错

8、码的关系：,按上表判决: 无错码,信息位中有奇数个“1”，校验码组 = 00000,发送码组为11001 11001,纠检能力：,（n, k）线性分组码,11.5,线性码：按照一组线性方程构成的代数码。 即每个码字的监督码元是信息码元的线性组合。,基本概念,代数码：建立在代数学基础上的编码。,-监督关系式,若 S=0，认为无错（偶监督时）；若 S=1，认为有错 。,若要构造具有纠错能力的（n，k）码，则需增加督元的数目。,当“=”成立时，构造的线性分组码 称为汉明码,校正子,构造原理,只有一位监督元,-检错,汉明码的,能纠1位错码 的高效 线性分组码,(7, 4)汉明码,由表可见:,仅当一位错

9、码的位置在a2 、a4、a5 或a6 时， 校正子S1为1；否则S1为 0。,同理：,(A),移项运算解出监督位,(A),接收端译码检错纠错过程,以上构造的线性分组码 ，称为汉明码。,最小码距：,当 n很大和 r 很小时，码率 Rc 接近 1。,编码效率：,汉明码特点:,d0 = 3 （纠1或检2）,r 是不小于3的任意正整数,答：最小码距:,故能 纠1 或检2,d0 =3,线性分组码的一般原理,将前面(7, 4)汉明码的监督方程：,改写为：,表示成如下矩阵形式：,H -监督矩阵,简记为,H,A = a6 a5 a4 a3 a2 a1 a0,0 = 000,监督矩阵,或,转置,转置,“T”,r

10、 行n 列,= P Ir ,r k 阶矩阵,r r 阶方阵, 典型监督矩阵,H 矩阵的性质, H 的行数 等于监督位的数目r 。,H 的每行中“1”的位置表示相应码元之间存在的监督关系。, H的各行应该是线性无关的，否则得不到r个线性无关的监督关系式。,若一矩阵能写成典型阵形式 P Ir ，则其各行一定是线性无关的。,将上面汉明码例子中的监督位公式：,改写成矩阵形式：,G -生成矩阵,或者写成：,P 阵,式中，Q 为一个k r 阶矩阵，它为P 的转置，即:,Q = PT,P 阵,Q 阵,将Q的左边加上1个k k 阶单位方阵，就构成矩阵:,生成矩阵，,或者,因此，若找到了码的G，则编码的方法就完

11、全确定了。,具有IkQ形式的称为典型生成矩阵。,由典型G得到的码称为系统码。,称为,典型生成矩阵,码组A中，信息位的位置不变，监督位附在其后。,由它可以产生整个码组，即有:,G 矩阵的性质, G 矩阵的各行是线性无关的。,由式,可以看出:,任一码组A都是G的各行的线性组合。,G共有k行，若它们线性无关，则可以组合出2k 种不同的码组A。,它恰是有k位信息位 的全部码组。,G 和H 的关系,校正子与错误图样,设发送码组为一个n列的行矩阵 A，,接收码组的行矩阵 B,则发送码组和接收码组之差就是错码矩阵（错误图样）：,式中,(模2),A = B + E,在接收端，若能求出错误图样E 就能恢复出发送

12、码组 A ，即,任一发送码组 A 都应满足式：,对于接收码组 B，可通过计算:,来进行检测。,将 B = A + E 代入上式，可得,0,因此，可根据S 是否为0 判断 接收码组 是否 出错 !,由以上分析可知，（n,k) 线性分组码译码的三个步骤：,2) 由S 找到错误图样E；,3) 由公式 A = B + E 得到译码器译出的码组。,（n,k) 线性分组码译码的三个步骤：, 封闭性,A1和A2,(A1+A2),证明：若A1和A2是两个码组，则有,A1 HT = 0 和 A2 HT = 0，,将两式相加，有,A1 HT + A2 HT = (A1 + A2) HT = 0, 最小距离,（证毕

13、）,线性分组码的性质,表中所列的(7, 4)汉明码的最小码距 d0 = ？,d0 =3,纠1 或检2,根据性质 只需找最小码重无需两两码组比较,循 环 码,西安电子科技大学 通信工程学院,课件制作：曹丽娜,它除了具有线性分组码的一般性质外，还具有循环性。,11.6,表中的第 2 码组向 右移一位即得到第 5 码组；,(7, 3)循环码,11.6.1 循环码原理,表中的第 6 码组向 右移一位即得到第 3码组 。,码字（）的多项式可表示为：,码多项式,多项式的系数就是码组中的各码元，x 仅是码元位置标记 。,n=7 时,码字（码组）的多项式表示,1. 码多项式的按模运算,一般说来，若一个整数m

14、可以表示为,（Q 为整数）,m p (模n),则在模n 运算下，有,码多项式的按模运算：,或,则,式中，码多项式系数之间的加法和乘法仍按模2 运算。,解 运算过程：,即有,则有,这是因为，A(x)正是 A(x) 代表的码组向左循环移位 i 次的结果。,循环码的码多项式,则 A(x) 也是该编码中的一个许用码组。,循环码组,，其码长n = 7。,现给定 i = 3，则,左移 i 位,3,由上述分析可见:,2. 循环码的生成矩阵G,生成矩阵G可由k 个线性无关的码组构成。,引思：,那么，如何寻找这 k 个线性无关的码组呢？,因此，用这个线性无关的码组可构成该循环码的生成矩阵G ，即,r = n-k

15、 = 7-3 =4，,解,码组中唯一一个4次码多项式代表的,或,据此，可以写出此循环码多项式A(x):,任一循环码多项式 A(x) 都是 g(x) 的倍式，可以写成,而生成多项式 g(x) 本身也是一个码组，即有,A (x) = g(x),A(x) = h(x)g(x),码组 A(x)是一个 (n k)次多项式，故 xkA(x) 是一个n次多项式。,可知， xk A(x)在模 (xn + 1) 运算下也是一个码组，故可写成,由式,上式左端分子和分母都是n次多项式，故商式Q(x) = 1。上式可化成,将 和 代入上式，化简后得到,A(x) = g(x),A(x) = h(x)g(x),求(7,

16、3)循环码的生成多项式 g(x) 。,将 (x7+1) 进行因式分解：,解：,n k,即有,或,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)=,A(x)= m(x)g(x),即,（1）用 xn-k 乘 m(x)，得到 xn-k m(x),（2）作g(x) 除 xn-k m(x)，即,将信元左移（n k）位，附上（n k）个0，预留给督元。,得到余式 r(x)，作为监督码元, 即得循环码的码多项式。,系统循环码

17、的编码步骤：,（3）作 A(x) = xn-k m(x)+r(x),通常是 非系统码,编码电路：可采用(n k)级移位寄存器组成的除法电路实现。,设,例如，上例 (7, 3) 循环码的生成多项式 g(x) = x4 + x2 + x + 1， 其编码电路：,2. 循环码的解码,目的：检错 和 纠错。,若能除尽，则无错；若除不尽而有余项，则表示在传输中发生错误。,11.6.3 截短循环码,例：构造一个能够纠正1位错码的(13, 9)码。可由(15, 11)循环码的码组中选出前两信息位均为“0”的码组，构成一个新的码组集合。在发送时不发送这两位“0”。于是发送码组成为(13, 9)截短循环码。,截

18、短目的：在设计纠错编码方案时，若找不到合适的码长n及信息位k 时，可以把循环码的码长截短以得到符合要求的编码。,截短方法：设给定一个(n, k)循环码，它共有 2k 种码组，现使其前 i (0 i k)个信息位全为“0”，于是它变成仅有 2k- i 种码组。然后从中删去这 i 位全“0”的信息位，最终得到一个(n i , k i )的线性码截短循环码。,截短循环码性能：循环码截短前后至少具有相同的纠错能力，并且编解码方法仍和截短前的方法一样。,11.6.4 BCH码,解决了生成多项式与纠错能力的关系问题，可以在给定纠错能力要求的条件下寻找到码的生成多项式。有了生成多项式，编码的基本问题就随之解

19、决了。,BCH码的重要性:,何谓BCH码？,BCH码的分类：,汉明码是能够纠正单个随机错误的码。可以证明，具有循环性质的汉明码就是能纠正单个随机错误的本原BCH码。,BCH码的性能：,码长n 与监督位、纠错个数 t 之间的关系： 对于正整数m (m 3)和正整数t 1，且除得尽(2m -1)），则为非本原BCH码。,BCH码的设计：,在工程设计中，一般不需要用计算方法去寻找生成多项式g(x)。因为前人早已将寻找到的g(x)列成表，故可以用查表法找到所需的生成多项式。,教材353页的表11-7 给出了码长n 127的二进制本原BCH码生成多项式。,在上表中的(23, 12)码称为戈莱(Golay

20、)码。其最小码距为7，能纠3个随机错码；其生成多项式系数 (5343)8 = (101 011 100 011)2，对应g(x) = x11 + x9 + x7 + x6 + x5 + x + 1，且解码容易，实际应用较多。,BCH码的长度都为奇数。在应用中，为了得到偶数长度的码，并增大检错能力，可以在BCH码生成多项式中乘上一个因式(x + 1)，从而得到扩展BCH码(n + 1, k)。扩展BCH码相当于在原BCH码上增加了一个校验位，因此码距比原BCH码增加1。扩展BCH码已经不再具有循环性。例如，广泛实用的扩展戈莱码(24, 12)，其最小码距为8，码率为1/2，能够纠3个错码和检4个

21、错码。它比汉明码的纠错能力强很多，付出的代价是解码更复杂，码率也比汉明码低。此外，它不再是循环码了。,扩展BCH码：,11.6.5 RS码, 它是一类具有很强纠错能力的多进制BCH码。 由里德和索洛蒙(Reed Solomon)提出。,一个能够纠t个错误符号的m进制的RS码有如下参数：,最小码距： d0 = 2t + 1个 符号， 或 q（ 2t + 1）比特,码组长度： n = m 1 = 2q 1个符号，,督元长度： r = n-k = 2t 个符号， 或 2tq 比特,信元长度： k 个符号， 或 k q个比特,参数,或 q(2q 1)个比特,RS码能够纠正t个m进制错码，即能纠正码组中

22、t个不超过q位连续的二进制 错码，RS码特别适用于存在突发错误的信道，例如，移动通信网等衰落信道中。此外，它是多进制纠错编码，特别适合用于多进制调制 的场合。,RS码的生成多项式：,g(x) = (x + )(x +2) (x +2t),式中， 是伽罗华域GF(2q )中的本原元素。,卷 积 码, 一种非分组码,11.7,非分组码概念：,分组码:, 每个码组中的督元仅与本码组中的k个信元有约束关系。,非分组码:,即一个码组中的督元 监督着N个信息段。,卷积码的符号: (n, k, N ),N - 编码约束度， 表示编码过程中互相约束的码段个数；,nN - 编码约束长度，表示编码过程中互相约束的

23、码元个数。,卷积码的码率: R =k / n,(n, 1, N ) 简单, 常用,N 或nN 也反映了卷积码编码器的复杂度。,11.7.1 卷积码的基本原理,编码器原理方框图,存储以前的k(N-1)个信息码,当前 K个,共有N 段移存器，每段k 级,如图所示的(n, k, N) = (3, 1, 3)卷积码编码器。,共有3 段移存器，每段1 级（存储1个信元）,每次输入1b，输出 3b,分析：,信息位-,设移存器初始是全零状态，当输入信息序列 ：,则编码器输出序列：,结果为系统码形式。,信息位bi 的监督位和各信息位之间的约束关系如下图中虚线所示：（编码约束度 N=3，约束长度 nN =33

24、=9）,卷积码的表述方法：,11.7.2 卷积码的代数表述,仍以前面 (3, 1, 3)卷积码为例分析。设各级移存器初始是“0”状态，则监督位di、ei和信息位bi之间的关系可以写为:,上式：,表示的卷积码也是一种线性码。,可完全由 H 或 G 所确定。,监督矩阵 H,监督矩阵,生成矩阵,左式可以改写为,注：上面两式及后面的式子中“” 表示“”。,将上式用矩阵表示成：,H,可见，卷积码的监督矩阵H 是一个有头无尾的半无穷矩阵。,且自第7行起，每两行的左端比上两行多了3个“0”。,此外，该矩阵的每3列的结构相同，只是后3列比前3列向下移了两行。,这种截短监督矩阵的结构形式如下图所示：,因此，通常

25、只需研究产生前 nN 个码元（此例 nN=9）的监督矩阵。,(3, 1, 3),由图可见,约束长度,此例 (3, 1, 3) 码中的截短监督矩阵有如下形式：,式中：, 2阶单位方阵；,Pi 2 1 阶矩阵，i = 1, 2, 3；,02 2阶全零方阵。,H1 =,式中 In-k (n k)阶单位方阵； Pi (n k) k 阶矩阵； 0n-k (n k)阶全零方阵。,h是卷积码的一个最重要矩阵。只要给定h，则可构造出H1 。,H1的末行：,h = PN 0n-k PN-1 0n-k PN-2 0n-k P1 In-k,H1,截短监督矩阵H1 一般形式：,基本监督矩阵h, b1 d1 e1 b2

26、 d2 e2 b3 d3 e3 b4 d4 e4 = b1 b1 b1 b2 b2 (b2 + b1) b3 (b3 + b1) (b3 + b2 + b1) b4 (b4 + b2) (b4 + b3 + b2) ,生成矩阵 G,上例(n, k, N) = (3, 1, 3)中的输出码元序列可写成：,对比：,可见，循环码的G也是一个半无穷矩阵，其特点：每一行的结构 相同，只是比 上一行 向 右 退后 n = 3 列 。,可知，此码的生成矩阵G 即为上式最右矩阵：,式中， I1 为 一阶单位方阵； Qi 为 1 2 阶矩阵； 0 为一阶全零方阵。,截短生成矩阵 G1,与H1矩阵比较可见，Qi

27、是 矩阵 Pi 的转置：,Qi = PiT,一般说来，截短生成矩阵具有如下形式：,(i = 1, 2, ),只要给定 g，则可从已知的信息位得到整个编码序列。,基本生成矩阵g,式中: Ik k阶单位方阵； Qi (n k)k阶矩阵； 0k k阶全零方阵。,G1矩阵第一行,g Ik Q1 0k Q2 0k Q30k QN,截短生成矩阵一般形式,分类：,代数解码： 利用编码本身的代数结构进行解码，不考虑信道的统计特性。,概率解码（最大似然解码）： 基于信道的统计特性和卷积码的特点进行计算。,11.7.3 卷积码的解码,如：大数逻辑解码（门限解码），适用 nN 较短的卷积码。,序贯解码: 适用无记忆

28、信道,维特比算法：当码的 nN 较短时，效率更高、速度更快,约束长度,首先将接收信息位暂存于移存器中，并从接收码元的信息位和监督位计算校正子。然后，将计算得出的校正子暂存，并用它来检测错码的位置。在信息位移存器输出端，接有一个模2加电路；当检测到输出的信息位有错时，在输出的信息位上加“1”，从而纠正之。,1 大数逻辑解码,工作原理,这里的错码检测是采用二进制码的大数逻辑解码算法。它利用一组“正交”校验方程进行计算。,这里的“正交” 定义：若被校验的那个信息位出现在校验方程组的每一个方程中，而其他的信息位至多在一个方程中出现，则称这组方程为正交校验方程。这样就可以根据被错码影响了的方程数目在方程

29、组中是否占多数来判断该信息位是否错了。,下面将用一个实例来具体讲述这一过程。,c1 = b1c2 = b2c3 = b3c4 = b1 + b4c5 = b1 + b2 + b5c6 = b1 + b2 + b3 + b6 ,(2, 1, 6)卷积码,编码器方框图：,监督位和信息位的关系：,（当输入序列为b1 b2 b3 b4 时）,S1 = c1 + b1S2 = c2 + b2S3 = c3 + b3S4 = c4 + b1 + b4S5 = c5 + b1 + b2 + b5S6 = c6 + b1 + b2 + b3 + b6,监督位,监督关系式,在上式中，只有信息位b1出现在每个方程

30、中，监督位和其他信息位均最多只出现一次。因此，在接收端解码时，考察b1、c1至b6、c6等12个码元，仅当b1出错时，式中才可能有3个或3个以上方程等于“1”。从而能够纠正b1的错误。,正交校验方程组,上式经过简单线性变换后，得出如下正交校验方程组：,解码器方框图：,2 卷积码的几何表述,1）码树图,以前面 (3, 1, 3) 卷积码为例：,并设 M1，M2和 M3 的初始状态 000,(n, k, N),(3, 1, 3) 码树图：,每条树枝上标注的码元为输出比特，每个节点为移存器的状态a b c d,若信息位 1 1 0 1,编码输出 111 110 010 100,(3, 1, 3) 码

31、树图：,(3, 1, 3) 码树图：,若信息位 1 1 0 1,编码输出 111 110 010 100,码树图原则上还可以用于解码。,发送序列,若信息位 1 1 0 1,编码输出 111 110 010 100,发送序列,一般说来，码树搜索解码法并不实用，因为随着信息序列的增长，码树分支数目按指数规律增长；在上面的码树图中，只有4个信息位，分支已有24 = 16个。但是它为以后实用解码算法建立了初步基础。,2）状态图,码树图状态图,由(3, 1, 3)编码器结构可知：,前一状态 a只能转到下一状态a或b； 前一状态b只能转到下一状态c或d， 等等。,按照 表中的规律 画出的状态图：,由表看出

32、：,利用状态图可方便地从输入序列得到输出序列。例如：,输入信息位 1 1 0 1,编码输出 111 110 010 100,111,110,010,100,可见：在第4时隙以后的网格图形完全是重复第3时隙的图形。 这是因为此(3, 1, 3)卷积码的约束长度为3。,3）网格图,将状态图在时间上展开 网格图,图中画出了5个时隙。,当输入信息位为11010时，在网格图中的编码路径：,这时的输出编码序列：111 110 010 100 011。,基于上面的状态图和网格图，下面将讨论维特比解码算法。,3 维特比解码算法,基本原理,仍用上面(3, 1, 3)卷积码的例子来说明维特比算法的原理。,设发送信

33、息位为1101，为了使图中移存器的信息位全部移出，在信息位后面加入3个“0”，故编码后的发送序列为 111 110 010 100 001 011 000设接收序列为 111 010 010 110 001 011 000,现在，比较网格图中的这8条路径和接收序列之间的汉明距离。,(n, k, N),第1步,例如，由出发点状态 a 经过 3级 路径后到达状态 a 的两条路径中：上面一条为“000 000 000”，它和接收序列“111 010 010”的汉明距离=5下面一条为“111 001 011”，它和接收序列 的汉明距离=3同样，由出发点a经过3级路径后到达状态b、c和d的路径分别都有两

34、条，故总共有8条路径。 下表中列出了这8条路径和其汉明距离。,接收序列 111 010 010 110 001 011 000,将到达每个状态的两条路径的汉明距离作比较，将距离小的一条路径保留，称为幸存路径。若两条路径的汉明距离相同，则可任意保存一条。这样就剩下4条路径： 2, 4, 6，8,第2步,接收序列 111 010 010 110 001 011 000,按照表中的幸存路径画出的网格图示于下图中：,上例卷积码的约束度 N = 3，需要存储和计算 8 条路径的参量。,故维特比解码算法适合约束度较小（N 10）的编码。 对于约束度大的卷积码，可以采用其他解码算法。,由此可见，维特比解码算

35、法的复杂度 随约束长度 N 按指数形 式 2N 增长。,Turbo 码, 一种特殊的链接码 (1993),11.8, 属于复合码类,由于分组码和卷积码的复杂度随码组长度或约束度的增大按指数规律增长，所以为了提高纠错能力，不要单纯增大码的长度，而是将两种或多种简单的编码组合成复合编码。,Turbo码 基本原理,Turbo码的编码器在两个并联或串联的分量码编码器之间增加一个交织器，使之具有很大的码组长度，能在低信噪比条件下得到接近理想的性能。,Turbo码的译码器有两个分量码译码器，译码在两个分量译码器之间进行迭代译码，故整个译码过程类似涡轮（turbo）工作，所以又形象的称为Turbo码。,RS

36、CC编码器和卷积码编码器之间的主要区别：从移存器输出端到信息位输入端之间有反馈路径。原来的卷积码编码器像是一个FIR数字滤波器。增加了反馈路径后，它就变成了一个IIR滤波器，或称递归滤波器。,Turbo码 编码器,它由一对递归系统卷积码(RSCC)编码器和一个交织器组成：,因为输出中第1位是信息位，所以它是系统码。,RSCC编码器举例：,它是一个码率等于1/2的卷积码编码器，输入为bi，输出为bici 。,矩阵交织器：,它由容量为 (n-1)m 比特的存储器构成：,矩阵交织器原理图：,再按列的方向输出,将信号码元 按行的方向 输入存储器,卷积交织器：,低密度奇偶校验码,11.9,(Low-De

37、nsity Parity-Check ，LDPC),当码组很长时才具有优良性能，广泛地应用于 移动通信、无线局域网和光纤通信等多种领域,LDPC码简介：,LDPC码分类：,LDPC码和普通的奇偶监督码一样，可以由有n列、m行的监督矩阵H 确定；n是码长，m是校正子个数。但是其H矩阵和普通奇偶监督码的有所不同：它是稀疏矩阵，即矩阵中“1”的个数很少，密度很低；设H矩阵每列有 j 个“1”，每行有 k个“1”，则应有 j m，k n，且 j 3。其H 矩阵的任意两行的元素不能在相同位置上为“1”，即H矩阵中没有四角由“1”构成的矩形。LDPC码通常用上述3个参量(n, j, k)表示。在编码时，设

38、计好H矩阵后，由H 矩阵可以导出生成矩阵G。这样，对于给定的信息位，不难算出码组。,LDPC码的构造：,LDPC码的解码方法也和一般的奇偶监督码的解码方法不同。 基本的解码算法称为置信传播算法，通常简称BP算法。 这种算法实质上是求最大后验概率，类似于一般的最大似然准则解码算法，但是它需要进行多次迭代运算，逐步逼近最优的解码值。LDPC码的具体编解码算法十分复杂，这里不再深入讨论。,LDPC码的解码：,网格编码调制, 将纠错编码和调制相结合,11.10, 同时节省功率和带宽,Trellis Coded Modulation , TCM,11.10.1 TCM的基本概念,回顾QPSK系统：,QP

39、SK是一个4相相移键控系统，它的每个码元传输2 比特信息。若在接收端判决时因干扰而将信号相位错判至相邻相位，则将出现错码。现将系统改成8PSK，它的每个码元本可以传输3 比特信息。但是，仍令每个码元传输 2 比特信息，第3 比特用于纠错码，例如，采用码率为2/3的卷积码。这时，接收端的解调和解码是作为一个步骤完成的，不像传统作法，先解调得到基带信号后再为纠错去解码。,右图示出了8PSK信号 星座图中的8个信号点：假设信号振幅等于1，则相邻两信号点的欧氏距离d0=0.765,两个信号序列的欧氏距离越大，即它们的差别越大，则因干扰造成互相混淆的可能性越小。,为了利用卷积码维特比解码的优点，这时仍然

40、需要用到网格图。但是，和卷积码维特比解码时的网格图相比，在TCM中是将这些波形映射为网格图，故TCM网格图中的各状态是波形的状态。,图中的信号点代表某个确定相位的已调信号波形。,11.10.2 TCM信号的产生,集划分方法,将信号星座图划分成若干子集，使子集中的信号 点间距离比原来的大。每划分一次，新的子集中信号点间的距离 就增大一次。,8PSK星座图划分。 A0 是8PSK信号星座图 d0 是任意两个信号点 间的距离。该星座被划分为B0和B1两个子集，在子集中相邻信号点间距离为d1。,可见：d2 d1 d0,由上图可见，这个卷积码的约束长度等于3。编码器输出的前两个比特c1和c2用来选择星座

41、图划分的路径，最后1个比特c3用于选定星座图第3级（最低级）中的信号点。,卷积码编码器的方框图：,通常采用维特比算法，但是现在的网格图表示的状态是波形，而不是码组。解码器的任务是计算接收信号序列路径和各种可能的编码网格路径间的距离。若所有发送信号序列是等概率的，则判定与接收序列距离最小的可能路径（又称为最大似然路径）为发送序列。因为卷积码是线性码，它具有封闭性，故要考察的路径距离与所用的测试序列无关。所以，不失一般性，可以选用全“0”序列作为测试序列。,11.10.3 TCM信号的解调,TCM信号的解调算法：,用全“0”序列作为测试序列时，如下图中虚线路径U 所示。图中还用实线示出另一许用波形

42、序列路径V，它从全“0”序列路径分开又回到全“0”序列路径。,8PSK信号的解码路径。,若发送序列是全“0”序列，但是接收序列有错误，使接收序列路径离开全“0”路径然后又回到全“0”序列，且中间没有返回状态a，则解码器需要比较此接收序列路径和U的距离与接收序列路径和V的距离之大小。若后者小，则将发生一次错误判决。这里的距离是指欧氏距离。,自由欧氏距离是指许用波形序列集合中各元素之间的最小距离。它决定了产生错误判决的概率。自由欧氏距离越大，错误判决概率越小。在上例中，U和V两条路径间的欧氏距离d由下式决定：,自由欧氏距离Fed ：,上式是按照在欧氏空间求矢量和的方法计算的。因此，,另外一种许用波

43、形序列的路径是，U1WU3（见上图）。它和 V序列相似，从状态a开始，离开U（虚线路径），再回到状态a。这个路径和U的距离等于,即 d 2,比较上面两条路径可见，路径U1WU3和路径V相比，前者和路径U的距离更小。并且，可以逐个验证，这是和路径U距离最小的许用序列的路径。因此，按照上述定义，上式中的距离就是这种编码的自由欧氏距离。故可以将其写为,dFed = 2,另一方面，未编码的QPSK信号的相继码元（波形）没有约束。若将其自由欧氏距离作为参考距离dref，则由下图可知:,所以，可以证明，和未编码QPSK系统相比，8PSK的TCM系统可以获得的渐近编码增益等于,在下表中列出了通过大量仿真计算得出的部分8PSK/TCM系统的(渐近)编码增益。,配套辅导教材：,曹丽娜 樊昌信,编著,国防工业出版社,整理知识 归纳结论梳理关系 引导主线剖析难点 解惑疑点强化重点 点击考点,谢谢！,