葛广君 , 殷柳国
清华大学 航天航空学院, 清华信息科学与技术国家实验室(筹), 北京 100084

收稿日期: 2015-12-02
基金项目: 国家自然科学基金资助项目(61132002,91538203);清华大学自主科研计划(20121088030)
作者简介: 葛广君(1989－), 男, 博士研究生
通讯作者: 殷柳国, 副研究员, E-mail: yinlg@tsinghua.edu.cn

摘要：针对卫星高速数传系统的高增益、多码率、高可靠性通信编码应用需求, 提出了一种低密度奇偶校验(LDPC)码组的低实现复杂度、高速的编码器设计实现方案, 通过高效复用不同码率和不同扩展因子的编码硬件资源, 并采用低存储和局部三模冗余设计, 有效降低了多码率高速LDPC编码器的整体硬件规模并显著提升了编码速率和可靠性。现场可编程门阵列(FPGA)实现结果表明: 该方法设计的融合28种码字的航天加固编码器可基于单片Xilinx XC2V3000 FPGA芯片实现, 最高编码速率可达3.2 Gb/s; 其触发器、查找表和存储器资源与已有方案相比, 分别降低了24.5%、34.4%和11.1%。该编码器设计方案在当前及未来的卫星数传系统中具有较高应用价值。
关键词： 低密度奇偶校验码 高速编码器设计 多码率融合 低复杂度 卫星数传
Multi-rate LDPC encoder for high-speed satellite data transmissions
GE Guangjun, Yin Liuguo
Tsinghua National Laboratory for Information Science and Technology, School of Aerospace Engineering, Tsinghua University, Beijing 100084, China


Abstract:Satellite data transmission systems need high coding gains, multiple rates and high reliability channel coding. A low complexity, high speed encoder is designed for low-density parity-check (LDPC) codes, which reduces the hardware size and improves the encoding speed and reliability. The system reuses hardware resources for codes of various rates and lengths and uses a low-storage architecture and a partially triple-modular-redundant design scheme. Field programmable gate array (FPGA) synthesized results show that the encoder integrates 28 codes with aerospace reinforcement and a maximum encoding speed of 3.2 Gb/s in a Xilinx XC2V3000 FPGA chip. The flip-flop, look-up table (LUT) and RAM costs of the encoder are 24.5%, 34.4% and 11.1% less than that for the traditional scheme. This encoder design scheme will improve satellite data transmission systems.
Key words: low-density parity-check (LDPC) codeshigh-speed encoder designmulti-rate integratedlow-complexitysatellite data transmission
卫星对地观测系统是了解和把握资源与环境态势,解决人类面临的资源紧缺、环境恶化、人口剧增、灾害频发等一系列重大问题的重要技术手段^[1]。随着卫星观测载荷精度的不断提高和卫星应用技术的飞速发展,星地数据传输需求快速增长,如何在星上硬件资源、带宽、功率受限的情况下实现高速数据传输,是卫星对地观测技术领域的研究热点之一^[2]。
低密度奇偶校验(low-density parity-check,LDPC)码是一种纠错性能逼近Shannon理论极限的信道编码技术,具有译码速度快、误码平底低等优势,是近年来卫星通信领域的研究热点^[2-3]。针对航天通信应用,美国空间数据系统咨询委员会(Consultative Committee for Space Data Systems,CCSDS)制定了《131.0-B-2遥测同步及信道编码》标准^[4],规定了近地卫星通信应用和深空通信应用的两套LDPC码字。近地卫星通信部分采用了编码效率为7/8的准循环(8 160,7 136)LDPC码,可以支持高速星地数据传输; 深空通信部分则采用了一套性能优异的累积重复4参差累积(accumulate repeat by 4 jagged accumulate,AR4JA)码组,具有28种不同码长、码率的编码,适用于低速率、低功耗、远距离的深空通信环境。与国外数传系统相比,中国卫星数传系统星上功率受限,地面接收站主要集中在境内,传输时间窗口小,仰角变化范围大,信道环境复杂; 同时,针对空天信息网络的发展需求,未来中继卫星将与不同轨道高度、不同功能的卫星进行协同数传,面临多信道、多用户接入的应用场景。综上,星载编码对使用AR4JA等性能优异的码组,进行多码率多码长的兼容设计具有强烈的应用需求。然而,AR4JA码组主要面向单通道低速率的深空通信应用设计,如何在星上硬件资源约束苛刻的条件下设计低实现复杂度、多码长多码率融合的高速LDPC编码器,是一个技术难题。
对于LDPC编码器的设计,文^[5-6]分别针对CCSDS近地通信和欧洲第二代数字电视地面广播标准(digital video broadcasting second generation terrestrial,DVB-T2)中的LDPC码进行了单核编码器设计; 文^[7]对中国数字电视地面广播标准(digital multimedia broadcasting for terrestrial,DMB-T)中3种不同码率的LDPC码进行了多码率融合设计; 文^[8]设计的多码率融合编码器,主要针对存储器进行了重构和复用; 文^[9-10]分别提出一种串行多码率LDPC编码器结构,不同码字可共用循环移位累加器; 文^[11-12]中提出的系列LDPC码字,采用核内并行的方式,进行了多码率融合高速编码器设计,对码长相近的码字,可进行高效的硬件资源复用。
本文面向AR4JA码组中的28种码字,充分考虑其构造规律,利用多核并行与核内并行的灵活配置,最大限度进行硬件资源复用,提出了一种多码长多码率兼容的高速编码器设计方案和基于局部三模冗余的航天加固方案,并进行了硬件实验验证。现场可编程门阵列(field-programmable gate array,FPGA)实现结果表明,多码率融合航天加固编码器的触发器、查找表和存储器资源与已有方案相比,分别降低了24.5%、34.4%和11.1%,且最高编码速率可达3.2 Gb/s,可以满足当前及未来一段时间卫星数传系统的编码应用需求。
1 码字定义与编码算法AR4JA码组有1/2、2/3、3/4、4/5共4种码率。其校验矩阵分别由式(1)—(4)表示^[4]：

${{H}_{1/2}}=\text{ }\left[ \begin{matrix} {{O}_{L}} & {{O}_{L}} & {{I}_{L}} & {{O}_{L}} & {{I}_{L}}\oplus {{\Pi }_{1}} \\ {{I}_{L}} & {{I}_{L}} & {{O}_{L}} & {{I}_{L}} & {{\Pi }_{2}}\oplus {{\Pi }_{3}}\oplus {{\Pi }_{4}} \\ {{I}_{L}} & {{\Pi }_{5}}\oplus {{\Pi }_{6}} & {{O}_{L}} & {{\Pi }_{7}}\oplus {{\Pi }_{8}} & {{I}_{L}} \\\end{matrix} \right],$

(1)

${{H}_{2/3}}=\left[ \begin{matrix} \begin{matrix} {{O}_{L}} \\ {{\Pi }_{9}}\oplus {{\Pi }_{10}}\oplus {{\Pi }_{11}} \\ {{I}_{L}} \\\end{matrix} & \left. \begin{matrix} {{O}_{L}} \\ {{I}_{L}} \\ {{\Pi }_{12}}\oplus {{\Pi }_{13}}\oplus {{\Pi }_{14}} \\\end{matrix} \right| & {{H}_{1/2}} \\\end{matrix} \right],$

(2)

${{H}_{3/4}}=\left[ \begin{matrix} \begin{matrix} {{O}_{L}} \\ {{\Pi }_{15}}\oplus {{\Pi }_{16}}\oplus {{\Pi }_{17}} \\ {{I}_{L}} \\\end{matrix} & \left. \begin{matrix} {{O}_{L}} \\ {{I}_{L}} \\ {{\Pi }_{18}}\oplus {{\Pi }_{19}}\oplus {{\Pi }_{20}} \\\end{matrix} \right| & {{H}_{2/3}} \\\end{matrix} \right],$

(3)

${{H}_{4/5}}=\left[ \begin{matrix} \begin{matrix} {{O}_{L}} \\ {{\Pi }_{21}}\oplus {{\Pi }_{22}}\oplus {{\Pi }_{23}} \\ {{I}_{L}} \\\end{matrix} & \left. \begin{matrix} {{O}_{L}} \\ {{I}_{L}} \\ {{\Pi }_{24}}\oplus {{\Pi }_{25}}\oplus {{\Pi }_{26}} \\\end{matrix} \right| & {{H}_{3/4}} \\\end{matrix} \right].$

(4)

式(1)—(4)中： I_L为L维单位方阵,Π_k(k=1,2,…,26)为L×L维置换阵,相关参数计算方法见文^[4]。
对每一种码率,AR4JA码组定义了L=2⁷,L=2⁸,…,L=2¹³共7种扩展因子,因此该码组共有28个码字。 AR4JA 码组通常采用系统码的形式,即生成矩阵G_N×K可表示为

${{G}_{N\times K}}={{\left[ \begin{matrix} {{I}_{K}} & {{P}_{K\times M}} \\\end{matrix} \right]}^{T}}.\text{ }$

(5)

由校验矩阵与生成矩阵的关系得

$\begin{matrix} {{H}_{M\times N}}\cdot \text{ }{{G}_{N\times K}}=\left[ {{H}_{M\times K}}{{H}_{M\times M}} \right]\cdot {{\left[ {{I}_{K}}{{P}_{K\times M}} \right]}^{T}}= \\ {{H}_{M\times K}}+\text{ }{{H}_{M\times M}}\cdot {{\left( \text{ }{{P}_{K\times M}} \right)}^{T}}=\text{ }{{O}_{M\times K}}. \\\end{matrix}$

(6)

式(6)中: H_M×K、 H_M×M分别为 H_M×N的前K列、后M列,进而可求得编码矩阵为

${{P}_{K\times M}}={{\left( {{\left( \text{ }{{H}_{M\times M}} \right)}^{-1}}\cdot \text{ }{{H}_{M\times K}} \right)}^{T}}.$

(7)

式(7)即为由校验矩阵得到的编码生成矩阵,由一系列l×l维(L=4l)的循环方阵构成。编码器的设计只需一组移位寄存器读入l维方阵首行,进行循环移位,与信息序列相乘累加即可,见图 1。其中： ROM(read-only memory) 为只读存储器。

图 1 AR4JA码组编码器的设计

图选项

2 多码长多码率融合的编码器设计LDPC系统码编码的核心是校验序列的生成。对于AR4JA码组,不同码字的校验序列长度都是8l。对于其中l相同、码率不同的码字,可以共用移位寄存器进行融合设计; 对于l不同,即码长不同的码字,可以对移位寄存器进行重组复用融合设计; 对于航天抗辐照设计,可以根据编码器的结构特点,对辐照敏感部位进行局部三模冗余加固。
2.1 多码率融合设计对于码字中l相同、码率不同的多码率融合设计,例如式(7),此类码对应同一扩展因子,不同码率码字的 H_M×M部分相同,而 H_M×K部分呈依次包含关系。令 H_M×K=[H_4/5^' H_3/4^' H_2/3^' H_1/2],其中 H'是各个码率相对较低码率的矩阵多出来的部分,则

$\begin{matrix} {{P}_{K\times M}}={{\left( \text{ }H_{_{M\times M}}^{^{-1}}\cdot \text{ }{{H}_{M\times K}} \right)}^{T}}=\text{ } \\ {{\left( \text{ }H_{_{M\times M}}^{^{-1}}\cdot \left[ H_{_{4/5}}^{^{'}}H_{_{3/4}}^{^{'}}H_{_{2/3}}^{^{'}}{{H}_{1/2}} \right] \right)}^{T}}= \\ [H_{_{M\times M}}^{^{-1}}\cdot \text{ }H_{_{4/5}}^{^{'}}H_{_{M\times M}}^{^{-1}}\cdot \text{ }H_{_{3/4}}^{^{'}}H_{_{M\times M}}^{^{-1}}\cdot \text{ }H_{_{2/3}}^{^{'}} \\ H_{_{M\times M}}^{^{-1}}\cdot \text{ }{{H}_{1/2}}{{]}^{T}}. \\\end{matrix}$

(8)

由式(8)可以得出,对于同一扩展因子L下不同码率R的编码矩阵,也有依次包含关系,见图 2。

图 2 不同码率编码矩阵结构

图选项

由图 2可得,低码率的编码过程依次包含在高码率的过程中。因此,对于l值相同的码字,其移位寄存器长度相同,不同码率编码器都可由8组长度为l的移位寄存器和累加器实现。码字切换只需调整时序控制计数器的计数周期和ROM的读地址即可。综上,对于校验序列长度相同、码率不同的融合编码,可用一组完全相同的移位寄存器实现,且ROM存储仅为4/5码率下单一码字的存储量。
2.2 多码长融合设计如图 2所示,AR4JA码组中规定的码字,校验序列长度都为8l。对于l值不同即扩展因子不同的码字,其移位寄存器的长度不同,无法再利用简单的共用移位寄存器进行融合设计。本文提出了一种可配置循环移位寄存器,如图 3所示。
图 3中,将N组移位寄存器的末位构成一组总线,各移位寄存器的首位利用多路选择器( multiplexer,MUX )从该总线中选择一位进行赋值,即可配置成若干组不同循环长度的移位寄存器。

图 3 可配置循环移位寄存器

图选项

对于AR4JA码组,其扩展因子共有7种,对应的 l 值分别为32、 64、 128、 256、 512、 1 024、 2 048。显然,这些数值依次呈现2倍关系,针对AR4JA码组,本文设计了64组32 b的寄存器,通过配置即可分别得到7种对应长度的移位寄存器。
2.3 高速并行编码设计针对高速编码,本文引入了一种多核并行与核内并行并存的方案。对于核内并行,令每一组移位寄存器,对信息序列进行 p b并行编码处理。如图 4所示,移位寄存器每个时钟进行 p b循环右移,由组合逻辑依次得到1 b至 p b右移的结果。利用此种结构,K b长的信息比特可在 K/p 个时钟内完成编码。

图 4 核内多路并行编码结构

图选项

对于多核并行,如2.2节的64组32 b可配置移位寄存器,针对某一 l 值的码字,可配置得到 64×32/ l 组移位寄存器,进而可得到64×32/(8 l )个独立编码核的多核并行结构(每个核需要8组移位寄存器)。
结合核内并行度 p ,单个核的编码速率为p×f _enc ,即核内并行度乘以编码时钟频率。可得,对于扩展因子为l的码字,其总编码速率为256pf _enc /l。l越小的码字,编码速率越高。
对于航天应用编码器,考虑其可靠性和功耗约束,编码时钟f _enc 取100 MHz 。若要达到最高编码速率3 Gb/s 以上的高速编码需求,可得核内并行度p应取4。不同扩展因子码字的编码速率如表 1所示。
表 1 不同扩展因子码字的编码速率

l值	并行寄存器	并行核	编码速率
	组数	个数	Mb·s -1
32	64	8	3 200
64	32	4	1 600
128	16	2	800
256	8	1	400
512	4	1/2	200
1 024	2	1/4	100
2 048	1	1/8	50

表选项






2.4 低存储设计 由于AR4JA码组的编码矩阵并不是稀疏矩阵,因此需要较大的ROM存储矩阵子块的首行。对于扩展因子大的码字,其高存储量将显著提高实现复杂度。本节针对该问题,提出了一种低存储设计。
结合式(7),对于信息序列 U_1×K,生成校验序列 C_1×M的算法可进一步写成

$\begin{matrix} {{C}_{1\times M}}=\text{ }{{U}_{1\times K}}\cdot \text{ }{{P}_{K\times M}}=\text{ } \\ {{U}_{1\times K}}\cdot {{\left( {{\left( \text{ }{{H}_{M\times M}} \right)}^{-1}}\cdot \text{ }{{H}_{M\times K}} \right)}^{T}}= \\ {{U}_{1\times K}}\cdot {{\left( \text{ }{{H}_{M\times K}} \right)}^{T}}\cdot {{\left( {{\left( \text{ }{{H}_{M\times M}} \right)}^{-1}} \right)}^{T}}. \\\end{matrix}$

(9)

由式(9)可以得到,编码过程可转化为由信息序列分别与( H_M×K)^T 、(( H_M×M)^-1)^T 相乘的级联过程。图 5所示为级联编码示意图。

图 5 级联编码示意图

图选项

由图 5可知,由于( H_M×K)^T 的前L列为全0阵,因此在二级编码时,(( H_M×M)^-1)^T 矩阵的前L行可作删除处理。同时,CCSDS 标准规定最后L b 校验序列不传输,故(( H_M×M)^-1)^T 的后L列也可作删除处理。最终第二级编码只需完成 U_1×3L^'与图 5中(( H_M×M)^-1)^T 矩阵阴影部分相乘即可。
( H_M×K)^T 为稀疏矩阵,一级编码只需存储各块的首行非0元素位置,存储为 log ₂l量级。二级编码只需存储(( H_M×M)^-1)^T 矩阵中8×8个子块的首行值。各个码率下单级编码与两级编码所需存储量对比如表 2所示。
表 2 不同码率下存储量对比

码率	存储量/b
	单级编码	两级编码
1/2	64l	20 log 2l+64l
2/3	128l	52 log 2l+64l
3/4	192l	84 log 2l+64l
4/5	256l	116 log 2l+64l

表选项






由表 2可知,码率越高,使用两级编码的存储优势越明显。例如2.1节,本文的融合编码器将在4/5码率下兼容不同码率,因而能最大化该优势。
2.5 航天加固设计星载编码器的设计还需考虑空间高能粒子引发的逻辑差错问题。最常见的加固方法是三模冗余设计,但完整的三模冗余将消耗成倍的硬件资源。考虑到编码本身的纠错能力,码字中单个比特的错误对译码性能几乎无影响。因此,可以将加固目标放宽为： 对于任何阶段发生的单比特逻辑错误,只要在编码输出仅造成单比特错误而不发生扩散,则认为加固有效。
基于这一原则,本文采用局部三模冗余的方案进行航天加固设计。编码器主要构成结构包括乘法器、累加器、移位寄存器、ROM和状态控制计数器。显然,状态控制计数器的错误将导致整个编码流程混乱,需进行三模冗余加固。其他几个结构的差错扩散效应如图 6所示。

图 6 各结构差错扩散示意图

图选项

由图 6可以得出,乘法器的信息比特输入会造成差错扩散,累加器的输入不会造成差错扩散,移位寄存器会造成差错扩散。
可见,只需对编码器的信息比特、移位寄存器和状态控制计数器几个模块进行三模冗余设计即可。作为给移位寄存器提供初值的ROM同样会造成差错扩散,但针对存储器已有诸多可参考的高效纠错设计^[13-14],本文不再赘述。
3 编码器硬件资源比较基于Xilinx公司的Virtex XC2V3000 FPGA芯片,利用本文第2节所述的多码率融合方案和航天加固方案,对AR4JA码组中的28个码字进行了FPGA设计实现。同时,利用文^[7]提出的多码率融合方案,对同一组码字进行FPGA设计并进行对比。所得硬件资源使用情况如表 3所示。
表 3 本文与文^[7]方案硬件资源对比

	触发器	查找表	存储器
文[7]方案	19 843	29 264	99
本文方案	14 978	19 183	88
资源节省/%	24.5	34.4	11.1

表选项






由表 3可见,利用本文方案设计所得的多码率融合的航天加固编码器,其触发器(flip flop)、查找表(LUT)和存储器(RAM16)资源分别节省了24.5%、34.4%和11.1%,有效降低了多码率融合编码器的硬件规模。
4 结 论本文针对卫星高速数传系统的高增益、多码率、高可靠性的通信编码应用需求,给出了一种AR4JA码组的低实现复杂度、高速的编码器设计方案,通过在并行编码结构下高效复用不同码率和不同扩展因子的编码硬件资源,采用低存储设计和局部三模冗余航天加固设计,有效降低了多码率高速LDPC编码的整体硬件规模并显著提升编码速率。FPGA实现结果表明,本文方法设计的融合28种编码的航天加固编码器,最高编码速率可达 3.2 Gb/s,其触发器、查找表和存储器资源与已有设计相比,分别降低了24.5%、34.4%和11.1%,在卫星数传等系统中具有较高应用价值。

参考文献

[1]	Journal of Central South University(Science and Technology), 41(2):649-654.-->安培浚, 高峰, 曲建生. 对地观测系统未来发展趋势及其技术需求[J].遥感技术与应用,2007, 22(6): 762–767.AN Peijun, GAO Feng, QU Jiansheng. Trend and technology requirements of Earth observing system[J].Remote Sensing Technology and Application,2007, 22(6): 762–767.(in Chinese)
[2]	Journal of Central South University(Science and Technology), 41(2):649-654.--> 詹亚峰, 殷柳国, 陆建华. LDPC码技术及其在深空探测中的应用 [C]// 哈尔滨工业大学深空探测基础研究中心. 中国宇航学会深空探测技术专业委员会第一届学术会议论文集. 哈尔滨: 哈尔滨工业大学, 2005: 303-307.
[3]	Journal of Central South University(Science and Technology), 41(2):649-654.-->LI Qi, YIN Liuguo, LU Jianhua. Performance study of a deep space communications system with low-density parity-check coding under solar scintillation[J].International Journal of Communications,2012, 6(1): 1–9.
[4]	Journal of Central South University(Science and Technology), 41(2):649-654.--> CCSDS. Low Density Parity Check Codes for Use in Near-Earth and Deep Space Applications: CCSDS 131.0-B-2 [S]. Washington, DC: CCSDS, 2011.
[5]	Journal of Central South University(Science and Technology), 41(2):649-654.-->李跃东. LDPC编码技术在FPGA中的实现 [D]. 成都: 成都理工大学, 2012. LI Yuedong. Implement of LDPC Codes in FPGA [D]. Chengdu: Chengdu University of Technology, 2012. (in Chinese)
[6]	Journal of Central South University(Science and Technology), 41(2):649-654.-->常静. 可配置FFT及LDPC编码器的FPGA实现 [D]. 西安: 西安电子科技大学, 2014. CHANG Jing. FPGA Implementation of Configurable FFT and LDPC Encoder [D]. Xi'an: Xidian University, 2014. (in Chinese)
[7]	Journal of Central South University(Science and Technology), 41(2):649-654.--> ZHANG Huxing, YU Hongyang. Multi-rate QC-LDPC encoder [C]// ICTD 2009. IEEE Circuits and Systems International Conference on Testing and Diagnosis. Piscataway, NJ: IEEE, 2009: 1-4.
[8]	Journal of Central South University(Science and Technology), 41(2):649-654.-->王刚, 李冰, 刘勇, 等. 一种可重构LDPC编码器的设计与实现[J].微计算机信息,2010, 26(12-2): 168–170.WANG Gang, LI Bing, LIU Yong, et al. Design and implementation of a reconfigurable LDPC encoder[J].Micro Computer Information,2010, 26(12-2): 168–170.(in Chinese)
[9]	Journal of Central South University(Science and Technology), 41(2):649-654.-->许元志. 可配置LDPC码编码器的FPGA设计与实现 [D]. 哈尔滨: 哈尔滨工程大学, 2012. XU Yuanzhi. Design and Implementation of Configurable LDPC Encoder Based on FPGA [D]. Harbin: Harbin Engineering University, 2012. (in Chinese)
[10]	Journal of Central South University(Science and Technology), 41(2):649-654.--> WANG Fei, ZHANG Peng, WAN Xin, et al. Design of a multi-rate quasi-cyclic low-density parity-check encoder based on pipelined rotate-left-accumulator circuits [C]// CISP 2014. IEEE International Congress on Image and Signal Processing. Dalian, 2014: 1105-1109.
[11]	Journal of Central South University(Science and Technology), 41(2):649-654.-->张浩, 殷柳国. 星地高速数传系统LDPC编码器ASIC集成芯片设计[J].宇航学报,2015, 36(1): 96–102.ZHANG Hao, YIN Liuguo. ASIC design of an LDPC encoder for satellite-ground high-speed data transmission system[J].Journal of Astronautics,2015, 36(1): 96–102.(in Chinese)
[12]	Journal of Central South University(Science and Technology), 41(2):649-654.-->殷柳国. 低密度奇偶校验码编译码技术研究与应用 [D]. 北京: 清华大学, 2005. YIN Liuguo. Coding Technique and Application Studies on Low-Density Parity-Check (LDPC) Codes [D]. Beijing: Tsinghua University, 2005. (in Chinese)
[13]	Journal of Central South University(Science and Technology), 41(2):649-654.-->GUO Jing, XIAO Liyi, MAO Zhigang, et al. Enhanced memory reliability against multiple cell upsets using decimal matrix code[J].IEEE Transactions on Very Large Scale Integration Systems,2014, 22(1): 127–135.
[14]	Journal of Central South University(Science and Technology), 41(2):649-654.-->Brkic S, Ivanis P, Vasic B. Reliability of memories built from unreliable components under data-dependent gate failures[J].IEEE Communications Letters,2015, 19(12): 2098–2101.