Two Low-complexity Symbol Flipping Decoding Algorithms for Non-binary LDPC Codes

Haiqiang CHEN; Yaoling WANG; Wenjuan WEI; Bingxu JIANG; Youming SUN; Xiangcheng LI; Tuanfa QIN

doi:10.11999/JEIT191008

Volume 43 Issue 1

Jan. 2021

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2021 > 43(1): 51-59

Haiqiang CHEN, Yaoling WANG, Wenjuan WEI, Bingxu JIANG, Youming SUN, Xiangcheng LI, Tuanfa QIN. Two Low-complexity Symbol Flipping Decoding Algorithms for Non-binary LDPC Codes[J]. Journal of Electronics & Information Technology, 2021, 43(1): 51-59. doi: 10.11999/JEIT191008

Citation:

Haiqiang CHEN, Yaoling WANG, Wenjuan WEI, Bingxu JIANG, Youming SUN, Xiangcheng LI, Tuanfa QIN. Two Low-complexity Symbol Flipping Decoding Algorithms for Non-binary LDPC Codes[J]. Journal of Electronics & Information Technology, 2021, 43(1): 51-59. doi: 10.11999/JEIT191008

Citation:

Haiqiang CHEN, Yaoling WANG, Wenjuan WEI, Bingxu JIANG, Youming SUN, Xiangcheng LI, Tuanfa QIN. Two Low-complexity Symbol Flipping Decoding Algorithms for Non-binary LDPC Codes[J]. Journal of Electronics & Information Technology, 2021, 43(1): 51-59. doi: 10.11999/JEIT191008

PDF( 3118 KB)

Two Low-complexity Symbol Flipping Decoding Algorithms for Non-binary LDPC Codes

doi: 10.11999/JEIT191008

1.
School of Computer, Electronics and Information, Guangxi University, Nanning 530004, China
2.
Guangxi Key Laboratory of Multimedia Communication and Network Technology, Guangxi University, Nanning 530004, China

Funds: The National Natural Science Foundation of China (61761006, 61961004, 61662004), The Natural Science Foundation of Guangxi (2017GXNSFAA198263, 2017GXNSFAA198276, 2018GXNSFAA138079)

Received Date: 2019-12-18
Rev Recd Date: 2020-11-23

Available Online: 2020-11-26

Publish Date: 2021-01-15

Abstract

Abstract

Two low-complexity symbol flipping decoding algorithms, the Improved weighted-Algorithm B algorithm (Iwtd-AlgB) and the Truncation-based Distance-Symbol-Flipping-Decoding with Prediction (TD-SFDP) algorithm, are presented for non-binary Low Density Parity Check (LDPC) codes. For the Iwtd-AlgB algorithm, the scaling factor of the flipping metric can be replaced by the simple sums of the extrinsic information and the distance-based parameter, which can avoid the multiplication operations in the iterations and thus can reduce the decoding complexity. For the presented TD-SFDP algorithm, the variable nodes and the finite field symbols are truncated and classified based on the extrinsic information frequency and the flipping function. Only those nodes/symbols that satisfy the designed conditions can be involved in the message updating process. Simulations and numeric results show that, the presented two decoding algorithms can reduce the computational complexity at each iteration with a controllable performance degradation, thus can make efficient trade-offs between performance and complexity.
- Non-binary Low Density Parity Check (LDPC) code,
- Symbol flipping,
- Iterative decoding,
- Decoding algorithm

FullText(HTML)

References(23)

References

KOU Yu, LIN Shu, and FOSSORIER M P C. Low-density parity-check codes based on finite geometries: A rediscovery and new results[J]. IEEE Transactions on Information Theory, 2001, 47(7): 2711–2736. doi: 10.1109/18.959255

BARNAULT L and DECLERCQ D. Fast decoding algorithm for LDPC over GF (2^q)[C]. 2013 IEEE Information Theory Workshop, Paris, France, 2013: 70–73. doi: 10.1109/ITW.2003.1216697.

SONG Hongxin and CRUZ J R. Reduced-complexity decoding of Q-ary LDPC codes for magnetic recording[J]. IEEE Transactions on Magnetics, 2003, 39(2): 1081–1087. doi: 10.1109/TMAG.2003.808600

DECLERCQ D and FOSSORIER M. Decoding algorithms for non-binary LDPC codes over GF(q)[J]. IEEE Transactions on Communications, 2007, 55(4): 633–643. doi: 10.1109/TCOMM.2007.894088

MA Xiao, ZHANG Kai, CHEN Haiqiang, et al. Low complexity X-EMS algorithms for nonbinary LDPC codes[J]. IEEE Transactions on Communications, 2012, 60(1): 9–13. doi: 10.1109/TCOMM.2011.092011.110082

DEKA K, RAJESH A, and BORA P K. A novel truncation rule for the EMS decoding of non-binary LDPC codes[C]. 2018 International Conference on Signal Processing and Communications, Bangalore, India, 2018: 11–15. doi: 10.1109/SPCOM.2018.8724394.

LI Yibing, ZHANG Sitong, YE Fang, et al. Improved extended min-sum algorithm for non-binary LDPC codes based on node reliability[C]. 2019 IEEE-APS Topical Conference on Antennas and Propagation in Wireless Communications, Granada, Spain, 2019: 292–297. doi: 10.1109/APWC.2019.8870565.

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

YANG Wei and ZHANG Wei. A Decoding algorithm based on layered decoding and Min-max for nonbinary LDPC codes[J]. Journal of Electronics &Information Technology, 2013, 35(7): 1677–1681.

SONG Liyuan, HUANG Qin, WANG Zulin, et al. Two enhanced reliability-based decoding algorithms for nonbinary LDPC codes[J]. IEEE Transactions on Communications, 2016, 64(2): 479–489. doi: 10.1109/TCOMM.2015.2512582

LI Xiangcheng, QIN Tuanfa, CHEN Haiqiang, et al. Hard-information bit-reliability based decoding algorithm for majority-logic decodable nonbinary LDPC codes[J]. IEEE Communications Letters, 2016, 20(5): 866–869. doi: 10.1109/LCOMM.2016.2537812

YEO S and PARK I C. Improved hard-reliability based majority-logic decoding for non-binary LDPC codes[J]. IEEE Communications Letters, 2017, 21(2): 230–233. doi: 10.1109/LCOMM.2016.2623783

RYBIN P and FROLOV A. On the decoding radius realized by low-complexity decoded non-binary irregular LDPC codes[C]. 2018 International Symposium on Information Theory and Its Applications, Singapore, 2018: 384–388. doi: 10.23919/ISITA.2018.8664375.

JAGIELLO K and RYAN W E. Iterative plurality-logic and generalized algorithm B decoding of q-ary LDPC codes[C]. IEEE Information Theory and Applications Workshop, La Jolla, USA, 2011: 1–7.

HUANG Chaocheng, WU C J, CHEN Chaoyu, et al. Parallel symbol-flipping decoding for non-binary LDPC codes[J]. IEEE Communications Letters, 2013, 17(6): 1228–1231. doi: 10.1109/LCOMM.2013.051313.130303

NHAN N Q, NGATCHED T M N, DOBRE O A, et al. Multiple-votes parallel symbol-flipping decoding algorithm for non-binary LDPC codes[J]. IEEE Communications Letters, 2015, 19(6): 905–908. doi: 10.1109/LCOMM.2015.2418260

GARCIA-HERRERO F, DECLERCQ D, and VALLS J. Non-binary LDPC decoder based on symbol flipping with multiple votes[J]. IEEE Communications Letters, 2014, 18(5): 749–752. doi: 10.1109/LCOMM.2014.030914.132867

WANG Shuai, HUANG Qin, and WANG Zulin. Symbol flipping decoding algorithms based on prediction for non-binary LDPC Codes[J]. IEEE Transactions on Communications, 2017, 65(5): 1913–1924. doi: 10.1109/TCOMM.2017.2677438

MU Haiwei, MENG Jiahui, ZHANG Liang, et al. Weighted symbol flipping decoding for non-binary LDPC codes based on iteration stopping criterion[C]. The 37th Chinese Control Conference, Wuhan, China, 2018: 8447–8452. doi: 10.23919/ChiCC.2018.8483599.

DAI Bin, LIU Rongke, GAO Chenyu, et al. Symbol flipping algorithm with self-adjustment strategy for LDPC codes over GF(q)[J]. IEEE Transactions on Vehicular Technology, 2019, 68(7): 7189–7193. doi: 10.1109/TVT.2019.2915802

OH J, HAN S, and HA J. An improved symbol-flipping algorithm for nonbinary LDPC codes and its application to NAND flash memory[J]. IEEE Transactions on Magnetics, 2019, 55(9): 3500113. doi: 10.1109/TMAG.2019.2918985

HUANG Qin, ZHANG Mu, WANG Zulin, 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

ZENG Lingqi, LAN Lan, TAI Yingyu, et al. Transactions Papers - Constructions of nonbinary quasi-cyclic LDPC codes: A finite field approach[J]. IEEE Transactions on Communications, 2008, 56(4): 545–554. doi: 10.1109/TCOMM.2008.060024.

ZENG Lingqi, LAN Lan, TAI Yingyu, et al. Construction of nonbinary cyclic, quasi-cyclic and regular LDPC codes: A finite geometry approach[J]. IEEE Transactions on Communications, 2008, 56(3): 378–387. doi: 10.1109/TCOMM.2008.060025

Relative Articles

Supplements(0)

Cited By

Proportional views