编织码的主要内容及其发展

编织码(WovenCode)是在编织卷积码(1997年由三位欧洲学者提出)的基础上发展起来的一种组合码。最早的组合编码是级联码,由Forney提出,其目的是找到一类纠错码及其译码算法,在R
展开查看详情

1.第七章 编织码 2017/5/2 1

2. 本章内容  第七章 编织码  7.1 编织码编码基本原理  7.2 编织码的译码 2

3. 第七章 编织码  编织码(Woven Code)是在编织卷积码(1997年由三位欧洲学者提出)的 基础上发展起来的一种组合码。最早的组合编码是级联码,由Forney提出 ,其目的是找到一类纠错码及其译码算法,在R<C的情况下使得差错概率 随码长呈指数下降,而译码复杂度呈代数关系增加,从而获得高的编码增 益。由于使用了两个或更多相对简单的成员码来构成级联码,因此,其纠 错性能和许多非级联码的长码相当。常见结构形式是内码采用约束长度短 的卷积码和最大似然译码算法,外码采用高码率的多进制RS码和代数译码 结构。  Turbo码的出现提供了一个性能优越的编码方法,其思想精髓被推广到其他 的编码方案中。1998年,Benedntto提出了以卷积码为成员码的串行级联卷 积码(SCCC),该码保持了Turbo码在低信噪比时的最大似然译码性能, 同时消除了Turbo码在高信噪比时的“误码平台”效应。除了以卷积码为分 量码外,还可以用分组码作分量码,Pyndiah提出了分组Turbo码。于是, 在这样的思路引导下,Host提出了编织卷积码(WCC),又推广到更一般 的编织码,其系统结构可完全包容传统分组码、卷积码以及各类Turbo码。 3

4. 7.1 编织码编码基本原理  编织码的基本原理类似于纺织业中的织布原理,其编码结构主要有三种: 外经(Outer Warp)、内经(Inner Warp)和斜纹(Twill)结构。它们是 指外编码器的输出码字比特在缓冲器中以按列读出(外经)或按行读出( 内经)输入到各个内编码器。 1. Host’s Ph.D thesis:On Woven Convolutional Codes. 1999 2. Host, etc. Woven Convolutional Codes I: Encoder Properties. IEEE Trans. On Info. Theory. Vol.48, No.1. 2002. p149—161. 3. Jordan, etc. Woven Convolutional Codes II: Decoding Aspects. IEEE Trans. On Info. Theory. Vol.50, No.10. 2004. p2522—2529. 4

5. 外经结构编码器  外经编码器结构如下图所示,假定外编码器由K个普通二进制编码器并行级 o 联组成,所有成员编码器生成矩阵 Gk (k=1, 2, …, K)可以相同,也可以 不同。内编码器由一个普通二进制编码器构成,其生成矩阵为Gi。假定外编 码器的每个子编码器的码率为Ro=bo/co,即输入信息比特数为bo ,输出序列 长为co。u被分为K个bo长度的数据块,即图中的 u = ( u (1)u (2)  u ( bo ) ) ,每个 u (i ) (=u (i ) (i ) u  u K ) ,i (i ) 1,..., bo , 第k个成员编码器的信息序列就 为 uk = ( uk uk  uk o ) ,这些信息子块再以并行的方式输入到K个并联 1 2 o (1) (2) (b ) 的子编码器中,每个子编码器的输出序列(长度为co )以串行方式按行写入 缓冲器(共K行),缓冲器的输出按列读出,作为内编码器(编码速率为 Ri=bi/ci )的输入信息序列,此结构的总编码速率为R=RoRi。 u1o o v1o i G1 u o o v1o u2 v2 i v i u o o G2 v2o u Gi ... ... ... u o K v o K vKo GKo 5

6. 内经结构编码器  与外经结构相反,内经结构中是由一个二进制编码器作为外编码器,K 个并联二进制编码器构成内编码器。外编码器的输出码序列按列写入缓 冲器(共K行),作为K个并联内编码器的信息序列。外编码器的编码速 率为Ro=bo/co,内编码器的编码速率为Ri=bi/ci ,则内经编码器的总的编 码速率为R=RoRi。 o u1i v1i v G1i u1i u o v o i u2i i v2i vi Go u 2 G 2 ... ... ... uKi uKi vKi GKi 6

7. 斜纹结构编码器  斜纹结构是前两种结构的综合,如下图所示。外编码器由Ko个码率为 Ro=bo/co的二进制编码器并联组成,内编码器由Ki个码率为Ri=bi/ci的二进 制编码器并联组成。信息序列uo被分为KoKibo长的子块,这些子块输入 到Ko个并联的外编码器,输出按行写入缓冲器,按列读出作为内编码器 的信息序列,输入到Ki个并联的内编码器。斜纹编码器的总的编码速率 为R=RoRi。  显然,外经结构和内经结构都是斜纹结构的特殊情况。当Ki=1及Ko>1时 为外经结构,当Ki>1及Ko=1时为内经结构,当Ki=1及Ko=1时为通常的级 联码结构 。 u o vo u1i v1i 1 G1o 1 G1i u2o v2o u2i v2i u o G o v o u i G i vi 2 2 ... ... ... ... uKo o vKo o uKi i vKi i GKo o GKi i 7

8. 在斜纹结构中,Ko和Ki的值应满足:gcd(Ko,Ki)=1,如不满足,则编织码 的经纬不能构成斜纹。 例如Ko=10, Ki=3时,内编码器和外编码器间缓 冲器中信息分布如图(a)所示。 左边10个箭头表示外编码器,右边3个箭头表示内 编码器,缓冲器中来自外编码器的码流按行写入, 读出按列进行。即第一个码比特输入到第一个内 编码器作为它的信息比特,第二个码比特输入到 第二个内编码器,第三个码比特输入到第三个内 (a) 编码器,第四个码比特输入到第一个内编码器, 依次类推。可见,输入到相应内编码器的比特序 列在缓冲器中组成图(a)中的斜纹结构。 例如Ko=10, Ki=4时,内编码器和外编码器间缓 冲器中信息分布如图(b)所示。 形成不了斜纹结构!相当于两个Ko=5, Ki=2的斜 纹编码器的并联。 (b) 8

9. 编织码的分类  编织码的包容性很强,具体体现在分量码型上,按其分量码型的组成可 分为两大类:一是其分量码为单一码型的,即内外码采用同样的码型; 二是其分量码为混合码型,即内外码型不同。无论是哪一类分量码型, 经过编织后所构成的新码型(编织码),其距离都得到了提高(即纠错 能力提高)。不同的码型采用不同的交织器。 (1)编织卷积码(WCC,Woven Convolutional Code) WCC是串行级联卷级码,其内外编码器都是卷级码,总体上可视为一个卷级码,因 此可以用卷级码的性质来分析和优化。(研究最为广泛) (2)编织Turbo码(WTC) WTC的编码器结构如图所示,它由K个并行 u1o v1o ,(1) 外编码器和一个内编码器组成(都是卷级 G1o o ,(2) ui vi v 1 Gi v 码)。信息序列u被分为K个子块,分别作 v o ,(1) u2o 2 为K个码率为Ro=bo/co的外编码器的输入,u G2o o ,(1) v2o ,(2) 外编码器的部分输出序列 vk (k =1, v o ,(2) ... 2, …,K)组成内编码器的输入序列ui ,其他 ... vKo ,(1) uKo vKo ,(2) 输出序列 v o ,(2) (k=1,2,…,K)直接与内编码 GKo k 器的输出vi一起组成最终的编织码v。 9

10.(3)编织分组码(WBC) WBC编码器如下图所示,外码编码器由K个分组码编码器或者卷级码编码器组成, 内码编码器由一个卷级码编码器构成,交织器按行交织。 u1o o v1o v1o G1 交织器 u2o v2o v2o u o Go 交织器 ui i vi 2 G ... ... uKo vKo vKo o G K 交织器 (4)串行级联码(SCC, Serial Cascaded Code) SCC编码器如下图所示,由内外码编码器及交织器级联组成,它可看成编织码的特 例。 u o v o ui vi Go 交织器 Gi 10

11. 7.2 编织码的译码  以编织卷积码为例,讲解译码原理。WCC的译码与其编码特性有关,由 于WCC为组合编码,其译码可以采用Turbo码的译码方式,将各个成员 码分离出来分别进行译码,最后再将各译码器的值按一定的方式组合, 就可得到最终的译码结果;也可采用内外译码器迭代的方式来提高译码 的准确性。  WCC的译码主要有三种:传统的软输入软输出Viterbi译码(SOVA)[1] 、SW-BCJR译码算法[2]和pipeline译码算法[3]。 1. S. Benedetto, etc. A soft-input soft-output APP module for iterative decoding of concatenated codes. IEEE Communications letters. Vol.1, No.1, 1997. p22-24. 2. S. Benedetto, etc. Soft-output Decoding Algorithms in Iterative Decoding of Turbo Codes. TDA Progress Report. 1996. p63-87. 3. R. Jordan, etc. Pipeline Decoding of Woven convolutional codes. Proc. 3rd ITG Conf. Sour ce, Channel Coding. Munich, 2000. 11

12. BCJR 算法  为了应用迭代译码,我们需要对成员码进行软输出译码(如BCJR和 SOVA),我们主要讲解BCJR算法。  假设接收序列为r,信息序列或码字序列的先验概率为 P ut ( )或 P ( v ) ( j) ( j) t ( ,我们可以计算出对应的后验概率 P ut( j ) | r 或 P vt( j ) | r ) ( ) ,如下图 所示。 r P(v|r) P(v) APP 定义信息序列为u[0,T)=(u0,u1,…,uT-1),每个信元ut是一个二进制b-tuple, T是帧长,对应的码字序列为v[0,T)=(v0,v1,…,vT-1),其中vt是一个二进制 c-tuple,即编码效率为b/c;状态序列为S[0,T]=(σ0, σ1,…, σT),状态σt 是一个二进制矩阵,表示编码器在t时刻的物理状态,我们用S来表示所 有可能的状态集合;这样接收序列可表示成r[0,T)=(r0,r1,…,rT-1),其中每 个接收到的信元rt都是一个c-tuple的信道信元。 Host’s Ph.D thesis:On Woven Convolutional Codes. 1999 12

13. 假设信道是无记忆的AWGN信道,给定码字序列的情况下,接收序列 r[0,T)的概率为: T −1 T −1 ∏∏ t t ) ( c P(r= [0,T ) | v [0,T ) ) ∏ = P(rt | v t ) =t 0 P r =t 0=j 1 ( j) | v ( j) 其中 P ( rt ( j ) | vt( j ) ) 是信道转移概率。 已知信息或码序列的先验概率,很容易得到网格图中各分支的先验概 ( St +1 σσ 率 P= =′ | St ) P ( St σσ 或= =| St +1 ′ ) 。考虑一个分支:t时 刻在状态σ,t+1时刻在状态 σ′ 。 初 始 条 件 P(S0=σ)=1/|S| , 其 中 |S| 表 示 状 态 数 , 有 P(St=σ)=1/|S| , t=1,2,…,则有 P ( St= +1 σσσσ ′| = ) P (= St = St | St= +1 ′) 为了简化表示,引入4个变量: α t (σ )  P ( St = σ | r[0,t ) ) βt (σ )  P ( St = σ | r[t ,T ) ) δ t (σ , σ ′)  P (= ′; St σ | r[0,T ) ) St +1 σ= P ( St +1 σ= γ t (σ , σ ′) = ′; rt | St σ ) 13

14.  得到前面的公式后,继而就可得到后验概率,为: ( t u |= P=u (i ) r[0,T ) ) ∑ ; St +1 σ ′ | r[0,T ) ) P( St σ= = (σ ,σ ′ ):σ  →σ ′ u = ∑ δ t (σ , σ ′) (σ ,σ ′ ):σ  →σ ′ u 及 ( t v |= P=v (i ) r[0,T ) ) ∑ = ; St +1 σ ′ | r[0,T ) ) P( St σ= (σ ,σ ′ ):σ  →σ ′ v = ∑ δ t (σ , σ ′) (σ ,σ ′ ):σ  →σ ′ v (σ , σ ′) : σ  u → σ ′表示 σ 和 σ ′ 取自状态对集合,并在网格图中存在 一条分支:在t时刻状态为 σ ,当第i个信息信元为 ut(i ) = u 时,转移到 状态 σ ′(t+1时刻)。 (σ , σ ′) : σ  u →σ ′ 同理。 σ : σ → σ ′ 表示t时刻的状态集合,这些状态必须满足在t+1时刻转移到 状态 σ ′ 这个条件。 σ ′ : σ → σ ′ 表示t+1时刻的状态集合,这些状态 必须满足在时刻t状态为 σ 的条件。 14

15. 计算各度量值 : , σ ′) P= γ t (σ= ( St +1 σ ′;= rt | St σ ) 分 支 = P(= rt | St σ=; St +1 σ ′) P= ′ | St σ ) ( St +1 σ= 度 量 = P ( rt | v(σ , σ ′) ) P= ′ | St σ ) ( St +1 σ= ! 其中 v (σ , σ ′) 是t时刻状态为 σ 、t+1时刻状态为 σ ′ 这条分支对应 的码字。 如果在时刻 t,α t (σ ) 的值已知,就可推导出 t+1 时刻的值,为: (σ ′) P= α t +1= ( St +1 σ ′ | r[0,= t +1) ) ∑ : → ′ σσ σ P= (S t +1 ′; St σ | r[0,t ) ; rt ) σ= 1 = ∑ P(rt | r[0,t ) ) σ :σ →σ ′ P= ′; St σ ; rt | r[0,t ) ) ( St +1 σ= = ktα+1 ∑ t = P ( S σ :σ →σ ′ σ | r[0,t )=) P ( S t +1 σ=′; rt | S t σ ) = k α t +1 ∑ α (σ )γ (σ , σ ′) : → ′ σσ σ t t 前向状态度量! 15

16.如果在时刻 t+1, β t +1 (σ ′) 的值已知,就可推导出 t 时刻的值,为: βt= (σ ) P= ( St σ | r[t ,T ) ) = ∑ = P( S ′: → ′ σ σ σ t ; St +1 σ ′ | rt ; r[t +1,T ) ) σ= 1 = ∑ = P (rt | r[t +1,T ) ) σ ′:σ →σ ′ ; St +1 σ ′; rt | r[t +1,T ) ) P ( St σ= k= t β ∑ P(St +1 σ ′= σ ′:σ →σ ′ | r[t +1,T ) ) P( St +1 σ ′; rt | St = σ ) = ktβ ∑ β ′: → ′ σ σ σ t +1 (σ ′)γ t (σ , σ ′) 反向状态度量! 16

17. 对于由状态 ( St , St +1 ) = (σ , σ ′) 定义的支路, α t (σ ) 表示到t时刻的序列 的后验信息,β t +1 (σ ′) 表示t+1时刻及之后的序列的后验信息,状态之间 的支路信息在 γ t (σ , σ ′) 中。知道了这些信息,就可计算 δ t (σ , σ ′) ,为: σ ′) P= δ t (σ ,= St +1 σ ′ | r[0,T ) ) ( St σ ;= 1 = = P( St σ ; r[0, = t ) ) P ( St +1 ′; r[t ,T ) | St σ ) σ= P(r[0,T ) ) P(r[0,t ) ) = α t (σ ) P( St +1 σ ′; rt | S= t = σ ) P ( r[ t +1,T ) | St +1 σ ′) P(r[0,T ) ) = ktδ α t (σ )γ t (σ , σ ′) βt +1 (σ ′) 得到后验信息! 17

18.BCJR 算法归纳 18