第10章 Turbo码

Size: px

Start display at page:

Download "第10章 Turbo码"

枫蒙
5 years ago
Views:

1 第六章 Turbo 码虽然软判决译码级联码和编码调制技术都对信道码的设计和发展产生了重大影响, 但是其增益与 Shannon 理论极限始终都存在 ~ 3dB 的差距因此, 在 Turbo 码提出以前, 信道截止速率 R 0 一直被认为是差错控制码性能的实际极限,Shannon 极限仅仅是理论上的极限, 是不可能达到的根据 Shannon 有噪信道编码定理, 在信道传输速率 R 不超过信道容量 C 的前提下, 只有在码组长度无限的码集合中随机地选择编码码字并且在接收端采用最大似然译码算法时, 才能使误码率接近为零但是最大似然译码的复杂性随编码长度的增加而加大, 当编码长度趋于无穷大时, 最大似然译码是不可能实现的所以人们认为随机性编译码仅仅是为证明定理存在性而引入的一种数学方法和手段, 在实际的编码构造中是不可能实现的在 1993 年于瑞士日内瓦召开的国际通信会议 (ICC'93) 上, 两位任教于法国不列颠通信大学的教授 C.Brrou A.Gaviux 和他们的缅甸籍博士生 P.thitimajshima 首次提出了一种新型信道编码方案 Turbo 码, 由于它很好地应用了 shannon 信道编码定理中的随机性编译码条件, 从而获得了几乎接近 shannon 理论极限的译码性能

Caud Brrou Dav Forny Turbo 码又称并行级联卷积码 (PCCC,Para Concatnatd Convoutiona Cod), 它巧妙地将卷积码和随机交织器结合在一起, 在实现随机编码思想的同时, 通过交织器实现了由短码构造长码的方法, 并采用软输出迭代译码来逼近最大似然译码可见,Turbo 码充分利用了 Shannon 信道编码定理的基本条件, 因此得到了接近

2 Caud Brrou Dav Forny Turbo 码又称并行级联卷积码 (PCCC,Para Concatnatd Convoutiona Cod), 它巧妙地将卷积码和随机交织器结合在一起, 在实现随机编码思想的同时, 通过交织器实现了由短码构造长码的方法, 并采用软输出迭代译码来逼近最大似然译码可见,Turbo 码充分利用了 Shannon 信道编码定理的基本条件, 因此得到了接近 Shannon 极限的性能在介绍 Turbo 码的首篇论文里, 发明者 Brrou 仅给出了 Turbo 码的基本组成和迭代译码的原理, 而没有严格的理论解释和证明因此, 在 Turbo 码提出之初, 其基本理论的研究就显得尤为重要 J.Hagnaur 首先系统地阐明了迭代译码的原理, 并推导了二进制分组码与卷积码的软输入软输出译码算法由于在 Turbo 码中交织器的出现, 使其性能分析异常困难, 因此 S.Bndtto 等人提出了均匀交织 (UI,Uniform intravr) 的概念, 并利用联合界技术给出了 Turbo 码的平均性能上界 D.Divsaar 等人也根据卷积码的转移函数, 给出了 Turbo 码采用 MLD 时的误比特率上界对于 Turbo 码来说, 标准联合界在信噪比较小时比较宽松, 只有在信噪比较大时才

3 能实现对 Turbo 码性能的度量因此,T.M.Duman I.Sason 和 D.Divsaar 等人在 Gaagr 限等已有性能界技术的基础上进行改进. 扩展了 Turbo 码性能界的紧致范围 D.Divsaar 等人还根据递归系统卷积码的特点提出了有效自由距离的概念, 并说明在设计 Turbo 码时应该使码字有效自由距离尽可能大 L.C.Prz 等人从距离谱的角度对 Turbo 码的性能进行了分析, 证明可以通过增加交织长度或采用本原反馈多项式增加分量码的自由距离来提高 Turbo 码的性能他们还证明了 Turbo 码虽然自由距离比较小, 但其低重量码字的数目较少, 从而解释了低信噪比条件下 Turbo 码性能优异的原因, 并提出了交织器增益的概念 S.Doinar 的研究表明,Turbo 码的最小距离码字主要由重量为的输入信息序列生成, 是形成错误平台的主要原因为提高高信噪比条件下 Turbo 码的性能, 就必须提高低重输入信息序列的输出码重 J.Sghrs 系统地分析了 Turbo 码的距离特性由于交织器的存在, 无法给出 Turbo 码自由距离的严格数学表示, 相应地也出现了许多分析和计算 Turbo 码最小距离重量分布和性能上限的方法 A.Ambroz 还构造了 Turbo 码的树图, 用来作为计算码字距离谱的工具此外,R. Tannr E.Offr 和 K.Engdah 分别从代数和统计的角度对 Turbo 码进行了分析考虑到 Turbo 码的延时问题,E. Ha 等人提出了面向流的 Turbo 码也可以用其他系统模型采描述 Turbo 码及其迭代译码过程 :T.Richardson 把 Turbo 码作为一个动力学系统进行描述 ;A. Khandani 则把 Turbo 码考虑成一个周期性的线性系统 ;J.Lartyy, X.G 和 F. Kschischang 描述了

4 Turbo 码的图模型 ; 在图模型的基础上,MaKay 等人证明了 Turbo 码的校验矩阵与 LDPC 码的校验矩阵是等价的, 从而可以将 Turbo 码看成一类特殊的 LDPC 6.1 Turbo 码的编码 Turbo 码的编码结构可以分为并行级联卷积码 (PCCC) 串行级联卷积码 (SCCC) 和混合级联卷积码 (HCCC) 三种, 如图 6.1 所示交织器分量编码器 1 分量编码器穿刺矩阵复接 (a) 外码编码器交织器内码编码器 (b) 交织器 1 并行编码器外码编码器交织器内码编码器 (c)

5 外码编码器交织器 1 内码编码器 1 交织器 (d) 内码编码器图 6.1 Turbo 码的几种编码结构 (a)pccc(b)sccc(c)hccc-i (d)hccc-ii 1993 年,C.Brrou 提出的 Turbo 码就是 PCCC 结构, 主要由分量编码器交织器穿刺矩阵和复接器组成分量码一般选择为递归系统卷积 (RSC) 码, 当然也可以选择分组码非递归卷积 (NRC) 码以及非系统卷积 (NSC) 码通常两个分量码采用相同的生成矩阵 ( 也可不同 ) 若两个分量码的码率分别为 R 1 和 R, 则 Turbo 码的码率为 : RR + (6.1) 1 R = R 1 R RR 1 在 AWGN 信道上对 PCCC 的性能仿真证明, 当 BER 随 SNR 的增加下降到一定程度时, 就会出现下降缓慢甚至不再降低的情况, 一般称为误码平台 (rror foor) 为解决这个问题,1996 年,S.Bndtto 提出了串行级联卷积码 (SCCC) 的概念, 它综合了 Forny 串行级联码 (RS 码 + 卷积码 ) 和 Turbo 码 (PCCC) 的特点, 在适当的信噪比范围内, 通过迭代译码可以达到非常优异的译码性能 Bndtto

6 的研究表明, 为使 SCCC 达到比较好的译码性能, 至少其内码要采用递归系统卷积码, 外码也应选择具有较好距离特性的卷积码若外码编码器和内码编码器的编码速率分别为 R o 和 R I, 则 SCCC 的码率 R 为 : R=R o R I (6.) HCCC 是将前两种方案结合起来, 从而既能在低 SNR 下获得较好的译码性能, 又能有效地消除 PCCC 的误码平台, 称为混合级联卷积码综合串行和并行级联的方案很多, 这里只给出两种常见的方案, 一是采用卷积码和 SCCC 并行级联的编码方案, 如图 6.1(c) 所示 ; 另一种是以卷积码为外码, 以 PCCC 为内码的混合级联编码结构, 如图 6.1(d) 所示我们主要讨论 PCCC 结构的卷积码为便于讨论, 将 PCCC 编码结构重画为图 6.(a) 所示 u = ( u0, u1,, uk 1) (0) (0) (0) (0) v = v0 v1 vk 1 (,,, ) π 分量编码器 1 分量编码器 (a) v v = ( v, v,, v ) (1) (1) (1) (1) 0 1 K 1 = ( v, v,, v ) () () () () 0 1 K 1

7 u (0) v (1) v π u (b) () v 图 6. PCCC 编码器基本结构系统包括输入信息序列 u, 两个 (,1,v) 系统反馈 ( 递归 ) 卷积编码器, 一个交织器 ( 用 π 表示 ) 假设信息序列含有 K* 个信息比特以及 v 个结尾比特 ( 以便返回到全 0 态 ), 其中 v 是第一个编码器的约束长度, 因此有 K=K*+v, 信息序列可表示为 : u = ( u, u, ) (6.3) 0 1 uk 1 由于编码器是系统的, 因此信息序列就等于第一个输出序列, 即 : u= v = ( v, v, v ) (6.4) (0) (0) (0) (0) 0 1 K 1 第一个编码器输出的校验序列为 : v = ( v, v, v ) (6.5) (1) (1) (1) (1) 0 1 K 1 交织器对 K 个比特进行扰序处理, 得到 u, 第二个编码器输出的校验序列为 : v = ( v, v, v ) (6.6) () () () () 0 1 K 1 从而最终的发送序列 ( 码字 ) 为 : v = ( v v v, v v v, v v v ) (6.7) (0) (1) () (0) (1) () (0) (1) () K 1 K 1 K 1

8 因此, 对该编码器来说, 码字长度 N=3K,R t =K*/N=(K-v)/3K, 当 K 比较大时, 约为 1/3 在图 6.(b) 中, 两个分量码都是 (,1,4) 系统反馈编码器, 具有相同的生成矩阵, 为 : G ( D) = [1 (1 + D ) /(1 + D+ D + D + D )] (6.8) 对于 Turbo 码来说, 需要注意以下几点 : (1) 为了得到靠近 Shannon 限的系统性能, 信息分组长度 ( 交织器大小 )K 一般比较大, 通常至少几千个比特 () 对于分量码来说, 一般选择相同结构, 且约束长度较短, 通常 v 4 (3) 递归分量码 ( 由系统反馈编码器产生 ) 会比非递归分量码 ( 前馈编码器 ) 有更好的性能 ; (4) 高码率可通过穿刺矩阵产生, 如图 6.(b) 中, 可通过交替输出 (1) v 和 () v 得到 1/ 的编码速率 (5) 通过增加分量码和交织器也可得到较低编码速率的 Turbo 码, 如图 6.3 所示

9 u (0) v 分量编码器 1 (1) v π 1 分量编码器 () v π 分量编码器 3 (3) v 图 6.3 速率 R=1/4 的 Turbo 码 (6) 最好的交织器能够对比特以伪随机的方式进行排序, 传统的块交织器 ( 行 - 列 ) 在 Turbo 码中性能不好, 除非 bock 长度很短 ; (7) 由于交织器只是对比特位置进行重新排序, 因此, 交织后的序列 u 与原始序列 u 具有相同的重量 ; (8) 对每个分量码来说, 用 BCJR( 或 MAP) 算法作为 SISO 译码器能够获得最好的性能 ; 因为 MAP 译码器使用了前向 - 后向算法, 信息是以 bock 的形式进行的, 因此, 对第一个分量译码器来说, 附加 v 个 0 比特能够让它返回到全 0 态 ; 但对于第二个译码器来说, 由于交织器的作用, 将不能返回到全 0 态图 6.(b) 所示的编码器, 穿刺后得到 1/ 的码率此时穿刺矩阵可 1 0 以为 P = 0 1, (0) (1) (0) () 其输出就为 v = ( v0 v0, v1 v1, ) Turbo 码有两个缺点 :(1) 较大的译码时延, 这是由于 bock 长度较

10 大译码需要多次迭代造成的这样对于实时业务或高速数据的传输就非常不利 ;()BER 在 10-5 后会出现误码平台, 这是由于 Turbo 码的重量分布造成的对于某些对 BER 要求较高的应用就不适合, 当然通过交织器的设计能够提供码字的最小距离, 从而降低误码平台 ======================================= 例 6.1: 结尾卷积码的重量谱考虑 (,1,4) 非系统前馈卷积码, 编码器生成矩阵为 : G ( ) = [ ] (6.9) ff D D D D D D 该码的最小自由距离是 6, 对应的输入信息序列为 (110 ) 如果该编码器转为系统反馈形式, 生成矩阵为 : ( ) [1 (1 ) /(1 )] G (6.10) D = + D + D+ D + D + D fb 由于码是相同的, 因此自由距离仍是 6, 但在这种情况下, 最小重量码字是由信息序列 ( ) 产生的, 即 u(d)=1+d 5 两个不同的编码器得到相同的码, 但信息序列和码字之间的映射关系不同说明 :Turbo 码编码的对象是长度固定的数据序列, 即在编码过程中首先将输入信息数据分成长度与交织长度相同的数据序列, 然后对每个数据序列进行编码如果 Turbo 码的分量码在数据序列编码结束时利用结尾比特使得网格图状态归零, 则 Turbo 码可等效为一个分组码设每个编码器信息长度为 K*=K-4, 附加 4 个比特让编码器返回到全 0 态, 此时, 我们就可得到 (N,K*)=(K,K-4) 的分组码, 码率为 R=(K-4)/K, 当 K 很大时, 约等于 1/ 这个分组

11 码含有 K-5 个重量为 6 的码字, 因为这些码字的信息序列可以从 K -5 个任意位置开始, 都可以得到相同的码字类似的分析显示, 对于重量为 7 及其他较低重量, 码字数都很多在表 6.1(a) 里, 给出了 (3,1) 码的所有重量谱, 其中 K=16

12 表 6.1 两个 (3,1) 码的重量谱 (a) 结尾卷积码 (b) 并行级联码重量码字数重量码字数 ~4 0 1~ ~3 0 7~3 0 从上表可以看出, 在每个重量的码字数增加迅速, 在重量为 16(bock 长度的一半 ) 时达到峰值, 还可看出, 在低端, 码的重量谱很密集, 这也导致在低 SNR 下有相对较高的错误概率通常, 如果一个非结尾卷积码具有 A d 个重量为 d 的码字, 这些码字是由信息序列集合 {u(d)} 产生, 则信息序列集合 {Du(D)} 也能产生 A d

13 个重量为 d 的码字, 依此类推结尾卷积码本质上也具有相同的特性换句话说, 卷积码是时不变的, 这个特性能够说明为什么在结尾卷积码中低重量码字数较多当一个伪随机交织器用于产生一个并行级联码时, 又会如何? ======================================= ======================================= 例 6.: 并行级联码的重量谱选用式 (6.10) 所示的系统反馈卷积编码器, 输入序列长度 K=16, 长度为 16 的交织图案为 : = [0,8,15,9, 4, 7,11,5,1,3,14, 6,13,1,10, ] (6.11) 扰序后的输入序列用相同的校验生成器 (1 + D ) /(1 + D+ D + D + D ) 进行编码, 因此会得到不同的校验序列为了与例 6.1 进行比较, 我们用周期 T= 的穿刺矩阵 : 1 0 P = 0 1 (6.1) 进行处理, 这样同样会得到一个 (3,1) 的码, 该码的重量谱如表 6.1(b) 所示观察 (a) 和 (b) 我们可以看出两者有明显的不同, 自由距离由 6 减小到 5, 但只有 1 个码字, 更重要的是, 重量为 6~9 的码字数明显减少了, 这表示在并行级联码中, 低重量码字向高重量码字偏移了, 这种偏移称为谱细化 (spctra thinning) 例如, 重量为的输入信息序列 u=( ), 这样会得到低重量校验序列 v (1) =( ), 因此, 没有交织器, 结尾卷积码产生的码

14 字重量为 6 交织后的输入序列假定为 u =( ), 则产生的校验序列为 v () =( ), 复用 v (1) 和 v (), 用式 (6.1) 式进行穿刺, 得到的校验序列为 ( ) 这样, 对于同是重量为的输入序列, 在并行级联码中就产生了重量为 8 的码字值得注意的问题 : (1) 不同的交织器和穿刺矩阵会产生不同的结果 ; () 谱细化对最小自由距离的影响很小, 但却能大大减小低重量码字的数目 ; (3) 随着分组长度和交织器大小 K 的增加, 并行级联卷积码的重量谱近似于一个随机分布 ======================================= 由此可看出, 交织器在 Turbo 码中起着关键的作用, 传统的块交织在 Turbo 中并不适用, 一定要做到伪随机化, 这样构造出的码重量谱就近似于一个二项式分布,Shannon 曾证明过, 只有随机 ( 二项式 ) 重量分布的码是性能达到 Shannon 限的前提产生随机交织图案的方法很多, 例如用如下简单算法 : km( m + 1) cm (mod K ), 0 m< K (6.13) 来产生一个序号映射函数 cm c m + 1(mod K), 其中 K 是交织器大小,k 是一个奇数例如,K=16,k=1, 可得到 : (c 0,c 1,,c 15 )=(0,1,3,6,10,15,5,1,4,13,7,,14,11,9,8) (6.14)

15 这意味着交织后序列 u 中的序号 0( 输入比特 u 0 ) 与原始序列 u 中 u = u ), 的序号 1 相对应 ( 即 0 1 这样交织器为 : 16 u 中的 1 与 u 中的序号 3 相对应, = [1,3,14, 6,13,1,10,, 0,8,15,9, 4, 7,11,5] (6.15) C0 C1 C C3 C4 C5 C6 C7 C8 C9 C10 C11 C1 C13 C14 C15 U U 按照 U 的升序 (0,1,,,15) 重新排列, 所对应的 U 序列值就是交织图案 : 该交织图案如果向右循环移动 8 位, 就得到式 (6.11) 所示的交织图案对于 K 是的指数, 可以证明这些交织器具有与随机交织类似的统计特性, 因此用于 Turbo 码中具有很好的性能 6. Turbo 码的迭代译码 Turbo 码的迭代译码器基本结构如图 6.4 所示 ( 假设速率 R=1/3 没有穿刺的并行级联码 ), 它使用了两个 SISO 译码器 (MAP 算法 ) 在每个时间单元, 从信道接收到三个输出值, 一个是对应着信息比特 u 别用 = v, 用 (1) r (0) 和 (0) r 表示, 其他两个对应着校验比特 (1) v () r 表示, 这样接收到的向量 (3K 维 ) 为 : ( r (0) (1) () (0) (1) () (0) (1) () 0 r0 r0, r1 r1 r1, rk 1rK 1rK 1) r = (6.16) 和 v (), 分

16 (0) Lr c () Lr c (0) Lr c L () ( u ) (1) Lr c 译码器 1 L ( u) Lr (1) (0) c + - L (1) ( u ) 解交织交织器 L (1) ( u ) 交织器译码器 - L () ( u ) () (0) + L ( u) Lr () ( ) L u c 解交织图 6.4 迭代译码器的基本结构现在假设每个发送比特的映射关系为 0 1和 1 + 1, 软输出的 AWGN 信道给定接收值 r, 发送信息比特 u 的对数似然值 (L (0) (0) (0) (0) 值 ) 定义为 Lv ( r ) Lu ( r ) (0) ( r ) Lu = ( 译码前 ): ( ) ( ) ( ) (0) ( u = 1) ( ) ( ) p u r p r u pu = n = n p u r p r u pu (0) (0) =+ 1 =+ 1 ( =+ 1) (0) (0) = 1 = 1 ( = 1) (0) (0) ( Es / N0 )( r 1 p r ) u = + 1 pu ( =+ 1) pu ( =+ 1) = n + n = n + n (0) p r pu ( 1) ( Es / N0 )( r 1 = + ) pu ( = 1) E (0) s (0) = {( r 1) ( r ) } pu ( = + 1) n N pu ( = 1) 0 E pu ( = + 1) = + + (6.17) s (0) (0) 4 r n = Lcr La( u) N0 p ( u = 1) (0) 其中 E s /N 0 是信道 SNR, u 和 r 都是用 E s 归一化的,L c =4E s /N 0 是信道可靠度因子,L a (u ) 是比特 u 的先验 L 值在发送校验比特是

17 v ( j) ( ) 的情况下, 给定接收到的值为 r j,j=1,,l 值 ( 译码前 ) 为 : ( ) ( ) L v r = Lr + L v = Lr, j= 1, (6.18) ( j) ( j) ( j) ( j) ( j) c a c 因为在一个线性码中信息比特等概, 校验比特为 +1 和 -1 的概率也是相同的, 因此校验比特的先验 L 值为 0, 即 : ( j) ( = + 1) ( ) ( = 1) p v ( j) La( v ) = n = 0, j = 1, j p v (6.19) ( 注意 : 对于译码器 1 的第一次迭代, L ( u ) a 也等于 0, 之后, 信息比特的先验 L 值就被另一个译码器输出的外部 L 值所取代, 后面会讲到 ) 接收到的信道 L 值 ( 软信息 ) Lr (0) c (for u ) 和 Lr (1) Lr c (for 进入译码器 1, 交织后的信道 L 值 ( 软信息 ) (0) (for u ) 和 (for () v ) 进入译码器, 译码器 1 的输出包括项 : (1) 给定接收到的向量 ( 部分 ) c (1) v ) () Lr c r r r, r r, rk rk (0) (1) (0) (1) (0) (1) (1) (1) (1) (1) 以及先验输入向量 L a La ( u0), La ( u1), La ( uk 1), 每个信息比特的后验 L 值 ( 译码后 ) 为 L (1) (1) ( = + 1 r1, La ) p u ( u ) = n (1) p( u = 1 r1, L ; a ) () 与每个信息比特相关的外部后验概率值 ( 译码后 ) (1) (1) (0) () L ( u) = L ( u) Lcr + L ( u), 该信息经交织后送给译码器, 作为先验值 L () ( u ) 同样地, 译码器的输出也包括两项 : a

18 (1) L () () ( = + 1 r, La ) p u ( u ) = n () p( u = 1 r, La ), 其中 r () 是 ( 部分 ) 接收向量, L () a 是先验输入向量 ; () () (0) (1) L ( u) = L ( u) Lcr + L ( u) 后验 L 值, 经过解交织后, 作为先验值器 1 的输入这样, 每个译码器的输入包含三项 : 软信道 L 值是译码器产生的外部 L (1) ( u ) 反馈作为译码 a Lr Lr (1) (0) c c ( 或 () Lr c ) 以及从另一个译码器传送的外部后验 L 值 L ( u ) L ( u ) = ( 或 () (1) a L ( u ) L ( u ) = ) 注意 : 在译码器 1 的 (1) () a () (1) 初始迭代时, 外部后验 L 值 L ( u ) = L ( u ) 就是初始先验 L 值 a L ( u ) ( 对于等概信息比特, 该值为 0), 在译码器 1 的随后迭代中, a 先验 L 值 L (1) ( u ) 就用接收到的外部后验 L 值 L () ( ) a u ( 进行解交织处理后 ) 代替 ; 对于译码器, 其第一次迭代和随后的迭代都是相同的, 外部后验 L 值一直都是 L (1) ( u ) 译码迭代处理, 每个译码器将其外部 L 值传送给另一个译码器, 形成一个 Turbo 的效果, 如图 6.5 所示, 使得译码结果越来越可靠

图 6.5 汽车发动机的 Turbo 结构经过一定次数的迭代后, 译码后的信息比特就从译码器输出的后验 L 值为 -1 L () ( u ) 中判决得到, 如果该 L 值为正, 就判为 +1, 否则就判值得一提的是 :Turbo 的很多特性与 LDPC 很类似, 如编码方案都是产生随机重量分布的码译码方法都是在迭代过程中利用了后验概率似然值都利用了外部信息的概念等实际上,

19 图 6.5 汽车发动机的 Turbo 结构经过一定次数的迭代后, 译码后的信息比特就从译码器输出的后验 L 值为 -1 L () ( u ) 中判决得到, 如果该 L 值为正, 就判为 +1, 否则就判值得一提的是 :Turbo 的很多特性与 LDPC 很类似, 如编码方案都是产生随机重量分布的码译码方法都是在迭代过程中利用了后验概率似然值都利用了外部信息的概念等实际上, 正是由于 Turbo 码的出现, 才使得人们对 LDPC 码的优点有了重新的认识 ====================================== 例 6.3: 使用 Log-MAP 算法进行迭代译码考虑一个 PCCC 结构的 Turbo 码, 它是由两个 (,1,1) 系统递归卷积码构成, 如图 6.6(a) 所示, 生成矩阵为 : G(D)=[1 1/(1+D)] (6.0)

20 u (0) v (1) v π (a) () v S 0 +1/+1,+1 S 1-1/-1,+1-1/-1,+1 S1 1-1/-1,-1-1/-1,-1-1/-1,-1-1/-1,-1 S0 S0 S0 S0 S +1/+1,-1 (b) 图 6.6 (a) 一个态 Turbo 编码器 (b)(,1,1) 分量码的译码网格图 (K=4) 考虑输入序列长度为 K=4, 包括一个结尾比特, 这样就相当于一个 (1,3) 的码, 码率 R=1/4 K=4 的分量码译码网格图如图 6.6 (b) 所示, 其中的分支映射关系为 0 1和设输入 bock 表示为 u = [u 0, u 1, u, u 3 ], 交织后的输入 bock 表示为 u = [ u, u, u, u ] = [ u, u, u, u ] p p = [ p, p, p, p ] (1) (1) (1) (1) (1) () () () () () 0 1 3, 第一个分量码的校验向量为, 第二个分量码的校验向量为 = [ p, p, p, p ] 我们可以将 1 个发送比特表示成一个阵列形式, 如图 6.7(a) 所示, 其中输入向量 u 决定的校验向量 p (1) 在前两行, 交织后的输入向量 u 决定的校验向量 p () 在前两列

21 u u 0 1 (1) p 0 (1) p u u 3 (1) p (1) p () p 0 () p () p 1 () p (a) (1,3) PCCC (b) 编码后的值 (c) 接收到的 L 值 (d) 第一次行译码后的外部 L 值 () 第一次列译码后的外部 L 值 (f) 第一次行和列译码后的软输出 L 值 (g) 第二次行译码后的外部 L 值 (h) 第二次列译码后的外部 L 值 (i) 第二次行和列译码后的软输出 L 值图 6.7 (1,3)PCCC 的迭代译码过程为了更好地描述, 假设给定特定的比特, 如图 6.7(b) 所示同时, 假设信道信噪比 E s /N 0 =1/4(-6.0dB), 这样, 对应于接收向量 r 的信道 L 值为 : (0) (1) () (0) (1) () (0) (1) () (0) (1) () = r0 r0 r0, r1 r1 r1, r r r, r3 r3 r3 E Lr = 4 r = r, = 0,1,,3, j= 0,1, (6.1) ( j) s ( j) ( j) c N0 同样为了简化描述, 接收到的信道 L 值如图 6.7(c) 所示

22 在译码器 1 的第一次迭代中 ( 行译码 ), 应用 og-map 算法到态 (, 1,1) 码的网格图中, 来计算每个输入比特的后验 L 值及对应的传送给译码器的外部后验 L 值 L (1) ( u ), 以 L (1) ( u ) 类似地, 在译码器的第一次迭代中,og-MAP 算法用从译码器 1 收到的外部后验 L 值 L (1) ( u ) 来计算每个比特的后验 L 值 L () ( u ), 以及对应的传送给译码器 1 的外部后验 L 值 L () ( u ) 随后的译码就这样迭代进行 ======================================= 在继续讨论这个例子之前, 我们用 og-map 算法对后验 L 值 Lu ( ) 外部后验 L 值 L ( u ) 的一般式进行推导为了简化表示, 定义发送和向量为 v=(v 0, v 1, v, v 3 ), 其中 v =(u,p ), =0,1,,3, u 是输入比特,p 是校验比特类似地, 接收到的向量表示为 r=(r 0, r 1, r, r 3 ), 其中 = ( r, r ) r u p,=0,1,,3, u r 是接收到的信元, 对应于发送的输入比特 u ; r 是接收到的信元, 对应于发送的输入比特 p ; 输入比特 p 的后验 L 值为 ( 见第五章公式 5.67 和 5.7): pu ( = + 1 r) Lu ( ) = n pu ( = 1 r) 其中 = n ( s, s) Σ ( s, s) Σ + Σ 表示在时刻状态为 s s + ps ( = s, s+ 1 = s, r) ps ( = s, s+ 1 = s, r) (6.) =,+1 时刻状态为 = + 1, 这种状态转移是由输入比特 u = + 1 所引起的, 所有这些状态对的集合就构成 + Σ s s

23 ps (, s, ) α γ β + = 其中 * * * ( s ) ( s, s) ( s) r (6.3) α * ( s ) * ( s, s) γ 和 * β + () 1 s 数域表达 ( 见第五章公式 5.88) 注意: * ( s ) 是 MAP 算法中 α γ 和 β 的对 α * γ ( s, s) 和 * β + () 1 s 分别表示时刻之前时刻和时刻之后的接收序列对时刻输入比特估计的影响对一个连续输出 AWGN 信道, 信噪比为 E s /N 0, 我们可得到 : ul( ) 分支度量 : * a u Lc γ ( s, s) = + r v, = 0,1,,3 (6.4a) 前向度量 : α * * * * + 1 ( s) = max s σ (, ) ( ), 0,1,,3 γ s s + α s = (6.4b) * * * * 后向度量 : β ( s ) = max s σ γ (, ) 1 1( ) s s β s (6.4c) * * α ( S ) = β ( S ) = 0, α ( S ) = β ( S ) = 初始条件为 : * * 分支度量进一步可写为 : * ul a( u) Lc γ ( s, s) = + ur + pr ( ) u p u p (6.5) = La( u) + Lr c u + Lr, 0,1,,3 c p = 从图 6.6(b) 可看出, 为了确定比特 u 0 的后验 L 值, 在式 (6.) 中的每个和式只有 1 项, 因为此时在网格图中只有 1 个 +1 和 -1 的比特转移, 因此, 比特 u 0 的后验 L 值可表示为 :

24 Lu ( ) = n ps ( = S, s= S, r) n ps ( = S, s= S, r) * * * = α0( S0) + γ0( s = S0, s = S1) + β1( S1) * * * α0( S0) + γ0( s = S0, s = S0) + β1( S0) 1 1 * = + La( u0) + Lr c u + Lr 0 c p + β 0 1( S1) 1 1 * La( u0) + Lr c u Lr 0 c p + β 0 1( S0) = L r + L ( u ) + L ( u ) c u0 a 0 0 (6.6a) 其中 L( u ) Lr + β ( S) β ( S ) (6.6b) * * 0 c p 表示 u 0 的外部后验 L 值式 (6.6a) 表明, 在 og-map 译码器的输出端计算出的 u 0 的后验 L 值包括三部分 : Lr c u 0 : 对应于比特 u 0 的接收到的信道 L 值, 是译码器输入的一部分 L ( ) a u 0 :u0 的先验 L 值, 也是译码器输入的一部分除了译码器 1 的第一次迭代, 该项等于从另一个译码器输出接收到的 u 0 的外部后验 L 值 ( 对于译码器 1 的第一次迭代, L ( ) 0 a u 0 = ) L ( ) u 0 :u0 的外部后验 L 值, 不依赖于 Lr c u或 L ( ) 0 a u 0 另一个译码器作为先验输入该项送给类似地, 我们可计算比特 u 1 的后验 L 值, 从图 6.6(b) 可看出, 在式 (6.) 中的每个和式都有项, 因为此时在网格图中有个 +1 和 -1 的比特转移, 因此, 比特 u 1 的后验 L 值可表示为 :

25 [ r r ] Lu ( ) = n ps ( = S, s= S, ) + ps ( = S, s= S, ) [ ps = S s= S r + ps = S s= S r ] n (,, ) (,, ) { { * * * = max* α1( S0) + γ1( s = S0, s = S1) + β( S1), * * * α1( S1) + γ1( s = S1, s = S0) + β( S0) * * * max * α1( S0) + γ1( s = S0, s = S0) + β( S0), * * * α1( S1) + γ1( s = S1, s = S1) + β( S1) = Lr + L( u) + L( u) (6.7a) c u1 a 1 1 其中 1 * * 1 * * L( u1) = max * + Lr c p+ α1( S0) + β( S1), 1( 1) ( 0) Lr c p+ α S + β S 1 * * 1 * * max * Lr c p+ α1( S0) + β( S0), + Lr 1( 1) ( 1) c p+ α S + β S (6.7b) 特别说明: 在上面的推导中, 使用了一个等式即 :max*(z+x, z+y)=z+max*(x,y) 同样会得到 u 和 u 3 的后验 L 值 : Lu ( ) = Lr + L( u ) + L( u ) (6.8a) c u a 其中 1 * * 1 * * L( u) = max * + Lr c p+ α s( S0) + β3( S1), ( 1) 3( 0) Lr c p+ α S + β S 1 * * 1 * * max * Lr c p+ α ( S0) + β3( S0), + Lr c p+ α ( S1) + β3( S1) } }

26 (6.8b) Lu ( ) = Lr + L( u) + L( u) (6.9a) 3 c u a * * 1 * * L( u3) = Lr c p+ α 3 3( S1) + β4( S0) Lr c p+ α 3 3( S0) + β4( S0) (6.9b) = α ( S ) α ( S ) * * L ( ) u 注意 : 接收到的校验信元 r p 不会影响 3 3, 在图 6.6(b) 可看出, 在 =3 时刻两个分支 p 3 =0, 因此 r p 没有携带任何有助于译码 3 的信息在计算外部后验 L 值 L ( u ),=0,1,,3 时, 需要用到前向度量和后向度量利用式 (6.4) 和 (6.5), 并对信息比特 L 值和校验比特 L 值采用简化表示, 即 : Lu Lr c u + La( u) 和 p c p 可得到 : L Lr,=0,1,,3, * 1 a1( S0) = ( Lu + L ) 0 p0 (6.30a) * 1 a1( S1) =+ ( Lu + L ) 0 p0 (6.30b) * 1 * 1 * a( S0) = max * ( Lu + L ) ( ) 1 p + a 1 1( S0), + Lu L 1 p + a 1 1( S1) (6.30c) * 1 * 1 * a( S1) = max * + ( Lu + L ) ( ) 1 p + a 1 1( S0), Lu L 1 p + a 1 1( S1) (6.30d)

27 * 1 * 1 * a3( S0) = max * ( Lu + L ) ( ) p + a ( S0), + Lu L p + a ( S1) (6.30) * 1 * 1 * a3( S1) = max * + ( Lu + L ) ( ) p + a ( S0), Lu L p + a ( S1) (6.30f) ( ) 1 ( u p ) * β 3 S0 = L + L (6.30g) ( ) ( u p ) * β 3 S1 =+ L L (6.30h) 3 3 * 1 * 1 * β( S0) = max * ( Lu + L ) ( ) p + β 3( S0), + Lu + L p + β 3( S1) (6.30i) * 1 * 1 * β( S1) = max * + ( Lu L ) ( ) p + β 3( S0), Lu L p + β 3( S1) (6.30j) * 1 * 1 * β1( S0) = max * ( Lu + L ) ( ) 1 p + β 1 ( S0), + Lu + L 1 p + β 1 ( S1) (6.30k) * 1 * 1 * β1( S1) = max * + ( Lu L ) ( ) 1 p + β 1 ( S0), Lu L 1 p + β 1 ( S1) (6.30) 对所有, 校验比特的先验 L 值 L ( p ) = 0, 因为对于等概信息比特 a 的线性码, 校验比特也是等概的 ; 而且, 与信息比特不同, 校验比特的 L 值不被迭代译码算法所更新, 即在整个译码过程中校验比特的 L

28 值保持不变因此, L = Lr + L( p) = Lr 最后计算外部后验 L 值 : * * 0 p p c p a c p L ( u ) = L + β ( S ) β ( S ) (6.31a) 1 * * 1 * * L( u1) = max * + Lp + α 1 1( S0) + β( S1), 1 1( 1) ( 0) Lp + α S + β S 1 * * 1 * * max * Lp + α 1 1( S0) + β( S0), + Lp + α 1 1( S1) + β( S1) (6.31b) 1 * * 1 * * L( u) = max * + Lp + α ( S0) + β3( S1), ( 1) 3( 0) Lp + α S + β S 1 * * 1 * * max * Lp + α ( S0) + β3( S0), + Lp + α ( S1) + β3( S1) * * (6.31c) L ( ) ( ) ( ) u = α S α S (6.31d) 我们注意到, 在计算外部 L 值 L( u ) 时, u L 并没有在公式中出现, 这表示比特 u 的外部 L 值不直接依赖于 u 的先验 L 值 ====================================== 继续例 6.3 设接收到的信道 L 值如图 6.7(c) 所示, 根据式 (6.30) 和 (6.31), 我们可计算出外部后验 L 值在译码器 1( 行译码 ) 对比特 u 0 u 1 u u 3 进行第一次迭代译码时, 考虑到在从式 (6.30) 可得到 : L u 中初始化先验 L 值为 0,

29 1 ( ) * a1( S 0) = = 0.45 (6.3a) 1 ( ) * a1( S 1) = = (6.3b) * 1 1 a( S0) = max* ( ) 0.45, + ( ) = 1.34 (6.3c) * 1 1 a( S1) = max* + ( ) 0.45, ( ) = 0.44 (6.3d) * 1 1 a3( S0) = max* ( ) , + ( ) = 1.76 (6.3) * 1 1 a3( S1) = max* + ( ) , ( ) =.3 (6.3f) 1 ( S ) ( ) 0 * β 3 0 = = (6.3g) 1 ( S ) ( ) 1.6 * β 3 1 =+ + = (6.3h) * 1 1 β( S0) = max* ( ) + 0, + ( ) = 1.59 (6.3i) * 1 1 β( S1) = max* + ( ) + 0, ( ) = 3.06 (6.3j)

30 * 1 1 β1( S0) = max* ( ) , + ( ) = 3.44 (6.3k) * 1 1 β1( S1) = max* + ( ) , ( ) = 3.0 (6.3) 然后, 根据式 (6.31), 我们得到 : L ( u ) = L + β ( S ) β ( S ) = = 0.3 (1) * * 0 p (6.33a) (1) 1 * * 1 * * L ( u1) = max * + Lp + α 1 1( S0) + β( S1), 1 1( 1) ( 0) Lp + α S + β S 1 * * 1 * * max * Lp + α 1 1( S0) + β( S0), + Lp + α 1 1( S1) + β( S1) {[ ] [ ]} = max* , { } max* [ ],[ ] = 0.38 (6.33b) L ( u ) = (6.33c) (1) (1) L ( u ) = (6.33d) 3 这些外部信息值经过行译码的第一次迭代后如图 6.7(d) 所示现在, 使用这些外部后验 L 值作为译码器 ( 列译码 ) 的先验输入, 就有 L = Lr + L (1) ( u), 从式 (6.30) 得到 : u c u

31 1 ( ) * a1( S 0) = = 0.36 (6.34a) 1 ( ) * a1( S 1) = = 0.36 (6.34b) * 1 1 a( S0) = max* ( ) , + ( ) 0.36 = 0.44 (6.34c) * 1 1 a( S1) = max* + ( ) , ( ) 0.36 = 1.31 (6.34d) * 1 1 a3( S0) = max* ( ) , + ( ) = 1.7 (6.34) * 1 1 a3( S1) = max* + ( ) , ( ) = 1.68 (6.34f) * 1 β 3( S0) = ( ) = (6.34g) * 1 β 3( S1) =+ ( ) = (6.34h)

32 * 1 1 β( S0) = max* ( ) 0.485, + ( ) =.05 (6.34i) * 1 1 β( S1) = max* + ( ) 0.485, ( ) = 1.55 (6.34j) * 1 1 β1( S0) = max* ( ) +.05, + ( ) =.51 (6.34k) * 1 1 β1( S1) = max* + ( ) +.05, ( ) =.83 (6.34) 需要注意的是, 与式 (6.3) 相比, 式 (6.34) 中的 u 1 和 u 要互相颠倒, 因为经过交织后 1 () * * 0 p u = u 和 u = u1 再根据式 (6.31), 可得到 : L ( u ) = L + β ( S ) β ( S ) = = 0.88 () {[ ] [ ]} L ( u ) = max* , {[ ] [ ]} max* , (6.35a) = (6.35b)

33 L ( u ) = 0.69 (6.35c) () () 3 1 L ( u ) = 0.04 (6.35d) ( 同样要注意 u 1 和 u 的位置问题 ) 这些外部信息值经过列译码的第一次迭代后如图 6.7() 所示最后, 4 个信息比特经过第一次完整的迭代译码后的后验 L 值为 : () () (1) () L ( u0) = Lcru + L ( 0 a u0) 1 L ( u0) 就是译码器输出的 + L ( u0) = = 0.4 (6.36a) () () (1) () L ( u) = Lcru + L ( a u) 1 L ( u) 就是译码器输出的 + L ( u) = = 0.8 (6.36b) () () (1) () L ( u1) = Lcru + L ( 1 a u1) 1 L ( u1) 就是译码器输出的 + L ( u1) = = (6.36c) () () (1) () L ( u3) = Lcru + L ( 3 a u3) 1 L ( u3) 就是译码器输出的 + L ( u3) = =.3 0 (6.36d) 结果如图 6.7(f) 所示如果此时进行判决, 就会得到 : uˆˆˆ= 1, u = 1, u = 1 (6.37) 0 1 注意 : 此时比特 u 1 就会被判决出错

34 第二次迭代时, 译码器 1 的先验 L 值码器输出的外部后验 L 值 L (1) ( u ) 就是第一次迭代后译 a L () ( u ), 然后进行相同步骤的迭代译码过程, 就会得到 6.7(g~i) 所示的值, 经过次迭代后, 所有信息比特就会被正确译码 6.3 Turbo 码的性能界码字错误概率为 : P( E) AP (6.38) w d d ( d d) fr 比特错误概率 : P( E) BP (6.39) b d d ( d d) fr 在二值输入连续输出 AWGN 信道下,P d 为 : P d dre b = Q N 0 dre frreb N d f N0 其中 ( ) = ( ) f x Q x x 0 b (6.40) 将 (6.40) 代入 (6.38) 和 (6.39), 可得到 : d RE Pw( E) f Ad N0 ( dfr d) b / 0 ( ) fr b RE N d d frreb = f AX ( ) N0 X= REb / N0 (6.41)

35 d RE Pb( E) f Bd N0 ( dfr d) b / 0 ( ) fr b RE N d d frreb = f BX ( ) N0 X= REb / N0 (6.4) 因此, 为了得到 Turbo 码的性能界, 我们需要知道自由距离码字 WEF A(X) 和比特 WEF B(X) d fr 6.4 交织器设计 Turbo 码系统中交织器的作用是用于减少校验比特之间的相关性, 进而在迭代译码过程中降低误比特率设计性能较好的交织器的特点和基本原则 : 通过增加交织器的长度, 可以使译码性能得到提高, 好的交织器可使总的码字的自由距离随交织器长度的增加而增加, 即提供一定的交织器距离交织器应该使输入序列尽可能地随机化, 从而避免编码生成低重码字的信息序列在交织后编码仍旧生成低重码字, 导致 Turbo 码的自由距离减小交织深度与码重参数是交织器设计时两个重要的参数指标, 但它们之间还没有找到定量的关系式目前, 对交织器的设计一般都是采用计算机仿真的方法来搜索出较满意的交织器从信息论的角度看, 在 turbo 码编码器中引入交织器的目的是实现随机性编码, 但是对于长度有限的的输入信息序列, 在交织深度有

36 限的实际情况下, 实现完全随机编码是不可能的交织深度越短, 随机性越差, 这时采用按照一定的确定规则设计的交织器可以得到比伪随机交织器更好的性能而交织深度较大时, 伪随机交织器或者满足一定距离属性要求的随机交织器可以获得比较好的性能根据不同的设计思想, 交织器大致可分为两类 : 规则交织器和随机交织器规则交织器通常按照一定的规则映射来实现交织, 通常比较容易实现交织前后比特之间的距离如果交织器能够通过交织在原始序列中距离较近的信息比特经过交织后有一定的距离, 则可以在一定程度上提高 Turbo 码的性能在穿刺 Turbo 码中, 如果设计的交织器能够实现对系统比特的均匀保护, 则有助于提高 Turbo 码的性能例如, 在采用伪随机交织器时, 原始序列中某个位于奇数位置的比特经过交织后可能在交织序列的偶数位置出现, 这样经过编码后它对应的两个校验比特也分别位于两个校验序列的奇数位置和偶数位置根据前述穿刺方法, 这两个校验比特要么都被删除, 要么都被保留在译码时, 那些两个校验比特均被删除的信息比特出现错译的概率大大增加, 降低了 Turbo 码的性能因此所设计的交织器如果能够保证交织后信息比特位置的奇偶性不变, 则有助于提高性能如果在 Turbo 码的编码器中引入交织器, 那么在译码中就必须有与其相对应的解交织器, 即需要两个设备来分别实现交织和解交织过

37 程如果所设计的交织器满足对称特性, 则交织器和解交织器就是完全相同的, 从而可以用同一个设备实现几种典型的交织器设计 : 块交织器块交织器是最简单的一类交织器, 如图 6.8 所示其交织映射过程为 : 将数据序列按行写入 m n 矩阵, 然后按列的顺序读出, 即完成交织 ; 相应的解交织过程就是将交织后的数据按列的顺序写入, 按行的顺序读出写入读出 1 n n+ 1 n+ n ( m 1) n+ 1 ( m 1) n+ mn 图 6.8 块交织器其交织映射函数可表示为 : [ ] Ii ( ) = ( i 1) mod n m+ ( i 1) / n + 1, i= 1,,..., N (6.43) 其中 N 为交织深度循环移位交织器循环移位交织器的映射为 : I(i)=a*i mod N (6.44) 其中 a 是步长, 为与交织长度 N 互素的正整数, 且 a N 1 步长 a 的值决定了原始序列中相邻的比特经过交织后在交织序列中

38 的距离例如图 6.8 中交织长度 N=19 a=17 的循环移位交织器的输入输出位置 00 循环移位交织器的输入输出位置图示例输出位置输入位置图 6.9 循环移位交织器分组螺旋交织器分组螺旋交织器首先将数据序列按行的顺序写入 m n 矩阵, 其中 m 与 n 互素在交织时, 从矩阵的左上角开始向右下方向读取数据, 如下图所示在行的方向和列的方向分别对索引取模 m 和 n, 即若令 r i 和 c i 分别表示第 i 个比特的行索引和列索引, 则分组螺旋交织器的数据读取顺序为 : r i+1 = r i +1 mod m

39 c i+1 =c i +1 mod n 图 6.10 分组螺旋交织器伪随机交织器伪随机交织器的交织过程可简单描述如下 : 长为 n 的信息序列 d 1 d d 3 d 4 d 5 d 6 d 7 d 8 相应的 n 个随机数按大小排列随机数交织后的信息序列 d 3 d 7 d 5 d 1 d 4 d 8 d d 6 在以往的信道编码中使用交织器的目的主要是抗信道突发错误, 而在 Turbo 码中, 交织器除了抗信道突发错误外, 主要是改变码的重量分布, 控制编码序列的距离特性

ThemeGallery PowerTemplate

ThemeGallery PowerTemplate 7 7.8 7.8. 前言 7.8.2 卷积编码器表示 7.8.3 卷积译码公式 7.8.4 卷积码的特性 7.8.5 最常用的卷积码 7.8.6 卷积码在 GSM 系统中的应用 7.8.7 卷积码在 WCDMA 系统中的应用 2 7.8. 线性分组码由两个整数 n 和 k 以及一个生成矩阵或者生成多项式决定, 其中 k 是输入的数据比特数,n 是输出比特数其特点就是每个 n 元组码字由 k 元组输入消息唯一决定