（通信与信息系统专业论文）低密度编码技术及其实现研究.pdf

一 中国科学技术大学博士论文摘要 摘要 低密度码( l o w d e n s i t ) ，p 盯i t y c h e c kc o d e s ，l d p cc o d e s ) 是近年来数字通信领 域中的一个研究热点。l d p c 码最早是由g a l l a g e r 在1 9 6 2 年提出，但是由于当 时的硬件水平无法满足l d p c 码编解码器的实现需求，导致l d p c 码在当时并 没有受到一定的重视。2 0 世纪9 0 年代以后，随着硬件发展水平的突飞猛进和软 判决迭代解码技术的成熟，l d p c 码也逐渐开始受到众多学者的关注。人们研 究发现，l d p c 码在采用软判决解码的情况下能够提供逼近s h a n n o n 极限的纠 错性能，同时还具有错误平台低、解码器结构简单以及适合全并行的高速解码 等优点。但是作为一种新兴的信道编码方式，l d p c 码在其正式走向实际应用 之前，必须首先解决在码字构造、编解码算法优化和硬件实现等方面还依然存 在的一些问题。 本文以l d p c 码的实现与系统应用为最终目标，以降低实现复杂度并维持 其纠错性能为原则，对l d p c 码的码字构造、编解码算法设计、f p g a 实现等 领域进行深入研究并取得了一系列研究成果，其中包括一套完整的l d p c 码实 现解决方案。本论文的主要内容可以大致划分为l d p c 码的基础知识、l d p c 码的解码算法、准循环l d p c 码的相关内容以及系统形式l d p c 码的相关内容 四个方面。 本文首先简单介绍了信道编解码技术的发展历史和l d p c 码的主要研究方 向，然后对线性分组码、信道容量、l d p c 码的定义以及一些经典的l d p c 码 构造和编码技术等基础知识进行了阐述，让读者对本论文所涉及的研究领域有 一个基本的认识，从而有助于更好的理解本论文其余部分的内容。 由于l d p c 码的解码算法比较重要，并且在整个l d p c 码研究领域内相对 独立，因此本文对该方向进行了单独的介绍，包括一些经典的l d p c 码解码算 法和作者提出的两种改进的解码算法。作者提出了一种基于加权错误校验的改 进硬判决解码算法，该算法无需利用任何软信息即可实现性能的提升；作者还 分析了传统的置信度传播解码算法和最小和解码算法的特点，结合两者的优点 提出了一种兼顾解码性能和实现复杂度的软判决解码算法。经过研究发现，该 第1 页共1 5 5 页 中国科学技术人学博十论文摘要 解码算法的复杂度远远低于置信度传播解码算法，但是通过合理的参数设置， 却几乎可以提供和置信度传播解码算法同样优秀的性能。 准循环l d p c 码和系统形式l d p c 码是两类特殊的l d p c 码，它们的特殊 结构在降低l d p c 码实现复杂度方面有很大的优势，因此是本文研究的重点。 作者对这两种l d p c 码的相关技术进行了深入的研究，提出了一些优秀的准循 环l d p c 码和系统形式l d p c 码的构造方法，并介绍了它们独特的编解码算法 和硬件实现结构等相关内容。 一 在准循环l d p c 码方面，作者提出了一种高周长的准循环l d p c 码的构造 方法。l d p c 码的校验矩阵周长对其性能有很大的影响，一般周长大于等于6 的l d p c 码才能提供比较好的纠错性能。通常在列重不小于3 的前提下，不易 构造出周长大于等于8 的l d p c 码。作者借助不均衡区组设计的数学方法构造 出了列重等于3 ，且周长大于等于1 0 的准循环l d p c 码，这在当时国际相关研 究领域尚属首次。该码虽然是规则l d p c 码，但凭借其高周长的优势，却具有 不输与非规则l d p c 码的性能。同时，由于它是一种准循环l d p c 码，在编解 码器的设计方面也有一定的优势。 在高周长的准循环l d p c 码基础上，作者又提出了一种准系统形式的分块 循环l d p c 码的构造方法。普通的准循环l d p c 码的校验矩阵具有分块循环的 特性，有助于降低解码复杂度，但是其生成矩阵却是一个密集矩阵，因此编码 器的复杂度依然较高。作者针对这个问题提出了准系统形式的分块循环l d p c 码，由于其校验矩阵的结构特点，只需利用稀疏的校验矩阵即可完成递推编 码，因此其编码器的复杂度比一般的准循环l d p c 码低很多，具有很大的实用 价值。 针对提出的准系统形式的分块循环l d p c 码，作者又提出了两种编码器和 一种解码器的f p g a 实现结构。根据准系统形式的分块循环l d p c 码的校验矩 阵的结构特点，作者提出了一种递推的编码方法，并且采用循环移位寄存器的 方式实现了复杂的矩阵乘法运算，因此大大降低了编码复杂度。根据不同系统 对信道编解码模块的要求，作者分别提出了具有高编码速率和低资源消耗两种 特点的编码器实现结构，这两种结构均能实现g b p s 的编码输出速率。另外，作 者以一种准循环l d p c 码通用的最小和解码器为基础，针对准系统形式的分块 循环l d p c 码校验矩阵的分块特性和三对角线特性，提出了一种准系统形式的 第1 i 页共1 5 5 页 中国科学技术大学博七论文摘要 分块循环l d p c 码专用的改进最小和解码器实现结构。该解码器能实现较高的 解码速率，同时资源消耗比改进前的通用解码器更低。 在系统形式l d p c 码方面，作者提出了一种并行级联结构的系统形式 l d p c 码的构造方法。虽然系统形式l d p c 码的实现复杂度非常低，但其性能 较差( 与同参数的随机l d p c 码相比有4 5 d b 的性能差距) ，因此实用价值不 高。作者针对系统形式l d p c 码性能低下的原因，提出了并行级联结构的系统 形式l d p c 码，通过实现复杂度的少量增加来换取纠错性能的有效提升。研究 发现，该l d p c 码相比同参数的随机l d p c 码只有1 5 d b 左右的性能差距，但 是其编码复杂度与系统形式l d p c 码相当，只有随机l d p c 码的1 0 左右。 作者还提出了一种针对系统形式l d p c 码的最优功率分配方法，并利用半 高斯近似算法对该方法进行了理论分析。作者研究发现，在不改变系统形式 l d p c 码校验矩阵结构的前提下，只需调整发送符号的功率分配方式就能有效 的提升其纠错性能。通过研究系统形式l d p c 码的列重分布特点，作者提出了 一种最优功率分配方法，能够在完全不增加系统开销的前提下有效的提升系统 性能( 最大提升幅度达2 5 d b ) 。这一研究成果对于系统形式l d p c 码在实际 系统中的应用有很大意义。作者还进一步采用半高斯近似算法对不等功率分配 方法进行了理论上的分析，验证了其合理性，为该方向的进一步深入研究提供 了理论支持。 任何优秀的信道纠错码如果无法实现并在实际系统中得到应用，其优秀的 纠错性能都没有太大的意义。本文的研究成果使得l d p c 码在实际系统中的应 用变得更加简单可行，其中的一些构造和优化方法均具有国际领先水平，对其 他研究人员在l d p c 码应用领域的深入研究具有一定借鉴意义。 关键词：低密度码，构造，编码算法，解码算法，准循环，周长，系统形式， 准系统形式，并行级联，功率分配，f p g a 实现，半高斯近似 第1 i i 页共1 5 5 页 中国科学技术大学博士论文 a b s t r a c t a b s t r a c t l o w - d e n s 时p a r i t y c h e c k ( l d p c ) c o d e s i so n eo ft h em o s tp o p u l a rt o p i c si nt h e r e s 黜ha r e ao fd i g i t a lc o m m u n i c a t i o t l si nr e c e n ty e a r s l d p cc o d e sw e r ep r o p o s e d b yg a l l a g e ri nl9 6 0 s ，b u tp e o p l ed i dn o tp a ym u c ha t t e n t i o nt oi t a tt h a tt i m e ，j u s t b e c a u s eo ft l l ep 0 0 rt e c l l l l o l o g ) ，o fc o m p u t e r s 觚dh a r d w a r e s i n c el9 9 0 s ，“t ht h e g r e a ti m 西r 0 v e m e n t so fc o m p u t e r sa n dh a r d w a r e ，l d p cc o d e sh a v eg r a d u a l l yr e g a i n e d t h ei n t e r e s t so fr e s e a r c h e r s p e o p l ef o u n dt h a tl d p cc o d e sh a v em a n ye n c o u r a g i n g c h a r a c t e r i s t i c s ，s u c ha st h e yc a np r o v i d en e a r - c 印a c i t yp e r f l o n n a n c ew i t hv e r yl o w e n d r n o o r ，t h e yh a v ev e 巧s i m p l ed e c o d e rs t m c t u r e s ，w h i c h i ss u i t a b l ef o rm l l y p 龇毽l l e li m p l e m e n t a t i o n ，a n ds oo n b u ta sak i n do fn e we r r o r c o r r e c t i n gc o d e s ，t h e r e a r es t i l lm a n yp r o b l e m ss h o u l db ea d d r e s s e d ，b e f o r el d p cc o d e sc a nb eu t i l i z e di n p r a c t i c a ls y s t e m s t h ea u t h o rh a sb e e n 、v o r 王( i n go nm ec o n s t l l j c t i o n ，e n c o d i n g ，d e c o d i n g ，a n df p g a i m p l e m e n t a t i o no fl d p cc o d e s ，w i t ht h ep r i n c i p l eo fr e d u c i n gt h ei m p l e m e n t a t i o n c o m p l e x 时o fu ) p cc o d e s 、h i l e m a i n t a i n i n g t h e i r g o o dp e 怕n n a n c e s o m e a c l l i e v e m e n t sa b o u tl d p cc o d e sa r ep r o p o s e di n t h j sd i s s e r t a t i o n ，i n c l u d i n ga c o m p l e t es o l u t i o nf o ri m p l e m e n t a t i o no fl d p cc o d e s s o m ep r i m a r ya c h i e v e m e n t so f t l l i sd i s s e n a t i o na r el i s t e db e l o w d e c o d i n ga l g o r i t h mi sav e 巧i m p 6 n a n tp a r ti nt h er e s e a r c ha r e ao fl d p c c o d e s t h ea u t h o rs t u d i e st h ef e a t u r e so fb pa l g o r i n u na n dm sa l g o r i t h m ，t h e np r o p o s ean e w s o r d e c i s i o nd e c o d i n ga l g o r i t h m ，n a m e da s “m z sa l g o “t h m ”t h ep e r f o n n a n c eo f m z s a l g o r i t h mi sa l m o s ta sg o o da st h a to ft h eb pa l g o r i t h m ，b u tw i t hm u c hi o w e r c o m p l e x i t y n eg i n ho fp 撕t yc h e c km a t r i xi sv e d ，c m c i a lf o rt h ep e r f o 肌a n c eo fl d p c c o d e s g e n e r a l l y ，o n l yl d p cc o d e sw i t hg i n hl a r g e rt h a n 4c a np r o v i d eg o o d p e r f 0 舯a 1 1 c e u s u a l l yi ti sn o te a s yt oc 0 i l s t r u c tl d p c c o d e s 、】 r i mg i n hl a 唱e rt h a j l8 ， w i t ht h er e s t r i c t i o nt h a tm ec o l l l m nw e i 曲ti sn o tl e s st h a n3 t h ea u t h o rc o n s t r u c t sa k i n do fq c l d p cc o d e s ，n 锄e da s 3 d l d p cc o d e s ”w i t hg i r i hl a r g e rm a n8a n d c o l l h 玎n 、v e i g h tl a r g e rt h a n3 3d - l d p cc o d e sc a np r o v i d et h es 锄eg o o dp e r f o n n a n c e i u s ta st h ei r r e g u l a rl d p cc o d e sd o ，w h a ti sm o r e ，a sak i n do fq c l d p cc o d e s ，3 d - l d p cc o d e sa l s oh a v es o m ea d v a n t a g e si ni m p l e m e n t a t i o n 第v 页共1 5 5 页 中国科学技术大学博士论文a b s l r a c t q c - l d p cc o d e sa r ev e 拶p o p u l a ri nr e c e n ty e a r s ，b e c a u s et h e i rs p e c i a ls t r u c t u r e s c a nh e l pal o ti nr e d u c i n gt h ei m p l e m e n t a t i o nc o m p l e x i i y t h ea u t h o rp r o p o s e sak i n d o fs p e c i a lq c - l d p cc o d e s ，n a m e da s q s b c l d p cc o d e s ”t h ee n c o d i n gp r o c e s so f q s b c - l d p cc o d e sc a nb ef i n i s h e di nr e c u r s i v ew a yw i t ht h ep a r i t y c h e c km a r i x ，s o t h ec o m p l e x i t yo fe n c o d e r si sv e d ，l o w ，a n dt h ep e r f o n n a j l c eo f q s b c l d p cc o d e si s a l s ov e 叫g o o d t h ea u t h o rb e l i e v e st h a tq s b c - l d p cc o d e si sv e 巧g o o dc a n d i d a t e f o rp r a c t i c a lu t i l i z a t i o n t h ea u t h o ra l s op r o p o s e st 、or e c u r s i v ee n c o d i n gs i r u c t u r e sf 斫t h eq s b c l d p c c o d e sw i t hf p g a t h e s et w o e n c o d i n gs t m c t u r e sa r ee s s e n t i a l l yt h es a m e ，b u tt h e ya r e o p t i m i z e df o rd i f f e r e mg o a l s 0 n ee n c o d i n gs t r u c t u r ei so p t i m i z e df o rh i g he n c o d i n g t h r o u g h p u ta n dt h eo t h e ri sf o rl o wr e s o u r c ec o n s u m p t i o n b o t ht h et w oe n c o d i n g s t m c t u r e sc a np r o v i d ee n c o d i n gt h r o u 曲p u to v e rg b p s a ni m p r o v e dm s ad e c o d e rs t r l l c t u r ef o rf p g ai m p l e m e n t a t i o ni sa l s op r o p o s e d i nt i l i sd i s s e n a t i o n t h ea u t h o rs t u d i e sa g e n e r a lm e m o r ye m c i e n td e c o d e rs t m c t u r ef o r c o n m l o nq c l d p cc o d e s ，a n dm a k e ss o m em o d i f i c a t i o n sa c c o r d i n gt ot h es p e c i a l s t r u c t u r eo ft h ep a r i 够- c h e c km a t r i xo fq c l d p cc o d e s t h ei m p r o v e dm s ad e c o d e r s t r u c t u r ei so n l yf o rq s b c l d p cc o d e s ，a n di tc a np r o v i d eh i g hd e c o d i n gt h r o u g h p u t w i t hl e s sr e s o u r c ec o n s u m p t i o nt h a nt h eg e n e r a lm s ad e c o d e rf o rc o m m o nq c l d p c c o d e s s l d p cc o d ei sak i n d o fs p e c i a ll d p cc o d e s ，w i t hv e 巧l o we n c o d i n g c o 埘l p l e x i t ya n dp o o rp e r f i o m l a n c e a c c o r d i n gt ot h i s ，t h ea u t h o rc o m b i n e st h ep a r a l l e l s t m c t u r ew i t h3 d - l d p cc o d e s ，a n dp r o p o s e st h ep c s l d p cc o d e s t h i sd e s i g nc a n s i g n i 丘c a n t l yd e c r e a s et h ei m p l e m e n t a t i o nc o m p l e x i t y ，w h i l eo n l yt i n yp e r f o m a n c e d e g r a d a t i o ni sf o u n da c c o r d i n gt ot h es i m u l a t i o n s p c s - l d p cc o d ei sv e 拶s u i t a b l e f o r 印p l i c a t i o n si np r a c t i c a ls y s t e m s t h ea u t h o ra l s os t u d i e st h ee f f e c to fu n e q u a lp o w e ra l i o c a t i o nf o rs - l d p cc o d e s ， a n d 百v e ss o m et h e o ua n a l y s i sw i t hs e m i - g a u s s i a na l g o r i t h m t h ea u t h o rf i n d st h a t ， w i t hu n e q u a lp o w e ra l l o c a t i o nm e t h o d ，a no p t i m a lp o w e ra l l o c a t i o np a r a m e t e rc a nb e f o u n d ，a n dt h ep e r f i o m a n c eo fs - l d p cc o d e sc a nb ee f f e c t i v e l ye n h a n c e dw i l ha l m o s t n oc o m p l e x i t yi n c r e m e n tt ot h e 、v h o l es y s t e m a l lt h ee r r o r c o r r e c t i n gc o d e sa r ed e s i g n e df o rp r a c t i c a l 印p l i c a t i o n s ，s oi tw i l lb e m e 砌n g l e s sa n dr e g r e t f h li fak i n do fe r r o r - c o r r e c t i n gc o d e sw i t hg o o dp e r f o n n a n c e c a nn o tb er e a l i z e d t h er e s e a r c hr e s u l t si nt h i sd i s s e r t a t i o nm a k ei te a s i e ra n dm o r e p o s s i b l et o r e a l i z ea n du t i l i z el d p cc o d e si n p r a c f i c a l s y s l e m s ， s o m eo ft h e 第v i 页其1 5 5 页 中国科学技术大学博士论文 a b s t r a c t a c h i e v e m e n t si n t h i sd i s s e n a t i o na r eo fi n t e m a t i o n a ll e v e l t h ea u t h o rb e l i e v e st 1 1 a t t h i sd i s s e r t a t i o nc a nb eg o o dr e f e r e n c ef o r 如r t h e rr e s e a r c hi ni m p l e m e n t a t i o no fl d p c c o d e s 1 ( e yw o r d s ： l d p cc o d e s ，c o n s t l u c t i o n ，e n c o d i n ga l g o r i t h m ，d e c o d i n ga l g o r i t h m ， q u a s i 。c y c l i c ， g i r t h ，s y s t e m a t i c ， q u a s i s y s t e m a t i c ， p a r a u e lc o n c a t e n a t e d ，p o w e r a l l o c a t i o n ，f p g ai m p l e m e n t a t i o n ，s e m i g a u s s i a n 印p r o x i m a t i o n 第v i i 页共1 5 5 页 中国科学技术大学博士论文 插图日录 插图目录 图2 1 二进制a w g n 的信道容量2 l 图2 2 ( 1 6 ，8 ) 规则l d p c 码的t a i m e r 图2 3 图2 3 根据m a c k a y 的构造方法1 构造的( 3 ，6 ) l d p c 码j 2 5 图2 - 4 根据m a c k a y 的构造方法2 构造的l d p c 码2 6 图2 5 近似下三角结构的l d p c 码校验矩阵2 8 图2 6 下三角结构的l d p c 码校验矩阵3 0 图2 7 本文研究内容的关系树状图3 2 图3 一l 基于( 2 7 3 ，1 9 1 ) g a l l a g e r 码的性能比较：3 8 图3 2 妒( z ) 函数示意图4 1 图3 3 六区域划分缈( x ) 以及线性近似方法4 6 图3 4 六区域划分伊( x ) 以及均值近似方法4 7 图3 - 六区域划分的性能曲线比较( 11 2 5 ，6 7 5 ，5 ，3 ) 5 0 图3 6 六区域划分的性能曲线比较( 2 9 8 9 ，1 2 8 1 ，7 ，3 ) 5 1 图3 7 不同区域划分方法的性能曲线( 线性近似) 5 1 图3 8 不同区域划分方法的性能曲线( 均值近似) 5 2 图4 1 长度分别为4 和6 的块循环之间存在数目为2 的交叠5 9 图4 - 2 置换矩阵中的解码软信息存储6 1 图4 - 3q = 4 5 ，r = 5 ，c = 3 的三维网格图6 3 图4 4 一个q 平面和它在尺c 面上对应的直线6 4 图4 - 5 一个q 平面内的平行直线6 4 图4 石q 平面内的直线排列顺序示意图6 5 第x i i i 页共1 5 5 页 中国科学技术大学博+ 论文插图目录 图4 7 ( 6 7 5 ，1 1 2 5 ) 大小的校验矩阵6 5 图4 83 d l d p c 码与m a c k a y 的l d p c 码性能比较6 6 图4 93 d l d p c 码的校验矩阵机和生成矩阵6 7 图4 1 0 大小为1 5 2 5 的宏矩阵h r 6 8 图4 1 l 大小为1 5 1 5 的宏矩阵h r 6 9 图4 1 2 大小为1 5 4 0 的宏矩阵h m ：7 0 图4 1 3 大小为6 7 5 1 8 0 0 的q s b c l d p c 码校验矩阵7 1 图4 1 4 三种l d p c 码的性能比较( 6 7 5 ，1 8 0 0 ，o 6 2 5 ) 7 4 图4 1 5 三种l d p c 码的性能比较( 1 9 9 5 ，6 5 0 0 ，o 7 ) 7 4 图5 - 1 ( 6 7 5 ，1 8 0 0 ，o 6 2 5 ) q s b c l d p c 码编码器结构示意图7 6 图5 2 递推编码模块内部详细结构示意图：7 6 图5 3 高速的可配置同步循环移位寄存器模块：7 8 图5 4 “f u l l s p e e d ”结构的q s b c l d p c 码编码器逻辑框图8 0 图5 5 f u l l s p e e d ”结构编码器的m o d e l s i m 时序仿真波形8 0 图5 6 “l e a s t r e s o u r c e ”结构的q s b c l d p c 码编码器逻辑框图8 1 图5 7 l e a s t r e s o u r c e ”结构编码器的m o d e l s i m 时序仿真波形8 2 图5 8 基于m s a 解码算法的通用解码器结构示意图8 4 图5 9 基于列合并准则存储的h 。矩阵8 6 图5 1 0q s b c l d p c 码的m s a 解码器结构示意图8 7 图5 1lm s a 解码器的时序仿真图9 0 图6 1s l d p c 码的编码序列比特位置错误次数累计9 4 图6 2b c s l d p c 码的相关矩阵9 5 图每3p c s l d p c 编码器结构示意图9 6 图甜p c s l d p c 解码器结构示意图9 6 图6 5 不同类型的交织器性能比较9 9 第x i v 页共1 5 5 页 中国科学技术大学博+ 论文插图目录 图6 6 简化的p c s l d p c 编码器结构示意图1 0 0 图6 7 简化的p c s l d p c 解码器结构示意图1 0 0 图6 _ 8 三种l d p c 码性能比较( 1 0 0 次迭代) _ 1 0 2 图6 9 三种l d p c 码性能比较( 1 0 次迭代) 1 0 2 图6 1 0b c s l d p c 码的编码器结构：1 0 3 图6 1 1 度为5 深度为1 的树状图1 0 6 图6 1 2 度为l 深度为1 的树状图1 0 6 图6 1 3 不同功率分配情况的外信息图转移曲线1 0 9 图6 1 4 一个交点情况下的外信息图解码轨迹11 0 图6 1 5 三个交点情况下的外信息图解码轨迹1 1 1 图6 1 6 三个交点情况下的不同所值所对应的外信息转移曲线1 1 2 图6 1 7 ( 6 0 0 0 ，o 5 ) 的s - l d p c 码的遍历曲线( b e r v s 所) 1 1 4 图6 - 1 8 ( 1 0 0 0 0 ，o 5 ) 的s - l d p c 码的遍历曲线( b e r v sb ) 1 1 4 图6 - 1 9 ( 6 0 0 0 ，o 5 ) 的s - l d p c 码在最优功率分配下的性能1 1 5 图6 - 2 0 ( 1 0 0 0 0 ，o 5 ) 的s l d p c 码在最优功率分配下的性能1 1 6 第x v 页共1 5 5 页 中国科学技术大学博士论文表格目录 表格目录 表2 1 不同码率条件下a w g n 信道的最小信噪比2 1 表2 2c 。的分解计算步骤：2 9 表2 3c ，的分解计算步骤3 0 表3 1 四区域划分的相关参数与近似方法4 8 表3 2 六区域划分的相关参数与近似方法4 9 表3 3 八区域划分的相关参数与近似方法4 9 表3 4 三种解码算法运算量比较( 横向迭代) ：5 3 毒3 - 5 最小区域内的如个数比例。5 4 表4 1 校验矩阵存储空间比较6 0 表4 2q s b c l d p c 码编码器资源消耗估算：7 3 表5 1 两种结构的q s b c l d p c 码编码器比较8 3 表5 2m s a 解码器的资源消耗和速率j 。9 0 表6 ：l 三种l d p c 码的参数1 0 1 表6 2 三种l p d c 码编码器的运算量和存储器估计j 。1 0 4 表6 3 用于仿真的两组s l d p c 码1 1 3 表6 4 ( 6 0 0 0 ，o 5 ) 的s - l d p c 码在不同信噪比条件下的所，叫1 1 5 表6 5 ( 1 0 0 0 0 ，o 5 ) 的s - l d p c 码在不同信噪比条件下的所，叫1 1 5 第x v i i 页共1 5 5 页 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含 任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本 研究所做的贡献均己在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 作者签毫：必 2 删宕年争月22 日 中国科学技术大学博士论文第l 章绪论 章绪论 1 1信道编解码技术的发展史 信道编解码技术的最初起源应该追溯到美国贝尔实验室的s h a n n o n 【1 】在 1 9 4 8 年发表的一篇题为通信的数学理论( am a t h e m a t i c a it h e o d ro f c o i m u i l i c a t i o n ) 的文章。这是一篇关于现代信息理论的奠基性论文，它的发表标 志着信息与编码理论这一学科的创立。s h a i m o n 在该文中指出，任何一个通信 信道都有确定的信道容量c ，如果通信系统所要求的传输速率尺小于c ，则存 在一种编码方法，当码长刀充分大并应用最大似然解码时，信息的错误概率可 以达到任意小，这就是著名的有噪信道编码定理。s h a n n o n 通过该定理给出了 数字通信系统中实现可靠通信的方法以及在特定信道上实现可靠通信的信息传 输速率上限。尽管s h a n n o n 只给出了编码的存在性定理和纠错码的理论极限， 并没有给出具体实现的方法，但他的理论为以后的研究指明了方向和目标。 就在s h a n n o n 提出有噪信道编码定理的同时，h a m m i n g 【2 】和g o l a y 【3 】提出 了第一个实用的差错控制编码方案，使编码理论这个应用数学分支的发展得到 了极大的推动。通常认为h a r n m i n g 提出了第一个差错控制码，他将输入数据每 4 个比特分为一组，然后通过计算这些信息比特的线性组合得到3 个校验比特， 这种编码方法被称为h a m m i n g 码，在早期编码史上具有里程碑意义。由于 h 锄m i n g 码的编码效率较低而且只能纠正一个比特错误，g o l a y 经过研究后提 出了两种以他自己名字命名的码字：一种是二元g o l a y 码，采用1 2 个信息比 特，11 个冗余校验比特的形式，能够纠正3 个错误；另一种是三元g o l a y 码， 它的操作对象是三元符号，采用6 个三元信息符号，5 个三元冗余校验符号的形 式，能够纠正两个错误。 m u l l e r 4 】和r e e d 5 】在1 9 5 4 年分别从布尔代数和多元多项式角度提出了一 类性能良好的二元线性分组码，被称为r e e d m u l l e r 码，简称为i w 码。r m 码 在h 锄m i n g 码和g o l a y 码的基础上前进了一大步，在码字长度和纠错性能方面 具有更强的适应性。i w 码、g 0 1 a y 码和h a n 蛐i n g 码的基本原理相同，因此它 们都存在一些共同的缺点，比如构造出的码字长度都比较短、码字随机性不强 第l 页共1 5 5 页 中国科学技术大学博士论文第1 章绪论 等等。按照s h 锄o n 的信道编码定理的条件来看，这些码字的性能都不会太 好。另外它们都是采用硬判决解码，必然会损失掉一定的软判决增益。 p r a j l g e r 【6 】在1 9 5 7 年提出了循环码的概念。循环码实际上也是一类分组 码，但它的码字具有循环移位特性，即任意一个有效码字经过比特循环移位后 依然是有效码字。循环码也被称为循环冗余校验( c y c l i cr e d u n d a n c yc h e c k ，c r c ) 码，可以采用m e g g i t t 解码器 7 】来实现解码。由于m e g g i t t 解码器的解码复杂度 随着纠错能力的增加而呈指数形式增长，因此c r c 码通常只用作检错码。 循环码的一个非常重要的子集就是分别由h o c q u e n 曲e m 【8 】在1 9 5 9 年， b o 和r a y c h a u d h u r i 研究组 9 】在1 9 6 0 年几乎同时提出的b c h 码( b o s e c h a u d h u r ih o c q u e n 曲e m ，b c h ) 。b c h 码的码字长度为玎= g 埘一1 ，其中加为一个 整数，二元b c h 码的纠错能力上限为f 2 肘一1 1 2 。1 9 6 0 年r e e d 和s o l o m o n 将 、， b c h 码扩展到了非二元的情况，得到了r s 码( r e e d s o l o m o n ，r s ) 【1 0 】。r s 码最 大的优点是其非二元特性可以纠正突发错误。 分组码自从被提出以来，一直是信道编码领域的研究重点，并且在实际通 信系统中得到了广泛的应用。但是分组码由于其本身的特性限制，存在一些较 大的缺陷。首先，分组码是面向数据块的，这一特性必然会导致系统时延的增 加；其次分组码需要精确的帧同步，这对系统的时间和相位同步提出了较高的 要求：最后，分组码在较低信噪比下的纠错性能不佳，而且解码复杂度较高。 鉴于分组码存在的众多缺陷，e l i a s 【l l 】于1 9 5 5 年提出了卷积码，通常记为 ( 刀，七，聊) ，其中刀为码长，j i 为信息源个数，聊是编码寄存长度。卷积码的编 码和解码过程都是连续进行的，这样可以保证其系统时延相对较小。卷积码的 最优解码算法是v i t e r b i 解码算法 1 2 】。卷积码是一种非常优秀的编码方法，在 实际系统中得到了极为广泛的应用，在商业卫星通信系统和移动通信领域中都 采用了卷积码作为其标准编码方式。 2 0 世纪6 0 年代至8 0 年代之间，在信道编码领域涌现了大量的优秀技术。 其中级联码 1 3 】、软判决解码【1 4 和编码调制技术【1 5 ，1 6 】都对信道编码的设计和 发