分层准循环扩展构造的LDPC码的编码器

摘要

本发明公开了一种分层准循环扩展构造的LDPC码的编码器，包括：输入缓存、第一处理－缓存流水级、第二处理流水级、第三缓存流水级、第四处理－缓存流水级、输出级，根据校验矩阵H是准循环移位阵拼接的特点，简化了RU编码方法的流水线结构，使流水线级数从六级降到了四级，缩短了编码时延。同时根据主要功能模块的实现特点，降低了最大流水线时延，提高了编码吞吐量。随后依据准循环移位阵运算的特点，减少了编码器ROM的资源消耗，用准循环移位单位阵乘向量取代了RU方法中的稀疏矩阵乘向量，用准循环移位阵乘向量取代了RU方法中的非稀疏矩阵乘向量。为了适应可变码长、可变码率的要求，级间的乒乓RAM可预留较大存储空间。

说明书

技术领域

本发明涉及一种数据通信技术领域的编码器，具体涉及一种分层准循环扩展构造的LDPC码的编码器。

背景技术

LDPC码(低密度校验码)是1963年Gallager首先提出的一种编码技术，它可用作多种通信系统或信息存贮系统的纠错/检错技术，由于它具有逼近信道极限的性能，成为近十年来最受关注的一项热门技术。常用的LDPC码编码方法有RU方法和基于生成矩阵的方法。RU方法实现简单，但编码吞吐量低；基于生成矩阵的方法吞吐量高，但需要占用较多的资源。

随着对LDPC码研究的深入，分层准循环LDPC码渐渐进入人们的视线。这种码的层的概念是指校验矩阵H的相邻行组成的子矩阵的最大列重为1。若校验矩阵能分割为具有相同大小的几层，则对应的LDPC码称为分层LDPC码。若一个方阵可由单位矩阵经循环右移n位后得到，那么这个矩阵称为循环移位单位阵(CS-Identity)；一般的，若一个方阵除去第一行后的每一行都可由该方阵上一行经循环右移一位后得到，并且第一行是最后一行经循环右移一位后得到，那么这个方阵称为循环移位阵(CS-Matrix)。进一步，如果将p个大小相同的循环移位单位阵和p(p-1)个相同大小的零阵拼接得到方阵，并且使得该方阵的行重、列重均为一，那么这个方阵称为准循环移位单位阵(QC-Identity)；如果将p²个大小相同的循环移位阵拼接得到方阵，那么这个方阵称为准循环移位阵(QC-Matrix)。显然，准循环移位单位阵是一种特殊的准循环移位阵。准循环移位阵的加、减、乘、求逆运算(如果存在)所得仍是准循环移位阵。若可将分层LDPC码中的每一层分为准循环移位单位阵的拼接，则对应的LDPC码称为分层准循环LDPC码(Layered QC-LDPC Code)。分层准循环LDPC码的出现不仅使提高吞吐量成为可能，而且还能减少编码复杂度。

经过对现有技术文献检索发现，D.Lee，W.Luk，C.Wang和C.Jones在《FieldProgrammable Custom Computing Machines》，2004，FCCM 2004，pp.101-111上提出的“A flexible hardware encoder for low-density parity-check codes”(低密度校验码的灵活编码器实现)给出了一种目前普遍采用的基于RU方法的LDPC编码器，该编码器成功地将LDPC编码复杂度降低到近似与码长成正比，并且在编码器中引入了流水线结构，将编码过程并行化，一定程度上能够增加编码器的吞吐量。但是该编码器每一级流水线消耗的时钟数差距极大，抑制了吞吐量的进一步提升，并且它所涉及的串行的前项替换模块进一步限制了吞吐量的提高。由于结构不够灵活，多码长、多码率LDPC码的编码器实现还是比较困难。

发明内容

本发明针对现有技术的不足，提供一种支持可变码长、可变码率的分层准循环LDPC码的编码器，它是一种适用于基于二次扩展构造的LDPC码的编码器，是对传统RU方法编码器的一种改进发明，可以得到比RU方法编码器更大的吞吐量。

本发明是通过以下技术方案实现的：

本发明包括：输入缓存，第一处理-缓存流水级，第二处理流水级，第三缓存流水级，第四处理-缓存流水级，输出级。其中：所述输入缓存将信息比特s按照校验矩阵H中块的大小p×q进行分割，分别存储在p个深度为q、位宽为1的乒乓RAM中，另外使用6块深度为p×q、位宽为的d_c-d_v的RAM对信息比特s进行FIFO操作以确保s与相应校验比特p₁、p₂同步传递给输出级；所述第一处理-缓存流水级，首先同时分块读取输入缓存各乒乓RAM的信息比特，然后同时分块执行准循环移位单位阵乘向量运算(CSIMV)，分块同时更新T^-1As^T，Cs^T，并将其按照H矩阵中块的大小p×q进行分割，分别存储在p个深度为q、位宽为1的乒乓RAM中，另外使用4块深度为p×q、位宽为1的RAM对T^-1As^T进行FIFO操作以确保T^-1As^T与相应的校验比特p₁同步传递给第四处理-缓存流水级；所述第二处理流水级，首先同时分块读取第一处理-缓存流水级各乒乓RAM中T^-1As^T，Cs^T的值，接着同时分块执行准循环移位单位阵乘向量运算，然后同时分块执行向量加法运算(VA)，最后同时分块执行准循环移位阵乘向量运算(CSDMV)，分块同时更新p₁并输出给第三缓存流水级；所述第三缓存流水级将p₁按照H矩阵中块的大小p×q进行分割，分别存储在p个深度为q、位宽为1的乒乓RAM中，另外使用3块深度为p×q、位宽为2的RAM对校验比特p₁进行FIFO操作以确保p₁与相应的信息比特s、校验比特p₂同步传递给输出级；所述第四处理-缓存流水级，首先同时分块读取第三缓存流水级各乒乓RAM中的p₁和第一处理-流水级的乒乓RAM中T^-1As^T的值，然后同时分块执行准循环移位单位阵乘向量运算，最后执行向量加法运算，更新p₂并将其存储在深度为p×q、位宽为1的乒乓RAM中；所述输出级同时分块读取输入缓存的乒乓RAM中的s、第三缓存流水级的乒乓RAM中的p₁以及第四处理-流水级的乒乓RAM中p₂的值，并将其输出给信道。

所述的校验矩阵H，行重为d_c，列重为d_v，则其可以按行分为d_v层，每一层的列重均为1。也可以将其按RU编码方法分成A、B、T、C、D、E六个子矩阵，其中A由1×(d_c-d_v的块组成，B由1×(d_v-1)的块组成，T只由一块组成，C由(d_v-1)×(d_c-d_v)的块组成，D由(d_v-1)×(d_v-1)的块组成，E由(d_v-1)×1的块组成。每个循环移位单位阵都是q×q的，则H矩阵每一块均由p²个这样的循环移位单位阵拼接而成。定义Φ＝-ET^-1B+D。

所述的信息比特s、校验比特p₁和p₂，共同组成编码后码字x＝(s，p₁，p₂)，其中s对应C所在的列，p₁和p₂分别对应D和E所在的列。

所述的输入缓存，使用6块深度为p×q、位宽为的d_c-d_v的RAM对信息比特s进行FIFO操作以确保s与相应校验比特p₁、p₂同步传递给输出级。除此以外输入缓存将信息比特s按照H矩阵中块的大小p×q进行分割，分别存储在p个深度为q、位宽为1的乒乓RAM中，每d_c-d_v对这样的乒乓RAM分块联合存储一份信息比特s的内容。一共有d_v+1份信息比特s被存储在输入缓存中。

所述的第一处理-缓存流水级，使用d_v个ROM存储矩阵C和T^-1A中循环移位单位阵的移位因子，每个ROM存储T^-1A或者C的一层中的所有移位因子，每一层中在同一行上的循环移位单位阵的移位因子被组合后存储在ROM的同一个地址。第一处理-缓存流水级使能时同时从d_v个ROM中顺次读出移位因子，将这些移位因子作为读地址分块循环读取输入缓存中的d_v份信息比特s，即同时分块执行准循环移位单位阵乘向量运算(CSIMV)，分块同时更新T^-1As^T，Cs^T，将T^-1As^T按照H矩阵中块的大小p×q进行分割，分别存储在p个深度为q、位宽为1的乒乓RAM中，将Cs^T按照H矩阵中块的大小p×q进行分割，分别存储在d_v-1对深度为p×q、位宽为1的乒乓RAM中，另外使用4块深度为p×q、位宽为1的RAM对T^-1As^T进行FIFO操作以确保T^-1As^T与相应的校验比特p₁同步传递给第四处理-缓存流水级。

所述的第二处理流水级，使用d_v-1个ROM存储矩阵E中循环移位单位阵的移位因子，每个ROM顺序存储E的一层中的所有移位因子。同时使用1个ROM存储矩阵Φ^-1中所有循环移位阵的第一列，将Φ^-1的每一列层的第一列组合后存储在ROM的低地址，之后顺次添加下一列循环移位阵的第一列的组合。第二处理流水级使能时同时从d_v-1个ROM中顺次读出移位因子，将这些移位因子作为读地址读取第一处理-缓存流水级的乒乓RAM中的T^-1As^T，即同时分块执行准循环移位单位阵乘向量运算(CSIMV)，分块同时更新ET^-1As^T。然后分块同时顺序读取第一处理-缓存流水级的乒乓RAM中的Cs^T，进而分块执行向量加法运算(VA)，逐比特更新(ET^-1A+C)s^T。最后从ROM中顺次读出Φ^-1的所有循环移位阵的第一列，分块同时执行准循环移位阵乘向量运算(CSDMV)，分块同时更新p₁并输出给第三缓存流水级。

所述的第三缓存流水级，使用3块深度为p×q、位宽为2的RAM对校验比特p₁进行FIFO操作以确保p₁与相应的信息比特s、校验比特p₂同步传递给输出级，另外还将校验比特p₁按照H矩阵中块的大小p×q进行分割，分别存储在p个深度为q、位宽为1的乒乓RAM中。这样一共有2份p₁被存储在第三缓存流水级中。

所述的第四处理-缓存流水级，使用1个ROM存储矩阵T^-1B中循环移位单位阵的移位因子，在同一行上的循环移位单位阵的移位因子被组合后存储在ROM的同一个地址。第四处理-缓存流水级使能时从ROM中顺次读出移位因子，将这些移位因子作为读地址分块循环读取第三缓存流水级中的校验比特p₁，即同时分块执行准循环移位单位阵乘向量运算(CSIMV)，分块同时更新T^-1B p₁。然后顺序读取第一处理-缓存流水级的乒乓RAM中的T^-1As^T，进而执行向量加法运算(VA)，逐比特更新p₂，并将其存储在深度为p×q、位宽为1的乒乓RAM中。

所述的准循环移位单位阵乘向量运算，考虑到循环移位单位阵乘向量相当于将向量循环移位，本发明将每个准循环移位单位阵乘向量的运算按照H矩阵中块的大小分解成多个循环移位单位阵乘向量的运算。假设α为移位因子，当一个q×q的循环移位单位阵与长为q的向量x相乘时，其结果就是将向量x循环上移了α位。在循环移位单位阵乘向量使能时，使用一个二进制计数器对向量x进行地址选通，把当前循环移位单位阵的移位因子α载入计数器，读出x的第α位，此后计数器按模q计数，每次读出x中的一位，q个时钟之后，就完成了循环移位单位阵与向量x的乘法。由于A、B、T、C、D、E都是准循环移位单位阵，编码预处理后的矩阵T^-1A、C、T^-1B、E也都是准循环移位单位阵，都能由循环移位单位阵构成，因此能适用上述算法。

所述的准循环移位阵乘向量运算，涉及Φ^-1与(ET^-1A+C)s^T的相乘的计算，本发明将该运算按照H矩阵中块的大小分解成多个循环移位阵乘向量的运算。当一个q×q的循环移位阵V与一个长为q的向量x相乘，在循环移位阵乘向量使能时，把V中的第一行并行载入寄存器组，同时把相乘向量x的各分量输入到对应的与门上，把各与门的输出结果进行模2加(异或)运算之后，就得到第一个输出比特。此后每经过一个时钟周期，寄存器循环右移一位，就能得到后续的输出比特，q个时钟之后，就完成了本次循环移位阵V与向量x的乘法。

与现有的基于RU方法的编码器相比，本发明所述的编码器具有以下特点：

(1)本发明利用T^-1A是准循环移位单位阵的特性，仅存储T^-1A的乘积矩阵，这样做要比RU方法编码器中分别存储T^-1和A两个矩阵节省资源，类似地，本发明只需要存储T^-1B的乘积矩阵。当T^-1、A和B都是准循环移位单位阵时，ROM资源可以节省[2/(d_c+1)]×100％。

(2)本发明利用T^-1的准循环移位单位阵特性，使得RU方法中与T^-1的串行乘法得以去除，将吞吐量提高了(3×d_c/d_v)×100％，而且将流水线级数从RU方法的6级缩短到现在的4级，在假定每一级流水线消耗时钟数不变的情况下，将编码时延缩短了33％。

(3)本发明进一步改进了流水线结构的平衡性，使每一级流水线的运算所需时钟数都为p×q，解决了RU方法流水线延时不平均的问题，进一步缩短了编码时延。

(4)本发明中准循环移位单位阵乘向量运算、向量加法运算和准循环移位阵乘向量运算均支持分块计算，因此编码器能支持可变码长、可变码率的各种LDPC码。通过改变d_c和d_v，本发明支持的码率有：1/2、2/3、3/4、4/5、…、n/n+1；通过改变p或q，就能实现码长的改变，只需要将每个模块的大小对应最大的p和q进行配置即可。

附图说明

图1为本发明实施基于的分层准循环LDPC校验矩阵的示意图；

图2为本发明实施例流水线结构示意图；

图3为本发明实施例的分层准循环LDPC校验矩阵的示意图；

图4为本发明实施例中根据图3的校验矩阵预处理后结果示意图；

图5为本发明实施例中根据图4预处理矩阵进行编码的示意图；

图6为本发明实施例中各ROM存储示意图；

图7为本发明实施例中准循环移位单位阵乘向量示意图；

图8为本发明实施例中准循环移位阵乘向量示意图；

图9为本发明实施例中RAM分割示意图；

图10为本发明为适应不同码长、码率配置准循环移位单位阵乘向量示意图。

具体实施方式

下面结合附图对本发明的实施例作详细说明：本实施例在以本发明技术方案为前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

图1给出了本发明实施基于的分层准循环LDPC校验矩阵的示意图。图中假设校验矩阵H行重为d_c，列重为d_v，则H矩阵分层数为d_v，每个循环移位单位阵都是q×q的，每一个块由p²个循环移位单位阵拼接而成，其中A由1×(d_c-d_v)的块组成，B由1×(d_v-1)的块组成，T只占用一个块的大小，C由(d_v-1)×(d_c-d_v)的块组成，D由(d_v-1)×(d_v-1)的块组成，E由(d_v-1)×1的块组成。

令x＝(s，p₁，p₂)，其中s是信息比特，p₁和p₂分别表示校验比特的前后两部分，分别对应图1中D和E所在的列，Φ＝-ET^-1B+D。

在本实施例中，假设d_c＝6、d_v＝3，p＝2，q＝2，故得到的校验矩阵H为12行24列。

图2示出了本实施例流水线结构，给出了流水线的分级及各级流水线中主要模块的划分。本发明将流水线级数从RU方法的6级缩短到现在的4级，在假定每一级流水线消耗时钟数不变的情况下，将编码时延缩短了33％。

本实施例具体包括：输入缓存、第一处理-缓存流水级、第二处理流水级、第三缓存流水级、第四处理-缓存流水级、输出级，其特征在于：

所述的输入缓存，将信息比特s按照校验矩阵H中块的大小p×q进行分割，分别存储在p个深度为q、位宽为1的乒乓RAM中，另外使用6块深度为p×q、位宽为的d_c-d_v的RAM对信息比特s进行FIFO操作以确保信息比特s与校验比特p₁、p₂同步传递给输出级；

所述第一处理-缓存流水级，先同时分块读取输入缓存各乒乓RAM的信息比特，然后同时分块执行准循环移位单位阵乘向量运算，分块同时更新向量T^-1As^T，Cs^T，并将其按照校验矩阵H中块的大小p×q进行分割，分别存储在p个深度为q、位宽为1的乒乓RAM中，另外使用4块深度为p×q、位宽为1的RAM对向量T^-1As^T进行FIFO操作以确保向量T^-1As^T与的校验比特p₁同步传递给第四处理-缓存流水级；

所述第二处理流水级，首先同时分块读取第一处理-缓存流水级各乒乓RAM中向量T^-1As^T，Cs^T的值，接着同时分块执行准循环移位单位阵乘向量运算，然后同时分块执行向量加法运算，最后同时分块执行准循环移位阵乘向量运算，分块同时更新校验比特p₁并输出给第三缓存流水级；

所述第三缓存流水级，将校验比特p₁按照校验矩阵H中块的大小p×q进行分割，分别存储在p个深度为q、位宽为1的乒乓RAM中，另外使用3块深度为p×q、位宽为2的RAM对校验比特p₁进行FIFO操作以确保校验比特p₁与信息比特s、校验比特p₂同步传递给输出级；

所述第四处理-缓存流水级，首先同时分块读取第三缓存流水级各乒乓RAM中的校验比特p₁和第一处理-流水级的乒乓RAM中向量T^-1As^T的值，然后同时分块执行准循环移位单位阵乘向量运算，最后执行向量加法运算，更新校验比特p₂并将其存储在深度为p×q、位宽为1的乒乓RAM中；

所述输出级同时分块读取输入缓存的乒乓RAM中的信息比特s、第三缓存流水级的乒乓RAM中的校验比特p₁以及第四处理-流水级的乒乓RAM中校验比特p₂的值，并将其输出给信道。

图3示出了本发明实施例的分层准循环LDPC校验矩阵的示意图，它的几个分割已经在图中标注；

图4示出了本发明实施例中根据图3的校验矩阵预处理后结果；如图4所示，本实施例中的校验矩阵预处理包括以下部分：

为了解释方便，定义矩阵的(r₁，r₂；c₁，c₂)子矩阵为限定于原矩阵[r₁，r₂]行和[c₁，c₂]列的矩阵。则矩阵A 301是矩阵H 201的(1，4；1，12)子矩阵，矩阵B 302是矩阵H的(1，4；13，18)子矩阵，矩阵T 303是矩阵H的(1，4；19，24)子矩阵，矩阵C 304是矩阵H的(5，12；1，12)子矩阵，矩阵D 305是矩阵H的(5，12；13，18)子矩阵，矩阵E 306是矩阵H的(5，12；19，24)子矩阵。经过模2矩阵乘法运算和高斯消元后得到Φ307以及Φ^-1308，T^-1A 309和T^-1B 310。

图5示出了本发明实施例的编码流程图，基于图4的预处理矩阵和图2的流水线结构，本实施例中编码包括以下步骤：

假定待编码信息比特为s401，一份s被存储在输入缓存的由6块深度为4、位宽为3的RAM组成的缓存101中，另外两份s被分块存储在输入缓存的18对深度为2、位宽为1的乒乓RAM 102中。经过第一处理-缓存流水级的准循环移位单位阵乘向量运算106，得到T^-1As^T402，一份T^-1As^T被存储在第一处理-缓存流水级的2对深度为2、位宽为1的乒乓RAM 108中，另一份T^-1As^T被存储在第一处理-缓存流水级的由4块深度为4、位宽为1的RAM组成的缓存109中。经过准循环移位单位阵乘向量运算105，得到C₁s^T 403，C₂s^T 404，并将其分别存储在第一处理-缓存流水级的2对深度为4、位宽为1的乒乓RAM 107中。乒乓RAM 108中的T^-1As^T经过第二处理流水级的准循环移位单位阵乘向量运算111，得到E¹T^-1As^T 405，E₂T^-1As^T 406，将它们同时分块与乒乓RAM 107中的C₁s^T 403，C₂s^T 404作向量加法运算，得到(E₁T^-1A+C₁)s^T 407，(E₂T^-1A+C₂)s^T 408，分别经过第二处理流水级的准循环移位阵乘向量运算116，分块逐比特得到p₁ 410。第三缓存流水级将一份p₁存储在由3块深度为4、位宽为2的RAM组成的缓存117中，另一份p₁被分块存储在4对深度为2、位宽为1的乒乓RAM118中。经过第四处理-缓存流水级的准循环移位单位阵乘向量运算120，得到T^-1Bp₁ 411，将其与第一处理-缓存流水级的乒乓RAM中的T^-1As^T作向量加法运算122，得到p₂ 412，并将其存储在第四处理-缓存流水级的深度为4、位宽为1的乒乓RAM 123中。输出级读取第一处理-缓存流水级的乒乓RAM 101中的s、第三缓存流水级的乒乓RAM 117中的p₁以及第四处理-缓存流水级的乒乓RAM 123中的p₂，并组合成输出编码后码字x413。

图6为根据本发明实施例的方法各ROM存储示意图。对应图2来看，501存放在图2中的ROM 104，502存放在图2中的ROM 119，503、505存放在图2中的ROM 103，504、506存放在图2中的ROM 110，507存放在图2中的ROM 115。举例ROM E₁ 504的生成方法，由矩阵H 201可知，E₁由四个循环移位单位阵组成，存储E₁的ROM的每一个地址上，高位指示该地址对应行块中循环移位单位阵的位置，低位指示该循环移位单位阵的移位因子。另外，若如RU方法编码器所述分别存储T^-1、A和B，由于A、B在大小上和T^-1A、T^-1B无异，则需要多存储两份T^-1，每份需要一个深度为2、位宽为2的ROM，这样将增加40％的ROM资源消耗。

图7为本发明实施例中准循环移位单位阵乘向量示意图。举例E₁×T^-1As^T来说，步骤701读出存储E₁的ROM的低地址数据，步骤702根据当前ROM数据高位截取输入向量长度为2(q)的2(p)段中的一段，如果高位是1则截取输入向量的下半段，反之则截取输入向量的上半段，步骤703按照当前ROM数据低位对该段输入向量循环移位后构成目标向量的上半段。步骤704读出存储E₁的ROM的高地址数据，步骤705根据当前数据高位截取输入向量长度为2(q)的2(p)段中的一段，步骤706按照当前ROM数据低位对该段输入向量循环移位后构成目标向量的下半段，最终组合得到目标向量707。可见，通过分块计算完成一次准循环移位单位阵乘向量所需的时钟数只是p×q＝4。

图8为本发明实施例中准循环移位阵乘向量示意图。步骤801读出存储Φ^-1的ROM的低地址数据，作为循环移位单位阵1、5、9、13、3、7、11、15的第一列，步骤802将上述数据与对应的输入向量a、c的第一比特相乘，步骤803对上述循环移位单位阵的第一列循环移位一位后得到其第二列，并再次与对应的输入向量a、c的第二比特相乘；步骤804读出存储Φ^-1的ROM的高地址数据，作为循环移位单位阵2、6、1O、14、4、8、12、16的第一列，步骤805将上述数据与对应的输入向量b、d的第一比特相乘，步骤806对上述循环移位单位阵的第一列循环移位一位后得到其第二列，并再次与对应的输入向量b、d的第二比特相乘，最终相加后得到目标向量。

图9为本发明实施例中RAM分割示意图。注意到步骤702需根据准循环移位单位阵ROM数据高位确定相关上级输入向量的移位范围，因此上级输入向量需要被分块存储在RAM中。步骤901将T^-1As^T 402的前2(q)位数据存储在乒乓RAM1的第一块RAM中，步骤902将T^-1As^T的后2(q)位数据存储在乒乓RAM2的第一块RAM中。由于采用了流水线结构，在下一帧到来时，步骤903将下一帧T^-1As^T的数据存放在乒乓RAM1和乒乓RAM2的第二块RAM中，以达到并行计算的效果。

图10为本发明为适应不同码长码率配置准循环移位单位阵乘向量的示意图。步骤1001矩阵{A₂，A₁}乘以向量{s₂，s₁}可以完全并行分解为A₂乘以向量s₂1002和A₁乘以向量s₁ 1003，所需时间与单个A₁乘以向量s₁完全相同。于是并行处理即可实现在可变码长、可变码率的要求下的编码吞吐量不变。

本实施例为了便于说明，选取了较小的H矩阵，本发明适用的H矩阵可以很大。

以上所述仅为本发明的实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。