当前位置:首页 >> 信息与通信 >>

LDPC编码原理


LDPC 编码原理
LDPC 码是一种线性分组码,它于 1962 年由 Gallager 提出,之后很长一段时间没有收 到人们的重视。直到 1993 年 Berrou 等提出了 turbo 码,人们发现 turbo 码从某种角度上说 也是一种 LDPC 码, 近几年人们重新认识到 LDPC 码所具有的优越性能和巨大的实用价值。 1996 年 MacKay 和 Neal 的研究表明.采用 LDPC 长码可以达到 turbo 码的性能,而最近的 研究表明, 被优化了的非规则 LDPC 码采用可信传播(Belief Propagation)译码算法时, 能得 到比 turbo 码更好的性能。 和另一种近 Shannon 限的码——Turbo 码相比较,DLPC 码主要有以下几个优势: 1.LDPC 码的译码算法, 是一种基于稀疏矩阵的并行迭代译码算法, 运算量要低于 Turbo 码译码算法, 并且由于结构并行的特点, 在硬件实现上比较容易。 因此在大容量通信应用中, LDPC 码更具有优势。 2.LDPC 码的码率可以任意构造,有更大的灵活性。而 Turbo 码只能通过打孔来达到高 码率,这样打孔图案的选择就需要十分慎重的考虑,否则会造成性能上较大的损失。 3.LDPC 码具有更低的错误平层,可以应用于有线通信、深空通信以及磁盘存储工业等 对误码率要求更加苛刻的场合。而 Turbo 码的错误平层在 10-6 量级上,应用于类似场合中, 一般需要和外码级联才能达到要求。 4.LDPC 码是上个世纪六十年代发明的,现在,在理论和概念上不再有什么秘密,因此 在知识产权和专利上不再有麻烦。 这一点给进入通信领域较晚的国家和公司, 提供了一个很 好的发展机会。 而 LDPC 码的劣势在于: 1.硬件资源需求比较大。全并行的译码结构对计算单元和存储单元的需求都很大。 2.编码比较复杂,更好的编码算法还有待研究。同时,由于需要在码长比较长的情况才 能充分体现性能上的优势,所以编码时延也比较大。 3.相对而言出现比较晚,工业界支持还不够。 目前,LDPC 码被认为是迄今为止性能最好的码。LDPC 码是当今信道编码领域的最令 人瞩目的研究热点, 近几年国际上对 LDPC 码的理论研究以及工程应用和 VLSI(超大规模集 成电路)实现方面的研究都已取得重要进展。基于 LDPC 码的上述优异性能可广泛应用于光 通信、卫星通信、深空通信、第四代移动通信系统、高速与甚高速率数字用户线、光和磁记 录系统等。LDPC 码可以用非常稀疏的校验矩阵或二分图来描述,也就是说 LDPC 码的校 验矩阵的矩阵元除一小部分不为 0 外,其它绝大多数都为 0。通常我们说一个(n,j,k)LDPC 码是指其码长为 n,其奇偶校验矩阵每列包含 j 个 1,其它元素为 0;每行包含 k 个 1,其它 元素为 0。j 和 k 都远远小于 n,以满足校验矩阵的低密度特性。校验矩阵中列和行的个数 即 j 和 k 为固定值的 LDPC 码称为规则码,否则称为非规则码。一般来说非规则的性能优于 规则码。

一、编码部分
LDPC码所面临的一个主要问题是其较高的编码复杂度和编码时延。对其采用普通的编 码方法,LDPC码具有二次方的编码复杂度,在码长较长时这是难以接受的,幸运的是校验 矩阵稀疏性使得LDPC码的编码成为可能。目前,好的编码方法一般有如下几种情况: 1、 T.J.Richardson 和R.L.Urbanke 给出了利用校验矩阵的稀疏性对校验矩阵进行一定的预处 理后,再进行编码。 2、设计LDPC 码时,同时考虑编码的有效性,使H矩阵具有半随机矩阵的格式。 3、H 矩阵具有某种不变特性所采用的其他编码方法,例如基于删除译码算法

提出的编码方案。 这几种编码方案都是在线性时间内编码的有效算法,初步解决了LDPC 码的应用所面 临的一个主要问题。下面对这几种编码方案作一些简单的说明。 Richardson等提出的有效编码方案: LDPC 码的直接编码方法就是利用高斯消去法,产生一个下三角矩阵,然后进一步初等
' 由 从而由 C=M*G 直接编 变换得到右边单位阵形式 H= [ P | I ] , G= ? I | P ? 得到生成矩阵, ? ?

码。 这样的编码方法是复杂的, 主要原因是由于高斯消去法破坏了原有奇偶校验矩阵的稀疏 性。为了保持矩阵的稀疏性,Richardson 提出了有效编码方案,首先可以对矩阵的列做重 排,这样虽然不能得到一个完全的下三角形式的矩阵,但可以获得一个近似的下三角矩阵。 如图所示,分成六个分块的稀疏矩阵,其中 g 是一个相当小的数。如下图所示:

图1 对于要发送的信息序列,依然直接作为LDPC 码字的前N-M个信息位比特输出,对于 其生成的校验比特, 将其分成两块[p1,p2], v=[u,p1,p2],根据H? v 个关系式
T T Au T + Bp1 + Tp2 = 0
T

= 0, ,我们将得到以下的两

(1) (2)

( ? ET ( ? ET

?1

T A + C ) u T + ( ? ET ?1 B + D ) p1 = 0

由(1)式乘以?ET ?1再加上(2)式,我们可以得到式(3)如下:
?1 T A + C ) u T + ( ? ET ?1 B + D ) p1 = 0

(3)

通过(3)式求出p1,代入(1)式,就可以得到p2,从而完成编码过程。 编码复杂度的分析, 因为这六个分块阵是通过对原有稀疏矩阵的列做重排获得的, 所以 这些分块阵依然满足稀疏性, 我们可以进一步分析出求解P1 和P2 的运算量分别为o(N + g2 ) 和 o ( N ) 。由此可以看出,当g尽量小的时候,LDPC 码的编码运算量,就可以控制在线性 复杂度附近。 在特殊情况下,设计码字时,考虑令Φ = ?ET ?1B + D ,当其为I阵时,又可以进一步 降低编码的复杂度,此时编码步骤可以参考如下:

步骤1)计算 Au 和 Cu , 步骤2)计算 ET 步骤3)计算 p1
T

T

T

?1

( Au )
T

步骤4)计算 p2

T

编码结构图如下所示:

图2 定义校验矩阵 H = [ H1 H 2 ] , H1 是k*(n-k), H 2 是(n-k)*(n-k);设计码字时,令 H 2 矩 阵具有如下的形式:

0? ?1 1 0 ?0 1 1 O 0? ? ? H 2 = ?0 0 1 0 M ? ? ? ? M O O O 1? ?0 L L 0 1 ? ? ?
将生成的码字v分成两部分[u,p],u代表信息比特,p代表生成的校验比特。考虑G=[I,P], 由 GH = 0 ,可以得到 IH1 + IH 2 = 0 ,所以 P = H1 H 2 ,根据 H 2 的特性可知, H 2 可
T T T T ?T ?T

以由一个特征多项式为 f ( D ) = 1/ (1 + D ) 的递归卷积码来表示。 此时编码结构如下图所示:

图3 这种编码算法的缺点在于, H 2 矩阵存在列重为1的列,这对迭代译码过程不利,会产 生误码平台,可以通过改变这一列重的方法来优化,降低误码平台。

二、编码部分
LDPC 码有很多种译码方法,本质上大都是基于Tanner 图的消息迭代译码算法。根据

消息迭代过程中传送消息的不同形式,可以将LDPC 的译码方法分为硬判决译码和软判决 译码。如果在译码过程中传送的消息是比特值,称之为硬判决译码;如果在译码过程中传送 的消息是与后验概率相关的消息,称之为软判决译码,有时也称为和积译码算法。硬判决译 码计算比较简单,但性能稍差;软判决译码计算比较复杂,但性能较好。为了平衡性能和计 算复杂度,可以将两者结合使用,称为混合译码算法。根据消息迭代过程中传送的消息是否 进行了量化及量化所使用的比特数, 我们可以将译码方法分为无量化译码和量化译码。 硬判 决译码可以看成是1 比特量化译码,软判决译码可以看成无穷多比特量化译码,而混合译 码可以看成变比特量化译码。 从量化译码的角度看, 硬判决译码和软判决译码属于同一类译 码方法,已有的研究表明,可以用3 比特量化取得和和积译码算法非常接近的性能。目前 主要的硬判译码算法有一步大数逻辑译码算法 (MLG) Gallager提出的比特翻转算法(BF), , 加权的大数逻辑译码算法(WMLG),加权的比特翻转算法(WBF)以及一些对以上几种 算法作改进的算法如IWBF等硬判译码算法;软译码算法主要有迭代结构的置信传播算法 (BP)(有时也称之为和积算法(SPA)),以及基于标准BP 算法,对信息进行部分处 理,降低译码复杂度的译码算法,如UMP BP-based 算法(min-sum 算法),Normlized BP-based 算法,还有基于最优化理论的译码算法如线性规化算法(LP)。下面对译码算 法作简单的介绍: 一、硬判译码算法 一步大数逻辑译码算法,主要原理是根据通过一系列的正交方程,比较校验结果1 和0 的数目来完成译码过程。这种译码算法译码结构简单,复杂度较低,但是应用场合有限,只 适用于某些码结构比较特殊的码字,如有限几何LDPC码。 基于 Tanner 图的信息传递的比特翻转算法,在每一次迭代过程,根据某一种准则,决 定将其中的某一个比特进行翻转,直至迭代过程结束,或者校验方程全部满足。这种译码算 法的核心在于确定比特翻转的准则,如Gallager 最初提出的BF 算法,准则是不满足校验方 程个数最多的比特进行翻转, 后来提出的加权算法主要是在翻转准则加入变量节点可靠性度 量, 改进算法主要是在检测翻转过程中防止出现翻转成环的现象, 这些改进都进一步提高了 性能,而没有增加复杂度。 二、软判译码算法 软判译码算法主要包含BP算法及其简化形式,LP算法等。 BP算法中消息的传递形式是对数似然比(LLR),在迭代过程中,每次在变量结点和校验 结点分别按照和规则与tanh 规则更新节点的信息。直至译码结束或者校验方程全满足。BP 算法适用于各类信道, 具有逼近香农限的优异性能, 但校验节点的消息计算复杂度非常复杂, 为了简化校验节点的消息计算,人们提出了很多简化算法,如UMP(min-sum)译码算法就 是一个有代表性的简化算法,另外为了保证性能上接近与BP 算法,以提出了归一化的BP 算法。 各种译码简化译码算法的目的就是在计算复杂度、 译码性能及译码时延等方面取得最 优的折中。 线性规化算法(LP)是基于最优化理论提出的一种新的译码算法,主要思想是可以把 译码问题看作一个整数优化问题,通过对约束条件的放缩,形成一个简单的线性规化问题, 利用最优化理论的知识完成译码。 这种译码算法的好处在于译码复杂度是线性的, 性质便于 分析,开拓了新的译码思路。 以下分别从性能与译码复杂度两个角度分析比较各种译码算法,如图及表所示:

图4.TYPE-I 2-D(1023,781)EG_LDPC码的在不同译码算法下性能曲线图 译码算法 标准BP算法 Normalized BP-based 算法 UMP BP-based 算 法 WBF 算法 IWBF 算法 改进式WBF 算法 乘法次数 除法次数 加法次数

11Nwc ? 6 ( N + M )
0 0 0 0 0

N ( wc + 1)
Nwc
0 0 0 0

N ( 3wc + 1) 4 N ( wc ? 1) + N log 2 2wc / 2 4 N ( wc ? 1) + N log 2 2wc / 2
N ? 1 + wc wr N ? 1 + wc wr N ? 1 + wc wr

表1.典型的几种译码算法复杂度比较

三、LDPC码的展望
LDPC码具有很好的性能,译码也十分方便。特别是在GF(q)域上的非规则码其性能非 常接近香农限。今后,LDPC码的研究方向主要有: (1)码的设计; (2)选择合适的硬件(以降低编译码的运算复杂性); (3)LDPC码应用于下一代通信系统。目前,LDPC码已成为第四代移动通信编码技术中的首选


相关文章:
LDPC码及其译码实现
由于校验矩阵H的稀疏性以及构造时所使用 的不同规则,使得不同LDPC码编码二分...LDPC编译码原理课件 88页 2下载券 LDPC码构造及译码技术研... 87页 5下载...
现代编码理论期末报告LDPC
21 3 绪论 1.1 研究背景编码是信息从一种形式或格式转换为另一种形式的过程...12 2.2 和积算法原理 LDPC 码的译码方法有硬判决译码和软判决译码方法。 ...
LDPC码应用研究
【摘要】ldpc 码是迄今为止实验中最接近 shannon 极限的信道编码,也为短波通信...[4]文红,符初生.ldpc 码原理与应用[m].电子科技大学出版社,2006. 作者简介...
LDPC码译码算法及性能分析
1 LDPC 码编码 LDPC 码是一种性能非常接近香农极限的“好”码,它是惟一用...LDPC-BP译码 9页 免费 LDPC码编译码器的原理及... 63页 免费 Matlab的卷积...
LDPC码的学习之一
LDPC 码的学习之一(LDPC 码的介绍、表示、和积译码)一、 简单介绍 LDPC,(...LDPC码课件 暂无评价 10页 ¥9.98 LDPC编码原理 暂无评价 5页 2下载券 ...
LDPC码实现及性能研究
会议确定 5G 将使用 LDPC 码作为移动宽带(eMBB)业务数据信息的长码块编码方案...原理图,但是由于当时科技水平有限,硬件条件的限制,LDPC 码并没有得到重 视和...
Matlab LDPC码性能研究毕业设计说明书
15 3.2 二进制 LDPC 码编码原理 ......介绍 了信道编码理论及其发展历程,最后概述了低密度奇偶校验码的提出、发展和现状。 1.1 数字通信系统通信系统的基本...
基于Matlab的LDPC码研究及实现
1 LDPC 编码原理 从本质上来说 LDPC 码是属于线性分组码的一种特殊形式。 一个用(n,k)表示 的线性分组码将长度为 k 位的信息 u 映射成为长为 n 位的...
LDPC编译码仿真
2 LDPC 编译码算法原理 2.1 LDPC 码基本概念 LDPC 码是线性分组码的一种, ...4 结论本文简单地对 LDPC 编码译码算法在高斯加性信道下进行 Matlab 仿真,并 ...
LDPC码的编译码算法研究本科毕业论文
本文的重点是对 LDPC 码的编译码算法的论述与研究, 介绍 LDPC 码的基本 原理和分类,分别从基于生成矩阵和基于校验矩阵详细讨论了 LDPC 码编码算 法,简单介绍了...
更多相关标签: