硬件可实现的LDPC译码算法研究

姜博宇　+姚远程　+秦明伟

摘 要： 低密度奇偶校验（LDPC）码有着较强的纠错能力，已被确定为第四代移动通信技术中首选码字。分析对比了几种LDPC译码算法的过程，基于硬件可实现性这一研究热点，对传统的译码算法进行了优化，提出一种易于硬件实现的LDPC译码算法。仿真结果表明：归一化最小和算法在不增加迭代次数，码长较长的情况下也有着很好的译码性能，适合在LDPC译码器的硬件实现中推广。

关键词： LDPC码； 译码算法； 归一化最小和算法； 译码器

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2014）17?0005?04

Abstract： LDPC code possesses excellent capability of error correction， and has been intended to be the preferred codeword of the fourth generation of mobile communication technology. Based on the research focus on hardware implementation of the LDPC decoding algorithm， the traditional decoding algorithm was optimized. The LDPC decoding algorithm， which is easy to be implemented， is proposed on the basis of analysis and comparison of several LDPC decoding algorithms. Simulation results show that normalization min?sum （NMS） algorithm is suitable for LDPC decoder hardware implementation， and has perfect decoding performance even if the number of iterations is not increased and code length is long.

Keywords： LDPC code； decoding algorithm； NMS algorithm； decoder

0 引 言

低密度奇偶校验（Low?density Parity?check Codes，LDPC）码是一种用稀疏的奇偶校验矩阵或Tanner图定义的线性分组码[1]。近年来，由于LDPC码具有逼近香农极限的纠错性能，在信道编码的研究中引起越来越多学者的重视，其已经被确定为第四代移动通信编码技术中的首选码字。LDPC码之所以成为信道编码领域的热门研究方向，除了它具有很强的纠错性能外，还有一个重要的原因是其在译码上的优势[2?3]。由于LDPC码具有稀疏的校验矩阵，使更高效的译码算法成为可能。

近年来就LDPC码的实际应用，国内外进行了大量的研究工作，大部分选择大规模集成电路作为实现方案。本文重点研究LDPC码的译码算法，通过不同译码算法性能的对比，结合易于硬件实现这一初衷，对译码算法进行优化。

1 和积译码算法

文献[1]提出了两种译码方法：软判决和硬判决。硬判决算法有较低的复杂度，容易实现，但译码性能远低于软判决。软判决译码利用后验概率信息，通过迭代运算，使LDPC码的性能更接近香农极限[4]，文献[5?7]给出了几种LDPC码的译码算法。在每次迭代中，利用Tanner图定义的LDPC码，其译码过程包括两步：校验节点的信息更新；变量节点的信息更新。每次迭代过程中，每一个校验节点从关联的变量节点处得到消息，处理之后再传回到关联的变量节点，所有变量节点进行的过程相同，最后变量节点收集到所有可利用的消息之后进行判决。当达到停止条件或者定义的最大迭代次数时，根据迭代结果计算判决信息，输出译码码字。如果码字符合校验关系c×[Ht]=0，则代表译码结果为合法码字[8]。

4 结 语

本文结合传统LDPC和积译码算法的思想，基于硬件可实现性，提出一种易于硬件实现的LDPC译码算法。在不影响译码性能的同时，降低了译码的复杂性，并分析了归一化最小和译码算法中迭代次数与码长对译码性能的影响。仿真结果表明：归一化最小和算法在迭代次数较低，码长较长的情况下依然能够有很好的译码性能，符合硬件实现的要求。

参考文献

[1] GALLAGER R G. Low?density parity?check codes [J]. IEEE Transactions on Information Theroy， 1962， 8（1）： 21?28.

[2] MACKAY D J C， NEAL R M. Near?Shannon?limit performance of low density parity check codes [J]. Electronics Letters， 1996， 32（18）： 1645?1646.

[3] MACKAY D J C. Good error?correcting codes base on very sparse matrices [J]. IEEE Transactions on Information Theory， 1999， 45（2）： 399?431.

[4] TANNER R M. A recursive approach to low complexity codes [J]. IEEE Transactions on Information Theory， 1981， 27（3）： 533?547.

[5] CHEN J， FOSSORIER M P C. Decoding low?density parity?check codes with normalized APP?based algorithm [C]// Proceedings of IEEE 2001 Globe Telecommunications Conference. San Antonio， TX： IEEE， 2001， 2： 1026?1030.

[6] CHEN J， FOSSORIER M. Near optimum universal belief propagation based decoding of low?density parity?check codes [J]. IEEE Transactions on Communication， 2002， 50（1）： 406?414.

[7] HU Xiao?yu， ELEFTHERIOU E， ARNOLD D M， et al. Efficient implementation of the sum?product algorithm for decoding LDPC codes [EB/OL]. [2010?01?10]. http：// WWW. citeseerx.ist.psu.edu.

[8] 贺鹤云.LDPC码基础与应用[M].北京：人民邮电出版社，2009.

摘 要： 低密度奇偶校验（LDPC）码有着较强的纠错能力，已被确定为第四代移动通信技术中首选码字。分析对比了几种LDPC译码算法的过程，基于硬件可实现性这一研究热点，对传统的译码算法进行了优化，提出一种易于硬件实现的LDPC译码算法。仿真结果表明：归一化最小和算法在不增加迭代次数，码长较长的情况下也有着很好的译码性能，适合在LDPC译码器的硬件实现中推广。

关键词： LDPC码； 译码算法； 归一化最小和算法； 译码器

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2014）17?0005?04

Abstract： LDPC code possesses excellent capability of error correction， and has been intended to be the preferred codeword of the fourth generation of mobile communication technology. Based on the research focus on hardware implementation of the LDPC decoding algorithm， the traditional decoding algorithm was optimized. The LDPC decoding algorithm， which is easy to be implemented， is proposed on the basis of analysis and comparison of several LDPC decoding algorithms. Simulation results show that normalization min?sum （NMS） algorithm is suitable for LDPC decoder hardware implementation， and has perfect decoding performance even if the number of iterations is not increased and code length is long.

Keywords： LDPC code； decoding algorithm； NMS algorithm； decoder

0 引 言

低密度奇偶校验（Low?density Parity?check Codes，LDPC）码是一种用稀疏的奇偶校验矩阵或Tanner图定义的线性分组码[1]。近年来，由于LDPC码具有逼近香农极限的纠错性能，在信道编码的研究中引起越来越多学者的重视，其已经被确定为第四代移动通信编码技术中的首选码字。LDPC码之所以成为信道编码领域的热门研究方向，除了它具有很强的纠错性能外，还有一个重要的原因是其在译码上的优势[2?3]。由于LDPC码具有稀疏的校验矩阵，使更高效的译码算法成为可能。

近年来就LDPC码的实际应用，国内外进行了大量的研究工作，大部分选择大规模集成电路作为实现方案。本文重点研究LDPC码的译码算法，通过不同译码算法性能的对比，结合易于硬件实现这一初衷，对译码算法进行优化。

1 和积译码算法

文献[1]提出了两种译码方法：软判决和硬判决。硬判决算法有较低的复杂度，容易实现，但译码性能远低于软判决。软判决译码利用后验概率信息，通过迭代运算，使LDPC码的性能更接近香农极限[4]，文献[5?7]给出了几种LDPC码的译码算法。在每次迭代中，利用Tanner图定义的LDPC码，其译码过程包括两步：校验节点的信息更新；变量节点的信息更新。每次迭代过程中，每一个校验节点从关联的变量节点处得到消息，处理之后再传回到关联的变量节点，所有变量节点进行的过程相同，最后变量节点收集到所有可利用的消息之后进行判决。当达到停止条件或者定义的最大迭代次数时，根据迭代结果计算判决信息，输出译码码字。如果码字符合校验关系c×[Ht]=0，则代表译码结果为合法码字[8]。

4 结 语

本文结合传统LDPC和积译码算法的思想，基于硬件可实现性，提出一种易于硬件实现的LDPC译码算法。在不影响译码性能的同时，降低了译码的复杂性，并分析了归一化最小和译码算法中迭代次数与码长对译码性能的影响。仿真结果表明：归一化最小和算法在迭代次数较低，码长较长的情况下依然能够有很好的译码性能，符合硬件实现的要求。

参考文献

[1] GALLAGER R G. Low?density parity?check codes [J]. IEEE Transactions on Information Theroy， 1962， 8（1）： 21?28.

[2] MACKAY D J C， NEAL R M. Near?Shannon?limit performance of low density parity check codes [J]. Electronics Letters， 1996， 32（18）： 1645?1646.

[3] MACKAY D J C. Good error?correcting codes base on very sparse matrices [J]. IEEE Transactions on Information Theory， 1999， 45（2）： 399?431.

[4] TANNER R M. A recursive approach to low complexity codes [J]. IEEE Transactions on Information Theory， 1981， 27（3）： 533?547.

[5] CHEN J， FOSSORIER M P C. Decoding low?density parity?check codes with normalized APP?based algorithm [C]// Proceedings of IEEE 2001 Globe Telecommunications Conference. San Antonio， TX： IEEE， 2001， 2： 1026?1030.

[6] CHEN J， FOSSORIER M. Near optimum universal belief propagation based decoding of low?density parity?check codes [J]. IEEE Transactions on Communication， 2002， 50（1）： 406?414.

[7] HU Xiao?yu， ELEFTHERIOU E， ARNOLD D M， et al. Efficient implementation of the sum?product algorithm for decoding LDPC codes [EB/OL]. [2010?01?10]. http：// WWW. citeseerx.ist.psu.edu.

[8] 贺鹤云.LDPC码基础与应用[M].北京：人民邮电出版社，2009.

摘 要： 低密度奇偶校验（LDPC）码有着较强的纠错能力，已被确定为第四代移动通信技术中首选码字。分析对比了几种LDPC译码算法的过程，基于硬件可实现性这一研究热点，对传统的译码算法进行了优化，提出一种易于硬件实现的LDPC译码算法。仿真结果表明：归一化最小和算法在不增加迭代次数，码长较长的情况下也有着很好的译码性能，适合在LDPC译码器的硬件实现中推广。

关键词： LDPC码； 译码算法； 归一化最小和算法； 译码器

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2014）17?0005?04

Abstract： LDPC code possesses excellent capability of error correction， and has been intended to be the preferred codeword of the fourth generation of mobile communication technology. Based on the research focus on hardware implementation of the LDPC decoding algorithm， the traditional decoding algorithm was optimized. The LDPC decoding algorithm， which is easy to be implemented， is proposed on the basis of analysis and comparison of several LDPC decoding algorithms. Simulation results show that normalization min?sum （NMS） algorithm is suitable for LDPC decoder hardware implementation， and has perfect decoding performance even if the number of iterations is not increased and code length is long.

Keywords： LDPC code； decoding algorithm； NMS algorithm； decoder

0 引 言

低密度奇偶校验（Low?density Parity?check Codes，LDPC）码是一种用稀疏的奇偶校验矩阵或Tanner图定义的线性分组码[1]。近年来，由于LDPC码具有逼近香农极限的纠错性能，在信道编码的研究中引起越来越多学者的重视，其已经被确定为第四代移动通信编码技术中的首选码字。LDPC码之所以成为信道编码领域的热门研究方向，除了它具有很强的纠错性能外，还有一个重要的原因是其在译码上的优势[2?3]。由于LDPC码具有稀疏的校验矩阵，使更高效的译码算法成为可能。

近年来就LDPC码的实际应用，国内外进行了大量的研究工作，大部分选择大规模集成电路作为实现方案。本文重点研究LDPC码的译码算法，通过不同译码算法性能的对比，结合易于硬件实现这一初衷，对译码算法进行优化。

1 和积译码算法

文献[1]提出了两种译码方法：软判决和硬判决。硬判决算法有较低的复杂度，容易实现，但译码性能远低于软判决。软判决译码利用后验概率信息，通过迭代运算，使LDPC码的性能更接近香农极限[4]，文献[5?7]给出了几种LDPC码的译码算法。在每次迭代中，利用Tanner图定义的LDPC码，其译码过程包括两步：校验节点的信息更新；变量节点的信息更新。每次迭代过程中，每一个校验节点从关联的变量节点处得到消息，处理之后再传回到关联的变量节点，所有变量节点进行的过程相同，最后变量节点收集到所有可利用的消息之后进行判决。当达到停止条件或者定义的最大迭代次数时，根据迭代结果计算判决信息，输出译码码字。如果码字符合校验关系c×[Ht]=0，则代表译码结果为合法码字[8]。

4 结 语

本文结合传统LDPC和积译码算法的思想，基于硬件可实现性，提出一种易于硬件实现的LDPC译码算法。在不影响译码性能的同时，降低了译码的复杂性，并分析了归一化最小和译码算法中迭代次数与码长对译码性能的影响。仿真结果表明：归一化最小和算法在迭代次数较低，码长较长的情况下依然能够有很好的译码性能，符合硬件实现的要求。

参考文献

[1] GALLAGER R G. Low?density parity?check codes [J]. IEEE Transactions on Information Theroy， 1962， 8（1）： 21?28.

[2] MACKAY D J C， NEAL R M. Near?Shannon?limit performance of low density parity check codes [J]. Electronics Letters， 1996， 32（18）： 1645?1646.

[3] MACKAY D J C. Good error?correcting codes base on very sparse matrices [J]. IEEE Transactions on Information Theory， 1999， 45（2）： 399?431.

[4] TANNER R M. A recursive approach to low complexity codes [J]. IEEE Transactions on Information Theory， 1981， 27（3）： 533?547.

[5] CHEN J， FOSSORIER M P C. Decoding low?density parity?check codes with normalized APP?based algorithm [C]// Proceedings of IEEE 2001 Globe Telecommunications Conference. San Antonio， TX： IEEE， 2001， 2： 1026?1030.

[6] CHEN J， FOSSORIER M. Near optimum universal belief propagation based decoding of low?density parity?check codes [J]. IEEE Transactions on Communication， 2002， 50（1）： 406?414.

[7] HU Xiao?yu， ELEFTHERIOU E， ARNOLD D M， et al. Efficient implementation of the sum?product algorithm for decoding LDPC codes [EB/OL]. [2010?01?10]. http：// WWW. citeseerx.ist.psu.edu.

[8] 贺鹤云.LDPC码基础与应用[M].北京：人民邮电出版社，2009.