LDPC码在联合信源信道编码中的应用

OF NAVAL AERONAUTICAL ENGINEERING INSTITUTE Mar. 2006 2006年3月 JOURNAL

LDPC码在联合信源信道编码中的应用 李 鑫1，王红星2，许 阳1 （1．海军航空工程学院研究生管理大队；2．海军航空工程学院电子信息工程系，山东烟台，264001） 摘 要：介绍了LDPC码的编译码原理，建立了一种应用LDPC码的联合信源信道编码图像传输系统结构，对其性能进行了分析，并给出了LDPC码在联合信源信道编码中应用的进一步研究方向。 关键词：低密度校验码；联合信源信道编码；和积算法 中图分类号：TN 919.8 文献标识码：A低密度校验码（Low-Density Parity-Check codes, LDPC码）及其迭代译码算法由Gallager于1962年首次提出[1]。由于客观条件上的限制，直到20世纪90年代中期被Mackay和Neal等学者[2，3]重新发现后，LDPC码才引起广泛关注。LDPC码是一种能逼近香农容量限的渐进码，在长码时的性能甚至超过了Turbo码。此外，LDPC码的译码采用了具有线性复杂度的和积算法，译码复杂度大大低于Turbo码。LDPC码的优异性能及其在信息传输中的良好应用前景已引起学术界和信息产业界的高度重视，成为当前信道编码领域最受瞩目的研究热点之一。本文在介绍LDPC码编译码原理的基础上，将LDPC码应用于联合信源信道编码图像传输系统中，分析了其性能，给出了其进一步的研究方向。 么码率为(k−j)k，否则码率是(k−j')k，其中j'是校验矩阵行线性独立的数目。 ⎡1⎢1H=⎢⎢0⎢⎣001001⎤10100⎥⎥ 10011⎥⎥01110⎦图1 （6,2,3）LDPC码的校验矩阵 这种校验矩阵中行和列中“1”的数目固定的LDPC码称为规则码。如果行或列中的“1”的数目并不是全部相同，则称为非规则LDPC码（这里主要讨论规则LDPC码）。规则码的校验矩阵H能很容易地由一个随机产生的二分图构造，如图2所示。 图2 （6,2,3）LDPC码的二分图表示 1 LDPC码的编、译码原理 1.1 基本概念 LDPC码是一种线性纠错码。线性纠错码采用一个生成矩阵G，将要发送的信息u={u1,u2,L,um}[4]转换成被传输的码子t={t1,t2,L,tn},n>m。与生成矩阵G相对应的是一个校验矩阵H，H满足Ht=0。LDPC码的校验矩阵H是一个几乎全部由0组成的稀疏矩阵。Gallager定义的(n,j,k)LDPC码是码长为n的码字，在它的校验矩阵H中，每一行和列中1的数目是固定的，其中每一列1的个数是j（列重为j），每行1的个数是k（行重为k），k≥3。列之间1的重叠数目小于等于1。图1是一个(6,2,3)的码字的校验矩阵。如果校验矩阵H的每一行是线性独立的，那 收稿日期：2005-09-07

作者简介：李 鑫（1981−），男，硕士生.

在图的上方每一个节点代表的是信息节点，对应校验矩阵的一列；下方的节点代表的是校验约束节点，对应校验矩阵的一行。对于规则码，与每个信息节点相连的边的数目是相同的，校验节点也具有相同的特点。与这两种节点相连的边的数目称为该节点的度。由图2可以看出，此时，信息节点的度数为2，校验节点的度数为3。 ·254· 海 军 航 空 工 程 学 院 学 报 2006年 第2期

1.2 LDPC码的编码

LDPC码的编码过程可分为以下几个步骤[5]： （1）构造LDPC码的校验矩阵H：校验矩阵的构造有很多种，主要研究热点是如何消除小环[6]；

（2）通过高斯消去法变换，把校验矩阵变换成系统形式，H=PI1]，I1为m阶单位阵；

T

二元LDPC码的译码，信道模型采用二元输入连续输出的平稳无记忆AWGN信道模型，假设采用BPSK调制，噪声服从高斯分布N(0,σ2)。

图3 LDPC码的译码器

rij0r信息节点0qijei0（3）由H得到其生成矩阵G，G=[I2P]，其中（4）用信息比特去乘生成矩阵，就得到了编码

[校验节点I2为（n−m）阶单位阵；

后的码字，t=uG。

和积算法有如下4个步骤：

（1）初始化：对特定的信道预设信息比特的先

0

和q1分别初验概率。qmnmn表示码字xn的两种概率，

1.3 LDPC码的译码

图3描述了LDPC码的译码器结构，其中r是信道的输出结果，rij0表示校验节点到信息节点传递消息

0

“0”时的概率，qij表示信息节点到校验节点传递消

始化为fn0和fn1。对于AWGN信道，有：

fn0=1−fn1，fn1=11+exp−2aynσ2， (1)

(())息“0”时的概率，ei0是译码器输出“0”的概率。

LDPC码的译码算法是一种消息传递算法，称为和积算法[7]。此方法测定信息值的后验概率，并通过多次迭代提高了计算的准确性。这里主要讨论

0

=rmn

其中：a为BPSK调制器的输出；yn为高斯信道的输出。

（2）水平迭代过程：从校验矩阵行开始，主要是信息节点将更新信息传递给校验节点的过程。

⎧x'⎫⎪⎪'n

=∈Probx|x0,x:nN(m)/nq， (2) ''⎨n∑∏nnmn'⎬''⎪⎪{xn':n∈N(m)/n}n∈N(m)/n⎭⎩

{}{}1

=rmn

⎧x'⎫⎪⎪'n

()=∈Probx|x1,x:nNm/nq''⎬， (3) ⎨n'n∑∏nmn

⎪{xn':n'∈N(m)/n}n'∈N(m)/n⎪⎩⎭

{}{}式(2)、(3)中：N(m)/n表示除信息节点n外所有与校

x

表示信息节点n验节点m相连接的信息节点集；rmn

然不为零，则宣布译码失败。

满足时检验节点m的概率。

（3）垂直迭代过程：主要完成校验节点将更新信息传递给信息节点的过程，该过程主要基于校验矩阵的一列。

00

qmn=αmnfn0∏rm:m'∈M(n)/m， (4) '

n11'

q1mn=αmnfn∏rm'n:m∈M(n)/m， (5)

2 LDPC码在联合信源信道编码中的应用

2.1 一种应用LDPC码的联合信源信道编码图像传输系统

具体的联合编码结构框图如图4所示[8]。在此联合编码系统中，信源编码方案采用的是新一代静止图像压缩编码标准JEPG2000[9]。

JPEG 2000与传统JPEG最大的不同在于它放弃了JPEG所采用的以离散余弦变换为主的区块编码方式，而采用以小波变换为主的多解析编码方式，并且具有高压缩率，支持渐进传输，支持无损压缩和有损压缩等特点[10]。

信源JPEG2000编码器JPEG2000译码器 LDPC码编码器LDPC码译码器调制信道信宿解调这里，αmn的选择要满足q概率由下式可得：

0mn

+q

1mn

=1，预设的后验

00qn=αnfn0∏rmn:m∈M(n)/m， (6) 11q1n=αnfn∏rmn:m∈M(n)/m。 (7)

（4）判决过程：首先设定一个最大迭代次数，然后获得信息节点的边界信息进行判决，把判决结果通过校验矩阵求出伴随式，然后检查伴随式是否为零。如果满足，译码结束；如果不满足，则重复(2)~(4)步骤，反复迭代直到条件满足，得出译码结果。如果迭代次数达到预设的最大次数，伴随式仍

图4 联合信源信道编码系统结构框图

总第86期 李 鑫等：LDPC码在联合信源信道编码中的应用

·255·

信道编码方案采用的是LDPC码。对于JEPG2000静止图像压缩算法，编码器输出码流为嵌入式码流，其重要性大致由高到低排列，即码流对恢复图像质量影响的重要性由大到小排列。这样，我们对编码器输出码流采用不等误差保护方法，对图像恢复质量影响大的数据采用强的误差保护，而对影响小的数据采用弱的误差保护。具体的方法是：比等误差保护LDPC码的性能约有0.5dB的提高。

对于前者采用码率较低的LDPC码进行保护；而对于后者采用码率较高的LDPC码进行保护。

2.2 性能分析

这里我们简要分析上述的联合编码系统在AWGN信道的性能[11，12]。

AWGN信道的数学模型可用下式表示：

p(yw)=1

⎛(y−w)2⎞

⎟2πσ2

exp⎜⎜−2σ2⎟， (8) ⎝⎠

式中：y为输入；w=1−2x，表示BPSK调制的输出，

x为“0”或者“1”。

仿真分析中，我们采用了128×128的“Lena”图像，调制方式为BPSK。我们构造了3种规则LDPC码，码的参数在表1中给出，其中H(m, n)为校验矩阵，R表示码率，j表示列重，k表示行重，并设定译码的最大迭代次数为400次。

表1 LDPC码的参数

H(m, n) R j

k

码1 (1024,2048) 1/2 3 6 码2 (2048,4096) 1/2 3 6 码3

(3072,4096) 1/4 3 4

对每一种码，在不同输入信噪比（SNR）时的误比特率在图5给出。当SNR小于3dB时，3种码的性能差别不大，随着SNR的增加，低码率的码3的性能优势非常明显。

下面我们分析对编码器输出码流分别采用不等误差保护和等误差保护时的性能，其中输出码流经过BPSK调制后，通过加性高斯白噪声信道。我们将一幅图像经压缩后的码流按照给定的大小分为许多帧，以确定数据的重要性。对于等误差保护，LDPC码的码率为1/2。对于不等误差保护，码流数据按重要性分为3组，第一组重要数据采用码率为1/4的LDPC码进行保护，第二组次重要数据和第三组非重要数据分别采用码率为1/3、1/2的LDPC码进行保护。仿真结果如图6所示，不等误差保护

SNR/dB

图5 三种LDPC码的误比特性能

SNR/dB

图6 不同误差保护的性能比较

综合以上仿真结果，可知：在不同的码长、码率等条件下，作为一种性能良好的信道编码，LDPC码能极大地提高重建图像的质量；在相同的误比特率下，对静止图像采用不等误差保护方案比采用等

误差保护方案获得的编码增益更大。

3 结论与进一步的工作

LDPC码具有以下特点：具有较大的灵活性和较低的差错平底特性，描述简单，对严格的理论分析具有可验证性，译码复杂度低于Turbo码，且可实现完全的并行操作，便于硬件实现，吞吐量大，极具高速译码潜力。因此研究将LDPC码应用于联合信源信道编码中具有重要意义。

笔者认为，LDPC码应用于联合信源信道编码中进一步的工作，将主要围绕以下几个方面：如何在信源编码和LDPC码之间进行动态的码率分配；如何自适应地实现不等误差保护，即如何根据信源编码码流来调节LDPC码的码率；非规则LDPC码以及在GF(q)，q>2上构造的LDPC码在联合信源信道编码中的应用。

参考文献：

[1] Gallager R G. Low density parity check codes[J]. IRE

·256· 海 军 航 空 工 程 学 院 学 报 2006年 第2期

Trans, 1962,8(1):21-28

[2] Mackay D J C. Good error-correcting codes based on

very sparse matrices[J]. IEEE Trans Inform Theory, 1999,45(3):399-431

[3] MacKay D J C, Neal R M. Near Shannon Limit

Performance of Low Density Parity Check Codes [J]. Electronic Letters, 1996,32(18):1 64521 646

[4] Richardson T, Urbanke R. The capacity of low - density

parity-check codes under message-passing decoding[J]. IEEE Trans. Inform. Theory, 2000,47:599-618 [5] 孙韶辉, 慕建君, 王新梅. 低密度校验码研究及其新

进展[J]. 西安电子科技大学学报（自然科学版）, 2001, 28(3):393-397

[6] Prabhakar A, Narayanan K. Pseudorandom construction

of low-density parity-check codes using linear congruential sequences[J]. IEEE Trans on Commun.

2002,50(9):1389-1396

[7] 王单. 低密度校验码理论及其译码研究[D]. 西安:

西安电子科技大学, 2004

[8] 张建国. LDPC码的应用研究[J]. 通信技术, 2003,(11):

24-25

[9] JPEG2000 IMAGE CODING SYSTEM[S]. ISO/IEC

FCD15444-1:2000(V1.0), 2000

[10] 邱风, 翁璐. JPEG2000抗干扰性能的研究与仿真[J].

海军航空工程学院学报, 2005,20(3):365-367

[11] Zang Di, et al. Low-Density Parity-Check Codes Used

for Compressed Image Transmission over Noisy Channel. from Internet, http://image.chonbuk.ac.kr /kwak/data1/2002-4.pdf,Apr.2003

[12] 翁芸, 颜珂斐, 郭引川, 杨万全. LDPC码的改进及

其应用研究[J]. 现代电子技术, 2005,(1):49-51

Application of LDPC codes on Joint Source-Channel Coding

LI Xin1，WANG Hongxing2，XU Yang1

（1．Graduate Students’ Brigade of NAEI；

2．Department of Electronic and Information Engineering，NAEI，Yantai，Shandong，264001） Abstract: The principles of encoding and decoding of Low-Density Parity-Check codes are presented, and the structure for Joint Source-Channel Coding in image transmission system is constituted on LDPC codes. The performance of the structure is analyzed and the future development of LDPC codes’ application on JSCC is also described.

Key words: Low-Density Parity-Check (LDPC) codes; Joint Source-Channel Coding (JSCC); sum-product algorithm

（上接第252页）

Application of boundary scan technique to

the design for board-level test

SHI Xianjun1，ZHOU Shaolei1，ZHANG Wenguang2，ZHOU Jie2

（1．Department of Control Engineering，NAEI；

2．Graduate Students’ Brigade of NAEI，Yantai，Shandong，264001）

Abstract: The basic principle of JTAG technique is presented. The design for test of PCB based on JTAG is researched from designed method, optimization strategy, realization technique and so on. Some concrete implementing methods are given, and the realization of the measurability design of the data collection circuit board of the missile universal test system is presented.

Key words: circuit board; boundary scan; design for test; JTAG