一种利用软判决的信道编码识别新算法

于沛东;李静;彭华

【摘 要】The existing methods for channel coding recognition usually use hard-decision of the demodulator output sequence, and their robustness against error bits is to be improved.Focusing on situations of low signal-to-noise ratio, this paper presents a novel recognition algorithm which uses soft-decision.The algorithm is based on the error-containing equation model, and it solves the equation, thus accomplishes the recognition, through regarding the probability that the equation holds right as the measurement of the performance of a solution vector. The use of log-likelihood ratio(LLR) algebra makes the algorithm greatly simplified. Results of simulation experiments show that the new algorithm improves recognition performance,especially in lower signal-to-noise ratio cases,compared to the existing algorithm based on Walsh-Hadamard transform.%现有的信道编码识别方法通常利用解调输出的硬判决序列来进行,其容错能力有待提高.本文针对低信噪比的接收信号,提出了一种利用软判决的编码识别新算法.该算法基于含错方程模型,以方程成立的概率作为衡量解向量性能的量度,从而求解方程,完成识别.对数似然比(LLR)代数的使用使得算法具有简单的形式.仿真实验表明,与基于Walsh-Hadamard变换的传统算法相比,新算法提高了识别性能,且信噪比越低,性能提高越显著. 【期刊名称】《电子学报》 【年(卷),期】2013(041)002

【总页数】6页(P301-306)

【关键词】信道编码识别;软判决;低信噪比;对数似然比(LLR);Walsh-Hadamard变换

【作 者】于沛东;李静;彭华

【作者单位】信息工程大学,河南郑州450002;信息工程大学,河南郑州450002;信息工程大学,河南郑州450002 【正文语种】中 文 【中图分类】TN911.7 1 引言

为了提高数字通信系统中数据传输的可靠性,需要对发送数据进行信道编码.信道编码识别则是对信道编码的和参数的逆向求解分析,它在协作通信、智能移动通信、信号截获等诸多领域中都有重要意义[1].

常规的信道编码识别方法,如高斯直解法[2]、线性矩阵分析法[2]和欧几里得分析法[3]等,通常假定接收序列与发送序列相同,即传输过程中没有发生误码,或者总能找到足够长的无误码序列.在低信噪比强干扰的接收条件下,常规识别方法中关于无误码的假设很难满足,因此具有容错能力的信道编码识别方法成为近年来的研究热点.现有的容错识别方法以求解含错线性方程为主,基于Walsh-Hadamard变换的含错方程求解算法[2,4]就是其中一种经典而实用的算法.此外,一种基于近世代数理论的Sy2sy快速合冲算法也具有一定的容错能力[5];而文献[6]则针对信道编码中的卷积交织提出了具有容错能力的交织参数盲估计方法.

无论是常规还是容错识别,现有的方法通常使用解调输出的硬判决序列进行分析.事

实上,解调输出的软判决中不仅含有比特符号信息(“0”或“1”),还包含了该符号的可靠度信息.使用硬判决的编码识别方法利用了比特符号信息,而丢弃了可靠度信息.在实际中,待识别的信号常属于微弱信号,并且,新通信和信号处理技术的应用,使得正常接收所必需的信号发射功率越来越低.在这种情况下,软判决中的可靠度信息对于提高编码识别的容错能力显得尤为重要,而容错能力的提高是当前信道编码识别研究面临的关键问题之一.

本文创新地提出利用解调输出的软判决序列来进行信道编码识别,给出一种全新的利用软判决的含错方程求解算法,并将其与基于Walsh-Hadamard变换的经典算法进行对比.新算法尤其在低信噪比情况下具有更好的性能,这是使用软判决所带来的必然结果.

2 信道编码识别的含错方程模型及其求解 2.1 含错方程模型

设二元域GF(2)的元素集合为{0,1},其中0为加法零元.考虑GF(2)上的线性分组码和卷积码,它们具有相似形式的监督方程,分别如式(1)和式(2)(本文算式中凡是GF(2)元素之间的加法和乘法运算均为相应的二元域运算)所示：

它们表示了信道编码的约束关系,即码向量 c(或码多项式向量 c(D))应当与监督矩阵 H(或监督多项式矩阵H(D))中的每个行向量正交[7].

对(n,k)线性分组码,码向量 c为1×n向量;令r=n-k,监督矩阵 H是秩为r的r×n维矩阵,因此监督方程组(1)有r个方程.如果接收码字不满足所有r个监督方程,则一定不是该码的码字.如果已知N个码字,则由式(1),可以建立如下方程组[2]：

式中c k为第k个码字(k=1,2,…,N),C为N个码字排成的N×n矩阵,监督向量 h为 H的行向量.解该方程组,即可得到全部的监督向量h,从而实现分组码的识别.

对(n,k,m)卷积码,式(2)中c(D)为1×n的码多项式向量,H(D)为r×n的监督多项式矩阵,D表示单位延时单元.分组码式(1)与卷积码式(2)是相通的,前者可以看作后者仅取D 0项而得.简单起见,考察常用的(2,1,m)卷积码,这时式(2)简化为

c1(D)和c2(D)为两路码序列的多项式表示;h1(D)和h2(D)为两个监督子多项式,它们与生成子多项式的关系为h1(D)=g2(D),h2(D)=g1(D).设卷积码编码器最大时延m=M,两路输出码序列的片段记为(c1,1,c1,2,…,c1,N(M+1))及(c2,1,c2,2,…,c2,N(M+1)),则由式(4),可以建立如下方程组[2]：

其中 hij(i=1,2;j=0,1,…,M.)为 hi(D)的 Dj项系数,以它们为未知量,解该方程组,就可实现(2,1,m)卷积码的识别.

由式(3)及式(5),信道编码识别问题可归纳为求解GF(2)上的线性方程组的问题,方程组的形式为

实际中,接收到的码序列一般含有误比特,即式(6)中系数矩阵A中的元素是含有错误的.由含错的系数矩阵A求解最符合式(6)的解向量x,从而获得分组码的监督矩阵或卷积码的所有监督多项式,达到编码识别的目的,这就是信道编码容错识别的含错方程模型.

2.2 基于Walsh-Hadamard变换的求解算法

利用蝶形运算,Walsh-Hadamard变换(WHT,或称Walsh变换[8])拥有快速算法[9],这使得基于Walsh-Hadamard变换的含错方程求解算法成为一种经典而实用的信道编码容错识别算法.

这里通过式(6)简要阐述该算法的基本步骤[2,4].设解向量x为l维向量,含错系数矩阵 A为N×l矩阵.算法首先设置一个2l维统计向量t,并将 A的所有行向量(二进制)

转化为十进制数,使向量t中以各十进制数为坐标的元素之值等于该十进制数出现的次数;然后,对统计向量 t作快速 Walsh-Hadamard变换(FWHT),将t变换为一个2l维的谱系数向量s;最后,从 s中找出数值最大的元素,其坐标对应的二进制向量即为最优的解向量.实际操作时,一般需从 s中找出若干个最大元素,从它们的坐标向量中挑选符合实际的解向量.例如,全零解向量不合实际,则应当舍弃.

谱系数向量 s的元素具有明确的物理意义：元素的值等于该元素的坐标所对应的二进制向量使得方程组N个方程(A的每一行对应一个方程)中成立的方程个数与不成立的方程个数之差.因此,该算法最终得到方程组的解是使得方程成立的个数最多的解.也就是说,该算法以方程成立个数作为解向量符合度的量度. 3 利用软判决的含错方程求解算法 3.1 算法的基本思想

解调输出的软判决中不仅含有比特符号信息,还包含了该比特的可靠度信息.上述基于FWHT的算法是利用接收解调硬判决序列来构造系数矩阵A,在有限域GF(2)中求解含错方程(6).它仅考虑到整个序列的误码率,而没有利用各个比特的可靠度信息,这导致算法对接收信息的利用不充分,影响算法的性能.在极端情况中,假使构造的方程组中,每个方程都含有较多误比特,那么FWHT方法很可能无法找出方程组的正解.而在实际应用中,待识别信号的噪声环境可能十分恶劣,可靠度信息变得尤为可贵. 利用接收解调的软判决序列,可以从全新的角度考虑含错方程模型(6)的求解.我们不是简单地关心某个方程成立与否,而是关心它成立的概率;不以方程成立的个数为衡量标准,而以整个方程组成立的概率作为解向量符合度的量度.仍然考察GF(2)上的线性方程组(6),记 A=(aij)N×l,x=(x1,x2,…,xl)T,假定方程组中的各个方程相互,定向量 x的符合度函数J(x)为所有方程成立的联合概率,即

其中,由于涉及二元域和实数域运算的混合,特别地用∑ ⊕表示模2求和,用⊗表示二

元域乘法.式中求积的对象是单个方程成立的概率.选取使得符合度函数J(x)最大的且符合实际的解向量 x,即可完成含错方程模型的求解.这就是利用软判决的含错方程求解算法的基本思想. 3.2 算法的实现

接收软判决序列中含有每个系数aij的对数似然比(LLR),其绝对值即是该系数的可靠度信息,可转化为概率 P(aij=1)=1-P(aij=0),故式(7)中的概率是可以计算的.但是,将接收LLR值转化成概率值来计算式(7),其过程比较复杂,且运算量太大.如果将运算从概率域转移到LLR域中,使运算直接在各系数 aij的LLR值之间进行,则可以利用LLR代数[10]来简化过程,并得到简捷的近似计算方法.

为此,先不考虑方程成立的概率,而考虑其LLR.定义GF(2)中的随机变量 a的LLR值为L(a)=ln(P(a=0)/P(a=1)),并记方程组(6)中第i(i=1,…,N)个方程所对应的对数似然比Li为

于是问题可转化为Li的计算.在开始计算之前,先引入LLR代数的一些结论.记a与b皆为GF(2)中的随机变量且相互,c亦在GF(2)中取值,则有以下结论[10]：

其中sign(y)表示取实数y的符号(±1).显然,在L(b)=+∞的情况下则有

利用上述结论很容易计算 Li.首先,由式(10)可去掉式(8)LLR函数内的模2求和,从而将Li化简为

然后,根据式(9)可消去LLR函数内的xj,再由式(11)可知j只需在较小的集合中取值,即

其中集合 Φ={j|xj=1,j=1,…,l},L(aij)可直接从接收软判决序列中取得.这就是方程组(6)中第 i个方程LLR值的近似算式,其中仅含有简单的取符号运算和比较运算. 接下来考虑符合度函数J(x)的计算.显然,通过先把Li转化为第i个方程成立的概率,再将所有 N个概率值相乘的方法来计算J(x),其运算量仍然很大;另外由于概率均在[0,1]中取值,则当N较大时,所有解向量x对应的J(x)值都接近0,这可能影响计算精度.为此,不直接计算 J(x)而计算其对数值 ˆJ(x)=ln(J(x)),称ˆJ(x)为对数符合度函数.考虑到对数函数的单调递增性质,使用对数符合度函数不会影响解向量的正确选取.对于GF(2)中的随机变量a,其对数似然值有如下近似算式：

则对数符合度函数ˆJ(x)可以近似计算为

目前,由式(13)及式(15)给出了利用软判决的含错方程求解算法的计算实现,其中将对数符合度函数ˆJ(x)作为解向量符合度的量度.式(15)右端表明,在所有N个方程的LLR值 Li(i=1,…,N)中,只有负值对ˆJ(x)有贡献,正值则被舍弃而以0代替.这是由于将J(x)修改为对数形式并近似计算而导致的,对数运算是非线性的,当方程成立的概率较大(0.5～1之间)时,其对数值被近似为0.事实上,仿真实验表明,由式(15)给出的算法其信道编码识别性能较差.一个可能的原因就是舍弃正的Li值会较大地削弱算法性能.因此,为了保留正的Li值,继续将J(x)修改为如下形式：称J*(x)为改进的符合度函数.显然,改进的符合度函数保留了正的Li值,且具有更为简单的形式,即

第4节所述的仿真实验结果证明了其具有良好的性能.

最终,由式(13)及式(17)给出了本文算法的具体实现,其中仅涉及取符号、比较,以及加法等运算,运算所需LLR值可直接从接收软判决序列中取得.解向量 x对应的J*(x)

值越大,表明 x越符合方程组(6).在BPSK调制的情况下,从AWGN信道中获得的符号采样值正比于该符号的LLR(比值为与噪声功率有关的常数),直接使用符号采样值代替LLR不会影响算法结果.

本算法利用了接收解调的软判决序列,在较低信噪比下,软判决中的可靠度信息的重要性将体现得更为突出,此时本算法将表现出优于基于FWHT的算法的性能. 利用本算法进行编码识别与利用基于FWHT的算法时一样,在解含错方程前后还需要一些附加操作.例如,在构造方程前,分组码需要确定码长 n和码字起始比特,卷积码则需要对延时单元数m进行估计;在完成方程的求解之后,还需要从一系列最佳解向量中挑选出符合实际者,进而得到分组码的监督矩阵或卷积码的监督多项式. 3.3 算法运算量分析

仍记 A=(aij)N×l,x=(x1,x2,…,xl)T.计算式(13)时,应避免进行重复的比较运算,为此,可依次将 l个LLR值L(aij)(j=1,2,…,l)加入运算.即首先利用L(ai1)计算解向量(1,0,0,…,0)T和(0,0,0,…,0)T对应的Li值,在此基础上,再利用L(ai2)计算

(1,1,0,…,0)T和(0,1,0,…,0)T对应的 Li值,依此类推,当所有L(aij)均被利用之后,2l个解向量所对应的Li值全部计算完毕.因此,对于 A的一行(即对应于一个方程)需进行(20+21+…+2l-1)=(2l-1)次比较运算.计算完所有N个方程的Li值后,根据式(17)进行求和.为了完成式(6)的求解,总共需要进行N(2l-1)次比较运算和N-1次向量加法运算.

对于长度为2l的统计向量t,对其作基于蝶形运算的FWHT,需要l2l次加法运算.此前,为得到统计向量t,还需对A的全部N个行向量进行二进制到十进制的转换和统计.这是基于FWHT算法的运算量.

上述分析表明,就各自的主要运算而言,新算法的运算量约为基于FWHT算法的N/l倍.

4 仿真实验及结果分析

由于含错方程模型式(6)是线性分组码和卷积码识别的共同模型,故上述算法可对此两种不同的编码进行识别.本节针对一些常用(2,1,m)卷积码(码率为1/2,延时单元的个数为 m)进行仿真实验,对比基于FWHT的识别算法(简称FWHT方法)与上述利用软判决的含错方程求解算法(简称软判决方法)在识别性能上的差异.显然,对(n,1,m)卷积码的识别可以(2,1,m)卷积码的识别为基础来进行.

对于(2,1,m)卷积码,其含错方程的具体形式如式(5).从两路码序列中各截取长(M+1)的片段,拼凑成方程系数矩阵 A的一行,其中M为m的估计值,通常M≥m;解向量x的长度为2(M+1),其元素与两个生成多项式(或监督多项式)的各项系数相对应;A的行数即含错方程组中方程的个数,记为 N.显然,生成多项式的识别正确率与信噪比Eb/N0及用于识别的接收数据量有关,可以将方程个数 N作为所用数据量的量度.仿真实验使用BPSK调制,信道模型为AWGN模型.实验中假定估计值M=m+1. 4.1 有效性验证

图1展示了m=4(即(2,1,4)卷积码)情况下,当Eb/N0=-1dB,数据量 N=20000时,两种方法解向量符合度的分布情况.FWHT方法与软判决方法各自的解向量符合度具有不同的意义.前者代表了解向量使得方程组(6)中成立的方程个数与不成立方程个数之差,后者则是整个方程组成立概率的近似度量.但由于挑选最佳解向量时直接以符合度的大小为依据,故编码识别的性能仅决定于正确解向量的符合度相对于非正确解向量符合度的突出程度.因此,图1不再关心符合度的具体意义,而是各自相对其最大值进行了归一化处理,以便对比观察.

实验所用生成多项式的系数为(11101;10011).由于对m的估计值M=m+1,故含错方程正确解应为(010011011101)及其左移一位后的(100110111010),其十进制数分别为1245和2490.若数据量足够,则符合度分布图中,在横坐标为1245及2490位置应有突起.可见,图1的两幅子图分别验证了FWHT方法的有效性和本文提出的

软判决方法的有效性. 4.2 识别性能对比

下面通过Monte Carlo实验统计两种方法的识别正确率.图2为m=2且数据量 N=1000时,两种方法的识别正确率随信噪比 Eb/N0的变化曲线.图中显示,相同条件下,软判决方法的识别正确率相对于FWHT方法有所提高,在正确率90%处的信噪比增益约为0.5dB.图3为m=2时,使得识别正确率达到90%所需的数据量N随信噪比Eb/N0的变化曲线.可见,对于(2,1,2)卷积码,达到相同性能时软判决方法相对于FWHT方法节省了近一半的数据量,且信噪比越低,节省得越多.

图4为m=3～5情况下识别正确率达到90%时所需的数据量N随信噪比Eb/N0的变化曲线,其结论与图3类似.当信噪比较高时,软判决方法的优势并不明显,这是由于此时误码率较低,软判决中的可靠度信息的重要性尚未充分体现;当信噪比逐渐降低时,误码率升高(即硬判决的错误增多),从而可靠度信息的作用逐渐凸显,使得实验中软判决方法对数据量的节省逐渐明显.并且,信噪比越低,软判决方法的性能优势将越显著.在某些领域的实际应用中,常常需要对低信噪比强干扰下的接收信号进行信道编码识别,上述实验表明,软判决方法提升了低信噪比下的信道编码识别性能. 5 结束语

在信道编码识别领域,现有的识别方法一般都利用接收解调的硬判决序列,这些方法在低信噪比下的容错能力亟待提高.本文创新地提出了利用解调输出的软判决序列求解含错方程的信道编码识别新算法,它以校验方程成立的概率作为衡量解向量符合度的量度,并利用对数似然比推导得到了较为简洁的近似计算过程.实验表明,与经典的FWHT方法相比,它提高了编码识别的性能.特别是在低信噪比情况下,新算法具有更好的容错能力,信噪比越低,达到相同的识别性能时对数据量的节省越多.

不过,该算法的运算量比FWHT方法有所增加,因此接下来的工作可集中于寻找合适的优化手段,进一步降低新算法的运算量,实现低复杂度算法. 参考文献

【相关文献】

[1]柴先明,黄知涛,王丰华,等.信道编码盲识别问题研究[J].通信对抗,2008,(2)：33-36.Chai Xian-ming,Huang Zhi-tao,Wang Feng-hua,et al.On blind recognition of channel coding[J].Communication Countermeasures,2008,(2)：33-36.(in Chinese) [2]张永光,楼才义.信道编码及其识别分析[M].北京：电子工业出版社,2010.9：1-159.

[3]Wang Feng-hua,Huang Zhi-tao.A method for blind recognition of convolution code based on euclidean algorithm[A].IEEE International Conference on Wireless

Communications Networking and Mobile Computing[C].Shanghai：IEEE Press,2007.1414-1417.

[4]刘健,王晓君,周希元.基于 Walsh-Hadamard变换的卷积码盲识别[J].电子与信息学报,2010,32(4)：884-888.Liu Jian,Wang Xiao-jun,Zhou Xi-yuan.Blind recognition of convolutional codingbased on Walsh-Hadamard transform[J].Journal of Electronics&Information Technology,2010,32(4)：884-888.(in Chinese)

[5]邹艳,陆佩忠.关键方程的新推广[J].计算机学报,2006,29(5)：711-718.Zou Yan,Lu Pei-zhong.A new generalization of key equation[J].Chinese Journal of Computers,2006,29(5)：711-718.(in Chinese)

[6]甘露,刘宗辉,廖红舒,等.卷积交织参数的盲估计[J].电子学报,2011,39(9)：2173-2177.Gan Lu,Liu Zong-hui,Liao Hong-shu.Blind estimation of the parameters of convolutional interleave[J].Acta Electronica Sinica,2011,39(9)：2173-2177.(in Chinese) [7]刘玉君.信道编码(第三版)[M].郑州：河南科学技术出版社.2006：63-71,215-225.

[8]李胜华,曾祥勇,胡磊,等.基于两族函数的低相关二元序列集构造[J].电子学报,2007,35(11)：2215-2219.Li Sheng-hua,Zeng Xiang-yong,Hu Lei,et al.Construction for families of binary sequences with low correlation based on two families of functions[J].Acta Electronica Sinica,2007,35(11)：2215-2219.(in Chinese)

[9]林晓娴,王维欢.SIMD-BF模型上的并行FWHT算法研究[J].计算机时代,2011,(1)：30-32.Lin Xiao-xian,Wang Wei-huan.A study of parallel FWHT algorithm based on SIMD-BF model[J].Computer Era,2011,(1)：30-32.(in Chinese)

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