低信噪比下卷积交织器识别

吴昭军, 张立民, 钟兆根

(1. 海军航空大学信息融合研究所, 山东 烟台 264001; 2. 西南电子电信研究所, 四川 成都 610041; 3. 海军航空大学航空基础学院, 山东 烟台 264001)

0 引 言

通信系统中,为了对抗突发信道干扰,交织器被广泛应用于信道编码之中。20世纪70年代初,文献[1]提出了一种能够连续工作的卷积交织器,这种交织器相比于矩形交织器,除了具有确定的交织深度和交织宽度外,还具备收发两端存储器个数减半的优点,故被广泛的应用于如ATSC、DVB-S等通信协议中。对于非合作通信而言,首先需要分析出码字之间的交织映射关系,这是后续信道编码逆向分析的前提[2-13]。

目前大多数算法局限于Turbo码交织器的重建[14-16],而单独针对编码后交织关系识别的算法还比较少。文献[17-18]首先将交织器重建问题作为研究对象,将截获的码元序列排列成分析矩阵,当分析矩阵的列数等于交织深度以及码字长度的整数倍时,矩阵将出现秩亏现象,从而识别出相关参数,但是该方法仅仅能够分析出交织周期,不能对交织宽度、交织深度以及交织起点进行识别,同时该方法不具有容错性;文献[19]为提高容错性,利用消元后相关列与独立列之中0,1个数分布不同,设定门限,判断矩阵秩亏,完成交织周期识别,然后遍历交织宽度、交织深度以及交织起点,实现其他3种参数的识别,该方法虽然具有一定的容错性,但是在识别过程中必须采用三重循环进行高斯消元,其计算复杂度太高,不具有工程实用性;文献[20-24]同样采用了高斯消元的思路,但与文献[19]的不同点在于,在每次高斯消元后,都记录下矩阵中0元素的占有比例,将0元素比例作为矩阵秩亏的度量,该方法容错性能进一步提升,但是计算复杂度高的缺点仍然未能解决。文献[25]从数据帧结构中的同步码作为突破口,利用分析矩阵的列数等于交织深度与数据帧长的整数倍时,交织后的同步码位置对应于分析矩阵列上的一阶累积量将出现峰值,从而实现交织周期识别,然后利用同步位置之间的数量关系,分析出交织深度与交织宽度。该方法虽然克服了传统高斯消元法的缺点,但是在同步位置检测过程中,设定的判决门限并不合理,这导致在高误码率情况下,会出现很高的虚警概率,同时在交织深度与交织宽度识别中,需要完全检测出同步位置,这使得算法在高误码率情况下的鲁棒性不好。在此基础上,文献[26]采用2的幂次倍递减的方式遍历可能的交织周期,使得遍历次数大大减少,然后通过三重循环的方式对数据进行解交织,完成交织深度、交织宽度以及数据可恢复起点识别。该方法计算效率与识别性能有了明显提升,但是在同步码检测过程中,存在对矩阵每一列的统计特性分析不全面,噪声一旦恶化,虚警概率会增加。同时，三重循环解交织过程使得算法的计算效率不高。从以上分析来看,利用交织后同步码的位置分布特性作为卷积交织器识别的突破口,仍然是目前最佳的选择,但是为了实现算法性能与效率的提升,还需要进一步深入分析数据矩阵中每一列一阶累积量的统计特性。

基于此,本文同样基于帧同步码交织以后,分析矩阵中的位置分布规律,但是不同于文献[25-26]的地方在于,在同步码位置检测过程中,全面研究了在不同条件下,分析矩阵中每一列的累积量统计特性,提出了更为稳健的判决门限,为交织周期识别奠定了基础;其次在交织周期识别中,充分利用了分析矩阵的结构特点,仅构造一次分析矩阵即可完成多次的交织周期遍历,极大的减少了分析矩阵的构造次数,使得算法的效率得到有效提升;最后定义了峰值聚合度概念,只需要二重循环即可完成交织深度与交织宽度的识别,相比于文献[26]的三重循环,计算效率进一步提升。从仿真结果来看,提出的方法识别性能要明显好于文献[25-26]中的算法,同时计算效率成倍的提升。

1 卷积交织器原理

卷积交织器是一种能够连续工作的交织器,其交织和解交织的原理框图如图1所示。

图1 卷积交织/解交织原理图Fig.1 Principle of convolutional interleaving/deinterleaving

图1中B为交织深度,J为交织宽度。在卷积交织器中,第0路寄存器无存储单元,第i路寄存器都比i-1路寄存器多J个存储单元。对于每一个到来的码元符号,转换开关转接到下一路寄存器,从第0路一直到第B-1路,周期反复。存储器中最早输出的码元经过调制后,经过信道到达接收端,在接收端解交织的过程与交织过程相反。在图1中,所有的转换开关必须严格同步。在原始序列中,相邻两码元进入交织后,位置距离至少为B·J。设图1中比特流为(x1,x2,…,xl),其中,l为待交织的数据量,则卷积交织的过程可以等价于将序列排入如下的半无限大矩阵中,然后按照列输出交织后的序列,即

(1)

式中,矩阵A中第i行由元素vi=[xi,xi+B,xi+2B,…]构成,且相比于第i-1行,初始元素xi在矩阵中的位置右移J个单位。

解交织的过程是其逆过程,只需要将交织后的数据按列排入矩阵A中,然后矩阵中第i行向左平移(i-1)J个单位,然后按列输出即可。

对于非合作通信而言,卷积交织器识别的主要内容包括:交织周期、卷积交织深度B以及卷积交织宽度J,由于在数据侦收过程中,不可避免会出现数据的丢失,此时还需要识别出数据可恢复的交织起点。本文重点研究的内容就是直接利用截获到的软判决序列,恢复出上述参数,为后续信道编码参数的分析准备条件。

2 基于同步码分布特性的参数识别

2.1 卷积交织周期识别

在实际通信系统中,为了实现帧数据同步,通常会在每一帧数据中添加同步码,而这些同步码同样也会随着业务数据进行交织,如ATSC,DVB-S以及DVB-T等协议[25]。在交织之前,同步码序列位置在一起,交织之后,同步码位置被打乱在业务数据之中,此时如果将交织后的数据序列按行方向排列成分析矩阵,当矩阵的列数是数据帧长以及交织深度B的整数倍时,分析矩阵中每一行同步码位置分布是固定的,对应于交织后的数据,同步码位置分布将出现周期性变化,设最小正周期为T0,则T0为数据帧长L以及交织深度B的最小公倍数,即

T0=lcm(B,L)

(2)

式中,符号lcm(·)表示取最小公倍数。

由上面分析,当分析矩阵的列数正好等于T0的整数倍时,由于矩阵中每一行上的同步码分布一样,此时求取矩阵每一列的一阶累积量,那么在同步码位置上将会出现峰值。设发送的数据序列为(syn,c1,syn,c2,…),其中,ci为码字序列,syn为同步码序列,即

syn=(a1,a2,…,as)

(3)

为了提高算法在低信噪比下的识别性能,本文直接利用信道的软解调序列,并假设调制方式为BPSK,码元c映射方式为:0映射为-1, 1映射为+1,信道噪声为高斯白噪声,则截获的软解调码元x可表示为

x=2c-1+r

(4)

式中,r～N(0,σ2),σ2为白噪声方差。

设构造的分析矩阵为H,列数为l′,即

H=[h1,h2,…,hl′]

(5)

式中,列向量hj(1≤j≤l′)为矩阵H的第j列,即

hj=[x1, j,x2, j,…,xM, j]T

(6)

定义H中第j列的一阶累积量为

(7)

当l′为T0的整数倍时,H中每一行同步码位置分布固定,此时分析矩阵中同步码位置所在列上的一阶累积量服从均值为2c-1,方差为σ2/M的高斯分布,而其他列上的一阶累积量服从均值为0,方差为σ2/M+1;当l′不为T0的整数倍时,文献[25-26]认为此时矩阵中每一列的一阶累积量都近似服从均值为0,方差为σ2/M+1的概率分布,事实上这种近似是非常粗糙的,例如当l′=T0/2时,在构建的分析矩阵中,同步码位置所在列的概率分布是由两部分组成,即同步码序列部分和随机的业务数据部分,二者合在一起,服从均值为(2c-1)/2,方差为σ2/M+3/4的概率分布。当信道环境变得恶劣时,在文献[25-26]设定的门限下,同步码位置的检测将会出现很高的虚警概率。由此可见,还需要全面考虑分析矩阵中每一列的统计特性,而不能简单的用两种概率分布来近似替代。

考虑构建的分析矩阵列数l′为一任意大于0正整数,将截获的数据排入分析矩阵中,当同步码位置分布再次重复第1行中的分布规律时,则已经排入矩阵的数据长度一定为T0的整数倍,由于矩阵的列数是l′,故同时也是l′的整数倍,不妨设此时排入矩阵的数据量为len。由此可知,len为l′与T0的最小公倍数,即

len=lcm(l′,T0)

(8)

此时,在分析矩阵中,同步码位置具有相同分布规律的行将以len/l′为周期间隔出现,不妨记ξ=len/l′,则在分析矩阵中同步码出现相同分布的概率一定为ξ。此时分析矩阵中第j列的一阶累计量cum(j)服从以下的高斯分布:

(9)

从式(9)可知,当ξ→0时,即使存在同步码,cum(j)的概率分布也会趋近于不存在同步码的情况。图2进一步给出了在σ2=3,M=100情况下,不同ξ条件下,累积量概率密度函数。

图2 不同ξ下的概率密度函数Fig.2 Function of probability density at different ξ

(10)

(11)

a2Λ2+a1Λ+a0=0

(12)

其中,

(13)

(14)

(15)

求解该一元二次方程,得到在c=1条件下的最小错误判决门限,即

(16)

当c=0时,此时门限与Λ互为相反数,为了将门限统一于Λ上,只需要取矩阵中每一列的一阶累积量的绝对值,然后与Λ进行比较,即可完成同步码位置的快速检测。由于业务数据长度要远远大于同步码长度,考虑到在低信噪比与门限Λ下,不存在同步码的列,检测的结果出现虚警的概率更大,因此除了要考察同步码的漏警概率外,还需要考虑到来自其他列的虚警概率,这在信噪比较低时,尤为重要。记Psa为当l′为T0的整数倍时,同步码位置出现的漏警概率,而Psf为来源于不存在同步码列(此时ξ=0)的虚警概率,由其概率分布,可以得到计算表达式为

(17)

(18)

当分析矩阵的列数l′为T0整数倍时,设存在同步码的列数为SL,则同步码位置未被检测出来的个数S0服从二项分布,即

S0～B(SL,Psa)

(19)

而非同步码位置所在列被误判为同步码位置的个数S1,同样服从二项分布,即

S1～B(l′-SL,Psf)

(20)

将同步码位置上的漏警以及随机业务数据上的虚警充分考虑在内。按照统计学中3倍标准差准则,当遍历的l′等于T0的整数倍时,检测出的同步码位置数目S应当满足:

(21)

由此,可以得到交织周期识别的最优判决门限Λopt为

(22)

式中,SL一般不能准确获得,故在门限计算中,SL值初始一般设置较小,故设定的实际门限Λs一般小于Λopt。由于实际工程中同步码一般是成字节(8位比特)形式出现,所以在一开始可以设定SL为8,然后按照8的倍式增加。

文献[26]仅仅考虑了同步码所在列出现漏警的情况,却未能考虑到由业务数据所构成列可能会出现虚警的情况,相比而言,本文算法的门限设定更为合理。

(23)

当交织周期门限确定后,需要对交织周期进行遍历求解,该过程是整个卷积交织识别最耗时的过程。文献[25]从初始设定的最小交织周期Tmin到最大交织周期Tmax依次进行遍历,这种遍历方式效率较低,文献[26]首先计算在最大交织周期处的累积量,然后由此结果直接计算与最大交织周期构成2的幂次倍关系处的累积量,其计算效率提升了一倍以上,但是文献[26]仅仅考虑了减少累积量的计算次数,但未能考虑到由于截获的数据量往往非常大,构造分析矩阵同样也会减弱算法的实时性,本文从减少构成分析矩阵的次数出发,提出一种快速的交织周期遍历方法。设在遍历的交织周期为l′,截获的数据总量为L情况下,构造的分析矩阵为X,即

(24)

考虑当分析矩阵的列数等于k·l′的情况,此时分析矩阵的每一列可由X的行间隔k抽样构成,由此可见,当构建的分析矩阵列数由l′扩展为k·l′,对应于一阶累积量为cumk·l′,其每一列可由式(24)计算得到,即

(25)

基于上述分析,可以得到在低信噪比下卷积交织周期快速识别算法,流程如算法1所示。

算法 1 交织周期快速识别Require: Tmin, Tmax, 软判决序列1. 构建遍历周期集合Tset={Tmin, Tmin+1,…, Tmax},初始化标志位flag=02. while Tset≠⌀ do3. 令软判决序列长度为l,l'==Tset{1},N=l/l'构造数据矩阵XN×l'4. for k=1 toTset{end}/l' do5. 计算同步码检测门限Λ以及交织周期检测门限Λs6. 由式(25)计算累积量cumk·l'7. 将cumk·l'取绝对值,并与Λ比较,确定出同步码个数S8. if S>Λs do9. EsT=k·l', flag=110. break11. end if12. end for13. if flag==1 do14. break15. else16. Tset=Tset{l',2l',…,kl'}17. end if18. end whileEnsure: EsT

2.2 卷积交织器参数识别

当交织周期识别完成后,紧接着进行交织器参数识别。交织器参数识别包含的具体内容为交织宽度J、交织深度B以及可恢复数据的交织起点stp。文献[25]主要利用了交织后,同步码位置与交织周期之间的数量关系确定出J与B,这需要以交织周期完全正确,同时检测出全部同步码位置为前提,当信噪比较低或交织周期不正确时,无法解算J与B,同时也未给出可恢复数据的交织起点;文献[26]将J,B以及stp进行遍历,构建出三重循环对数据进行解交织,对应于同步码位置聚集程度越高的参数即为识别的参数。由于这种方法涉及到了三重循环遍历,不可避免存在着计算效率低下的缺点;其次,当同步码位置的分布很接近时,文献中给出的衡量同步码位置聚集程度的方法,难以对其进行区分。基于此,本文重新定义了聚合度这一概念,能够更好的表征同步码位置的聚集程度,仅仅需要二重循环即可完成J与B的识别。

由于在交织前,同步码位置是连续在一起的,当未被交织器打乱时,在每一帧数据中,同步码位置前后两项之差一定为1,基于此,通过遍历J与B对序列进行解交织,当B与J正确时,即使此时可恢复数据的交织起点还未被确定,通过解交织过程仍然能够将某些被打乱的同步码变换到一起。设解交织后,检测出的同步码位置为synpos=[w1,w2,…,wm],将synpos中元素作后向差值运算,得到

Dsynpos=[w2-w1,w3-w2,…,wm-wm-1]

(26)

设Dsynpos中元素等于1的个数为Nums,则解交织后,能够反映同步码位置聚集程度的聚合度ε定义为

ε=Nums/(m-1)

(27)

通过遍历B以及J,使得ε值最大的参数即为识别出的卷积交织器参数,即

(28)

在交织深度以及交织宽度完成识别后,仅仅需要一重循环遍历,即可完成可恢复数据的交织起点识别,此时只需要从1到EsB进行遍历,将其作为数据的起点,利用估计出的EsB以及EsJ对数据解交织,使得ε最大的起点,即为可恢复数据的交织起点,即

(29)

由上述分析过程可知,仅仅利用二重循环遍历即可得到B与J的估计算法,详细流程如算法2所示。

算法 2 交织深度B与交织宽度J快速识别Require: Bmin, Bmax, Jmin, Jmax, EsT1. 赋初值:EsB=0, EsJ=0, εmax=02. for B=Bminto Bmax do3. if mod(EsT, B)==0 do4. for J=Jminto Jmax do5. 利用参数(B, J)将数据解交织6. 利用解交织的数据构建列数为EsT的分析矩阵7. 检测矩阵中同步码位置并求取ε8. if ε≥εmax do9. εmax=ε, EsB=B, EsJ=J10. end if11. end for12. end if13. end forEnsure: EsB, EsJ

当得到卷积交织器的交织深度以及交织宽度后,最后仅仅需要一次遍历循环即可完成可恢复数据的交织起点识别,具体过程如算法3所示。

算法 3 可恢复数据的交织起点识别Require: EsB, EsJ, EsT1. 赋初值:std=0, εmax=02. for i=1 to EsB do3. 剔除序列前i-1个数据,然后利用参数(EsB,EsJ)解交织4. 利用解交织的数据构建列数为EsT的分析矩阵5. 检测矩阵中同步码位置并求取ε6. if ε≥εmax do7. εmax=ε, std=i8. end if9. end forEnsure:std

从算法2与算法3来看,本文仅仅利用二重循环遍历以及单独一次的一重循环遍历即可完成交织深度B,交织宽度J以及可恢复数据的交织起点std识别,相比较于文献[26]的三重循环遍历,算法的计算效率进一步提升。

2.3 计算复杂度分析

3 仿真分析

3.1 算法有效性验证

本节首先验证算法能够实现参数的正确识别。仿真设定信道编码为(63,43)BCH码,数据帧中业务数据由10个码字的BCH码构成,每帧数据同步码位数设定为32,同步码序列为1ACFFC1D(16进制表示形式),截获的帧数目为10 000,卷积交织器交织深度B=7,交织宽度J=9,由于数据帧长度为662,故卷积交织最小正周期T0=lcm(662,7)=4 634;在发送过程中,将数据前46 bit丢弃,同时设定信噪比为-6 dB,仿真中信噪比定义为SNR=10lg(1/(2σ2)),后续不再重复说明。遍历的交织周期范围为Tmin=1 000,Tmax=10 000。按照算法流程,首先假定交织周期中同步码数目SL=16(实际为224个),当遍历到l′=9 268时,检测出同步码位置大于设定的门限,如图3(a)与表1所示,此时得到交织周期为9 268;然后进一步识别最小正周期,由于9 268能够整除2,4,7,故依次构造以4 634, 2 317以及1 324为列数的矩阵,得到每一种情况下的检测门限以及同步码数目如表1所示。

图3 卷积交织器识别过程Fig.3 Recognition of convolutional interleaver

表1 最小正周期识别结果

从表1可以清楚的看出,当矩阵列数等于4 634时,检测出的同步码数目为217,远远大于13.694 2,此时识别出最小正周期为4 634,此时的矩阵中每一列的一阶累积量如图3(b)所示,这与仿真设定一致,说明算法1对于交织周期识别有效。

识别出交织周期后,按照算法2识别B与J。算法中设定Bmin=2,Bmax=16,Jmin=1,Jmax=16,通过二重循环遍历B与J,计算聚合度ε,结果如图3(c)所示,发现在B=7,J=9时,聚合度具有最大值0.7,此时识别出交织深度为7,交织宽度为9,这与仿真设定一致,说明算法2有效;最后遍历从1到7遍历可恢复数据的起点,当起点等于5时,聚合度具有最大值0.973,其解交织结果如图4所示。从图4结果来看,在识别出的参数下,同步码被全部变换到了一起,这证明在起点为5情况下,能够恢复出交织前的数据,说明算法3有效。

图4 解交织结果Fig.4 Result of deinterleaving

3.2 算法综合性能测试

本节主要从容错性能以及实时性两个方面考察算法的综合性能。仿真实验设定为4组,第1组实验主要考察估计的同步码数目对算法性能的影响,仿真中将文献[25]、文献[26]与本文算法进行对比;第2组实验主要用于验证当交织周期与交织深度不是互素关系时,文献[25]算法无法完成B与J的识别,同时也考察本文算法与文献[26]容错性能;第3组仿真实验主要验证数据帧中同步码数目对本文算法与文献[26]算法性能的影响;最后一组实验对比了本文方法、文献[25]与文献[26]算法的实时性。

第1组仿真实验中参数设定与第4.1节中一致,信噪比范围从-11.5 dB到-2 dB,间隔0.125 dB。在同一条件下,将本文方法、文献[25]以及文献[26]算法在同一条件下进行对比,由于本文算法与文献[26]的方法都需要对交织周期内同步码数目进行估计,故设定估计同步码数目SL设定为8 bit, 16 bit, 32 bit, 64 bit以及224 bit(交织周期内实际数目为224 bit),然后统计在不同SL下,本文算法与文献[26]方法正确识别率。3种算法的结果如图5所示。

图5 3种算法的识别性能Fig.5 Performance of three algorithms

从图5结果来看,估计的同步码数目越接近于实际同步码数目,本文算法与文献[26]的方法识别性能就越好。虽然本文方法需要首先设定每一帧的同步码数目,但是即使是在设定的最小同步码数目为8的情况下,本文方法的性能相比较于文献[25]的方法提升2.5 dB,并且在同一SL下,本文方法相比较于文献[26],其性能提升近1 dB,这说明本文设定的同步码检测门限以及交织周期判决门限更为合理。

第2组实验中,信道编码为(63,43)BCH码,设定每一帧数据长度为1 260,其中前32位为同步码,后面1 228位由BCH码构成(19个BCH码加第20个码字前31 bit),卷积交织器,帧块数据以及数据丢失起点设定与第4.1节一致。此时最小交织正周期为T0=lcm(1 260,7)=1 260,图6给出了本文算法与文献[26]方法在不同估计的SL下,交织周期、B以及J识别率。本例中,文献[25]仅能够识别出卷积周期,无法正确识别出B与J,主要原因在于文献[25]认为最小周期等于交织深度B与数据帧长的乘积(该结论仅仅在B与帧长互素成立),而本例最小周期正好等于帧长,这导致文献[25]无法正确解算参数。

图6 3种不同方法对比Fig.6 Comparison of three different methods

第3组仿真实验主要考察交织周期中同步码数目对于算法性能的影响,实验中设定数据帧长度为1 260,每帧数据帧头同步码数目分别为8 bit, 16 bit, 24 bit, 32 bit以及40 bit,设定截获的帧数目为10 000,在不同信噪比下,对比本文算法与文献[26]的方法识别性能,其中两种算法设定的每帧同步码数目与实际情况一致,得到结果如图7所示。

图7 同步码数目对算法影响Fig.7 Effect of synchronization codes on Algorithm

从图7结果来看,当帧头的同步码数目增加时,本文算法与文献[26]的方法性能都有较为明显提升,主要原因在于同步码数目一旦增多,算法检测出同步码的可能性就大,在同步周期检测过程出现误判的概率就越小;同时也注意到,在同一条件下,本文方法相比于文献[26],性能有将近2 dB的提升,这进一步证明本文改进的判决门限更为合理。

第4组仿真实验主要用于对比3种算法的实时性能,实验设定了4组不同帧长的数据,每帧数据的同步码数目为32,业务数据为(63,43)BCH码,码字数目分别为3, 5, 10和20,设定截获的数据帧块数目为10 000。对应于帧长、最小正周期以及每种方法完成一次识别所需要的时间,如表2所示。

表2 算法实时性对比

从表2的结果来看,首先本文方法与文献[26]方法的实时性要明显好于文献[25]算法,并且随着最小交织正周期的增大,算法的耗时差距将会更加明显;其次,本文方法实时性要好于文献[26]的方法,特别是在短周期以及长周期情况下,优势将会更为明显。主要原因在于本文算法充分利用了分析矩阵的特点,仅构造一次分析矩阵就能够完成多次周期参数遍历,使得矩阵的构成次数大大降低;最后,在新定义的同步码聚合度概念下,仅仅需要二重循环遍历方法即可完成B与J的识别,相比较于文献[26]方法,时效性进一步提高。

从以上4组仿真结果来看,与同类算法相比,本文提出的方法在参数识别性能以及计算效率两个方面都具有明显的优势。

4 结 论

本文利用数据帧中同步码序列经过卷积交织后的位置分布规律,提出一种识别性能更好、实时性更高的算法。算法首先深入分析了在数据矩阵中,同步码位置所在列的一阶累积量统计特性,基于最小错误判决准则有效实现同步码的检测;其次充分考虑了分析矩阵中同步码位置列以及其他随机位置列引起的漏警与虚警概率,基于3倍标准差准则,设定了更为合理的卷积周期判决门限;再次,在交织周期识别过程中,利用了分析矩阵中每一行数据的分布特点,提出了一种仅仅构造一次分析矩阵就能实现多个交织周期遍历的方法,使得分析矩阵的构造次数大大减少,使得算法的实时性得到提升;最后在交织深度、交织宽度以及可恢复数据起点的识别中定义了聚合度概念,仅仅需要二重的遍历循环和单独一重的交织起点遍历即可实现参数的识别。仿真结果表明提出的算法能够在低信噪比下有效完成参数的识别,与以往算法相比,本文算法在识别性能以及实时性两个方面都具有明显的优势,在恶劣信道环境下,具有更好的工程实用性。