（通信与信息系统专业论文）基于遗传算法的卷积turbo码译码算法研究.pdf

基于遗传算法的卷积t u r b o 码译码算法研究 专业：通信与信息系统 硕士生：张仕爽 指导教v i i i ：刘星成副教授 摘要 1 9 9 3 年由c b e r r o u 等人提出的t u r b o 码具有接近s h a n n o n 极限的性能。因此 t u r b o 码自提出起就成为信息论和编码理论界热切关注的焦点。目前t u r b o 码已经 成为第三代移动通信系统的标准之一。对t u r b o 码的研究主要集中在编码器、交 织器的设计及软输入、软输出迭代译码算法等方面。 t u r b o 码以高译码复杂度换取优异的性能。即使采用复杂度较低的软输出 v i t e r b i 算法( s o v a ，s o f t o u t p u tv i t e r b ia l g o r i t h m ) ，t u r b o 码译码的计算量仍随2 棚 ( 川为编码器存储长度) 增长。对于迭代译码，该计算量是相当大的。本文的主要 目的是利用遗传算法( g a ，g e n e t i ca l g o r i t h m ) 这一优化搜索工具实现迭代最大似 然译码，通过减小在格图上的搜索范围来降低计算量。在相似计算量的情况下， 获得比软输, q 4 m a ( s o m a ，s o f t o u t p u tm a l g o r i t h m ) 译码算法更好的性能。 本文首先研究了软输出v i t e r b i 译码算法、软输出m a 译码算法和遗传算法卷 积码译码算法的原理。在此基础上，提出适用于t u r b o 码的g a 分量码译码算法。 借鉴s o m a 译码算法中计算软输出的思想，提出了利用滑动窗口存储器来计算软 输出的方法，从而得到软输出g a ( s o g a ，s o f t o u t p u tg e n e t i ca l g o r i t h m ) 译码算法。 随后对t u r b o 码采用不同的译码算法的性能进行仿真。结果表明，所提出的s o g a 译码算法误比特率性能介于s o v a 算法和s o m a 算法之间。在计算量方面，s o g a 算法仅比s o m a 增加了少量运算。另外，s o g a 算法的在格图上搜索最优路径的 范围比s o v a 小，对应的计算量也比s o v a 小。因此s o g a 译码算法较好的实现了 中由夭学颁士学像论文 译码性能和复杂度的均衡。最后，本文对仿真结果进行了分析比较，并对全文做 了总结。 论文的主要研究工作包括以下几个方面： l 。首次在卷积t u r b o 码的译码过程中采用了遗传算法。在分析遗传算法用于 t u r b o 码译码时要解决的问题后，提魄相应的解决方案，并详细会绍了其 实现过程。另外，根据s o m a 译码算法计算软输出的思想，提如了利用 滑动窗口存储器的方法来实现该计算过程。 2 对s o g a 算法进行了实验仿真与性能分析。通过v c + 十6 0 仿真了该算法的 性能，从交织长度、迭代次数、搜索保留路径数和圈溯深度等方面对其 性能迸彳亍了考察与分析。结果表明，本文提出的软输出g a 迭代译码算法 可以获褥较好的误比特率( b e r , b i te r r o rr a t e ) 性能。本文的译码思想对 今愚的研究工作具有一定的参考价值。 关键词：t u r b o 码，软输出遗传算法( s o g a ，s o f t - o u t p u tg e n e t i ca l g o r i t h m ) ，译码 算法，误比特率 珏 s t u d yo ht h eg a b a s e dd e c o d i n ga l g o r i t h mf o r m a j o r ： n a m e ： c o n v o i u t i o n a lt u r b oc o d e s c o m m u n i c a t i o n sa n di n f o r m a t i o ns y s t e m z h a n gs h i s h u a n g s u p e r v i s o r ：a s s o c i a t ep r o f e s s o r l i ux i n g c h e n g a b s t r a c t t u r b oc o d e s ，w h i c hw e r ei n t r o d u c e db yb e r r o ue ta 1 i n19 9 3 ，p e r f o r ma tr a t e s e x t r e m e l yc l o s et ot h es h a n n o n sc h a n n e lc a p a c i t yl i m i t d u et o t h e i re x c e l l e n t p e r f o r m a n c e ，t u r b oc o d e sh a v ea t t r a c t e dc o n s i d e r a b l ei n t e r e s t ss i n c et h e i ri n t r o d u c t i o n i nc o d i n gt h e o r y n o w a d a y s ，t h e ya r ea d o p t e di nt h et h i r dg e n e r a t i o np a r t n e r s h i p p r o j e c t ( 3 g p p ) s t a n d a r d s r e s e a r c h e so nt u r b oc o d e sm a i n l yf o c u so nt h ed e s i g no f e n c o d e r s ，i n t e r l e a v e r s ，a n ds i s o ( s o f t i ns o f t o u t ) d e c o d i n ga l g o r i t h m s t u r b oc o d e so b t a i n o u t s t a n d i n gp e r f o r m a n c e a tt h e e x p e n s e o f h i g h c o m p u t a t i o n a lc o m p l e x i t y t h ed e c o d i n gc o m p l e x i t yg r o w sw i t h2 历( mr e f e r st ot h e c o n v o l u t i o n a le n c o d e r s m e m o r yl e n g t h ) e v e ni ft h es o f t - o u t p u tv i t e r b ia l g o r i t h m ( s o v a ) t h a th a sl e s sc o m p l e x i t yi su s e df o rd e c o d i n g t h ec o m p l e x i t yi sc o n s i d e r a b l e w h e ni t e r a t i v ed e c o d i n gs c h e m ei sa p p l i e d t h eg o a lo ft h i st h e s i si st or e a l i z e i t e r a t i v em a x i m u m l i k e l i h o o d ( m l ) d e c o d i n gu s i n gt h eg e n e t i ca l g o r i t h m ( g a ) i n t h i sw a y , w ec a nd e c r e a s et h ed e c o d i n gc o m p l e x i t yb e c a u s et h eg ao n l ye x t e n d s s e v e r a lp a t h sw h e ns e a r c h i n gf o rt h em l p a t ho v e rt h et r e l l i s w ea i m e dt oa c h i e v e b e t t e rp e r f o r m a n c et h a nt h a to ft h es o m a ( s o f t o u t p u tm a l g o r i t h m ) w i t ht h es i m i l a r c o m p l e x i t y i nt h i st h e s i s ，t h ed e c o d i n gp r i n c i p l ea n ds c h e m eo ft h es o f t o u t p u tv i t e r b i i i i 中山大学硕士学像论文 a l g o r i t h m ，t h es o f t o u t p u tm a l g o r i t h ma n dt h eg ad e c o d i n ga l g o r i t h ma r e d i s c u s s e d t h e n ，an e wd e c o d i n ga l g o r i t h mf o rc o n v o l u t i o n a lt u r b oc o d e s b a s e do nt h e g e n e t i ca l g o r i t h mt h a ti sc a l l e dt h es o f t - o u t p u tg e n e t i ca l g o r i t h m ( s o g a ) i s p r o p o s e d a n das c h e m ei nw h i c has l i d i n gw i n d o wi sa d o p t e dt oc a l c u l a t et h e s o f t - o u t p u ti n f o r m a t i o ni nt h es o g ad e c o d i n ga l g o r i t h mi si n t r o d u c e d 。s i m u l a t i o n r e s u l t ss h o wt h a tt h ep e r f o r m a n c eo ft h es o g ai sb e t w e e nt h a to ft h ec o n v e n t i o n a l s o v aa n dt h a to ft h es o m a i nt e r m so fc o m p l e x i t y ，f e wo p e r a t i o n sa r er e q u i r e dt o b ea d d e dt or e a l i z et h es o g ad e c o d i n ga l g o r i t h m ，c o m p a r e dw i t ht h es o m a b e s i d e s ，t h es e a r c hr a n g eo ft h es o g ai ss m a l l e rt h a nt h a to ft h es o v a t h a ti st o s a y ，o u rp r o p o s e ds o g ac a nm a k eag o o dt r a d e o f fb e t w e e nt h ed e c o d i n g p e r f o r m a n c e a n dc o m p l e x i t y l a s t l y ，a n a l y s e sa n dc o m p a r i s o n so fd i f f e r e n t a l g o r i t h m sa l ec a r r i e do u t 。 t h er e s e a r c hw o r ko ft h i st h e s i sm a i n l yi n c l u d e st h ef o l l o w i n gp a r t s ： 1 g e n e t i ca l g o r i t h mi sa d o p t e di nt u r b od e c o d i n gf o rt h ef i r s tt i m e a f t e r a n a l y z i n gt h ep r o b l e m si nt u r b od e c o d i n gw h e nu s i n gg a ，w ep r o p o s e ds o l u t i o n st oi t a n dd e s c r i b e di t si m p l e m e n t a t i o ni nd e t a i l b e s i d e s ，as c h e m ef o rc a l c u l a t i n gt h e s o f t - o u t p u ti n f o r m a t i o ni nt h es o g a i sp r o p o s e d 2 t h ep e r f o r m a n c eo ft h e p r o p o s e da l g o r i t h m ，s o g a ，o nt h ev c 一6 。0 p l a t f o r m ，i sa n a l y z e da n ds i m u l a t e d 。w ea n a l y z e dt h es o g a sp e r f o r m a n c eu n d e rt h e c o n d i t i o n so fd i f f e r e n ti n t e r l e a v i n gl e n g t h s ，i t e r a t i o nn u m b e r s ，p a t h ss a v e di ne v e r y s t e p ，t r a c e d b a c kd e p t h ，a n de t e t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e ds o g a c a na c h i e v eag o o db i te r r o rr a t e ( b e r ，b i te r r o rr a t e ) p e r f o r m a n c ea n di s b e n e f i c i a lt of u r t h e rr e s e a r c hw o r k k e yw o r d s ：t u r b oc o d e s ，s o f t - o u t p u tg e n e t i ca l g o r i t h m ( s o g a ) ，d e c o d i n g a l g o r i t h m ，b i te r r o rr a t e ( b e r ) 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均己在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：力时年歹月? 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：；锰竹爽 导师躲么1 日期：年月日日期：年月日 第1 章绪论 l 。l数字通信系统结构 通信的任务是传递信患，即通过传输媒介把信源产生的信息尽可能准确地传 送给信宿。传输信息的有效性和可靠性是通信系统最主要的质量指标。有效性是 指在给定信道内能传输的信患内容的多少，丽可靠性是指接收信息的准确程度。 如何提高通信的可靠性，降低数据传输的误码率是一直是数字通信系统设计中要 考虑的重要课题。 根据s h a n n o n ( 香农) 编码理论，数字通信系统的结构如图i i 所示【i j ： 图1 - 1数字通信系统结构 数字透信系统一般壹信源、发送设备、接收设备和信宿等部分组成。发送设 备包括信源编码、信道编码和调制等模块，其基本功能是将信源和传输媒介匹配 起来，即把信源产生的信息信号变换成为便于传输的信号形式。信源编码器是把 信源输出的信息变换成二进制形式信息序列m ，信源编码器根据传输的有效性进 行编码。信道编码器是将信源编码器输出的数字序列m 、映射到较长的二进制数 字序列c ，也就是人为地增加若干位，使其具有检错或纠错的能力。增加的位数 是根据信道出错情况或采用的编码方式来决定的。调制器是把信道编码器输出的 序列c ，变换成适合于媒质传输的信号波形h l 。 中山大学硕上学位论文 对应的，接收设备各模块的功能是实现与发送设备相反的变换，即进行解调、 译码、解密等，从接收到的带有干扰的信号中正确恢复出来自信源的信息。 由通信系统各模块的功能可知，在有限的信号功率、系统带宽和硬件复杂性 要求有限的条件下实现高效、可靠的通信，差错控制编码，即信道编码是最有效 的途径之一。差错控制编码的基本做法是在发送端待传输的信息序列上附加一些 监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联( 约束) 。 接收端按照既定的规则检验信息码元与监督码元之间的关系，一旦传输过程中发 生差错，信息码元与监督码元之间的关系将受到破坏，从而可以发现错误，乃至 纠正错测1 1 。在许多数字通信系统中，没有信道编码就不可能顺利地完成通信任 务。对特定的纠错编码方式，如何寻找译码错误概率小、译码速度快、设备简单 的译码算法，一直是纠错编码技术中的一个非常重要而又实际的问题。 1 2信道编码基本理论 1 9 4 8 年，美国b e l l 实验室的应用数学家c e s h a n n o n 在贝尔技术杂志上发 表了题为通信中的数学理论( am a t h e m a t i c a lt h e o r yo fc o m m u n i c a t i o n ) 的论文， 标志着信息与编码理论这一学科的创立【2 1 。在该文中，s h a n n o n 以概率论为基础， 给出三个定理和一个公式，即无失真信源编码定理、有扰离散信道的信道编码定 理、限失真信道编码定理及有扰信道容量的s h a n n o n 公式，奠定了信息论和纠错 编码理论的基础。 s h a n n o n 公式指出：对于有扰连续信道，假设噪声为加性高斯白噪声，噪声 功率为，且与信号独立。信号功率为s ，则该有扰连续信道的信道容量为【2 1 ： c = w l 0 9 2 ( i + s n ) b i t s 。( 1 - 1 ) 由香农公式可得如下结论【1 】： ( 1 ) 提高信号与噪声功率之比，即s n ，能增加信道容量。 ( 2 ) 当噪声功率_ + o 时，信道容量c 趋于，这意味着无干扰信道的容量 为无穷大。 ( 3 ) 增加信道带宽形并不能无限制地使信道容量增大。这是因为，当噪声 为高斯白噪声时，随着形增大，噪声功率n = w n o ( 这里d 为噪声的单 边功率谱密度) 也增大，在极限情况下： 2 第l 章绪论 l i m l i mw l 0 9 2 w - - * o ow - a o ( 1 + 南) 、 渺7 = 瓦s 旷l i m n8w-logzllm o g s ( 1 + 南) 。 ( 1 1 2 ) = 一 - l l + 一 o ll z n a w 一 、 n 秽一 、 _ t o 妒“4 4 番 ( 4 ) 信道容量c 一定时，带宽w 与信噪比s n 之间可以彼此互换。 信道编码定理指比：对于具有确定的信道容量c 的信道，对任何小于c 的 码率r ，存在有速率为r ，码长为，z 的分组码及( k o , 脚) 卷积码，若用最大似然 译码，则随着码长的增加其译码错误概率仇可以任意小器1 ，即 见4 9 一噶融， ( 1 3 ) 和 魏茎4 9 一酬璃磊鼬。( 1 4 ) 式( 1 - 3 ) 和( 1 4 ) 中，a b 和a c 为大于0 的系数，e b ( r ) 和髓( 霞) 为正实函数，称为误差 指数，它与r 、c 的关系如图1 - 2 所汞【3 】。豳中，c ，、c 2 先信遂容量，f t 6 。 嚣爱) 0 c 2c i r 图l - 2误差指数e 鼬与码率r 的关系 该定理告诉我们： ( 1 ) 在码长及发送信息速率定的情况下，为减小错误概率终，霹以增大信 道容量。错误概率随误差指数e 倒呈指数下降。 ( 2 ) 在信道容量及发送信息速率一定的条件下，增加码长，可以使错误概率 指数下降。从实际的角度来看，这时设备复杂性和译码延时也随之增加。 3 中山大学硕士学位论文 虽然信道编码定理仅仅是一个存在性定理，但它开创了信道编码理论这一富 有活力的研究领域。有噪信道编码定理从理论上给出了纠错码的理论极限，指出 了纠错码的研究方向。几十年来，纠错编码理论和实践的发展都是沿着两条主线 展开的，即构造码长，2 _ 的渐进好码，以及在可以接受的译码复杂度范围内实 现最大似然译码。 1 3常用的纠错码 按照对信息元处理方法的不同，纠错码可以分为分组码和卷积码两大类。 分组码是最早应用的信道编码技术。编码方式为：把信源输出的信息序列， 以k 个码元划分为一段，通过编码器把这段k 个信息元按一定的规则产生，个校 验元，输出长为，z = 脚的一个码组。每一码组的校验元仅与本组的信息元有关， 而与别组无关。分组码用( ，z ，助表示，n 表示码长，k 表示信息位。 线性分组码的校验元与信息元之间线性相关，是分组码中最重要的一类码。 纠错能力户l 的汉明码是r h a m m i n g 于1 9 5 0 年提出的分组码 4 1 ，也是第一个纠 错码，其码长n 和信息序列长度k 满足关系：n = 2 m 1 ，婷2 m m 1 ，最小距离靠加= 3 。 循环码是p r a n g e 于1 9 5 7 年提出的【引，它是线性分组码的一个重要子类。循 环码的外在特点是码字经循环移位仍然是码字，这一特点为循环码的编译实现带 来了便利。 b c h 码是于1 9 5 9 年由h o c q u e n g h e m 6 1 ，1 9 6 0 年由b o s e 和r a y c h a n d h a f i 研究组【7 1 分别提出的。b c h 码是纠错能力可控的纠随机差错码，是循环码的子类。 该码有严格的代数结构，生成多项式贴) 与最小距离d 有密切的关系，因此可以 根据对d 的要求，构造出具有预定纠错能力的码。另外b c h 码的编、译码电路 比较简单，易于工程实现，在中、短码长情况下的性能接近理论最佳值。因此， b c h 码不仅在编码理论上，具有重要地位，也是实际应用最广泛的码之一。1 9 6 0 年r e e d 和s o l o m o n 将b c h 码扩展到非二元( q 2 ) 得情况，得到了 r s ( r e e d s o l o m o n ) 硒j 哺j 。r s 码最大优点是其非二元特性可以纠正突发错误。 卷积码是e l i a s 等人在1 9 5 5 年提出的【叭。其编码方法是把信息源输出的信息 序列，以鳓个码元分为一段，通过编码器输出长为n d 一段的码段。不同于分组 码的是，该码段的 d 勃个校验元不仅与本组的信息元有关，而且也与其前m 段 4 第l 章绪论 的信息元有关，称脚为编码存储。卷积码用d ，玩小) 表示。正是由于在卷积码 的编码过程中，充分利用了各组之间的相关性，且锄和勃也较小，在与分组码 同样的码率和设备复杂性条件下，卷积码性能不比分组码差，而且实现最优和准 最优译码也比较容易实现，当编码存储m 较大时，可以得到较低的译码错误概 率。 1 9 9 3 年，c + b e 嚣o u 等在瑞士日内瓦召开的国际通信会议上提出了并行级联 卷积码( p c c c ) ，即t u r b o 码【l o j 。t u r b o 码的基本思想是迭代和交织，由于它充分 利用了s h a n n o n 信道编码定理中的随机性编码、译码条件，从而获得了接近 s h a n n o n 理论极限的优异性能。仿真结果表明，当既懈7 d b 时，码率为l 2 的t u r b o 码( 迭代次数1 8 次，交织器大小为2 5 6 2 5 6 = 6 5 5 3 6 ) ，在a w g n 信道 上的误比特率b e 髓l 伊5 ，这个结果与l 趁码率的香农限( 蛾= 0 d b ) 仅差0 7 d b 。 这一超乎寻常的优异性能，立即弓l 起信息与编码理论界的轰动。1 9 9 6 年，c 。b e 嚣o u 等人将他们的发现进一步整理总结，将文章发表在i e e e 会刊上【l 。 t u r b o 码巧妙地将卷积码和随机交织器结合在一起，在实现随机编码思想的 同时，通过交织器实现了由短码构造长码的方法，并采用软输出迭代译码来逼近 最大似然译码。t u r b o 码的提出，更新了编码理论研究中的一些概念和方法。现 在人们更喜欢基于概率的软判决译码方法，而不是早期基于代数的构造与译码方 法，而且入们对编码方案的比较方法也发生了交化，从以前靛相互毙较过渡到现 在的均与s h a n n o n 限进行比较。量蘸，t u r b o 码被看作信道编码理论与技术研究 上重要的里程碑之一【1 2 】。 1 4t u r b o 码的研究现状 t u r b o 码自提出以来就是信道编码领域热切关注的焦点，许多国家的学者都 围绕t u r b o 码作了大量的研究，并取得了一些进展。总体来说，目前t u r b o 码的 研究主要集中在t u r b o 码设计、译码技术以及t u r b o 码在通信系统中的应用等方 面。 1 4 1t u r b o 码的设计 t u r b o 码由分量码编码器和交织器级联而成，分量码和交织器设计的好坏是 5 中山大学硕士学位论文 决定t u r b o 码性能的关键因素。分量码的不同主要体现在码字类型和结构上，而 交织器的设计的研究主要集中在交织算法和优化等方面。 t u r b o 码的分量码可以是卷积码或分组码。c b e r r o u 等人最早提出以卷积码 为分量码的卷积t u r b o 码( c t c s ，c o n v o l u t i o n a lt u r b oc o d e s ) ，或称为t u r b o 卷积 码( t c c s t u r b oc o n v o l u t i o n a lc o d e s ) 1 0 l 【l l 】。p y n d i a h 提出以分组码作为分量码的 t u r b o 码，即分组t u r b o 码( b t c s ，b l o c kt u r b oc o d e s ) ，或称t u r b o 乘积码( t p c s ， t u r b op r o d u c tc o d e s ) ，并推导出分组t u r b o 码的外信息计算公式，实现了迭代译 码【l3 1 。所有线性分组码都可以作为分组t u r b o 码的分量码，且分组t u r b o 码编码 器不需要交织器，对分量码进行行、列编码后级联即得到编码输出。分组t u r b o 码编码结构简单，容易实现，而且比卷积t u r b o 具有更低的错误平底，因此分组 t u r b o 码自提出后也成为一个研究热点。 传统的t u r b o 码分量码以系统码为主，a 。b a n e r j e e 等人则介绍了非系统t u r b o 码的结构，并从性能、码字有效自由距离等方面与常用的系统码进行分析比较， 证明了非系统t u r b o 码比传统的系统码具有更低的错误平底【i 引。 t u r b o 码编码器另一个重要组成部分是交织器，也是t u r b o 码的特征之一。其 作用是通过改变输入信息的位置，提高低重序列的输出码重，减小译码输出比特 之间的相关性。t u r b o 码中常用的交织器有分组交织器和随机交织器两大类。s b e n e d e t t o 等人首次提出了均匀交织器( u n i f o r mi n t e r l e a v e r l 的概念【1 5 1 。m l a d d o m a d a 等人提出伪随机、可修剪的交织器设计方案，采用迭代的方式使交织 器长度从较小增长到能够满足需求的长度，通过使用结合外信息相关性和交织 器扩展的概念构造的代价函数实现交织器优化【l 引。j b o u t r o s 等人提出一种适用 于并行结构的准循环交织器，与传统的随机交织器相比，准循环交织器对于短分 组t u r b o 码需要的存储量少，并且能够取得较低的误比特率【1 7 i 。m “卿n m s h e i k h 讨论了结合随机化和去相关原则设计的确定性交织器的原理及性能，这种 交织器按照确定的规则对信息进行置换，确保能够扩大分量码码字之间的最小距 离【1 引。 1 4 2t u r b o 码译码技术 t u r b o 码译码算法总体上可以分为两大类，最大后验_ 枵5 率( m a p ，m a x i m u ma 6 第1 章绪论 p o s t e f i o f i ) 类和软输出维特比( s o v a ) 类算法。其中m a p 算法是一种最佳最大后验 概率算法，是目前所有算法中b e r 性能最好，也是译码复杂度最高、计算量最大 的译码算法【l o j f l l l 。针对m a p 算法的缺点，很多简化算法都被相继提出。l o g m a p 算法是m a p 算法的对数形式，将大量的乘法运算转化成加法来简化复杂性嘲。 通过对l o g m a p 算法中分支度量计算的简化，黼l j m a x l o g m a p 算法四l 。 s o v a 算法是在维特比算法【2 1 1 基础上进行修芷，使其具有提供软判决输出和 利用外部信息能力的一种算法【2 2 l 【2 3 】。s o v a 算法计算简单，存储量小，易于硬件 实现。但算法的简化、复杂度的降低和寄存器数量的减少一般是以降低译码性能 为代价换取的，因此s o v a 算法提出以后，不少学者致力于提高其译码性能。j c h e n 等提出双向s o v a 译码算法，可以获得接近m a x l o g m a p 算法的性能强引。 yc h a n g 等入提出带缩放因子的双向s o v r a ，得到比m a x l o g m a p 算法更好的译 码性缝，并从译码复杂度方葱将这两种算法进行比较【2 熨。 舅前对译码算法的研究中不仅有对传统算法的改进，也有新的译码思想提 出。s p a p a h a r a l a b o s 等人提出基于m a x l o g m a p 和l o g m a p 算法的s i s o 译码算 法，计算软输出时在不同的可靠性等级情况下采用不同的计算方法，实现译码性 能和复杂度的折衷【2 6 l 。f j i a n g 把t u r b o 码看作串行链接码，得出t u r b o 码得生成矩 阵和校验矩阵，并提出一种基于低密度校验矩阵的和积( s u m p r o d u c t ) t u r b o 码译 鹃算法嗣。 在不同的信道下，t u r b o 码译码算法的实现过程、误比特率性能等都会有所 不同。因此，很多研究工作者针对不同的信道提出相应的译码方案。x 。l i u 等人 提出了t u r b o 码在非对称z 信道上的最大后验概率( m a p ) 译码算法，与其它编译码 系统相比，该译码算法可以获得很好的b e r 性能【2 8 l 。i c h a t z g e o r g i o u 等人研究了 有天线差异和无天线差异的准静态衰落信道下的t u r b o 码性能，比较了相同译码 复杂度情况下的t u r b o 码和卷积码的在这两种信道下的误比特率f 揪。 1 4 3t u r b o 码的应用 由于t u r b o 码性能优越，尤其是低信嗓比下的优晃性能使t u r b o 码在许多通信 系统中的应用都有巨大的潜力。t u r b o 码不仅是一种性能优越的编码方法，其交 织、迭代思想被众多通信系统采用。例如t u r b o 码与调制结合、t u r b o 码与a r q 7 中山大学硕士学位论文 的结合、t u r b o 多用户检测以及t u r b o 均衡器等技术【3 0 l ，t u r b o 码与o f d m 调制、 差分检测技术相结合，具有较高的频率利用率，可有效地抑制短波信道中多径时 延、频率选择性衰落、人为干扰与噪声带来的不利影响。 t u r b o 码的优异性能，使其在与调制系统的结合方面也有很大的吸引力。利 用t c m 技术可以在不增加系统带宽要求的条件下有效地提高编码增益。将t u r b o 码与t c m 相结合来实现高增益高频谱效率的编码调制方案称为t - t c m 。yz h u 等人提出的针对特定噪声的a w g n 信道下t u r b o 码与编码调制技术相结合的方 案，不仅得到了优异的性能，而且还有较低的译码复杂度p 1 1 。e r o s n e s 等人设计 了一种基于位交织的t u r b o 码调制系统，该系统具有较低错误平底( e r r o rf l o o r ) ， 与传统的随机位交织器调制系统相比，在不同的噪声区域有相似甚至更好的性能 3 2 1 o 在无线移动通信领域，结合不同的系统，t u r b o 码也得到了广泛的应用。f c h i t i 等人将t u r b o 码与超宽带无线网络结合，提出适用于t h u w b 系统的删余跳 频c d m a 调制方式，与采用全速率t u r b o 码系统相比，不仅保持了原有的网络吞 吐量，而且也得到了较好的误比特性能p 3 1 。n o h k u b o 等人对用于进化的u m t s 陆地无线接入系统( e u t r a ，e v o l v e du t r ad o w n l i n ko f d mr a d i oa c c e s s ) 中的 t u r b o 码和l d p c 码编码方式作详细的分析，从误包率、译码复杂度等方面将两种 编码方式进行比较，并得出结论：在e u t r a 中t u r b o 码i ：匕l d p c 码更有前途【3 4 1 。 1 5遗传算法简介 遗传算法( g a ，g e n e t i ca l g o r i t h m ) 是一种基于达尔文进化论和孟德尔的遗传 学说，模拟自然选择过程的随机优化搜索方法。美i 垂i m i c h i g a n 大学的h o l l a n d 教授 及其他科学家分别独立地通过对自然和人工系统的研究，提出了遗传算法的思想 基础。1 9 7 5 年h o l l a n d 出版y a d a p t a t i o ni nn a t u r ea n d a r t i f i c i a ls y s t e m s ，标志着遗 传算法的正式诞生【3 5 l 。在此基础上d g o l d b e r g 对遗传算法用于优化、搜索和机器 学习等进行了深入的探讨【3 6 1 。 g a 优化搜索过程中，首先随机产生若干个个体作为初始群体，个体通过遗 传算子产生新的后代，用个体的适应度来表示个体的生存能力，即适应环境的能 力。再通过选择算子对个体进行评价，决定保留或淘汰它们。同时，遗传算法采 8 第1 章绪论 用类似于人类婚姻的交叉算子产生新个体，对个体中染色体的倒位、突变操作模 仿自然界中的变异过程。通过对群体的不断进化，利用“优胜劣汰的自然选择 机制，使群体中的个体收敛到一个最适应环境的个体上，最终找到问题的最优解。 作为复杂系统的一种优化搜索工具，遗传算法已经在数学函数优化、机器学 习、模式聚类、参数估计等领域获得了广泛的应用。 1 6本文研究意义和创新点 1 6 1 研究意义 芷如前文所述，t u r b o 码具有接近s h a n n o n 理论极限的优异性能，尤其在低 信噪比下的卓越表现，使其在许多通信系统中都有非常大的应用潜力。除了在深 空通信、卫星通信以及多媒体通信等领域的应用以外，t u r b o 码已经成为第三代 移动通信系统的标准之一。 现有的t u r b o 码软输出译码算法虽然误比特率性能优雾，僵在计算量和译码 复杂度方蘸仍不尽人意，这大大限制了t u r b o 码在实际逶信系统中的应用。如何 能在保持t u r b o 码优异性能的前提下降低译码计算量和复杂度，是研究t u r b o 码 软输出译码算法的热点之一。 遗传算法作为一种具有隐含并行性的搜索算法，目前已经广泛应用于生物、 化学和机械等领域的系统优化。在纠错码领域，已有将遗传算法用于分组码阳f 3 s l 和卷积码湖i 4 0 1 的译码，码字设计方面可以利用g a 这优化搜索工具进行t u r b o 分量码刚和t c m 码的搜索吲。如果能将这种基于全褥优化的人工智能工具和性 能优异的t u r b o 码译码结合起来，将会有利予t u r b o 码译码性能的提高，弗降低 译码计算量。 1 6 2 创新点 针对传统的t u r b o 码译码算法存在的缺陷，本文以降低s o v a 译码计算量，获 得比s o m a 译码算法更好的译码性t 月- q 匕a 为目的，尝试将基于全局优化搜索的遗传算 法应用到卷积t u r b o 码译码中来。对遗传算法用于最优路径搜索过程中非常关键 的选择操作进行分析，提出了软输童g a ( s o g a ) 译码算法。该算法中的两个g a 9 中山大学硕上学位论文 分量译码器按照适者生存、优胜劣汰的原则，实现在格图上最佳路径的搜索。在 此基础上借鉴s o m a ( s o f t o u t p u tm a l g o r i t h m ) 中的软输出计算思想，提出一种利 用滑动窗口存储器的方法来计算软输出信息，为另一个分量码译码器提供先验信 息，实现软输出迭代译码。 g a 路径选择的范疆l i 己v a 算法中的小，又能通过模仿生物界进化法则进行最 优化搜索。因此，s o g a 译码算法不仅可以降低译码复杂度和计算量，还能保证 t u r b o 码的性能降低较小。此外以适当的原则丢弃一些路径意味着s o g a 具有一定 的自适应性，即可以通过信道估计策略实时调整每一轮进化需要保留的个体数。 这些都是软输出g a 译码算法的优势所在。本文在最后对影响s o g a 译码性能的 参数做了细致的讨论，并在此基础上通过仿真验证这些参数对t u r b o 码s o g a 译码 性能的影响，同时把所提出的s o g a 译码算法与s o v a 、s o m a 算法从误比特率 性能、译码计算量等方瑟进行毙较。仿真结果证明，将遗传算法孳| 入t u r b o 码译 码是可行恧且是有效的。 1 7课题来源 ( 1 ) 广东省科技计划项墨( t h es c i e n c ea n dt e c h n o l o g yp l a no fg u a n g d o n g p r o v i n c eo f c h i n an o 2 0 0 6 8 5 0 l o l 0 0 3 1 。 ( 2 ) 广州市科技计划项( t h es c i e n c ea n dt e c h n o l o g yp l a no fg u a n g z h o uc i t y n o 2 0 0 7 2 3 一d 0 0 7 1 ) o 1 8文章内容安排 第l 章即本章，介绍了数字通信系统的基本结构和各模块的功能，讨论了信道 编码理论的基本定理，简单分析了几种常用的纠错码原理及特点，对 t u r b o 码的研究和应用现状、遗传算法的原理进行篱萃概括。最看说明本 文的选题意义和研究目的。 第2 章从有噪信道编码定理出发，介绍了t u r b o 码编译码器的结构，简单阐述了 t u r b o 码取得优异性能的内在机理。接着讨论了编码器结构中的分量码、 交织器等关键组成部分的设计原则和工作原理。最后介绍t t u r b o 码常用 的软输入软输出译码算法，并总结了这些算法的优缺点。 l o 第1 章绪论 第3 章分析了利用g a 进行卷积码译码的原理，推导并提出适用予a w g n 信道下 t u r b o 码译码的软输出g a 译码算法，介绍了软输出及外信息的计算方法， 并对s o g a 的译码实现过程进行详细说明。 第4 章性能仿真，讨论采用不同译码算法的t u r b o 码性能，及参数的选择对s o o a 译码性能的影响，如分量码的选择、交织长度、迭代次数、回溯深度等。 仿真结果表明，所提出的s o g a 迭代译码算法能够获得比s o m a 更低的误 比特率。而且与s o v a 算法相比，s o g a 译码算法性能降低很小。 第5 章概括了本文的主要工作和研究结果，并指出进一步研究的方