（通信与信息系统专业论文）基于bch码改进查找表译码算法的tpc编译码技术研究.pdf

基于b c h 码改进奄找表译码算法的t p c 编译码技术研究 i i 捅要 差错控制编码( 也称为信道编码或纠错码) 是一种提高数据传输可靠性的技术，广 泛应用于各种通信及计算机系统中。在众多差错控制编码中，t l l 舢乘积码( t p c ) 因 具有相对简单的编译码方法和接近香农限的纠错能力，已经成为信道编码领域的研究热 点，具有广泛的应用前景。但是t l l 舢乘积码译码仍然存在计算量大、资源占用较多等 问题，其中主要因素在于其子码译码器的复杂度。所以本文重点在于如何降低t u r b o 乘 积码子码译码器的复杂度和译码时间，进而达到提高t l l f b 0 乘积码译码速度的目的。 首先，本文概述了信道编码的发展历史，并概括性介绍了t p c 常用的子码- b c h 码的研究现状，以及t p c 编译码所涉及的基础知识。 其次，深入研究了b c h 码的译码方法，基于查找表译码方法提出了一种二进制b c h 码改进查找表算法。该算法在查找表中仅存储b c h 码信息位发生任意可纠正错误时的 错误图样和对应的伴随式图样，利用查找表和伴随式的汉明重量判决码字的错误位置， 从而极大地降低了译码复杂度，减少了资源损耗。对( 1 5 ，5 ，7 ) b c h 码的m a t l a b 仿 真结果表明，改进查找表译码算法比传统查找表算法译码速度提高了约1 5 8 ，较好地 平衡了译码速度与译码资源之间的关系；在q 瑚r t l l si i 环境下对同一码型采用改进查找 表算法进行译码的f p g a 仿真结果表明，在系统时钟为5 0 m h z 时，可在2 个时钟内完 成译码。 一 最后，在深入研究基于c l l a s e 算法的t l l 椭乘积码迭代译码方法的基本原理、译码 过程、软信息计算和迭代结构的基础上，以( 3 1 ，2 1 ，5 ) b c h 码作为t u r b 0 乘积码的子码， 将提出的b c h 码改进查找表算法引入t l l 舭乘积码的迭代译码中，在m a = r i ，a b 7 0 环 境下分别对基于c 1 1 a s e 算法的t p c 迭代译码算法和传统硬迭代译码算法进行了仿真实 验，分析了不同参数设置下的实验结果，并对子码分别采用传统查找表算法和改进查找 表算法时的p c 迭代译码速度进行了仿真实验。实验结果表明，在b e r = 1 0 巧时，基于 c l 粥e 算法的t p c 迭代译码算法可比传统硬迭代译码算法提高约2 7 d b 的增益，在误帧 率性能上，前者也明显好于后者；用本文提出的b c h 码改进查找表算法对子码译码， 不仅可以节省子码译码器的资源消耗，还可大幅提高t u r b o 乘积码的译码速度。 关键词：t l l 乘积码；b c h 码；查找表算法；c l 啪e 算法：迭代译码 基于b c h 码改进究找表译码算法的t p c 编译码技术研究 a b s t r a c t e r r o rc o n t r o lc o d i n g ( i e c h a n n e l - c o d i n g ，e c c ) i sat e c h n o l o g yt oe n h a n c et h e r e l i a b i l i t yo ft h ed a t at r a n s m i s s i o n , w h i c hi sw i d e l ya p p l i e di nv a r i o u sc o m m u n i c a t i o na n d c o m p u t e rs y s t e m i nv a r i o u sc h a n n e lc o d i n gt e c h n o l o g y , t h et u r b op r o d u c tc o d e ( t p c ) h a s b e c o m et h ef o c u si nt h ee c cf i e l da n dh a sa v e r yb r o a da p p l i c a t i o np r o s p e c tw h i c hd u e st oi t s r e l a t i v e l ys i m p l ec o d i n ga n dd e c o d i n gm e t h o da n de r r o rc o r r e c t i o na b i l i t yn g a rt h es h a n n o n l i m i t b u tt h e r ea r es t i l ls o m ep r o b l e m s ，s u c ha sh i g hc o m p l e x i t y , l a r g ed e l a ya n dal a r g e a m o u n to fm e m o r yr e q u i r e m e n t si nt h ed e c o d i n go ft h et p c ，w h i c hi sm a i n l yd e p e n d e n to n t h ed e c o d i n gc o m p l e x i t yo ft h ec o m p o n e n t - c o d ed e c o d e r t h e r e f o r e ，t h i st h e s i sf o c u s e so n h o wt or e d u c et h ec o m p l e x i t ya n dd e l a yo fc o m p o n e n t - c o d ed e c o d e r st oi m p r o v et h ed e c o d i n g s p e e do ft p c f i r s t l y , a no v e r v i e wo fd e v e l o p m e n th i s t o r y o fe e ci s i n t r o d u c e d ，a n dt h e nt h e d e v e l o p m e n to fb c h a n dt h eb a s i ck n o w l e d g eo ft p ca l es u m m a r i z e d s e c o n d l y ，t h ed e c o d i n ga l g o r i t h m so ft h eb c hc o d ew h i c hi sc o m m o n l yu s e da st h e c o m p o n e n t c o d e so ft h et p c ，a r ed e e p l yr e s e a r c h e d , a n daf a s td e c o d i n ga l g o r i t h mo ft h e b i n a r yb c h c o d ei sp r o p o s e db a s e do l ll o o k u pt a l b em e t h o d t h ed a t ai nt h el o o k u pt a b l e c o n s i s t so fs y n d r o m ep a t t e r n sa n dc o r r e s p o n d i n ge r r o rp a t t e r n sw h i c ho n l yo c c u r ei nt h e m e s s a g eb l o c ko ft h er e c e i v e de o d e w o r d t h ep r o p o s e da l g o r i t h mm a k e su s eo ft h el o o k u p t a b l ea n dt h ew e i g h to fs y n & o m e s i to f t e nr e s u l t si nas i g n i f i c a n tr e d u c t i o ni nt h em e m o r y r e q u i r e m e n t sa n dl o w e rc o m p l e x i t yc o m p a r i n gw i t ht h et r a d i t i o n a ll o o k u pt a b l eo ro t h e r a l g e b r a i cd e c o d i n gm e t h o d s m o r e o v e r , t h es i m u l a t i o no f ( 15 ，5 ，7 ) b c hc o d eb a s e do n m a t l a bs o f t w a r es h o w st h a ts u c han o v e lm e t h o dc a ni n c r e a s ea b o u t15 8 d e c o d es p e e d c o m p a r i n gw i t ht h et r a d i t i o n a lf u l ll o o k u pt a b l es e a r c h i n ga l g o r i t h m ，w h i c hi n d i c a t e st h a tt h e p r o p o s e da l g o r i t h mi sag o o dt r a d e o f fb e t w e e nm e m o r yr e q u i r e m e n t sa n dd e c o d et i m e t h e i m p r o v e dd e c o d i n ga l g o r i t h mi ss i m u l a t e do n ( 15 ，5 ，7 ) b c hc o d eu n d e rq u a r t u si i ，t h e f p g as i m u l a t i o ns h o w st h a tt h ed e c o d i n gp r o c e s sc a nb ea c c o m p l i s h e di nt w oc l o c k sw h e n t h es y s t e mc l o c ki s5 0 m h z l a s t l y , t h eb a s i cp r i n c i p l eo ft p ci t e r a t i v ed e c o d i n ga l g o r i t h mb a s e do nt h ec h a s e a l g o r i t h m ，a n dt h eb a s i cs t e p so ft h ei m p l e m e n t a t i o no ft h i sd e c o d i n ga l g o r i t h ma r eg i v e n a n dt h e n , t h ec a l c u l a t i o no ft h ee x t r i n s i ci n f o r m a t i o n sa n dt h ei t e r a t i v es t r u c t u r eo ft h i s 哈尔滨_ t 程大学硕+ 学位论文 a l g o r i t h ma r ed i s c u s s e d o nt h e s eb a s e s ，t a k e ( 31 ，21 ，5 ) b c hc o d ea st h ec o m p o n e n t - c o d e s ， t h ep r o p o s e da l g o r i t h mi si n t r o d u c e di n t ot h ei t e r a t i v ed e c o d i n go ft p c 硼1 em a r l a b s i m u l a t i o ns h o w st h a tt h et p ci t e r a t i v es o f t - d e c i s i o nd e c o d i n ga l g o r i t h mb a s e do nt h ec h a s e a l g o r i t h mc a ne n h a n c ea2 7 d bg a i nc o m p a r i n gw i t ht h et r a d i t i o n a li t e r a t i v eh a r d - d e c i s i o n d e c o d i n ga l g o r i t h mw i t h10 。b e ra n di nt h ep e r f o r m a n c eo ff r a m ee r r o rr a t e ，t h ef o r m e ri s m u c hb e t t e rt h a nt h el a t e r i ti sc o n c l u d e dt h a tt h ep r o p o s e da l g o r i t h mc a nn o to n l yr e d u c et h e m e m o r yr e q u i r e m e n t so ft h ec o m p o n e n t - c o d ed e c o d e r s ，b u ta l s oi m p r o v et h ed e c o d i n gs p e e d o ft p cg r e a t l y k e y w o r d s ：t u r b op r o d u c tc o d e ；b c hc o d e ；l o o k u pt a b l ed e c o d i n g a l g o r i t h m ；c h a s e a l g o r i t h m ；i t e r a t i v ed e c o d i n g 第1 章绪论 第1 章绪论 1 1 课题研究的目的、背景及意义 近年来，随着通信与信息技术、计算机技术的发展，人们对高效可靠的数字传输和 存储系统的需求日益增长，这种需求随着面向数字信息的交换、处理和存储的大规模高 速数据网的出现而变得更加迫切i t 】。因此，在进行系统设计时，采用一个好的差错控制 编码( 也称信道编码或纠错码) 对系统差错进行控制，是系统设计师必须考虑的一个重 要问题。采用信道编码的数字通信系统的原理框图如图1 1 所示。 图1 1 数字通信系统模型 图中，信源( 可以是人或计算机等信息发送端) 将语音、图像或数字序列经过信源 编码器转换成二进制( 或多进制) 形式的信息序列，并将其中与有用信息无关的冗余删 除，以提高信息传输的有效性。而信道编码器为了使信息在传输过程中抵抗各种干扰和 噪声，则故意加入一些冗余，以提高信息序列的相关性和规律性，使其获得自动检错或 纠错能力。调制器将这些信息序列转换成适合信道传输的信号，经有噪信道传输送达接 收端，经解调器解调后输出二进制( 或多进制) 的信息序列，由于受到噪声或干扰的影 响，信息序列存在失真，与原始发送的序列相比，存在差错，而信道译码器则利用信道 编码赋予信息序列的规律性和相关性，采用有效的译码方法纠正失真序列中的差错，再 经过信源译码器还原为发送端发送的原始信息序列，送达信宿( 接收端) 2 1 。 由于信道编码通过适当增加冗余，提高了系统的可靠性，从而可以节省因抵抗噪声 和干扰而额外消耗的功率资源，提高系统整体的效益，因而在许多数字传输系统中得到 了广泛应用。例如，深空信道由于传输距离遥远而使信号衰减严重，信噪比低，但其频 带资源丰富，采用高效的信道编码就可以使系统功率资源要求更低，发射设备体积更小， 降低系统成本，同时意味着空间平台可以飞行更远【3 】。在光纤通信中，采用前向纠错编 哈尔滨t 程大学硕十学位论文 码技术( f e c ) ，在获得较低的通信系统误码率的同时，不但可以放宽对高速通信系统 器件的性能要求，降低系统成本，而且可以提高系统对非线性效应、色散、q 值和光信 噪比( o s n r ) 的容忍度，有利于信号的高速率、长距离传输【4 】。移动通信信道存在多径 效应、多普勒频移和阴影效应，信号容易产生快衰落，码间干扰和失真严重，信噪比低， 通过采用信道编码、多址技术、分集技术等关键技术，可以极大提高通信质量，降低终 端的体积和功率损耗，如英国的模拟蜂窝移动通信中的b c h 码；g s m 系统中应用的 b c h 编码、f i r e 编码、c r c 编码；还有3 g 移动通信中的t u r b o 码方案【5 】，以及预计在 4 g 移动通信中应用的l d p c 码等【6 】，都是纠错码在移动通信中的成功应用。此外，信道 编码技术还广泛应用于数字广播电视系统 t l 、靶场遥测系统【s 】、全息数据存储系统【，l 等领 域。由此可见，研究信道编码技术，对提高通信系统的整体性能具有十分重要的意义。 1 2 信道编译码的国内外研究现状 1 2 1 信道编码的起源， 信道编码的起源可以追溯到1 9 4 8 年香农( c l a u d ee 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 ) ( 通信的 数学理论) 【t o 】。在这篇论文中，香农提出了信道编码定理，为在通信系统中实现高效 可靠的信息传输奠定了理论基础，并由此开创了信息论这门新学科。香农信道编码定理 指出：每个离散无记忆信道都有一个非负数c ( 称之为信道容量) 与之相联系，并具有 以下性质：对于任意给定的s 0 和r 9 。、x7 1 2 图2 1 二维乘积码构造原理图 具体编码过程按以下步骤进行： ( 1 ) 将( 毛乞) 个未编码信息比特放入毛行、恕列的矩阵中； 9 哈尔滨t 程大学硕士学位论文 ( 2 ) 用c z 码的编码规则对毛行未编码信息比特进行编码，得到大小为( 毛惕) 的矩 阵，其中右边的( 毛，坞一乞) 码块中的各行分别对应为左边的局行未编码信息比特的校验 位，称为行校验位； ( 3 ) 用g 码的编码规则对坞列未编码信息比特进行编码，得到大小为( 毛坞) 的矩 阵，其中码块( 一墨，如) 中的各列分别对应上边乞列未编码信息比特的校验位，称为列 校验位；右下角的( 一局，惕一岛) 码块为第( 2 ) 步骤中得到的行校验位的列校验位，称 为校验位的校验位 由此就可以得到由c t ( 以，k l ，d ) 、c ：( 刀2 ，k 2 ，d ：) 编码构成的乘积码尸( 行，k ，d ) ，通常用 ，l r 尸= c loc 2 表示，其参数刀= 啊xn 2 ，k = 毛如，d = 儡畋，其码率为r = 墨马= 业， ，z lx 伤 其中墨、咫分别为分组码c ，、c ：的码率o s l 0 9 1 。通过这种编码方式，将最小汉明距离小 的短码c l ( n ，k l ，d 1 ) 、c ；( n 2 ，k 2 ，d ：) 构造成了最小距离大的长码，码块中所有，z l 行都是c 的 码字，所有列都是c 的码字，因此，乘积码p 也可视为一种串行级联分组码，即外 码c 2 ，内码c l ，通过交织器长度为l = ，z 毛的分组交织器( 即行列互换型交织器) 进 行串行级联后即可得到乘积码p 【4 2 】，如图2 2 所示。 图2 2 二维乘积码编码器框图 一 上述编码过程是按先对行编码，后对列编码来构成乘积码，实际上也可以按先对列 编码，后对行编码来构成乘积码，这两种编码次序得到的乘积码结果相邴钉i 。这里我们 以两个( 7 ，4 ) 汉明码作为子码，举例说明乘积码的编码过程，( 7 x 4 ) x ( 7 x 4 ) 的编码矩阵 如图2 3 所示，其中 m ) 表示信息比特， p ) 表示对应的校验比特，下标i ，歹分别表示行、 列数。 ，啊1毛1打与1见l见l 打气2 见zp n 刀 如如 打 珥p s 4鼬 a ，p u岛5凡见，几 a 氏氏儿氏死 a 7p 打马7见7踟p r r踟 图2 3 ( 7 4 ) ( 7 x 4 ) 乘积码编码矩阵示意图 1 0 第2 章t u r b o 乘积码编译码理论基础 若以先行后列编码为例，行编码器按( 7 x 4 ) 汉明码的编码规则对首行信息比特 ( 铂。，他l ，鸭。，。) 进行编码，计算出其对应的校验冗余比特( 既l ，风l ，岛。) 并添加在 ( 铂，鸭。，鸭。，弛。) 右侧，行编码器接着转向下一行进行同样的编码过程，直到完成第4 行信息比特，即( 铂。，鸭。，) 的编码，从而形成( 4 7 ) 的矩阵；然后列编码器也按 ( 7 4 ) 汉明码的编码规则对首列信息比特( ，l l ，铂：，确。) 进行编码，计算出对应的校验 冗余比特( a ，a 。，a ，) 并添加在信息比特( 。，：，嘲；，确。) 的下面，列编码器接着转向下 一列进行同样的编码过程，当完成第4 列信息比特的编码后，列编码器继续对右边的三 列行校验位依次编码得到校验位的校验位，最终完成乘积码的编码。此码块在信道中传 输时，将按照，z 1 1 ，鸭l ，m s l ，m 4 1 ，p 5 l ，风l ，p 7 l ，2 ，p 7 7 的顺序串行发送，在接收端，译 码器将接收的串行序列依旧按照上述方法排列，转换为二维矩阵，再根据矩阵结构来译 码。乘积码通常会采用结构简单的系统码进行编码，而译码通常采用先行后列译码，所 以其译码复杂程度只随其子码的译码复杂程度线性增加【：刀。 由二维乘积码的构造原理类推，我们可以得到三维乘积码p = c 10c 2oc 3 的构造原 理如图2 4 所示1 4 4 1 。 y r 。， i 图2 4 三维t p c 的构造原理图 三维乘积码的编码步骤为： ( 1 ) 将( 局k s 毛) 个未编码信息比特放入一个三维空间，其中彳方向毛比特，l ，方 向岛比特、z 方向厩比特； ， ( 1 ) 在三维空间中表示z = 0 的那个平面内用c l ( n ，k l ，d 1 ) 沿x 方向对七2 行信息比 特编码，形成( 乞，惕) 二维码块； ( 2 ) 在z = 0 的平面内用c z ( 栉：，k 2 ，d ：) 沿j ，方向对( 乞，啊) 二维码块的伤列进行列编 码，形成( n 2 ，r 6 ) 二维码块，完成z = 0 平面的二维编码； 哈尔滨t 程大学硕十学位论文 ( 3 ) 分别在z = l ，( 毛一1 ) 这( 毛- 1 ) 个二维平面内重复步骤( 1 ) 步骤( 2 ) ，完 成各个面内的二维编码； ( 4 ) 沿z 方向用c 3 ( n 3 ，k 3 ，d ，) 对步骤( 3 ) 形成的毛个二维乘积码进行第三维编码。 与二维乘积码类似，三维乘积码参数为：力= 1 1 1 力：吃，k = 毛k ，x 颤， d = 面吐以，r = r 。xr 2xr 3 。依此类推可以得到维乘积码，从实现复杂度上考虑， 本文只针对二维乘积码展开研究。 从乘积码的构造原理可以看出，当乘积码使用不同长度的子码时，可以得到不同码 率的乘积码。此外，还可以根据设计要求对码块部分行列或部分比特进行删除处理( 也 称作截短) ，以获得所需码率的乘积码。这种子码选择和截短处理的灵活性使得乘积码 译码器可以支持较宽的码率范围，即使在信道条件比较差的情况下，也可以通过适当降 低码率来获得较高的误比特率性能，因此，更容易设计出符合要求的码。此外，它还可 以实现多个不同码率的信道复用一个译码器，降低系统成本1 1 2 。 2 2 2 乘积码的纠错能力 由乘积码的构造原理可知，行列交织编码结构使得乘积码既可以纠随机错误，又可 以纠突发错误，因为这种行列交织结构使得它能将突发错误打乱后，转化成随机错误， 由行列译码器分别予以纠正，从而获得纠突发错误的能力【4 5 】。 以子码均为汉明码所构成的二维t u r b o 乘积码p = c 1pc 为例，如图2 5 所示，图 中的黑块表示出错的比特。c l ( ，毛，吐) 的纠随机错误的能力为f i - i 鱼i ：l 莩l ：1 ， l z jl 么j g ( 啊，毛，盔) 的纠随机错误的能力也为乞- - i 垒i ：i 掣i ：1 ，乘积码尸( 啊他，岛岛，匾吃) l 二 jlzj 的纠随机错误的能力为r ：l 堕冬兰l - l 兰安兰1 - 4 。现假设在接收码字矩阵中第衍亍出 l z j l z j 现了一个长度为，的突发错误，超出了行译码器的纠错能力，当对第衍亍进行行译码时就 必然出错，并可能导致行译码的输出错上加错，但是在进行列译码时由于第i 行的突发 错误相对于接收码字矩阵的各列码字而言，只是在第f 位上出现了单个错误，并未超出 列译码器的纠错能力范围，因而列译码器可以在对各列进行译码时，轻松地将第f 行的 错误逐个纠正，正确译码，从而获得纠突发错误的能力；同理，对于列码字出现的突发 错误，行译码器也可以进行正确译码。据此原理，不难得到乘积码尸可以纠长度为 b m a 如，啦f 1 ) 的突发错误。进一步我们还可以得到如下结论：如果子码c 1 和c 分别 具有纠长度不大于岛和以的突发错误的能力，则由它们构成的乘积码p 可以纠正长度 第2 章t u r b o 乘积码编译码理论基础 b m a x ( r 毛b 2 ，心6 1 ) 的突发错误旧。 ? 2 图2 5 乘积码某行出现突发错误示意图 2 2 3t u r b o 乘积码的常用子码 根据实际系统用途和设计复杂度的需求，t u r b o 乘积码的子码可以采用汉明码、b c h 码、扩展汉明码、i 塔码等线性分组码，而且子码的码型和码长可以相同，也可以不同， 常用的主要有h a m m i n g 码、b c h 码、r s 码等，但是考虑到编码器和译码器设计上的复 杂度，t u r b o 乘积码通常选择相同的码型作为子码。 2 2 3 1 h a m m i n g 码 h a m m i n g 码( 汉明码) 是1 9 5 0 年汉明为了解决计算机运行不稳定的问题而提出的 一种能纠正单个随机错误的线性分组码l 删。这是一种完备码，编译码较简单，且容易工 程实现，故应用广泛。对于任意整数朋2 ，汉明码的参数如下： 码长：胛= 2 舸一1 信息比特数：k = 2 “一m 一1 校验比特数：，= 疗一k = m 码率：尺：鱼 最小汉明距离： “；。= 3 在上述参数中，一旦m 给定，就可构造出具体的汉明码( 疗，k ) 。根据线性分组码最 小汉明距离与其纠错能力的关系可知，汉明码的纠错能力，= 【- 生手j = 1 ，只能纠一位 错。如果对汉明码所有码元进行模2 和后得到一个全校验位，将此全校验位加入到汉明 哈尔滨丁程大学硕士学位论文 码的校验位，从而增加原汉明码的校验位数，这样就形成了扩展汉明码。扩展汉明码的 码长为2 厨，信息位数仍是2 崩一m l ，但最小汉明距离增至4 ，这样，它就可以在纠一位 错的同时又能发现两位错误。系统扩展汉明码还具有循环移位自闭性，因此是一种循环 码【2 l 。 另外，由于扩展汉明码的码长为2 ”，通过合理的选择可以得到码长为8 的倍数的扩 展汉明码，因而特别适合在计算机等数据处理系统中应用1 4 7 。 2 2 3 2b c h 码 循环码是线性分组码中一个重要的子类，它除了具有一般线性分组码的结构特点 外，还具有循环移位自闭性的特点，即对任何循环码字进行移位后的结果依然是循环码 字，可以采用更为简便的多项式方法对其进行描述，因而其编码和校正子( 也称伴随式) 计算可以很容易地通过线性时序电路实现。循环码具有严谨的基于有限域的代数结构， 不仅易于根据所要求的纠错能力t 去构造相应的码字，而且很容易找到多种实用译码方 法，因而成为目前研究最为成熟、应用最为普遍的一种码类1 2 1 。 b c h 码是循环码的一种重要子类，具有很强的纠错能力。它是在汉明码的基础上， 通过增加一致校验矩阵的行数，从而提高了码字的纠错能力，是汉明码在纠多重错方面 的一种推广码【4 s 】。b c h 码具有严格的代数结构，能提供对分组长度、编码效率、码元集 大小和纠错能力的多种选择，人们可以根据所要求的纠错能力构造出适当的b c h 码。 b c h 码纠错能力很强，尤其是在短码和中等码长下，其性能接近于理论值，并且构造 方便，编码简单 3 9 1 。 实际中应用最多b c h 码为二进制b c h 码，如果按设计要求给定码字长度甩和码字 纠错能力t ，就可以确定一个二进制本原b c h 码。在第三章中将详细介绍b c h 码的编 译码原理，这里不作过多阐述，只给出其有关参数【鹌】。 码长n = 2 厢一l 校验比特数 ，= 刀一k m t 最小汉明距离2 t + l 纠错能力 ， 其中d = 2 t + 1 称为b c h 码的设计距离，又叫做b c h 限，它是构造b c h 码时所要 达到的距离下限f 4 4 】。 与扩展汉明码相同，若对最小距离为奇数的b c h 码( ，l ，k ，d ) 增加一个全校验位，则 可得到仰+ l ，k ，d + 1 ) 扩展b c h 码i s 。 1 4 第2 章t u r b o 乘积码编译码理论基础 2 2 3 3r s 码 r s 码 4 9 1 是一种多进制的b c h 码，关于b c h 码结论差不多都可以用于r s 码。r s 码在编码方法上与二进制循环码不同，它是以每符号m 个比特进行的多进制编码。码字 长”= 2 肘一l 的比特数为m ( 2 ”一1 ) 比特，当历= 1 时就是二进制编码。 r s 码是一种多进制纠错码，特别适合于多进制调制的场合，其最小汉明距离比校 验符号数多l ，因此可以高效利用r s 码的冗余度，而且可以根据需要在大范围内调整 参数，便于码率的选择，而且它译码方便、高效，适合于纠正衰落信道中的突发错误。 纠错能力为f 的r s 码的有关参数如下 2 】： 码长刀= 2 ”一1 ( 符号) 信息组长度k 个符号，k = 疗一力 校验位个数 刀一k = 2 t ( 符号) 最小汉明距离d m 缸= 2 t + 1( 符号) 综上所述，与只能纠单个错误的h a m m i n g 码和可纠突发错误的r s 码相比，b c h 码在纠错能力上比汉明码要强，在编译码实现上要比r s 更为简便，因而，本论文选择 以b c h 码作为t u r b o 乘积码的子码。 2 31 r l l r b o 乘积码的译码方法 t u r b o 乘积码译码分为硬判决译码和软判决译码两种方式。在硬判决译码时，解调 器送给译码器用于译码的每个码元只取0 或1 ，判决门限设为0 ，译码器则根据信号幅 度是否超过判决门限进行译码，得到译码码字，显然这种判决方式损失了接收信号波形 中的有用信息( 也称作软信息) 。而软判决时，译码器直接利用解调器输出的量化电压 或模拟电压进行译码，有效地利用了接收信号波形中的有用信息，提高了译码性能。在 这两种译码方法中，硬判决译码较为简单，工程实现较为容易，但在性能上比软判决译 码在a w g n 信道中的性能差2 d b 一- - 3 d b ，在衰落信道中相差更大。因此，软判决译码方 法以其良好的译码性能逐渐受到人们的重视，尤其是在1 9 9 3 年t u r b o 码提出后，更加 激发了人们研究软判决译码的兴趣 4 2 1 。本节简要介绍t u r b o 乘积码的几种比较典型的硬 判决译码方法和软判决译码方法。 2 3 1t u r b o 乘积码的硬判决译码 硬判决译码又称作代数译码。它是根据乘积码的编码过程而提出的一种由行、列硬 哈尔滨t 程大学硕士学位论文 判决译码器级联形成的译码结构，如图2 6 所录埘。 图2 6 级联硬判决译码器 其中行列译码器对输入的码字进行代数译码，对于校验矩阵为日的线性分组码 c ( n ，k ，d ) ，接收端接收到经信道干扰后的码字足，对r 的代数译码按以下步骤进行： ( 1 ) 计算伴随式：s = r h 7 ； ( 2 ) 根据伴随式s 找出错误图样e ； ( 3 ) 根据错误图样窟对足纠错，得到估计码字：0 = r + 应，如果e = c ，译码正 确，否则译码不正确【伽。 乘积码在编码时是按照先行( 列) 或先列( 行) 进行编码，在译码时也可按先行( 列) 后列( 行) 译码进行，例如在先行后列译码时，行硬译码器先对输入的码字r 形成的码 块矩阵的各行进行代数译码，当所有行译码完成后，行译码结果输出作为列硬判决译码 器的输入，列硬译码器对其各列进行列代数译码，列译码结果即为最终的译码结果。这 种译码方式结构简单，复杂度低，易于工程实现，但译码性能差。因此，可以通过迭代 的方式进行多次行列译码来提高译码性能，其结构如图2 7 所示m 。 图2 7 中的这种级联硬判决译码器的迭代结构只是将图2 6 中列译码器输出的结果 再次返回到行硬判决译码器的输入端，再次进行上述行列代数译码的过程。对输入信 号矩阵所有行( 或列) 完成一次行( 或列) 译码称为半次迭代，一次完整的行( 或列) 列( 或行) 译码称为一次迭代译码。 图2 7 级联硬判决译码器的迭代结构 虽然t u r b o 乘积码硬判决译码性能不如软判决译码，但其结构简单，易于实现，因 此，在一些信道条件好，对误码率要求不是太高，且复杂译码器难于实现的场合还是得 到了一些应用i s o l 。 第2 章t u r b o 乘积码编译码理论基础 2 3 2t u r b o 乘积码的软判决译码 如前所述，软判决译码相比硬判决译码而言，由于能够充分利用信道的有用信息， 因而译码性能比硬判决译码要好2 d b - 3 d b ，下面介绍乘积码的几种典型软判决译码方 法。 2 3 2 1 软输出维特比译码算法( s o v a ) 维特比算法( v i t e r b ia l g o r i t h m ，v a ) 由v i t e r b i 在1 9 6 7 年首先提出的，它是基于码 的网格图的一种最大似然译码算法，它以码字为单位进行逐字软判决译码，目的是使码 字错误概率达到最低。这种算法既适用于卷积码，也适用于分组码，其译码基本思想是： 在所有竞争路径中找到似然度量最大的路径，以实现最大似然译码。经典v a 虽然可以 接收码字先验信息作为软输入，但是其输出为硬判决信息，并不适于t u r b o 译码。1 9 8 9 年，h a g e n a u e r 等人在传统v a 的基础上进行修正，提出了软输出v i t e r b i 算法( s o f t - o u t p u t v i t e r b i a l g o r i t h m ，s o v a ) 4 2 1 。此算法的软比特判决信息由对数似然( l l r , l o gl i k e l i h o o d r a t i o ) 提供，l l r 数学表示形式如下【1 2 】： 弘舢引 协。 式中： 口归一化因子，通常取值4 d 脾e 0 ； 。 多，枷传递过程中某个比特出错的概率估计。 ： 三i 的递归更新表示如下：。 t + - - m i n ( ，口) ( 2 - 2 ) 式中： 。 路径度量的差值。 s o v a 算法在找到最大似然路径同时，还能计算每个信息比特的后验概率，因而适 合于级联使用。f r e e m a n 等人将s o v a 算法应用于行码为卷积码、列码为线性分组码的 乘积码译码，在对列的最大似然译码的软判决中，就用到了s o v a 算法计算的行软比特 输出t 。h a g e r l a u c r 等人的仿真结果表明：乘积码的行码采用码率为疋= j 1 及恐= 吾 的卷积码，列码采用汉明码( 6 3 ，5 7 ，3 ) ，在信道条件为a w g n 信道，误码率b e r = 1 0 巧的 条件下，对疋= i 1 的情况，编码增益可达7 3 d b ，对足：丢的情况，编码增益可达7 8 d b 【5 i 】。 1 7 哈尔滨工程大学硕士学位论文 s o v a 算法基于序列进行译码，适用于对连续数据流译码，具有较低的译码延时和 计算复杂度，易于工程实现。但是其译码性能不如b c j r 算法 s o l 。 2 3 2 2m a p 迭代译码算法 m a p 算法就是最大后验概率算法，它是一种基于码字网格图的逐位软判决译码方 法，可以使误比特概率降到最低1 4 2 。此算法由l r b a h l 、j c o c k e 、e j e l i n e k 和j r a v i v 四人在1 9 7 4 年共同提出，并以他们名字命名，故也称为b c j r 算法 s 2 j 。在该算法提出的 初期并未引起人们的关注，直到1 9 9 3 年c b e r r o u 等学者对m a p 算法进行简单修改后 应用于t u r b o 译码才引起了人们的关注【5 】。二维乘积码的m a p 迭代译码器结构如图2 8 所示。 输入 出 图2 8 二维乘积码基于m a p 迭代译码器结构示意图 m a p 迭代译码算法的核心思想是：译码时根据最大后验概率原理，行m a p 译码器 计算每行中各比特的后验概率作为软信息输出，用于列m a p 译码器的输入，列m a p 译码器轮流计算每比特位置后验概率，如此往复，以最后一次迭代时列译码器输出的各 比特位置的后验概率大小来判断比特信息 s o l 。 由于m a p 算法涉及许多对数、指数和乘法的运算，且需要消耗大量存储空间，其 实现复杂度较高。因此k o c h 和e r f a n i a n 提出了m a x l o g m a p 算法，将乘法转换至对 数域并进行近似计算，降低了m a p 算法的复杂性，但是由于引入了近似计算，其性能 比m a p 算法差，为此，1 9 9 5 年r o b e r t s o n 等人对m a x l o g m a p 算法中的近似计算进 行了修正，提出了l o g m a p 算法，虽然复杂度提高了一些，但其性能得到了较大改善， 几乎与m a p 算法相等【4 2 】。 2 3 2 3带非本征信息的s i s o 迭代译码器 在m a p 迭代译码结构的启发下，1 9 9 6 年h a g e n a u e r 等人对m a p 迭代译码器作出 改进，给出了图2 9 所示的二维乘积码迭代译码器结构，它由两个软输入软输出( s i s o ) 译码器级联构成【2 1 。 第2 章t u r b o 乘积码编译码理论基础 下次迭代的反馈 输出 图2 9 二维乘积码的s i s o 迭代译码器 与对并行级联卷积码( p c c c ) 进行t u r b o 译码时采用的对数似然比( l l r ) 表示 形式类似，这里对子码为系统码的s i s o 译码器的软输出信息可以表示为i t 2 ： 三( d ，) = 厶( x ) + 厶( d ，) + t ( d ，) ( 2 3 ) 式中； 三( d ，) 对第歹个信息符号估计d ，的对数似然比； t ( x ) 信道信息，a w g n 信道条件下取值为4 e o ； 厶( d ) 先验值，假设为已知，初始化时设为o ； 厶( d ) 非本征信息，在码字序列中包含的其它所有编码比特的软输出信息。 需要说明的是，式( 2 3 ) 中的非本征信息t ( d ) 独立于先验值厶( d ) 和信道信息 厶( x ) ，是关于码字的新信息；而且似然比( l l r ) 值可以通过软输入软输出m a p 译码 器进行计算【1 2 j 。 一 这种译码器与迭代的m a p 译码器类似，但由于乘积码的编码结构本身就包含了一 种行列交织结构，因而在两个s i s o 译码器间就不用再加入交织器和解交织器环节。其 译码过程简述如下： 在进行首次迭代时，需要对译码器进行初始化，由于行s i s o 译码器无可用的先验 信息，故通常令l o ( d ) = 0 ；在行s i s o 译码结束后，行s i s o 输出行非本征信息矿( d ) 作 为列s i s o 译码器的先验信息( 0 ) 送入列s i s o 译码器，即掣( 0 ) = ( 0 ) ，利用此先 验信息掣( d ) 和信道信息l a x ) ，列s i s o 译码器求出列非本征信息( d ) ，并将其反馈 给行s i s o 译码器作为其先验信息穿( 0 ) ；即口( i ) = ( 0 ) ，如此往复迭代，直到完 成指定的迭代次数后，得到最终的似然比三( d ) 结果为： ( d ) = ( d ) = 厶( x ) + l 7 ( d a + 上罗( d ，) ( 2 - 4 ) 最后，根据三口) 的符号按式( 2 5 ) 判断译码结果1 1 2 1 。 1 9 哈尔滨丁程大学硕士学位论文 f“ i 三( d ) 0 ，d = 1 ( 2 5 ) i 1 工( d ) 0 ，d = 0 2 3 2 4 基于c h a s e 算法的迭代译码算法 c h a s e 算法是d c h a s e t 3 于1 9 7 2 年提出的一种利用线性分组码代数译码进行逐字软 判决译码的方法，是对1 9 6 6 年g d f o m e y 提出的广义最小距离( g e n e r a l i z e dm i n i m u m d i s t a n c e ，g m d ) 译码算法的一种推广，能够获得接近最大似然( m l ) 译码的性能【4 2