APP下载

Turbo乘积码译码算法的简化

2014-09-26张晓明韩月平宋庆国

电子设计工程 2014年1期
关键词:码元码字译码

柳 昭,张晓明,韩月平,宋庆国

(山东航天电子技术研究所 山东 烟台 264003)

1993年Berrou等学者提出了基于软输入软输出(Soft Input Soft Output,SISO)迭代译码算法的Turbo码[1]。由于Turbo码具有接近香农限的优异性能,使之成为信道编码领域的研究热点。1994年,Pyndiah将Turbo码的子码码型拓展到线性分组码,认为由分组码串行级联构造的Turbo码同样具较好的性能。Pyndiah还设计出可以实现SISO的迭代Chase译码算法[2],并将其应用于乘积码的译码,给出了一种译码方法类似Turbo码的SISO迭代译码算法,从而提出了Turbo乘积码(Turbo Product Code,TPC)的概念。

1998年Pyndiah针对TPC提出一种修正的Chase译码算法[3],这是一种近似的最大似然译码,可以获得接近Shannon极限的纠错性能。但是这种算法需要大量的运算来寻找竞争码字和计算软输出,因此译码复杂度高,延时大。近几年来,有不少学者提出了TPC改进译码算法[4-5],如梯度算法[6]、并行译码算法等。这些算法在一定程度上减少了运算量,降低了系统延时,但是由于在迭代译码中仍然需要寻找竞争码字和计算软输出,所以算法的复杂度并未实质降低。

本文在传统Chase算法的基础上,提出了两种新的简化方法,这两种方法不再需要寻找竞争码字和计算软输出,大大减小了算法的计算量,提高了算法的译码速度。

1 传统Chase算法

硬判决译码,即代数译码,先用一个固定的判决门限,把超过门限电压的信号判为逻辑 ,把低于门限电压的信号判为逻辑 ,然后利用校验子结合奇偶校验位进行纠错。软判决译码,是指先把解调器输出的抽样电压进行Q进制(Q=2m,m>1)电平量化,再送给译码器进行译码。Chase软判决译码算法是一种软输入硬输出(Soft Input Hard Output,SIHO)译码算法,译出的码字为硬输出。

1.1 Chase算法

假设二进制信息码元{0,1}通过分量码都为线性分组码(n,k,d) 的二维TPC编码器,经BPSK调制后得到发送码字E=(e1,e2, …,en),,再经AWGN信道中传输,N=(n1,n2, …,nn)信道噪声 的均值为0,方差为σ2。接收码字为R=(r1,r2, …,rn),三者满足:R=E+N。Chase算法实现方法步骤[3]如下:

步骤1:对接收码字R进行硬判决得到Y=(y1,y2, …,yn),yj∈{,}0 1 。

步骤2:确定Y的p=[d/2]个最不可靠位,记录其位置。

确定最不可靠位是通过考察yj的可靠度得出的,码元yj的可靠度定义如下:

p(ej= +1/rj)为信道的转移概率,推导过程参考文献[3]。经归一化后,码元yj的可靠度可通过考察|rj |得到, |rj |值越小,可靠度越低。

步骤3:构造测试图样T q。分别在p个不可靠位置上取'0'和'1' ,'0' 其它位置取 ,构造一个由2p个n维向量组成的测试图样T q。

步骤5:将Z q进行代数译码(即硬判决译码)。得到译码结果C i,将译码结果作如下映射:0映射成-1,1映射成+1,后归入集合Ω 。

步骤6:计算集合Ω中的码字C i与接收信号R间的欧氏距离,选出欧氏距离最小的码字作为候选码字D。欧氏距离的计算如下:

1.2 基于Chase算法的软入软出译码算法

上述Chase算法译出的码字为硬输出,纠错能力不能得到保证。为了提高TPC的译码性能,必须采用迭代译码方式,这就需要保证译码器的输出为软数据。下面直接给出译码器软输出值的计算公式,推导过程参考文献[3]。译码器的软输出值为:

其中,R为接收序列,它是经过解调器解调和Q进制量化得到的软数据;D为经过SIHO译码得到的候选码字;C为D的竞争码字,C满足:与接收序列R的欧式距离最小,且Cj≠Dj。由于在候选码字集合Ω中存在找不到竞争码字C的可能,此时可用含可信度因子β(m)的式子来近似计算,β(m)≥0,在实际的工程实践中,β(m)值主要通过仿真实验来确定。用软输出值减去软输入值,就可以得到外部信息。

2 影响算法复杂度的关键因素分析

第1节中介绍的传统Chase算法在硬件上实现比较复杂,主要原因是欧氏距离的计算以及寻找竞争码字C需要大量的运算。欧氏距离的计算可以用相关值的计算进行简化,欧氏距离最小等价于相关值最大[7]。寻找竞争码字C就成为影响算法译码复杂度的关键因素。

竞争码字C同时满足两个条件:1)与接收序列R的欧式距离最小;2)Cj≠Dj。传统Chase迭代译码算法是将条件b放在前[3],先判断Cj≠dj,在候选码字Ω集合中找到Cj≠dj的序列,把找到的序列放入子集Ω1中,Ω1Ω;然后在Ω1中找到与接收序列R有最大相关值的序列作为竞

争码字C。用传统方法寻找竞争码字C半次迭代需要进行n2×(2p-1)次比较,动态构建n2个子集Ω1 ,进行n2次排序计算。传统方法寻找竞争码字C的过程相当繁琐,逐行或逐列译码时每个码元的竞争码字C是动态变化的。

3 新的简化译码算法

梯度算法的思想[6]是:为了简化外部信息的计算,在迭代译码时,用前一次迭代得到的候选码字D(m-2)来代替竞争码字C,省去了寻找竞争码字C的过程来降低译码复杂度。即当dj(m)≠dj(m-2)时,

当dj(m) =dj(m-2)时,

当m〈2时,仍应用Chase迭代译码算法进行译码,m≥2时用梯度算法进行译码, 为串行迭代译码的半迭代次数。由此可见,梯度算法尽管对传统的Chase算法有所简化,然而当m〈2时仍需繁琐的寻找竞争码字;当m≥2需要比对行和列的候选码字,而且部分码元的外部信息仍需通过公式(4)计算。因此,算法的复杂度仍然很大,并未实质减少。

在对梯度算法的研究中发现,行和列的候选码字大部分都保持不变,即dj(m)=dj(m-2),此时外部信息大部分都为β(m)dj。因此在梯度算法的基础上提出两种简化方案。第一种简化方案是:不找竞争码字C,不再计算软输出,外部信息wj直接用经过SIHO译码得到的候选码字D乘以β(m)得到,即wj=β(m)dj,dj∈ { - 1 , 1 } 。此处可信度因子β(m)是经过Q进制量化得到的。

4 性能仿真

使用MATLAB编程工具进行定点数仿真实验,子码选取(64,57)×(64,57)的扩展汉明码构成二维TPC码,编码效率为0.793。调制方式为BPSK,传输信道为AWGN信道。不可靠码元个数p=3,采用串行迭代,迭代次数为3次,8bit量化,缩放因子α(m)=[0.0,0.2,0.3,0.5,0.7,0.9],可信度因子β(m)=[0.2,0.4,0.6,0.8,1.0,1.0],设定参与仿真的码块个数为10 000,误码率仿真图如图1和图2所示。

由图1可以看出,在BER为10-6时,传统Chase算法译码可以获得大约6.6 dB的信道编码增益,相比硬判决译码,编码增益明显提高了大约2.5 dB。不找竞争码字,外部信息用 简化后,编码增益比传统Chase算法仅仅下降了0.5 dB,然而复杂度却大大降低。同时,简化算法比硬判决译码编码增益提高了2 dB。

由图2可以看出,在BER为10-6时,用β(m)简化算法后相比已有的梯度算法[6]编码增益下降了大约0.1 dB。若采用最大相关值的均值简化算法后,此时编码增益比梯度算法提高了大约0.1 dB,比传统Chase算法仅仅下降了0.3 dB,然而两种方法的译码过程比梯度算法和传统Chase算法都简单,复杂度大大降低。由上述分析可见,两种简化算法复杂度更低,实时性更好,而译码性能只是略微降低。

图1 简化后Chase算法译码性能Fig.1 Decoding performance of the simplified Chase algorithm

图2 简化后译码算法与梯度算法的对比Fig.2 Comparison of the simplified algorithm and gradient algorithm

5 结束语

文中在梯度算法的基础上介绍了两种新的TPC软判决串行简化迭代译码方法,以较小的性能代价换取了很大程度上译码复杂度的降低。用β(m)简化算法后可以获得大约6.1 dB的信道编码增益,相比传统Chase算法,编码增益下降了大约0.5 dB;而用最大相关值的平均值简化算法后可以获得大约6.3 dB的信道编码增益,相比传统Chase算法,编码增益仅仅下降了大约0.3 dB。两种简化算法能基本保持传统Chase算法的译码性能,然而译码复杂度却大大降低。这两种低复杂度算法非常适合硬件实现高码率实时译码,具有一定的工程实用参考价值。

[1]Berrou C,Glavieux A,Thitimajshima P. Near Shannon limit errorcorrecting coding and decoding :Turbo codes[C]// IEEE Int.Conf.Communications ICC’93.NewYork:IEEE,1993:1064-1071.

[2]Pyndiah P,Glavieux A,Picart A, et al. Near optimum decoding of product codes[C]//1994 IEEE GLOBECOM. New York: IEEE,1994:339-343.

[3]Pyndiah P. Near optimum decoding of product codes: block turbo codes[C]//IEEE Transaction on Communications. New York: IEEE,1998:1003-1010.

[4]黄小平,简福斌,谭燕庆. 一种新的Turbo乘积码简化迭代译码算法[J].计算机应用研究,2011,28(2):689-691 .

HUANG Xiao-ping,JIAN Fu-bin,TAN Yan-qing. New simplified iterative decoding algorithm for Turbo product codes[J]. Application Research of Computers,2011,28(2):689-691 .

[5]Chen Y,Parhik K. A very low complexity block Turbo decoder composed of extended hamming codes[C]//Proc of IEEE Global Telecommunications Conference.New York: IEEE, 2001:171-175.

[6]徐进延,李红信. Turbo乘积码梯度译码算法[J].通信技术,2008, 41(12) :81-83.

XU Jin-ting, LI Hong-xin.Study of Gradient Algorithm for Turbo Product Codes[J].Communications Technology, 2008, 41(12) :81-83.

[7]王玮,葛临东,巩克现. TPC基于相关运算的迭代译码算法[J]. 计算机应用,2010,30(7) :1760-1762.

WANG Wei,GE Lin-dong,GONG Ke-xian. Iterative decoding algorithm of TPC based on correlation computation[J]. Journal of Computer Applications,2010,30(7) :1760-1762.

猜你喜欢

码元码字译码
基于ZYNQ的IRIG-B(DC)码设计与实现
分段CRC 辅助极化码SCL 比特翻转译码算法
基于校正搜索宽度的极化码译码算法研究
LFM-BPSK复合调制参数快速估计及码元恢复
放 下
数据链系统中软扩频码的优选及应用
放下
基于极大似然准则的短猝发信号盲解调
从霍尔的编码译码理论看弹幕的译码
基于FPGA的IRIG-B码解码器设计