LDPC码译码算法及性能分析
2022-06-08
0引言
信道编译码技术可以检测并且纠正信号在传输过程中引入的错误，能够保证数据进行可靠的传输[1]。LDPC码的校验矩阵具有稀疏的特性，因此存在高效的译码算法，其纠错能力非常强。1981年，Tanner提出了基于图模型描述码字的概念，将LDPC码的校验矩阵对应到Tanner图的双向二部图上。采用Tanner图构造的LDPC码，通过并行译码可大大降低译码复杂度。Mackay和Neal利用随机构造的Tanner图研究了LDPC码的性能，发现采用和积算法（SPA）的LDPC码具有优异的译码性能，在长码时甚至超过了Turbo码[2]。本文采用Mackay基于二分图提出的改进方案构造LDPC码的校验矩阵。基于置信传播（BP）算法，给出了一种简化的BP算法--对数域迭代APPLLR算法，复杂度大大降低。目前，LDPC码是最有希望在广泛的信道范围取得香农容量的误差纠正技术[3]，在保证LDPC码纠错性能的前提下，降低编译码器实现的复杂度是研究的重点，引发了信道编码界的研究热潮。
1LDPC码编码
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所示。
图1Mackay的1A构造方法
Mackay的1A构造方法是最基本的一种构造方法，它要求保证固定列重为[γ]，而行重尽可能均匀的保持为[ρ]。利用Mackay构造方法得到的LDPC码距离特性很好，且没有短环。
1.2基于奇偶校验矩阵的编码算法
LDPC码的直接编码方法就是利用高斯消去法，产生一个下三角矩阵，然后进一步初等变换得到右边单位阵形式[H=[P|I]]，由[G=[I|P]]得到生成矩阵，再利用信息码元向量[u]和生成矩阵[G]相乘可得到完整码字[C，]即[C=M*G]直接编码[5]。
2LDPC码译码[4，6?7]
BP算法是在Gallager提出的概率译码算法基础上发展而来的。BP算法每次迭代包括2步：变量节点的处理和校验节点的处理。概率域就是在节点间传递的是概率信息，采用很多乘法运算，运算量大；而对数域的和积算法实现是将概率值通过对数似然比变化为软信息值（LLR），再进行传递，这样就将大量乘法运算变为加法运算，大大简化了译码复杂度，利于硬件实现。下面重点介绍对数域迭代APPLLR译码算法。
2.1迭代APPLLR译码算法的变量定义
对于[（N，K）]LDPC码，定义变量[U]取值为0和1时的对数似然比（LLR）为：
[LUdef=logP（U=0）P（U=1）]（1）
设发端发送的码字为[u=[u1，u2，…，uN]]，接收码字为[y=[y1，y2，…，yN]]，由此可以得出在迭代中传递的校验节点和信息节点的软信息为：
[λmn（un）def=log（qmn（0）qmn（1））]（2）
[Λmn（un）def=log（rmn（0）rmn（1））]（3）
2.2迭代APPLLR译码算法
迭代APPLLR译码算法的迭代过程如下：
（1）初始化：设每个变量节点[n]的软信息为：
[L（un）=ln{P（un=0yn）P（un=1yn}]（4）
对于矩阵中[H（m，n）=1，]相应的变量节点的软信息初始化为信道输出的软信息，即[λmn（un）=L（un），][Λmn（un）=0。]
（2）校验节点更新：根据每个变量节点[n，]向与该变量节点相连的所有校验节点传递更新的软信息，计算校验节点信息：
[Λmnun=2tanh-1n∈Nm＼ntanhλmnun2]（5）
（3）变量节点更新：根据每个校验节点[m，]向与该校验节点相连的所有变量节点传递更新的软信息：
[λmn（un）=L（un）+m∈M（n）＼mΛmn（un）]（6）
对变量节点[n]进行判决时，变量节点软信息应为：
[λn（un）=L（un）+m∈M（n）Λmn（un）]（7）
（4）判决：当[λn（un）≥0，]则[un=0]，否则[un=1，]此时判决出的码为：[u={u1，u2，…，uN}。]最后根据校验矩阵来判断所译出的码字是否正确。如果[uHT=0，]那么译码正确，此时，停止迭代；否则继续迭代进行译码，直到迭代次数达到所设定的最大次数。如果此时仍未正确译码，则译码失败。
信道编译码技术可以检测并且纠正信号在传输过程中引入的错误，能够保证数据进行可靠的传输[1]。LDPC码的校验矩阵具有稀疏的特性，因此存在高效的译码算法，其纠错能力非常强。1981年，Tanner提出了基于图模型描述码字的概念，将LDPC码的校验矩阵对应到Tanner图的双向二部图上。采用Tanner图构造的LDPC码，通过并行译码可大大降低译码复杂度。Mackay和Neal利用随机构造的Tanner图研究了LDPC码的性能，发现采用和积算法（SPA）的LDPC码具有优异的译码性能，在长码时甚至超过了Turbo码[2]。本文采用Mackay基于二分图提出的改进方案构造LDPC码的校验矩阵。基于置信传播（BP）算法，给出了一种简化的BP算法--对数域迭代APPLLR算法，复杂度大大降低。目前，LDPC码是最有希望在广泛的信道范围取得香农容量的误差纠正技术[3]，在保证LDPC码纠错性能的前提下，降低编译码器实现的复杂度是研究的重点，引发了信道编码界的研究热潮。
1LDPC码编码
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所示。
图1Mackay的1A构造方法
Mackay的1A构造方法是最基本的一种构造方法，它要求保证固定列重为[γ]，而行重尽可能均匀的保持为[ρ]。利用Mackay构造方法得到的LDPC码距离特性很好，且没有短环。
1.2基于奇偶校验矩阵的编码算法
LDPC码的直接编码方法就是利用高斯消去法，产生一个下三角矩阵，然后进一步初等变换得到右边单位阵形式[H=[P|I]]，由[G=[I|P]]得到生成矩阵，再利用信息码元向量[u]和生成矩阵[G]相乘可得到完整码字[C，]即[C=M*G]直接编码[5]。
2LDPC码译码[4，6?7]
BP算法是在Gallager提出的概率译码算法基础上发展而来的。BP算法每次迭代包括2步：变量节点的处理和校验节点的处理。概率域就是在节点间传递的是概率信息，采用很多乘法运算，运算量大；而对数域的和积算法实现是将概率值通过对数似然比变化为软信息值（LLR），再进行传递，这样就将大量乘法运算变为加法运算，大大简化了译码复杂度，利于硬件实现。下面重点介绍对数域迭代APPLLR译码算法。
2.1迭代APPLLR译码算法的变量定义
对于[（N，K）]LDPC码，定义变量[U]取值为0和1时的对数似然比（LLR）为：
[LUdef=logP（U=0）P（U=1）]（1）
设发端发送的码字为[u=[u1，u2，…，uN]]，接收码字为[y=[y1，y2，…，yN]]，由此可以得出在迭代中传递的校验节点和信息节点的软信息为：
[λmn（un）def=log（qmn（0）qmn（1））]（2）
[Λmn（un）def=log（rmn（0）rmn（1））]（3）
2.2迭代APPLLR译码算法
迭代APPLLR译码算法的迭代过程如下：
（1）初始化：设每个变量节点[n]的软信息为：
[L（un）=ln{P（un=0yn）P（un=1yn}]（4）
对于矩阵中[H（m，n）=1，]相应的变量节点的软信息初始化为信道输出的软信息，即[λmn（un）=L（un），][Λmn（un）=0。]
（2）校验节点更新：根据每个变量节点[n，]向与该变量节点相连的所有校验节点传递更新的软信息，计算校验节点信息：
[Λmnun=2tanh-1n∈Nm＼ntanhλmnun2]（5）
（3）变量节点更新：根据每个校验节点[m，]向与该校验节点相连的所有变量节点传递更新的软信息：
[λmn（un）=L（un）+m∈M（n）＼mΛmn（un）]（6）
对变量节点[n]进行判决时，变量节点软信息应为：
[λn（un）=L（un）+m∈M（n）Λmn（un）]（7）
（4）判决：当[λn（un）≥0，]则[un=0]，否则[un=1，]此时判决出的码为：[u={u1，u2，…，uN}。]最后根据校验矩阵来判断所译出的码字是否正确。如果[uHT=0，]那么译码正确，此时，停止迭代；否则继续迭代进行译码，直到迭代次数达到所设定的最大次数。如果此时仍未正确译码，则译码失败。