基于对角线法的 LDPC 编码 戴迎春1，赵忠文2，宋楠 3 (1.装备指挥技术学院研究生管理大队，北京，101416；2.装备指挥技术学院国防重点实验 室，北京，101416；3.装备指挥技术学院研究生管理大队，北京，101416） 摘 要： LDPC 码是一种具有稀疏校验矩阵的线性分组码。传统的纠错码码字都很 短，很难实现长码，因为它们的编译码算法的复杂度随码长的增加成指数级增长。而 LDPC 码编译码复杂度与码长呈线性关系，尤其适用于较长码长。本文介绍了一种用对角线构造 LDPC 的校验矩阵的方法，并用基于近似下三角矩阵的编码算法对 LPDC 码进行编码，整个过 程用 MATLAB 进行了实现。最后对计算复杂度进行简要分析。 关 键 词：LDPC；对角线法；基于近似下三角矩阵；MATLAB 中图分类号：TN914 LDPC Encoding Based on Diagonal Method DaiYing-Chun1, Zhao Zhong-Wen2, Song Nan3 (1.Company of Postgraduate Management, the Academy of Equipment Command and Technology, Beijing, 101416; 2.Key Lab of National Defense , the Academy of Equipment Command and Technology, Beijing, 101416; 3.Company of Postgraduate Management, the Academy of Equipment Command and Technology, Beijing, 101416;) Abstract: LDPC is Low Density Parity Check Code, which is one of linear block codes with sparse parity check matrix. Traditional error-correcting codes are very short and difficult to achieve long code, because their complexity of error-correcting decoding increases exponentially with the length of code.While the complexity of LDPC decoding increases linearly, while is especially available for long code. This paper presents a method of constructing LDPC check matrix with diagonal, and encodes LDPC codes based on approximate lower triangular matrix .The whole process was implemented using MATLAB. Finally, it analyses complexity of encoding . Key Words: LDPC; diagonal method; approximate lower triangle matrix ; MATLAB 1 引言 低密度奇偶校验（Low Density Parity Check Code，LDPC）码是一类具有稀疏校验 矩阵的线性分组码，由Gallager码[1]发展而 来，不仅有逼近香农（Shannon）限[2]的良 好性能，而且译码复杂度较低, 结构灵活， 易于进行理论分析和研究、译码简单且可以 实现并行操作，尤其适合于长码，其性能甚 至超过了著名的Turbo码。在通信系统信道 编码中展现出了十分优秀的性能，是近年信 道编码领域的研究热点，因此，越来越受到 通信领域的关注，成为了当前通信领域的热 门研究课题之一。目前已广泛应用于深空通 信、光纤通信、卫星数字视频和音频广播等 领域。LDPC码已成为第四代通信系统(4G) 强有力的竞争者，现在已经被多个通信标准 采用，例如WLAN（IEEE802.11n）、DVB-S2、 WIMAX（IEEE802.16e）等[3]。如今，LDPC码 研究工作主要包括LDPC码的构造及其优化、 LDPC码的译码研究、LDPC码的应用研究。虽 然LDPC码有很多卓越的性能，但自身仍有很 戴迎春，女，硕士研究生.主要研究方向：系统分析与集成.15201500792.daiyingchun163@163.com 赵忠文，男，硕士，硕士生导师.主要研究方向：嵌入式系统仿真，体系软件研究. 宋楠，男，硕士研究生.主要研究方向：系统分析与集成. 

多问题有待解决，研究LDPC码具有十分重要 码的校验矩阵 H 中的行和列中非零元素的 的理论价值和实用价值。 个数不限制相同，那么这样的码成为非规则 2 LDPC基本概念 [4] LDPC 码。 LDPC 码的稀疏校验矩阵 H(n,q,p)应当 通常在有限域上讨论码的构造，具有 g 满足如下定量和定性要求： 域，用 GF（q）或 个元素的有限域称之为 Galois（枷罗华） qF 表示，最简单的域是二 元域 GF(2),凡是本论文谈到的就是指二元 ⑴ 矩阵每行非 0 元素（即“1”）个数 为 p， 每列非 0 元素个数为 q，p>q>=3，m/n=q/p； ⑵ 任意两行或任意两列相重叠的非 0 元素 域。 个数不大于 1； LDPC（Low Density Parity Check Code） ⑶ 非 0 元素的位置按行或按列尽量地随机 码是低密度奇偶校验码的简称，它是一种具 排列，且分布稀疏； 有稀疏校验矩阵的线性分组码。它的名字来 ⑷ 分组长度尽量长（大于 1000）； 源于其校验矩阵 H 的稀疏性，即校验矩阵中 ⑸ 某个子矩阵的逆矩阵存在（满秩）。 只有数量很少的元素为‘1’，大部分都是 对于规则 LDPC 码稀疏校验矩阵还应做 ‘0’。对于一个 GF（2）上的 LDPC 码，它 到如下要求： 可以用一个大小为 m× n 阶的稀疏校验矩阵 ⑴ 每行每列非 0 元素的个数是固定的； H 来描述。稀疏校验矩阵 H 中大部分元素为 ⑵ 不能出现 4 线循环，出现就一定不满秩； 0，只有一小部分的元素等于 1，并且，校 验矩阵中的每一行代表一个校验位，每一列 3 对角线法构造LDPC校验矩阵 [5] 代表一个码元。其满足： LDPC 码的编译码器都是根据稀疏校验 矩阵的行重和列重与码长的比值远小于 1； 矩阵来进行,稀疏校验矩阵非零元素的随机 任意两行或列最多只有一个相同位置上 排列和稀疏性直接影响着码的性能。对角线 的 1； 的方法构造的稀疏校验矩阵是规则 LDPC 码。 任意线性无关的列数尽量大。 在介绍对角线法构造方法之前，先引入 校验矩阵 H(m× n)的一般结构图如图 1 一个概念：副单位矩阵。所谓副单位矩阵， 示。 0001   0100   . .  . .   . .  1010   0100  . . . . . . H = . . . . . . . . . . . . . . . 001 010 . . . . . . 100 010 . . .      .       就是副对角线上元素全为 1，其他元素全为 0 的矩阵。 设一个码长为 n 的 LDPC 码稀疏校验矩 阵 H(m×n)表示为 H(n,q,p)，满足上文的定 性与定量的要求。将所需校验矩阵 H(n,q,p) 分为左右两个矩阵,先分别构造然后合并。 nm × 其具体步骤如下： 图 1 LDPC 码校验矩阵 H 的一般结构 （1）设 a1,a2,a3 是 3 个长为 n/2 的全 1 矢 如果一个码的校验矩阵 H 每一行和每 量，使 a1 在左边方阵的主对角线下距离为 一列中非零元素的个数是相同的，那么称这 1 的位置，a2 在主对角线位置，a3 在主对 样的码为规则 LDPC 码，用（n,q,p）表示该 角线上距离为 2 的位置。 码，其中 n 代表码长,q 代表每列非零元素 （2）每一矢量在大小为 n/2 方阵的次对角 个数，p 代表每行非零元素个数。如果一个 线上布局的剩余部分，可以折断往上分布， 

要求任意两行或两列 1 相重叠的个数不大 将 得 到 的 副 单 位 矩 阵 赋 值 给 右 边 方 阵 于 1，这样得出的线是平行的。 n-g+1 至 n 行、1 至 g 列构成的子矩阵； （3）将 3 条全 1 矢量按列或按行进行随机 并且，为了保持近似下三角的特性，仅对 置换，满足随机性。因是初等变换，所以排 右边方阵对角线下的元素进行随机置换。右 序的随机性不会改变矩阵的秩，仍能满足求 边矩阵的构造过程用 MATLAB 实现图像如图 逆要求。左边矩阵的构造过程用MATLAB实现 3 示。 图像[6] 如图 2 示（为了仿真图像更清晰明了 （5）将构造好的左右两边矩阵合并，生成 展 现 校 验 矩 阵H 的 构 造 过 程 ， 这 里 选 取 校验矩阵。合并后矩阵的图像如图 4 示。 n=256）。 （6）最后将构造好的校验矩阵 H 按公式 （4）右边方阵的 a1 和 a2 的构造方法与左 边方阵类同。但 a3 距离对角线的位置应当 H  =   A B T C D E    (3.1) 等于近似下三角形式当中 g（g=0.0270746n） (3.1)进行分解，分解后的形状如图 5 示。 的大小。具体方法： 其中，A 是（m-g）乘以（n-m）阶矩阵，B 将 a3 布局的剩余部分，构成 g 乘以 g 阶 是（m-g）乘以 g 阶矩阵，C 是 g 乘以（n-m） 副单位矩阵； 左 边 矩 阵 构 造 图 像 左 边 矩 阵 随 机 置 换 后 图 像 图 2 LDPC 校验矩阵 H 左边矩阵的构造过程图像 右 边 矩 阵 构 造 图 像 右 边 矩 阵 随 机 置 换 后 图 像 图 3 LDPC 校验矩阵 H 右边矩阵的构造过程图像 

m n-m A C u g B D 1p m-g 0 T E 2p g 生 成 的 校 验 矩 阵H 图 像 图 4 生成的 LDPC 校验矩阵 H 图像 图 5 对角线法构造的校验矩阵 H 形式 阶矩阵，D 是 g 乘以 g 阶矩阵，E 是 g 乘以 （m-g）阶矩阵，T 是（m-g）乘以（m-g） 阶矩阵,u 为长为 n/ 2 的原始数据信息序列， 1p 与 2p 为校验位；遇到 DB 不可逆的情况，或者对右半部分的构造做些 −=Φ ET + −1 微小的改动，或者在不改变形式的条件下适 DB 可逆。对角线法构造出的校验矩阵可以作为 当调换两行或两列，使得， −=Φ ET + −1 基于近似下三角矩阵的编码算法的校验矩 阵。 4 基于近似下三角矩阵的编码 [7] 基 于 近 似 下 三 角 矩 阵 的 编 码 算 法 是 Richardson 和 Urbanke 提出的一种有效的 编码算法，又称之为 RU 算法，即 Efficient 编码算法，这种算法是利用校验矩阵的稀疏 性，对校验矩阵进行一定的预处理。这种方 法能够降低编码的复杂度，使编码复杂度与 码长接近线性关系。具体步骤为：先重排矩 阵的列，得到一个近似的下三角矩阵，（利 用上文提到的对角线法构造出稀疏校验矩 阵 H）如公式 3.1 所示，将 H 分成六个分块 的稀疏矩阵，见图 5。 将矩阵作线性变换，左乘一个矩阵， 得到一个用于递推校验比特位的矩阵，公式 如 4.1 所示： 1 − I   ET −  =   −    A B T 0   I C D E  B 1 − A 1 − ET A C + − ET B D + T 0    (4.1) −1 + ET DB 是否可逆，若不可逆， 在 进 行 编 码 之 前 ， 需 要 验 证 −=Φ 则需要与前面的列重排，直到满足可逆为止， 然后再进行编码。 将码字向量 c 分成三部分，c=(u ， 1p , 2p )， 1p 的长度为 g, 2p 的长度为（m-g）， 1p 和 2p 合起来表示校验部分。码字和校验 矩阵满足以下关系式： c =TH 0=TcH （4.2） 或者 0 则依据公式 4.2 得出两个方程式： T Au + T Bp 1 + Tp T 2 = 0 (4.3) 1 − ET uCA ) T pDB ( ) − 1 (4.4) ( −+ ET + + 1 − T = 0 ，由方程式(4.4)可以推 −1 + ET DB −=Φ 令 出校验位 1p 的表达式： + 1 −φ −= ET − 1 − ( T p 1 uCA ) T （4.5） 再由表达式(4.3) 和（4.5）得出 2p 的表达 式： T p 2 （4.6） T −= T Bp 1 Au + 1 − ) ( T 依据上述公式，最终实现了 LDPC 码的编码 过程，编码输出码字向量 c=(u ， 1p , 2p )。 5 编码复杂度分析 

编码的每一个过程的复杂度，见表 5.1 和表 5.2 所示。 表 5.1 T p 1 −= 1 −φ ( − ET 1 − uCA ) + T 计算过程和计算复杂度 复杂度 注释 矩阵运算 TCu TAu TAu T 1− ET 1− − −1 ET − 1 − ( −Φ TAu T Cu Au + 1 − ET Au + T T Cu o(n) o(n) o(n) o(n) o(n) T ) 2g ) o( 稀疏矩阵和向量相乘 稀疏矩阵和向量相乘 稀疏矩阵递归运算 稀疏矩阵和向量相乘 加法 gg × 阶矩阵相乘 步骤 1 2 3 4 5 6 步骤 1 2 3 4 表 5.2 p T 2 T −= 1 − T ( Au + T Bp 1 ) 计算过程和计算复杂度 矩阵运算 TAu TBp1 T Bp T Au + 1 T T Bp 1 − − T Au ( 1 + ) 复杂度 注释 o(n) o(n) o(n) o(n) 稀疏矩阵和向量相乘 稀疏矩阵和向量相乘 加法 稀疏矩阵递归运算 从上述两个表，可以清晰地看出计算 Tp1 的总复杂度为 o（n+ 2g ），当 g 尽量小 的时候，LDPC 码的编码运算量就可以控制 参 考 文 献 [1] R.G.Gallager. Low density parity check codes[J].IEEE Transactions on Information Theory.1962,8(1):21-28. 在线性复杂度附近。 [2]C.E.Sshannon.A Mathematical Theory of 6 结论 Communication[J].BSTJ.1948,27：379-423,632-656. [3] 夏洪星.用于 DVB-S2 标准 LDPC 码的研究与实现[D]. 武 本文用对角线法构造了 LDPC 的校验矩 汉：华中师范大学，2005. 阵，并用基于近似下三角矩阵对 LDPC 码进 [4] 贺鹤云.LDPC 码基础与应用[M]. 北京:人民邮电出版 行了编码。整个过程利用 MATLAB 进行了仿 社,2009. 真实验。 [5]贺琛，韩建兵，贺鹤云.一种性能优于 Turbo 码的 LDPC 规 采用对角线方法进行校验矩阵的构造 则码[J].无线电工程. 2008,38（5）：21-23. 的原因： [6] 占军，张倩，满谦.MATLAB 函数查询手册[M].北京：机 （1）对角线法理论简单，便于理解与掌握； 械工业出版社，2011.1 （2）构造出的校验矩阵正是基于近似下三 [7]Aaron E.Cohen,Keshab K.Parhi.A Low-Complexity Hybrid 角阵编码方法所需要的校验矩阵； （3）程序设计简单，易于实现。 LDPC Code Encoder for IEEE 802.3an(10GBase-T)Ethernet[J].IEEE Transactions on Signal 采用基于近似下三角阵的编码方法的原 Processing.2009,57(10):4085-4094. 因主要是编码复杂度低，编译码复杂度与码 长呈线性关系。