多码率码型QC-LDPC编码器的FPGA实现

FPGA Implementation of Multi-Bitrate Pattern QC-LDPC Encoders

摘要: LDPC码作为一种线性分组码，具备优异的纠错性能，被广泛应用在无线通信中的信道编码领域。采用QC-LDPC生成矩阵的编码方法，设计了一个支持多码率准循环低密度校验码的编码器，编码器的硬件结构由生成校验码单元(gccu)、源码暂存单元(ocsu)和控制单元(ctrl)等三个主要部分构成，ocsu通过对存储单元进行切割，采取乒乓操作，在数据对乒路原始数据进行编码的同时，将另一帧数据写入乓路，提高了编码速率；gccu实现编码的运算过程以及对生成矩阵进行预存储，通过分析各种码型生成矩阵的特点，对矩阵进行划分，提取必要生成向量进行缓存，减少资源占用；为了满足多种码型、码率的编码需求，加入配置信号，可以根据不同矩阵列块数量、块大小的不同分别选择相应数量的运算单元以及运算次数。此套编码器共支持四种码率、六种码型的编码模式，并支持后续的快速拓展。在XILINX的XC7K325tffg900 FPGA上，采用verilog语言完成了各种码率的仿真综合，同时搭建MATLAB软件模型进行验证，证明了本方案的可行性与有效性。

Abstract: As a linear packet code, LDPC code has excellent error correction performance and is widely used in the field of channel coding in wireless communications. Using the QC-LDPC generation matrix coding method, designed an encoder that supports multi-bitrate quasi-cyclic low-density check digitization, the hardware structure of the encoder is composed of three main parts such as generating the checksum unit (gccu), the source code staging unit (ocsu) and the control unit (ctrl). ocsu cuts the storage unit and performs ping-pong operation. When the original data is encoded on the ping circuit, another frame of data is written onto the ping circuit to improve the coding rate. gccu implements the operation process of coding and pre-storage of the generation matrix. By analyzing the characteristics of the generation matrix of various code types, the matrix is divided and the necessary generation vector is extracted for caching to reduce the occupation of resources. In order to meet the coding requirements of various code types and code rates, the corresponding number of operation units and operation times can be selected according to the different numbers and sizes of blocks in different matrix columns by adding configuration signals. This set of encoders supports a total of four-bit rates, six code patterns of coding modes, and supports subsequent rapid expansion. On XILINX’s XC7K325tffg900 FPGA, a simulation synthesis of various bitrates was completed using the verilog language. At the same time, the MATLAB software model was built for verification, which proved the feasibility and effectiveness of the scheme.

1. 引言

LDPC (Low-Density Parity-Check Codes，低密度奇偶校验码)作为一种前向纠错码，最早在20世纪60年代由Gallager提出 [1] [2]，LDPC码具备优异的纠错性能，其性能可以逼近香农极限，但是随机构造的LDPC码由于没有比较明显的结构特征，存在编译码的复杂度高以及矩阵存取困难等问题，不利于硬件实现，准循环LDPC (QC-LDPC, Quasi-Cyslic Low-Density Parity-Check Codes)是一种几何化的LDPC编码，在具备LDPC编码优点的同时，算法的低复杂度以及生成矩阵的规律性都提高了QC-LDPC编码的可实现性。

经过近十几年的发展研究，随着LDPC码的相关技术日趋成熟 [3] [4]，研究人员对LDPC编码器进行了大量研究 [5] - [10]，文献 [4] 中，作者基于QC-LDPC提出了一种基于生成矩阵的编码结构，编码的复杂度和源码的长度成正相关，极大地降低了编码运算的复杂度，但是该文献并没有描述详细的编码器整体架构。文献 [5] 给出了一种基于生成矩阵的部分并行编码器方案并实现了三种码率的编码，但是三种码率的生成矩阵在构造形式上一致，具体体现在生成矩阵的子矩阵大小均为127，使得生成矩阵的构造以及编码的运算过程相对简单。

综上所述，目前已有的研究大多为LDPC译码器的实现，对于LDPC编码器的研究较少，此外，随着各种协议中LDPC的码标准不断更新，编码的码率以及构造编码所需的生成矩阵形式都在不断增加，而已有的LDPC编码器往往只能支持单一的编码码率和生成矩阵形式，势必会造成资源的浪费，影响LDPC编码器的更新迭代。

基于此，本文通过研究LDPC的编码算法和生成矩阵的矩阵特征，对编码的存储方式以及运算单元做了相应的改进，设计了一种可以同时支持四种码率和六种码型的LDPC编码器。

2. LDPC编码基本原理

LDPC码可以通过校验矩阵或者生成矩阵来定义，它的特点是在校验矩阵中元素“0”的数量远比元素“1”多，元素“1”的密度非常低，使得校验矩阵具有很强的稀疏性。对于码长为m的发送码，其中信息位长度为n，那么校验位码长为k = m − n，码率为n/m，校验码的产生只与长度为n的信息位有关。LDPC码根据H校验矩阵可以分为规则LDPC和非规则LDPC，规则LDPC的校验矩阵中每行和每列有着相同个数的元素“1”，即行重列重相同，反之，行重或者列重不同的称之为非规则LDPC。图1为随机构造的一个(6, 2, 3)的规则LDPC矩阵及其Tanner图。

Figure 1. The 6 encoding methods supported by the LDPC encoder

图1. LDPC编码器支持的6种编码方式

该矩阵每行的元素“1”数量相同，均为3，行重为3；每列的元素“1”数量相同，均为2，列重为2，为规则LDPC矩阵。按照一般的线性分组码，H校验矩阵的码率计算公式为：(矩阵列数 − 矩阵行数)/矩阵列数，故该H校验矩阵的码率为1/2。将Tanner图对应到校验矩阵中，校验节点的数量对应矩阵的行数4，变量节点的数量对应矩阵的列数6，每个校验节点连接三个变量节点，每个变量节点与两个校验节点相连，当LDPC码的码长变得更长时，矩阵的稀疏性也就更好。

准循环LDPC (QC-LDPC, Quasi-Cyslic Low-Density Parity-Check Codes)是一种几何化的LDPC编码，它的校验矩阵可以分为众多大小相同的子矩阵，每个子矩阵都是单位矩阵循环移位得到或者是全零的方阵。每个子矩阵的具体特点如下：

1) 每个子矩阵都是一个方阵。

2) 子矩阵的每一行都是由上一行向右移动一位得到的(矩阵的第一行由最后一行循环右移一位得到)，同样地，循环移动列也可以得到该子矩阵。

3) 只通过一个行向量或者列向量的不断循环移位就可以构造出完整的校验矩阵。

QC-LDPC的H校验矩阵可以表示为：

$H=\left[\begin{array}{cccc}{A}_{11}& A_{12}& \cdots & A_{1c}\\ A_{21}& A_{22}& \cdots & A_{2c}\\ ⋮& ⋮& \ddots & ⋮\\ A_{l1}& A_{l2}& \cdots & A_{lc}\end{array}\right]$

式中A_i,j为循环子矩阵，循环子矩阵为B × B大小的零矩阵或者由循环行列式构成的循环方阵，B代表子矩阵的块大小，跟随不同编码码率变化。得到H校验矩阵后，通过H校验矩阵与G生成矩阵之间的正交性H × G^T = 0，推导出LDPC编码所需的G生成矩阵。

根据上述原理，使用软件对编码进行预处理，首先通过MATLAB软件对校验矩阵的原始矩阵求解得到实际的校验矩阵，原始矩阵的形式为 $H={\left[p\left(m,n\right)\right]}_{l\times c}$，如果p(m, n)的值等于0，代表A_m,n矩阵为单位矩阵，如果p(m, n)的值等于−1，代表A_m,n矩阵为单位零矩阵，如果p(m, n)的值是一个大于零的数值X，代表A_m,n矩阵为经过X次右移循环的单位矩阵，所有情况的单位矩阵大小均由该编码码型唯一决定。

3. LDPC编码器的总体方案

设计出的编码器共支持4种码率、6种编码方式，每种编码的矩阵特征均不相同。LDPC编码器支持的6种编码方式见表1所列。

Table 1. 6 encoding methods supported by the LDPC encoder

表1. LDPC编码器支持的6种编码方式

3.1. LDPC编码器硬件结构

LDPC编码器由生成校验码单元(gccu)、源码暂存单元(ocsu)和控制单元(ctrl)组成。为了使硬件同时支持多种码率码型的编码要求，在源码暂存单元对多种码率的生成矩阵进行存储，具体为根据生成矩阵的行数、列数等矩阵特征，提取各子矩阵的基向量存入ROM中。在生成校验码单元，以生成矩阵的一个列块为一个运算对象，运算单元的数量和码率中最大矩阵列块数相同，在实际运算时，根据不同码率的配置信号选择相应数量的运算单元，当源码长度为length时，获得校验结果的时间为length + n (n < 5)个周期。

由于本LDPC编码的输出数据格式为校验码在前，源码在后，所以在源码进入生成校验码单元的同时也传输进入源码暂存单元，通过源码暂存单元对输入编码器的源码数据进行缓存，等到生成校验单元将校验结果全部发送后，紧接着将源码流输出。控制单元根据全局配置信号确定本次编码的码型并产生相应的控制信号，这些信号包括源码长、块大小、乒乓操作信号等。编码器的整体硬件结构如图2所示。

Figure 2. Overall structure diagram of the LDPC encoder

图2. LDPC编码器整体结构图

3.2. 编码器各部分具体实现

3.2.1. 生成校验码单元

生成校验码单元的结构如图3所示。6种编码方式中最大列块数c为18，为了使用同一套硬件支持所有编码方式，运算单元get_pn的数量选定为18，每个get_pn单元的计算对象为一个列块。生成校验码单元由18个运算单元get_pn和1个生成矩阵存储单元get_matrix组成。每个get_pn单元的计算对象为一个列块，可以完成L*B次乘累加运算；18个get_pn同时计算，可以同时完成18*L*B路乘累加运算。在生成矩阵存储单元get_matrix中，18个ROM核根据.coe文件存储get_pn所需的多个码率对应的生成矩阵。

Figure 3. Generate a check code structure diagram

图3. 生成校验码结构图

1) get_pn单元

为了提高编码效率，运算单元get_pn采取乒乓计算的方式。对每个get_pn进行编号分配，当生成矩阵的列块数，也就是编码所需的get_pn运算单元数量大于该get_pn的编号时，使能该get_pn单元输出一个列块的编码数据。get_pn编码的时序如图4所示。输入数据被延时3个周期，延时的第一个周期确定读ROM的地址，延时的第二个周期读ROM，延时的第三个周期获得生成矩阵。在一个块计算结束前，为了使下一个块能够连续计算，所以提前3个周期更新读ROM的地址。

Figure 4. Coding timing diagram

图4. 编码时序图

2) 生成矩阵存储单元gen_matrix

本单元主要用来存储LDPC编码器的G生成矩阵，由准循环LDPC码的原理可以知道，实际的G生成矩阵可以根据一定数量的生成向量g唯一确定，同时考虑减少矩阵存储单元的资源占用，选择将这些g生成向量存储在ROM存储器中，这样原本需要L × B个存储空间，通过只存储生成向量的办法只需要L个存储空间。18个ROM的数据存储格式如图5所示。

Figure 5. Data storage format

图5. 数据存储格式

3.2.2. 源码暂存单元

源码暂存单元采用乒乓存储的方式对进入LDPC编码器的源码数据流进行缓存，在6种编码方案中，源码的长度最大为7056，为了能够同时对两帧的源码数据进行存储，所需双端口存储器的维度应该不低于2 × 7056，为此例化一个深度为16,384的双端口RAM核，其中一个端口用来写入源码，另一个端口用来读出源码。在A端口写入一帧数据时，B端口可以同时读出另一帧数据。通过控制单元传输进来的ping_pang信号控制乒乓操作的完成。当ping_pang等于1时，源码按照ping路保存，在源码缓存进入双端口RAM时，选择写ROM操作的起始地址为8192，当ping_pang等于0时，源码按照pong路保存，ROM缓存源码的起始地址为0。

3.2.3. 控制单元

控制单元的作用为：对本次编码所需的配置信息进行完善，同时控制乒乓操作的转变状态以及添加数据输出有效信号。LDPC编码器的顶层模块根据输入的码率选择信号对本次编码所需的配置信号进行赋值，配置信号包括编码器所需的列块数、源码长度、子矩阵块大小等，配置完成后输出给源码缓存单元、校验码生成单元并开始本次编码。

4. 仿真与实现结果

按照上文叙述的QC-LDPC硬件结构 ，使用verilog语言进行描述，在ISE10.1平台上完成编码器的编译、综合、布局布线，并在FPGA上实现设计，FPGA采用XILINX公司Kintex®-7系列，具体的型号为XC7K325tffg900，同时将每种码型下编码器的输出结果与同种码型的MATLAB模型输出结果比对，发现两者数据相同证明编码结果正确。编码器的工作时钟为144Mhz，FPGA资源消耗情况见表2所示。

Table 2. Resource consumption

表2. 资源消耗情况

根据吞吐量计算公式：

$T=\frac{n_{\text{LDPC}}\times f_{\max }}{n_{clk}}$

式中N表示一帧LDPC编码中的源码比特数，F表示编码器的工作时钟频率，n表示编码器处理进行一帧编码消耗的时钟数。

由此可得本编码器的吞吐量为143.289 Mbps，逻辑单元在FPGA中的占比约为6%，存储器单元占比约8%。在文献 [6] 中，逻辑资源和存储器资源占比分别为7%、6%，本文在资源没有大量增加的情况下，完成了四种码率共六种编码方式的编码器实现，具备一定的实用性。

5. 总结

本文分析QC-LDPC的编码过程，设计了一套支持多码率多码型的可配置LDPC编码器，在XC7K325tffg900 FPGA上完成硬件设计，通过仿真结果说明，本编码器在不降低纠错性能的同时，占用了较少的FPGA资源，能够支持多种码率码型的编码需求。