（通信与信息系统专业论文）现代编码的性能分析与简化译码算法.pdf

。、 一_=，一。 f强t鑫vb警 ：卅-。， 舢| i | | i | | | i i | i l | j | i j jj i | i i f i | | 删 y 17 6 0 5 4 9 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位 本人签名： 导师签名： 现代编码的性能分析与简化译码算法 摘要 编码理论一直是通信理论研究的重点问题之一，在第三代和第四 代移动通信系统的设计和应用的推动下，t u r b o 码、l d p c 码为代表 的近限好码尤其受人们关注。这些编码的优势在于具有非常强的前向 纠错能力，但译码复杂度相应的也会比较大，所以简化译码算法的研 究对于降低系统功耗和译码时延是很有帮助的。 随着t u r b o 码和l d p c 码等现代编码的广泛应用，对其进行性能 分析显得尤为重要。但是由于此类编码结构和译码算法相对复杂，所 以很难给出明确的理论分析。近代对此类编码性能的研究一般以仿真 辅助加以理论推导的方式进行，但通常这些方法对于分析实际系统都 或多或少存在一些局限性，这也影响他们的推广和应用。所以找到一 种具有实用价值的普适方法是非常重要的。 本文的研究主要集中在现代无线通信系统中广泛使用的t u r b o 码、l d p c 码的性能分析和译码算法。主要贡献如下： ( 一) 提出了平方半径谱( s r - p d f ) 的概念，并将其应用于现代编 码与现有无线通信系统中进行性能分析。平方半径谱的概念改变了为 获得系统错误概率所使用的传统仿真方法。以一种更快更灵活的方法 取而代之，在保证准确程度的同时大大减少了仿真量。同时利用这一 概念所得到的理论公式也对信道编码的理论分析给予很大支持。另 外，将该方法稍作拓展即可用来分析l d p c 码与t u r b o 码所能达到的 仙农极限。从而为现代编码的性能分析提供了另一种新途径。 ( 二) 提出以t u r b o 码与l d p c 码等强纠错码为内码，以s p c ( 单 比特校验码) 为外码，同时采用迭代译码与m r c ( 最大比合并) 结合的 简化译码算法的级联编译码方案。该方案在降低编译码复杂度的同时 让系统性能有所提高。 ( 三) 基于迭代译码算法中译码次数的随机性提出了利用译码器 池来提升t u r b o 码与l d p c 码译码器吞吐量的并行译码方案。并且吞 吐量的提升并不以译码性能的损失为代价。 关键词l d p ct u r b os p cs r p d f 密度进化 p e r f o r 队n c ea n a l y s i s0 fm o r d e r nc ha n n e i ， c o d i n ga n dt h es i 口l i f i e dd e c o d i n ga l g o i u t h m a bs t r a c t c h a n n e lc o d i n gi sa l w a y sah o tt o p i ci nw i r e l e s sc o m m u n i c a t i o n s p r o m o t e db yt h e3 ga n d4 gw i r e l e s sc o m m u n i c a t i o ns y s t e m s ，t u r b o c o d ea n dl d p cc o d ea r ep o p u l a r l yu s e di nm o d e m s y s t e m s t h e s ec o d e s h a v es t r o n gf o r w a r de r r o r c o r r e c t i n gc a p a b i l i t y , w h i l e t h e d e c o d i n g c o m p l e x i t yi sa l s oh i g h e rt h a ns o m es i m p l ec o d e s s oi t sv a l u a b l et of i n d a s i m p l i f i e dd e c o d i n ga l g o r i t h m i no r d e rt od e c r e a s et h ed e l a yi n d e c o d i n gp r o c e s sa n dt h ep o w e rc o n s u m p t i o ni nt h es y s t e m a st h ed e v e l o p m e n to fm o d e mc h a n n e lc o d i n ga n dt h ed e c o d i n g a l g o r i t h m s ，t h er e q u i r e m e n t sf o rp e r f o r m a n c ea n a l y s i st ot h e s ec o d e s b e c o m em o r ei m p o r t a n t p r e s e n t l y , t h ea n a l y s i st e c h n i q u ei sm a i n l yt h e s i m u l a t i o na s s i s t e dt h e o r e t i c a la n a l y s i s h o w e v e r , l i m i t e db ys o m ef a c t o r i nar e a ls y s t e m ，t h e s es c h e m e sc a nr a r e l yb eu s e d s oi ti ss i g n i f i c a n tt o f i n das c h e m et h a ti sa p p l i c a b l et om u l t i p l eo fr e a ls y s t e m s t h i st h e s i sm a j o r e di nt h ep e r f o r m a n c ea n a l y s i so fm o d e mc h a n n e l c o d i n ga n dt h es i m p l i f i e dd e c o d i n ga l g o r i t h m s t h em a i nc o n t r i b u t i o n s a r ea sf o l l o w i n g ： 1 p r o p o s e dt h ec o n c e p to fs r - p d f ( s q u i r e d r a d i u sp r o b a b i l i t yd e n s i t y f u n c t i o n ) t h i sc o n c e p tc h a n g e st h ew a yt oe v a l u a t et h ea v e r a g e e r r o rr a t ei nas y s t e m as i m p l ea n df l e x i b l ew a yi si n t r o d u c e d ， w h i c hs a v e s al a r g en u m b e ro fs i m u l a t i o n sw h i l eg u a r a n t e et h e p r e c i s e n e s so ft h er e s u l t s b a s e do nt h i sc o n c e p t ，t h i st h e s i sg a v e s o m ea p p r o x i m a t ee q u a t i o n st h a ta r eu s e f u lf o rt h e o r e t i c a la n a l y s i s o nm o d e mc h a n n e l c o d i n g f u r t h e r m o r e ，a f t e r t h e p r o p o s e d t e c h n i q u ei se x t e n d e dt oa n a l y z et h ed e c o d i n gt h r e s h o l do fc a p a c i t y i v 2 3 a c h i e v a b l em o d e mc h a n n e lc o d i n g i ti sf o u n dt h a ts r - p d fp r o v i d e s a n o t h e rw a yt oo b t a i nt h es h a n n o nl i m i tf o rt h e s ec o d e sb e s i d e st h e t r a d i t i o n a lw a y s p r o p o s e da ni m p r o v e dc o n c a t e n a t e dc o d i n ga n dd e c o d i n gs c h e m e ， w h i c he m p l o y ss p ca st h eo u t e rc o d ea n dm o d e mc h a n n e lc o d i n ga s t h ei n n e rc o d ea tt h ee n c o d e r a n de m p l o y s a n di t e r a t i v e d e c o d i n ga l g o r i t h m s a tt h ed e c o d e r t h i ss c h e m eh a sb e r e r p e r f o r m a n c ea n dl e s sc o m p l e x i t yc o m p a r e dw i t h t h et r a d i t i o n a l c o n c a t e n a t e dc o d i n ga n dd e c o d i n gs c h e m e s b a s e do nt h er a n d o m n e s so ft h en u m b e ro fi t e r a t i o n s 。t h i st h e s i s p r o p o s e dap a r a l l e ld e c o d i n gs c h e m et h a tc a nb eu s e dt oi m p r o v et h e t h r o u g h p u to fd e c o d e r sf o rb o t i l 眦oc o d e sa n dl d p cc o d e s f u t h e r m o r e ，t h ep e r f o r m a n c eo ft h ep a r a l l e ld e c o d i n gi sn o tw o r s e t h a nt h et r a d i t i o n a ls c h e m e k e yw o r d s ：t u r b ol d p cs r p d fs p cd e n s i t ye v o l u t i o n p a r a l l e ld e c o d i n g v 目录 第一章绪论8 1 1 无线通信中的信道编码技术8 1 2 信道编码的理论基础9 1 2 1 信息源的信息熵9 1 2 2 信道容量9 1 2 3 信道编码定理1 0 1 2 4 线性分组码1 2 1 2 5 卷积码13 1 3 信道编码的性能分析方法概述1 4 1 4 论文主要工作及结构安排1 5 1 5 本章参考文献1 6 第二章t u r b o 码与l d p c 码译码算法的研究1 7 2 1t u r b o 码的编译码算法一1 7 2 1 1m b o 码编码器一17 2 1 2t u r b o 译码算法2 6 2 1 3t u r b o 码并行译码算法的研究3 6 2 2 提出的基于译码器池的并行译码算法4 2 2 2 1 问题的提出4 3 2 2 2 提出的基于译码器池的并行译码算法4 5 2 3l d p c 码的编译码算法一4 8 2 3 1l d p c 码编码器4 9 2 3 2l d p c 码译码算法5 5 2 4 提出的新型级联编译码算法5 8 2 4 1s p c 级联码编码器结构5 9 2 4 2s p c 级联码译码算法6 l 2 5 本章小结7 3 2 6 本章参考文献7 4 第三章t u r b o 码与l d p c 码的性能分析7 6 3 1 利用e x i t 图的性能分析方法7 6 3 1 1e x i t 图的原理7 6 3 1 2t u r b o 码迭代译码的e x i t 图分析7 9 3 1 3l d p c 码迭代译码的e x i t 图分析8 5 3 2 利用性能界和加重采样的性能分析方法9 2 3 3 本章小结9 3 3 4 本章参考文献9 3 第四章平方半径谱( s r p d f ) 的概念及应用9 5 4 1 平方半径谱( s r p d f ) 的概念9 6 4 2 通过s r p d f 测量误码率的原理1 0 2 4 3s r p d f 的渐进特性10 3 4 4 利朋s r p d f 对通信系统进行分析10 5 v i 4 4 1 典型系统的s r p d f 1 0 6 4 4 2 利用s r - p d f 计算错误概率1 1 4 4 4 3 利用s r p d f 近似计算错误概率1 l8 4 5 利用s r p d f 测量t u r b o 码和l d p c 码的门限信噪比1 2 3 4 6 平方半径谱与传统方案的比较12 7 4 7 本章小结1 2 8 4 8 本章参考文献。1 2 8 第五章总结1 3l 缩略词表1 3 3 至筻谢13 5 攻读博士期间发表的论文1 3 6 一v 1 1 第一章绪论 1 1 无线通信中的信道编码技术 在无线通信系统中，信道编码主要通过两种途径发挥作用：第一种是差错控 制配合反馈重传的形式，即通过信道编码让接收端知道所接收到的信息正确与 否，来做出进一步的处理，例如丢弃或反馈重传。这类编码通常具有较小的冗余 度，只具备检错能力或较弱的纠错能力( 例如s p c 或c r c ) ，主要通过后续的处 理( 例如重传) 来提高传递信息的可靠性。另一种途径是本文主要讨论的前向纠错 编码，这类编码冗余度高，通常具有较强的纠错能力，可以在接收端纠正所传递 信息中一定数量的错误信息。现代通信系统中广泛使用的前向纠错信道编码主要 包括t u r b o 码、l d p c 码、卷积码以及简单的线性分组码。 t u r b o 码【1 1 】的显著纠错能力关键在于接近随机性的码距谱以及迭代译码的 思想。在无线信道低信噪比情况下，t u r b o 码的性能要比传统卷积码优异很多， 所以在3 g 系统主要提案中( 包扩w c d m a 和c d m a 2 0 0 0 等) ，在低速率和低性 能要求下，仍然采用与第二代系统相类似的卷积编码技术和交织技术，而在高速 率和高性能要求下，建议采用t u r b o 编码技术及r s 卷积级联码技术。t u b r o 码 比级联r s 卷积码性能更优，被普遍作为高速数据信道的纠错编码方式 1 2 】 1 3 】。 随着对t u r b o 码研究的深入，人们重新发现g a l l a g e r 早在1 9 6 2 年提出的低 密度奇偶校验码( l o w d e n s i t yp a r i t y c h e c kc o d e s ，简称l d p c 码) 【1 4 】也是一种 具有渐进特性的好码，它的译码性能同样可以逼近香农信道容量限。l d p c 码具 有在中长码长时优于t u r b o 码的纠错性能，并且译码复杂度更低，能够并行译码 以及译码错误可检测等特点，成为目前信道编码理论的研究热点。研究表明， t u r b o 码只是l d p c 码的一个特例【1 5 】，二者都是基于图构造的低密度码，译码 算法具有等价性，二者在基于图论的编译码研究中得到了统一。l d p c 码采用迭 代译码算法。这种算法的优点有：算法可以并行实现，因此译码速度极高；译码 算法的复杂度较低，其运算量不会因为码长增加而急剧增加，这是卷积码及其它 分组码所不能比拟的【1 6 。 一r 1 2 信道编码的理论基础 1 2 1 信息源的信息熵 设离散随机变量x ( 信息源) 有k 种可能取值鼍，i = o 1 ，足一1 ，其中样本薯 发生的概率为最( 墨) ( 简记为鼻) 。则随机变量x 取值为x j 的信息量定义为【1 7 】： = l 。g 丽1 = - l o g 只 ( 1 1 ) 其平均信息量为： 日( 功= 篓b ( 而) l 。g 瓦b = 莩p 1 。g ( 专) = 一军只l 。g p ( 心) 上式同热力学中的熵形式相似，故通常又称它为信息源的信息熵。 同样，关于连续消息的信息量可通过概率密度函数来描述。连续消息的平均 信息量定义为 日( x ) = 一jp ( x ) l o gp (x)dx(1-3) 其中p ( 功为连续消息的概率密度函数。 1 2 2 信道容量 一种经典的单输入单输出的通信系统模型如图卜1 所示。这种模型最先由仙 农提出用以研究。在噪声信道下发送信号u 皇 u ， 。发送端首先将信息 u 按照一定的规则映射为序列x 垒 工，五9o 0 9 k ，序列x 受到信道噪声干扰， 信道输出】，垒 x ，e ，匕) 以某种概率分布受限于x ，这种概率分布用以描述信道 的特性。接收端通过对j ，的判断获得信息的内容u 。 u 厂 x 一、y 厂一 u ， + 发射机l _ 7信道 接收机l + 7 一 一 9 一 图1 - 1 经典通信系统模型 如果信道某时刻的输出只与当前时刻信道的输入有关，而与之前或者之后的 信道输入都无关，则称为无记忆信道，也就是说 一 所( y l x ) = 兀p 私( mi x , ) ( 1 - 4 ) j 暑l 这种情况下，信道的统计特性完全由任意时刻的条件概率p r ( y lx ) 来表述。如 果发送符号置为独立同分布的随机变量，则接收端符号r 也是独立同分布的。 两个离散随机变量的联合熵定义为 日( x ，聊2 军莩p ( 薯，乃) 1 0 9 z 瓦而1 ( 1 - 5 ) 条件熵定义为 h ( x i 即= 尸( 乃) h ( x ly = y j ) = 一尸( t ，y j ) l o g ：尸( tly j ) ( 1 - 6 ) 仙农定义了两个离散随机变量之间的互信息，( x ；】，) 舭；y ) = h ( x ) - h ( x 阶莩弘舭g ： 掣 m 7 ， 互信息j ( x ；y ) 反映了在已知y 的条件下获得关于x 的信息量。无记忆信道 的信道容量定义为上述互信息量的最大值，即在已知接收端符号】，的情况可以获 得关于输入符号x 的最大信息量，也就是信息可以在该信道下进行可靠传输的 最大值【1 7 】【1 8 - c = m a x ，( x ；】，)( 1 8 ) 凡( j ) 1 2 3 信道编码定理 信道编码定理是指，对每一类信道都存在着一定的信道容量c ，它是信道的 最大极限传输能力，只要当实际传输速率r c 时，就可以实现在信道上无差错 的传输。仙农给出了这一定理在分组码情况下的证明，以后又有人推广至卷积码。 仙农证明了在信道中可以实现无差错的传输，也就是说如果采用了适合的编 码方法，实现可靠通信并不需要太大的发射功率。如果把码字看作是码窄间内的 1 0 一些点，那么噪声的影响会改变这些有效码字在码空间的位置，从而影响译码器 的判断造成译码错误；也就是说，一种编码造成的码字间距离越远，这种编码的 性能也就越好。由此可以看出，在无限维空间中随机摆放码字点，使得码字点之 间的距离可以无穷远，也就实现了无差错的传输。但是如果简单的照搬上述编码 条件，显然无法在实际系统中得到应用：首先，码字的数量就无法控制：其次， 随着码字长度的增加，译码复杂度升高造成的译码时延也是实际系统无法接受 的。为此，人们提出了以多个短码来构造长码的方法，如乘积码、级联码，以减 少编译码的复杂性，同时能够获得同等效长码一样的优异性能。但是利用传统的 短码构造长码方法具有不可避免的缺陷，即只有在远离信道容量的条件下才能够 获得同等效长码一样的优异性能，在渐进信道容量的情况下进行译码时，其优异 性能马上消失，这是所有已知短码存在的固有缺陷。即使由上述短码串行级联来 构造长码，其渐近状态的组合性能仍然是由串接的内外两个短码的性能决定，所 以由确定的短码构造的长码，其性能仍存在着一个渐进状态不可逾越的门限。 另一方面，译码方法要远比编码构造方法来的更为复杂。从理论上说，在高 斯白噪声信道下，实现译码错误概率最小的最佳译码算法早己解决，就是最大后 验概率译码，若码字的发送概率相同，等效为最大似然译码。对于二进制对称信 道，最大似然译码等价于最小汉明距离译码。虽然这是最佳的译码方法，但是因 为它要穷举搜索所有码字，因此对于长码来说，几乎是不可能实现的。卷积码中 的v i t e r b i 译码固然等价于最大似然译码，但也只能适用于约束长度较小的情形。 因此人们转而寻求译码性能相对于最佳译码来说损失不大的次最佳、准最佳 译码方法。一种方法是以追求每个码元译码错误概率最小为目的的逐位软判决译 码算法；另外一种则是以追求每个码字组错误概率最小为目标的逐组软判决译码 算法。逐位软判决译码算法的思想在t u r b o 码和l d p c 码的译码中得到了充分体 现，它们的译码算法均是一种递归迭代算法。 1 9 9 3 年，c b e r r o u 等提出的t u r b o 码 1 - 1 ，因为在工程上引入了随机编译 码的思想，从而成为第一种可以获得接近s h a n n o n 极限性能的好码。他们的仿真 结果表明，在a w g n 信道情况下，当信噪比e b n 0 = 0 7 d b 时，t u r b oc o d e s 的误比 特率( b e r ) 小于1 0 喃，与s h a n n o n 界相差仅有0 7 d b 。 低密度校验码( 1 0 w d e n s i t yp a r i t y c h e c k ，l d p c ) 码和t u r b o 码在有砦地方 有相同的思想。它最早是由g a l l a g e r 发明的，但一直被人们遗忘。直到t u r b o 码 提出之后，人们才重新对l d p c 码展开研究。此后的许多工作致力于容量极限、 编码和译码设计、不同信道下的实际实现等问题。随后s a e y o u n gc h u n g 等人提 出一种改进的构造l d p c 码的方法，仿真结果表明在a w g n 信道下，码长为1 0 7 ， 在误比特率为1 旷时，此时l d p c 码的性能与仙农极限相差0 0 4 d b 1 9 1 。 1 2 4 线性分组码 从概念上说，线性分组码是单比特校验码的扩展。单比特检验码是一种常见 的检错码。它在一个，l 比特的数据分组中加入一个比特，以指示该分组中l 的数 目是奇数还是偶数。如果发生了单个比特错误，不论错在校验位还是信息位，结 果都将使信息比特中1 的个数和校验比特的指示不一致，这样接收端就知道发生 了错误。线性分组码拓展了这种思想，它使用更多的校验比特，从而能够检测多 个错误或者能够纠正一个或多个错误。 二进制的( 刀，k ) 分组码是由k 个信息比特生成甩个编码比特，编码比特也称 为码字符号。以个编码比特有2 “个可能的取值，从中选出2 个作为码字，就形成 ； 一种编码率是足= k n 的二进制分组码。 当这些码字构成一个线性空间时，这样的分组码就是线性分组码。线性分组 码的构造是由生成矩阵描述的。生成矩阵反映如何从信息比特产生出线性分组码 的码字。线性分组码的设计就是要找到这样一个生成矩阵，它所对应的码容易实 现编解码，同时又有强大的纠错和检错能力。考虑( 刀，k ) 码的一个码字，其k 个 信息比特为： u = 胁，纵】 编码后的码字为 c ，= c l ，“，g 】 编码操作可用下面的7 个方程来表示 c q = 材，l g l ，+ u , 2 9 2 ，+ + 甜睹g 旬，j = l ，门 12 其中岛是二进制的0 或i 。这，1 个方程可写成矩阵形式 g 2 其中的k x ，维矩阵g 就是这个码的生成矩阵。系统线性分组码的生成矩阵有如 下形式：g - i lp 】，其中i 。是一个后尼的单位阵，p 是一个尼一后) 的矩阵， 它产生检错和纠错所需的冗余比特或称校验位。校验矩阵用来译出生成矩阵为g 的线性分组码。与生成矩阵g _ 【l 。ip 】对应的校验矩阵日为日= ip rii 柑l ，容易 验证册r = o ，一i ，其中o 咄是一个k x ( n k ) 的全零矩阵。因为码字c ，是信息 比特u ，与生成矩阵g 的乘积，即c ，= u 。g ，所以对任意的输入序列u ，有 c ，h r = u ，g h 丁= o 。廿，其中0 枞为全零行向量。因此，任意一个合法码字和校验 矩阵的乘积应是全零向量。l p d c 码就是一种线性分组码，其特征是校验阵日中 1 的个数很少，即稀疏矩阵。 1 2 5 卷积码 如果编码码字c ：只取决于第f 个输入信息以( e = 厂( q ) ) ，与以前的输入 ，咖配q ) 无关，这样的编码也叫无记忆的编码。如果编码器的输出不仅和现 在的输入有关，还和过去的m 个输入有关，即若c = 厂( ，巾，u 一。) ，则称 为有记忆的编码，m 称为记忆深度。当约束关系厂( ) 为线性运算时，这样的有 记忆编码记作( 门，k ，m ) 卷积码。 信号系统中处理有记忆系统的一种方法是用系统状态这种概念来体现过去 记忆所起的作用。“状态”的确切含义是指系统内部的一些变量的集合，使得在 某个时刻，如果给定当前时刻的输入以及前一时刻的状态，则当前时刻的输出、 状态都是确定的。卷积码编码器是一种有记忆的线性系统，因而我们也可以用状 态分析的方法来分析卷积码。 1 3 就图i - 2 中的这个( 2 ，1 ，2 ) 卷积码来说，第i 时刻编码器的状态变i s 。定义 为向量s ，= 0 ，1 = h ，札】，也就是第j 个时钟周期内我们在图中标处观 察到的值。若已知i 时刻的输入珥和i - l 时刻的状态s h ，则i 时刻的输出e 以及 i 时刻的状态s 。是确定的。 。 乙f r 。，、。 7 l j 1 l 并 s 艘厂s 垃广 。 串 7 l - j 一7 l - j 7 变 础础， r换 1 、 7 丫1。4 。， 图卜2 ( 2 ，1 ，2 ) 卷积码编码器 从上述分析中可知：( 2 ，1 ，2 ) 卷积码共有4 种不同的状态：0 0 、0 l 、1 0 、1 1 。对于 任意的( 力，1 ，肌) 卷积码，状态变量包括m 个元素，即s ，= | _ 0 叭，n ，0 川y ，在二 进制编码中，s 。有2 ”种不同的状态。在卷积码的译码算法中，卷积码的状态及 状态的转移成为设计优化译码算法的重要工具。 1 3 信道编码的性能分析方法概述 对于广泛应用的t l l m 及l d p c 码，其性能评估主要包括错误概率的计算和 迭代译码门限的估计。其中错误概率的计算在工程上主要通过蒙特卡罗仿真来计 算。而迭代译码门限则主要通过密度进化【1 10 相关理论来估计。 另外错误概率的估计在理论分析上也有许多研究成果，主要方法包括性能界 【1 1 1 】和加重采样法【1 1 2 。其中性能界在高信噪比时比较接近真实情况，但通常 我们感兴趣的低信噪比区域，就无能为力了。并且性能界的应用需要多个理想假 设，例如最大似然译码，a w g n 信道等实际中难以满足。加重采样多用于确定 系统的极低误码率，它的主要问题则是适应性差，需要对不同系统找到不同的加 重采样函数，而且这一过程是极其复杂的。所以这两种方法主要存在于对于某些 1 4 特定系统的理论分析，工程应用上很难实现。 1 4 论文主要工作及结构安排 本论文的主要研究内容为t u r b o 码和l d p c 码等现代编码的简化译码算法及 其性能分析。主要贡献包括： 一提出了“平方半径谱 的概念。并将这一概念应用于现代编码和系统的 性能分析，大大减小仿真量，同时保证分析准确度。这一概念同样具有 很重要的理论意义，包括可以用来给出近限编码的门限信噪比以及用于 理论分析的错误概率公式。 二提出了基于现有算法的以现代编码为内码的级联编码结构以及对应的译 码算法。该方案在性能和复杂度上都要好于传统的将现代编码作为内码 的级联编码方案。 三给出了一种基于译码器池的并行译码算法，在某些应用场合可以在保证 性能的同时大大提高译码器吞吐量。 下面将本论文以下各章节的内容简要介绍如下： 第二章主要介绍了t u r b o 码和l d p c 码的编译码算法以及相应的简化译码算 法，在此基础上提出了基于译码器池的并行译码方案以及一种新的级联编码结构 和对应的译码算法。 第三章主要介绍了现有的针对t u r b o 码和l d p c 码的性能分析工具，即e x i t 图，包括原理和实际应用中的方法并给出分析结果。另外对具有比较重要理论价 值的性能界和加重采样法做了简要说明。 第四章详细介绍了本文所提出的s r - p d f 的概念以及相关的渐进特性和理 论及实际应用价值。通过与e x i t 图的仿真结果对比验证了s r p d f 的合理性与 准确。同时通过对比s r - p d f 与传统的蒙特卡罗仿真得到的系统错误概率验证了 s r - p d f 在系统错误概率计算上的价值。 第五章对全文做出总结。 1 5 1 5 本章参考文献 【1 - 1 】c b e r r o ，a g l a v i e u x a n d p t h i t i m a j s h i m a , n e a r s h a n n o nl i m i t e r r o r - c o r r e c t i n gc o d i n ga n dd e c o d i n g ：t u r b o - c o d e s i np r o e i e e ei n t c o n f c o m m u n ( i c e 9 3 ) ，g e n e v a , s w i t z e r l a n d , m a y1 9 9 3 ，p p 1 0 “一1 0 7 0 【1 - 2 】e v a l u a t i o nr e p o r tb yt h ee u r o p e a na g e n c yi m t - 2 0 0 0s a t a l i t er i te v a l u a t i o n c o m m i t e e s e t s i ，1 9 9 8 【1 - 3 】c d m a2 0 0 0r 1 盯c a n d i d a t es u b m i s s i o nt oi t u - r ，t r 4 5 ，t i a ，1 9 9 8 【l 卅r gg a l l a g e r , “l o w - d e n s i t yp a r i t y c h e c kc o d e ，”i r et r a n s i n f o r mt h e o r y ， v 0 1 i t - 8 ，p p 2 1 - 2 8 ，j a n1 9 6 2 【1 - 5 】n w i b e r g ，“c o d e sa n dd e c o d i n g o ng e n e r a l g r a p h s ，”p h d d i s s e r t a t i o n ， l i n k o p i n gu n i v ，l i n k o p i n g ，s w e d e n ，19 9 6 【1 - 6 】x yh u ，e e l e f t h e r i o u ，d m a r n o l da n da d h o l a k i a ，“e f f i c i e n t i m p l e m e n t a t i o no ft h es u m - p r o d u c ta l g o r i t h mf o rd e c o d i n gl d p cc o d e s ，i n p r o c i e e eg l o b e c o m , s a na n t o n i o ，t x ，n o v , 2 0 01 ，p p 10 3 6 - 10 3 6 e 【l - 7 】c e s h a n n o n ，“t h em 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 ，”b e l ls y s t e m t e c h n i c a lj o u r n a l ，v 0 1 2 7 ，p p 3 7 9 4 2 3a n dp p 6 2 3 - 6 5 6 ，o c t19 4 8 【1 - 8 】s t e p h e ngw i l s o n ，“d i g i t a lm o d u l a t i o na n dc o d i n g ，”b yp r e n t i c e h a l l ， i n e 1 9 9 6 ，p p 8 8 1 2 3 【1 - 9 】s - yc h u n g ，gd f o r n e y , j r ，t j r i c h a r d s o n , a n dr u r b a n k e ，“o nt h ed e s i g n o fl o w - d e n s i t yp a r i t y c h e c kc o d e sw i t h i n0 0 0 4 5 d b o ft h es h a n n o nl i m i t ，i e e e c o m m u n l e t t ，v 0 1 4 ，p p 6 2 - 6 4 ，f e b 2 0 0 0 【1 - 10 】d a r i u s hd i v s a l a r , s a m u e ld o l i n a r , a n df a b f i z i op o l l a r a , ”i t e r a t i v et u r b o d e c o d e ra n a l y s i sb a s e do n d e n s i t y e v o l u t i o n ”i e e ej o u r n a lo n s e l e c t e da r e a si nc o m m u n i c a t i o n s ，v o l 19 ，n o 5 ，m a y2 0 01 【l - 11 】d d i v s a l a r , s d o l i n a r , ep o l l a r a ，a n dr j m c e l i e c e ，“t r a n s f e rf u n c t i o n b o u n d so nt h ep e r f o r m a n c eo ft u r b oc o d e sp a s a d e n a , ”c a ：j e tp r o p u l s i o nl a b ， t d a p r o g r r e p 4 2 - 12 2 ，p p 4 4 5 5 ，a u g 15 ，19 9 5 【1 - 1 2 j a b u c k l e w , l a r g e d e v i a t i o nt e c h n i q u e si nd e c i s i o n , s i m u l a t i o n ，a n d e s t i m a t i o n ，w i l e ys e r i e si np r o b a n dm a t h s t a t ，19 9 0 1 6 第二章t u r b o 码与l d p c 码译码算法的研究 本章重点介绍了t u r b o 码与l d p c 码的经典算法以及现有的改进型简化译码 算法。同时提出了在现有算法的基础上针对t u r b o 码和l d p c 码的并行译码算法。 本章另一个重点是提出了基于此类强纠错码的一种级联编码方案与对应的译码 算法。相对于传统级联编码，新提出的算法在复杂度和性能上都有所改善。 2 1t u r b o 码的编译码算法 t u r b o 码之所以能够获得如此之好的性能，是因为它在工程上基本实现了证 明信道编码定理时所需的三个条件，而其中最为关键的是引入了随机编译码的思 想 2 。1 】。虽然真正意义上的随机编译码是不可实现的，但可以通过伪随机编译码 来渐进实现随机编码。在t u r b o 码中就是通过伪随机交织器来实现的。需要指 出的是，t u r b o 码能获得逼近s h a n n o n 界的优异性能，并不只是因为引入了随机 编译码的思想，在译码过程中的反馈迭代译码思想也具有重要意义。这种思想被 广泛应用于均衡及多天线等众多领域【2 2 】 2 5 】。本文将以广泛使用的并行级联 t u r b o 码为例介绍t u r b o 码的编译码算法。 2 1 1t u r b o 码编码器 t u r b o 码编码器结构如图2 1 所示，信息序列u 被分成三部分：直接输入复 用器x 5 、经成员编码器( r s c i ) 再经过删除器输入复用器x 川、经过交织器再 经过编码器( r s c i i ) 通过删除器再输入复用器x 弘。其中经过两个编码器i i