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.
吕毅博，胡伟，王琳. Beyond-BP译码算法综述：原理与应用[J]. 电子与信息学报, 2017, 39(6): 1503-1514.
Lü Yibo, HU Wei, WANG Lin. Survey of Beyond-BP Decoding Algorithms: Theory and Applications. JEIT, 2017, 39(6): 1503-1514.
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.
[2]
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.
[3]
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.
[4]
IEEE P802.11 Task Group ad. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications[S]. 2010.
[5]
CCSDS. CCSDS 230.2-G-1-next generation uplink[R]. Washington, DC, USA, 2014.
[6]
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.
[7]
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.
[8]
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.
[9]
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.
[10]
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.
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.
[12]
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.
[13]
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.
[14]
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.
[15]
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.
[16]
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.
[17]
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.
[18]
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.
[19]
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.
[20]
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.
[21]
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.
[22]
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.
[23]
RYAN W E and LIN S. Channel Codes: Classical and Modern[M]. Cambridge University Press, 2009.
[24]
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.
[25]
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.
[26]
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.
[27]
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.
[28]
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.
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.
[31]
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.
[32]
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.
[33]
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.
[34]
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.
[35]
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.
[36]
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.
[37]
IEEE C802.16e-05/0066r3.LDPC Coding for OFDMA PHY [S]. 2005.
[38]
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.
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.
[40]
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.
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.
[42]
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.
[43]
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.
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.
[45]
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.
[46]
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.
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.
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.
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.
[50]
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.
[51]
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.
[52]
PLANJERY S K, DECLERCQ D, DANJEAN L, et al. Finite alphabet iterative decoders—part 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.
[53]
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.
[54]
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.
[55]
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.
[56]
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.
[57]
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.
[58]
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.
[59]
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.
[60]
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.
