Turbo码S随机交织器的实现*

钱 宏 李广侠

(解放军理工大学通信工程学院研究生4队1) 南京 210007)(解放军理工大学军事卫星通信重点实验室2) 南京 210007)

Turbo码S随机交织器的实现*

钱 宏1)李广侠2)

(解放军理工大学通信工程学院研究生4队1)南京 210007)(解放军理工大学军事卫星通信重点实验室2)南京 210007)

Turbo码中交织器的设计直接影响着Turbo码的性能。在讨论Turbo码交织器的设计准则和类型的基础上,着重介绍了S随机交织器的原理,并给出了其一种基于冒泡排序算法的实现方法。仿真结果表明,中短长度的S随机交织器性能优良。

Turbo码;S随机交织器;冒泡排序算法

Class NumberTN911.22

1 引言

Turbo码最早由法国的C.Berrou等人在1993年的ICC会议上提出[1],因其非常逼近香农限的性能而引起了当时通信领域的轰动。Turbo码通过分量码并行级联实现了应用短码构造长码的方法;并且在编解码过程中引入交织器,使码字具有近似随机的特性;同时,在接收端采用软输入软输出的迭代译码算法来逼近最大似然译码,实现了香农提出的码长趋近于无限长时的随机编码和最大似然译码的思想。Turbo码的提出,标志着信息论和编码技术进入了一个新的阶段。

理论分析和计算机模拟表明,交织器在Turbo码的设计中起着十分重要的作用[2]。自 Turbo码提出之后,众多学者对不同的交织器用于Turbo码时的性能进行了大量的分析和研究。本文探讨了Turbo码交织器的设计准则,列举了一些典型的交织器,并给出了其中的S随机交织器的一种冒泡排序实现方法。

2 Turbo码交织器的设计准则

交织器的性能影响了Turbo码编码器的编码输出距离特性,通过交织能够改变码重的分布,并降低子编码器的输入序列之间和外信息与信道输入之间的相关性,进而在迭代译码过程中降低误比特率。因此,在设计Turbo码交织器时,应遵循以下两大准则[3]:

1)码重分布准则。在AWGN信道下采用最大似然译码算法的线性纠错码的性能,和此种纠错码的最小汉明距离dm或自由距离df有关。Turbo码作为一种线性码,在AWGN信道下,误比特率近似等于:

其中,dm是Turbo码的最小汉明重量,Nmin是码重等于dm的码字的数量min是产生最小汉明重量码字的输入序列的平均汉明重量,N是交织器的长度。由上式可以看出,对于Turbo码,当交织器长度N固定时,要想获得更好的纠错性能,可以通过增加dm或者减小Nmin两种途径。当 Turbo码中的RSC分量码编码器固定时,交织器的结构决定了上述两个参数。因此,Turbo码交织器的设计就是尽量避免两个RSC编码器同时产生低汉明重的校验码字,尽可能地提高码字的dm,减少低汉明重量码字的数量Nmin,这就是码重分布准则。

2)迭代译码适应性IDS准则。对于第一个准则,当采用最大似然译码时,无疑是一个合适的标准,但Turbo码是采用迭代译码方法来逼近最大似然译码,在多数情况下,译码不是最大似然译码,因此必须对这一标准做一些补充。由此提出了第二个准则,即Turbo码的迭代译码适应性准则。

3 S随机交织器的基本原理及其实现

根据设计思想的不同,交织器大致可以分为规则交织器和随机交织器。规则交织器通常按照一定的规则映射来实现交织,常用的有行列交织器和螺旋交织器,比较易于实现,但并不能很好地降低输入信息的相关性,限制了Turbo码性能的提高。

随机交织器被期望能够实现随机交织过程,但实际上采用的随机交织器都是伪随机交织器。应该说,随机交织器能产生性能较好的交织器,尤其是在产生长度比较长的交织器时,性能一般都比较好。但因为是采用随机的方法,有时也会产生性能较差的交织器。正因为没有什么特殊准则要遵守,使得随机交织器很容易产生,但是其性能得不到保障。

S随机交织器,又叫半随机交织器(Semi-random Interleaver),是在随机交织器的基础上引入了限制条件S,是一种结合随机交织和非随机交织特点的交织器[4]。S随机交织器的设计步骤如下:

2)产生一个随机数i,使得1≤i≤N。

3)把i与前面所产生的s个整数相比较,如果当前的选择与前面s个整数中的任何一个相距都不在±s的范围内,则保留之;否则,重新产生随机数i,直到上述条件满足为止。

4)重复步骤2)、3),直到交织器的N个位置均被填满。

S随机交织器是部分基于汉明重原则设计的交织器。重量为2的输入序列通常被认为是引起Turbo码低汉明重码字输出的主要因素。设计S随机交织器的出发点就是要打乱这些重量为2的输入序列,减少这些输入序列同时在两个 RSC成员编码器上产生低重量输出的机会。经过S随机交织器后,使得重量为2的输入序列交织前的距离d1和交织后的距离d2,满足 d1+d2≥s+1,确保了最小的d1+d2值,而且随着N的最大,这个最小值也会随之增大。可以看到重量为2的输入序列被比较有效的分开了。

S随机交织器的设计利用上述搜索算法来实现,该算法的一个缺点是不能确保对于每一个s＜的值,都可以找到一个S随机交织器;而且算法的搜索时间随着s的增加而增加,当N比较大时,这一搜索算法会耗费大量时间。鉴于此,我们提出了S随机交织器的一种冒泡排序实现方法。

为了实现长度为N的S随机交织器,我们首先生成整数1～N的一个随机排列A,然后对其使用冒泡排序算法。通常,冒泡算法中搜索的是一串数字中最大或最小的数[5]。而我们这里采用的冒泡算法中搜索的是满足S随机交织器限制条件的整数,即与前面s个整数中的任何一个相距都不在±s范围内的整数。

仅采用冒泡算法并不能保证将初始序列A变成满足S随机交织器限制条件的序列。我们将初始序列A经过冒泡算法后得到的序列记为A′,将A′分成上下两部分,上半部分为使用冒泡算法后满足限制条件的部分序列,记为序列B,余下部分记为序列C。在执行完一次冒泡算法后,即序列C中不再存在满足S随机交织器限制条件的整数时,将序列C移至序列A′的顶端,并重新记为序列A,然后再执行冒泡算法,直到整个序列A满足S随机交织器限制条件。

图1 冒泡排序算法示例(N=10,s=2)

对应于长度为N,扩展参数为s的S随机交织器的冒泡排序算法,其步骤归纳如下:

1)生成整数1～N的一个随机排列A;

2)将序列A的第一个数置于序列A′的顶端;

3)执行冒泡算法,搜索序列 A余下的数中满足S随机交织器限制条件的数,将其置于序列 A′的下端;

4)如果序列A中所有的数都置于序列A′中,则生成S随机交织器;否则,将序列A中余下的数置于序列A′的顶端,并转到步骤2)继续执行。

结合冒泡算法,我们的冒泡排序算法比较易于实现。图1所示为冒泡排序算法的一个示例,生成一个长度N=10、扩展参数s=2的S随机交织器。仿真结果显示,使用冒泡排序算法,中短长度的S随机交织器能够在几秒内生成;而对于更长一些的S随机交织器,可能需要执行更多次数的冒泡算法,但也能够在有限的时间(几小时)内生成。

4 S随机交织器的性能仿真

为检验Turbo码S随机交织器的性能,我们分别对长度为274bit和600bit的分组交织器、随机交织器和S随机交织器做了性能仿真,仿真结果如图2所示。仿真实验在AWGN信道、BPSK调制下进行。所选取的Turbo码分量码为(13,15)8,译码采用Log-MAP算法,迭代次数为10次。长度为274bit的S随机交织器的扩展参数s=11,长度为600bit的S随机交织器的扩展参数s=17。

由图2可以看出,采用分组交织器的Turbo码性能较差,表现出很明显的“误码平层”效应;采用随机交织器的Turbo码性能优于采用分组交织器的Turbo码,“误码平层”效应有所改善;而采用S随机交织器的T urbo码性能最优,在高信噪比区,与采用随机交织器的 Turbo码相比,有约0.2～0.3dB性能增益。

图2 交织器性能比较

5 结语

交织器的设计是Turbo码的核心技术之一,通过选取好的交织矩阵,可以提高Turbo码的自由距离,减小低重量码字个数,最大限度发挥交织器的作用。本文介绍了Turbo码交织器的设计准则,并详细介绍了其中的S随机交织器的基本原理,给出了S随机交织器的一种冒泡排序实现方法。仿真结果表明,所设计的S随机交织器性能优于分组交织器和随机交织器。

[1]C.Berrou,A.Glavieux,P.Thitimajshima.Near Shannon limit error-correcting coding and decoding:Turbo codest[C]//Inpron.1993 IEEE Int.Confon on Communication.Ceneva,Switzerland,1993:1064～1070

[2]J.Yuan,B.Vucetic,W.Feng.Combined Turbo Codes and Interleaver Design[C]//IEEE Transactions on Communications,1999,47:484～487

[3]H.R.Sajjadpour,Neil J.A.Saloane,Masoud Salehi,et al.Interleaver Design for Turbo Codes[C]//IEEE J.Select.Area comm.,2001,19(5):831～837

[4]苏鹤禄,蒋宇中.Turbo码交织器的设计[J].舰船电子工程,2006,26(1):157～160

[5]M.H.Alsuwaiyel.算法设计技巧与分析[M].吴伟,方世昌,等,译.北京:电子工业出版社,2004

Implementation of Turbo Codes S-Random Interleaver

Qian Hong1)Li Guangxia2)
(Postgraduate Team 4 ICE,PLAUST1),Nanjing 210007)
(Military Satellite Communication LAB ICE,PLAUST2),Nanjing 210007)

The design of interleaver in Turbo codes directly affects the performance of Turbo codes.Based on discussing the design rules and types of interleaver,the theory of s-random interleaver is particularly introduced.The implementation of s-random interleaver based on bubble sorting method is given.Simulation result shows that the performance of s-random interleaver is excellent for short to medium interleaver length.

Turbo codes,S-random interleaver,bubble sorting method

TN911.22

2010年9月18日,

2010年10月15日

国家自然科学基金项目(编号:60972061);国家“863”计划项目(编号:2008AA12A204)资助。

钱宏,男,硕士研究生,研究方向:卫星通信与卫星导航。李广侠,男,博士,博士生导师,研究方向:卫星通信与卫星导航。