（通信与信息系统专业论文）ldpc码编译码算法的研究及其在图像传输中的应用.pdf

南京航空航天大学硕士学位论文 i 摘要 gallager 在 1962 年首先提出了一种基于稀疏校验矩阵的线性分组码，称为低密 度奇偶校验（ldpc）码，由于当时计算机水平的局限，人们认为级联码更易于实现 而忽视了 ldpc 码的存在。之后，turbo 码出现并得到了成功的应用。随着计算机能 力的增强和相关理论特别是图论的发展， mackay和 neal重新发现了它，并证明它在 与基于 bp 迭代译码算法相结合的条件下具有非常逼近 shannon限的性能。 ldpc 码和 turbo 码以各自的方式实现接近 shannon 限的这一目标。turbo 码在 低信噪比情况下的性能优于其它各种编码方式。而 ldpc 码的描述简单，具有较大 的灵活性，当码长足够长时具有比 turbo 码更良好的性能，其译码复杂度低于 turbo 码。近年来，ldpc 码以其优异的性能，以及巨大的潜在应用价值而受到编码界的极 大关注，已成为目前最热门的研究领域之一。 本文首先介绍了数字通信系统、信道编码理论的基础知识及纠错码技术；第二 章研究了 ldpc 的基本原理和多种编码算法； 第三章研究了 ldpc 码的 bp 算法和多 种简化算法，分别给出了原理和步骤；第四章仿真并研究了多种简化改进的译码算 法，进行了性能仿真并与 bp 算法进行了比较；第五章，介绍了联合信源信道编码的 基础知识；第六章，将 ldpc 码运用于图像的传输中，对二进制图像和灰度图像传 输做了性能仿真，研究出码率和迭代次数对于图像传输性能的影响；第七章，对于 细节较为丰富的图像，作者提出了一种基于分层图像压缩的联合信源信道编码的新 策略，并在 awgn 信道下对其性能进行了仿真，实验表明，采用这种分层的不等差 错保护方法优于未分层的同等差错保护方法，并且在高压缩比下更好地保留了图像 的纹理特征。 关键词：ldpc 码，bp 译码算法，校验矩阵，联合信源信道，不等差错保护， 图像传输 ldpc 码编译码算法的研究及其在图像传输中的应用 ii abstract in 1962 gallager first proposed a new kind of block code, which was named as low- density parity- check (ldpc) code defined by a sparse parity- check matrix. since the limited resource for the efficient computations at that time, people may incorrectly think that the concatenated codes were more efficient for the purpose of general error correction so that ldpc codes had been ignored for decades. however, after the advent of turbo codes and the extremely successful applications, ldpc codes were rediscovered by mackay and neal during the past decade by the aid of modern computer science and technologies and the rapid development of some related powerful theories, especially for the graph theories. it has been proved that the performance of ldpc codes is very close to the shannon limits when combined with an iterative belief- propagation- based decoder. ldpc codes and turbo codes are similar in many aspects; both can extremely approach to the shannon limits by their unique ways. the performance of turbo codes is better than any other codes at low snr. while ldpc codes are relatively easy to be characterized, and can outperform turbo codes with sufficiently long block lengths. its decoding complexity is also lower than turbo codes. in recent years, ldpc codes have attracted the worldwide attentions in the information theory and channel coding communities due to its impressive performance and great potentials in application. this thesis first introduces the fundamentals of digital communication and channel coding theory, and presents the state- of- the- art development of error- correcting code. in chapter 2, we give a research on the basic principles and several encoding algorithms for ldpc codes.chapter 3 maily focuses on bp algorithm and several other decoding algorithms, presenting the principles and reduced- complexity decoding approaches. in chapter 4, simulation results of reduced- complexity decoding approaches are abtained over an awgn channel, and the results are compared with the traditional bp algorithm results. chapter 5 introduces the basic concepts of joint source and channel coding. in chapter 6, we obtain simulations results of the applications of ldpc codes in the binary system and gray image transmission, and give the infection of code rate and iteration times to the image transmission performance. chapter 7, for the image with abundant textures, author proposes a new joint source- channel coding scheme with combination of multi- layered image coding and unequal error protection (uep) of ldpc codes, experimental results show that the performance of uep is much better than that of unequal error protection (eep), and the reconstructed image remains to be the better texture features with a high compression ratio. key words: ldpc code, bp decoding algorithm, parity- check matrix, joint source and channel coding, uep, image transmission ldpc 码编译码算法的研究及其在图像传输中的应用 vi 图、表清单 图 1.2 e(r)与 r 的关系图.3 图 1.3 二进制对称信道(bsc)的转移概率.5 图 2.1 a(9,2,3)ldpc 码的二分图 .15 图 2.2 a(9,2,3)ldpc 码的(3,2)子码.16 图 3.1 bp 算法第二步中信息传播流程示意图.28 图 4.1awgn 信道简单模型.37 图 4.2 r=1/2 时,不同码长的 ldpc 码在迭代 3 次下的译码性能.38 图 4.3 (4200,3,6)ldpc 码在不同迭代次数时的译码性能.39 图 4.4 不同码率的 ldpc 码迭代 3 次下的译码性能.39 图 4.5(300,3,5)ldpc 码在瑞利平坦衰落信道下,在不同迭代次数下的性能.41 图 4.6(300,3,5)码在两种不同信道下的性能比较.42 图 4.7(2000,3,5)ldpc 码硬判决译码算法的性能 .43 图 4.8 (2000,3,5)ldpc 码在 awgn 信道下的硬判决与 bp 算法的性能比较图.44 图 4.9awgn 信道中 bp 与 app- based 算法的性能比较图.44 图 4.10 awgn 信道中 bp 与 bp- based 算法的性能比较图.45 图 4.11(2000,3,5)awgn 信道中 bp 与其改进算法的性能比较图.46 图 5.1uep 的简单模型 .52 图 6.1 在不同信噪比下恢复的 lena 二值图 .54 图 6.2 在不同信噪比下恢复的 lena 灰度图.55 图 6.3 在不同迭代次数下恢复的 lena 灰度图.56 图 6.4 ldpc 对感兴趣部位不等保护的传输性能与同等保护性能的比较.57 图 7.1 一幅图像小波分解和二次压缩的图像.60 图 7.2 huffman 编码的示意图.63 图 7.3 在不同信噪比下恢复的 wbarb 灰度图.65 图 7.4 在不同迭代次数下恢复的 wbarb 灰度图.65 图 7.5 在不同码率下恢复的 wbarb 灰度图.65 图 7.6 基于分层图像压缩的不等差错保护系统框图.66 图 7.7 lena 的原图及未分层重建图.67 图 7.8 lena 的分层图及未分层重建图.68 南京航空航天大学硕士学位论文 vii 图 7.9 r1=0.5，r2=0.5 的 lena 重建图.69 表 7.1 lena 图各层重建的 psnr.69 ldpc 码编译码算法的研究及其在图像传输中的应用 viii 注释表 awgn additive white gaussian noise 加性白高斯噪声 ber bit error rate 误比特率 bp belief propagation algorithm 置信传播算法 bsc binary symmetric channel 二进制对称信道 dmc discrete memoryless channel 离散无记忆信道 ldpc codes low- density parity- check codes 低密度奇偶校验码 jscc joint source and channel coding 信源信道联合编码 snr signal to noise ratio 信噪比 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进 行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外， 本学位论文的研究成果不包含任何他人享有著作权的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标 明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许 论文被查阅和借阅,可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存论文。 (保密的学位论文在解密后适用本承诺书) 作者签名： 日 期： 南京航空航天大学硕士学位论文 1 第一章 绪论 1 . 1 数字通信系统的基本结构 通信按照传统的理解就是信息的传输与交换。在人类社会中，人们总是离 不开消息的传递。从古代的人力、马力及烽火台，到现代社会的文字、书信、 电报、电话及电视等，都属于通信的范畴。随着社会的发展和技术的进步，人 们对传递消息的要求越来越高，通信交流的方式也越来越复杂。现在，通信己 经渗透进每个人的生活，信息化时代己经来临。 所谓通信系统就是完成信息传递所需的所有设备的总和。按照信道中传输 的是模拟信号还是数字信号，通信系统可以分为模拟通信系统和数字通信系统。 由于数字通信具有抗干扰能力强、便于差错控制、便于使用现代数字信号处理、 易于加密、可以综合传递各种消息等优点，因此数字通信系统更适应于现代通 信的要求。 所有的数字通信系统，如通信、雷达、遥控遥测、数字计算机的存储系统 和内部运算以及数字计算机之间的数据传输等等，都可归纳为图 1.1 所示的基本 模型。 图 1.1 数字通信系统的基本模型 信源的功能是将载有信息的消息传送出去。信源可以是模拟的或者是离散 的，一般而言信源输出的消息为模拟信号，由信源产生的消息经信源编码器变 换成二进制数字序列。理论上，应当用尽可能少的二进制数字表示信源输出， 换句话说，我们要寻求一种信源输出的有效表示方法，使其很少产生或不产生 信源 信源编码器 信宿 调制器 信道 噪声源 信道编码器 信道译码器 信源译码器 解调器 等效信道： 离散输入、离散/ 模拟输出 ldpc 码编译码算法的研究及其在图像传输中的应用 2 冗余。将模拟或数字信源的输出有效地变换成二进制数字序列的处理过程称为 信源编码或数据压缩。由信源编码器输出的二进制数字序列称为信息序列，它 被传送到信道编码器。 信道编码器的目的是在二进制信息序列中以受控的方式引入一些冗余度， 以便于在接收机中用来克服信号在信道中传输时所遭受的噪声和干扰的影响。 因此，所增加的冗余是用来提高接收数据的可靠性以及改善接收信号的逼真度。 因为信道编码器输出的数字信号通常不适合直接在信道中传输，所以调制 器的作用就是将该数字信号转化成易于在信道中传输的模拟信号，调制器产生 有一定时间宽度的，适合于传输媒质传输的时间有限信号，所有有限信号组成 信道符号集。因此信道编码器的输出被转换成该集合中相应的信号波形。 信道是用来将发送机的信号发送给接收机的物理媒质。它的功能是承载和 存储信息。无论用什么物理媒质来传输信息，其基本特点是发送信号随机地受 到各种可能机理的恶化，例如由电子器件产生的加性热噪声、人为噪声及大气 噪声（如在雷暴雨时的闪电） 。由于上述种种因素使得到达接收端的信号不可避 免地产生失真，从而使解调器的输出出现错误。有时为分析方便，我们亦把导 致接收信号失真的各种干扰，噪声和失真从信道中分离出来等效为一个如图 1.1 所示的独立噪声源。 在接收端，解调器对受到信道恶化的发送波形进行处理，并将该波形还原 成一个数字序列，该序列表示发送数据符号的估计值。如果将解调器的输出量 化成两个电平，称之为硬判决解调，相应的译码过程为硬判决译码。反之，如 果将解调器的输出量化成q个（2q ）电平，则称为软判决解调。q = 是软 判决调制的一个极端情况，意味着无穷量化或直接对解调器输出的模拟信号进 行采样。与软判决解调相应的译码过程称为软判决译码。由于硬判决解调通常 会造成信息不可逆转的损失，所以对性能要求较高的通信系统一般采用软判决 解调。解调器输出的数字序列被送至信道译码器，它根据信道编码器所用的关 于码的知识及接收数据所含的冗余度重构初始的信息序列。当需要模拟输出时， 信源编码器从信道译码器接收其输出序列，并根据所采用的信源编码方法的相 关知识重构由信源发出的原始信号。 南京航空航天大学硕士学位论文 3 1 . 2 信道容量 信道编、译码器是用来提高信道的可靠性措施之一，它们的基础是 shannon 定理i ，信道能无错误地传送信息的最大信息率称为信道容量。 对于单用户信道 它是一个数，以比特每秒或符号每秒来表示。它代表每秒能传送的最大信息量。 shannon定理明确地指出任何一个有扰信道均存在一个确定的信道容量c，对于 小于此信道容量的信息传输速率，存在一种编码方式，当采用最大似然译码且 码长趋于无穷大条件下，其译码错误概率亦趋近于零。 )(rneb be eap （1.1） )()()1(ren c recm ce cc eaeap + = （1.2） 式中， b a 和 c a 为大于零的系数，)(reb和)(rec为正实数， 称为误差指数， 它与 r，c 的关系如图 1.2 所示。由图可看出：)(re随信道容量 c 的增大而 增大，随码率 r 的增大而减小。 )(re 2 c 1 cr 21 cc 0 图 1.2 e(r)与 r 的关系图 由上面的公式及图 1.2 可知，为了满足一定的误码率的要求，可用以下两类 方法实现。一种方法是增加信道容量 c，从而使 e(r)增加，可通过增加系统带 宽或增加信噪比的方法达到。另一种方法是在 r 不变情况下，增长分组码长 n （也就是增加分组码信号持续的时间 t） 。 1.2.1 bsc 信道容量 为了更完整和准确地理解 shannon 定理，我们先研究一个最简单的基本信 道，即m进制（2m ）输入q进制（qm）输出离散无记忆信道（dmc） 。 如图 1.3 所示，由信道编码器输出至 dmc 的m进制符号集为 011 , m xx xx =l，dmc 输出q符号集为 011 , q yyyy =l，该信道的转移 概率为 () ij p y x。信道输入x和输出y的平均互信息定义为ii ldpc 码编译码算法的研究及其在图像传输中的应用 4 () 1 1 00 () ;() ()log () q m ij jij ji i p y x i x yp x p y x p y = = （1.3） 输出y的熵( )h y为 ( ) 1 0 1 ()log ( ) q i i i h yp y p y = = （1.4） ( )h y是输出 y 与自身的平均互信息。在输入x被观察到情况下输出y的条件 熵 () h y x定义为 () 1 1 00 1 (,)log () q m ji ji ij h y xp xy p y x = = （1.5） 因此由（1.3）式所定义的互信息();i x y亦可以表示为 ()() ;( )i x yh yh y x= （1.6a） 它表示输出 i yy由于输入 j xx被观察到后所减少的熵（不确定性） 。易证 ();i x y也可以表示为输入x由于输出y被观察到后所减少的熵，即 ()() ;()i x yh xh x y= （1.6b） 对于一般 dmc，shannon定义它的信道容量c为 () 0,1,1 () max; j jm p x ci x y = = l （1.7） 如果对数以 2 为底，c的单位为比特(bits)/信道符号，即每个在 dmc 中传输的 符号所包含的最大平均比特数。如果采用自然对数e为底，c的单位为奈特(nat)/ 信道符号。 对于图 1.3 所示的二进制对称信道 （bsc） ， 它的信道容量可由 （1.7） 和 （1.6a） 计算，即 () 0,1 ( ) max( ) x p x ch yh y x = = （1.8） 令 0 (0)p xp=，则 0 (1)1p xp= 。由（1.1）式可得条件熵 () h y x为 ()() 11 00 (,)log jiij ji h y xp xyp y x = = 0000 (1)log(1)log(1) log(1)(1)log(1)pppp pppppppp= 南京航空航天大学硕士学位论文 5 log(1)log(1)pppp= ( )h p= （1.9） 由上式可知条件熵 () h y x与输入x的概率分布无关，因此求（1.4）式的 最大值就是求( )h y的最大值。二进制熵函数( )h p在0.5p =达到最大值 1。同 理当(0)(1)0.5p yp y=时( )h y取得最大值，即 00 (0)(1)(1)1/2p ypppp=+= （1.10） 易得 0 (0)0.5pp x=。即输入至 bsc 的二进制符号 0 和 1 为等概率分布 时，输入x和输出y的平均互信息达到最大值，即信道容量1( )ch p= 。它是 一个仅与转移概率p有关的函数。 图 1.3 二进制对称信道(bsc)的转移概率 1.2.2 awgn 信道容量 上一节我们研究了离散无记忆信道（dmc）的信道容量，然而对于许多实 际的数字通信系统，图 1.1 所示等效信道的输入/输出为离散输入/连续输出型， 特别是二进制输入，即,xaa= +且(),y = +。信道所受到的噪声为加性 白高斯噪声。可以证明二进制输入在等概率条件下，输入x和输出y的平均互 信息();i x y达到最大，本节我们将研究二进制输入/连续输出型信道的容量。 若xx，yy且加性白高斯噪声的均值为零、方差为 2 ，随机变量y的 概率密度函数为 ( )() ()() ()p yp xa p y xap xa p y xa=+= += 22 22 2 1()() expexp( ) 22 8 yaya y + =+= （1.11） 则由（1.6a）和（1.7）可得信道容量为 ()() 1 2 ( )() p xap xa ch yh y x =+= = （1.12） 1 1 0 0 1p 1p p p ldpc 码编译码算法的研究及其在图像传输中的应用 6 输出y的熵为 22 1 ( )( )log( )log( ) ( ) h yp ydyyy dy p y + = （1.13） 输出y在输入x已知下的条件熵为 () 2 1 ()log() 2 h y xp y xap y xa dy + = = += + 2 1 ()log() 2 p y xap y xa dy + = = 22 2 2 22 22 log1()() logexp 22 28 eyaya dy + =+ 22 2 2 2 22 2 log()()1 explog (2) 222 8 eyaya dye + + += （1.14） 由（1.13）和（1.14）可得二进制输入/ 连续输出 awgn 条件下的信道容量 为 2 22 1 ( )log( )log (2) 2 cyy dye + = （1.15） 而对于带宽受限的加性白高斯噪声（awgn）信道，shannon定义它的信道 容量为 ( ) 1 limmax(;) t p x ci x y t = （1.16） 输入输出信号和单边功率谱密度为 0 n 的 awgn 分别为( )x t，( )y t和( )n t， 假设接收机的带宽b与发射信号的带宽相同，接收机在时间间隔t内用速率为 2b的采样速率对接收信号进行采样，得到一组2nbt=个独立分散值的采样序 列 12 , nn yy yy=l， 与 此 对 应 的 发 射 信 号( )x t的 离 散 样 值 为 12 , nn xx xx=l且满足 iii yxn=+， i n 为 awgn 采样值()1,2,in=l。发射 信号和接收信号序列 n x 和 n y 的平均互信息为 () 1 () ;() ( )log ( ) n ii nniiiii i i p y x ixyp y x p xdxdy p y + = = （1.17） awgn 经过相关接收后的噪声功率为 0/2 n，故条件概率密度函数为 南京航空航天大学硕士学位论文 7 2 0 0 ()1 ()exp ii ii yx p y x nn = （1.18） 可以证明iii，当 i x为零均值方差为 2 x 的独立高斯序列时，即 () 2 12 2 11 1 ,( )exp 22 n nn i ni ii x x x p x xxp x = = l （1.19） 时（1.17）所示的平均互信息 (;) nn i xy达到最大，将（1.18）和（1.19）代 入（1.17）可得 () ( ) 0 max;log 1 av nn p x s ixybt bn =+ （1.20） 其中 av s 是发射信号( )x t的平均功率，因此带限 awgn 信道的信道容量为 0 log 1 av s cb bn =+ （1.21） 我们定义传输系统的谱效率为输入编码器的比特速率与传输信号所占用的信道 带宽之比，即/ b rb=（比特/秒/hz)。由于 av s 与该比特序列的功率是相同的， 故有 000 limlim bb avbbb rcrc sr ee bnbnn = （1.22） 其中 b e 为单位比特能量。与上一节所述 bsc 中的 shannon 定理类似，在带限 awgn 信道中， 若 b rc条件下，无论采用何种编码方式均无法实现无差错传输。 b rc且 c的单位为比特/秒时， （1.21）式又可以表达为 22 00 limlog1log1 b bb rc eecc bnb n =+=+ （1.23） 对于一个给定的/c b，能实现无差错传输的最小 0 / b en 为 / 0 21 / c b b e nc b = （1.24） ldpc 码编译码算法的研究及其在图像传输中的应用 8 如果带宽b，则/0c b(或0)。此时我们有 / (/)0 0 21 limln21.59(db) / c b b c b e nc b = （1.25） 由（1.24）可知 0 / b en 是/c b的增函数且(/)0c b ，因此1.59db是所有编码 系统的临界（门限）值。即单位比特能量 b e 与白高斯噪声的单边功率谱密度 0 n 的比值小于此值时，不可能存在任何能实现无差错传输的编码方式。 无限接近这一极限值是信息论和信道编码学术界为之奋斗的最终目标。当 0 / b en 大于此极限值时，码长足够长的 ldpc 码，能够无限接近于实现无差错 传输这一终极目标，这也是本文研究 ldpc 编/译码的理论依据。 1 . 3 信道纠错码技术的介绍 1.3.1 概述 shannon信道编码定理肯定了逼近 shannon限的编码方案的存在， 但并未说 明如何找到符合要求的编码方案。为了找到逼近 shannon 限的编码方案，上世 纪五十年代到六十年代初，人们相继研究了两大类纠错编码：线性分组码和卷 积码。线性分组码以代数中的群论、域论等理论为数学基础，他们的译码方法 通常是大数逻辑和捕错译码。卷积码在编码过程中引入了寄存器，增加了码元 之间的相关性，在相同复杂度的条件下可以获得比分组码更高的编码增益。卷 积码的译码算法主要有序列译码算法和维特比（viterbi）算法。实际应用中，无 论是分组码还是卷积码大多采用短码，因为它们的译码复杂度与码长成指数关 系，随着码长的增加，译码的计算量极大的增加，基本不可能实用。令人失望 的是，要达到 shannon 限，纠错码的码长必须足够长，所以上述的短码均难以 达到逼近 shannon限的目标。 到了上世纪八十年代到九十年代初，经过几十年的研究和实践，纠错编码 理论和技术取得了突飞猛进的发展。1993 年，c.berrou 等人在 icc93 会议上 提出了 turbo 码iv，它巧妙的将卷积码和随机交织器结合在一起，实现了随机 编码的思想。采用软输入、软输出的迭代译码算法，这种编码能够在码长较长 时逼近 shannon的理论极限。 目前较为流行的 turbo 码译码算法主要有： map 算 法、log- map 算法、max- log- map 算法和 sova 算法。仿真结果表明，在 南京航空航天大学硕士学位论文 9 awgn 信道和 bpsk 调制下，如果采用 65535 的随机交织器，并且进行 18 次迭代， 则在 eb/n00.7db 时， 码率 1/2 的 turbo 码的误比特率 5 10)ber( ， 逼近了 shannon 限的性能（1/2 码率的 shannon限约为 0db） 。turbo 码被看作 是 1982 年 tcm 技术问世以来，信道编码理论所取得的最大成就，具有里程碑 的意义。 在 turbo 码获得巨大成功的启发下，另一种具有相似特性的纠错码复活了， 这就是低密度奇偶校验（ldpc）码。ldpc 码是 gallager 码的推广，1962 年， gallager 在v中提出了一种编码，现在通常称为 gallager 码，这种编码由于校 验矩阵的稀疏性，使得译码的复杂度只与码长成线性关系，当码长较长时，仍 然可以进行有效的译码。然而当时人们普遍认为级联码更容易实现，忽视了 gallager码的存在。 d.j.c.mackay、 m.neal 和 n.wiberg 等人重新研究了 gallager 码，发现虽然该码性能较 turbo 码略有差距，但它同样具有逼近 shannon 限的 性能vi。在 gallager 码的基础上，他们进一步研究了多元域上的 ldpc 码vii， 发现多元域上的 gallager 码比二元域上的码的性能有较大提高，且域的阶数越 高编码的性能越好。m.g.luby 和 m.mitzenmacher 等人从另一个角度对 gallager 码进行了推广，提出非正规 ldpc 码viii，这种纠错码的性能能够赶上 甚至超过 turbo 码。 ldpc 码和 turbo 码有许多相似的地方，在它们的构造方法中存在许多随 机排列的元素，表现出随机码的特性。此外，两者的译码算法也存在着惊人的 相似。n.wiberg 在他的博士论文ix中，构建了迭代译码算法的一个通用结构， 通过研究， n.wiberg 发现 ldpc 码的迭代译码算法和 turbo 码的迭代译码算法 都可以用这一通用结构解释。ldpc 码的迭代译码算法是基于可信度传播的， mceliece、mackay 和 cheng 在x中认为 turbo 码的迭代译码算法可以看作 peal 的可信度传播算法(belief propagation)xi的一个特例。 1.3.2 ldpc 码的特点及发展现状 ldpc 码具有逼近 shannon限的性能特性，同时得益于校验矩阵的稀疏性。 这样优秀的性能是在不太高的译码复杂度(线性复杂度)内实现的。ldpc 码的描 述和实现简单，译码(message passing)算法本质上是并行的，有利于硬件的并行 实现，减少译码时延。 在编码上，ldpc 码具有自己简单的数学模型(tanner 图)。ldpc 码的缺点 ldpc 码编译码算法的研究及其在图像传输中的应用 10 主要在于编码的复杂度较高。虽然最新的研究表明它可以在线性时间 内编码， 但是其复杂度相对于卷积码等可以即时编码的码来说仍然过大。同时在码长很 长时，由于必须在接收到所有的信息比特后才能够进行编码，这就给编码带来 一定的时延。 thomas j. richardson和 rudiger l. urbanke 在文献xii中给出了利用 校验矩阵的稀疏性，对校验矩阵进行一定的预处理后，在线性时间内编码的有 效算法。初步解决了 ldpc 码的应用所面临的一个主要问题。但是编码前的数 据接收过程引入的编码时延仍然是 ldpc 码待解决的一个问题。 ldpc 码的性能受诸多因素的影响， 而编码长度决定了其性能在何种程度上 逼近该门限值。在中短码长给定次数分布对的条件下，编码二分图的结构对码 的性能又有着显著的影响。图中短长度环的数量越少越好，环的平均长度越大 越好。在接收端，译码算法的选择是影响编码性能的决定性因素，要得到好的 性能就需要付出实现复杂度上的代价。 ldpc 码的译码算法是影响其性能的一个重要因素。 研究发现，在理想的编 码条件下，即编码中没有闭合环路时，bp 算法与最大似然译码算法效果一致。 但是，在码长有限的情况下闭合环存在是必然的，这时 bp 算法与最大似然算法 有一定的差距。如何在不造成过高译码复杂度的前提下，缩小这个差距是 ldpc 码的一个研究课题。硬判决算法虽然性能比 bp 算法差，但译码复杂度很低，十 分适合在光纤通信等信道条件较好的系统中应用。针对硬判决译码算法的改进 也同样引起了人们的兴趣。另一方面，针对非高斯的低质量信道上译码算法的 研究也已经展开，如瑞利衰落、部分响应信道、和 isi 信道等xiiixivxv。 由上述介绍的 ldpc 码性能的优越性，可以预测在将来的通信系统中，它 将得到广泛的应用。近年来，国际上对 ldpc 码的理论研究已经取得了重要进 展，美国电气和电子工程师协会（ieee）的信息论会刊上已经出了一期关于图 码和迭代译码的专辑。目前，ldpc 码已经在很多方面得到了应用。例如应用于 压缩图像的传输xvi，信源编码方案采用 jpeg 静止图像压缩标准，信道编码采 用 ldpc 码。ldpc 码也应用于深空通信及磁记录信道 xviixviii和 dsl， adslxixxx 。而且在工程实现上一些试验性的硬件已经研制出来，如码率可调 的可编程 ldpc 译码芯片xxi。另外对 ldpc 其他方面应用的研究也非常广泛， 包括应用于外层空间和卫星通信、下一代无线通信、磁存储器，网络数据包传 输等等，ldpc 码被认为是能够应用于高速宽带传输系统中的理想编码方式。总 之在未来移动通信系统物理层的编码方案的选择上，正规(regular)ldpc 码将有 南京航空航天大学硕士学位论文 11 更好的发展前景。 1 . 4 本文的主要研究工作和内容安排 以下是本文的内容安排：第一章绪论，介绍本文的背景和基本理论；第二 章介绍了 ldpc 的基本概念和多种编码算法；第三章研究了 ldpc 码的几种主 要的迭代译码算法，给出了相应的原理和步骤；第四章仿真得出了 bp 算法的性 能，对多种简化改进的译码算法进行了性能仿真并与 bp 算法进行了比较；第五 章，介绍了联合信源信道编码的基础知识；第六章，将 ldpc 码运用于图像的 传输中，对二进制图像和灰度图像传输做了性能仿真，研究出码率和迭代次数 对于图像传输性能的影响；第七章，对于细节较为丰富的图像，提出了一种基 于分层图像压缩的联合信源信道编码的新策略，并在 awgn 信道下对其性能进 行了仿真，将译码效果与传统的未分层方案进行比较，实验证明该方法提高了 图像的传输质量，有效地降低了图像信息的误码率；最后，第八章对整篇论文 的研究内容进行了总结。 ldpc 码编译码算法的研究及其在图像传输中的应用 12 第二章 ldpc 码的基本原理及编码算法 2 . 1 ldpc 码的概念 传统 ldpc 码是一种基于规则稀疏校验矩阵h的线性分组码。很多学者研 究过 ldpc 码的编码问题。sipser 和 spielman 提出用级联图来减小编码复杂度 xxiixxiii，通过选择级联的层数以及每层的大小可以构造线性时间内可编/译码的 码字。mackay，wilson和 davey建议强制性的使奇偶校验矩阵具有下三角阵的 形式xxiv，该约束条件保证了编码具有线性的时间复杂度，但是它通常也会导致 性能上的一些损失。本章中的有效编码方法来自于