（通信与信息系统专业论文）ldpc编码的性能分析和实现算法.pdf

哈尔滨t 程大学硕七学竹论文 摘要 l d p c ( l o wd e n s i t yp a r i t yc h e c k ) 码是一类用非常稀疏的校验矩阵或二分 图定义的线性分组纠错码，最初由g a l l a g e r 发现，故亦称g a l l a g e r 码。这种 码采用b p 叠代译码，比如和乘积算法，可以实现非常好的纠错性能。u ) 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 码的基本概念、构造 方法、编码算法以及译码算法。在编码算法里详细讨论了传统的编码算法以 及e f f i c i e n t 编码算法。在译码算法里介绍了m p 算法集的基本原理和译码性 能最好的和乘积译码算法。接着介绍了一种改进后的l d p c 编码算法，该算 法先通过r i c h a r d s o n 和u r b a n k e 提出的e 伍c i e n t 编码算法对l d p c 码的校验 矩阵优化，然后再主要研究其二分图中长度为4 的短环，提出了一种校验矩 阵日的消4 一环算法。采用m a t l a b 完成了此算法的程序设计。采用此算法后 可避免l d p c 码译码过程中的重复迭代，显著提高了l d p c 码的误比特率性 能。同时对不同参数对l d p c 码性能的影响进行了仿真，得到了一些结论。 最后，利用v h d l 语言在复杂可编程逻辑器件( c p l d ) 上完成了l d p c 码 编码器的硬件实现。 关键词：纠错码；u ) p c 码；迭代译码；贪婪算法；短环；v h d l 哈尔滨t 程大学硕十学位论文 a b s t r a c t l d p c ( l o wd e n s i t yp a r i t yc h e c k ) c o d ei sak i n do fl i n e a rb l o c kc o d et h a t d e f i n e db yv e r ys p a r s ep a r i t ym a t r i xo rt a n n e rg r a p h , a n di ti sa l s oc a l l e dg a l l a g e r c o d es i n c eg a l l a g e ri n i t i a l l yp r e s e n t e di t l d p cc o d ew e r er e d i s c o v e r e da n d s h o w nt of o r mac l a s so fs h a n n o n - l i m i t - a p p r o a c h i n gc o d e si nt h el a t e1 9 9 0 s t h e s ec o d e s ，d e c o d e dw i t hi t e m t i v ed e c o d i n gb a s e do nb e l i e f p r o p a g a t i o n , s u c ha s t h es u m - p r o d u c ta l g o r i t h m , a c h i e v ea m a z i n g l yg o o de r r o fp e r f o r m a n c e e v e r s i n c et h e i rr e d i s c o v e r y , d e s i g n , c o n s t r u c t i o n ，d e c o d i n g , e f f i c i e n te n c o d i n g , p e r f o r m a n c ea n a l y s i s a n da p p l i c a t i o n so ft h e s ec o d e smd i g i t a lc o m m u n i c a t i o n a n ds t o r a g es y s t e m sh a v eb e c o m et h ef o c a lp o i n t so f r e s e a r c h l d p cc o d eb e l o n g st ot h el i n e a rb l o c kc o d ew h i c hi se n c o d e db yt h e i n f o r m a t i o ns e q u e n c em u l t i p l i e sg e n e r a t o rm a t r i x a l t h o u g ht h ep a r i t y - c h e c k m a t r i xo fl d p cc o d ei ss p a r s e ，t h eg e n e r a t o rm a t r i xi sn o t t h ee n c o d i n g c o m p l e x i t yo fi ti sl i n e a r l yp r o p o r t i o n a lt ot h es q u a r eo fc o d el e n 垂h t h ec o d e l e n g t hi sv e r yl a r g ew h e ni tb eu s e d a l s o ，as i g n i f i c a n ta m o u n to fm e m o f yi s n d e dt os t o r et h e i rp a r i t y c h e c km a t r i c e s i nt h i sw a y , t h ee n c o d i n gp r o b l e mo f l d p cc o d e sm a yb ea l lo b s t a c l ef o rt h e i ra p p l i c a t i o n sb e c a u s et h e yh a v eh i 曲 e n c o d i n gc o m p l e x i t y t h i sp a p e rm a i n l ys t u d i e se n c o d i n gp r o b l e mo fl d p c c o d e s f i r s t l y , t h ep a p a ri n t r o d u c e s t h ef u n d a m e n t a lp r i n c i p l eo fl d p cc o d e ， i n c l u d i n gl d p cc o d e sb a s i cc o n c e p t i o n , c o n s t r u c t i o n , e n c o d i n ga n dd e c o d i n g a l g o r i t h m t h e n d i s c u s s e sc o n v e n t i o n a l e n c o d i n ga l g o r i t h m a n de f f i c i e n t e n c o d i n ga l g o r i t h m , a n de x p a t i a t e st h ep r i n c i p l eo fm e s s a g ep 嬲s i n ga n ds p a w h i c hh a st h eb e s tp e r f o r m a n c ei nd e c o d i n ga l g o r i t h m s e c o n d l y , t h i sp a p e r i n t r o d u c e sak i n d o fo p t i m i z e dc o d ea l g o r i t h m ，f i r s tu s e st h ee f f i c i e n tc o d e a l g o r i t h mw h i c hp r o p o s e db yr i c h a r d s o na n du r b a n k eo p t i n l i 猫t h el d p cc o d e c h e c km a t r i x ，t h e nm a i n l ys t u d i e so nt h e4 一c i r c l ei ni t sb i p a r t i t eg r a p h , 掣o p o 辩s 哈尔滨r 程大学硕十学位论文 ak i n do fa l g o r i t h mc a n c e l st h e4 - c i r c l ei nt h ec h e c km a t r i x , r e a l i z e si t sp r o g r a m d e s i g ni na m a l g a m a t i o np r o g r a mf a s h i o no fm a t l a b i ta v o i d st h er e p e a t e d i t e r a t i o ni nt h ed e c o d i n gp r o c e s so fl d p cc o d e sa n dn o t i c e a b l yi m p r o v e st h eb i t f f f f o rr a t i oc a p a b i l i t yo fs h o r tf r d l l l el d p cc o d e s m o r e o v e r , i ta n a l y z e sd i f f e r e n t p a r a n a e t e r sf o rt h ep e r f o r m a n c eo f l d p cc o d e sa n dd r a w ss o m ec o n c l u s i o n s l a s t , t h i s p a p e rr e a l i z e st h ew h o l el d p ce n c o d e ru s i n gv h d ll a n g u a g eb a s e do n c p l d k e yw o r d s ：e r r o rc o r r e c t i n gc o d e ；l d p cc o d e ；i t e r a t i v ed e c o d i n g ；g r e e d y a l g o r i t h m ；s h o r tc i r c l e ；v h d l 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指 导下，由作者本人独立完成的。有关观点、方法、数据 和文献的引用已在文中指出，并与参考文献相对应。除 文中已注明引用的内容外，本论文不包含任何其他个人 或集体已经公开发表的作品成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：至照盛 e l 期：渊年，月彰日 哈尔滨t 程大学硕十学位论文 第1 章绪论 1 1 研究的背景及意义 在数字信号传输过程中，数据在信道中的传输会受到噪声的干扰。噪声 对信号的干扰作用，其实质就是破坏了信号的内部结构，产生畸变从而造成 信息的损失。为了使信号具有较强的抗噪声干扰的能力，需要对信号加以改 造，使信号内部结构具有更强的规律性或相关性，以保证在噪声干扰下，信 号的部分结构遭破坏时，仍能根据信号原有的内在规律性和相关性来发现错 误，甚至纠正错误，恢复原来的信息。也就是利用增加的冗余来换取抗干扰 性地提高。这就是抗干扰的基本思想，也是信道编码的宗旨。 在1 9 4 8 年，s h a n n o n 就提出了信道编码定理，界定了纠错编码的性能。 然而在1 9 9 3 年以前，实际使用的编码方式在接近s h a n n o n 限之前，性能就开 始急剧下降，更别说达到了。b e r r o u 等在1 9 9 3 年提出的t u r b o 码，性能接近 了s h a n n o n 限，这标志着信道编码理论进入了一个新的阶段。不久，m a c k a y 和n e a l 重新发现l d p c 码和t u r b o 码有着相似的优秀性能，而且在某些方面 已经超过了t u r b o 码。之后l d p c 码得到大家的关注，成为新的研究热点。 目前，在t u r b o 码研究的巨大成功的带动下，m a c k a y 等人重新研究了 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 码在磁记录信道、数字 用户线( d s l ) 、移动和固定无线通信以及数字图像水印等方面也有着广泛的 应用。所以对l d p c 码的性能进行进一步的论证和改进对通信传输领域有着 深远的意义。 哈尔滨t 程大学硕十学位论文 由于l d p c 码属于线性分组码，其编码过程一般采用线性分组码的通用 编码方法，即由信息序列根据码的生成矩阵来求相应的码字序列。尽管l d p c 码的校验矩阵是非常稀疏的，但它的生成矩阵却并不稀疏，这使得其编码复 杂度往往与其码长的平方成正比。l d p c 码在应用时选定的码长很长而且编 码实现时所需的用于存储的寄存器数量非常多。因此，相对于l d p c 码的译 码来说，它的编码复杂度特别大，成为应用的一个障碍。本课题主要针对 l d p c 码的编码问题进行研究。 1 2 通信系统的组成 在人类社会中，人与人之间要经常互通情报，交换消息，从一般意义上 讲这就是通信。因此，简单地说，通信就是互通信息。 通信系统的一般模型如图1 1 所示。 图1 1 通信系统的基本模型 从图1 1 可以看出，信息从信源发出，通过信道来传递，信道就是沟通 信源与信宿的通路或通道。因此，图1 1 中信源、信道、信宿就可以构成通 信系统的简单模型，从而完成信息传递的任务。 在通常情况下，为了使信息在信道中有效地传递，往往在发端要对信息 进行必要地加工或处理，统称为变换。在收端，为了还原信息，相应地要进 行反变换。信息的变换和反变换则包括各种各样的终端处理设备，通常包括 能量变换、编码与译码、调制和解调等过程。 编码是一种变换过程，主要的目的有两个：一种是为了改善信息的传输 效率，一种是为了提高信息传输的可靠性。前者称为有效性编码，主要针对 信源特性进行处理，所以有时也称为信源编码。后者称为可靠性编码或者抗 干扰编码，它主要是针对信道特性进行处理，所以有时也称为信道编码。 本文主要研究信道编码。半个多世纪以来，伴随通信技术的飞速发展及 各种传输方式对可靠性要求的不断提高，信道编码作为抗干扰技术的一种重 2 哈尔滨t 程大学硕士学付论文 要手段，在数字通信技术领域中和数字传输领域中显示出愈来愈重要的作用。 1 3 信道模型 为了更好的从数学上描述一个通信系统，我们可以把传送信号的物理信 道抽象为数学的信道模型，也只有在同一信道模型下，对通信系统其他部分 的讨论才有意义。本节将讨论三种最简单、最常用的信道。 为了更好的描述一个信道，我们一般可以从输入、输出和转移规则三个 方面来着手。一般而言信道的输入x 和输出y 都是随机变量，我们假设这些 随机变量的样本空间和分布规律都是已知或可以确定的。转移规则的表示可 以有很多的方式，如果输入、输出的样本空间都是有限集合，我们可以用转 移概率矩阵来表示；我们也可以用随机变量的函数来描述一个转移规则。 对于信道而言，信道容量是一个十分重要的参数。信道容量的概念最初 是由香农提出的：信道容量c 定义为输出l ，为输入x 提供的最大平均互信息 量： c = 嘴“x ；d = 搿莓莩p ( x ) p ( y l j ) l o g 号移产 ( 1 一1 ) 其中，以x ) = p ( x = x ) o r p ( x ) = l 。如果以2 为底数，c 的单位是 比特符号( b i t s y m b 0 1 ) ，表示信道上每符号能传送的比特数；如果每隔f 秒 输入一个符号，那么信道容量的单位是f 比特秒( b i f f s ，b p s ) 。 1 3 1 二进制删除信道和二进制对称信道 对于图1 3 所示的通信模型，如果检、纠错码编码器和编码信道的输出 c 和只是二进制序列，那么我们可以用信道转移概率矩阵p 来描述该信道。 肛 笼钢= 1 繁1 t 兔 ( 1 - 2 ) 其中，最。和毋。分别是0 错为1 的概率p ( 冠= l ic f = o ) 和l 错为0 的概率 p ( 置= o i q = 1 ) ，珞和墨分别为发送0 和发送1 时，正确传输的概率。如果 晶i = = ，其中o s 1 2 ，则称这种信道为二进制对称信道( b s c ) ， 哈尔滨t 稃大学硕十学位论文 可以表示为图1 2 ( a ) 的形式。显然，这种信道是无i 己忆信道，即错误的出 现不具有相关性。 考虑一种更简单的情形。如果我们仅仅对已知正确的位置输出0 或者l ， 对于没有把握正确的位置，我们并不勉强做出判断，而是只是输出一个待定 的符号“工”，成为删除符号。假设在发送0 或1 的情况下，出现删除的概率 相等都为q ( o q s l ，2 ) ，那么我们把这种信道模型成为二进制删除信道 ( b e c ) ，如图1 2 ( b ) 。可以看出，尽管输出随机变量的样本空间要大一 些，但是实际上二进制删除信道要比二迸制对称信道更简单，同时，二进制 删除信道也属于无记忆信道。 。o o i x = + 1 ) 吧o 一 = j p ( ) ，i x = 一1 ) 方= j e ( y l x = + d d y ( 卜l o ) = 圭咖( 船 因此，我们可以作出b p s k 在高斯信道中的误码率曲线图，如图2 1 所示。 高斯信道的信道容量由下面的式子给出： 巴2 胁g ( 1 + 赢- ) 卜i i ) 其中，只是符号功率，单位为瓦特( w a t t ) ；b 是信道所能提供的带宽，单 位为赫兹( h z ) 。 1 4 信道编码的发展及l d p c 码研究现状 1 4 1 信道编码的发展 从1 9 4 8 年香农( s h a n n o n ) 在他的开创性论文“通信的数学理论”中首次阐 明了在有扰信道中实现可靠通信的方法并提出了著名的有扰信道编码定理至 今，信道编码无论是在理论还是在实际中都得到了飞速发展，其发展过程大 致分为以下几个阶段： 1 5 0 年代至6 0 年代初，主要研究各种有效的编、译码方法，奠定了线 性分组码的理论基础；提出了著名的b c h 码、r s 码以及卷积码的序列译码； 给出了纠错码的基本性能限；还出版了纠错码的第一本专著。这是纠错码从 无到有得到迅速发展的年代。 2 6 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期。不仅 提出了许多有效的编译码方法，如门限译码、迭代译码、软判决译码和卷积 码的维特比( v i t e r b i ) 译码等。而且注意到了纠错码的实用化问题，讨论了与实 用有关的各种问题，如码的重量分布、译码错误概率和不可检错误概率的计 算、信道的模型化等，所有这些问题的研究为纠错码的使用打下了坚实基础。 3 7 0 年代初至8 0 年代，这是纠错码发展史中具有极其重要意义的时期。 在理论上以戈帕( g o p p a ) 为首的一批学者，构造了一类g o p p a 码，其中一类子 6 哈尔滨r 稃大学硕十学位论文 码能达到香农在信道编码定理中所提出的码香农码所能达到的性能，由 于译码复杂度过高而没有得到广泛应用，但这引起了一批学者对代数几何码 的研究兴趣。在这期间大规模集成电路和微机的迅速进展，为纠错码的实用 打下了坚实的物质基础，因而与实用相关的各种技术及有关问题得到了极大 关注，并在实用中取得了巨大成功。1 9 8 2 年，u n g e r b o e c k 将卷积码和调制 技术结合成一个整体进行设计，提出了网格编码调制技术( t r e l l i s c o d e d m o d u l a t i o n , t c m ) ，这一成果对带宽受限中的编码调制技术的发展具有 划时代的意义，在现代通信系统中获得了广泛的应用。 4 1 9 9 3 年，b 盯r o u 等人提出的t u r b o 码被看作信道编码理论研究的重要 里程碑。b e r r o u 等人将卷积码和随机交织器相结合，同时采用软输出迭代译 码来逼近最大似然译码，取得了超乎寻常的优异性能和可以接受的编译码复 杂度。在a w g n 信道中，采用b p s k 调制的1 2 码率t u r b o 码，用大小为 6 5 5 3 5 的随机交织器进行交织和1 8 次迭代译码的情况下，在信噪比 岛o = 0 7 船时，误码率可以达到1 0 一，t u r b o 码的性能一举超越了截止速 率，并且逼近了香农容量限，是一种信道编码理论界一直梦寐以求的可实用 好码，它的出现标志着信道编码理论研究进入了一个崭新的阶段。随着对 t u r b o 码研究的深入，人们重新发现g a l l a g e r 早在1 9 6 2 年提出的 l d p c ( l o w - d e n s i t yp a r i t y - c h e c k ) 码亦是一种具有渐进特性的好码。 1 4 2l d p c 码研究现状 l d p c 码是一类线性分组纠错码，最早由g a l l a g e r 在1 9 6 2 年提出。后来 的3 0 年里，l d p c 码一直处于被遗忘的角落，直到2 0 世纪9 0 年代的中后期， m a c k a y 和n e a l 将其重新带人人们的视线。通过大量的仿真，m a c k a y 等人 表明，和t u r b o 码一样，l d p c 码也具有近香农限的性质。 m a c k a y 、l u b y 提出的不规则l d p c 码将l d p c 码的概念推广。不规则 l d p c 码的性能不仅优于规则l d p c 码，甚至还优于t u r b o 码的性能，是目前 已知的最接近香农限的码。 r i c h a r d s o n 和u r b a n k 也为l d p c 码的发展做出了巨大的贡献。首先，他 们提出了一种新的编码算法，在很大程度上减轻了随机构造的l d p c 码在编 码上的巨大运算量需求和存储量需求。其次，他们发明了密度进化理论，能 哈尔滨t 稃大学硕士学位论文 够有效的分析出一大类l d p c 译码算法的性能限。仿真结果表明，这是一个 非常紧的性能限。最后，密度进化理论还可以用于指导不规则l d p c 码的设 计，以获得尽可能优秀的性能。 k o u 和l i n 等人从代数、几何理论着手，用确定性算法构造出了性能也 很好的l d p c 码。这一类l d p c 码一般都是规则码，和随机构造的规则l d p c 码相比较，尽管性能上有很小的损失，但是也非常受关注，主要是由于以下 几个方面的优点： 1 具有严谨的数学结构，构造和性能分析更加精确，甚至最小汉明距离 的准确计算都是可能的。 2 和随机构造的l d p c 码相比，具有更低的错误平层( e r r o rf l o o r ) ， 可以应用于有线通信、深空通信以及磁盘存储工业等对误码率要求更加苛刻 的场合。 3 可以具有循环( c y c l i c ) 或者准循环( q u a s i - c y c l i c ) 的结构，极大的 减低编码复杂度，也为译码提供了更加方便的选择。 工业界也已经有l d p c 编译码芯片问世。其中，处于领先地位的f l a r i o n 司推出的基于a s i c 的v e c t o r - l d p c 解决方案使用了约2 6 0 万门，内存为 1 9 0 k b ，最高可以支持5 0 0 0 0 的码长，0 9 的码率，最大迭代次数为1 0 ，译 码器可以达到1 0 g b p s 的吞吐量，其性能已经非常接近香农限，可以满足目 前大多数通信业务的需求。a h a 公司、d i g i t a lf o u n t a i n 公司也都推出了自己 的编译码解决方案。 总之，目前l d p c 码的研究、实现和应用是编码领域中的一个热点课题。 1 5 论文研究的主要内容 本文主要针对l d p c 码的编码问题进行研究。首先介绍了l d p c 码的基 本原理，包括l d p c 码的基本概念、构造方法、编码算法以及译码算法。在 编码算法里详细讨论了传统的编码算法以及e f f i c i e n t 编码算法。在译码算法 里介绍了m p 算法集的基本原理和译码性能最好的和乘积译码算法。接着介 绍了一种改进后的l d p c 编码算法。该算法先通过r i c h a r d s o n 和u r b a n k e 提 出的e f f i c i e n t 编码算法对l d p c 码的校验矩阵优化，然后再主要研究其二分 8 哈尔滨工稃大学硕十学位论文 图中长度为4 的短环，提出了一种校验矩阵h 的消4 环算法。采用m a n a b 完成了此算法的程序设计。采用此算法后可避免l d p c 码译码过程中的重复 迭代，显著提高了l d p c 码的误比特率性能。同时对不同参数对l d p c 码性 能的影响进行了仿真，得到了一些结论。最后，利用v h d l 语言在复杂可编 程逻辑器件( c p l d ) 上完成了l d p c 码编码器的硬件实现。 本论文研究的主要内容如下： 第1 章绪论，简单的介绍本课题的研究背景与意义，对通信系统的组成 及信道模型进行了介绍，并介绍了信道编码的发展及l d p c 码的研究现状。 第2 章先分别简要介绍了香浓编码定理及线性分组码的理论及其编译码 算法。然后主要介绍l d p c 码的定义与结构，讨论了l d p c 码的一些基本性 质。最后介绍了l d p c 码的环、l d p c 码中的环对编码特性的影响及如何消 除其中的短环。 第3 章首先介绍了l d p c 码的一些基本构造方法，在此基础上讨论了 l d p c 码的编码原理，在分析了传统算法的基础上，详细阐述了快速算法 e f f i e i e n t 算法的原理；最后简要说明了l d p c 码的译码原理。 第4 章提出了一种优化的l d p c 编码算法。首先利用e f f i c i e n t 算法对 l d p c 码的校验矩阵进行处理，使编码复杂度的大大降低，将编码复杂度控 制为与码长呈线性关系数量级；再将处理后的校验矩阵进行去环操作，消除 l d p c 码二分图中存在的短环，提出了一种l d p c 码校验矩阵的消4 一环生成 算法，从而即降低了编码的复杂度又提高了译码效率。最后采用m a t l a b 对编 码算法进行仿真。 第5 章使用i s e 8 1 开发工具，通过v h d l 语言编程的方法实现了l d p c 码编码器的硬件设计。选用的是x c 9 5 0 0 。系列的x c 9 5 1 4 4 x l 一1 0 芯片进行 仿真设计，仿真结果表明该编码器设计的正确性和合理性。 9 哈尔滨下稃大学硕十学位论文 第2 章信道编码定理及l d p c 码简介 2 1 信道编码定理 香农信道编码定理： l 、每个信道具有确定的信道容量c 如。，对于任何小于c 乩。的传输速 率月，存在码长为行的码，若采用最大似然译码，则随着码长行的增加，其 译码错误概率只可以任意的小。 2 、( 逆定理) 对于任何大于c ( 。的传输速率置，不论使用何种编译码 方法，错误概率始终会大于某个常数。 下面，我们在高斯信道环境下，对此定理作深入的讨论。对于某个码长 为丹，信息位长度为t 的码，其码率为r = k n 。假设传送一个一长码字所用 的时间为f 秒，在带宽为口的情况下，根据n y q u i s t 定理，至少有： 2口=盟(2-1) 而信息传输速率为r = k r ( b i t s s ) ，所以r = 七f = 2 b r 。根据信道编码 定理和高斯信道容量，有： 92(1+南=bl092(1+静(2-2)2br b l o gb l o g ：( 1 + 蔚22 ( “督 因此，我们可以得到： “l l o g ( 1 坩2 静 ( 2 q ) 我们可以把( 2 3 ) 式改写为： 务等( 2 - 4 ) 在上面的式子中令，趋近于0 ，即是信息传输速率趋近于0 ，得到历o 等于一1 6 d b ，这就是在无限带宽的高斯信道中进行可靠传输时，信噪比的下 限。也就是说，即使增加带宽到无限大，信道容量仍然是有限的。如果我们 l o 哈尔滨t 稃大学硕七学t i ) ：论文 只希望错误概率小于某个值，那么，( 2 - 4 ) 式可以修正为： 争学 ( 2 - 5 ) 于是，由信道编码定理确定昂0 的下限，我们可以得到在不同的码率 下误码率的特性曲线，如图2 1 所示。 2 2 线性分组码 图2 is h a n n o n 限和未编码b p s k 的误码曲线 香农在证明信道编码定理的时候使用的是随机码，其译码相当困难，译 码复杂度是随着刀的增加而指数增加，几乎没有任何实现意义的。因此，我 们必须找到一种码，具有近s h a n n o n 限的特性，并且为了可能实现，其编译 码复杂度最好是和码长拧成线性关系。 要实现香农的这一理论结果是相当困难的，而且为了确定信道的极限能 哈尔滨下稃大学硕士学侍论文 力需要知道信道干扰的统计特性。但实际情况下，信道干扰的分布很少可能 是已知的，而且可能随时问而变化。若按主观上预先定的干扰分布设计差错 控制系统会带来很大的问题。所幸的是，我们并不一定需要确知信道统计特 性才能动手设计。通常采用的方法是取某一特定的码，分析在几种确知干扰 类型下的性能，特别是在高斯信道下的性能，并与未编码的结果进行比较， 也与其它编码方法的结果进行比较，来得到有用的结论。这种方法在不涉及 通信系统的设计者和它的有关信道知识条件下，就可以给出明确的结果，从 而使纠错码得到广泛的应用。 有了s h a n n o n 所指出的方向和目标，经过几十年的发展，信道编码已经 取得了很大的成就，总的来说，目前信道编码的种类可以如图2 2 所表示。 图2 2 纠错码分类 接下来，我们将在二元域上讨论分组码和线性分组码。 分组码是信息序列以k 个码元分组，通过编码器将每组的k 元信息按一 定的规律产生m 个冗余码元( 称为校验元或监督元) ，输出长为”= k + m 的一 个码字。因此，每一码字的m 个校验元仅与本组的信息元有关而与别组无关。 分组码用( 玎，k ) 表示，胛表示码长，k 表示信息位数目，r = k n 为码率。 露长序列的可能排列总共有2 种( 每一n 长序列称为i 1 重) ，在二元域上，一个 ( 玎，j | ) 分组码的码字集合只有2 七种，分组编码其实就是以一定的规则从2 开个 刀重选择其中的2 七个开重构成一个许用码的码集c ，而其余的2 一一2 t 个 重 哈尔滨t 稃大学硕七学位论文 为禁用码组。 一 2 2 1 线性分组码的生成矩阵和校验矩阵 任何一个( 开，k ) 分组码，如果其信息元与监督元之间的关系是线性的，即 能用一个线性方程来描述的，就称为线性分组码。线性分组码在所有可能的 分组码中只占很少的一部分，然而，他却几乎是唯一具有实际价值的分组码。 线性分组码是所有纠错码中最基本最容易的一类码，它概念清楚，易于理解， 而且能方便地引出各类编码中广为使用的一些基本参数和名称。因此，线性 分组码成了讨论其他各类码的基础。 ( 后) 线性分组码的每个码字有m 个校验元，要从k 个信息元中求出m 个 校验元，必须有m 个独立的线性方程，根据求校验元的不同线性方程，就得 到不同的( 甩，七) 线性分组码。 因此( ”，七) 线性分组码的编码问题就是如何根据已知的k 个信息元求得 m 个校验元。由于是线性码，它们一定是由m 个线性方程构成的线性方程组。 ( 以，七) 线性分组码的2 七个码字组成竹维向量空间的一个k 维予空间，而线 性空间可由其基底张成，因此( 珂，j j ) 线性分组码的2 七个码字完全可由k 个独 立的向量所组成的基底张成。设k 个基向量为g l ，g 2 ，g ，那么，任何有效 码字都是这七个向量的线性组合，因此令g = 【g l ，g 2 ，q 】r ，则有： c = k x g ( 2 6 ) 其中k = ( 墨，k 2 ，疋) 是k 个信息比特组成的信源向量。由( 2 6 ) 式， 根据输入的信源向量，我们可以求得其相应的码字。g 就被做称为线性分组 码的生成矩阵。很容易知道，码元全部为0 的疗重码字一定是一个有效的码 字。 假设疗维线性空间的另外m 个基为羁，吼， 见。，那么显然有对任意的 码字c ，c h t = 0 。所以，令h = 【，马，e j ，则有： 月c 7 = 0 ( 2 7 ) 由上面的讨论可以看出，对一个线性分组码而言，其生成矩阵g 形式上 并不是唯一的，但是这些生成矩阵都是等价的；同时校验矩阵日形式上也不 是唯一的，但这些校验矩阵也都是等价的。一旦给定某个生成矩阵或者校验 哈尔滨t 程大学硕七学位论文 矩阵，这个线性分组码也就完全被确定。 两个栉重码字之间，对应位置取值不同的总个数，称为这两个珂重码字 之间的汉明距离。一个码字集中任两个码字间的汉明距离的最小值称为该码 的最小汉明距离，记为d m m 或磊。可以证明，( 刀，j i ) 线性分组码的最小距离等 于非零码字的最小重量。一种码的最小汉明距离是一个重要的参数，它决定 了该码的纠错、检错能力。一般而言，最小汉明距离越大，纠错的能力就越 好。( 行，七) 线性分组码的最小距离为磊的充分必要条件是校验矩阵日中，任 意如一l 列线性无关。要确定一个码的最小汉明距离是一个非多项式复杂度 ( 一p ) 问题，对码长很长的情况几乎是不可能做到的。 可以证明，对于一个最小距离为的( h ，七) 线性分组码，其最小汉明距离与 其纠错能力有如下关系： 1 检测e 个随机错误，要求码的最小汉明距离a o e + l ； 2 纠正t 个随机错误，要求a o 2 t + l ； 3 纠正r 个随机错误，同时检测e ( e r ) 个错误，则要求a o t + e + l ； 4 纠正r 个错误和p 个删除，则要求a o 2 t + p + l 。 因此，我们需要构造尽可能大的磊以确保更好的纠错能力。这是任何时 候我们设计码字的通用规则。 2 2 2 线性分组码的伴随式译码 译码器的任务是对发射码字的估计和重建，因此，我们希望尽可能准确 的重建，同时也希望尽可能小的计算复杂度。一般而言，译码器的输入( 或 已知条件) 包括以下三个方面： 1 接收序列胄。接收序列一般是通信系统中前一级模块的输出； 2 发送码集c 。译码器并不知道具体的发送码字，但是必须知道这些发 送码字的所有可能值，也就是发送码集； 3 信道的特征和参数。对译码器而言，信道的特征和参数并不一定是必 须的。但是，如果知道信道的特征和参数，有可能使得译码更加准确。 下面，就以经典的伴随式译码为例，介绍线性分组码的译码。 设发送码字c j 通过有扰信道传输，信道产生的错误图样e ，接收序列 置= c j + e 。以七) 线性分组码的每一码字c l 都必须满足( 2 7 ) 式。因此，对接 1 4 哈尔滨t 稃大学硕+ 学位论文 收序列胄进行检验： h r t = 日( c + d 7 = h e 7 ( 2 8 ) 可见h e r 仅仅与错误图样有关而与发送码字无关。令s = 王次r = h e r ， 称s 为接收序列的伴随式。伴随式完全由错误图样决定，是对信道干扰的充 分反映。因此，线性分组码的伴随式译码可以归结为以下三个步骤： 1 由接收序列r ，计算伴随式s = 舰7 = 月e r ； 2 如果s = 0 ，则认为接收没有错误，否则，由s 找出错误图样e ； 3 由e 和足，确定c = r e ，作为译码输出。 由上面的第2 步可以看出，如果接收序列r 刚好错为另外一个码字，那 么计算出的错误图案为0 ，这个时候尽管是有错误的但是译码器会认为没有 错误，因此就出现了不可检测错误。不可检测错误一般也是由最小汉明距离 太小导致的。不可检测错误带来的后果是译码性能曲线中会出现错误平层的 现象：不论如何增加信噪比，译码后的误码率始终会处于某个数量级上( 例 如l p 或更低) ，这显然是我们所不希望的。 可见，伴随式译码需要确定错误图样与伴随式之间的一一对应关系，因 此需要在译码器中建立译码表。这个表需要存储所有的s ，即是2 m 个m 重 序列。因此对于码长竹的增加，译码表的大小呈指数增加，当码长很长时， 这样的译码算法几乎是没有现实意义的。 2 3l d p c 码的定义与结构 2 3 1l d p c 码的定义 一个码长为、信息位个数为k 的线性分组码可以有一个生成矩阵g 来 定义，信息序列s 通过g 映射成发送序列，也就是码字v = j g 。线性分组码 也可以由一个一致校验矩阵日来等效描述，所有码字均满足v ，= 0 。校验 矩阵的每一行表示一个校验约束q ，其中所有非零元素对应的码元变量v ，构 成一个校验集，用一个校验方程表示；校验矩阵的每一列表示一个码元变量 参与的校验约束，但列元素不为零时，表示该码元变量参与了该行的校验约 柬。 l d p c 码是一种线性分组码，它的名字来源于其校验矩阵的稀疏性，即 哈尔滨：r 程大学硕十学位论文 校验矩阵中只有数量很少的“l ”，大部分都是“o ，。g a l l a g e r 最早给出了正则 l d p c 码的定义，正则l d p c 码的校验矩阵日满足下面三个条件： 1 日的每行有p 个“l ”； 2 日的每列有，个“l ”，五3 ； 3 与码长和h 矩阵的行数m 相比，p 和，都很小。 2 3 2l d p c 码的t a n n e r 图表示 任何一种线形分组码都可以1 表示成为编码二分图( t a n n e r 图) 。l d p c 码的二分图由两类节点组成：变量节点( v a r i a b l en o d e ) 和校验节点( c h e c k n o d e ) ，分别对应于校验矩阵日中的列和m 行。同一个集合内部的节点没 有连线，只有属于不同集合的两点之间可能有连线，每条连线对应于校验 矩阵中的1 。为了方便，我们借用g a l l a g e r 对l d p c 码的表示方法：将码长 为，行重、列重分别为p 和，的l d p c 码称为( n ，p ) l d p c 码。( 2 9 ) 式是某个( 8 ，2 ，4 ) l d p c 码的校验矩阵和相应的校验方程，根据校验矩阵我 们可以画出它的二分图( 图2 3 ) 。图中变量节点集合( m ，v 2 ，吨) 和校验节点 集合( q ，c 2 ，c 4 ) 内部不存在相连的边，但两类节点之问存在着连线。变量节 点和校验节点之间存在连线意味着该变量比特参加了此校验式，也就是校验 矩阵某一行中“1 ”的位置。我们将每个节点上的连线数目称为该节点的次数 ( d e g r e e ) 。图2 3 中，变量节点的次数( 矾) 为2 ，校验节点的次数( 以) 为4 。 r l ll000