基于校验方程平均符合度的Turbo码交织器估计

刘　骏,李　静,彭　华

(解放军信息工程大学，河南郑州 450002)



基于校验方程平均符合度的Turbo码交织器估计

刘骏,李静,彭华

(解放军信息工程大学，河南郑州 450002)

现有的交织器估计方法通常利用解调输出的硬判决序列进行，其容错能力有待提高，且一些方法只针对特定的交织器结构.针对Turbo码的随机交织器，提出一种利用接收软判决序列进行估计的算法.首先提出校验方程平均符合度的概念及计算方法，然后利用正确交织位置的码字可使得校验方程符合度取到最大值这一事实，逐步实现交织位置的估计.特别地，所提算法在删余条件下仍然有效.仿真结果表明，与现有的相关方法对比，特别是在低信噪比条件下，本文算法具有更好的性能以及相对低的复杂度.

turbo码交织器；软判决；低信噪比；校验方程平均符合度

1　引言

信道编码参数分析[1]是在编码参数未知的情况下，通过分析接收编码序列来识别编码参数，最终实现信息序列的提取，它是认知无线电、智能通信和信号截获等领域的关键技术之一.1993年Claude Berrou等人提出的Turbo码[2]为信道编码领域带来了一场革命，其通过引入交织器和解交织器，实现了随机性编码，获得了接近Shannon理论极限的性能.Turbo码在低信噪比环境中所展现的优异性能，使得其被广泛应用于现代数字通信系统中，因此对其参数的识别分析具有重要意义.

针对Turbo码的分析识别主要包括递归系统卷积(Recursive Systematic Convolutional,RSC)子编码器以及交织器.目前对于交织器的识别研究相对较少，文献[3～6]对矩形交织器和卷积交织器的识别进行了研究.然而Turbo码一般进行伪随机交织来获得更高的编码增益，文献[7～9]针对Turbo码的伪随机交织进行了分析.其中文献[7]和[8]都是基于多样本数据的一阶相关统计算法，文献[7]要求接收序列无误码，而文献[8]要求接收序列中的信息序列无误码.文献[9]也是基于多样本数据，利用信息序列和交织后的编码序列对交织器逐位恢复，对每一位交织图案列出多个候选，并计算出由每位候选带给卷积分量码编码器状态的平均信息熵，通过设定检测门限对候选进行排除，最终得到整个交织图案.

由于Turbo码主要应用于低信噪比环境中，接收方特别是信号截获方，接收的都是低信噪比信号，这给Turbo码编码参数的分析识别带来了困难与挑战.上述文献中关于Turbo码的分析方法通常使用解调输出的硬判决序列，而由低信噪比信号得到的解调硬判决序列往往存在大量的误码，因此传统的依靠无误码或者低误码率的识别分析方法不再适用.目前已有文献基于解调软判决对RSC子编码器进行识别[10,11]，文献[11]提出利用解调软判决，建立编码系数的代价函数，借助实数域中的优化理论和方法，求得编码器系数的最优解.然而针对交织器的基于解调软判决的分析识别方法还很少见.

本文主要针对Turbo码的伪随机交织，利用解调软判决，提出一种基于校验方程平均符合度的识别算法.文章首先给出了校验方程平均符合度的定义及计算方法，在此基础上，利用每一时刻正确交织位置的码字可使得校验方程平均符合度取到最大值这一特征，逐步恢复交织位置，最终得到整个交织图案.最后对所提算法的性能进行了仿真.仿真结果表明，本文算法能够快速有效地对交织进行识别(包括删余条件下)，与现有的相关方法对比，在低信噪比条件下，该方法具有更好的性能以及相对低的复杂度.

2　问题模型

本文考虑如图1所示的Turbo码编码器，其由两个相同的码率为1/2的递归系统卷积(RSC)编码器通过一个交织器分开并行级联而成.信息序列x通过交织器π得到交织后的序列xπ，交织就是将序列中元素的位置进行重置，即x与xπ所包含的元素内容相同，但元素位置不同.x和xπ分别输入到两个RSC子编码器得到校验序列y′和z′，y′和z′经过删余后得到y和z，并与信息序列x复用，再经过映射调制后通过信道进行传输.

假设编码序列(x,y,z)经过BPSK(BinaryPhaseShiftKeying)映射调制，并通过均值为0方差为σ2的高斯白噪声信道，解调序列经过SISO解映射后得到对应的软判决序列为(a,b,c)(假设能够分离出这三路序列，即假设每帧编码序列的起点和长度已知)，且RSC子编码器参数也已知(可通过文献[11]识别出)，本文讨论在没有删余(码率为1/3)和删余(码率为1/2)两种条件下，利用多组接收软判决序列(a,b,c)恢复交织器π.

3　基于校验方程平均符合度的交织识别

3.1校验方程平均符合度

(1)

其中g1(D)=g1,0+g1,1D+…g1,mDm(m为编码器寄存器个数)为校验序列的前向生成多项式，g2(D)=g2,0+g31D+…g2,mDn为反馈多项式，式(1)可以写为

xk(D)·g1(D)=yk(D)·g2(D)

(2)

由于二元域上两个相等的多项式之和等于零多项式，因此有

xk(D)·g1(D)⊕yk(D)·g2(D)=0

(3)

式(3)左端各项系数为零，因此可改写为

∀t=1,2,…,N(4)

其中⊕和∑⊕分别表示模2加和模2求和，式(4)即为信息序列和校验序列之间满足的校验方程，记式(4)左端部分为

(5)

表示第k帧序列在t时刻满足的校验方程，并定义校验方程的符合度为

(6)

式(6)给出了校验方程的概率形式，显然当校验方程成立时，有Fk,t=1，当校验方程不成立时，有Fk,t=-1.取Fk,t(1≤k≤M)的均值即得到t时刻的平均符合度

(7)

下面讨论如何利用对应于xk(D)和yk(D)的接收软判决序列ak=[ak,1,ak,2,…,ak,N]和bk=[bk,1,bk,2,…,bk,N](ak,n,bk,n∈R，分别表示比特xk,n,yk,n对应的对数似然比，n=1,2,…，N)计算校验方程平均符合度.由于g1,0,g1,1,…,g1,m以及g2,0,g2,1,…,g2,m可以看成是来自F2的互相独立的随机变量，而xk,t和yk,t是已知的接收数据，可视为常量，因此xk,t-ug1,u以及yk,t-ug2,u(u=0,1,…,m)也可看成是来自F2的互相独立的随机变量，根据文献[13]关于F2中独立随机变量概率计算的相关结论，t时刻的符合度可写为

(8)

其中

P(xk,t-ug1,u=1)=P(xk,t-u=1)·P(g1,u=1)

(9)

P(yk,t-ug2,u=1)=P(yk,t-u=1)·P(g2,u=1)

(10)

当编码器系数已知时，P(gi,u=1)(i=1或2)的值是确定的，记

(11)

P(xk,t-u=1)和P(yk,t-u=1)的值可以通过对应接收软判决序列ak,t-u和bk,t-u的值计算后验概率代替，记

(12)

(13)

因此校验方程的符合度计算公式为

(14)

其中q1,u、q2,u、pxk,t-u和pyk,t-u的定义见式(11)、(12)和(13)，通过式(7)可得到t时刻平均符合度Dt(M).显然当t时刻校验关系成立时，Fk,t为正值，且信噪比越高，越接近于1；当校验关系不成立时Fk,t为负值，且信噪比越高，越接近于-1.

3.2交织估计(码率为1/3)

针对图1所示Turbo码编码器，假设共输入M帧信息序列xk(1≤k≤M)，且每帧长度都为N(交织长度也为N).在没有删余(码率为1/3)时，校验序列yk和zk的长度都为N.对于子编码器2，其输入为交织后的信息序列xk,π(1≤k≤M)，则xk,π与zk应满足如下关系

∀t=1,2,…,N(15)

实际中由于交织图案π未知，因此xk,π是未知的.现假设t(t≥2)时刻之前的交织位置π(1),…,π(t-1)已知，则xk,π(1),…,xk,π(t-1)也已知(t=1时，不需要此假设)，并假设t时刻交织位置为π(t)=j(j∈Λt，Λt={1,2,…,N}{π(1),π(2),…,π(t-1)}为t时刻可选的交织位置集合，t=1时，Λt={1,2,…,N})，记校验方程为

(16)

(17)

(18)

3.3交织估计(码率为1/2)

∀t=1,2,…,N/2(19)

(20)

∀t=1,2,…,N/2(21)

(22)

(23)

(24)

其中[it+1jt+1]为t+1时刻可能的交织位置，即

(25)

3.4复杂度分析

由于文献[7]和[8]中均要求信息序列无误码，实际中很难达到这个要求，而文献[9]以及本文都是在接收序列有误码的条件下进行的识别，因此仅对本文与文献[9]中Cluzeau算法的复杂度进行比较.当码率为1/3时，本文算法与Cluzeau算法均需N步计算，本文算法每一步计算复杂度为O(NMm)，算法的总计算复杂度为O(N2Mm)，而Cluzeau算法每一步计算复杂度为O(NM2m)，算法的总计算复杂度为O(N2M2m)，可以看出，本文算法的复杂度相对Cluzeau算法较低；当码率为1/2时，本文算法需要N/2步完成，每一步的计算复杂度为O(N2Mm)，算法的总计算复杂度为O(N3Mm)，此时算法复杂度约为1/3码率时的N倍.

4　仿真及分析

图4给出了信息长度N和帧数M对算法100%识别出交织图案成功率的影响.可见，相同条件下，信息长度N越大，识别成功率越低，因为N越大，即需要识别的交织长度越长，则完全识别出交织图案的难度也相应增加；而帧数M越大，识别成功率越高，因为选用的样本数越多，平均后的符合度越可靠，从而越能区分交织位置的假设是否正确.另一方面，码率为1/3时的识别成功率要比码率为1/2时的高，因为相同条件下，低码率序列含有更多的冗余信息.

表1给出了算法在不同信噪比下100%识别出交织图案所需数据量.从表1可以看出，相同条件下，当信噪比相对较高时，码率为1/3时所需数据量比码率为1/2时低，因为此时接收软判决序列的信息量较大，且码率为1/2时每一步都能确定两个交织位置，因此所需数据量较少；当信噪比较低时，码率为1/3时所需数据量比码率为1/2时高，因为此时接收软判决的信息量减小，而数据量成为影响识别率的主要因素.

表1　算法在不同信噪比下100%识别出交织图案所需数据量M

表2给出本文算法与文献[9]中算法对比情况(码率为1/3).从表2可以看出，达到相同识别性能时，本文算法所需数据量比文献[9]的要少，且信噪比越低(即σ越大)，数据量节省越多.

表2　本文算法与文献[9]算法100%识别出交织图案所需数据量M对比

5　结论

本文针对Turbo码中的伪随机交织，提出一种基于校验方程平均符合度的识别算法.文章首先给出校验方程平均符合度的概念和计算方法，然后推导出1/3码率和1/2码率两种条件下信息位和校验位所满足的校验方程，利用每一时刻正确的交织位置的码字会使得校验方程平均符合度取到最大值这一特征，逐步实现交织图案的识别.仿真结果表明，本文算法能够快速有效地对两种码率下的交织图案进行识别.与现有的相关方法对比，本文算法提高了识别性能，在相同信噪比条件下，达到相同识别性能时所需数据量减少，且信噪比越低，对数据量的节省越多.

需要指出，本文算法是在假设子编码器RSC参数已知的条件下提出的.由于校验方程的推导是在RSC参数已知的前提下进行的，若RSC参数未知或者估计错误，那么即使是正确交织位置的码字也无法对应合法的校验方程，相应地也就无法使得校验方程平均符合度取到最大值，此时本文算法失效.因此在后面的研究中，可以研究子编码器RSC参数与交织器的联合估计.

[1]解辉,黄知涛,王丰华.信道编码盲识别技术研究进展[J].电子学报,2013,41(6):1166-1176.

Xie Hui,Huang Zhi-tao,Wang Feng-hua.Research progress of blind recognition of channel coding[J].Acta Electronica Sinica,2013,41(6):1166-1176.(in Chinese)

[2]Berrou C,Glavieux A,Thitimajshima P.Near shannon limit error-correcting coding and decoding:turbo codes[A].IEEE International Conference on Communication 1993[C].Piscataway:IEEE Press,1993.1064-1070.

[3]Sicot G,Houcke S,Barbier J.Blind detection of interleaver parameters[J].Signal Processing,2009,89(4):450-462.

[4]Lu L,Li K H,Guan Y L.Blind detection of interleaver parameters for non-binary coded data streams[A].Proceedings of IEEE International Conference on Communication ICC 2009[C].Dresden,Germany:IEEE Press,2009.1-4.

[5]Lu L,Li K H,Guan Y L,et al.Blind identification of convolutional interleaver parameters[A].ICICS 2009 Proceedings of the 7th International Conference on Information,Communications and Signal Processing[C].Piscataway:IEEE Press,2009.1-5.

[6]甘露,刘宗辉,廖红舒,等.卷积交织参数的盲估计[J].电子学报,2011,39(9):2173-2177.

Gan Lu,Liu Zong-hui,Liao Hong-shu,et al.Blind estimation of the parameters of convolutional interleaver[J].Acta Electronica Sinica,2011,39(9):2173-2177.(in Chinese)

[7]张永光.一种Turbo码编码参数的盲识别方法[J].西安电子科技大学学报,2011,38(4):167-172.

Zhang Yong-guang.Blind recognition method for the turbo coding parameter[J].Journal of Xidian University,2011,38(4):167-172.(in Chinese)

[9]Cluzeau M,Finiasz M,Tillich J.Methods for the reconstruction of parallel turbo codes[A].International Symposium on Information Theory 2010[C].Austin,Texas,USA:IEEE Press,2010.2008-2012.

[10]于沛东,李静,彭华.一种利用软判决的信道编码识别新算法[J].电子学报,2013,41(2):301-306.

Yu Pei-dong,Li Jing,Peng Hua.A novel algorithm for channel coding recognition using soft-decision[J].Acta Electronic Sinica,2013,41(2):301-306.(in Chinese)

[11]Yu P D Li J,Peng H.A least square method for parameter estimation of sub-codes of turbo codes[J].IEEE Communication Letters,2014,18(4):644-647.

[12]Shen B,Patapoutian A,McEwen P A,et al.Punctured recursive convolutional encoders and their applications in turbo codes[J].IEEE Transactions on Information Theory,2001,47(6):2300-2320.

[13]Hagenauer J,Offer E,Papke L.Iterative decoding of binary block and convolutional codes[J].IEEE Transactions on Information Theory,1996,42(2):429-445.

刘骏男，1990年生于江苏仪征.解放军信息工程大学硕士研究生，主要研究方向为信道编码识别分析.

E-mail:501296470@qq.com

李静女，1972年生于山东烟台.博士，解放军信息工程大学副教授、硕士生导师，主要研究方向为信道编码，信号分析与处理.

Estimation of Turbo-Code Interleaver Based on Average Conformity of Parity-Check Equation

LIU Jun,LI Jing,PENG Hua

(PLAInformationEngineeringUniversity,Zhengzhou,Henan450002,China)

The existing methods for interleaver estimation usually use hard-decision of the demodulator output sequence,their robustness against error bits is to be improved and some methods only aim at certain interleavers.Focusing on the random interleaver of Turbo codes,this paper presents an estimation algorithm which uses soft-decision.Firstly,the concept and calculation method of the average conformity of parity-check equation are given.Then,the permutation positions of the interleaver are estimated step by step,using the truth that the correct permutation position could maximize the average conformity of parity-check equation.Especially,the proposed algorithm still performs well in puncturing case.Results of simulation experiments show that our algorithm has better performance and relatively lower complexity,especially in low signal-to-noise ratio cases,compared to the existing relevant algorithms.

turbo-code interleaver;soft-decision;low signal-to-noise ratio;average conformity of parity-check equation

2015-01-13;

2015-05-05；责任编辑：蓝红杰

国家自然科学基金(No.61072046)

TN911.7

A

0372-2112 (2016)05-1213-06

电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.029