ThemeGallery PowerTemplate

Size: px

Start display at page:

Download "ThemeGallery PowerTemplate"

琴玖杨
5 years ago
Views:

1 7

2 前言卷积编码器表示卷积译码公式卷积码的特性最常用的卷积码卷积码在 GSM 系统中的应用卷积码在 WCDMA 系统中的应用 2

3 7.8. 线性分组码由两个整数 n 和 k 以及一个生成矩阵或者生成多项式决定, 其中 k 是输入的数据比特数,n 是输出比特数其特点就是每个 n 元组码字由 k 元组输入消息唯一决定 k/n 为编码效率, 即编码冗余度的一种度量卷积码由 3 个整数 n,k,n 描述,k/n 也表示编码效率 ( 每编码比特所含的信息 ); 但 n 和分组码时不一样, 不再表示分组或码字长度,N 称为约束长度, 表示在编码移位寄存器中 k 元组的级数卷积码不同于分组码的一个重要特征就是编码器的记忆性, 即卷积编码过程产生的 n 元组, 不仅是当前输入 k 元组的函数, 而且还是前面 N- 个输入 k 元组的函数实际情况下,n 和 k 经常取较小的值, 而通过 N 的变化来控制编码的能力和复杂性 3

4 其中 m i 代表二进制数字, 每个 m i 独立等概, 即 m i 的知识不能带来关于 m j 的信息每个输入序列 m 转换成唯一的码字序列 U=G(m). 信源 m = m, m,..., 2 m... 信宿 i 卷积编码卷积译码 U = G( m) = U, U 调制,..., U 2 i i, U 2i,..., U ni 解调... 其中 U = U... i (t) s i 信道 ˆ ( t) s i m ˆ = mˆ, mˆ 2,..., mˆ i... Z = Z, Z2,..., Z... i i, Z2i,..., Zni 其中 Z = Z... i 序列 U 由一系列分支字组成, 每个分支字 U i 都由二进制码元组成, 码元之间并不独立 ; U 对波形 s(t) 进行调制, 接收波形为 ŝ(t), 根据相应的解调序列 Z 进行译码, 就可得到原信息的估计 ˆm 4

5 N k/n 输入序列 m = m, m2,..., m... i 每次移入 k 位 2... k kn 级移位寄存器 2 N 2... k k... n 个模 2 加法器输出码字序列 U = U, U 2,..., U... i 2... n 其中 U i = U i,..., U ji,..., U ni... 是第 i 个码字分支, U ji 是分支字 U i 的第 j 个二进制码元由该图可知,n 个输出序列不但与当前的 k 个输入比特有关, 而且与以前的 (N-)k 个输入信息比特有关 5

卷积码是 Elias 在 955 年提出的, 之后不久, Wozencraft 及 Reiffen 提出了序贯译码算法 963 年,Massey 提出了一个效率不高但易于实现的门限译码算法 ;967 年,Viterbi 提出了最大似然译码 (ML, Maximum Likelihood) 算法 ;974 年, Bahl Cocke Jelinek 及

6 卷积码是 Elias 在 955 年提出的, 之后不久, Wozencraft 及 Reiffen 提出了序贯译码算法 963 年,Massey 提出了一个效率不高但易于实现的门限译码算法 ;967 年,Viterbi 提出了最大似然译码 (ML, Maximum Likelihood) 算法 ;974 年, Bahl Cocke Jelinek 及 Raviv(BCJR) 提出了最大后验概率 ( MAP, maximum a posteriori probability) 译码算法 Viterbi 译码算法实质是 ML 算法, 码字误差概率最小 ;BCJR 算法实质是 MAP 算法,bit 错误概率最小 ; 实际应用中 Viterbi 算法易于实现, 用的较多 ; 对于迭代译码应用, 如 Turbo 码,BCJR 算法用的较多 6

7 7.8.2 卷积码的关键特征是其编码函数 G(m), 据此可由输入序列 m 方便地计算出输出序列 U 卷积编码器常用的描述方法有连接图连接矢量连接多项式状态图树状图及网格图连接图表示输入比特 m U: 第一个码元 U2: 第二个码元该图表示约束长度 N=3 的 (2,) 卷积码, 编码效率为 k/n=/2 在每个输入比特时间上, 位信息 bit 移入寄存器最左端的一级, 同时将寄存器中原有 bit 均右移一级, 接着便交替采样两个模 2 加法器, 得到的码元就是与该输入 bit 相对应的分支字 7

8 说明 : 与分组码具有固定码长 n 不同, 卷积码没有, 我们可通过周期性地截断来获得分组长度为了达到清空编码移位寄存器数据 bit 的目的, 需要在输入数据序列末尾附加若干 bit 由于附加的不包含任何信息, 因而, 有效编码效率降至 k/n 以下, 如果截断周期取值较大, 则有效编码效率会逼近 k/n 连接矢量表示指定 n 个连接矢量集, 每个矢量 (N 维 ) 对应一个模 2 加法器, 表示加法器和寄存器之间的连接关系如前面的 (2,,3) 卷积码编码器, 其连接矢量为 :g =, g 2 = 假设对信息矢量 m= 进行编码,3 位信息 bit 在时刻 t t 2 t 3 依次输入, 随后 N-=2 个分别在时刻 t 4 t 5 输入以清空寄存器, 从而保证信息能完全移出 8

9 时刻输出时刻输出 t m U U U2 t4 m U U U2 U2 U2 U U U2 U U U2 t2 t5 U2 U2 U U U2 U U U2 t3 t6 U2 U2 9

10 现借助冲激响应, 即编码器对输入的单个的响应, 来分析编码器这时寄存器的内容为 : 输入序列 : 输出序列 : 寄存器内容分支字 U U2 输入序列 m= 对应的输出序列可按如下方式线性叠加 : 输入 m 输出模 2 和 : 计算结果同前面一致! 由于可以通过将按时间移位的脉冲线性叠加, 或者将输入序列和编码器的脉冲响应相卷积, 来产生输出编码, 因此称为卷积码

11 多项式表示用 n 个生成多项式来描述寄存器和加法器的连接方式, 如前例 (2,,3) 编码器中, g (x)=+x+x 2, g 2 (x)=+x 2 注 : 多项式的最低阶项对应于寄存器的输入级输出序列可根据 U(x)=m(x)g (x) 与 m(x)g 2 (x) 交织求得例 : 信息矢量 m= 表示成多项式形式为 m(x)=+x 2, 则 m(x)g (x)=(+x 2 )(+x+x 2 )=+x+x 3 +x 4 m(x)g 2 (x)=(+x 2 )(+x 2 )=+x 4 m(x)g (x)=+ x+x 2 + x 3 +x 4 m(x)g 2 (x)=+x+x 2 +x 3 +x 4 U(x)=(,)+(,)x+(,)x 2 +(,)x 3 +(,)x 4 U= 与前面结果一致!

12 方法 2: u () (x)=m(x)g (x); u (2) (x)=m(x)g 2 (x); U(x)=[u () (x) u (2) (x)] U(x)=u () (x 2 )+xu (2) (x 2 ) 方法 3: g(x)=g (x 2 )+xg 2 (x 2 ) U(x)=m(x 2 )g(x) 2

13 卷积编码器属于有限状态机的器件有限表明状态机制只有有限个不同的状态有限状态机的状态可以用设备的当前输入和最少的信息量, 来预测设备的输出状态提供了有关过去序列过程及一组将来可能输出序列的限制, 下一状态总是受到前一状态的限制将编码器在时刻 t i 的状态定义为 X i =m i-,m i-2,,m i-n+ 方框内的状态表示寄存器最右端 N- 级的内容, 状态间的路径表示由此状态转移时的输出分支字对应于两种可能的输入 bit, 从每个状态出发只有两种转移状态图 a= b= c= d= 编码器状态输出分支字输入比特输入比特 3

14 例 2 假定 (2,,3) 编码器的输入信息序列 m=, 并附加 N-=2 个以清空寄存器, 假设寄存器初始状态为全, 求对应的状态变化及输出码字序列 U 解 : 输入寄存器 t i 时刻 t i+ 时刻 t i 时刻分支字比特 m i 内容状态状态 U U 状态 t i+ 状态 t i 输出序列 :U = 4

15 例 3 假定 (2,,3) 编码器的输入信息序列 m=, 并附加 N-=2 个以清空寄存器, 假设寄存器初始状态不为, 而是 x, 求对应的状态变化及输出码字序列 U 解 : 输入寄存器 t i 时刻 t i+ 时刻 t i 时刻分支字比特 m i 内容状态状态 U U 2 - x x - - 状态 t i+ 状态 t i 输出序列 :U = 5

16 a b c d a b c a b c d c d d b a t t2 t3 放大 a b c d a b a a b c d c d b a b c d a b c a b c d c d d a b a 树状图 6

17 网格图 a t t2 t3 t4 t5 t6 t7 t8 b c d 输入比特输入比特 7

18 7.8.3 最大似然译码 : 如果所有的输入信息序列等概, 则通过比较各个条件概率, 也称为似然函数 P(Z U (m) ), 选择其中的最大者, 就可以得到具有最小差错概率的译码器, 这里 Z 是接收序列,U (m) 是可能的发送序列如果满足下式, 译码器就选择 U (m ) : P(Z U (m ) ) = max P(Z U (m) ) 对所有 U (m) 假定噪声是零均值的加性高斯白噪声, 而且信道无记忆性, 即噪声独立地影响各个码元编码效率为 /n 的卷积码的似然函数为 ( ( m ) ) ( ( m ) ) ( ( m = ) ) i i = ji ji P Z U P Z U P z u 其中 Z i 是接收序列 Z 的第 i 个分支,U i (m) 是特定码字序列 U (m) 的第 i 个分支,z ji 是 Z i 的第 j 个码元,u ji (m) 是 U i (m) 的第 j 个码元, 每个分支由 n 个码元组成译码问题就是在网格图中选择一条路径 ( 每条可能的路径对应着一个码字 ), 使得上式右端最大 i= i= j= n 8

19 通常对最大似然函数取对数, 从而用加法代替乘法, 以简化计算对数最大似然函数定义为 : ( ( m) ) ( ( m) ) ( ( m) = ) i i = ji ji log P Z U log P Z U log P z u i= i= j= 其实质是从树状图或网格图中选择一条路径, 使上式最大对接收序列进行译码时, 若用树状图, 需要彻底比较与所有可能发送的码字序列相对应的 2 L 个累积对数似然函数值 ; 若用网格图, 能够抛弃最大似然序列不可能经过的路径, 译码路径从幸存路径中选取 n 9

20 维特比译码算法由维特比在 967 年提出维特比算法的实质是最大似然译码, 但它利用了编码网格图的特殊结构, 从而降低了计算的复杂性该算法计算网格图上在时刻 t i 到达各个状态的路径和接收序列之间的相似度 ( 或者说距离 ), 去除不可能成为最大似然选择对象的网格图上的路径, 即, 如果有两条路径到达同一状态, 则具有最佳量度的路径被选中, 称为幸存路径较早地抛弃不可能的路径, 降低了译码器的复杂性注意, 选择最优路径可以表述为选择具有最大似然量度的码字, 或者选择具有最小距离的码字 2

21 输入数据序列发送序列接收序列 m: U: Z: a b 2 t t2 t3 t4 t5 t6 c d 2 2 2

22 将某条给定的路径在时刻 t i 的累积汉明路径量度, 定义为该路径直至 t i 沿途各分支的汉明距离之和维特比译码的思想 : 如果网格图上有两条路径在某个状态合并, 在寻找最优路径时, 舍弃路径度量较大的那条路径如下图中, 在时刻 t 5 有两条路径在状态合并 a t t2 t3 t4 t5 路径量度 =4 b 2 路径量度 = c d 22

23 网格图中每个时刻 t i 上有 2 N- 个状态. 这里的 N 是约束长度, 每种状态都可经两条路径到达维特比译码计算到达每个状态的两条路径的路径量度, 并舍弃其中一条路径在一个给定的时刻, 各状态的幸存路径量度就是该状态在该时刻的状态量度 a b t 2 t2 t 2 时刻的幸存路径状态量度 Γ a = 2 Γ b = a b c d 2 t t2 t3 2 状态量度 Γ a = 3 Γ = 3 b Γ c Γ d = 2 = t 3 时刻的幸存路径 23

24 a b t t2 t3 t a b t t2 t3 t4 2 状态量度 Γ a = 3 Γ = 3 b c c Γ c = d d 2 Γ d = 2 t 4 时刻的量度比较 t 4 时刻的幸存路径 24

25 a b t t2 t3 t4 t5 c t 5 时刻的量度比较 d a t t2 t3 t4 t5 状态量度 Γ a = b 2 Γ b = t 5 时刻的幸存路径 c Γ c = 3 d 2 Γ d = 2 25

26 a b c t t2 t3 t4 t5 t t 6 时刻的量度比较 d a b c 2 t t2 t3 t4 t5 t6 2 4 状态量度 Γ a Γ b Γ c = 2 = 2 = 2 只有当路径量度计算进行到网格图较深处时才产生第一位译码比特!! t 6 时刻的幸存路径 d 2 Γ d = 26

27 由网格图可知, 任意一个时间间隔内的状态转移可分组为 2 v- 个离散区间, 每个区间描述四种可能的状态转移, 其中 v=n- (2,,3) 卷积码的区间划分 δ xy 表示每个转移支路的路径量度, 下标表示从状态 x 到状态 y 的转移 a c 区间 ti δ aa t i+ δ ab δ ca δ cb a' b' b 区间 2 ti t i+ δ bd δ bc c' d δ dc δ dd d' 27

28 - - Γa Γc δ aa δ ca δ ab δ cb 比较比较 mˆ a mˆ c mˆ a mˆ c 2 选 2 选 2 选 2 选 Γ a m ˆ a Γ b m ˆ b 到另一逻辑单元到另一逻辑单元 mˆˆ, m 是状态 a 的旧路径记录和新路径记录 a a' 28

29 7.8.4 在分组码中, 我们关心的是该编码中这些码字序列对之间的最小距离, 因为最小距离与编码的纠错能力相关 ; 对卷积码, 寻找最小距离可简化为寻找所有码字序列和全序列之间的最小距离假定输入序列是全序列, 那么, 我们感兴趣的是起始状态和结束状态都是, 且中间不出现状态的路径标注了与全路径之间距离的网格图所有分叉后又合并的任意长度路径中的最小距离称为自由距离 d f 纠错能力 d f t = 2 a b c d t t2 t3 t4 t5 t

30 从网格图可直观计算 d f, 但用状态图可获得封闭形式描述图中 D 的指数表示该分支的分支字与全路径之间的汉明距离 abce 的状态转移函数为 D 2 DD 2 =D 5 D = abdce 的状态转移函数为 D 2 DDD 2 =D 6 a= b= c= D 2 D 2 D e= abcbce 的状态转移函 D 数为 D 2 DDD 2 =D 6 D d f=5 d= D 由上图可知 X b =D 2 X a +X c ;X c =DX b +DX d X d =DX b +DX d ;X e =D 2 X c 转移函数 T(D)=X e /X a, 求解上述状态方程, 有 5 D j j+ 5 T( D) = = D + 2D + 4 D D D 3

31 为状态图的每个分支引入一个因子 L, 则 L 的指数就表示任意给定的路径上从状态 a= 到状态 e= 的分支数 ; 同时, 在所有输入 bit 产生的分支转移里引入因子 N LN a= b= c= D 2 LN DL D 2 L e= DLN d= DL DLN 3

32 由上图, 我们可得 X b =D 2 LNXa+LNX c ; X c =DLX b +DLX d X d =DLNX b +DLNX d ; X e =D 2 LX c 转移函数 T(D)=X e /X a, 求解上述状态方程, 有 TDLN (,, ) 5 3 D LN = DL( + L) N = D LN+ D L( + L) N + D L( + L) N D L N + j+ 5 j+ 3 j 说明 : 有条距离为 5 的路径, 其长度为 3, 与全路径的输入序列只有 bit 的差别 ; 有 2 条距离为 6 的路径, 其长度分别为 4 和 5, 与全路径的输入序列都有 2bit 的差别 32

33 系统卷积码指输入的 k 元组是与其相关联的输出 n 元组分支字的一部分对线性分组码, 将非系统码转换为系统码不会改变分组的距离属性, 但对卷积码就不同, 因为卷积码很大程度上依赖于自由距离一般, 对于给定的约束长度和编码效率的卷积码, 将其系统化会减小自由距离输入输出约束长度编码效率 /2 系统码自由距离非系统码自由距离

34 所谓灾难性错误传播, 指有限数量的码元差错引起的无限数量的已译码数据比特差错对于编码效率为 /n 的编码方式, 发生灾难性错误传播的条件是这些生成多项式有共同的多项式因子 ( 阶数不低于 ) 例 5: g (x)=+x g 2 (x)=+x 2 输入由于 +x 2 =(+x)(+x) 所以该编码器会引起灾难性错误传播! 输出 34

35 假定全路径是正确的路径, 那么, 无论在节点 d 的自环有多少次, 不正确的路径 abdd dce 上只有 6 个! a= b= c= e= d= 对于任意编码效率的编码器状态图, 当且仅当任意闭环路径的重量为 ( 与全距离为 ) 时, 才会出现灾难性错误传播 35

36 7.8.5 编码约束自由编码效率长度距离矢量 /2 3 5, /2 4 6, /2 5 7, /2 6 8, /2 7, /2 8, /2 9 2, 36

37 编码约束自由编码效率长度距离矢量 /3 3 8,, /3 4,, /3 5 2,, /3 6 3,, /3 7 5,, /3 8 6,, 37

38 7.8.6 GSM 在 GSM 系统中, 无线信道按其功能可分为业务信道 (TCH) 和控制信道 (CCH); 其中业务信道用于传送语音和数据, 控制信道用于传送信令和同步业务信道 (TCH) 语音信道数据信道全速率语音信道半速率语音信道全速率数据业务信道 (9.6kbps) 全速率数据业务信道 (4.8kbps) 半速率数据业务信道 (4.8kbps) 全速率数据业务信道 (<2.4kbps) 半速率数据业务信道 (<2.4kbps) 38

39 控制信道 (CCH) 广播信道公共控制信道专用控制信道频率纠错信道 (FFCH): 用于移动台频率纠错同步信道 (SCH): 用于移动台帧同步与集站识别广播控制信道 (BCCH): 用于发送一般信息寻呼信道 (PCH): 基站寻呼移动台随机接入信道 (RACH): 移动台随机接入网络, 上行信道准予接入信道 (SDCCH): 传送连接移动台, 下行信道独立专用控制信道 (SDCCH): 传送连接移动台与基站和分配信道的命令慢速相关控制信道 (SACCH): 与一条业务信道或一条 SDCCH 联合使用, 传送某些特定信息 ; 快速相关控制信道 (FACCH): 与一条业务信道联合使用携带 SDCCH 同样信令, 但仅在未分配 SDCCH 时才分配 FACCH; 39

40 GSM 中的信道编码方案包括三个步骤 : 用分组码 ( 系统循环码 ) 进行外编码, 建立由信息比特 + 奇偶校验比特构成的码字, 然后在其后加若干比特作为尾比特 ;( 不同的信道, 采用的系统循环码不同 ) 用卷积码进行内编码, 得到编码比特 ; 采用交织技术将衰落引起的长突发错误改变成随机独立错误 ; 外编码器内编码器交织器信道外译码器内译码器反交织 4

41 首先将输入待编码数据分成 2ms 的 26bit 一帧, 其中 5bit 是最重要的比特 (I a 类 ), 采用截短循环码 (53,5) 进行保护, 其生成多项式为 : g(x)=+x+x 3 得到 3 个奇偶校验比特 p(),p(),p(2) 码多项式为 : d()x 52 +d()x 5 + +d(49)x 3 +p()x 2 +p()x+p(2) 编码电路为 : 门 2 门 2 数据输入编码输出 4

42 26 比特中有 32bit 为重要 bit(i b 类 ), 将它后面加上 4 个作为尾比特, 则前两部分总计 : =89bit 对这 89bit 进行块卷积编码, 编码速率为 /2 的 (2,,5) 编码器, 生成多项式为 : g (x)=+x 3 +x 4 输入 g 2( x)=+x+x 3 +x g(x) g2(x) 卷积编码后共 378 个比特, 最后再加上不重要的 78 个比特, 不加保护 ; 因此, 最后的 2ms 语音数据 ( =26bit) 经信道编码, 共计 456 个比特语音编码本身的速率为 3kbps, 编码后其速率为 22.8kbps 42

43 (Interleaving) 交织就是把码字顺序重新排列, 以改善实发持续误码状况它只是改变比特的位置, 不加冗余比特, 所以交织前后码速率不变 2ms 语音数据经信道编码后为 456bit, 它们的传输不是从序号到 456, 而是将 456bit 分为 8 帧, 每帧 57bit, 即序号为第一帧 ;2 45 为第二帧, 依次类推比特帧 43

44 7.8.7 WCDMA (convolution code) 码块数据流串行依次进入编码器, 每输入 bit, 在输出端同时得到 2( 编码速率为 /2 时 ) 或 3bit( 编码速率为 /3 时 ) 需要编码的码块数据流结束时, 继续输入 8 个值为的尾 bit, 在输出端得到的全部信息, 就是本码块编码后的数据 (2,,9) 卷积编码器 g (x)=+x 2 +x 3 +x 4 +x 8 g 2 (x)=+x+x 2 +x 3 +x 5 +x 7 +x 8 输入 D D D D D D D D 输出 G=56(octal) G=753(octal) 输出 2 44

45 (3,,9) 卷积编码器 g (x)=+x 2 +x 3 +x 5 +x 6 +x 7 x 8 g 2 (x)=+x+x 3 +x 4 +x 7 +x 8 g 3 (x)=+x+x 2 +x 5 +x 8 输入 D D D D D D D D 输出 G=557(octal) G=663(octal) G=7(octal) 45

46 7.9 Turbo 7.9. 前言 Turbo 码的编码结构交织器的设计原则 Turbo 码的译码 WCDMA 系统中采用的 Turbo 码 46

47 年, 在国际通信会议 (ICC) 上法国学者 C.Berrou 等人在他们的论文逼近 Shannon 限的纠错编码和译码 Turbo 码中首次提出了 Turbo 码该文论述, 在加性白高斯噪声的环境下, 采用编码效率 R=/2 交织长度为的 Turbo 码, 经过 8 次迭代译码后, 在 E b /N =.7dB 时, 其误码率到达 -5, 与香农极限只相差.5dB, 从而产生了在该领域的巨大兴趣但 Berrou 仅给出了 Turbo 码的基本组成和迭代译码的原理, 而没有严格的理论解释和证明 ; 随后 J. Hagenauer 阐明了迭代译码的原理, 并推导了二进制分组码与卷积码的软输入软输出译码算法由于在 Turbo 码中交织器的出现, 性能分析非常困难, 因此 S. Benedetto 提出了均匀交织 (UI,Uniform Interleaver) 的概念, 并利用联合界技术给出了 Turbo 码的平均性能上界 ;J. Seghers 系统地分析了 Turbo 码的距离特性 ;Mackay 证明了 Turbo 码的校验矩阵与 LDPC 码的校验矩阵是等价的, 从而可以将 Turbo 码看出一类特殊的 LDPC 码 47

48 7.9.2 Turbo Turbo 码的最大特点在于它通过在编译码器中交织器和解交织器的使用, 有效地实现随机性编译码的思想, 通过短码的有效结合实现长码, 达到了接近 Shannon 理论极限的性能通常, Turbo 码编码器可分为并行级联卷积码 (PCCC, Parallel Concatenated Convolutional Codes) 结构串行级联卷积码 (SCCC, Serial Concatenated Convolutional Codes) 结构和混合级联卷积码 (HCCC, Hybrid Concatenated Convolutional Codes) 结构 48

49 PCCC Berrou 最初提出的 Turbo 码采用的是并行级联卷积码结构下图给出了由两个分量编码器组成的 Turbo 码的编码框图 { d k } { x k } 交织器 { d k } 分量编码器分量编码器 2 { y } k { y } 2 k 穿刺和复接分量码一般选择为递归系统卷积 (RSC) 码, 也可以为分组码非递归卷积 (NRC) 码以及非系统码 (NSC) 码, 但分量码的最佳选择是递归系统卷积码一般来说, 两个分量码采用相同的生成矩阵, 当然也可以不同 49

50 在编码过程中, 两个分量码的输入信息序列是相同的, 长度为 N 的信息序列 {d k } 一个支路直接作为系统输出 {x k } 送至复接器, 另一个支路送入第一个分量编码器, 得到校验序列 {y k }, 第三个支路经过交织器 I 后信息序列为 {d k }, 送入第二个分量编码器, 得到校验序列 {y 2k }, 其中 k =I(k) I(.) 为交织映射函数,N 为交织长度, 即信息序列长度为提高码率和系统频谱利用率, 可以将两个校验序列经过穿刺矩阵后, 再与系统输出 {x k } 一起经过复接构成码字序列 {c k } 设输入序列在 k 时刻的比特为 d k, 经约束长度为 N 的卷积码编码后, 输出的校验位 Y k 可表示为 : Y N = gd k i k i i= N 2k 2i k i i= 其中,G : {g i }, G 2 : {g 2i } 分别是两个编码器的生成多项式若某一时刻输入比特 d k, 则 Turbo 码编码器的输出码字为 {d k,y k,y 2k }, 即编码速率 R 为 /3 为了获得更高的码率如 R=/2, 可用穿刺矩阵按一定的规则将校验位二选一 Y = g d 5

51 Turbo 注 : g=[,] 若输入序列 d k = [ ] 则第一个 RSC 编码器的输出 Y K = [ ] 经交织器后的序列为 d k = [ ] 则第二个 RSC 编码器的输出 Y 2k = [ ] 编码器的输出是上述三个码序列的复合, 为 X=[ ] 序列码率 R=/3. 5

52 若 R=/2, 则需将校验位做穿刺处理, Y k : [ ] Y 2k : [ ] 穿刺矩阵为 d k = [ ] 穿刺后的结果为 [ ] 则编码器的输出序列 X 为 [ ] 52

53 Turbo 对于由两个分量码组成的 Turbo 码, 其码率 R 与两个分量码的码率 R 和 R 2 之间满足 : RR R 2 = R + R RR 2 2 显然, 降低 R 和 R2 的值可以使 R 减小 ; 反之,R 增大如果分量码的个数为 n, 不采用穿刺矩阵时, 得到的码率为 R = n + 可以综合上述两种方法得到任意码率的 Turbo 码 53

54 SCCC 在 AWGN 信道上对 PCCC 的性能仿真证明, 当 BER 随 SNR 的增加下降到一定程度以后, 就会出现下降缓慢甚至不再降低的情况, 即出现了误码平台 (error floor) 为此,S. Benedetto 在 996 年提出了串行级联卷积码 (SCCC) 的概念, 如下图所示 { d k } Outer c k I( k) Outer { } { c } Inter { } 外码编码器交织器内码编码器 c k 研究表明, 为使 SCCC 达到较好的译码性能, 至少其内码要采用递归系统卷积码, 外码也应选择具有较好距离特性的卷积码若内外编码器的编码速率为 R I 和 R O, 则 SCCC 的编码速率为 R=R I R O 54

55 HCCC 将上述两种方案结合起来, 从而既能在低 SNR 条件下获得优异的译码性能, 又能有效地消除 PCCC 所谓的误码平台, 这种综合 PCCC 和 SCCC 的编码方案就称为混合级联卷积码 (HCCC) 综合串行和并行级联的方案很多, 这里给出两种 : 一是采用卷积码和 SCCC 并行级联的编码方案 ; 另一个是采用卷积码为外码, 以 PCCC 为内码的混合级联编码结构交织器 I 内码编码器 HCCC 编码结构外码编码器交织器 I2 内码编码器 HCCC 编码结构 2 外码编码器交织器 I 内码编码器交织器 I2 内码编码器 2 55

56 7.9.3 Turbo 码系统中交织器的作用是用于减少校验比特之间的相关性, 进而在迭代译码过程中降低误比特率设计性能较好的交织器的特点和基本原则 : 通过增加交织器的长度, 可以使译码性能得到提高, 好的交织器可使总的码字的自由距离随交织器长度的增加而增加, 即提供一定的交织器距离交织器应该使输入序列尽可能地随机化, 从而避免编码生成低重码字的信息序列在交织后编码仍旧生成低重码字, 导致 Turbo 码的自由距离减小交织深度与码重参数是交织器设计时两个重要的参数指标, 但它们之间还没有找到定量的关系式目前, 对交织器的设计一般都是采用计算机仿真的方法来搜索出较满意的交织器 56

57 交织实际上就是将数据序列中的元素的位置进行重置, 从而得到交织序列的过程 ; 其逆过程就是将交织后的序列元素恢复为原有顺序, 也称为解交织例如, 交织器 I 的输入为 d=(d,d 2,,d N ) 交织映射输出序列为 d =(d,d 2,,d N ) 序列 d 和 d 仅仅是元素的位置顺序不同如果把输入序列和交织输出序列看成一对含有 N 个元素的集合, 则交织过程可以看成从集合 d 到集合 d 的一个一一映射过程, 即 I: d i -- d j i,j=,2, N 57

58 从信息论的角度看, 在 turbo 码编码器中引入交织器的目的是实现随机性编码, 但是在交织长度有限的实际情况下, 实现完全随机编码是不可能的交织长度越短, 随机性越差, 这时采用按照一定的确定规则设计的交织器可以得到比伪随机交织器更好的性能而交织长度较大时, 伪随机交织器或者满足一定距离属性要求的随机交织器可以获得比较好的性能因此, 根据不同的设计思想, 交织器大致可以分成两类 : 规则交织器和随机交织器规则交织器通常按照一定的规则映射来实现交织, 通常比较容易实现 ; 基于随机性准则设计的交织器通常称为伪随机交织器对于长度有限的输入信息序列而言, 交织长度有限, 实现完全随机是不可能的当然也可以将规则交织和伪随机交织相结合作为交织器设计的方法 58

59 交织前后比特之间的距离如果交织器能够通过交织在原始序列中距离较近的信息比特经过交织后有一定的距离, 则可以在一定程度上提高 Turbo 码的性能在穿刺 Turbo 码中, 如果设计的交织器能够实现对系统比特的均匀保护, 则有助于提高 Turbo 码的性能例如, 在采用伪随机交织器时, 原始序列中某个位于奇数位置的比特经过交织后可能在交织序列的偶数位置出现, 这样经过编码后它对应的两个校验比特也分别位于两个校验序列的奇数位置和偶数位置根据前述穿刺方法, 这两个校验比特要么都被删除, 要么都被保留在译码时, 那些两个校验比特均被删除的信息比特出现错译的概率大大增加, 降低了 Turbo 码的性能因此所设计的交织器如果能够保证交织后信息比特位置的奇偶性不变, 则有助于提高性能如果在 Turbo 码的编码器中引入交织器, 那么在译码中就必须有与其相对应的解交织器, 即需要两个设备来分别实现交织和解交织过程如果所设计的交织器满足对称特性, 则交织器和解交织器就是完全相同的, 从而可以用同一个设备实现 59

60 块交织器是最简单的一类交织器, 其交织映射过程为 : 将数据序列按行写入 m n 矩阵, 然后按列的顺序读出, 即完成交织 ; 相应的解交织过程就是将交织后的数据按列的顺序写入, 按行的顺序读出写入读出 2 n n+ n+ 2 2n ( m ) n+ ( m ) n+ 2 mn 其交织映射函数可表示为 : N 为交织长度 [ ] Ii ( ) = ( i ) mod n+ ( i ) / n +, i=, 2,..., N 6

61 循环移位交织器的映射为 : I(i)=a*i mod N 其中 a 是步长, 为与交织长度 N 互素的正整数, 且 a 2N 步长 a 的值决定了原始序列中相邻的比特经过交织后在交织序列中的距离例如右图中交织长度 N=92 a=7 的循环移位交织器的输入输出位置输出位置循环移位交织器的输入输出位置图示例输入位置 6

62 分组螺旋交织器首先将数据序列按行的顺序写入 m n 矩阵, 其中 m 与 n 互素在交织时, 从矩阵的左上角开始向右下方向读取数据, 如下图所示在行的方向和列的方向分别对索引取模 m 和 n, 即若令 ri 和 ci 分别表示第 i 个比特的行索引和列索引, 则分组螺旋交织器的数据读取顺序为 : r i+ =r i + mod m c i+ =c i + mod n

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

64 7.9.4 Turbo Turbo 码获得优异性能的根本原因之一是采用了迭代译码, 通过分量译码器之间软信息的交换来提高译码性能对于并行级联码, 如果分量译码器的输出为硬判决, 则不可能实现分量译码器之间软信息的交换 ; 同样, 对于串行级联码, 如果内码译码器的输出为硬判决结果, 则外码译码器也无法采用软判决译码技术, 从而限制了系统性能的进一步提高从信息论的角度来看, 任何硬判决都会损失部分信息, 因此, 如果分量译码器 ( 内码译码器 ) 能够提供一个反映其输出可靠性的软输出, 则其他分量译码器 ( 外码译码器 ) 也可以来用软判决译码, 从而系统的性能可以得到进一步提高为此, 人们又提出了软输出译码的概念和方法, 即译码器的输入输出均为软信息 64

65 PCCC 解交织器 Λ ( ) 2 e uk s y k Λ ( ) a uk Lc Λ ( ; ) k u O Λ ( ; ) Σ ( ) e uk Λ c s I k 分量译码器交织器 ( s Λ ; ) I ( k ) c I Λ ( ) 2 a uk 分量译码器 2 Λ ( ; ) 2 I( k) u O + 解交织器 Σ - - p y k Λ ( c p k ; I ) 2 Λ ( c p k ; I ) 交织器 Λ ( ; ) 2 k u O 硬判决 uˆk 65

66 假设编码输出信号为接收信号为其中 s p Y = ( y, y ) k k k s s k = k + k y x i y = x + q p p k k k i k 和 q k 是服从均值为, 方差为 N /2 的独立同分布高斯随机变量经过 s/p, 可得到 3 个序列 : 系统接收信息序列译码器的接收校验序列译码器 2 的接收校验序列 s p X = ( x, x ) k k k Y s = y s s s y2 y N (,,..., ) p p p p Y = ( y, y2,..., y N ) Y p = ( y p, y p 2,..., y p N ) 66

67 值得注意的是, 若其中某些校验比特在编码过程中通过穿刺矩阵被删除了, 则在接收校验序列的相应位置以来补充上述三个接收序列 Y s Y p 和 Y 2p 经过信道置信度 L c 加权后作为系统信息序列 Λ(c s ;I) 校验信息 Λ(c p ;I) 和 Λ(c 2p ;I) 送入译码器 L = 4 E / N 对于 AWGN 信道,L C 定义为 : c s 67

68 对于第 k 个被译比特,PCCC 译码器中每个分量译码器都包括系统信息 Λ k (c s ;I) 校验信息 Λ k (c ip ;I) 和先验信息 Λ ia (u k ) 其中先验信息 Λ ia (u k ) 由另一个分量译码器生成的外部信息 Λ 3-i,e (u k ) 经过解交织 / 交织后的对数似然比值译码输出为对数似然比 Λ ik (u;o), 其中 i=,2 在迭代过程中, 分量译码器的输出 Λ ik (u;o) 可表示为系统信息 Λ k (c s ;I) 先验信息 Λ a (u k ) 和外部信息 Λ e (u k ) 之和的形式 Λ ik (u;o)= Λ k (c s ;I) + Λ a (u k )+ Λ e (u k ) 其中 Λ a (u I(k) )= Λ 2e (u k ),I(k) 为交织映射函数 68

69 在第一次迭代时, Λ 2e (u k )=, 从而 Λ a (u k )= 对于分量译码器 2, 其外部信息 Λ 2e (u k ) 为输出对数似然比 Λ 2k (u;o) 减去系统信息 Λ I(k) (c s ;I)( 经过交织映射 ) 和先验信息 Λ 2a (u k ) 的结果, 即 Λ 2e (u k )=Λ 2I(k) (u;o)-λ I(k) (c s ;I)-Λ 2a (u k ) 其中 Λ 2a (u k )= Λ e (u I(k) ) 外部信息 Λ 2e (u k ) 解交织后反馈为分量译码器的先验输入, 完成一轮迭代译码随着迭代次数的增加, 两个分量译码器得到的外部信息值对译码性能提高的作用会越来越小, 在一定迭代次数后, 译码性能不再提高这时根据分量译码器 2 的输出 LLR 经过解交织后再进行硬判决即得到译码输出 69

70 7

71 Turbo 码译码算法 Turbo 码的译码算法主要有 : 最大后验概率 (MAP) 算法和软输出维特比译码算法 (SOVA) 两者的共同点都是利用软输出来进行迭代译码 MAP 是最优的译码算法, 但其缺点是具有较大的运算复杂度和需较大的存储空间 ;SOVA 的译码性能虽不如 MAP, 但其运算复杂度较低, 有利于硬件的实现 MAP 算法 : 在最初提出 Turbo 码时所采用的译码算法是修正的 Bahl 算法, 也叫做最大后验概率 (MAP) 算法, 它是 Turbo 码译码的最优算法 MAP 算法采用对数似然比函数 (LLR), 即后验概率比值的绝对值作为其软判决的输出对于比特 u k, 其后验概率表示为 Pr{u k =i/y}, i=,, 软判决输出可表示为 : Pu { k = / Y} Λ ( uk ) = log Pu { = / Y } 其中,u k 为信息序列,Y 为观察序列若 Λ(u k )> 判决 u k =; 反之判决 u k = k 7

72 SOVA 算法 : 对于卷积码,Viterbi 算法是最优的最大似然译码方法, 译码输出为卷积码的最优估计序列但对于属于级联卷积码的 Turbo 码而言, 传统的 Viterbi 算法存在两个缺陷 : 首先, 一个分量译码器输出中存在的突发错误会影响另一个分量译码器的译码性能, 从而使级联码的性能下降其次, 无论是软判决 Viterbi 算法还是硬判决 Viterbi 算法, 其译码输出均为硬判决信息, 若一个分量码采用 Viterbi 算法译码, 则另一个分量译码器只能以硬判决结果作为输入, 无法实现软判决译码, 从而性能会有所下降因此, 如果 Viterbi 译码器能够提供软信息输出, 则可以弥补上述两个缺陷, 并且可以通过在分量译码器之间软信息的交换使级联码的性能大大提高为此, 需要在传统的 Viterbi 算法上进行修正, 使之提供软信息输出, 相应的算法就称为软输出 Viterbi 算法 (SOVA, Soft Output Viterbi Algorithm) 72

73 7.9.5 WCDMA Turbo 编码框图第一个成员编码器 x k x k D D D z k MIL 交织器 z k x k D D D 第二个成员编码器 73

74 RSC 生成多项式 g (D)=+D 2 +D 3 (3) 8 g (D)=+D+D 3 (5) 8 转移函数为 : GD ( ), 编码后的输出比特为 : g ( D) = g( D) x, z, z, x, z, z,..., x, z, z K K K 采用的是多级交织算法 (MIL, Multi-stage InterLeaving method) 的块交织器协议规定, 交织器的交织长度 K 在 4~ 54 之间具体的交织过程分三个步骤 : 比特流输入至内部矩阵 ; 对内部矩阵进行行内重排和行间重排 ; 对重排后的矩阵修剪输出 ; 74

75 确定交织矩阵的行数 R( 从上到下依次为,,2,, R-); 5 if 4 K 59 R = if 6 K 2 or 48 K 53 2 others 确定交织矩阵的列数 C( 从左到右依次为,,2,, C-); p = 53 if 48 K 53 p if K R ( p ) C = p if R ( p ) < K R p p + if R p < K R ( p + ) 其中 p 是满足 K R ( p+) 的最小素数 75

76 比特流从行列开始逐行写入到 R C 矩阵 : x x2 x3 x x x x x x x x x C+ C+ 2 C+ 3 2C C( R ) + C( R ) + 2 C( R ) + 3 RC 如果 K<R C, 则 x K+,, x R C 可以任意填充或者, 因为它们在交织完成后还会被删除, 最终不会输出 C 76

77 2 行内重排 () 根据 p 值从下表中选取对应的原根 v: p v p v p v p v p v

78 (2) 建立一个行内重排基准序列 s(i): s(i)=[v s(i-)]mod p, i=,2, (p-2), s()= (3) 建立各行行内重排的步长 {q j }, j=,2,,r-, q = 必须满足 g.c.d{q j, p-}=, q j >6 且 q j >q j- 注 :g.c.d (greatest common divisor) 是取最大公约数 ; (4) 计算 {r j } r T(j) =q j, j=,,, R- 根据输入比特数目 K 的不同确定四种重排模式 T(j):Pat, Pat 2, Pat 3, Pat 4 j 为重排后的行号,T(j) 为重排后第 j 行在重排前的行号 Pat4 4 K 59 Pat3 6 K 2 Pat 2 K 48 Pat3 48 K 53 T( j) = Pat 53 K 228 Pat2 228 K 248 Pat 248 K 36 Pat2 36 K 32 Pat 32 K 54 78

79 重排模式为 : Pat : {9,9,4,4,,2,5,7,2,8,,8,3,7,3,,6,6,5,} Pat 2 : {9,9,4,4,,2,5,7,2,8,6,3,7,5,3,,6,,8,} Pat 3 : {9,8,7,6,5,4,3,2,,} Pat 4 : {4,3,2,,} (5) 进行行内重排 U j (i) 为第 j 行的第 i 列在重排前的列号若 C=p, 则若 C=p+, 则若 K=C R, 则还得交换 U R- (p) 和 U R- () 若 C=p-, 则行间重排 ( ) ( ) U ( i) = s i r mod( p ), i =,,2,...,( p 2), U ( p ) = j j j U j( i) = s i rj mod( p ), i =,,2,...,( p 2), U j( p ) =, U j( p) = ( j ) U j( i) = s i r mod( p ), i =,,2,...,( p 2) 将完成行内重排的矩阵基于行间重排模式 T(j) 作行间重排, T(j) 是重排后第 j 行在重排前的行号 79

80 3 经过行内行间重排后, 矩阵转换为 : y y y y y y y y y y y y R+ 2R+ ( C ) R+ 2 R+ 2 2R+ 2 ( C ) R+ 2 R 2R 3R CR Turbo 码交织器的输出是从重排后的 R C 矩阵中从行列始一列一列从上向下依次读到 R- 行 C- 列的了输入序列中不存在的 x k (k>k) 重排对应的开输出时删除实际上 Turbo 码内部交织器最后输出的比特数目仍为 K, 删除的比特数目为 R C-K y y k CR y 8

81 K 62 确定行数 :R=5 确定列数 :C=3,p=3 写入 5 3 矩阵 : x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x53 x54 x55 x56 x57 x58 x59 x6 x6 x

82 () 由于 p=3, 查表得 v=2 (2) s()=, 由 s(i)=[v s(i-)]mod p, i=,2, (p-2), 可得到 s()=2, s(2)=4, s(3)=8, s(4)=3, s(5)=6, s(6)=2 s(7)=, s(8)=9, s(9)=5, s()=, s()=7 (3) q =, so q =7, q 2 =, q 3 =3, q 4 =7 (4) r 4 =q =, r 3 =q =7, r 2 =q 2 =, r =q 3 =3, r =q 4 =7 (5) 由于 C=p, ( ) U j( i) = s i rj mod( p ), i =,, 2,...,( p 2), U j( p ) = U j (i) 为第 j 行的第 i 列在重排前的列号对于第行 : 当 i 从到 p-2= 变化时, 得到 U ()=s()=, U ()=s(5)=6, U (2)=s()=, U (3)=s(3)=8 U (4)=s(8)=9, U (5)=s()=2, U (6)=s(6)=2, U (7)=s()=7 U (8)=s(4)=3, U (9)=s(9)=5, U ()=s(2)=4, U ()=s(7)=, U (2)= 82

83 这样对于第行的数据, 行内重排的结果为 : 即对应着 x x x x x x x x x x x x x 同样的道理, 对于第行, 当 i 从到 p-2= 变化时, 得到 U ()=s()=, U ()=s()=2, U (2)=s(2)=4, U (3)=s(3)=8 U (4)=s(4)=3, U (5)=s(5)=6, U (6)=s(6)=2, U (7)=s(7)= U (8)=s(8)=9, U (9)=s(9)=5, U ()=s()=, U ()=s()=7, U (2)= 这样对于第行的数据, 行内重排的结果为 : 即对应着 x x x x x x x x x x x x x

84 对于第 2 行, 当 i 从到 p-2= 变化时, 得到 U ()=s()=, U ()=s()=7, U (2)=s()=, U (3)=s(9)=5 U (4)=s(8)=9, U (5)=s(7)=, U (6)=s(6)=2, U (7)=s(5)=6 U (8)=s(4)=3, U (9)=s(3)=8, U ()=s(2)=4, U ()=s()=2, U (2)= 这样对于第 2 行的数据, 行内重排的结果为 : x x x x x x x x x x x x x 即对应着对于第 3 行, 当 i 从到 p-2= 变化时, 得到 U ()=s()=, U ()=s(7)=, U (2)=s(2)=4, U (3)=s(9)=5 U (4)=s(4)=3, U (5)=s()=7, U (6)=s(6)=2, U (7)=s()=2 U (8)=s(8)=9, U (9)=s(3)=8, U ()=s()=, U ()=s(5)=6, U (2)= 这样对于第 2 行的数据, 行内重排的结果为 : x x x x x x x x x x x x x 即对应着

85 对于第 4 行, 当 i 从到 p-2= 变化时, 得到 U ()=s()=, U ()=s()=2, U (2)=s(2)=4, U (3)=s(3)=8 U (4)=s(4)=3, U (5)=s(5)=6, U (6)=s(6)=2, U (7)=s(7)= U (8)=s(8)=9, U (9)=s(9)=5, U ()=s()=, U ()=s()=7, U (2)= 这样对于第行的数据, 行内重排的结果为 : x x x x x x x x x x 即对应着

86 经过行内重排后, 矩阵变为 : x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 经过行间重排后, 矩阵变为 : x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x

87 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 输出序列为 : x 54, x 4, x 28, x 5, x 2, x 55, x 5, x 34, x 6, x 7, x 57, x 44, x 37, x 8, x, x 6, x 45, x 32, x 22, x 9, x 56, x 43, x 36, x 7, x, x 59, x 47, x 38, x 2, x 3, x 52, x 39, x 26, x 3, x 42, x 33, x 25, x 8, x 62, x 49, x 3, x 23, x 4, x 58, x 48, x 35, x 9, x 6, x 5, x 3, x 24, x 5, x 6, x 46, x 29, x 2, x 2, x 53, x 4, x 27, x 4, x 87

88 (P33~333)

第10章 Turbo码

第10章 Turbo码第六章 Turbo 码虽然软判决译码级联码和编码调制技术都对信道码的设计和发展产生了重大影响, 但是其增益与 Shannon 理论极限始终都存在 ~ 3dB 的差距因此, 在 Turbo 码提出以前, 信道截止速率 R 0 一直被认为是差错控制码性能的实际极限,Shannon 极限仅仅是理论上的极限, 是不可能达到的根据 Shannon 有噪信道编码定理, 在信道传输速率 R 不超过信道容量