2020, Vol. 37 
上海微小卫星创新研究院, 上海 201203;
上海科技大学信息科学与技术学院, 上海 201210;
中国科学院大学, 北京 100049
Shanghai Engineering Center for Microsatellites, Shanghai 201203, China;
School of Information Science&Technology, ShanghaiTech University, Shanghai 201210, China;
University of Chinese Academy of Sciences, Beijing 100049, China
随着航天技术的不断进步以及信息的高度数字化，空间探测、光学遥感等卫星应用承载了更广泛、更精确的空间任务[1]。以空间数据源遥感卫星为例，高分辨率、高光谱成像技术的日益更新使得数据量大幅提升，与此同时，用于气象预报、灾害预警等领域的遥感数据具有更高的实时性需求[2]。由此可见，海量数据的高效利用需要高速率的数据传输系统来支持。在星地数据传输中，需要考虑在低信噪比环境、可用频带资源和发射功率有限、系统设计复杂度和成本造价等内外因素条件下，保证数据信息的高速有效传输。采用高性能和高收敛速率的信道编码是提高数传系统传输效率的有效途径。
低密度奇偶校验码(low density parity check, LDPC)于1962年由麻省理工学院Gallager首次提出[3]，是一类具有稀疏校验矩阵的线性分组码，1999年MacKay证明LDPC长码可达到接近Shannon限的性能, 同样也有更低的线性译码复杂度和可并行译码的结构特性，可克服Turbo码的长码延时缺陷[4]。虽然LDPC码具有良好的误码性能，但工程上要实现LDPC码并非易事。为降低工程实现的复杂度，文献[5]提出一种由循环子矩阵构成的校验矩阵，由此产生的码字成为准循环LDPC(quasi-cyclic LDPC, QC-LDPC)码。由于其突出的可实现性，QC-LDPC码被应用于众多研究领域并被纳入相关标准[6-7]，其中最常用的7/8码率(8 176，7 154)LDPC码就是由国际空间数据系统咨询委员会(Consultative Committee for Space Data Systems，CCSDS)提供的[6]。该码作为近地空间和深空通信的信道编码方式，构造了具有准循环特性的校验矩阵和系统码结构单位生成矩阵，译码收敛速率较快且便于硬件工程实现。但随着对卫星通信数据传输速率需求的不断增长，串行编码方式的吞吐量远远不能满足应用需求。
目前，关于LDPC码低复杂度编码器的实现，国学外学者已开展了大量研究[8-12]。文献[8]提出一种CCSDS标准下基于递归卷积的并行编码器，在将资源利用率保持在较低水平的同时，实现理想的吞吐量性能; 文献[9]充分利用QC-LDPC校验矩阵的循环特性和行重相同的特点提出一种CMMB标准下基于block-row-cycle的LDPC编码器; 文献[10]根据IEEE 802.22无线区域网络(wireless regional area network, WRAN)标准，提出全串行编码器和串并混合编码器的设计能够在84种码率的组合下实现低功耗和低资源占用。国内Li等[11]提出3种高效的QC-LDPC硬件编码结构：第1种是移位寄存器累加(shift-register-adder-accumulator, SRAA)的串行编码结构，但不适用于高速编码需求；第2种是SRAA的并行编码结构，但组帧延时较高、同比例所需的寄存器较多；第3种是两级编码TWO-STAGE结构，但需要校验矩阵满秩。文献[12]对上述第1种SRAA的串行编码给出并行编码算法，但并行度的选取受制于准循环子矩阵阶数的整数因子分解情况，当阶数为素数时，不能应用该编码算法来实现并行编码，因此并行度的通用化有待研究。
本文针对文献[11]中低延时与并行度可配置的应用研究需求，根据第1种SRAA串行编码结构的并行优化方案，提出一种基于FPGA可动态配置的N位并行LDPC编码器设计，推导论证N与速率的制约关系，并使用Xilinx系列在ISE平台上实现了8位并行编码，吞吐量可达2.5 Gbps。
1 准循环LDPC的CCSDS标准应用 1.1 CCSDS标准CCSDS标准近地空间应用中，LDPC码字结构为7/8码率(8 176，7 154)的系统分组码，也是一组典型的QC-LDPC码。其校验矩阵H是由2×16个准循环子矩阵构成的维度为1 022×8 176的准循环矩阵，如下所示
| $ \mathit{\boldsymbol{H}} = \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{A}}_{1, 1}}}&{{\mathit{\boldsymbol{A}}_{1, 2}}}& \cdots &{{\mathit{\boldsymbol{A}}_{1, 15}}}&{{\mathit{\boldsymbol{A}}_{1, 16}}}\\ {{\mathit{\boldsymbol{A}}_{2, 1}}}&{{\mathit{\boldsymbol{A}}_{2, 2}}}& \cdots &{{\mathit{\boldsymbol{A}}_{2, 15}}}&{{\mathit{\boldsymbol{A}}_{2, 16}}} \end{array}} \right]. $ | (1) |
其中，Ai, j是阶数为511×511的循环移位子矩阵(i=1, 2;j=1, 2, …, 16)，每个Ai, j行重和列重均为2(即每行、每列有两个“1”)。图 1为校验矩阵H的散点图(“1”的位置)，可直观看到其稀疏和循环特性。
|
Download:
|
| 图 1 奇偶校验矩阵散点图 Fig. 1 Scatter chart of parity check matrix | |
生成矩阵G同样是具有准循环特性的大小为7 154×8 176的矩阵
| $ \mathit{\boldsymbol{G}} = \left[ {\begin{array}{*{20}{c}} \mathit{\boldsymbol{I}}&0& \cdots &0&{{\mathit{\boldsymbol{B}}_{1, 1}}}&{{\mathit{\boldsymbol{B}}_{1, 2}}}\\ 0&\mathit{\boldsymbol{I}}& \cdots &0&{{\mathit{\boldsymbol{B}}_{2, 1}}}&{{\mathit{\boldsymbol{B}}_{2, 2}}}\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0&0& \cdots &\mathit{\boldsymbol{I}}&{{\mathit{\boldsymbol{B}}_{14, 1}}}&{{\mathit{\boldsymbol{B}}_{14, 2}}} \end{array}} \right]. $ | (2) |
生成矩阵G由两部分组成G=[I Q]，一部分是左边7 154×7 154的单位矩阵I，另一部分是右边由28个准循环子矩阵Bi, j组成的准循环矩阵Q (i=1, 2, …, 14;j=1, 2)，如公式(3)每个准循环子矩阵Bi, j都是511×511的方阵，
| $ {\mathit{\boldsymbol{B}}_{i, j}} = \left[ {\begin{array}{*{20}{c}} {b_{i, j}^1}&{b_{i, j}^2}& \cdots &{b_{i, j}^{510}}&{b_{i, j}^{511}}\\ {b_{i, j}^{511}}&{b_{i, j}^1}& \cdots &{b_{i, j}^{509}}&{b_{i, j}^{510}}\\ \vdots & \vdots &{}& \vdots & \vdots \\ {b_{i, j}^3}&{b_{i, j}^4}& \cdots &{b_{i, j}^1}&{b_{i, j}^2}\\ {b_{i, j}^2}&{b_{i, j}^3}& \cdots &{b_{i, j}^{511}}&{b_{i, j}^1} \end{array}} \right]. $ | (3) |
LDPC编码算法主要分为两类：基于生成矩阵的直接相乘编码算法和基于近似下三角矩阵RU(Richardson-Urbanke)编码算法。CCSDS标准中7/8码率的系统码(8 176，7 154)采用生成矩阵直接相乘的编码算法，其中7 154为待编码信息向量n
| $ \mathit{\boldsymbol{n}} = ({n_1}\;\;{n_2}\;\; \cdots \;\;{n_{7\;154}}). $ | (4) |
将待编码信息向量n与生成矩阵G作如下运算，得到LDPC系统码U
| $ \mathit{\boldsymbol{U = n}} \cdot \mathit{\boldsymbol{G, }} $ | (5) |
| $ \mathit{\boldsymbol{U = }}({n_1}\;\;{n_2}\;\; \cdots \;\;{n_{7\;154}}\;\;{c_1}\;\;{c_2}\;\; \cdots \;\;{c_{1\;022}}). $ | (6) |
输入7 154位待编码信息n，经编码后输出8 176位系统码，其中前7 154位为原编码信息位，后1 022位为生成的奇偶校验位c。
2 高速编码器FPGA结构实现方案 2.1 串行编码方案Li等在文献[11]中推导了由校验矩阵求得具有系统码结构特性生成矩阵的算法，由此生成矩阵利用SRAA串行编码结构(如图 2)可实现低复杂度的串行编码。
|
Download:
|
| 图 2 SRAA串行编码结构 Fig. 2 SRAA serial coding structure | |
串行编码方案即利用生成矩阵的准循环特性，以B1, j和B2, j两个计算单元为一组，共14组(j=1, 2, …, 14)进行运算。并将待编码信息向量n如下对应分为14个子向量。
| $ {\mathit{\boldsymbol{n}}^{\rm{T}}} = \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{m}}_1}}\\ {{\mathit{\boldsymbol{m}}_2}}\\ \vdots \\ \vdots \\ {{\mathit{\boldsymbol{m}}_{14}}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {{n_1}}&{{n_2}}& \cdots &{{n_{511}}}\\ {{n_{512}}}&{{n_{513}}}& \cdots &{{n_{1\;022}}}\\ \vdots & \vdots &{}& \vdots \\ \vdots & \vdots &{}& \vdots \\ {{n_{6\;644}}}&{{n_{6\;645}}}& \cdots &{{n_{7\;154}}} \end{array}} \right]. $ | (7) |
编码步骤如下：
1) 硬件初始化时，累加器1、2复位，将B1, 1和B1, 2第1行数据分别读入511位移位寄存器A和B。
2) 对于待编码信息向量m1，第1个时钟时，将m1向量的第一比特数据n1依次与移位寄存器A和B中的数据做相与运算，得到的结果再与累加器中的对应数据相异或，最后结果分别存入累加器1和2中。
同理可得，在2~511个时钟内，每个时钟到来时，移位寄存器A和B所有比特数据右移一位，与待编码信息向量m1的n2~n511数据重复第1个时钟的操作。直到第511个时钟完成后，涉及待编码信息向量m1以及生成矩阵的第1组计算单元B1, 1和B1, 2的运算完成。并将移位寄存器A和B中的数据更换读入B2, 1和B2, 2的第1行数据。
3) 对于待编码信息向量m2至m14，重复上述向量m1的运算过程，直到第14×511个时钟到来时，所有7 154位待编码信息完成编码，通过累加器1和2组合得到1 022位校验信息，将7 154位缓存信息与这1 022位校验信息结合最终得到8 176位系统码。
2.2 高速并行编码设计方案串行编码设计方案虽然结构简单，节约资源，但也存在高时延，速率低的弊端。随着超宽带卫星通信高速率、高品质应用需求的日益显著，并行编码方案是实现空间高速数据传输的有效手段。
本文根据准循环LDPC码的结构特点以CCSDS标准7/8码率为例，基于SRAA串行编码方案提出N位可配置高速并行的编码架构，并以8位并行为例加以分析和实现。
当并行度为N，准循环子矩阵阶数为511时，首先对公式(7)的待编码信息做补零处理以满足N位并行的结构特性。设511除以N，余数为r(r=511modN, 且r < N)。则在每个子向量mi(i=1, 2, …, 14)的末端添k个“0”(其中，k=(N－511)modN)，得到7 154+14×k位待编码信息p，使其可平均分为N组并行输入
| $ \begin{array}{l} \mathit{\boldsymbol{p = }}{\rm{[}}{\mathit{\boldsymbol{q}}_1}\;\;{\mathit{\boldsymbol{q}}_2}\;\; \cdots \;\; \cdots \;\;{\mathit{\boldsymbol{q}}_{14}}{\rm{]}}\\ = {\left[ {\begin{array}{*{20}{c}} {{n_1}}&{{n_2}}& \cdots &{{n_{511}}}&0& \cdots &0\\ {{n_{512}}}&{{n_{513}}}& \cdots &{{n_{1\;022}}}&0& \cdots &0\\ \vdots & \vdots &{}& \vdots & \vdots & \vdots &{}\\ \vdots & \vdots &{}& \vdots & \vdots &{}& \vdots \\ {{n_{6\;644}}}&{{n_{6\;645}}}& \cdots &{{n_{7\;154}}}&0& \cdots &0 \end{array}} \right]^{\rm{T}}}, \end{array} $ | (8) |
将添“0”得到的子向量qi(i=1, 2, …, 14)再次分割成N个并行输入向量qil(i=1, 2, …, 14;l=1, 2, …, N)，对于子向量q1，分割为以下N个向量
| $ \begin{array}{l} \begin{array}{*{20}{l}} {\mathit{\boldsymbol{q}}_1^1 = }&{\left( {{n_1}} \right.}&{{n_{1 + N}}}&{{n_{1 + 2N}}}& \cdots &{\left. {{n_{1 + (511 + k - N)}}} \right), }\\ {\mathit{\boldsymbol{q}}_1^2 = }&{\left( {{n_2}} \right.}&{{n_{2 + N}}}&{{n_{2 + 2N}}}& \cdots &{\left. {{n_{2 + (511 + k - N)}}} \right), } \end{array}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots \\ \begin{array}{*{20}{l}} {\mathit{\boldsymbol{q}}_1^l = }&{\left( {{n_l}} \right.}&{{n_{l + N}}}&{{n_{l + 2N}}}& \cdots &{\left. {{n_{l + (511 + k - N)}}} \right), }\\ {\mathit{\boldsymbol{q}}_1^N = }&{\left( {{n_N}} \right.}&{{n_{N + N}}}&{{n_{N + 2N}}}& \cdots &{\left. {{n_{N + (511 + k - N)}}} \right), } \end{array} \end{array} $ | (9) |
其中，当l+(511+k－N)>511时，nl+(511+k－N)=0。
同样，生成矩阵G的右边准循环矩阵Q部分，每个Bi, j也将对应公式(8)被重新分割成N个并行编码子矩阵Bi, jl(i=1, 2, …, 14;j=1, 2;l=1, 2, …, N)，
| $ \begin{array}{l} \mathit{\boldsymbol{B}}_{i, j}^1 = \left[ {\begin{array}{*{20}{c}} {b_{i, j}^1}&{b_{i, j}^2}& \cdots &{b_{i, j}^{510}}&{b_{i, j}^{511}}\\ {b_{i, j}^{511 - N + 1}}&{b_{i, j}^{511 - N + 2}}& \cdots &{b_{i, j}^{511 - N - 1}}&{b_{i, j}^{511 - N}}\\ \vdots & \vdots &{}& \vdots & \vdots \\ \vdots & \vdots &{}& \vdots & \vdots \\ {b_{i, j}^{N - k + 1}}&{b_{i, j}^{N - k + 2}}& \cdots &{b_{i, j}^{N - k - 1}}&{b_{i, j}^{N - k}} \end{array}} \right], \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots \\ \mathit{\boldsymbol{B}}_{i, j}^l = \left[ {\begin{array}{*{20}{c}} {b_{i, j}^l}&{b_{i, j}^{l + 1}}& \cdots &{b_{i, j}^{l - 2}}&{b_{i, j}^{l - 1}}\\ {b_{i, j}^{511 - N + l}}&{b_{i, j}^{511 - N + l + 1}}& \cdots &{b_{i, j}^{511 - N + l - 2}}&{b_{i, j}^{511 - N + l - 1}}\\ \vdots & \vdots &{}& \vdots & \vdots \\ \vdots & \vdots &{}& \vdots & \vdots \\ {b_{i, j}^{N - k + l}}&{b_{i, j}^{N - k + l + 1}}& \cdots &{b_{i, j}^{N - k + l - 2}}&{b_{i, j}^{N - k + l - 1}} \end{array}} \right], \end{array} $ | (10) |
其中，编码子矩阵Bi, jl是大小为
| $ c = \sum\limits_{i, j} {{\mathit{\boldsymbol{p}}_i}} {\mathit{\boldsymbol{B}}_{i, j}} = \sum\limits_{i, j, l} {\mathit{\boldsymbol{q}}_i^l} \mathit{\boldsymbol{B}}_{i, j}^l. $ | (11) |
除此之外，为了解决串行编码方案中高时延、速率低这两个主要弊端，本文在结构上不仅做出了并行调整，同时也将存放待编码信息位的输入缓存单元换为延时单元，待编码信息在并行输入添“0”单元的同时也并行送至延时单元，经相应时钟延迟后并行输出，这样既能减少输入缓存模块的资源占用也大大减小了待编码信息由输入到输出的延时周期。以N=8为例，具体结构如图 3所示。
|
Download:
|
| 图 3 基于SRAA结构的8位并行编码结构 Fig. 3 8-bit parallel coding structure based on SRAA structure | |
待编码的7 154位编码信息分8位依次送至延时单元和输入信息添“0”单元，延时单元根据编码矩阵单元的周期作相应延时输出，输入信息添“0”单元每隔511位进行一次添“0”操作。随后将8位并行数据输入编码矩阵单元，8组(共16个)移位寄存器同串行编码过程类似，经过每个时钟8 bit移位、异或和累加运算，在14×64个时钟后产生1 022位校验信息。最后与延时单元的待编码信息位在输出数据处理单元进行合并，输出编码后LDPC系统码。
3 编码器复杂度分析与资源评估针对文献[11]提出的前两种编码方案以及本文的优化方案, 表 1给出这3种编码算法复杂度的分析对照。由此可见，本文方案所占用的逻辑门数量与并行N成正比，而随着N的增加，编码所用周期成比例减少；当SRAA并行方案与本文方案的编码速率(编码周期)相同(N=7)时，SRAA并行方案所用触发器数量为7 154，本文所需触发器数量仅为2 920。综上所述，SRAA串行方案复杂度较低，但编码速率有限；而对于SRAA并行方案，在相同编码速率情况下，本文并行方案较SRAA并行方案复杂度更低。
|
表 1 3种编码算法速率与复杂度比较 Table 1 Comparison of rate and complexity among three coding algorithms |
本文根据所提出的可配置并行架构，在FPGA开发平台上，基于ISE的集成开发环境采用Xilinx公司C4VSX55系列的12ff1148型实现了8位并行编码。通过表 2与串行方案的资源对比可知，并行方案不仅比串行方案节省9%的资源占用，且最大工作频率达到330 MHz，8位并行吞吐率可达2.5 Gbps。
|
|
表 2 串行与8位并行编码算法资源占用比较 Table 2 Comparison of resource occupancy between serial and 8-bit parallel coding algorithms |
本文针对准循环LDPC码，为更好地应对卫星超宽带通信系统中高速率、低时延的应用需求，提出一种基于FPGA可动态配置的N位并行LDPC编码器设计，并推导论证并行度N与编码速率间的制约关系。主要具有如下优点：1)通过编码前信息预处理，解决了并行度受限于循环矩阵位数的问题；2)将存放待编码信息位的输入缓存单元换为延时单元，大大减小编码的延时周期；3)相较于SRAA并行方案复杂度更低。最后以7/8码率的LDPC为例，对8位并行编码方案仿真，吞吐量达到2.5 Gbps，实现了高速数据传输的应用需求。本方案的并行度可根据实际情况作以调整，具有更好的工程实现背景。
| [1] |
Arbinger C, Baskcomb S, Berdermann J, et al. Air meets space: shaping the future of commercial space traffic: I. study introduction and initial results[C]//67th International Astronautical Congress. Guadalajara. 2016: 26-30.
|
| [2] |
刘沛龙, 陈宏宇, 魏松杰, 等. LEO卫星网络海量遥感数据下行的负载均衡多径路由算法[J]. 通信学报, 2017, 38(S1): 135-142. |
| [3] |
Gallager R G. Low-density parity-check codes[J]. IRE Transactions on Information Theory, 1962, 8(1): 21-28. |
| [4] |
Mackay D C. Good error-correcting codes based on very sparse matrices[J]. IEEE Transactions on Information Theory, 1999, 45(2): 399-431. |
| [5] |
Chen L, Xu J, Djurdjevic I, et al. Near-Shannon-limit quasi-cyclic low-density parity-check codes[J]. IEEE Transactions on Communications, 2004, 52(7): 1038-1042. Doi:10.1109/TCOMM.2004.831353 |
| [6] |
CCSDS 131.1-O-2. Low density parity check codes for use in near-Earth and deep space applications[S]. Washington DC: CCSDS, 2007.
|
| [7] |
Ortega A L, Bravo-torres J F. Combining LDPC codes, M-QAM modulations, and IFDMA multiple-access to achieve 5G requirements[C]//2017 International Conference on Electronics, Communications and Computers (CONIELECOMP). Cholula: IEEE, 2017: 1-5.
|
| [8] |
Theodoropoulos D, Kranitis N, Paschalis A. An efficient LDPC encoder architecture for space applications[C]//2016 IEEE 22ndrnational Symposium on On-Line Testing and Robust System Design (IOLTS). Sant Feliu de Guixols: IEEE, 2016: 149-154.
|
| [9] |
Liu L, Zhang P, Lin Z. An efficient LDPC encoder based on block-row-cycle structure for CMMB[C]//2013 IEEE Third International Conference on Information Science and Technology (ICIST). Yangzhou: IEEE, 2014: 1451-1454.
|
| [10] |
Neto N A F, De Oliveira J R S, De Oliveira W L A, et al. VLSI architecture design and implementation of a LDPC encoder for the IEEE 802.22 WRAN standard[C]//201525th International Workshop on Power and Timing Modeling, Optimization and Simulation (PATMOS). Salvador: IEEE, 2015: 71-76.
|
| [11] |
Li Z, Chen L, Zeng L, et al. Efficient encoding of quasi-cyclic low-density parity-check codes[J]. IEEE Transactions on Communications, 2006, 54(1): 71-81. Doi:10.1109/TCOMM.2005.861667 |
| [12] |
张仲明, 许拔, 杨军, 等. 800 Mbps准循环LDPC码编码器的FPGA实现[J]. 信号处理, 2009, 25(12): 1937-1940. |