一种结构化奇偶校验码的编码方法及其编码器

摘要

一种结构化奇偶校验码的编码方法及其编码器，涉及通信信道的编解码。提供一种可减少编码复杂度，实现线性编码的结构化奇偶校验码的编码方法及其编码器。分别构造准循环矩阵H1和双对角矩阵H2；根据准循环矩阵H1和双对角矩阵H2构造校验矩阵H，H＝[H1H2]；根据校验矩阵H构造系统生成矩阵形式G，其中I为M×M的单位矩阵，将生成矩阵形式G与信息序列相乘，得到校验位序列，与原来的信息序列一起构成一帧完整的码字，即实现结构化奇偶校验码的编码。基于双口RAM的编码器设有中间校验序列计算器、多路选择器和累加器，中间校验序列计算器的输出端接多路选择器的输入端，多路选择器的输出端接累加器的输入端。

权利要求

1.基于双口RAM的编码器，其特征在于设有中间校验序列计算器、多路选择器和累加 器，中间校验序列计算器的输出端接多路选择器的输入端，多路选择器的输出端接累加器的 输入端，中间校验序列为pj(pj1，pj2……，pjn)；

所述中间校验序列计算器设有地址指针存储器、地址指针处理器、异或门运算器、双口 RAM阵列、数据分配器以及模二和加法器，地址指针存储器的输出端接地址指针处理器的输 入端，地址指针处理器的输出端接双口RAM的地址输入端，双口RAM的读出口接数据分配 器的输入端，数据分配器的输出端分别接模二和加法器输入端以及异或门运算器的一个输入 端，所有异或门运算器的另一输入端串接并外接信息序列输入，异或门运算器输出端接双口 RAM的写入口，模二和加法器输出端接多路选择器输入端，多路选择器输出端接累加器。

2.如权利要求1所述的基于双口RAM的编码器，其特征在于地址指针处理器设有双输 入选择器和加法器，双输入选择器中的第1个选择器的1个输入端固定接零，另1个输入端 固定接1，第2个选择器的1个输入端接地址指针存储器的输出端，另1个输入端接加法器 的输出端。

说明书

技术领域

本发明涉及通信信道的编解码，尤其涉及通信数据传输与数据存储中的一种结构化的奇 偶校验码(LDPC码)的编码方法及其编码器。

背景技术

1962年，Gallager(R.G.Gallager.Low-Density Parity-Check Codes.IRE Transon.Inform. Theory.1962，(8)：21～28)首次提出了低密度奇偶校验码(LDPC码)，但是由于其译码算法过 于复杂，并没有得到足够的重视。1996年，Mackay和Neal(D.J.C.MacKay，R.M.Neal.Near Shannon Limit Performance of Low-Density Parity-Check Codes.Electron.Lett.1997， (33)：457～458)发现LDPC码和Turbo码同样具有优异的性能，从而引发了对LDPC码研究 的热潮。基于迭代译码算法，LDPC的译码器可以达到数Gbps的数据吞吐量，但较高的编码 复杂度和编码时延是其应用所面临的一个主要问题。因此，构造出具有线性编码复杂度且性 能优越的结构型LDPC码，成为了对LDPC码的研究热点。
通信系统为了提供不同的服务质量以适应不同的传输环境，需要前向纠错编码的码率甚 至帧长能够自适应的根据信道环境做出相应调整。码率及帧长自适应虽然可以由多个编码器 和译码器实现，但此举势必使得编译码器的复杂度过高，因而如何设计复杂度较低的变码率 变帧长编译码器显得尤为重要，且已成为当前编码领域的研究热点。

发明内容

本发明的目的在于针对现有LDPC码构造方法的不足，以及编码器实现时复杂度过高等 问题，提供一种可减少编码复杂度，实现线性编码的结构化奇偶校验码的编码方法。
本发明的另一目的在于提供一种基于双口随机读取存储器(RAM)实现的，不仅可有效 降低硬件资源，而且能够实现灵活变码率编码的基于双口RAM的编码器。
本发明所述的结构化奇偶校验码的编码方法包括以下步骤：
1)分别构造准循环矩阵H1和双对角矩阵H2
采用欧氏有限几何方法构造的准循环矩阵H1，H1具有如下形式：

式(1)中H1是一个N′×M的矩阵，数组中的元素Ai，j是b*b稀疏准循环方阵，只要确定其 第一行(列)hi，j，即整个确定Ai，j，其中1≤i≤t-c，1≤j≤c，称hi，j为Ai，j的“行(列)生 成矢量”；
对应H1的行数，生成M×M的双对角矩阵H2，H2具有如下形式：
$H_2=\left(\begin{array}{ccccc}1& & & & \\ 1& 1& & & \\ & ...& ...& & \\ & & 1& 1& \\ & & & 1& 1\end{array}\right)---\left(2\right)$
2)根据准循环矩阵H1和双对角矩阵H2构造校验矩阵H，H＝[H1H2]；
3)根据校验矩阵H构造系统生成矩阵形式G，系统生成矩阵G＝[I|P]，其中 $P=H_1^T{H}_2^{-T};$ H2 -T具有以下形式：

其中I为M×M的单位矩阵，将生成矩阵形式G与信息序列相乘，得到校验位序列，与 原来的信息序列一起构成一帧完整的码字，即实现结构化奇偶校验码的编码。
本发明针对上述的结构化的LDPC码提出一种基于双口RAM的硬件实现架构，具体描 述如下。
(1)由于H1 T的循环稀疏特性，因此该矩阵可以由其各个子矩阵的第一行或者第一列表 示，并可以通过存储这些行或者列来表示该矩阵，节省了大量的存储空间；
(2)信息序列首先与H1 T相乘，得到一组中间校验值Pj′；具体实现时用双口RAM组来 缓存Pj′，通过对RAM的读写操作更新Pj′来实现信息序列和H1 T相乘的操作过程，并得到中 间校验序列Pj；
(3)H2 -T可以用累加器来实现，当一帧信息序列处理完成后，将中间校验序列Pj通过累 加器即可得到最终的校验比特序列P，即完成了编码过程。
本发明所述的基于双口RAM的编码器设有中间校验序列计算器、多路选择器和累加器， 中间校验序列计算器的输出端接多路选择器的输入端，多路选择器的输出端接累加器的输入 端，中间校验序列为pj(pj1，pj2……，pjn)。
中间校验序列计算器设有地址指针存储器、地址指针处理器、异或门运算器、双口RAM 阵列、数据分配器以及“模二和加法器”，地址指针存储器的输出端接地址指针处理器的输入 端，地址指针处理器的输出端接双口RAM的地址输入端，双口RAM的读出口接数据分配器 的输入端，数据分配器的输出端分别接模二和加法器输入端以及异或门运算器的一个输入端， 所有异或门运算器的另一输入端串接并外接信息序列输入，异或门运算器输出端接双口RAM 的写入口，模二和加法器输出端接多路选择器输入端，多路选择器输出端接累加器。
地址指针处理器设有双输入选择器和加法器，双输入选择器中的第1个选择器的1个输 入端固定接零，另1个输入端固定接1，第2个选择器的1个输入端接地址指针存储器的输 出端，另1个输入端接加法器的输出端，即另1个输入端接地址指针处理器的输出端。
本发明通过构造一种高度结构化的校验矩阵，设计出了一种结构化的LDPC码，并结合 码型特点提出了一种基于RAM的硬件实现架构，本发明具有以下突出优点：
1)编码方法具有线性复杂度。由于并置了双对角矩阵，可以通过校验矩阵直接生成校验 比特，因此减少了编码复杂度。2)节省存储空间。由于是代数编码方法，编码时只需要存储 校验矩阵的生成元，因此极大地节省了存储空间。3)所获得的码型具有较好的性能。计算机 仿真表明该码在中长帧时其性能甚至优于相近参数的随机LDPC码。4)可以灵活地实现变码 率编码。由于双口RAM的长度可灵活变化，因此不同码率和帧长的码字可以复用相同的双 口RAM资源及至Pj计算模块，从而可以灵活实现变码率编码。

附图说明

图1为有限几何系统示意图。
图2为本发明所述基于双口RAM的编码器实施例的组成框图。
图3为本发明所述基于双口RAM的编码器实施例的移位累加电路组成原理图。
图4为图2中的中间校验序列计算器的组成框图。
图5为图4中的地址指针处理器的组成框图。
图6为生成元存储形式。

具体实施方式

下面结合附图和实施例对本实用新型作进一步说明。
首先给出LDPC码的校验矩阵的详细设计方法，然后给出其编码方法以及硬件实现架构。
1.构造校验矩阵H
校验矩阵由两个子矩阵构成，H＝[H1H2]，下面分别介绍两个字矩阵的构造方法。
1.1构造双对角矩阵H2
H2是一个双对角方阵，其具体形式如式(2)所示。具体的构造算法是：第一列的第一 位和第二位是“1”元素，从第二列开始，下一列是上一列的循环下移一位得到，最后一列仅有 最后一位是“1”。
1.2构造准循环矩阵H1
采用欧氏有限几何方法构造循环校验矩阵H1。欧氏有限几何是由有限个点组成的系统， 假设有n个点和J条线，并且满足下面的构造特性：每条线经过ρ个点；任意两个点都构成有 且仅有的一条线；每个点都由γ条线交叉而成；任意两条线都有至多一个公共点。
如图1所示的一个欧氏有限几何，其参数为n＝4，J＝6，ρ＝2，γ＝3。这样的一个系 统中，它所有的线对应着所要构造矩阵的行，它所有的点对应着所要构造矩阵的列。矩阵中 的元素，则由下述方式进行填充：若第j个点在第i条线上，则hi，j＝1；反之，Hi，j＝0。故 每一个欧氏几何有限系统，就对应着一个矩阵。
EG(m，2s)是域GF(2s)上的一个m维的欧氏几何，m和S都是两个正整数。这个几何由 2ms个点组成，每个点在GF(2s)上都是m重的。全零的m重0＝(0，0，...，0)叫做原点。 EG(m，2s)上的每一个点在GF(2s)中都表现为一个m维的向量空间。EG(m，2s)中的点和线具 有以下几个特征：
(1)共有n＝2ms-1个非0点；
(2)共有J＝(2(m-1)s-1)(2ms-1)/(2s-1)条不过原点0的直线，每条直线上有2s个点；
(3)每个非0点所经过的直线数目为： $\gamma =\frac{(2^{\mathrm{ms}}-1)}{(2^s-1)}-1;$
(4)EG(m，2s)中不过原点的直线可以分割成k＝(2(m-1)s-1)/(2s-1)个循环类，称之为 Q1，Q2，…，QK。每个循环类可以看作是一个(2ms-1)×(2ms-1)的“循环方阵”。该矩阵可以由 本循环类中的任一条直线经过(2ms-2)次循环移位得到。
对于大小为b×b，行(列)重为ω的循环方阵Q，其分解方式分为列分解和行分解两种。
以列分解为例详述分解过程：
定义“t”为列分解因子，1≤t≤ω，表示将循环方阵Q依次分解成t个循环子矩阵。
具体分解步骤如下：
(1)取A的第一列q1；
(2)设定一个整数集合{δi}，1≤δ1，δ2，…δt≤ω，且 $\underset{i=1}{\overset{t}{\Sigma }}{\delta }_i=\omega ;$
(3)根据{δi}，将q1分解成t个长度为b，列重分别为δ1，δ2，…δt的列矢量 q1 (1)，q1 (2)，…，q1 (t)，即把q1中的前δ1个“1”映射成为q1 (1)；接着δ2个“1”映射成q1 (2)，以此类推， 直到最后δt个“1”映射成为q1 (t)；
(4)将3中得到的列矢量q1 (1)，q1 (2)，…，q1 (t)分别进行b-1次向下的循环移位，得到t个b×b 的行(列)重分别为δ1，δ2，…δt的循环方阵A1，A2，…，At，称其为循环方阵Q的“子矩阵”，显 然有Q＝A1+A2+…+At；
(5)将列分解得到的“子矩阵”按照如下方式进行重组：
D＝[A1A2…At]。
行分解方式类似，在循环方阵的分解中，并不是只使用“列分解”或“行分解”，而往往是 两者都使用，即在已经使用“列分解”的基础上使用“行分解”，或是反之。通过上述分解重组 等方式获得的H1矩阵如式(1)。若H1矩阵非满秩，需要对其利用高斯消元法进行满秩处理。
通过上述方式构造的H1矩阵满足以下特性：
(1)每个循环矩阵Ai，j的行(列)重相对其大小b而言都较小；
(2)H1的任意两行(列)最多有一个“1”在相同位置，这称之为“行列”限制。
上述两个特点既保证了H1的稀疏性，同时也保证H1对应的二分图中无二线循环以及四 线循环，从而保证了该种结构的LDPC码具有接近随机构造的LDPC码的性能。
1.3根据H＝[H1H2]，构造校验矩阵H
以构造(6131，5110)码为例来进一步说明校验矩阵的构造过程。
第一步，由有限几何系统，可得到一组{Q}i，其中Qi是511×511，行(列)重为8的循 环方阵。
第二步，从{Q}i中任取5个循环方阵Q1，Q2，…，Q5，然后将其均按照c＝t＝2的方式进行 行列分解，其中c为行分解因子，得到下面5个矩阵：
$D_1=\left[\begin{array}{cc}{A}_{\mathrm{1,1}}^{\left(1\right)}& A_{\mathrm{1,2}}^{\left(2\right)}\\ A_{\mathrm{1,1}}^{\left(2\right)}& A_{\mathrm{1,2}}^{\left(2\right)}\end{array}\right],$ $D_2=\left[\begin{array}{cc}{A}_{2,1}^{\left(1\right)}& A_{2,2}^{\left(1\right)}\\ A_{2,1}^{\left(2\right)}& A_{2,2}^{\left(2\right)}\end{array}\right],$ $...,D_5=\left[\begin{array}{cc}{A}_{5,1}^{\left(1\right)}& A_{5,2}^{\left(1\right)}\\ A_{5,1}^{\left(2\right)}& A_{\mathrm{5,2}}^{\left(2\right)}\end{array}\right].$
在对Qi进行行列分解时，对其进行满秩处理，所以得到的Di是1021×1022，行(列)重 为4的循环方阵。
第三步，将D1，D2，...，D5组合在一起，得到矩阵H1，H1是一个1021×5110的矩阵， 如下式：
$H_1=\left[\begin{array}{ccccc}{A}_{\mathrm{1,1}}^{\left(1\right)}& A_{\mathrm{1,2}}^{\left(1\right)}& ...& A_{\mathrm{5,1}}^{\left(1\right)}& A_{\mathrm{5,2}}^{\left(1\right)}\\ A_{\mathrm{1,1}}^{\left(2\right)}& A_{\mathrm{1,2}}^{\left(2\right)}& ...& A_{\mathrm{5,1}}^{\left(2\right)}& A_{\mathrm{5,2}}^{\left(2\right)}\end{array}\right].$
第四步，将H1并置一个1021×1021的双对角矩阵H2即得到校验矩阵H，如式：
$H\left[H_1{H}_2\right]=\left[\begin{array}{ccccc}{A}_{\mathrm{1,1}}^{\left(1\right)}& A_{\mathrm{1,2}}^{\left(1\right)}& ...& A_{\mathrm{5,1}}^{\left(1\right)}& A_{\mathrm{5,2}}^{\left(1\right)}\\ A_{\mathrm{1,1}}^{\left(2\right)}& A_{\mathrm{1,2}}^{\left(2\right)}& ...& A_{\mathrm{5,1}}^{\left(2\right)}& A_{\mathrm{5,2}}^{\left(2\right)}\end{array}{H}_2\right],$
该校验矩阵对应着一个码长6131，码率为0.83的LDPC码，即(6131，5110)码。
2.编码器的实现
由于H＝[H1H2]中的H2具有的双对角结构，则它有系统生成矩阵形式：G＝[I|P]，其 中 $P=H_1^T{H}_2^{-T},$ H2 -T具有以下形式：

可以用累加器实现，所以编码可以分解为两步来完成：首先将信息位与稀疏矩阵H1 T相 乘得到中间校验比特pj，然后将pj输入累加器，累加器输出的结果便是最终所求的校验位序 列，这些校验序列与信息序列一起便构成了完整的码字。
结合H1矩阵的循环特性，本发明引入双口RAM阵列存储中间校验比特pj，通过地址指 针表征校验矩阵并指示双口RAM的操作地址，由对双口RAM的读写操作实现中间校验位的 更新过程，最终通过将双口RAM阵列的中间校验比特进行模二和得到最终的校验序列。
参见图2，基于双口RAM的编码器设有中间校验序列计算器211～21n、多路选择器22 和累加器23，中间校验序列计算器211～21n的输出端接多路选择器22的输入端，多路选择 器22的输出端接累加器23的输入端，中间校验序列为pj(pj1，pj2……，pjn)。其中累加器23 可以用图3所示的异或门(XOR)31和D触发器32实现。
参见图4，中间校验序列计算器设有地址指针存储器41、地址指针处理器421～42n、异 或门运算器431～43n、双口RAM阵列441～44n、数据分配器451～45n以及“模二和加法 器”46，地址指针存储器41的输出端接地址指针处理器421～42n的输入端，地址指针处理 器421～42n的输出端接双口RAM441～44n的地址输入端，双口RAM441～44n的读出口接 数据分配器的输入端，数据分配器451～45n的输出端分别接“模二和加法器”46输入端以 及异或门运算器431～43n的一个输入端，所有异或门运算器431～43n的另一输入端串接并 外接信息序列输入，异或门运算器431～43n的输出端接双口RAM441～44n的写入口，“模 二和加法器”46的输出端接多路选择器22(参见图2)的输入端，多路选择器22的输出端 接累加器23(参见图2)。在图4中，代号A为地址指针，a为信息序列。
参见图5，地址指针处理器设有双输入选择器51与52以及加法器53，双输入选择器中 的第1个选择器51的1个输入端固定接零，另1个输入端固定接1，第2个选择器52的1 个输入端接地址指针存储器的输出端，另1个输入端接加法器的输出端。此处的加法器53为 一个模b加法器。每b个时钟读取一次地址指针存储器的值，且当前时钟时第1选择51选择 0作为输入，其余b-1个时钟51选择1作为输出。
其中异或门的两个输入端分别是信息序列a(见图4)和双口RAM的读出值，其输出则 被送到双口RAM的输入口重新覆盖到的读位置；双口RAM的读写操作的地址通过地址指针 存储器的指示值实现，且读操作的地址经过一个时钟延时作为写地址，从而保证了读写操作 指示相同的位置；地址指针存储器由只读存储器(ROM)阵列组成，每一组ROM阵列对应 校验矩阵H1 T的一列，其内部存储的是生成元hi，j的1的位置。图5给出生成元存储形式，图 5所示的是一组行重量为2的hi，j的存储方式；当一帧信息位操作完成后，数据分配器将双口 RAM的读出值输送到模二和累加器，此时模二和累加器的输出就是pji，此处pji表示第i路 的中间校验序列pj。上述pj计算模块的模二和运算器以前的单元是并行操作的，但是在信息 序列运算完成后，需要各个计算模块的双口RAM阵列逐个读取出来进行模二和运算，并通 过多路选择器送入后面的累加器。
由于准循环矩阵H1 T是稀疏的，所以只需要花费很小的资源便可以将其表示成地址指针， 而且不同码率和不同帧长在编码时对pj计算模块的操作相同，所以这一部分资源可以复用， 从而使得变码率编码实现时耗费的资源有效降低。
基于双口RAM的编码器各电路之间的相互配合由控制器总体控制，以达到时序上的衍 接。控制器可采用有限状态机实现。
下面结合(6131，5110)码和(8175，7154)码的编码实现为例进一步说明编码器变码 率编码的实现过程。如上所述对于(6131，5110)码，H1 T由10×2个子矩阵组成，所以其 生成元共有20个，又由于其行重为4，按照图5所示的方式进行存储，一共需要2个地址指 针存储器共2×2＝4个ROM和2组pj计算模块，每组pj计算模块包含2个RAM即可实现 编码。由于每个生成元的长度是511，所以RAM的长度设为511。
同理，对于(8175，7154)码，其校验矩阵形式为：
$H=\left[H_1{H}_2\right]=\left[\begin{array}{ccccc}{A}_{\mathrm{1,1}}^{\left(1\right)}& A_{\mathrm{1,2}}^{\left(1\right)}& ...& A_{\mathrm{7,1}}^{\left(1\right)}& A_{\mathrm{7,2}}^{\left(1\right)}\\ A_{\mathrm{1,1}}^{\left(2\right)}& A_{\mathrm{1,2}}^{\left(2\right)}& ...& A_{\mathrm{7,1}}^{\left(2\right)}& A_{\mathrm{7,2}}^{\left(2\right)}\end{array}{H}_2\right],$
其H1 T有14×2个子矩阵，即28个生成元即可完全表示该矩阵，且H1 T行重为4，所以我 们需要4个ROM和2组pj计算模块即可实现编码，且在实现上述两种码型变码率编码时，2 组pj计算模块可以完全复用，只是不同码率编码时需要读取相应码率的地址指针存储器。同 理，在更多码率实现时，只需要设定实现其中单一码率所需最多的pj计算模块的资源数量， 选取单一码率最长的子矩阵维数作为pj计算模块中RAM的长度，即可以实现这些码率的自 适应编码。
采用本发明方法设计的确定的LDPC码结构，校验矩阵的存储只需要几个参数，极大的 节省了存储空间，且变码率实现时编码器的资源可以有效复用，为LDPC的实用迈出了坚实 的一步。