作者简介院薛丽(1986-)，女，硕士研究生，工程师，研究方向为数字信号处理，E-mail：********************。
CCSDS 标准中LDPC 码译码器研究与实现
Research and Implementation of LDPC Codes Decoder in CCSDS Standards
薛丽(中国西南电子技术研究所，四川成都610036)
Xue Li (Southwest China Electronic Technology Institute,Sichuan Chengdu 610036)
摘要：目前，准循环LDPC (QC_LDPC)已经广泛应用IEEE 802.11、IEEE 802.16、DVB-S2、CCSDS、3GPP 5G-NR 等系列标准。LDPC 码的性能非常优越、复杂度较低、吞吐量高、可以进行并行解码，解码时延小。该文针对CCSDS131.0-B-2标准中10种码字的LDPC 码以码率为单位在FPGA 上进行了兼容实现，并给出了进一步实现高速译码和降低硬件资源的方法，
为在实际工程实现需要提供了重要参考。关键词：准循环低密度校验码(QC_LDPC 码)；译码器；FPGA 实现中图分类号：TN911.22
文献标识码：A
文章编号：1003-0107(2021)05-0099-06
Abstract:Nowadays,Quasi-cyclic low-density parity-check (QC_LDPC)codes has been widely used in IEEE 802.11,IEEE 802.16,DVB-S2,CCSDS,3GPP 5G-NR series of standards.LDPC code has excellent perfor-mance,low complexity,high throughput,parallel decoding and small decoding delay.This paper aims to compatible implement the 10kinds of code in the CCSDS131.0-B-2standard on the FPGA,and gives the method of further realizing high speed decoding and reducing hardware resources,providing important reference to the realization needs of engineering.
Key words:Quasi-cyclic low-density parity-check codes;decoder;FGPGA implementation CLC number:TN911.22
Document code:A
Article ID ：1003-0107(2021)05-0099-06
0引言
低密度校验码(LDPC)[1-2]是在1963年由Gallager 发明的线性分组码。由于该码的校验矩阵H 具有很低的密度(H 只有少量的"1"，大部分是"0"，即H 的密度很低；H 是一个稀疏矩阵)，故Gallager 称其为低
密度校验码。经过50多年的发展，LDPC 码的构造、编码、译码等方法已经相当完备。LDPC 码已经广泛应用到数据存储、光通信和无线通信等系统中。
在LDPC 码的实现中，译码算法和译码器设计是决定码字性能和应用前景的重要因素之一。目前，BP 算法[3]作为LDPC 码的一种经典译码算法被人们广泛使用。在应用中，人们需要根据具体码字和系统需求，对BP 算法做出相应的改进或调整，使译码器在复杂度适当的条件下，向最优译码性能靠近。
本文针对CCSDS131.0-B-2[4]标准中4种码率10种码字的LDPC 码以码率为单位在FPGA 上进行了兼容实现，并给出了进一步实现高速译码和降低硬件资源的方法，为在实际工程实现需要提供了重要参考。
1LDPC 码的译码迭代机制
1.1QC-LDPC 码定义
QC-LDPC(Quasi-cyclic low-density parity-check)码，即准循环LDPC 码，是根据系统化构造方法构造的一类非常重要的LDPC 码，目前已经成为面向硬件实现LDPC 码研究的热点。QC-LDPC 码可以采用移位寄存器的方式进行编码，大大降低了编码复杂度。针对该类型码字的准循环特性，可以专门设计适用于该类型码字的
认证与实验室
99
电子质量
2021年第05期(总第410期)
图1LDPC 码泛洪机制的典型译码器组成框图
译码器。其校验矩阵由循环矩阵组成，
可以表示为：H qc =A 1,1A 1,2…A 1,t A 2,1A 2,2…A 2,t ……
……A c ,1
A c ,2…A c ,t
⎡⎣
⎢
⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎤⎦
⎥⎥⎥
⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥=[M 1M 2…M t ]
(1)
可以看到该QC-LDPC 码的校验矩阵H qc 由ct 个子矩阵排列而成，其中A i,j 均为b*b 循环矩阵。循环矩阵H qc 为方阵，他的每一行都是上一行的循环右移1位所得，第一行为最后一行的循环移位。对于这样的循环矩阵，他的每一列都是左边一列循环下移一位所得，最左边一列是最后一列的循环移位。循环矩阵的列重和行重都是一样的，记为w 。当w =1时即为置换矩阵(permuta-tion matrix)。循环矩阵可以由它的第一行完全确定，所以可以将它的第一行称为循环矩阵的生成向量。
H qc 的结构特征为：(1)A i,j 重量相对于b 比较小；
(2)H qc 的任意两行(两列)中最多只有一个"1"在相同的位置。
QC-LDPC 码的校验矩阵由单位阵的循环移位矩阵构成，使得码有准循环特性，有利于实现高效编码。并且，码生成和校验矩阵的代数结构特性也利于大规模集成电路实现编译码器。
1.2LDPC 码的译码迭代机制
BP 算法的典型消息传递机制有两种，一种是泛洪(flooding scheduling)译码算法机制，另一种是分层译码算法机制[5]，本文主要利用泛洪机制进行了实现。
在泛洪译码算法机制中，每轮迭代中校验节点信息和变量节点信息都是并行处理的，
即在每次译码迭代中，并行执行完成所有校验节点信息更新运算，
称之为水平运算，且并行执行完成所有变量节点信息更新运算，称之为垂直运算。
泛洪机制将译码过程分为水平运算和垂直运算两部分，该机制中所有的变量信息(或校验信息)可以同时更新计算，实现全并行译码，此时对应的译码器结构称为全并行译码器[6]，其每次译码迭代时间很短，因而可以达到很高的译码吞吐量，但当校验矩阵很大时，即当LDPC 码的码长大于2000时，要同时存储和处理如此多的信息需要大量的存储和逻辑资源，当前的VLSI 工艺水平是几乎不能实现的。但对于QC-LDPC 码而言，我们可以利用校验矩阵的准循环特性，
将全并行译码器转化为部分并行译码器，因而，这种部分并行译码器在实际中得到了广泛的应用。
图1所示为一个典型泛洪机制的LDPC 码译码器硬件实现的组成框图。它主要由两个连接网络、一组变量节点处理单元、一组校验节点处理单元，相应的存储
块和控制单元组成。
100
对于LDPC码，当码长很长时，最大似然译码算法几乎不可实现。因此，寻一种有效的译码算法甚至比构造一个好码更为重要。和积算法(BP算法)通过Bayes 准则获得近似最大后验概率译码，是基于无环图的LDPC码的最优迭代译码算法。
采用的符号表示如下：(1)M(n)表示与变量节点n相连的校验节点的集合，即H矩阵第n列中1的位置；(2) N(m)表示参与第m个校验方程的变量节点的集合，即H 矩阵第m行中1的位置；(3)N(m)\n表示从集合N(m)中去掉元素n之后的子集；(4)M(n)\m表示从集合M(n)中去掉元素m之后的子集；(5)○代表模二和。
LDPC码的和积算法在对数似然比度量下的泛洪译码过程如下：
步骤一、初始化：l=0，最大迭代次数为l max。对于LDPC码的一致校验矩阵H中的每一个非零元h mn=1，0≤m≤M，0≤n≤N初始化：
L(q nm)=L(P n)=L(x n|y n)=log(P(x n=0|y n)/P(x n=1|y n))=2y n/σ2(2)
步骤二、迭代消息传递和更新：
第一步(校验节点更新)：对每个校验节点m及n∈N (m)，计算
L(r
mn
)=(∏sign(L(q n'm)))f[∑f(L(q n'm))](3)其中，
f(x)=-ln tanh(x
2)=ln
e x+1
e x-1(4)
第二步(变量节点更新)：对每个变量节点n及m∈M (n)，计算
L(q
nm
)=L(P n)+∑L(r m'n)(5)
L(Q
n
)=L(P n)+∑L(r mn)(6)第三步(判决)：如果L(Q n)≥0，令x n=0，否则x n=1。
步骤三、译码尝试：
判决码字x~=[x~1,x~2,…,x~N]，如果伴随式x~H T=0，停止迭代，将x作为译码输出，否则跳至第一步继续执行。如果迭代次数到达l max仍未成功，则宣告失败，终止迭代。
2CCSDS中LDPC译码器的实现
2.1修正最小和算法
和积算法中存在着大量的tanh和它的反函数运算，因此计算的复杂度偏高。对校验节点更新的公式进行简化，得最小和算法。
最小和译码算法校验节点更新公式简化为：
L(r
mn
)=(∏sign(L(q n'm)))×min|L(q n'm)|(7)最小和译码算法的译码过程中的初始化和变量节点更新公式和和积译码算法相同。
最小和算法大幅度降低实现复杂度的后果是会损失一定的译码性能，近似导致的译码性能损失通常在0.3dB以上，对于有的LDPC码性能损失更达1.1dB之多。为了改善因校验节点消息更新运算的近似处理而造成的性能损失，已有很多论文做了探讨，为了能让最小和算法的纠错能力更接近BP算法，进行修正后得到的算法统称为修正的最小和算法(modified min-sum algorithm)[7-9]。其中最典型的是J.Chen[10]提出的两种方法，即归一化最小和译码算法(normalized MSA)和带偏移量的最小和译码算法(offset MSA)。
本文采用归一化最小和译码算法进行了实现，乘以一个小于1的常量α改进性能，在性能和硬件实现复杂度进行折衷后，本文实现中α取值为7/8，此时校验节点的更新公式为：
L(r
mn
)=(∏sign(L(q n'm)))×(min|L(q n'm)|)×α(8) 2.2CCSDS中LDPC码特征
CCSDS131.0-B-2标准规定了4种码率的10种QC -LDPC码，该组码字是典型的QC-LDPC码。它的校验矩阵如下所示。
H
1/2
=
0M0M I M0M I M○Π1
I
M
I
M0M
I
MΠ2○Π3○Π4
I MΠ
5○Π60MΠ7○Π8I M
⎡
⎣
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎤
⎦
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥⎥
(9)
H
2/3
=
0M0M
Πq○Π10○Π11I M|H1/2
I
M
Π
12○Π13○Π14
⎡
⎣
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢
⎤
⎦
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥
decoder(10)
H
4/5
=
0M0M0M0M
Π
21○Π22○Π23I MΠ15○Π16○Π17I M|H2/3
I
M
Π
24○Π25○Π26I MΠ18○Π19○Π20⎡
⎣
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎤
⎦
⎥⎥
⎥⎥
⎥⎥
⎥⎥
(11)
H
7/8
=
A
1,1
A
1,2
A
1,3
A
1,4
A
1,5
A
1,6
A
1,7
A
1,8
A
1,9
A
1,10
A
1,11
A
1,12
A
1,13
A
1,14
A
1,15
A
1,16 A
2,1
A
2,2
A
2,3
A
2,4
A
2,5
A
2,6
A
2,7
A
2,8
A
2,9
A
2,10
A
2,11
A
2,12
A
1,13
A
2,14
A
2,15
A
2,16 [](12)
其中，0M、I M、Π1…Π26、A1,1…A2,16都是准循环矩阵，其中非零元的位置计算请参考CCSDS131.0-B-2标准中的相应计算公式，我们可以得到该标准中采用的LDPC码校验矩阵特征如表1所示，其中，子矩阵维数是指每一个循环子矩阵的行数或列数，超行数乘以子矩阵维数为整个校验矩阵的行数，超列数乘以子矩阵维数为整个校验矩阵的列数。
+
n'∈N(m)\n n'∈N(m)\n Δ
m'∈M(n)\m
m∈M(n)\m
n'∈N(m)\n n'∈N(m)\n
n'∈N(m)\n n'∈N(m)\n
+
+
+
+
+
++
++
++
++++
+
+
^^
^
101
电子质量
2021年第05期(总第410期)
表1CCSDS 中10种LDPC 码校验矩阵特征
CCSDS131.0-B-2标准在深空、近地等通信中得了广泛的应用，因此对该标准中的LDPC 码进行研究实现，具有很大的工程实现意义。
由于该标准的码为QC-LDPC 码，根据表1中校验矩阵的特征，可以采用部分并行译码结构，校验节点计算的并行路数为超行数，变量节点计算的并行路数为超列数。2.3译码器的实现
(1)译码器的整体控制部分
整个译码过程基本按照图2所示的三个步骤，进行类似流水线的操作，
即信道初始似然值缓冲单元接收完一帧数据，译码单元开始进行一帧的译码，同时信道初始似然值缓冲单元进行下一帧数据的缓冲；
在完成预定的迭代次数之后，译码结果缓冲单元输出判决结果，译码单元等待(或开始)进行下一帧的译码。
除此之外，译码器控制部分还需要监视迭代主体部分每次迭代的完成
状况，即每次变量节点处理过程和校验节点过程的完成状态，以判断是否达到了预定的最大迭代次数，以及何
时启动各个处理单元等。
图2译码器的整体控制示意图
由图2可以看出，校验节点处理运算和变量节点处理运算是整个硬件结构的核心部分，本文以下将单独对其进行介绍。
(2)校验节点更新
将校验节点处理过程分为两部分进行，一部分计算符号，另一部分计算归一化比较结果，在这两部分计算完毕后，将符号和归一化比较结果值转变为补码输出。对于行重为k 超行的校验节点的计算过程示意图如图3所示。
(3)变量节点更新
图3校验节点处理单元示意图
观察变量节点更新公式和译码判决公式，
显然如果
102
优先计算出L (Q n )，则L (q mn )的计算将会变得更加简单，只需减去多加的L (r mn )：
L (q mn )=L (Q n )-L (r mn )
(13)
信道的初始似然值用Ln 表示，对于一个列重为他
的超列的变量节点的计算过程如图4所示。
图4变量节点处理单元示意图
需要说明的是，
变量节点处理单元接收符号-幅度格式的数据需要先转化为二进制补码格式的数据，而输出的二进制补码格式数据也需转化为符号-幅度格式之后再被写回存储单元中。2.4实现结果
本设计在QuartusII9.0平台下综合，选用Altera Stratix II EP2S180F1508I4芯片，通过Verilog HDL 硬件描述语言完成了CCSDS131.0-B-2标准中的4种码率的10种QC-LDPC 码设计与实现，
由于不同码长的码字在码率相同时共用一个校验矩阵，
只是子矩阵维数不同，为了节省资源，结合标准中码字的特点，我们可以以码率为单位进行资源复用兼容，可大大节省硬件资源。其实现的译码器资源利用表如表2所示。
表2CCSDS 中4种LDPC 码率译码器资源利用表
译码器延时计算公式为：T delay ≈2×E×iternum
f sysclk
(14)
其中，f sysclk 为译码器工作时钟，E 为表1中每个子矩
阵维数，iternum 为译码迭代次数。
则译码器接收最高码速率，即译码器吞吐量为：
coderate ≈framelength
T delay
(15)
其中framelength 为一帧数据长度。
以7/8码率LDPC 码为例，framelength 为8160bit，本实现中f sysclk 为120M，E 为511，iternum 为30次，则译码器吞吐量约为32M，可满足中低速应用的需要。
若要实现更高速译码，
可以将E 取较小的值即继续提高译码器并行度，或者适当的减小迭代次数，或者提高译码器工作时钟，但带来的代价是硬件资源的增加或译码性能的降低。
在译码器吞吐量不变的情况下，
若要进一步降低硬件成本，节省资源，则可以将4个码率的矩阵位置提前存储到存储器或者查表之中，
译码器的并行路数按照最大的子译码器来进行设计，
校验节点及变量节点的计算也按照最大的度数来进行设计，
然后根据需要的码率码字查需要的参数进行选择译码，
这样就可以将所有的译码器兼容到一个译码版本之中，但带来的代价是译码器复杂度的增加。
3结束语
信道编码技术是现代通信系统的关键技术之一，LDPC 码则是近年来最受关注的信道编码之一，由于LDPC 码纠错能力强且易于实现并行译码，已经成为多个通信标准的信道编码码型，
本文介绍了QC-LDPC 码的定义及译码方法，并针对CCSDS131.0-B-2标准中4种码率10种码字的LDPC 码以码率为单位在Altera Stratix II EP2S180F1508I4FPGA 芯片上进行了兼容实现，并给出了进一步实现高速译码和降低硬件资源的方法，为在实际工程实现需要提供了重要参考。
参考文献：
[1]Gallager R G.Low-density parity-check codes[J].IRE Tra nsactions on Information Theory,1962,8(1)
:21-28.[2]Gallager R G.Low-Density Parity-Check Codes[M].Cam-bridge,MA:MIT Press,1963.
[3]MacKay D J C,Neal R M.Near Shannon limit performance of low density parity check codes [J].Electronics Letters,1996,32(18):1645-1646.
[4]CCSDS 131.0-B-2.TM SYNCHRONIZATION AND CHANNEL CODING [S].Washington D.C.,USA:CCSDS,2011.
[5]薛丽.码率兼容QC-LDPC 码的译码器设计及FPGA 实
现[D].西安：西安电子科技大学,2011.
下转107页
103

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。