基于优化搜索矩阵LU分解的LDPC码编码方法

摘要

一种信道编码技术领域的基于优化搜索矩阵LU分解的LDPC码编码方法，通过软件预处理以及硬件编码两部分来实现，首先消去校验矩阵相关行，接着按列重大小重新排列校验矩阵，然后采用非相关列组合算法选取非奇异矩阵，再采用简易LU分解算法进行分解，并通过按非奇异矩阵对角线元素渐近归1优化搜索，最后选取得到LU分解后三角矩阵稠密度最低的非奇异矩阵，并采用时段控制并行流程硬件结构，进一步降低了整个编码系统的延迟。本发明保持了传统LU分解编码方案硬件结构相对简单的优势，通过优化搜索矩阵，编码运算量却大大逼近基于Greedy算法近似下三角化的LDPC码编码方案的运算量。本发明适合任何LDPC码，尤其对于非规则码及含有相关行的规则码，优势会更明显。

说明书

技术领域

本发明涉及的是一种信道编码技术领域的方法，具体是一种基于优化搜索矩阵LU分解的LDPC码编码方法。

背景技术

低密度校验(LDPC)码相对于Turbo码可以获得更好的纠错性能，还具有译码器实现简单且可并行运算的优势，但LDPC码编码器相对于Turbo码就复杂得多，Turbo码编码运算量是随码长线性增长的，而LDPC码却是随码长平方增长，由于LDPC码的优异性能是由较长码(一般均大于1000)才获得的，因此编码运算量以及硬件实现的复杂度就是其实际应用中的一个主要障碍。传统的LDPC码编码方法是通过对校验矩阵高斯消元，得生成矩阵，再用信息比特与生成矩阵相乘生成码字，其原理很简单但运算量却巨大，因为高斯消元得到的生成矩阵已不再具有稀疏性，行列重均很大，不利于硬件实现。后来业界提出一种移位寄存方案，采用移位寄存器加反馈的组合实现编码，简单易实现，运算量与码长成线性关系，但只适合具有规律性的循环码或近似循环码。

经对现有技术的文献检索发现，2001年，Richardson等在《IEEE Trans.Inf.Theory》vol.47，no.2，pp.638-656，Feb.2001上发表的“Efficientencoding of low-density parity-check codes”(IEEE信息理论学报2001年2月，第47卷，638到656页，低密度奇偶校验码的有效编码)，该文中提出了一种编码方案，由于方案中用到的大部分矩阵均是运用贪心(greedy)算法对校验矩阵行列置换后得到的，保持了矩阵的稀疏性，很大程度上降低了编码的运算量，使其近似与码长成线性关系，然而这种编码方案将校验矩阵分成六块，还有一个行列均为g(近似下三角和下三角之差)的非奇异稠密矩阵，硬件实现结构比较复杂，时序控制比较困难。检索中还发现，2003年，Su-Chang Chae等人在《IEEE 58^th Vehicular Technology Conference》vol.3，pp.1822-1826，6-9Oct.2003上发表的“Low Complexity Encoding of Regular Low DensityParity Check Codes”(IEEE第58届车载技术会议2003年10月6至9日，第3卷，1822到1826页，规则低密度奇偶校验码的低复杂度编码)，该文中提及的编码方案用到了矩阵的LU分解特性，与RU方案相比编码器的结构大大简化了，但LU分解要求矩阵具有非奇异性，为了满足非奇异性以及便于LU分解的要求，该文提出了转轴与比特颠倒(PABR)算法，这种算法虽然克服了传统LU分解算法有可能不能顺利实施的缺点，但却在大部分情况下搜索非奇异矩阵以及LU分解时需要改变码子位重分布结构，这样势必影响到使用性能最优异的码子，而且未考虑生成的三角矩阵稠密度问题。

发明内容

本发明的目的在于克服现有技术中的不足，提出一种基于优化搜索矩阵LU分解的LDPC码编码方法，使其通过采用全新的预处理方法以及改进后的硬件实现结构，大大降低了整个编码系统的运算量及其延迟，充分发挥了编码器硬件结构相对简单和其运算量及延迟相对较小的两种优势。

本发明是通过以下技术方案实现的，本发明首先消去校验矩阵相关行，接着按列重大小重新排列校验矩阵，然后采用非相关列组合算法选取非奇异矩阵，再采用简易LU分解算法进行分解，并通过按非奇异矩阵对角线元素渐近归1优化搜索非奇异矩阵，最后选取得到LU分解后三角矩阵稠密度最低的非奇异矩阵，很大程度上降低了编码运算量，并采用时段控制并行流程硬件结构，进一步降低了整个编码系统的延迟。

所述的消去校验矩阵相关行，是指：对于校验矩阵中的相关行，当采用迭代译码时，相关行具有增加译码迭代次数的作用，但对于编码来说，这些相关行除了增加编码冗余外没有什么作用，为此软件预处理时首先就是消去相关行，若校验矩阵为H_(m×n)，运用高斯消元法将校验矩阵化成上三角形式，当有m-k个相关行时，必有m-k个行重全为零的行，消去这些行所对应的原校验矩阵中的行即可得非相关行组合矩阵H′_(k×n)。

所述的采用非相关列组合算法选取非奇异矩阵，是指：当将校验矩阵H_(m×n)消去相关行后，所得矩阵H′_(k×n)具有满行秩，有k个线性无关的行，那么矩阵H′_(k×n)也就至少有一组由k个且不多于k个列组成的线性无关组，对H′_(k×n)的列(相当于转置后的行)运用行初等变换法，转换为上三角形式，根据上三角所包含的各列至少可以提取其中一组由k个列组成的线性无关组，这样组成的k×k矩阵B_(k×k)的秩等于k，于是得到非奇异矩阵B_(k×k)，再将H′_(k×n)中B_(k×k)选剩下的列划为矩阵A_(k×(n-k))。

所述的采用简易LU分解算法进行分解，是指：若B_(k×k)＝L_(k×k)U_(k×k)，其中L_(k×k)为下三角，U_(k×k)为上三角，

第一步：初始化，生成两个k×k的单位矩阵L和U，将矩阵B的第一列赋给L的第一列，将矩阵B的第一行赋给U的第一行，并令矩阵L的列c为2，令矩阵U的行r为2；

第二步：根据矩阵方程两边相等的原则，按照式 $>>>l>>(>i>,>n>)>\; >=>>b>>(>i>,>n>)>\; >\oplus >>>>\oplus >>>j>=>1>>>n>->1>\; >>l>>(>i>,>j>)>\; >>u>>(>j>,>n>)>\; >,>$>3≤i≤k，2≤n≤k-1，依次解得矩阵L从c+1行至k行在c列的所有值，按照式 $>>>u>>(>m>,>l>)>\; >=>>b>>(>m>,>j>)>\; >\oplus >>>>>\oplus >>>i>=>1>>>m>->1>\; >>l>>(>m>,>i>)>\; >>u>>(>i>,>j>)>\; >,>$>3≤j≤k，2≤m≤k-1，依次解得矩阵U从r+1列至k列在r行的所有值；

第三步：令c＝c+1，r＝r+1，若r＝k或c＝k，跳至第四步，否则返回第二步；

第四步：分别输出下三角矩阵L和上三角矩阵U，至此矩阵B的LU分解完成。

值得注意的是，在这种算法里没有校验非奇异矩阵B与其LU分解后的积在对角线元素是否全部相等，不是说LU分解不用校准B的对角线元素，而是通过非相关列组合算法选取的非奇异矩阵行列排列顺序刚好满足了这样的要求，这样不必再为了保证对角线元素也相等而揣摩各种分解算法或改变原有校验矩阵位重结构。

所述的按列重大小重新排列校验矩阵，是指：在选取非奇异矩阵前将消去相关行的校验矩阵按列重大小从小到大重新排列。在运用非相关列组合算法选取非奇异矩阵时，是将去掉相关行的校验矩阵转置后利用高斯消元来化为上三角形式的，由于在对每一列进行高斯消元时，造成了事实上的列处理先后次序问题，这样次序不同就导致优先选取的非奇异矩阵所包含的非相关列也是不同的，若消去行相关后校验矩阵各列的列重不全相等，在列高斯消元前对校验矩阵各列按列重从小到大重新排列，选取的非奇异矩阵将优先包含列重低的列，这样能使三角矩阵稠密度明显降低。需要注意的是，列重按小到大排列，经非相关列组合算法选取的非奇异矩阵已不再是按列重大小顺序排列，但这种事先处理方法将得到尽量多的列重小的列排在非奇异矩阵的前列，进而降低分解后的L、U的稠密度。不难看出，上述方法只适合非规则码或者存在相关行的规则码，因为这样才存在列重的不同种排列。

所述的按非奇异矩阵对角线元素渐近归1优化搜索非奇异矩阵，是指：由于非奇异矩阵往往不止一个，这就存在一个最优的非奇异矩阵，由它分解的L、U矩阵最稀疏。而矩阵L、U中元素为1并不仅仅受非奇异矩阵B的稀疏性影响，还受到矩阵B位重分布的影响。鉴于选取的非奇异矩阵已不再具有原始校验矩阵的位重分布结构，本发明通过行列变换化非奇异矩阵对角线元素渐近归1来选取非奇异矩阵，将非奇异矩阵中对角线元素不能归1的列对应的校验矩阵的列在下次非相关列组合时除去，由此搜索，直到对角线元素渐近归1完成，生成L、U稠密度曲线，选取最稀疏的L、U对。这种搜索方法的优点首先是搜索量小，经过非相关列组合算法选取的非奇异矩阵，再经过行列变换，对角元素大部分都能归1，这就导致在去掉对角元素不能归1的那一列时，原先的非奇异矩阵保留了大部分列，基本保持了第一次选取的非奇异矩阵的稀疏性，进而缩小了搜索范围。其次是无无效搜索，由于去掉的每一列都是对角元素不能归1的那一列，去掉后均能顺利搜索出下一个非奇异矩阵。

所述的采用时段控制并行流程硬件结构，是指：鉴于上述全新软处理方法的应用，最后得到的由下、上三角矩阵L、U参加的前、后代入运算量一般均小于等于或者略大于稀疏矩阵A参加的乘法运算量，这就为采用时段控制并行流程硬件结构提供了可能，若前、后向代入法运算量(此两种运算量一般均近似相等)大于或者近似等于乘法运算量，直接可利用下面提供的硬件结构，若乘法运算量是前、后向代入法运算量的a倍，则将矩阵A按行分成a个行数相近的子矩阵并行参加乘法运算。为此将编码大致分为五个时段，第一时段包括输入本次编码信息比特，第二时段包括稀疏矩阵与向量乘法(MVM)器，第三时段包括前向代入(FS)器，第四时段包括后向代入(BS)器，第五时段包括按列置换表生成码字以及输出码字，每一时段通过统一的开始信号控制并输出单独的结束信号，将整个编码器的延时降低为其中一个最大时段的延时，这样可以达到时钟频率的最大化而不至于造成整个系统的不稳定。于是编码器硬件结构包括一个后向代入器、一个前向代入器和a(a≥1)个稀疏矩阵与向量的乘法器，再外加一个用于有效并行运算的时段控制器。

本发明提出的方案能够在保持基于传统LU分解的LDPC码编码器硬件结构相对简单的基础上，通过采用全新的软件预处理方法以及时段控制的并行流程硬件结构，大大降低编码器的运算量及其延迟，基本逼近基于Greedy算法近似下三角化的LDPC码编码方案的运算量及其延迟。该发明在近似不增加编码运算量及其延迟的同时，在一定程度上降低了LDPC码编码器设计的复杂度。

附图说明

图1是本发明软件预处理后的LDPC码校验矩阵形式；

图2是本发明软件预处理执行流程图；

图3是本发明硬件实现结构框图；

图4是随机构造非规则码原始校验矩阵位重分布结构图；

图5是列重按大小排列非相关行组合转置位重分布结构图；

图6是转置行初等变换后非相关行组合位重分布结构图；

图7是最后选取的非相关列组合，即非奇异矩阵B位重分布结构图；

图8是对角线元素渐进归1搜索非奇异矩阵LU分解后的全部三角矩阵非零数目曲线图；

图9是采用本发明搜索的非奇异矩阵LU分解后下三角矩阵L的位重分布结构图；

图10是采用本发明搜索的非奇异矩阵LU分解后上三角矩阵U的位重分布结构图；

图11是采用本发明选取非奇异矩阵后剩余列组成的稀疏矩阵A的位重分布结构图；

图12是采用本发明硬件结构应用于实施例在第二时段部分结构框图。

具体实施方式

以下结合附图提供具体的实施例：

实施例采用随机构造非规则码的校验矩阵，列重最小2、最大20，行重最小5、最大32，行宽750、码长1500，图4至7及9至11所示矩阵中，“1”用点表示，“0”未标出。如图4，整个实施例实现过程如下：

第一步：对校验矩阵进行行、列初等变换，消去相关行，得非相关行组合，本实施例无相关行，故同图4；

第二步：将非相关行组合按列重从小到大依次排列，处理后的非相关行组合非零元素数目不变，但排列次序已打乱，如图5，从上至下行重(转置列重)依次增大；

第三步：转置非相关行组合，进行行初等变换，处理后矩阵变为上三角形式，如图6，对角线以下元素全为零；

第四步：选取行(列转置)非零组合序号所对应的非相关行组合的列，保持排列顺序不变组成非相关列组合，即非奇异矩阵B，边长为750，刚好为非相关行的数目，如图7，此矩阵位重结构按选取顺序分布，不需对对角线元素规1化；

第五步：运用简易LU分解算法分解非奇异矩阵B，得上三角矩阵U和下三角矩阵L，统计并保存其非零元素数目，便于最后比较选取最好用曲线显示，如图8，此为三角矩阵非零数目随搜索次数变化图；

第六步：对非奇异矩阵B进行行、列置换，令其对角线元素渐进归1，统计并保存其对角线元素为零的列所对应的非相关行组合的列序号，运用这种方法总能实现对角线元素全部归1；

第七步：判断第六步所得矩阵是否对角线元素全为1，若是，跳至第八步，若否，令所得矩阵对角线元素为零的第一列所对应的非相关行组合的列全为零，使其不参加以后的非相关列组合选取，跳至第三步；

第八步：比较所有搜索非奇异矩阵LU分解后所得上三角矩阵U和下三角矩阵L的非零元素数目之和，取其中最小的一对，并将原始校验矩阵中对应的非奇异矩阵所包含的非相关列组合除去，剩余列选为稀疏矩阵A，如图9-11，矩阵A的非零数为11064，三角矩阵L、U的非零数分别为4093、4422，为了进一步降低编码延迟，矩阵A还需分为三个行数相近的子矩阵A1、A2及A3进行并行乘法运算；

需要注意的是，在上述所有处理过程中，任何矩阵列的置换顺序均需要记录并保存，在硬件编码结束后需要利用这些置换顺序反方向置换生成码字，只有这样生成码字与原始校验矩阵的乘积才为零，整个执行流程如图2，至此，软件预处理已全部完成，校验矩阵被分成A、L、U三个矩阵，如图1。

硬件编码部分采用时段控制的并行流程硬件结构，如图3，图中灰色部分均表示RAM，设置前后两个缓冲器主要是因为前后两个时段中读写同一RAM可能产生冲突，交替使用可以避免逻辑混乱，箭头方向表示数据流向，转置表RAM储存的是软件预处理时校验矩阵所有列变换的次序。为了进一步降低编码延迟，矩阵A已分成三个矩阵，所以硬件结构第二时段应相应变化，如图12，矩阵A1、A2及A3并行参加乘法运算，结果按A1、A2及A3在A中的排列顺序依次存入缓冲器z。