多进制ldpc码的编码算法研究

多进制ldpc码的编码算法研究

0多进制ldpc码编码算法196年，garago首次提出了ldpc（低密度奇偶校验）代码。目前针对多进制LDPC编码的算法主要有直接编码算法、近似下三角编码算法和准循环RA结构编码算法。直接编码算法原理简单,计算复杂度较高,但对校验矩阵无要求;近似下三角编码算法,也叫做RU编码算法,该算法要求校验矩阵具有下三角或可化简为下三角构造,算法复杂度有所减小,但该种结构的码在性能上会有损失多进制LDPC译码算法复杂度高,大量计算集中在校验节点的更新,因此目前针对多进制LDPC译码算法的改进主要在校验节点更新算法的简化上。最初Davey和MacKay提出概率域和积译码算法(QSPA),该算法运算量太大,硬件无法实现;HenkWymccrsch等人提出对数域和积译码算法(log-SPA)本文所述多进制LDPC码应用背景校验矩阵为64进制、维度为44×88的普通稀疏矩阵,并不具有下三角或准循环结构,因此编码算法采用直接编码算法,提出一种利用查表法计算伽罗华域乘法运算的方法,有效降低了直接编码算法的计算复杂度,提高了编码效率。译码算法在TMM的基础上,对其进行了Matlab仿真验证,并对硬件实现方法进行了进一步优化,提出了多个关键模块的优化设计方案,如整体架构设计、交换网络设计、存储单元设计、比较最小次小值单元设计等。最后以64进制44×88的校验矩阵为例进行编译码的FPGA实现。本文提出的设计方案有效解决了多进制LDPC译码工程实现中资源消耗过大的问题,并在工程实践中得到验证。150.ldtc码的多输入1.1编码算法流程假设校验矩阵为:待编码信息向量为:式中,x编码后的信息向量为c=[x由校验矩阵性质c·H直接编码算法即根据式(1),由待编码信息和校验矩阵直接计算得出冗余位。流程图如图1所示。具体步骤如下:(1)接收并存储待编码的信息;(2)将待编码信息与变换后的校验矩阵在伽罗华域相乘;(3)乘法运算的结果在伽罗华域相加;(4)与待编码信息组合输出编码后的信息比特。1.2多进制ldpc的译码过程多进制LDPC译码算法主体步骤类似于二进制LDPC译码算法,主要包括初始化、迭代更新和输出判决。主要区别在于多进制LDPC译码过程中所涉及到的除概率外的计算均在伽罗华域GF(q)中进行,另外,在迭代更新过程中由于多进制LDPC每个节点有q个取值的可能,计算复杂度明显增加。对于校验矩阵H1.2.1数值积分法处理初始化的目的是根据接收到的信息完成每个信息对应q个取值的概率。对数操作可将乘除法运算变为加减法运算,显著降低计算量。归一化的目的是使所有的概率取值为非负,为方便后续计算,此时概率越小表示置信度越高。具体计算公式如下:式中,L1.2.2计算变量节点更新值q迭代更新包括变量节点更新和校验节点更新,根据初始化信息,通过一定次数的反复迭代计算,最终使变量节点真值位置概率最小,具体计算公式如下:式中,Q计算变量节点更新值Q按照m=1,2…M的顺序进行更新,在完成M行计算后表示一次迭代更新结束,重新开始下一次迭代更新,在完成设置次数的迭代更新后,迭代更新步骤完成。1.2.3校验节点的更新根据迭代更新步骤计算的变量节点信息,比较计算最小值所在位置即为译码结果,具体计算公式如下:式中,TMM译码算法在计算校验节点更新时通过额外引入一列中间变量,使得校验节点的更新值在每行最小值、次小值和额外引入的值之间选取,整个计算过程只涉及比较和赋值运算,不涉及数据位的扩展,大大简化了计算量,易于硬件实现。TMM的具体计算步骤如下,假设输入为Q式中,z1.3古希腊域元素表示法编译码算法中涉及到的关于位置的运算均在伽罗华域GF(q)中进行,伽罗华域元素可以由本原表示和矢量表示,表1为GF(8)域元素表示法对照表。伽罗华域中的运算与普通域中运算有所不同,加法运算为矢量表示按位异或;乘法运算中本原表示为0的元素与任何元素相乘仍为0,本原表示非0的元素乘法运算为本原元素的幂次模(22仿真结果分析采用Matlab对多进制LDPC直接编码算法及TMM译码算法进行仿真验证。以GF(64)域校验矩阵为H仿真结果如图2所示,为便于比较引入同样为528bit码长的二进制LDPC由仿真结果可以看出,多进制LDPCTMM译码算法原理正确,比同样码长的二进制LDPC性能要好,GF(64)LDPC译码性能优于GF(2)LDPC约0.3dB。3硬件安装3.1校验矩阵模块直接编码算法具体硬件实现整体框图如图3所示,包括存储模块、校验矩阵模块、伽罗华域乘法器、伽罗华域加法器、组合模块和控制模块。存储模块用于接收待编码信息,并在控制模块的作用下以p比特为单位存储待编码信息,将待编码信息分别发送至伽罗华域乘法器和组合模块。校验矩阵模块用于存储对校验矩阵进行变换后得到的矩阵:将变换后的校验矩阵每一行的值存入一个存储单元,并在控制模块的作用下将各个存储单元中的值发送至伽罗华域乘法器,所述的校验矩阵模块包括M个存储单元。伽罗华域乘法器用于每次提取各个存储单元中相同列数的一个值,将提取值与待编码信息在伽罗华域相乘,得到乘法运算的结果输出至伽罗华域加法器。伽罗华域加法器用于将乘法运算的结果在伽罗华域采用按位异或的方法相加,将相加的结果输出至组合模块。组合模块用于在控制模块的作用下将相加的结果与待编码信息组合,输出编码后的信息。控制模块用于控制存储模块中输入数据的存储、校验矩阵模块输入伽罗华域乘法器的数据以及编码信息的输出。伽罗华域乘法器采用查表法实现,实现框图如图4所示,包括第一查找表、第二查找表、模23.2迭代控制模块TMM译码算法整体实现框图如图5所示,主要包括初始化模块、迭代更新模块、存储模块、输出判决模块和迭代控制模块。初始化模块用于在迭代控制模块的作用下接收待译码信息,计算所有输入的待译码信息的后验概率,从所有后验概率中找到最大的后验概率,并根据最大后验概率初始化待译码信息,将初始化后的待译码信息输出至存储模块,并将本模块运行状态报告给迭代控制模块。迭代更新模块用于在迭代控制模块的作用下从存储模块中读取初始化后的待译码信息、前一次校验节点的迭代更新值和变量节点的迭代更新值,计算本次校验节点及变量节点的迭代更新值,将更新值存入存储模块,并将本模块运行状态报告给迭代控制模块。输出判决模块用于在迭代控制模块的作用下从存储模块中读取最后一次变量节点的迭代更新值,根据最后一次变量节点的迭代更新值进行译码输出计算,输出译码后的信息,并将本模块运行状态报告迭代控制模块。存储模块用于存储初始化信息、2组变量节点信息、校验节点信息、校验矩阵信息,接收初始化模块送入的初始化信息,与迭代更新模块进行初始化、变量节点、校验节点、校验矩阵的信息交互,并将最后一次更新的变量节点信息送入输出判决模块。迭代控制模块用于接收初始化模块、迭代更新模块和输出判决模块的运行状态,并控制初始化模块、迭代更新模块和输出判决模块的工作状态。迭代更新模块是整个译码算法中最关键的一部分,算法的核心部分都集中在该模块,具体实现框图如图6所示。整个模块的输入包括初始化信息L本次变量节点信息Q该模块中与概率有关的运算均在普通域中进行,与位置有关的运算均在伽罗华域中进行。置换模块(P和P最小值次小值及最小值对应列查找模块(2minfinder)设计2个基本的比较单元,一个比较单元输入为2个被比较值及其所对应列,输出为最小值、次小值及最小值对应的列;另一个比较单元输入为2组最小值、次小值及最小值对应的列,输出为最小值、次小值及最小值对应的列。通过这2种比较器的组合可实现任意多个输入的最小值次小值及最小值对应列信息查找。具体实现框图如图7所示。额外列提取模块(ExtraColumn)根据最小值及最小值所在的列信息在配置集conf整个提取过程通过二级比较运算和一级选择运算实现。第一级比较运算通过3个两输入一输出的最大值比较器实现,随后输出至二选一选择器的一个输入口,选择器另一个输入口输入固定最大值,以确保在列信息相等时不会被下一级最小值查找单元选中。选择器通过对应的列信息进行选择,若对应的列信息相等则输出最大值,否则输出2个参与比较的较大的一个,选择器的输出送入最小值查找单元。在计算ΔQ4生成编码运算由于多进制LDPC译码算法较为复杂,即使采用计算复杂度最小的TMM算法仍要在资源占用和计算延迟方面权衡考虑,本文在硬件实现时大部分计算以一个节点为最小单位进行串行运算,这样可以最大化地减小资源消耗。在进行m本文以GF(64)域校验矩阵为H编译码器实现后Modelsim仿真结果分别如图9和图10所示。编码器只需要7个时钟周期即可得出第一个校验位计算结果,再经过43个系统时钟周期就可以完成整个编码运算。译码器在10次迭代时只需约2500个时钟周期即可完成从数据输入到译码输出的计算。最终实现的编译码器在相同激励作用下运算结果与Matlab仿真计算结果一致,该编译码器设计正确可行。5基于资源消耗和折中的实现方案多进制LDPC编码器采用直接编码算法,利用查表法实现伽罗华域乘法运算,原理简单易于实现。译码器虽然采用目前计算复杂度最小的TMM算法,但在硬件实现过程中资源消耗仍较大,尤其是随着进制的增加,每个节点对应