一种适用于层间并行译码器的QC-LDPC码构造方法

摘要

本发明涉及一种适用于层间并行译码器的QC-LDPC码构造方法，1）初始化QC-LDPC码校验矩阵参数；根据并行行分层译码器电路要求设置延迟值Γ；设置QC-LDPC码校验矩阵H中循环偏移量基础矩阵Hb的每一行的偏移量Roffset(i)；2）利用Block-PEG算法构造QC-LDPC码的循环偏移量基础矩阵Hb，构造所述H矩阵对应的基础校验矩阵二分图的连接及权重时，满足条件：同一变量节点与校验节点的任意两个连接之间的权重间距Δ不小于设置的延迟值，即满足Δ≥Γ；3）根据构造得到的循环偏移量基础矩阵Hb，填充相应偏移量的循环偏移单位矩阵和全0矩阵，得到最终QC-LDPC码的校验矩阵H。本发明方法基于PEG算法，在QC-LDPC码设计过程中，规划了校验矩阵中每列的偏移量间距，保证所造码能适用于全并行行分层译码器结构。

说明书

技术领域

本发明涉及一种准循环LDPC（QC-LDPC）码的构造方法，具体涉及适用于层间并行译码 器规划偏移量间距的准循环LDPC码构造方法，属于通信工程差错控制领域。

背景技术

信道编码技术是提高通信系统可靠性的基本技术，其中LDPC码作为一种误码性能优良， 便于工程实现的信道编码方法，被广泛用于现代通信系统，已经被WiMAX，DVB-S2等通信标 准所采纳。随着通信系统对传输速率要求的日益增长，信道编码的高速译码成为迫切需求。 因此LDPC高速译码算法和结构得到了广泛研究，同时更适于高速译码的码集构造算法也要得 到相应的发展。

以实现高速译码为目标的针对准循环LDPC码（QC-LDPC）码的译码算法及相关的硬件结 构设计很多，其中分层译码算法的平均迭代次数可比传统置信度传播译码方式减少一半，能 有效地提高译码速率，是近年来应用研究的热点。

LDPC行分层译码一般采用最小和算法，其译码流程中的关键公式如下：

u_ij＝U_j-v_ij       (1)

$v_{\mathrm{ij}}^{\prime }=\underset{k\in N\left(i\right)\backslash j}{\Pi }\mathrm{sign}\left(u_{\mathrm{ik}}\right)\times \underset{k\in N\left(i\right)\backslash j}{\min }\left|u_{\mathrm{ik}}\right|\times \alpha ---\left(2\right)$

U′_j＝u_ij+v′_ij   (3)

上式中U_j是变量节点后验概率信息，v_ij是校验节点i传给变量节点j的外信息。N(i)为 校验节点i相邻的变量节点集合，N(i)|j是N(i)集合排除节点j后所得的集合；sign(.)表 示求符号运算，min(.)表示对集合求最小运算；0<α<1。

现有技术中按所有层并行的层间并行行分层译码结构给出了具体的优化设计和实现，证 明了该结构优异的速率潜力图1所示，但是该译码结构对码的校验矩阵有特殊要求，目前还 没有发现给本译码结构专门设计的码集构造算法，所以需要提出一种性能优良而且能直接适 用于层间并行译码结构的码构造算法。

图1中每1层对应QC-LDPC码循环偏移量基础矩阵中的一个行，所有层同时进行译码 操作。每层处理电路包含1个并行行运算器模块(CNU)，它完成式(1～3)对应的运算。图1中 的外信息存储器模块(ExRam)存储式(1)中的外信息v_ij变量，存入更新过的外信息v′_ij。后验信 息中转存储器模块(AppTMem)输出式(3)需要的后验概率信息U_j，并回存更新过的后验信息 U′_j。在译码开始阶段，AppTMem输入信道信息，然后AppTMem通过与所有层互连将U_j值 在不同层之间互传。迭代次数足够后，判决模块根据U_j符号判决得到译码结果。图1中的流 水线型CNU能够不间断地进行译码操作，可在p（循环偏移单位矩阵大小为P*P）拍内完成 一轮迭代，采用现有特殊码字可证明该结构有很高的速率潜力，可参考文献[Zhang K,Huang X, Wang Z.High-throughput layered decoder implementation for Quasi-Cyclic LDPC codes[J].IEEE Journal on Selected Areas in Communications.,2009,27(6):985-994.]。

图2是图1中并行行运算器模块(CNU)的示意图，其中行维度以3为例，所有模块为组合 逻辑。图2中减法模块执行式(1)运算；求绝对值最小及次小模块执行运算；求符号 积模块执行运算；行运算合成模块接着执行完式(2)运算；加法模块执行式(3)运 算；图2中3根虚线处可各插入一列寄存器造成一级流水线。图1中的行运算器单元若含两 个或更多图2所示的CNU，则迭代一轮需要的拍数可以减少为一半或更少，译码速率可以更 快。

图1～2中电路存在层间处理和传输延迟。CNU模块延迟Γ₁的典型值为1～4拍，AppTMem 模块的读写操作造成的最小传输延迟Γ₂为0~3(0表示允许直通)。一个U_j变量值进入第I₁层 CNU入口，经过更新到达第I₂层CNU入口，最快需要延迟Γ＝Γ₁+Γ₂拍，然后才允许被后续运 算访问。Γ的典型值为1~7，Γ值随着资源速率要求等因素变化。

由于电路的层间处理和传输延迟，使用普通QC-LDPC码时，分层译码器所有层进行并行 运算时，同一变量节点所对应的多个层之间可能会存在U_j变量值的访问冲突问题。

图3(a)具体展示了有访问冲突的情形,其中QC-LDPC校验矩阵H中p＝10，H的一个块列 对应循环偏移量基础矩阵的一列。列维度为2。其中后验信息(App)框包含H的一个块列对应 的U_j变量，R₀到R₉表示子行号，A₀到A₉表示子列号。图3(a)包含H中同一个块列的第I₁块行 (层)和第I₂块行(层)的两个单位循环移位子矩阵B₁,B₂。B₁子矩阵的偏移量为Offset(I₁)＝0，B₂子矩阵的偏移量为Offset(I₂)＝2。第I₁层CNU和第I₂层的CNU同时从各自的第R0行开始逐行连 续计算，图1～2流水线不含等待节拍，故第I₁层要用到的Uj值依次为{U₀,U₁,U₂,U₃,U₄...}，第 I₂层要用到的U_j值依次为{U₂,U₃,U₄,U₅,U₆...}，如表1所示。第I₂层对U₂值的更新从第0拍开 始，第I₁层在第2拍后要访问第I₂层更新过的U₂，时间差为Δ₁＝2-0拍。由于两层之间处理和 传输的延迟Γ＝4，则需再空闲等待Γ-Δ₁＝2＞0拍才能等到更新后的U₂值，这就是U₂访问冲突。 即如果图1～2的流水线中不插入空闲节拍，且不满足Δ₁≥Γ，则会产生U₂访问冲突问题。同 理，后续U₃□U₉等变量也存在访问冲突问题。访问冲突破坏了行分层译码算法的置信度传播， 故图3(a)对应的码不适用于图1的高速并行结构。

表1访问冲突问题中的U_j读取情况

图3(b)展示了可避免访问冲突的情形，可以设计如图3(b)特征的矩阵H，以满足图1结 构的要求。图3(b)是图3(a)基础上改用Offset(I₂)＝6所得，第I₂层用到的U_j变量依次变为 {U₆,U₇,U₈,U₉,U₀,U₁,U₂...}，如表1末行所示。第I₂层要在第0拍读取U₆，第I₁层要在第6拍读 取U₆，节拍差Δ₁＝6,Γ＝4，故满足Δ₁≥Γ，第I₁层可以在第6拍使用第I₂层已更新过的U₆变量, 不需插入空闲等待节拍。同理，第I₁层在第0拍读取U₀，第I₂层在第4拍读取U₀，节拍差 Δ₂＝4,Γ＝4，故满足Δ₂≥Γ,所以第I₂层可以及时读到第I₁层更新过的U₀变量，没有U₀访问冲 突问题。同理，其他的U_j变量也没有访问冲突问题。Δ₁,Δ₂也可以由式(4～5)用偏移量间距计 算得到：

Δ₁=(p+Offset(I₂)-Offset(I₁))mod p=6-0=6    (4)

Δ₂=(p+Offset(I₁)-Offset(I₂))mod p=10+0-6=4 (5)

定义偏移量间距Δ＝min(Δ₁,Δ₂)，min(·)表示求最小运算。要Δ₁≥Γ，Δ₂≥Γ都成立，只需Δ≥Γ 成立。为了能实现图1中结构，QC-LDPC码循环偏移量基础矩阵中维度为2的列的偏移量要 满足Δ≥Γ。Δ₁,Δ₂,Δ涉及到循环偏移量，图3(b)中情形可进一步在图4(a)所示的偏移量圆周 中理解，Δ就是各偏移量在圆周上排列的时候，其所在位置在圆周上的最小间距。

若QC-LDPC循环偏移量基础矩阵某列维度大于2(比如为4)，参见图4(b),四个偏移量散布 在偏移量圆周上。若保证本列任何两偏移量的间距Δ≥Γ，即保证了Δ_c≥Γ(c＝1,2,3,4)，则在图 1结构电路中，安排该列对应的U_j变量在4层间的传递次序为：I₁→I₃→I₂→I₄→I₁周而复始， 则任意两层之间的U_j传递没有访问冲突。同理，循环偏移量基础矩阵其他列也要求Δ≥Γ。

若要QC-LDPC码适用于图1结构，需其循环偏移量基础矩阵所有列中的任意两个偏移量间 距Δ满足Δ≥Γ。由于普通码在构造时不含有Δ≥Γ的规划，现有QC-LDPC码一般不适于图1的 无空闲等待并行译码结构。为此，本专利的目的是直接构造满足Δ≥Γ的QC-LDPC码。

发明内容

本发明提出了一种适用于层间并行译码器的QC-LDPC码构造方法，通过寻找最优校验 节点时，加入可用偏移量的限制，从而使构造的QC-LDPC码能够在进行层间并行译码时能 够不产生冲突。

为了实现本发明的目的，采用的技术方案概述如下：一种适用于层间并行译码器的 QC-LDPC码构造方法，其步骤如下：

1）初始化QC-LDPC码校验矩阵参数；根据并行行分层译码器电路要求设置延迟值Γ； 设置QC-LDPC码校验矩阵H中循环偏移量基础矩阵H_b的每一行的偏移量Roffset(i)；

2）利用Block-PEG算法构造QC-LDPC码的循环偏移量基础矩阵H_b，构造所述H矩阵对 应的基础校验矩阵二分图的连接及权重时，满足条件：同一变量节点与校验节点的任意两个 连接之间的权重间距Δ不小于设置的延迟值，即满足Δ≥Γ；

3）根据构造得到的循环偏移量基础矩阵H_b，填充相应偏移量的循环偏移单位矩阵和全 0矩阵，得到最终QC-LDPC码的校验矩阵H。

步骤1）中需要初始化QC-LDPC校验矩阵参数，包括：初始化校验矩阵H对应的循环偏 移量基础矩阵Hb的列数即变量节点个数n，行数即校验节点个数m及校验矩阵维度分布函数； 循环偏移单位矩阵(Block)的大小pxp；用i和j分别表示基础校验矩阵的行号和列号，1≤i ≤m,1≤j≤n。

确定校验矩阵维度分布函数，可利用密度推演方法或者EXIT图方法；

所述步骤2）利用Block-PEG算法构造循环偏移量基础矩阵H_b包含以下步骤：

2-1）初始化循环偏移量基础矩阵Hb的二分图，向所述基础校验矩阵的二分图中添加m 个没有连接的校验节点；

2-2）向二分图中逐个添加变量节点，挑选校验节点建立连接，并确定边线权重，满足条 件：同一变量节点与校验节点的任意两个连接之间的权重间距Δ满足Δ≥Γ；

2-3）判断是否所有变量节点被添进二分图，如果否，则返回2-2），如果是，则进入步 骤3）。

满足2-2）所述与满足Δ≥Γ条件的目的校验节点建立连接路径包括以下步骤：

2-2-1）以当前添加的变量节点j为根节点展开为二分图；

2-2-2）计算当前变量节点j相邻各边的权重与相应的行移位量之和，形成SOffset集合；

2-2-3）挑选出距离根节点j最远且维度最小的校验节点，形成集合一，并计算集合一中 校验节点的所有可用偏移量；

2-2-4）求出上述集合一中校验节点的所有可用偏移量与当前校验节点的行移位量之和， 形成SOffsetR集合；

2-2-5)计算步骤2-2-4）中SOffsetR集合任一元素与步骤2-2-2）中SOffset集合所有元 素之间的所有偏移量间距Δ；

2-2-6)通过遍历搜索求2-2-4）中SOffsetR集合中的一个元素，可用（i,k）表示，其 中i表示集合一中的可用校验节点i，k表示可用校验节点的第k个可用偏移量，使得其与 2-2-2）中的SOffset集合中的所有元素之间的偏移量间距Δ都大于等于设置的延迟值Γ，即 满足Δ≥Γ。如果SOffsetR中的所有元素都不能满足上述条件，那么返回2-1），重新开始构 造；如果SOffsetR中有多个值可用，则随机选择或选取使得Δ最大的值，进入2-2-7）；

2-2-7)选择校验节点i建立与当前根节点的连接，而边线权重取为p_i(k)，表示校验节点 i的第k个可用偏移量，判断根节点的维度是否满足维度分布要求，若满足则进入步骤4）； 若不满足则返回步骤2-2-1）继续遍历添加。

所述步骤2-2-3）中计算集合一中校验节点所有可用偏移量，依次遍历根节点到集合一 中校验节点的所有路径，计算路径权重累计值：其中2L是路径环 长，p(i_k,j_k)是路径上的边线权重值；按照随机原则或者环长最大化原则获得该校验节点的所 有可用偏移量。

所述步骤2-2-2）形成SOffset(r)＝[p(r,j)+ROffset(r)]mod p集合，其中r∈N(j)，N(j)表示与 当前变量节点j相邻的校验节点集合,p(r,j)表示校验节点r与变量节点j间的边线权重(偏 移量)，p＞p(r,j)≥0。

所述步骤2-2-4）中集合一中校验节点的所有可用偏移量与当前校验节点的行移位量之 和SOffsetR(i,k)＝(p_i(k)+ROffset(i))mod p，其中p_i(k)表示校验节点i的第k个可用的偏移量。

所述偏移量间距为：Δ(i,k,r)＝min(Δ₁(i,k,r),Δ₂(i,k,r))其中，

Δ₁(i,k,r)＝(p+SOffsetR(i,k)-SOffset(r))mod p Δ₂(i,k,r)＝(p+SOffset(r)-SOffsetR(i,k))mod p，

H矩阵维度分布函数可采用与Wimax码形式相同的双对角线结构。

本发明的有益效果：

本发明方法基于PEG算法，在QC-LDPC码设计过程中，规划了校验矩阵中每列的偏移量 间距，保证所造码能适用于全并行行分层译码器结构，达到译码器的超高速吞吐率。经过仿 真，所构造码误码率性能良好。

附图说明

图1是典型的并行行分层高速QC-LDPC译码器结构示意图。

图2是图1中并行行运算器模块(CNU)的示意图。

图3a是不同层间的后验信息访问冲突示意图。

图3b是避免不同层间的后验信息访问冲突示意图。

图4a是偏移量p=10时循环偏移量间距示意图。

图4b是偏移量p=10时，四个偏移量散布在偏移量圆周上示意图。

图5是当前变量节点为根节点展开为树状子图。

图6是本发明适于层间并行译码器的准循环LCPC(QC-LDPC)码OffsetBPEG构造算法构造 的码偏移量基础校验矩阵Hb。

图7是本发明适于层间并行译码器的准循环LCPC(QC-LDPC)码OffsetBPEG构造算法构造 的码偏移量基础校验矩阵的行移位矩阵。

图8是通过本发明的OffsetBPEG方法构造出的0.5码率QC-LDPC码的误码率性能比较仿 真图。

图9是通过本发明的OffsetBPEG方法构造出的0.75码率QC-LDPC码的误码率性能比较 仿真图。

具体实施方式

下面通过构造m=12,n=24,p=96，码率为0.5，码长为2304的QC-LDPC码对构造流程进 行说明。

1）初始化QC-LDPC码校验矩阵参数；根据并行行分层译码器电路要求设置延迟值Γ； 设置QC-LDPC码校验矩阵H中基础校验矩阵H_b的每一行的偏移量Roffset(i)；

2）利用Block-PEG算法构造QC-LDPC码的循环偏移量基础矩阵H_b，构造所述H矩阵对 应的基础校验矩阵二分图的连接及权重时，满足条件：同一变量节点与校验节点的任意两个 连接之间的权重间距Δ不小于设置的延迟值，即满足Δ≥Γ；

3）根据构造得到的循环偏移量基础矩阵H_b，填充相应偏移量的循环偏移单位矩阵和全 0矩阵，得到最终QC-LDPC码的校验矩阵H。

步骤1）中确定H矩阵维度分布函数，本例采用和WIMAX码中0.5码率同参数码的列维 度分布。

步骤1）中根据全并行行分层译码器电路要求设置延迟值Γ=7。这个参数和电路结构有 关。对于图1译码结构，Γ设置越大，得到的码可以允许的译码流水线延迟越大，一个流水 级的组合逻辑可更简单，所以允许的时钟速率更高，流水线型译码器的吞吐率也更高，但是 Γ越大构造难度加大。此方法构造的码也适用于图1中延迟小于Γ的译码电路，而没有任 何吞吐率损失。

步骤1）中对应Hb的m(=12)行，取行移位量ROffset＝{8,0,8,0,8,0,8,0,8,0,8,0}。 ROffset值的选取要求很宽松，为了最简单，取各元素为两种小值，但也需考虑4步的要求。 步骤2）中，为解释方便，用i，r表示校验节点，j表示变量节点，其中0<=i<m,0<=r<n,0<=j<n。

步骤2）中为了便于编码，需要采用各种双对角线结构或者其变形。本例采用与Wimax 码形式相同的双对角线结构，为使Hb1双对角部分的每列造成的偏移量间距满足Δ≥Γ，每 列的SOffset(i)值的差别要大于或等于7。显然3步Roffset的取值满足要求。

步骤2）中利用Block-PEG方法展开二分图。考虑当前列已添加的非-1元素的偏移情况， 挑选出距离根节点j最远且维度最小的校验节点，形成集合一，为后续校验节点选择和边线 权重选择提供候选集合，体现了Block-PEG算法的特点。计算集合一中校验节点的所有可用 偏移量与当前校验节点的行移位量之和为确保避免访问冲突，确保Hb矩阵对应的Hb1矩阵满 足Δ≥Γ。在给Hb的一个列新添一个非-1元素时，都要计算对应的Hb1矩阵中对应列新添 的偏移量和已经加入的其他偏移量的间距Δ，并使Δ满足Δ≥Γ，最终保证Hb1所有列都 满足Δ≥Γ。

图6是本文算法构造完成的偏移量基础校验矩阵Hb。图6的左12列对应信息比特部分， 右12列双对角结构对应校验比特部分，便于LDPC编码。查看图6的第7列对应的偏移量为 {25,94,60}，对应的循环行移位量为ROffset7={0,0,8},所以依据式8)计算出本列对应的 Hb1偏移量SOffset7={25,94,68}，即为图7的第7列。依此类推，由式8)从图6得到图7 矩阵Hb1。

可以图7第11列为例来检查该图矩阵是否满足Δ≥Γ。第11列的偏移量集合SOffset₁₁= {10,92,53,66,23,37}，要确认SOffset₁₁任意两元素的循环偏移间隔Δ满足Δ≥Γ，只 需确认排序以后的偏移量序列所含间隔的最小值DifOffMin满足DifOffMin≥Γ。按大小顺 序重排SOffset₁₁，得到SOffset₁₁’={10,23,37,53,66,92}，得到每个数和其右侧相邻数 间隔的数列为{13,14,16,13,26,14}。SOffset₁₁’中的最小值DifOffMin=13,即满足 DifOffMin＞Γ，即第11列满足Δ≥Γ。注意，SOffset₁₁’中92的右侧数是循环过来的 SOffset₁₁’第一个元素10，92和10的偏移量间距为(p+10-92)mod p=14。同理，可确认图 7所有其他列都满足Δ≥Γ,即所构造的码满足偏移量规划。

图7相对于图6进行了每p=96行内的行循环移位，两种校验矩阵从二分图看是相同的， 它们对应相同的QC-LDPC码集合。在实际中，可以依照图6进行QC-LDPC编码，依照图7结 构进行图1的全并行分层高速译码。图7码和图6码的大小和维度分布相同，因而采用译码 电路(本文图1的实例)可以达到该结构带来的2Gbps级译码速率。

OffsetBPEG码构造算法分析

表2给出OffsetBPEG构造常见码长、码率QC-LDPC码的例子，表中参数包括码长、码率、 分块大小p、延迟要求Γ、OffsetBPEG构造布通率等。其中平均迭代次数表示表中每行采用 相同的典型信噪比条件(即能使平均迭代次数取在10左右的一个信噪比)成功译码所需的平 均迭代次数。表2中OffsetBPEG算法布通率是算法对当前参数码的构造成功机率，一般基础 矩阵越大，p值越大，构造越容易成功，而Γ越大，布通难度会加大。算法存在随机选择环 节，所以可通过增加尝试次数达到构造成功。从这些数据看，本算法能够有效地构造LDPC码。

表2可构造成功的LDPC码参数

OffsetBPEG码性能分析与讨论

本节给出OffsetBPEG构造LDPC码的误码率性能仿真情况。利用OffsetBPEG算法构造得 到各种Γ值，码长分别为2016（p＝84），8064（p＝252），64800（p＝360），码率分别为0.5 和0.75的6个QC-LDPC码。然后用20次迭代的行分层译码算法仿真其误码率性能，分别与 BPEG（Block-PEG）构造得到的8064码长、WiMAX中的2016码长、DVB-S2中的64800码长的 LDPC码的误码性能进行对比，结果可参见图8和图9。从图8～9的对比可看到用OffsetBPEG 算法得到的LDPC码与BPEG算法得到的LDPC码以及WiMAX、DVB-S2标准中的LDPC码具有相 当的性能，但本文构造的LDPC码在结构上进行了优化，确保能够采用图1中的高速并行结构 译码。为所有层并行译码的QC-LDPC译码结构设计了OffsetBPEG码构造算法。本文提出的设 计方法基于PEG算法，在QC-LDPC码设计过程中，规划了校验矩阵中每列的偏移量间距，保 证所造码能采用全并行行分层译码结构，达到译码器的超高速吞吐率。仿真结果表明 OffsetBPEG算法能有效地构造QC-LDPC码，Offset-BPEG算法所构造的码在性能上与 Block-PEG、DVB-S2、WiMAX等码接近。本发明为面向译码器深度实现的LDPC码设计提供了 参考。