硬件可實現的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.