LDPC码及其译码实现

格式：docx
大小：345.90 KB
文档页数：12

LDPC码及其译码实现

一、 LDPC码简介

LDPC码最早在 20 世纪 60 年代由Gallager在他的博士论文中提

出，但限于当时的技术条件，缺乏可行的译码算法，此后的 35 年间

基本上被人们忽略，其间由Tanner在 1981 年推广了LDPC码并给出了

LDPC码的图表示，即后来所称的Tanner图。1995 年前后MacKay和Neal

等人对LDPC码重新进行了研究，提出了可行的译码算法，从而进一步

发现了LDPC码所具有的良好性能，迅速引起强烈反响和极大关注。

LDPC码（低密度奇偶校验码）本质上是一种线形分组码，它通过

一个生成矩阵G将信息序列映射成发送序列，也就是码字序列。对于

生成矩阵G，完全等效地存在一个奇偶校验矩阵H，所有的码字序列C

构成了H的零空间 (null space)，即HCT=0。LDPC码的奇偶校验矩

阵H是一个稀疏矩阵，相对于行与列的长度，校验矩阵每行、列中非

零元素的数目(我们习惯称作行重、列重)非常小，这也是LDPC码之所

以称为低密度码的原因。由于校验矩阵H的稀疏性以及构造时所使用

的不同规则，使得不同LDPC码的编码二分图(Taner图)具有不同的闭

合环路分布。而二分图中闭合环路是影响LDPC码性能的重要因素，它

使得LDPC码在类似可信度传播(Belief ProPagation)算法的一类迭

代译码算法下，表现出完全不同的译码性能。

当H 的行重和列重保持不变或尽可能的保持均匀时，我们称这样

的LDPC码为正则LDPC码，反之如果列、行重变化差异较大时，称为

非正则的LDPC码。根据校验矩阵H中的元素是属于GF(2)还是

GF(q)(q=2p)，我们还可以将LDPC码分为二元域或多元域的LDPC码。

二、LDPC译码算法

2.1、Gallager概率译码算法

Gallager当初为了介绍LDPC码，同时还提出了一种迭代的概率译

码算法，Gallager概率译码算法，后来在此基础上又发展出了置信度

传播译码算法（BPA，也称SPA或者MPA）。

假设一个二进制序列是一个LDPC码字，那么这n个比特就要满足

由该码字的校验矩阵所确定的一系列的校验方程。并且，包含某一比

特 C 的校验方程可能不止一个，这些校验方程中的其他比特又可能包 i

含在其他更多的校验方程中。为了直观的表示这种关系，Gallager引

入了校验集合树的概念。图 2.1 所示为某一比特的校验集合树。

(1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3)

图 2.1 校验集合树

根节点表示比特d，和d相连的每一条边表示包含d的一个校验方

程，在图 2.1 中，d包含在 3 个校验方程中；第一层中的每一线段上

的节点表示这一校验方程中除d以外的其他比特，因此包含d的 3 个校

验方程分别是：

d  C

 C

1,1

2,1

3,1  C

 C

1,2

2,2

3,2  C

 C

1,3

2,3

3,3  0

 0

校验方程中的加法是模 2 加。C 即为比特d的数值，C 即为比特 d 1,1

（1,1）的数值。

与第一层各节点相连接的每条边同样表示包含该比特的一个校

验方程，第二层中的每一线段上的节点同样表示该校验方程中除第一

层比特以外的其他比特。以比特（2,2）为例，和比特（2,2）相连接

的边有 3 条，其中一条与本层节点（2,1），（2,3），及根节点d相连，

另外两条与第二层中节点u,v,w和x,y,z相连。因此包含比特（2,2）的 3

个校验方程分别为：

2,2  C

2,1  C

2,3  C

d  0

2,2

2,2  C

 C

x  C

 C

y  C

 C

z  0

 0

第三层（图中未画出）及以后的各层依此类推，每个比特都有相

应的以该比特为根节点的校验集合树。

假设信道是无记忆信道， y

i 仅与 c

i 及信道噪声有关，考虑根

节点 d 和第一层节点组成的集合，这些比特组成了包含比特 d 的

j1(12P)P  i  1 1   (1  2 P )

l  1

j 个校验方程，每个校验方程由 k 个比特组成（包含比特 d ），显

然发送的这些比特满足这 j 个校验方程。因此假设当发送的码字是

c  ( c , c , L , c 0 1

n  1 ) 时，那么在以上情况下接收到的符号即

为 y  ( y , y , L , y 0 1

n  1 ) 。

这样在传送码字 c 时，码字中的各比特满足包含比特 d 的 j

个校验方程。当接收到相应的符号序列 y 时，比特 d 为 1 的条件

概率可以表示为 P ( c

d  1 | y , c ) 。同理，比特d 为 0 的条件

概率表示为 P ( c

d  0 | y , c ) 。又令当不考虑发送比特间的相

关性时， d 为 1 的概率表示为 P ( c

有关。

d  1 | y ) ，它与信道模型

令 P

d  P ( c

d  1 | y ) ， P

il 表示 d 的校验集合树第一

层中包含 d 的第 i 个校验方程的第 l 个比特为 1 的概率，那么有：

P [ c

d  0 | y , c ] 1  P il  l  1  1 | y , c ] k  1 d k  1

(2.1 )

il 根据式 2.1，只要知道了图 2.1 的第一层中各比特为 1 的概率

，就可以算出比特 d 的条件概率。在其他根节点的校验树里比

特 d 又作为一个节点参与到根节点的概率计算中去，即比特 d 从

与其有关的节点中获取信息计算出概率，再将其计算出的概率信息传

出用于计算其他的节点 c ，由于在计算其他节点 c 时同样会用到 i i

计算比特 d 时所用过的运算，所以可以通过共享计算的中间结果而

使计算量大为降低，进而发展出了BPA（也称SPA或MPA）。

LDPC码译码算法及性能分析

龙源期刊网

LDPC码译码算法及性能分析

作者：李秀花高永安马雯

来源：《现代电子技术》2014年第01期

摘要：为了进一步降低低密度奇偶校验（LDPC）码译码算法的复杂度，基于经典置信传播（BP）译码算法，给出了对数域迭代后验概率对数似然比（APP LLR）算法。通过概率域的和积算法（SPA）和对数域的迭代APP LLR算法的性能仿真及分析可见，迭代APP LLR算法能以较小的性能损失换取复杂度的大幅降低。进一步选用迭代APP LLR算法，结合不同地形条件下的VHF频段信道模型，仿真了LDPC码编译码系统的性能。理论分析及仿真结果均表明，基于迭代APP LLR算法的LDPC码，实现简单，性能优异，具有良好的工程应用前景。

关键词： LDPC码；迭代APP LLR；和积算法； VHF频段

中图分类号： TN91⁃34 文献标识码： A 文章编号： 1004⁃373X（2014）01⁃0001⁃04

0 引言

信道编译码技术可以检测并且纠正信号在传输过程中引入的错误，能够保证数据进行可靠的传输[1]。LDPC码的校验矩阵具有稀疏的特性，因此存在高效的译码算法，其纠错能力非常强。1981年，Tanner提出了基于图模型描述码字的概念，将LDPC码的校验矩阵对应到Tanner图的双向二部图上。采用Tanner图构造的LDPC码，通过并行译码可大大降低译码复杂度。Mackay和Neal利用随机构造的Tanner图研究了LDPC码的性能，发现采用和积算法（SPA）的LDPC码具有优异的译码性能，在长码时甚至超过了Turbo码[2]。本文采用Mackay基于二分图提出的改进方案构造LDPC码的校验矩阵。基于置信传播（BP）算法，给出了一种简化的BP算法——对数域迭代APP LLR算法，复杂度大大降低。目前，LDPC码是最有希望在广泛的信道范围取得香农容量的误差纠正技术[3]，在保证LDPC码纠错性能的前提下，降低编译码器实现的复杂度是研究的重点，引发了信道编码界的研究热潮。

LDPC码译码算法研究和FPGA实现的开题报告

标题：LDPC码译码算法研究和FPGA实现

摘要：

LDPC码是一种近年来广泛应用于通信领域的误差纠正编码技术，其具有低复杂度和好的纠错性能等优点，因此在Wi-Fi、蓝牙等无线通信标准中得到广泛采用。在本课题中，我们将研究LDPC码在信道编码中的应用以及LDPC码的译码算法。同时，我们还将通过FPGA实现译码算法，优化编码器和译码器的设计，提升算法的实时性和效率。

本文主要研究内容包括：

1. LDPC码的基本原理和编码方式。

2. LDPC码的译码算法，包括1. Min-Sum译码、2. SPA译码和3. 消息传递译码等算法。

3. FPGA实现LDPC码译码算法的设计，优化编码器和译码器的结构和流程，提升算法的实时性和效率。

4. 对比不同译码算法和FPGA实现的效果，分析其性能和优缺点。

通过本次研究，可以深入掌握LDPC码的基本原理和译码算法，并通过对FPGA实现的优化，提升算法的实时性和效率，在通信领域的应用中发挥重要的作用。

关键词：LDPC码、译码算法、FPGA实现、通信。

ldpc译码原理

LDPC译码原理

LDPC（Low-Density Parity-Check）码是一种由Robert Gallager在1960年代提出的一种编码技术，被广泛应用于通信领域中的信道编码和译码中。LDPC译码原理是指利用LDPC码的结构特点进行译码，以实现在信道传输中更高的可靠性和更好的性能。

LDPC码是一种线性块码，其校验矩阵具有低密度的特点，即大部分元素为0。在LDPC译码过程中，采用迭代译码的方式，即多次对接收到的码字进行译码，每次译码后更新信息位的概率分布，直到满足一定的条件为止。

LDPC译码原理的核心思想是利用校验矩阵的低密度结构，通过消息传递算法进行译码。消息传递算法包括和节点更新和校验节点更新两个步骤。在和节点更新中，根据接收到的信息位和校验节点传递的校验信息，更新每个和节点的信息。在校验节点更新中，根据和节点传递的信息更新每个校验节点的信息。通过多次迭代这两个步骤，最终可以得到一个较为准确的译码结果。

LDPC译码原理的优势在于其具有较好的译码性能和低复杂度的特点。LDPC码的译码性能接近信道容量极限，可以在高速通信系统中得到广泛应用。同时，LDPC译码算法的复杂度相对较低，适合在硬件实现中使用。

总的来说，LDPC译码原理是利用LDPC码的结构特点和消息传递算法进行译码，以提高通信系统的可靠性和性能。通过不断优化算法和结构设计，LDPC码在现代通信领域中发挥着重要作用，成为一种重要的信道编码技术。