Survey of Beyond-BP Decoding Algorithms: Theory and Applications

Lü Yibo; HU Wei; WANG Lin

doi:10.11999/JEIT161288

Volume 39 Issue 6

Jun. 2017

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2017 > 39(6): 1503-1514

Lü Yibo, HU Wei, WANG Lin. Survey of Beyond-BP Decoding Algorithms: Theory and Applications[J]. Journal of Electronics & Information Technology, 2017, 39(6): 1503-1514. doi: 10.11999/JEIT161288

Citation:

Lü Yibo, HU Wei, WANG Lin. Survey of Beyond-BP Decoding Algorithms: Theory and Applications[J]. Journal of Electronics & Information Technology, 2017, 39(6): 1503-1514. doi: 10.11999/JEIT161288

Lü Yibo, HU Wei, WANG Lin. Survey of Beyond-BP Decoding Algorithms: Theory and Applications[J]. Journal of Electronics & Information Technology, 2017, 39(6): 1503-1514. doi: 10.11999/JEIT161288

Citation:

Lü Yibo, HU Wei, WANG Lin. Survey of Beyond-BP Decoding Algorithms: Theory and Applications[J]. Journal of Electronics & Information Technology, 2017, 39(6): 1503-1514. doi: 10.11999/JEIT161288

PDF( 394 KB)

Survey of Beyond-BP Decoding Algorithms: Theory and Applications

doi: 10.11999/JEIT161288

Funds:

The National Natural Science Foundation of China (61271241, 61671395)

Received Date: 2016-11-28
Rev Recd Date: 2017-03-21
Publish Date: 2017-06-19

Abstract

Abstract

Low Density Parity Check (LDPC) codes are employed in several standards and systems, due to their Shannon limit approaching ability. However, in order to satisfy the communication systems requirements at the aspects of error correction ability, computing complexity, decoding latency, hardware source consumption and power consumption under different application circumstances, the Belief Propagation (BP) algorithm used for decoding LDPC codes needs to be further investigated and improved. In this survey, authors summarize several different Beyond-BP algorithms from the aspects of motivation, methodology, complexity and performance. Moreover, this survey also discusses the optimization of decoding algorithms for iterative receive system, which can provide a reference for further investigation on this topic.
- Low Density Parity Check (LDPC) codes,
- Belief Propagation (BP) algorithm,
- Beyond-BP algorithm,
- Trapping set,
- Reliability,
- Iterative receive

FullText(HTML)

References(67)

References

GALLAGER R G. Low density parity check codes[J]. IEEE Transactions on Information Theory, 1962, 8(1): 21-28. doi: 10.1109/TIT.1962.1057683.

MACKAY D J C and NEAL R M. Near Shannon limit performance of low density parity check codes[J]. Electronics Letters, 1996, 32(18): 1645-1646. doi: 10.1049/el:19961141.

DVB Organization. ETSI EN 302 307 V1. 2. 1. Digital Video Broadcasting (DVB); second generation framing structure, channel coding and modulation systems for broadcasting, interactive services, news gathering and other broadband satellite applications (DVB-S2)[S]. 2009.

IEEE P802.11 Task Group ad. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications[S]. 2010.

CCSDS. CCSDS 230.2-G-1-next generation uplink[R]. Washington, DC, USA, 2014.

FOSSORIER M, MIHALJEVIC M, and IMAI H. Reduced complexity iterative decoding of low density parity check codes based on belief propagation[J]. IEEE Transactions on Communications, 1999, 47(5): 673-680. doi: 10.1109/26. 768759.

TANNER R M. A recursive approach to low complexity codes[J]. IEEE Transactions on Information Theory, 1981, 27(5): 533-547. doi: 10.1109/TIT.1981.1056404.

DAVEY M and MACKAY D. Low density parity check codes over GF(q)[J]. IEEE Communications Letters, 1998, 2(6): 165-167. doi: 10.1109/4234.681360.

WYMEERSCH H, STEENDAM H, and MOENECLAEY M. Log-domain decoding of LDPC codes over GF(q)[C]. IEEE International Conference on Communications, Paris, France, 2004: 772-776.

WANG C, CHEN X, LI Z, et al. A simplified min-sum decoding algorithm for non-binary LDPC codes[J]. IEEE Transactions on Communications, 2013, 61(1): 24-32. doi: 10.1109/TCOMM.2012.101712.110709.

杨威, 张为. 一种基于分层译码和Min-max的多进制LDPC码译码算法[J]. 电子与信息学报, 2013, 35(7): 1677-1681. doi: 10.3724/SP.J.1146.2012.01634.

YANG W and ZHANG W. A decoding algorithm based on layered decoding and min-max for non binary LDPC codes[J]. Journal of Electronics Information Technology, 2013, 35(7), 1677-1681. doi: 10.3724/SP.J.1146.2012.01634.

LI E, DECLERCQ D, and GUNNAM K. Trellis-based extended min-sum algorithm for non-binary LDPC codes and its hardware structure[J]. IEEE Transactions on Communications, 2013, 61(7): 2600-2611. doi: 10.1109/ TCOMM.2013.050813.120489.

ZHAO D, MA X, CHEN C, et al. A low complexity decoding algorithm for majority-logic decodable nonbinary LDPC codes[J]. IEEE Communications Letters, 2010, 14(11): 1062-1064. doi: 10.1109/LCOMM.2010.100810.101403.

CHEN C, HUANG Q, and CHAO C. Two low-complexity reliability based message-passing algorithms for decoding non-binary LDPC codes[J]. IEEE Transactions on Communications, 2010, 58(11): 3140-3147. doi: 10.1109/ TCOMM.2010.091310.090327.

HUANG Q, ZHANG M, WANG Z, et al. Bit-reliability based low-complexity decoding algorithms for non-binary LDPC codes[J]. IEEE Transactions on Communications, 2014, 62(12): 4230-4240. doi: 10.1109/TCOMM.2014.2370032.

LIU X, LIANG C, ZHANG Y, et al. Decoding of non-binary low-density parity-check codes based on the genetic algorithm and applications over mobile fading channels [J]. IET Communications, 2015, 9(16): 1941-1948. doi: 10. 1049/iet-com.2015.0085.

WAINWRIGHT M, JAAKKOLA T, and WILLSKY A. A new class of upper bounds on the log partition function [J]. IEEE Transactions on Information Theory, 2005, 51(7) : 2313-2335. doi: 10.1109/TIT.2005.850091.

WYMEERSCH H, PENNA F, and SAVIC V. Uniformly reweighted belief propagation for estimation and detection in wireless networks[J]. IEEE Transactions on Wireless Communications, 2012, 11(4): 1587-1595. doi: 10.1109/TWC. 2012.021412.111509.

LIU J and DE LAMARER C. Low-latency reweighted belief propagation decoding for LDPC codes[J]. IEEE Communications Letters, 2012, 16(10): 1660-1663. doi: 10. 1109/LCOMM.2012.080312.121307.

WYMEERSCH H, PENNA F, SAVIC V, et al. Comparison of reweighted message passing algorithms for LDPC decoding [C]. IEEE International Conference on Communications, Budapest, Hungary, 2013: 3264-3269.

DIVSALAR D, DOLINAR S, JONES C R, et al. Capacity approaching protograph codes[J]. IEEE Journal on Select Areas in Communications, 2009, 27(6): 876-888. doi: 10.1109 /JSAC.2009.090806.

HU X Y, ELEFTHERIOU E, and ARNOLD D M. Regular and irregular progressive edge-growth tanner graphs [J]. IEEE Transactions on Information Theory, 2005, 51(1): 386-398. doi: 10.1109/TIT.2004.839541.

RYAN W E and LIN S. Channel Codes: Classical and Modern[M]. Cambridge University Press, 2009.

VASIC B, CHILAPPAGARI S K, NGUYEN D V, et al. Trapping set ontology[C]. 47th Annual Allerton Conference on Communication, Control, and Computing, Monticello, USA, 2009: 1-7.

HAN Y and RYAN W E. Low-floor decoders for LDPC codes[J]. IEEE Transactions on Communications, 2009, 57(6): 1663-1673. doi: 10.1109/TCOMM.2009.06.070325.

HAN Y and RYAN W E. Low-floor detection/decoding of LDPC-coded partial response channels[J]. IEEE Journal on Select Areas in Communications, 2010, 28(2): 252-260. doi: 10.1109/JSAC.2010.100214.

VARNICA N, FOSSORIER M P, and KAVCIC A. Augmented belief propagation decoding of low-density parity-check codes[J]. IEEE Transactions on Communications, 2007, 55(7): 1308-1317. doi: 10.1109/ TCOMM.2007.900611.

KANG J, ZHANG L, DING Z, et al. A two-stage iterative decoding of LDPC codes for lowering error floors[C]. IEEE Global Telecommunication Conference, New Orleans, USA, 2008: 1-4.

吕毅博. 多元差分混沌通信系统数字迭代接收关键技术研究[D]. [Ph.D. dissertation], 厦门大学, 2016: 30-37.

MAO Y Y and BANIHASHEMI A H. Decoding low-density parity-checkcodes with probabilistic scheduling[J]. IEEE Communications Letters, 2001, 5(10): 414-416. doi: 10.1109 /4234.957379.

CASADO A V, GRIOT M, and WESEL R. Informed dynamic scheduling for belief-propagation decoding of LDPC codes[C]. IEEE International Conference on Communications, Glasgow, UK, 2007: 932-937.

HOCEVAR D. A reduced complexity decoder architecture via layered decoding of LDPC codes[C]. IEEE Workshop on Signal Processing Systems, Austin, USA, 2004: 107-112.

CASADO A, GRIOT M, and WESEL R. LDPC decoders with informed dynamic scheduling[J]. IEEE Transactions on Communications, 2010, 58(12): 3470-3479. doi: 10.1109/ TCOMM.2010.101910.070303.

LEE H C, UENG Y L, YEH S M, et al. Two informed dynamic scheduling strategies for iterative LDPC decoders[J]. IEEE Transactions on Communications, 2013: 61(3): 886-896. doi: 10.1109/TCOMM.2013.012313.120172.

LIU X, ZHANG Y, and CUI R. Variable-node-based dynamic scheduling strategy for belief-propagation decoding of LDPC codes[J]. IEEE Communications Letters, 2015, 19(2): 147-150. doi: 10.1109/LCOMM.2014.2385096.

LIU X, ZHOU Z, CUI R, et al. Informed decoding algorithms of LDPC codes based on dynamic selection strategy[J]. IEEE Transactions on Communications, 2016, 64(4): 1357-1366. doi: 10.1109/TCOMM.2016.2527642.

IEEE C802.16e-05/0066r3.LDPC Coding for OFDMA PHY [S]. 2005.

KIM J H, NAM M Y, and SONG H Y. Variable-to-check residual belief propagation for LDPC codes[J]. Electronics Letters, 2009, 45(2): 117-118. doi: 10.1049/el:20092505.

马卓, 杜栓义, 王新梅. 基于量化的LDPC译码算法的高效实现[J]. 电子与信息学报, 2011, 33(9): 2273-2277. doi: 10.3724/ SP.J.1146.2011.00041.

MA Z, DU S Y, and WANG X M. Efficient Implementing of LDPC decoding algorithm based on quantization[J]. Journal of Electronics Information Technology, 2011, 33(9): 2273-2277. doi: 10.3724/ SP.J.1146.2011.00041.

JIAN Y Y and PFISTER H D. Convergence of weighted Min-Sum decoding via dynamic programming on trees[J]. IEEE Transactions on Information Theory, 2014, 60(2): 943-963. doi: 10.1109/TIT.2013.2290303.

姜明, 王晨. 基于原型图的低码率LDPC码最小和译码算法改进方案[J]. 电子与信息学报, 2010, 32(11): 2781-2784. doi: 10.3724/SP.J.1146.2009.01652.

JIANG M and WANG C. An improvement on the Min-sum algorithm for low-rate protograph LDPC codes[J]. Journal of Electronics Information Technology, 2010, 32(11): 2781-2784. doi: 10.3724/SP.J.1146.2009.01652.

KONG L, JIANG Y, HAN G, et al. Improved Min-Sum decoding for 2-D intersymbol interference Channels[J]. IEEE Transactions on Magnetics, 2014, 50(11): 1-4. doi: 10.1109/ TMAG.2014.2317749.

JIANG M, ZHAO C, SHI Z, et al. An improvement on the modified weighted bit flipping decoding algorithm for LDPC codes[J]. IEEE Communications Letters, 2005, 9(9): 814-816. doi: 10.1109/LCOMM.2005.1506712.

张高远, 周亮, 文红. LDPC码加权比特翻转译码算法研究[J].电子与信息学报, 2014, 36(9): 2093-2097. doi: 10.3724/SP.J. 1146.2013.01622.

ZHANG G, ZHOU L, and WEN H. Research on weighted bit-flipping decoding algorithm for LDPC codes[J]. Journal of Electronics Information Technology, 2014, 36(9): 2093-2097. doi: 10.3724/SP.J.1146.2013.01622.

FENG G and HANZO L. Reliability ratio based weightedbit- flipping decoding for low-density parity-check codes[J]. Electronics Letters, 2004, 40(21): 1356-1358. doi: 10.1049/ el:20046400.

CHANG T C and SU Y T. Dynamic weighted bit-flipping decoding algorithms for LDPC codes[J]. IEEE Transactions on Communications, 2015, 63(11): 3950-3963. doi: 10.1109/ TCOMM.2015.2469780.

张高远, 周亮, 苏伟伟, 等. 基于平均幅度的LDPC码加权比特翻转译码算法[J]. 电子与信息学报, 2013, 35(11): 2572-2578. doi: 10.3724/SP.J.1146.2012.01728.

ZHANG G Y, ZHOU L, SU W W, et al. Average magnitude based weighted bit-flipping decoding algorithm for LDPC codes[J]. Journal of Electronics Information Technology, 2013, 35(11): 2572-2578. doi: 10.3724/SP.J.1146.2012.01728.

张高远, 周亮, 文红. 基于幅度和的LDPC码加权比特翻转译码算法[J]. 系统工程与电子技术, 2014, 36(4): 752-757. doi: 10.3969/j.issn.1001-506X.2014.04.24.

ZHANG G Y, ZHOU L, and WEN H. Sum of the magnitude based weighted bit-flipping decoding algorithm for LDPC codes[J]. Systems Engineering and Electronics, 2014, 36(4): 752-757. doi: 10.3969/j.issn.1001-506X.2014.04.24.

陶雄飞, 王跃东, 柳盼. 基于变量节点更新的LDPC码加权比特翻转译码算法[J]. 电子与信息学报, 2016, 38(3): 688-693. doi: 10.11999/JEIT150720.

TAO X F, WANG Y D, and LIU P. Weighted bit-flipping decoding algorithm for LDPC codes based on updating of variable nodes[J]. Journal of Electronics Information Technology, 2016, 38(3): 688-693. doi: 10.11999/JEIT150720.

ZHAO J, ZARKESHVARI F, and BANIHASHEMI A H. On implementation of min-sum algorithm and its modifications for decoding low-density parity-check codes[J]. IEEE Transactions on Communications, 2005, 53(4): 549-554. doi: 10.1109/TCOMM.2004.836563.

ZHANG Z, DOLECEK L, NIKOLIC B, et al. Design of LDPC decoders for improved low error rate performance: Quantization and algorithm choices[J]. IEEE Transactions on Communications, 2009, 57(11): 3258-3268. doi: 10.1109/ TCOMM.2009.11.080105.

PLANJERY S K, DECLERCQ D, DANJEAN L, et al. Finite alphabet iterative decoderspart I: Decoding beyond belief propagation on the binary symmetric channel[J]. IEEE Transactions on Communications, 2013, 61(10): 4033-4045. doi: 10.1109/TCOMM.2013.090513.120443.

DECLERCQ D, VASIC B, PLANJERY S K, et al. Finite alphabet iterative decoderspart II: Towards guaranteed error correction of LDPC codes via iterative decoder diversity [J]. IEEE Transactions on Communications, 2013, 61(10): 4046-4057. doi: 10.1109/ TCOMM.2013.090513.120444.

CAI F, ZHANG X, DECLERCQ D, et al. Finite alphabet iterative decoders for LDPC codes: Optimization, architecture and analysis[J]. IEEE Transactions on Circuits Systems I: Regular Papers, 2014, 61(5): 1366-1375. doi: 10.1109/TCSI. 2014.2309896.

TRAN N H, NGUYEN H H, and LE-NGOC T. Performance analysis and design criteria of BICM-ID with signal space diversity for keyhole Nakagami-m fading channels[J]. IEEE Transactions on Information Theory, 2009, 55(4): 1592-1602. doi: 10.1109/TIT.2009.2013001.

AHMED S. Soft metrics and EXIT chart analysis of non-coherent MFSK with diversity reception in Rician fading channel[J]. IEEE Transactions on Wireless Communications, 2011, 10(6): 1692-1696. doi: 10.1109/TWC.2011.032411. 100499.

CHOI J and HA J. Iterative demodulation and decoding of uplink multiuser m-ary FSK using OFDMA mapping[J]. IEEE Communications Letters, 2013, 17(9): 1842-1845. doi: 10.1109/LCOMM.2013.070913.131359.

UCHOA A G D, HEALY C, and DELAMARE R C. Iterative detection and decoding algorithms for MIMO systems in block-fading channels using LDPC codes[J]. IEEE Transactions on Vehicular Technology, 2016, 65(4): 2735-2741. doi: 10.1109/TVT.2015.2432099.

LYU Y, WANG L, CAI G, et al. Iterative receiver for m-ary DCSK systems[J]. IEEE Transactions on Communications, 2015, 63(11): 3929-3936. doi: 10.1109/TCOMM.2015. 2425877.

LYU Y, WANG L, and XIONG Z. Performance advantage of joint source-channel decoder over iterative receiver under m-ary differential chaotic shift keying systems[C]. IEEE Vehicular Technology Conference 2016 Spring, Nanjing, China, 2016: 1-5.

Relative Articles

Supplements(0)

Cited By

Proportional views