PCCC码(Turbo码)的编码和译码算法

目录一、概述....................................................................1二、PCCC码的编码算法....................................................................................................................3三、PCCC码的译码算法..................................................................................................................13一、概述虽然软判决译码、级联码和编码调制技术都对信道码的设计和发展产生了重大影响，但是其增益与Shannon理论极限始终都存在2～3dB的差距。因此，在Turbo码提出以前，信道截止速率R0一直被认为是差错控制码性能的实际极限，shannon极限仅仅是理论上的极限，是不可能达到的。根据shannon有噪信道编码定理，在信道传输速率R不超过信道容量C的前提下，只有在码组长度无限的码集合中随机地选择编码码字并且在接收端采用最大似然译码算法时，才能使误码率接近为零。但是最大似然译码的复杂性随编码长度的增加而加大，当编码长度趋于无穷大时，最大似然译码是不可能实现的。所以人们认为随机性编译码仅仅是为证明定理存在性而引入的一种数学方法和手段，在实际的编码构造中是不可能实现的。在1993年于瑞士日内瓦召开的国际通信会议(1CC，93)上，两位任教于法国不列颠通信大学的教授C.Berrou、A.Glavieux和他们的缅甸籍博士生P.thitimajshima首次提出了一种新型信道编码方案——Turbo码，由于它很好地应用了shannon信道编码定理中的随机性编、译码条件，从而获得了几乎接近shannon理论极限的译码性能。仿真结果表明，在采用长度为65536的随机交织器并译码迭代18次情况下，在信噪比Eb/N0≥0.7dB并采用BPSK调制时，码率为1/2的Turbo码在AWGN信道下的误比特率≤10-5，达到了与Shannon极限仅相差0.7dB的优异性能（1/2码率的Shannon极限是0dB）。Turbo码又称并行级联卷积码(PCCC，ParallelConcatenatedConvolutionalCode)，它巧妙地将卷积码和随机交织器结合在一起，在实现随机编码思想的同时，通过交织器实现了由短码构造长码的方法，并采用软输出迭代译码来逼近最大似然译码。可见，Turbo码充分利用了Shannon信道编码定理的基本条件，因此得到了接近Shannon极限的性能。在介绍Turbo码的首篇论文里，发明者Berrou仅给出了Turbo码的基本组成和迭代译码的原理，而没有严格的理论解释和证明。因此，在Turbo码提出之初，其基本理论的研究就显得尤为重要。J.Hagenauer首先系统地阐明了迭代译码的原理，并推导了二进制分组码与卷积码的软输入软输出译码算法。由于在Turbo码中交织器的出现，使其性能分析异常困难，因此S.Benedetto等人提出了均匀交织(UI，Uniforminterleaver)的概念，并利用联合界技术给出了Turbo码的平均性能上界。D．Divsalar等人也根据卷积码的转移函数，给出了Turbo码采用MLD时的误比特率上界。对于Turbo码来说，标准联合界在信噪比较小时比较宽松，只有在信噪比较大时才能实现对Turbo码性能的度量。因此，T.M．Duman、I.Sason和D.Divsalar等人在Gallager限等已有性能界技术的基础上进行改进．扩展了Turbo码性能界的紧致范围。D.Divsalar等人还根据递归系统卷积码的特点提出了有效自由距离的概念，并说明在设计Turbo码时应该使码字有效自由距离尽可能大。L.C.Perez等人从距离谱的角度对Turbo码的性能进行了分析，证明可以通过增加交织长度或采用本原反馈多项式增加分量码的自由距离来提高Turbo码的性能。他们还证明了Turbo码虽然自由距离比较小，但其小重量码字的数目较少，从而解释了低信噪比条件下Turbo码性能优异的原因，并提出了交织器增益的概念。S.Dolinar的研究表明，Turbo码的最小距离码字主要由重量为2的输入信息序列生成，是形成错误平台的主要原因。为提高高信噪比条件下Turbo码的性能，就必须提高低重输入信息序列的输出码重。J.Seghers系统地分析了Turbo码的距离特性。由于交织器的存在，无法给出Turbo码自由距离的严格数学表示，相应地也出现了许多分析和计算Turbo码最小距离、重量分布和性能上限的方法。A．Ambroze还构造了Turbo码的树图，用来作为计算码字距离谱的工具。此外，R.M.Tanne、E.Offer和K.Engdahl分别从代数和统计的角度对Turbo码进行了分析。考虑到Turbo码的延时问题，E.K.Hall等人提出了面向流的Turbo码。也可以用其他系统模型采描述Turbo码及其迭代译码过程：T.Richardson把Turbo码作为一个动力学系统进行描述；A.K.Khandani则把Turbo码考虑成一个周期性的线性系统；J.Laertyy,X.Ge和F.R.Kschischang描述了Turbo码的图模型；在图模型的基础上，D．J．C．MaKay等人证明了Turbo码的校验矩阵与LDPC码的校验矩阵是等价的，从而可以将Turbo码看成一类特殊的LDPC。二、PCCC码的编码算法输入：信源消息u（消息分组u）输出：码字v处理：信源输出为一系列二进制数字0和1。在分组码中，这些二进制信息序列分成固定长度的消息分组（messageblocks）。每个消息分组记为u，由k个信息位组成。因此共有2k种不同的消息。编码器按照一定的规则将输入的消息u转换为二进制n维向量v，这里nk。此n维向量v就叫做消息u的码字（codeword）、码字矢量或码向量（codevector）。因此，对应于2k种不同的消息，也有2k种码字。这2k个码字的集合就叫一个分组码（blockcode）。若一个分组码可用，2k个码字必须各不相同。因此，消息u和码字v存在一一对应关系。由于n符号输出码字只取决于对应的k比特输入消息，即每个消息是独立编码的，从而编码器是无记忆的，且可用组合逻辑电路来实现。定义：一个长度为n，有2k个码字的分组码，当且仅当其2k个码字构成域GF(2)上所有n维向量组成的向量空间的一个K维子空间时被称为线性（linear）(n,k)码。卷积码是把信源输出的信息序列，以k0个(k0通常小于k)码元为一段，通过编码器输出长为n0(≥k0)的码段。但是该码段的n0-k0个校验元不仅与本组的信息元有关，而且也与其他前m段的信息元有关，称m为编码存贮，因此卷积码用(n0,k0,m)表示。卷积码与分组码不同，在进行编码时，本组的校验元不仅与本组的信息元有关，而且还与以前各时刻输入至编码器的信息组有关。同样，在卷积码译码过程中，不仅从此时刻收到的码组中提取译码信息，而且还要利用以前或以后各时刻收到的码组中提取有关信息。正是由于在卷积码的编码过程中，充分利用了各组之间的相关性，因此，在与分组码同样的码率和设备复杂性条件下，无论从理论上还是从实际上均已证明卷积码的性能至少不比分组码差，且实现最佳和准最佳译码也较分组码容易。为简便起见，我们以(2,1,2)卷积码为例，对其进行说明。D1D2输出输入12图1(2,1,2)卷积码编码器图3-2中给出了一个二进制卷积码的编码器，若每一时间单位输入编码器一个新信息元Im,且存储器内数据右移一位，则Im一方面将数据送入存储器，另一方面与刚才存储器中的两个数据按图中的规则进行运算，则此时刻得到两个输出码元)1(Ic、)2(Ic，组成一个子码送入信道。由图可知输入与输出的关系是iiiiiiimmcmmmc2)2(12)1((1-1)在每一时间单位送入编码器k0(这里为1)个信息元，编码器就送出相应的n0(这里为2)个码元组成一个子码cI送入信道。在卷积码中，这0n个码元组成的子码cI，也称为卷积码的一个码段或子组，上式中的“+”是模2和。由式(3-1)可知，输入与输出码元之间是线性关系，所以这类编码器输出的卷积码是线性码，称m为编码存储，它表示输入的信息组在编码器中存储的时间数，称m+1=N为编码约束度，说明编码过程中互相有约束关系的码元个数。同样，在卷积码译码过程中，不仅要根据此时刻输入到译码的子码，而且还要根据以后很长一段时间，如m’段时间内收到的各子码，才能译出一个子码的信息元，通常m’m。称dNm1为译码约束度，称dNn0为译码约束长度，它们分别表示译码过程中互相有约束的码段或码元个数。从式(3-1)中还可看出，输出的码元中，不一定与输入的码元相等，所以这样的码是非系统码。当然，如果输出的码段中的某一位码元与输入的码元固定相等，则这样的码为系统码。总之，在卷积码的各码段之间，不论是编码还是译码，都不是每段各自处理，而是与前后m或m段有关，所以卷积码通常用),,(00mkn表示，Rnk00/，称为卷积码的码率。1.Turbo码的编码Turbo码的编码结构可以分为并行级联卷积码（PCCC）、串行级联卷积码（SCCC）和混合级联卷积码（HCCC）三种，如图1所示。交织器交织器交织器1交织器2交织器1交织器2分量编码器1分量编码器2外码编码器内码编码器外码编码器并行编码器内码编码器穿刺矩阵复接外码编码器内码编码器1内码编码器2(a)(b)(c)(d)图1-1Turbo码的几种编码结构（a）PCCC（b）SCCC（c）HCCC-I（d）HCCC-II1993年，C.Berrou提出的Turbo码就是PCCC结构，主要由分量编码器、交织器、穿刺矩阵和复接器组成。分量码一般选择为递归系统卷积（RSC）码，当然也可以选择分组码、非递归卷积（NRC）码以及非系统卷积（NSC）码。通常两个分量码采用相同的生成矩阵（也可不同）。若两个分量码的码率分别为R1和R2，则Turbo码的码率为：R=212121RRRRRR(1-1)在AWGN信道上对PCCC的性能仿真证明，当BER随SNR的增加下降到一定程度时，就会出现下降缓慢甚至不再降低的情况，一般称为误码平台（errorfloor）。为解决这个问题，1996年，S.Benedetto提出了串行级联卷积码（SCCC）的概念，它综合了Forney串行级联码（RS码＋卷积码）和Turbo码（PCCC）的特点，在适当的信噪比范围内，通过迭代译码可以达到非常优异的译码性能。Benedetto的研究表明，为使SCCC达到比较好的译码性能，至少其内码要采用递归系统卷积码，外码也应选择具有较好距离特性的卷积码。若外码编码器和内码编码器的编码速率分别为RO和RI，则SCCC的码率R为：R=RO×RI（1-2）HCCC是将前两种方案结合起来，从而既能在低SNR下获得较好的译码性能，又能有效地消除PCCC的误码平台，称为混合级联卷积码。综合串行和并行级联的方案很多，这里只给出两种常见的方案，一是采用卷积码和SCCC并行级联的编码方案，如图1（c）所示；另一种是以卷积码为外码，以PCCC为内码的混合级联编码结构，如图1（d）所示。我们主要讨论PCCC结构的卷积码。为便于讨论，将PCCC编码结构重画为图1-2（a）所示。π分量编码器1分量编码器2(a)u=(u0,u1,…,uK-1)v(0)=(v0(0),v1(0),…,vK-1(0))v(1)=(v0(1),v1(1),…,vK-1(1))v(2)=(v0(2),v1(2),…,vK-1(2))+++++π+++++uu’v(0)v(1)v(2)(b)图1-2PCCC编码器基本结构系统包括输入信息序列u，两个（2，1，v）系统反馈（递