Turbo乘积码译码算法的优化和改进

J u n l fC mp t rAp l a in o r a o u e p i t s o c o

IS 0 19 8 S N lH . 0 1 D

2 3 0 01 01— 2.

计算机应用， 0 33 () 37— 9 2 1, 3 2:9 3 9文章编号：0 1— 0 1 2 1 )2— 3 7— 3 10 9 8 (0 3 0 0 9 0

C0 DEN J I U YID

ht:/ w . c . n t/ w w j aa p o

di1 .7 4 S ..07 2 1 .0 9 o:0 32/ P J18 .0 3 0 37

T r o乘积码译码算法的优化和改进 ub柳昭’魏延清，,张晓明(东航天电子技术研究所，山山东烟台 24 0 ) 60 3

(通信作者电子邮箱 x oho 1@13 Cl i za37 6 .Ol a 1 )

摘

要：hs2算法是 T ro乘积码 ( P ) C ae ub T C软判决译码中常采用的算法之一。由于传统的 C ae hs2算法中欧氏距

离计算以及寻找竞争码字都需要大量的运算，因而在硬件上实现比较复杂。为此，在传统 C ae hs2算法的基础上， 采用相关度量等价替代欧氏距离的度量，简化寻找竞争码字的过程，以降低译码复杂度；调整竞争码字不存在时的软输出 信息值，以提高编码增益。仿真结果表明：改进算法比传统的 C ae算法译码速度更快， hs译码性能更好，常适合硬件非实现。

关键词：ub乘积码； hs2算法； T ro C ae软判决译码；信道编码增益；复杂度中图分类号： N 1 .2 T 9 12 文献标志码： A

Optm ia i n nd i p o e e o i z to a m r v m ntf r Tur o p o c o e d c d ng a g rt b r du tc d e o i l o ihmU U a .W EIYa q n Zh o n i g.ZHANG a mi g Xio n( h no gA rsaeEet ncTcnl yIstt a ti h n og24 0,C i ) S a dn e p c l r i ehoo tue o co g n i,Y na a dn 6 0 3 hn S a

A s a t h hs2agrh soe o tesfd c ind cdn lo tm fT roPoutC d T C .T e bt c:T eC ae lo tm i n f h o—eio eo i a rh so ub r c oe( P ) h r i

t s g gi dc n e t n lC a e lo i m n e s lr e mo n f c mp tt n t ac l t h E c i e n itn e a d e rh o o v n i a h s 2 a g rt o h e d a a g a u t o o u ai o c u ae t e u l a dsa c n s a c fr o l d c mp t g c d wo d O i i c mp e o i lme ti h a d a e T e eo e o h a i o h o v n in C a e o e i o e r,S t s o lx t mp e n n t e h r w r . h rf r, n t e b ss f t e c n e t￣ h s 2 n o ag r h lo i m,t e c reai n wa u si t d a h t cf rt e Eu l e n dsa c n h r c s fs a c ig f rc mp t g t h o r lt ss b t u e s te mer h ci a itn e a d t e p o e s o e r h n o o ei o t i o d n

cd w r a i lid t rdc h eoigcm l i; ad te sfotu a e w sajs d w e hr w sn oe od w ss ie o eu ete dcd o pe t mp f n x y n h ot up tvl a dut hn tee a o— u ec mp tn o wo d t m p o e t o i an. Th i a in r s lss o t a, c mpae t he c n e to a lo ih, o e ig c de r o i r v he c dng g i e smulto e ut h w h t o r d wih t o v ni n ag rt m l

t e mo i e lo tm a et rp roma c n a t rd c d n p e,a d i i s i b e frh r w e i lme tt n h d f d a g r h h s b t e r n e a d fse e o ig s e d n t s u t l o a d a mpe na i . i i e f a r o

Ke r s ub r ut oe( P ) h s2a oi m o—eio eoig h ne cd ggi;cm l i ywod:T roPo c C d T C;C ae l rh;sfdcs ndcdn;canl oi a d g

t t i n n o p xt e y

0引言 T ro乘积码 ( ub rd c C d, P )在 T ro积 ub T roPout oe T C是 ub卷

化方法，这种方法大大减小了算法的计算量，提高了法的译，算码性能和译码速度。

码 ( ub ovlt nlC d, C的基础上发展起来的。 T ro C n o i a oe T C) uo 19 9 3年 B r u等 提出了基于软输入软输出 ( o n u Sf eo r SfIpt o t t

1 C ae hs2软判决译码算法软判决译码，是指先把解调器输出的抽样电压进行 Q (=,>1 Q 2 m )进制电平量化，送给译码器进行译码。再 C ae hs 2算法的主要思想是：首先在接收序列中确定出错可能性较大的码元位置，由此构造一个二进制试探序列集合；并

O tu,IO) up tSS迭代译码算法的并行级联 T ro码。19 ub 94年，Pn ih y da等提出了分组 T ro码 ( lc ub o e B C) ub BokT roC d, T,以分组码为子码，计出可以实现软输入软输出迭代的设 C ae hs译码算法，并将这种迭代方式应用于乘积码。19 9 8年 Pn ih针对 T ro y da ub乘积码提出了一种基于修正的 C ae译 hs码算法，是一种近似的最大似然译码，以获得接近这可

其次再用每个试探序列修正接收到的硬判决序列，并将修正后的序列输入到硬判决译码器，而得到一个候选码字集合；从最后逐个计算候选码字与接收序列的欧氏距离，挑选出一个与接收序列有最小欧氏距离的候选码字作为最终译码结果。 1 1 C ae法 . hs2算假设二进制信息码元{,} 0 1通过分量码都为线性分组码(,,)的二维 T C编码器，二进制相移键控 ( iay nkd P经 Bnr P aeS i eig B S调制后得到发送码字 E: ( 1e, hs h K yn, P K) t f e, 2…

Sa nn极限的纠错性能。T ro乘积码被人们视为信道编 hn o ub码技术的一项历史性突破 J。它与 R S码、积码以及以 R 卷 S码为外码、积码为内码的级联码相比，有更大的编码增益卷具

和编码效率，而且结构简单、码长变动灵活、译

码复杂度较

小。T ro积码的优异性能使得 T ro积码在深空通信、 ub乘 ub乘卫星通信和移动通信等数字通信系统中均有较广泛的应用前景。目前，国内外对于 T ro乘积码算法的研究主要针对软 ub判决译码中译码复杂度的改善，使得译码性能和复杂度之间达到平衡。近几年来，不少学者提出对 T C译码算法的改有 P

,

e)e (∈ (,一1 )再经加性高斯白噪声 ( d iv+1 ); A dt e i

Wh eG us nN i, WG信道中传输，道噪声 N: i asi o e A N) t a s信 (,,:…, )的均值为 0方差为；/ n, /。,接收码字为 R=( r,r,, )三者满足：= E+N。 h s2算法实现方法步骤 2… 。 R C ae如下：

进。,。如梯度算法一、行译码算法。等。虽然这些算 并。法都在一定程度上减少了运算量，降低了系统延时，是由于但计算中采用了某些近似，可避免地带来一定的性能损失。不本文在传统 C ae算法的基础上，出了一种新的改进和优 hs提收稿日期：0 2 0 .5;回日期：0 2 1 .9 2 1— 8 1修 2 1—0 0。

步骤 1对接收码字 R进行硬判决得到 Y: ( Y,, Y,2…Y )Y ,f∈{ 1。 0,}步骤 2确定 y的 p=L/ J个最不可靠位，录其位 d2记

作者简介：柳昭( 9 6一)男， 18,陕西汉中人，硕士研究生，主要研究方向：航天测控、信道编译码；魏延清 (9 5一)男， 18,河南平顶山人，工程师，硕士，主要研究方向：航天测控、基带信号处理；张晓明(9 6一)女， 17,山东蓬莱人，高级工程师，主要研究方向：航天测控、卫星通信。

38 9置。

计算机应用

第3 3卷

确定最不可靠位是通过考察 y的可靠度得出的， 码元 Y i 的可靠度定义如下：

也为数∑ () n常项， =,其中∑ r为R‘内也 J与C的积，称作R 相关。于c{ 1+}∑ r乘法运算就转与C的由； -, 1,, c;

地 n (裴兰 )砉=) (值越小，靠度越低。可

(化为加减法运算， 1 ) 仅需进行 2 x( n一1 )次加减法运算即可。氏距离的计算结构进行了简化

,没有进行任何算法近似，并因此，相关值最大作为度量等价于欧氏距离最小作为度量，不会

经归一化后，码元的可靠度可通过考察 lI得到， r rI l I J步骤 3构造测试图样。分别在 P个不可靠位置上取…和“”其他位置取“”构造一个由 2 0’ 1, 0,个 n维向量组成 的测试图样 r。 步骤 4构造测试序列 Z=Y T,中④代表异或， o 其即模 2和。 步骤 5将 Z进行代数译码 ( 硬判决译码 )得到译码结，

∑相关值越大，欧氏距离越小。采用相关度量时，仅对欧

影响算法的译码性能。

另外， ( )软输出值 r可简化为：式 3 I,

一

、 D∑R ),C力 f∑R一 C 2∈ (/J =I

\

/

果 C, 将译码结果作如下映射： 0映射成一1 1映射成+1然，,后归入集合。 步骤 6计算集合中的码字 C与接收信号 R间的欧氏‘距离，出欧氏距离最小的码字作为候选码字 D。欧氏距离选

() k d,

C譬力

22简化寻找竞争码字 C的过程 .竞争码字 C同时满足两个条件：)与接收序列的欧氏 1距离最小； ),传统的 C ae 2 c≠d。 hs迭代译码算法足将条件 2 )放在前，先判断 c≠ d, 在候选码字力集合中找到 c d j≠ i 的序列，把找到的序列放人子集 1中， 力；后在力1力1c然 中找到与接收序列有最大相关值的序列作为竞争码字 C 。用传统方法寻找竞争码字 C半次迭代需要进行 n x(一1 2 )次比较，动态构建 n个子集 1进行 n次排序计算。这种方 , 法寻找竞争码字 C的过程相当繁琐，逐行或逐列译码时每个码元的竞争码字 C是动态变化的。 算法的次优方案是：将条件。放在前，则竞争码字 C只需寻找一次，即先在集合中找到与接收序列有次大相关值的码字作为竞争码字 C然后再逐个码元比较 c是否等于 d,,, 若 c≠ d, ,则次大相关值的码字为竞争码字 G; c若=d,,则竞争码字 C不存在。用优化方案寻找竞争码字 C半次迭代仅

的计算如下：

I CI=∑ ( c cE( 1一 ) R— 正一；;f+, 1 ) 12软入软出 ( IO)码算法 . SS译

() 2

由于

C ae法是一种软输入硬输出 ( o n u H r hs 2算 SfIpt ad t O t tSH译码算法， up,I O) u译出的码字为硬输出，纠错能力不能得到保证。因此， _高 T C的译码性能，为『提 P必须采用迭代

译码方式，这就需要保证译码器的输出为软数据，即带有可靠度量值的数据。下面直接给出译码器软输出值的计算公式，推导过程参考文献[] 3。译码器的软输出值为：

r= ( C一尺 D‘‘ 4 、 I R I,C,/ r『:』—『 I一 ) l【 I m) ( d,,

I fl 3’、、

C隹

其中： R为接收序列，它是经过解调器和 Q进制量化得到的软数据； D为上述 C ae hs2算法得到的候选码字； C为 D的竞争码字， C满足：与接收序列 R的欧氏距离最小， C≠ D。且 由于在候选码字集合 n中存在找不到竞争码字 C的可能，此时可用含可信度因子卢 m)的式子来近似计算， ( (卢 m)≥ 0,在实际的工程实践中， ( m)值主要通过实验来确定。用软输出值减去软输入值，可以得到外部信息[f m)。就 .(] f,

需进行次比较和 n次排序，而且逐行或逐列译码时每个码元的竞争码字 C是固定不变的。这种方案大大降低了算法的复杂度，减小了译码延时。23调整竞争码宇不存在时的软输出信息值 .

算法实现过程中，对竞争码字不存在时的软输出信息 J k d作调整， B )i (明显提高了译码的性能。当选择最不可靠位 P=3时，候选码字集合力中只有 8个候选序列，逐个码元寻找竞争码字时，大部分码元竞争码字不存在，常能找到竞争通码字的码元个数很少。传统 C ae hs 2算法中竞争码字不存在时软输出信息应该等于卢 J d(,{,}。法的创新 ( ),d∈一1 1 )算 j}

2 C ae hs2算法优化和改进第 1中介绍的 C ae章 hs2软判决译码算法在硬件上实现比较复杂，主要原因是欧氏距离的计算以及寻找竞争码字 C 都需要大量的运算。因此，有必要对算法进行改进，使其在译码复杂度和译码性能之间达到很好的折中。 2 1采用相关计算等价替代欧氏距离的计算 .传统 C ae hs2算法需要计算测试序列与接收码字之间的欧氏距

离，中选取欧氏距离最小的码字作为候选码字 D。从 而在寻找竞争码字 C时，也是在与 d符号不同的码字集合中 选取欧氏距离最小的码字作为竞争码字。由式 ( ) 2可见，欧

之处：对竞争码字不存在时的软输出信息 ( d作调整， )提高了码元的可信度。调整过程如下： 1计算所有存在竞争码字的码元外部信息绝对和； ) 2统计存在竞争码字的码元个数； ) 3计算所有存在竞争码字的码元的外部信息的加权平 )均和；

4对竞争码字不存在的码元的软输出信息 ( ) i以 ) k d乘上述计算的加权平均和；

氏距离的计算需要进行 2 n次减法运算，×× 2 n次乘法运算和2×n次加法运算，硬件实现上逻辑资源开销非常大。以下理论提出了一种采用相关作为度量的算法。 欧氏距离计算式可展开如下：

5按照软输出信息值减去软输入信息值计算外部信息 )值。

上述改进方法中，由于能找到竞争码字的码元个数很少， 所以给算法带来的额外复杂度不大，而且相对于明显提高的信道编码增益，这种改进方法是非常实用的。

I—=∑(— ) C R I 0=∑ 2∑ ()一∑0;+ 2 J=【 J L J l 』 l

c∈{,}:一1+1

() 4

3性能仿真 使用 M t b编程工具进行定点数仿真实验， al a子码选取

对于个给接码字R∑ 2常数∑ ( 一定的收， 为项， )

第 2期

柳昭等： ub T ro乘积码译码算法的优化和改进

39 9

[4 5 4 6,7,]×[4 5,] 6,7 4的扩展汉明码构成二维 T C码。调 P

复杂，在硬件上实现逻辑资源开销非常大，而且译码速率不高。本文介绍了一种基于相关的 T C软判决译码方法， P重点对算法进行了改进，改进后可以获得大约 7 4d . B的编码增

制方式为 B S传输信道为 A N信道。不可靠码元个数 P K, WG P=3采用串行迭代¨迭代次数为 3次， i量化，,, 8bt设定参与仿真的码块个数为 1 0 0误码率仿真图如图 1和图 2所 00,示。仿真结果表明， B R为 1时， P在 E 0 T C编码可以获得大约 7 4d . B的信道编码增益。相比梯度算法，编码增益明显提高了大约 14d效果十分

理想。采用相关作为度量来等 . B,价替代欧氏距离后，然简化寻找竞争码字 C ae虽 h s2算法的编

益，比梯度算法编码增益提高了大约 1 4 d,比传统相 . B相C ae hs算法编码增益提高了近 1 B; 同时简化了 C a 2算法， d hs e 大大降低了译码复杂度，减小了译码时延。这种低复杂度算法非常适合硬件实现，具有一定的工程实用参考价值。参考文献：『 B R O ,G A I U 1 1 E R UC L V E X A,T I I J H M .N a h n o H T MA S I A P erS a n n

码增益比传统 C ae法的编码增益下降了大约 0 1 B, hs2算 .但 d是这种简化方法大大降低了 T C译码的复杂度。同时，简 P对化后的算法改进软输出信息口 k ( )后编码增益明显提高了大

l i err orcn o ig ad d cdn: T ro cds[】/ i t r - r t g cdn n eoig ub oe C/ m oc e iI,3 I CC 9: EEE I t r a in l n e e c n C mmu iai n .Pic t n en t a o Co f r n e o o n c to s s a— a y E wa:I EE, 1 9: 0 4—1 7 . 9 3 16 0 1

约 1 B, 但给算法带来的额外复杂度不大。 dl 0

[] P DA R L VE X A IA TA t 1 er pi md— 2 YN IH,G A IU ,PC R ,ea.N a ot mu e cdn f rd c cds[】/G O E O’:Go a T l o o igo out oe C/ L B C M 9 p 4 lbl e cm— emu i ai n o f r n e n c t s C n e e c .P s aa y E o ic t wa:I EE, 1 9 9 4, 1 3 9—3 3:3 4 .

1一 0

[】 3l一 0

P N I H R M.N a pi m e o ig o rd c o e:bok Y DA e ro t mu d c dn fpo u t d s l c c

trocd s J .I E r sco so o u i tn,19,6 ub oe【】 E E Ta at n nC mm nc i s 9 8 4 n i ao () 10 8:0 3—1 1 . 0 0

重。 4 I1- 05l。一

[]王琳. 4高效信道编译码技术及其应用【 .

京：民邮电出版 M】北人社，0 7 1 0 2 0:—1 .

[】郭立浩， 5蒋培文，郑雪峰， T C编码在高码率数传中的应用等. P[]飞行器测控学报，00 2 () 5 5 . J. 2 1,9 5:1— 52 4 6 8 1 O l 2

1— 07 0

[]黄小平， 6简福斌，谭廷庆，一种新的 T ro乘积码简化迭代译等. ub码算法[]计算机应用研究，0 12 ( ) 69— 9 . J. 2 1,8 2: 8 6 1

[ b NO/ E/]dB

图 1简化寻找竞争码字和传统寻找竞争码字 B R对比 E1一 0 1一 0

【]张天瑜. 7基于偏移量和归一化的改进型 T C译码算法研究【] P J. 长春工业大学学报：自然科学版，0 0 3 ( )4 7—4 2 2 1, 14: 1 2.[】 C E 8 H N Y,P R .A vr wcm lxybokT rodcdr A HI K eyl o pei lc ub eoe K o t cm oe fetn e a mig cd s【/ G O E O ': o p sd o xedd h m n oe C]/ L B C M 0 1I EEE Gl b l T lc mmu i ai n n e e c . P s aa y I EE, o a e e o n c t s Co r n e o f ic twa: E2 01 0,1 1: 71—1 5. 7

1一 0。

置1- 0 4∞

【】徐进延， 9李红信. ub T ro乘积码梯度译码算法研究[】通信技术， J.2 0,1 1 ) 8 8 . 0 8 4 ( 2: 1— 3 [ O V N T AC E E C 1 1 A S R E L ,G L E ,B O S E - E L R B R S I R JM,e a.A lw t 1 o cmpe i lc rod cd rac i cue『 1 E E T a sci s o l t bo k t b e o e rht tr J .I E rn at n xy u e o

10一

1一 0 l 0

0

2

4

6

8

1 0

1 2

o o mu i tn,2 0, 6 1 ) 18 nC m nc i s 0 8 5 (2:9 5—18 . ao 9 7

[/]d Eb N0/B

[1岳殿武 .组编码学[ .安：安电子科技大学出版社， 1】分 M】西西20 7: 3一 l O 0 4 2 .

图 2改进软输出信息后译码性能仿真

4结语 T C软判决译

码算法是当今信道编码领域的研究热点之 P一

【2 1]王玮，葛临东，巩克现.T C基于相关运算的迭代译码算法[] P J. 计算机应用，0 0 3 ( ) 16 2 1,0 7:7 0—16 . 7 2[3 1】朱光喜，何业军，王锋， T ro乘积码的两种迭代译码器的比等. ub较【]电讯技术，0 4 4 ( ) 0—3 . J. 20,46:3 4

,

对它的研究具有一定的现实意义。统 C ae算法译码传 hs2

(上接第 3 4页) 8[】 R SI 6 O S G,D MMIK T E L ME T LD J pia pr r . I C ,B U N HA .O t l e om c fa c n trn n r c n iu a l DM p i a e w r s u i g s b n e mo i i g i e o fg r b e W o o t ln t o k sn u - c

mo i rn fp a e mo u a e in l sn s n h o o s a l- n ti g o h s - d l td sg a s u i g a y c r n u mp i o

td io a nl i[] Jun fLgtaeT cnlg, u ehs g m a a s J . ora o i w v eh ooy t r ys l h 2 0,2 (0:3 3—16 . 0 8 6 1) 15 31ANDERS ON B, KOW ALC YK T Z A, CL ARKE K, e 1 Mu ta. hi

cri ut lxn J .Ju a o ihw v e h oo y 0 0 ar rm lpe ig[】 o r l fL g t ac T c n l,2 0, e i n g1 ( 2:1 3 8 1 ) 6 9—1 4 . 6 8

i p i n o i r gfro t a n tok J .Ju n fLg t m ar t nt n o pil ew r s[】 o r a o i— me m o i c l hwa eT c n lg,2 0 2 1 ):3 2 v e h oo y 0 9, 7( 6 7 9—3 3 7 6.

[] RC E 7 IHT R A,FS E IHL R W,B C O K H,e a.O t a p r r nc t 1 pil e oma e c f m nt n n t saetad en grbe D M ntok J . o ir gi r prn n of ual WD e rs[] o i n a i wI E P c e ig:O te c o is 0 2 4 ( ) 1—5 E r

e dn s po l t nc,2 0,1 9 1: o er .

【 2 Y N 1] A G Y,Y ,D N AH.Suyo h fut r o.n e U QF O G td nte alac n1 ed. i tcn ae n w vlt igl t d t tn p n il【/ et gbsd o ae s ua y ee i r cpe C】/ i e n r i co iI I 9 P o e d n f t e 2 0 WAS n e ai n l Co f r n e C E 0: r c e i g o h 0 9 E I t r to a n e e c no n o ma in En i e rn . P s aa a: I n I fr t g n e g o i i c t w y EEE, 2 0 0 9, 2 51—:1 1 4. 5

[】 Y Y .A a s fot a pr r ac nt n tos 8 AH A C B n l i o pi l e o nemoir gme d ys c fm o i hb s do atr n i errr eet ai C/ ae n qfc dbt r t s m t n『 1/WO N 2 0: oa o a i o C 0 5I t r ai n n e e c n n e t a Co fr n e o Wie e s a d Op ia Co n ol r ls n tc l mmu i ai n nc t s oNe wo k .P s a a y EE t rs ic t wa:I E,2 0 0 5:1 6—1 9. 9 9

[3崔锦泰. 1]小波分析导论[ .正兴，西安： M]程译.西安交通大学出版社，9 5 19 .[ 4赵学智，叶邦彦.基于二分递推 S 1] VD的信号奇异性位置精确

[] S E 9 H N T S R,ME G K,L U A P T ta.O t a p r r a c N A ,e 1 pi l e o n e c fmmo i rn sn r fca e r ewo k tan d wi s n h o o s n ti g u i g a t i ln u a n t r r i e t a y c r n u o i i l h

a lu ehs ga[J . IE P ooi eh o g L tr, mpi d i orms t t] E E h t c cnl y et s n T o e2 1,2 ( 2:1 6 0 0 2 2 ) 6 5—1 6 . 6 7

检测[]电子学报，0 24 () 5 J. 2 1,0 1:3—5 . 9[5刘强， 1]

杨岳湘，唐川.于动态轮询策略的网络故障监视算法基

[0 K ZC IB T KU A 0 H D H K .O t a p r r ac 1】 O I K, A Y , I E I O T pi l e o ne c fm

(J计算机工程与设计，09 3 ( ) 26— 16 J. 2 0,0 9: 1 2 6 . 4

本文来源：https://www.bwwdw.com/article/sj21.html