基于二分图构造LDPC码的校验矩阵算法及性能分析
0 引言
信道编译码技术可以检测并且纠正信号在传输过程中引入的错误，能够保证数据进行可靠的传输[1].
ldpc码的校验矩阵具有稀疏的特性，因此存在高效的译码算法，其纠错能力非常强。1981年，tanner提出了基于图模型描述码字的概念，将ldpc码的校验矩阵对应到tanner图的双向二部图上。采用tanner图构造的ldpc码，通过并行译码可大大降低译码复杂度。mack-ay 和neal利用随机构造的tanner 图研究了ldpc 码的性能，发现采用和积算法(spa)的ldpc 码具有优异的译码性能，在长码时甚至超过了turbo 码[2].本文采用mackay 基于二分图提出的改进方案构造ldpc 码的校验矩阵。基于置信传播(bp)算法，给出了一种简化的bp算法--对数域迭代app llr 算法，复杂度大大降低。目前，ldpc码是最有希望在广泛的信道范围取得香农容量的误差纠正技术[3],在保证ldpc 码纠错性能的前提下，降低编译码器实现的复杂度是研究的重点，引发了信道编码界的研究热潮。
1 ldpc 码编码 ldpc码是一种性能非常接近香农极限的“好”码，它是惟一用校验矩阵来表示的线性分组码。ldpc码的编码主要分两步进行，首先构造奇偶校验矩阵，然后是基于奇偶校验矩阵的编码算法。
1.1 校验矩阵的构造 根据式子n*j = m*k 可知，规则的ldpc码(n,j,k)，当参数n, j, k 确定后，可以得到校验方程的数目m,则校验矩阵h 的大小就可以定为m × n.构造ldpc 码校验矩阵的一般步骤为：先生成一个m 行n 列的全0矩阵，然后随机地将每列中的j 个0换成1,每行中的k 个0换成1.但在随机置l的过程中，必须避免出现长度为4的环[4].
如果最小环长为4,在迭代中非常容易造成错误信息的扩散传播，从而导致译码性能的下降[5].
mackay 为了消除校验矩阵中长度为4 的环，基于tanner图提出了改进的构造方案。采取的准则是：在构造时必须保证任意两列间的交叠重量不超过1.本文采用的是mackay的1a构造方法，按照此方法构造的一个ldpc码(3,6)码如图1所示。
mackay的1a构造方法是最基本的一种构造方法，它要求保证固定列重为γ ,而行重尽可能均匀的保持为ρ .
利用mackay构造方法得到的ldpc码距离特性很好，且没有短环。
1.2 基于奇偶校验矩阵的编码算法 ldpc码的直接编码方法就是利用高斯消去法，产生一个下三角矩阵，然后进一步初等变换得到右边单位阵形式h = [p|i] ,由g = [i|p] 得到生成矩阵，再利用信息码元向量u 和生成矩阵g 相乘可得到完整码字c,即c = m*g 直接编码[5].
2 ldpc 码译码[4,6-7] bp 算法是在gallager提出的概率译码算法基础上发展而来的。bp算法每次迭代包括2步：变量节点的处理和校验节点的处理。概率域就是在节点间传递的是概率信息，采用很多乘法运算，运算量大;而对数域的和积算法实现是将概率值通过对数似然比变化为软信息值(llr)，再进行传递，这样就将大量乘法运算变为加法运算，大大简化了译码复杂度，利于硬件实现。下面重点介绍对数域迭代app llr译码算法。
2.1 迭代app llr译码算法的变量定义 对于(n,k) ldpc码，定义变量u 取值为0和1时的对数似然比(llr)为：
设发端发送的码字为u = [u1,u2 ,…，un ] ,接收码字为y = [y1,y2 ,…，yn ] ,由此可以得出在迭代中传递的校验节点和信息节点的软信息为：
2.2 迭代app llr译码算法 迭代app llr译码算法的迭代过程如下：
(1)初始化：设每个变量节点n 的软信息为：
对于矩阵中h(m,n) = 1,相应的变量节点的软信息初始化为信道输出的软信息，即λmn (un ) = l(un )，λmn (un ) = 0.
(2)校验节点更新：根据每个变量节点n,向与该变量节点相连的所有校验节点传递更新的软信息，计算校验节点信息：
(3)判决：当λn (un ) 0,则u-n = 0 ,否则u-n = 1,此时判决出的码为：u- ={u-1,u-2 ,…，u-n}.最后根据校验矩阵来判断所译出的码字是否正确。如果u-h t = 0,那么译码正确，此时，停止迭代;否则继续迭代进行译码，直到迭代次数达到所设定的最大次数。如果此时仍未正确译码，则译码失败。
由以上所述可见，在变量节点更新时只有加法运算，但是还可以再进一步降低算法的实现复杂度。采用迭代app llr 算法，将llr bp 算法中的λn (un ) 代替λmn′(u ) n′ 参与校验信息的迭代。即λn (un ) 不仅用于硬判决，还用于校验信息的更新。这样所传递的变量消息之间便引进了相关性，传递的变量消息就不再是外部消息，仅仅需要计算和存储一个变量消息的数值，可以大大地降低算法的复杂度。
3 ldpc 码在高斯信道下不同译码算法的仿真结果和分析 基于matlab按照上述的编译码方法，在高斯信道下分别对ldpc 码概率域的spa 和对数域的迭代appllr 译码算法进行了误码性能仿真。然后由所得到的性能仿真图形进行分析比较。
3.1 概率域的spa的仿真结果和分析 高斯信道下，用bpsk 调制，采用概率域的迭代译码算法，迭代次数为20,该程序的优点是译码效率高，其关键地方利用了log 函数，提高了译码效率。相同码率均为1 2,码长分别为36,256,512,用概率域的迭代译码算法时的编译码系统的误码率随信噪比变化的曲线如图2所示。
由图2 可见，译码前的误码率最高，采用概率域的迭代译码算法后，误码率大幅度降低，译码性能较好。码长为512的ldpc码纠错性能最好，码长为36的ldpc码纠错性能最差。由此可得：在相同码率下，随着码长的增加，ldpc码的纠错性能逐渐改善。
3.2 迭代app llr译码算法的仿真结果和分析 高斯信道下，用bpsk 调制，采用对数域的迭代译码算法，迭代次数为10,可以设置误码码字的最大数量来计算每个信噪比点，程序简明了，容易理解，而且译码效率非常高。相同码率为1/2,码长分别为36、256、512,用对数域的迭代app llr译码算法时的编译码系统的误码率随信噪比变化的曲线如图3所示。
由图3可见，码长为512的ldpc码纠错性能最好，码长为36的ldpc码纠错性能最差。即在相同码率下，随着码长的增加，ldpc码的纠错性能逐渐改善。
3.3 概率域的spa和对数域的迭代app llr译码算法的误码性能比较及分析 高斯信道下，用bpsk调制，分别对码率为1/2,码长为256 的ldpc 码概率域的spa 和对数域的迭代appllr译码算法的性能比较，如图4所示。
由图4 可见，概率域的spa 算法复杂，需耗费较多的硬件资源和时间，仿真性能略好;对数域的迭代appllr算法将大量乘法运算变为加法运算，大大简化了译码复杂度，算法收敛所需的迭代次数减少一半，译码器的延时也比较小，更利于硬件实现。对数域译码算法运算量的下降是以牺牲一部分的性能为代价的，在复杂度降低的同时，抗干扰能力也在下降，但性能的恶化并不大。
4 ldpc 码在vhf 频段信道下的仿真结果和分析[8-10] vhf频段小尺度模型信道的仿真场景为乡村、城市、沿海、郊区。所仿真的信道基本上是相关的，即是平稳衰落过程。其中相关时间是由时延相关时间(单位：ns)和移动速度来计算。一般情况下，将vhf频段划分为三个子频段：高频段(67.3~108 mhz)、中频段(47.4~67.3 mhz)、低频段(30~47.4 mhz)。本文只对低频段信道进行仿真，为了针对更恶劣的情况，在瑞利多径衰落信道下进行仿真，在四种不同的场景下的时延及功率如表1~表4所示。
ldpc 码在瑞利多径衰落信道(低频)下，用bpsk调制，采用对数域的迭代app llr 译码算法进行性能仿真，码率为1/2,码长为256 的ldpc 码的编译码系统分别在乡村、城市、沿海和郊区四种不同场景的误码率随信噪比变化的曲线，如图5所示。
由图5 可见，ldpc 码在比高斯信道更加恶劣的瑞利信道下，其误码率随信噪比变化的曲线呈下降的趋势。ldpc码在信道条件相对较好的乡村场景下的误码性能最好，在信道条件最恶劣的城市场景下的误码性能最差。由此可以得到，其误码性能与时延、功率及四种场景的环境、地形等因素有着密切的关系。时延越小，功率越小，地形越平坦开阔，障碍物越少，ldpc码的纠错性能越好。即ldpc 码随着信道条件恶劣程度的增加，其译码性能也在逐渐降低。
5 结束语 信道编译码技术已成为现代通信系统不可缺少的关键技术，基于图模型的ldpc 码使人们以较低的复杂度实现了可靠通信，对ldpc码的研究不仅具有重要的学术价值和理论指导意义，更具有强烈的应用背景及十分显着的经济效益。ldpc码是近年来信道编码领域一个里程碑式的进展，优异的纠错性能和自然并行的译码算法使得它在多个国际性通信标准中得到应用。理论分析及仿真结果均表明，基于迭代app llr算法的ldpc码，实现简单，性能优异，具有良好的工程应用前景。
如何在Ubuntu Linux上安装Flash
回流焊焊接后缺陷分析
3D视觉传感技术应用落地，无人车将拥有"3D眼睛"
坚果Pro 3正式降价到手价最低只要2399元
大力发展基于物联网技术的智能电网,我们需享受生活
基于二分图构造LDPC码的校验矩阵算法及性能分析
满载而归 | 瑞萨电子获多项汽车电子领域荣誉奖项
关于2022年汽车标准化工作要点
荣耀9最新消息,荣耀6plus用户换机,荣耀9碎了美的太脆弱
第六届非暴露空间PNT国际学术论坛即将召开
威刚推采用USB 3.1 Type-C接口的SSD移动硬盘SE730H
统计学和机器学习的真正差别你分得清吗？
PLC在千吨液压机控制系统改造中的应用
交流接触器的常见故障
苹果iPhone8专为秒杀你而来! 小米MIX全面屏很牛吗?
低调巨头放大招，紫光展锐首发AIoT产品V5663，性能强大！
区块链能为全球小额信贷市场带来怎样的影响
中科创达操作系统上的积累已成为掘金汽车市场关键武器
基于CYT34065的降压型LED驱动电路
电磁兼容三种抑制方法
ldpc码的校验矩阵具有稀疏的特性，因此存在高效的译码算法，其纠错能力非常强。1981年，tanner提出了基于图模型描述码字的概念，将ldpc码的校验矩阵对应到tanner图的双向二部图上。采用tanner图构造的ldpc码，通过并行译码可大大降低译码复杂度。mack-ay 和neal利用随机构造的tanner 图研究了ldpc 码的性能，发现采用和积算法(spa)的ldpc 码具有优异的译码性能，在长码时甚至超过了turbo 码[2].本文采用mackay 基于二分图提出的改进方案构造ldpc 码的校验矩阵。基于置信传播(bp)算法，给出了一种简化的bp算法--对数域迭代app llr 算法，复杂度大大降低。目前，ldpc码是最有希望在广泛的信道范围取得香农容量的误差纠正技术[3],在保证ldpc 码纠错性能的前提下，降低编译码器实现的复杂度是研究的重点，引发了信道编码界的研究热潮。
1 ldpc 码编码 ldpc码是一种性能非常接近香农极限的“好”码，它是惟一用校验矩阵来表示的线性分组码。ldpc码的编码主要分两步进行，首先构造奇偶校验矩阵，然后是基于奇偶校验矩阵的编码算法。
1.1 校验矩阵的构造 根据式子n*j = m*k 可知，规则的ldpc码(n,j,k)，当参数n, j, k 确定后，可以得到校验方程的数目m,则校验矩阵h 的大小就可以定为m × n.构造ldpc 码校验矩阵的一般步骤为：先生成一个m 行n 列的全0矩阵，然后随机地将每列中的j 个0换成1,每行中的k 个0换成1.但在随机置l的过程中，必须避免出现长度为4的环[4].
如果最小环长为4,在迭代中非常容易造成错误信息的扩散传播，从而导致译码性能的下降[5].
mackay 为了消除校验矩阵中长度为4 的环，基于tanner图提出了改进的构造方案。采取的准则是：在构造时必须保证任意两列间的交叠重量不超过1.本文采用的是mackay的1a构造方法，按照此方法构造的一个ldpc码(3,6)码如图1所示。
mackay的1a构造方法是最基本的一种构造方法，它要求保证固定列重为γ ,而行重尽可能均匀的保持为ρ .
利用mackay构造方法得到的ldpc码距离特性很好，且没有短环。
1.2 基于奇偶校验矩阵的编码算法 ldpc码的直接编码方法就是利用高斯消去法，产生一个下三角矩阵，然后进一步初等变换得到右边单位阵形式h = [p|i] ,由g = [i|p] 得到生成矩阵，再利用信息码元向量u 和生成矩阵g 相乘可得到完整码字c,即c = m*g 直接编码[5].
2 ldpc 码译码[4,6-7] bp 算法是在gallager提出的概率译码算法基础上发展而来的。bp算法每次迭代包括2步：变量节点的处理和校验节点的处理。概率域就是在节点间传递的是概率信息，采用很多乘法运算，运算量大;而对数域的和积算法实现是将概率值通过对数似然比变化为软信息值(llr)，再进行传递，这样就将大量乘法运算变为加法运算，大大简化了译码复杂度，利于硬件实现。下面重点介绍对数域迭代app llr译码算法。
2.1 迭代app llr译码算法的变量定义 对于(n,k) ldpc码，定义变量u 取值为0和1时的对数似然比(llr)为：
设发端发送的码字为u = [u1,u2 ,…，un ] ,接收码字为y = [y1,y2 ,…，yn ] ,由此可以得出在迭代中传递的校验节点和信息节点的软信息为：
2.2 迭代app llr译码算法 迭代app llr译码算法的迭代过程如下：
(1)初始化：设每个变量节点n 的软信息为：
对于矩阵中h(m,n) = 1,相应的变量节点的软信息初始化为信道输出的软信息，即λmn (un ) = l(un )，λmn (un ) = 0.
(2)校验节点更新：根据每个变量节点n,向与该变量节点相连的所有校验节点传递更新的软信息，计算校验节点信息：
(3)判决：当λn (un ) 0,则u-n = 0 ,否则u-n = 1,此时判决出的码为：u- ={u-1,u-2 ,…，u-n}.最后根据校验矩阵来判断所译出的码字是否正确。如果u-h t = 0,那么译码正确，此时，停止迭代;否则继续迭代进行译码，直到迭代次数达到所设定的最大次数。如果此时仍未正确译码，则译码失败。
由以上所述可见，在变量节点更新时只有加法运算，但是还可以再进一步降低算法的实现复杂度。采用迭代app llr 算法，将llr bp 算法中的λn (un ) 代替λmn′(u ) n′ 参与校验信息的迭代。即λn (un ) 不仅用于硬判决，还用于校验信息的更新。这样所传递的变量消息之间便引进了相关性，传递的变量消息就不再是外部消息，仅仅需要计算和存储一个变量消息的数值，可以大大地降低算法的复杂度。
3 ldpc 码在高斯信道下不同译码算法的仿真结果和分析 基于matlab按照上述的编译码方法，在高斯信道下分别对ldpc 码概率域的spa 和对数域的迭代appllr 译码算法进行了误码性能仿真。然后由所得到的性能仿真图形进行分析比较。
3.1 概率域的spa的仿真结果和分析 高斯信道下，用bpsk 调制，采用概率域的迭代译码算法，迭代次数为20,该程序的优点是译码效率高，其关键地方利用了log 函数，提高了译码效率。相同码率均为1 2,码长分别为36,256,512,用概率域的迭代译码算法时的编译码系统的误码率随信噪比变化的曲线如图2所示。
由图2 可见，译码前的误码率最高，采用概率域的迭代译码算法后，误码率大幅度降低，译码性能较好。码长为512的ldpc码纠错性能最好，码长为36的ldpc码纠错性能最差。由此可得：在相同码率下，随着码长的增加，ldpc码的纠错性能逐渐改善。
3.2 迭代app llr译码算法的仿真结果和分析 高斯信道下，用bpsk 调制，采用对数域的迭代译码算法，迭代次数为10,可以设置误码码字的最大数量来计算每个信噪比点，程序简明了，容易理解，而且译码效率非常高。相同码率为1/2,码长分别为36、256、512,用对数域的迭代app llr译码算法时的编译码系统的误码率随信噪比变化的曲线如图3所示。
由图3可见，码长为512的ldpc码纠错性能最好，码长为36的ldpc码纠错性能最差。即在相同码率下，随着码长的增加，ldpc码的纠错性能逐渐改善。
3.3 概率域的spa和对数域的迭代app llr译码算法的误码性能比较及分析 高斯信道下，用bpsk调制，分别对码率为1/2,码长为256 的ldpc 码概率域的spa 和对数域的迭代appllr译码算法的性能比较，如图4所示。
由图4 可见，概率域的spa 算法复杂，需耗费较多的硬件资源和时间，仿真性能略好;对数域的迭代appllr算法将大量乘法运算变为加法运算，大大简化了译码复杂度，算法收敛所需的迭代次数减少一半，译码器的延时也比较小，更利于硬件实现。对数域译码算法运算量的下降是以牺牲一部分的性能为代价的，在复杂度降低的同时，抗干扰能力也在下降，但性能的恶化并不大。
4 ldpc 码在vhf 频段信道下的仿真结果和分析[8-10] vhf频段小尺度模型信道的仿真场景为乡村、城市、沿海、郊区。所仿真的信道基本上是相关的，即是平稳衰落过程。其中相关时间是由时延相关时间(单位：ns)和移动速度来计算。一般情况下，将vhf频段划分为三个子频段：高频段(67.3~108 mhz)、中频段(47.4~67.3 mhz)、低频段(30~47.4 mhz)。本文只对低频段信道进行仿真，为了针对更恶劣的情况，在瑞利多径衰落信道下进行仿真，在四种不同的场景下的时延及功率如表1~表4所示。
ldpc 码在瑞利多径衰落信道(低频)下，用bpsk调制，采用对数域的迭代app llr 译码算法进行性能仿真，码率为1/2,码长为256 的ldpc 码的编译码系统分别在乡村、城市、沿海和郊区四种不同场景的误码率随信噪比变化的曲线，如图5所示。
由图5 可见，ldpc 码在比高斯信道更加恶劣的瑞利信道下，其误码率随信噪比变化的曲线呈下降的趋势。ldpc码在信道条件相对较好的乡村场景下的误码性能最好，在信道条件最恶劣的城市场景下的误码性能最差。由此可以得到，其误码性能与时延、功率及四种场景的环境、地形等因素有着密切的关系。时延越小，功率越小，地形越平坦开阔，障碍物越少，ldpc码的纠错性能越好。即ldpc 码随着信道条件恶劣程度的增加，其译码性能也在逐渐降低。
5 结束语 信道编译码技术已成为现代通信系统不可缺少的关键技术，基于图模型的ldpc 码使人们以较低的复杂度实现了可靠通信，对ldpc码的研究不仅具有重要的学术价值和理论指导意义，更具有强烈的应用背景及十分显着的经济效益。ldpc码是近年来信道编码领域一个里程碑式的进展，优异的纠错性能和自然并行的译码算法使得它在多个国际性通信标准中得到应用。理论分析及仿真结果均表明，基于迭代app llr算法的ldpc码，实现简单，性能优异，具有良好的工程应用前景。
如何在Ubuntu Linux上安装Flash
回流焊焊接后缺陷分析
3D视觉传感技术应用落地，无人车将拥有"3D眼睛"
坚果Pro 3正式降价到手价最低只要2399元
大力发展基于物联网技术的智能电网,我们需享受生活
基于二分图构造LDPC码的校验矩阵算法及性能分析
满载而归 | 瑞萨电子获多项汽车电子领域荣誉奖项
关于2022年汽车标准化工作要点
荣耀9最新消息,荣耀6plus用户换机,荣耀9碎了美的太脆弱
第六届非暴露空间PNT国际学术论坛即将召开
威刚推采用USB 3.1 Type-C接口的SSD移动硬盘SE730H
统计学和机器学习的真正差别你分得清吗？
PLC在千吨液压机控制系统改造中的应用
交流接触器的常见故障
苹果iPhone8专为秒杀你而来! 小米MIX全面屏很牛吗?
低调巨头放大招，紫光展锐首发AIoT产品V5663，性能强大！
区块链能为全球小额信贷市场带来怎样的影响
中科创达操作系统上的积累已成为掘金汽车市场关键武器
基于CYT34065的降压型LED驱动电路
电磁兼容三种抑制方法