硬件可實現(xiàn)的LDPC譯碼算法研究

姜博宇　+姚遠程　+秦明偉

摘 要： 低密度奇偶校驗（LDPC）碼有著較強的糾錯能力，已被確定為第四代移動通信技術(shù)中首選碼字。分析對比了幾種LDPC譯碼算法的過程，基于硬件可實現(xiàn)性這一研究熱點，對傳統(tǒng)的譯碼算法進行了優(yōu)化，提出一種易于硬件實現(xiàn)的LDPC譯碼算法。仿真結(jié)果表明：歸一化最小和算法在不增加迭代次數(shù)，碼長較長的情況下也有著很好的譯碼性能，適合在LDPC譯碼器的硬件實現(xiàn)中推廣。

關(guān)鍵詞： LDPC碼； 譯碼算法； 歸一化最小和算法； 譯碼器

中圖分類號： TN911?34 文獻標(biāo)識碼： 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碼具有逼近香農(nóng)極限的糾錯性能，在信道編碼的研究中引起越來越多學(xué)者的重視，其已經(jīng)被確定為第四代移動通信編碼技術(shù)中的首選碼字。LDPC碼之所以成為信道編碼領(lǐng)域的熱門研究方向，除了它具有很強的糾錯性能外，還有一個重要的原因是其在譯碼上的優(yōu)勢[2?3]。由于LDPC碼具有稀疏的校驗矩陣，使更高效的譯碼算法成為可能。

近年來就LDPC碼的實際應(yīng)用，國內(nèi)外進行了大量的研究工作，大部分選擇大規(guī)模集成電路作為實現(xiàn)方案。本文重點研究LDPC碼的譯碼算法，通過不同譯碼算法性能的對比，結(jié)合易于硬件實現(xiàn)這一初衷，對譯碼算法進行優(yōu)化。

1 和積譯碼算法

文獻[1]提出了兩種譯碼方法：軟判決和硬判決。硬判決算法有較低的復(fù)雜度，容易實現(xiàn)，但譯碼性能遠低于軟判決。軟判決譯碼利用后驗概率信息，通過迭代運算，使LDPC碼的性能更接近香農(nóng)極限[4]，文獻[5?7]給出了幾種LDPC碼的譯碼算法。在每次迭代中，利用Tanner圖定義的LDPC碼，其譯碼過程包括兩步：校驗節(jié)點的信息更新；變量節(jié)點的信息更新。每次迭代過程中，每一個校驗節(jié)點從關(guān)聯(lián)的變量節(jié)點處得到消息，處理之后再傳回到關(guān)聯(lián)的變量節(jié)點，所有變量節(jié)點進行的過程相同，最后變量節(jié)點收集到所有可利用的消息之后進行判決。當(dāng)達到停止條件或者定義的最大迭代次數(shù)時，根據(jù)迭代結(jié)果計算判決信息，輸出譯碼碼字。如果碼字符合校驗關(guān)系c×[Ht]=0，則代表譯碼結(jié)果為合法碼字[8]。

4 結(jié) 語

本文結(jié)合傳統(tǒng)LDPC和積譯碼算法的思想，基于硬件可實現(xiàn)性，提出一種易于硬件實現(xiàn)的LDPC譯碼算法。在不影響譯碼性能的同時，降低了譯碼的復(fù)雜性，并分析了歸一化最小和譯碼算法中迭代次數(shù)與碼長對譯碼性能的影響。仿真結(jié)果表明：歸一化最小和算法在迭代次數(shù)較低，碼長較長的情況下依然能夠有很好的譯碼性能，符合硬件實現(xiàn)的要求。

參考文獻

[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碼基礎(chǔ)與應(yīng)用[M].北京：人民郵電出版社，2009.

摘 要： 低密度奇偶校驗（LDPC）碼有著較強的糾錯能力，已被確定為第四代移動通信技術(shù)中首選碼字。分析對比了幾種LDPC譯碼算法的過程，基于硬件可實現(xiàn)性這一研究熱點，對傳統(tǒng)的譯碼算法進行了優(yōu)化，提出一種易于硬件實現(xiàn)的LDPC譯碼算法。仿真結(jié)果表明：歸一化最小和算法在不增加迭代次數(shù)，碼長較長的情況下也有著很好的譯碼性能，適合在LDPC譯碼器的硬件實現(xiàn)中推廣。

關(guān)鍵詞： LDPC碼； 譯碼算法； 歸一化最小和算法； 譯碼器

中圖分類號： TN911?34 文獻標(biāo)識碼： 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碼具有逼近香農(nóng)極限的糾錯性能，在信道編碼的研究中引起越來越多學(xué)者的重視，其已經(jīng)被確定為第四代移動通信編碼技術(shù)中的首選碼字。LDPC碼之所以成為信道編碼領(lǐng)域的熱門研究方向，除了它具有很強的糾錯性能外，還有一個重要的原因是其在譯碼上的優(yōu)勢[2?3]。由于LDPC碼具有稀疏的校驗矩陣，使更高效的譯碼算法成為可能。

近年來就LDPC碼的實際應(yīng)用，國內(nèi)外進行了大量的研究工作，大部分選擇大規(guī)模集成電路作為實現(xiàn)方案。本文重點研究LDPC碼的譯碼算法，通過不同譯碼算法性能的對比，結(jié)合易于硬件實現(xiàn)這一初衷，對譯碼算法進行優(yōu)化。

1 和積譯碼算法

文獻[1]提出了兩種譯碼方法：軟判決和硬判決。硬判決算法有較低的復(fù)雜度，容易實現(xiàn)，但譯碼性能遠低于軟判決。軟判決譯碼利用后驗概率信息，通過迭代運算，使LDPC碼的性能更接近香農(nóng)極限[4]，文獻[5?7]給出了幾種LDPC碼的譯碼算法。在每次迭代中，利用Tanner圖定義的LDPC碼，其譯碼過程包括兩步：校驗節(jié)點的信息更新；變量節(jié)點的信息更新。每次迭代過程中，每一個校驗節(jié)點從關(guān)聯(lián)的變量節(jié)點處得到消息，處理之后再傳回到關(guān)聯(lián)的變量節(jié)點，所有變量節(jié)點進行的過程相同，最后變量節(jié)點收集到所有可利用的消息之后進行判決。當(dāng)達到停止條件或者定義的最大迭代次數(shù)時，根據(jù)迭代結(jié)果計算判決信息，輸出譯碼碼字。如果碼字符合校驗關(guān)系c×[Ht]=0，則代表譯碼結(jié)果為合法碼字[8]。

4 結(jié) 語

本文結(jié)合傳統(tǒng)LDPC和積譯碼算法的思想，基于硬件可實現(xiàn)性，提出一種易于硬件實現(xiàn)的LDPC譯碼算法。在不影響譯碼性能的同時，降低了譯碼的復(fù)雜性，并分析了歸一化最小和譯碼算法中迭代次數(shù)與碼長對譯碼性能的影響。仿真結(jié)果表明：歸一化最小和算法在迭代次數(shù)較低，碼長較長的情況下依然能夠有很好的譯碼性能，符合硬件實現(xiàn)的要求。

參考文獻

[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碼基礎(chǔ)與應(yīng)用[M].北京：人民郵電出版社，2009.

摘 要： 低密度奇偶校驗（LDPC）碼有著較強的糾錯能力，已被確定為第四代移動通信技術(shù)中首選碼字。分析對比了幾種LDPC譯碼算法的過程，基于硬件可實現(xiàn)性這一研究熱點，對傳統(tǒng)的譯碼算法進行了優(yōu)化，提出一種易于硬件實現(xiàn)的LDPC譯碼算法。仿真結(jié)果表明：歸一化最小和算法在不增加迭代次數(shù)，碼長較長的情況下也有著很好的譯碼性能，適合在LDPC譯碼器的硬件實現(xiàn)中推廣。

關(guān)鍵詞： LDPC碼； 譯碼算法； 歸一化最小和算法； 譯碼器

中圖分類號： TN911?34 文獻標(biāo)識碼： 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碼具有逼近香農(nóng)極限的糾錯性能，在信道編碼的研究中引起越來越多學(xué)者的重視，其已經(jīng)被確定為第四代移動通信編碼技術(shù)中的首選碼字。LDPC碼之所以成為信道編碼領(lǐng)域的熱門研究方向，除了它具有很強的糾錯性能外，還有一個重要的原因是其在譯碼上的優(yōu)勢[2?3]。由于LDPC碼具有稀疏的校驗矩陣，使更高效的譯碼算法成為可能。

近年來就LDPC碼的實際應(yīng)用，國內(nèi)外進行了大量的研究工作，大部分選擇大規(guī)模集成電路作為實現(xiàn)方案。本文重點研究LDPC碼的譯碼算法，通過不同譯碼算法性能的對比，結(jié)合易于硬件實現(xiàn)這一初衷，對譯碼算法進行優(yōu)化。

1 和積譯碼算法

文獻[1]提出了兩種譯碼方法：軟判決和硬判決。硬判決算法有較低的復(fù)雜度，容易實現(xiàn)，但譯碼性能遠低于軟判決。軟判決譯碼利用后驗概率信息，通過迭代運算，使LDPC碼的性能更接近香農(nóng)極限[4]，文獻[5?7]給出了幾種LDPC碼的譯碼算法。在每次迭代中，利用Tanner圖定義的LDPC碼，其譯碼過程包括兩步：校驗節(jié)點的信息更新；變量節(jié)點的信息更新。每次迭代過程中，每一個校驗節(jié)點從關(guān)聯(lián)的變量節(jié)點處得到消息，處理之后再傳回到關(guān)聯(lián)的變量節(jié)點，所有變量節(jié)點進行的過程相同，最后變量節(jié)點收集到所有可利用的消息之后進行判決。當(dāng)達到停止條件或者定義的最大迭代次數(shù)時，根據(jù)迭代結(jié)果計算判決信息，輸出譯碼碼字。如果碼字符合校驗關(guān)系c×[Ht]=0，則代表譯碼結(jié)果為合法碼字[8]。

4 結(jié) 語

本文結(jié)合傳統(tǒng)LDPC和積譯碼算法的思想，基于硬件可實現(xiàn)性，提出一種易于硬件實現(xiàn)的LDPC譯碼算法。在不影響譯碼性能的同時，降低了譯碼的復(fù)雜性，并分析了歸一化最小和譯碼算法中迭代次數(shù)與碼長對譯碼性能的影響。仿真結(jié)果表明：歸一化最小和算法在迭代次數(shù)較低，碼長較長的情況下依然能夠有很好的譯碼性能，符合硬件實現(xiàn)的要求。

參考文獻

[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碼基礎(chǔ)與應(yīng)用[M].北京：人民郵電出版社，2009.