姜博宇　+姚遠(yuǎn)程　+秦明偉

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

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

中圖分類(lèi)號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

低密度奇偶校驗(yàn)（Low?density Parity?check Codes，LDPC）碼是一種用稀疏的奇偶校驗(yàn)矩陣或Tanner圖定義的線性分組碼[1]。近年來(lái)，由于LDPC碼具有逼近香農(nóng)極限的糾錯(cuò)性能，在信道編碼的研究中引起越來(lái)越多學(xué)者的重視，其已經(jīng)被確定為第四代移動(dòng)通信編碼技術(shù)中的首選碼字。LDPC碼之所以成為信道編碼領(lǐng)域的熱門(mén)研究方向，除了它具有很強(qiáng)的糾錯(cuò)性能外，還有一個(gè)重要的原因是其在譯碼上的優(yōu)勢(shì)[2?3]。由于LDPC碼具有稀疏的校驗(yàn)矩陣，使更高效的譯碼算法成為可能。

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

1 和積譯碼算法

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

4 結(jié) 語(yǔ)

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

參考文獻(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.

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

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

中圖分類(lèi)號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

低密度奇偶校驗(yàn)（Low?density Parity?check Codes，LDPC）碼是一種用稀疏的奇偶校驗(yàn)矩陣或Tanner圖定義的線性分組碼[1]。近年來(lái)，由于LDPC碼具有逼近香農(nóng)極限的糾錯(cuò)性能，在信道編碼的研究中引起越來(lái)越多學(xué)者的重視，其已經(jīng)被確定為第四代移動(dòng)通信編碼技術(shù)中的首選碼字。LDPC碼之所以成為信道編碼領(lǐng)域的熱門(mén)研究方向，除了它具有很強(qiáng)的糾錯(cuò)性能外，還有一個(gè)重要的原因是其在譯碼上的優(yōu)勢(shì)[2?3]。由于LDPC碼具有稀疏的校驗(yàn)矩陣，使更高效的譯碼算法成為可能。

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

1 和積譯碼算法

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

4 結(jié) 語(yǔ)

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

參考文獻(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.

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

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

中圖分類(lèi)號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

低密度奇偶校驗(yàn)（Low?density Parity?check Codes，LDPC）碼是一種用稀疏的奇偶校驗(yàn)矩陣或Tanner圖定義的線性分組碼[1]。近年來(lái)，由于LDPC碼具有逼近香農(nóng)極限的糾錯(cuò)性能，在信道編碼的研究中引起越來(lái)越多學(xué)者的重視，其已經(jīng)被確定為第四代移動(dòng)通信編碼技術(shù)中的首選碼字。LDPC碼之所以成為信道編碼領(lǐng)域的熱門(mén)研究方向，除了它具有很強(qiáng)的糾錯(cuò)性能外，還有一個(gè)重要的原因是其在譯碼上的優(yōu)勢(shì)[2?3]。由于LDPC碼具有稀疏的校驗(yàn)矩陣，使更高效的譯碼算法成為可能。

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

1 和積譯碼算法

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

4 結(jié) 語(yǔ)

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

參考文獻(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.