高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

两种降低复杂度的符号翻转多元LDPC译码算法

陈海强 王瑶玲 韦文娟 蒋炳旭 孙友明 黎相成 覃团发

陈海强, 王瑶玲, 韦文娟, 蒋炳旭, 孙友明, 黎相成, 覃团发. 两种降低复杂度的符号翻转多元LDPC译码算法[J]. 电子与信息学报, 2021, 43(1): 51-59. doi: 10.11999/JEIT191008
引用本文: 陈海强, 王瑶玲, 韦文娟, 蒋炳旭, 孙友明, 黎相成, 覃团发. 两种降低复杂度的符号翻转多元LDPC译码算法[J]. 电子与信息学报, 2021, 43(1): 51-59. doi: 10.11999/JEIT191008
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

两种降低复杂度的符号翻转多元LDPC译码算法

doi: 10.11999/JEIT191008
基金项目: 国家自然科学基金(61761006, 61961004, 61662004),广西自然科学基金(2017GXNSFAA198263, 2017GXNSFAA198276, 2018GXNSFAA138079)
详细信息
    作者简介:

    陈海强:男,1976年生,教授,研究方向为现代编码理论、协作通信

    王瑶玲:女,1997年生,硕士生,研究方向为通信与信息系统

    韦文娟:女,1996年生,硕士生,研究方向为通信与信息系统

    蒋炳旭:男,1994年生,硕士生,研究方向为通信与信息系统

    孙友明:男,1975年生,讲师,研究方向为通信与信息系统

    黎相成:男,1979年生,讲师,研究方向为通信与信息系统

    覃团发:男,1966年生,教授,研究方向为多媒体通信理论与技术

    通讯作者:

    黎相成 xcli@gxu.edu.cn

  • 中图分类号: TN911.22

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

Funds: The National Natural Science Foundation of China (61761006, 61961004, 61662004), The Natural Science Foundation of Guangxi (2017GXNSFAA198263, 2017GXNSFAA198276, 2018GXNSFAA138079)
  • 摘要: 该文提出两种低复杂度的基于符号翻转的多元低密度奇偶校验码(LDPC)译码算法:改进型多元加权译码算法(Iwtd-AlgB)和基于截断型预测机制的符号翻转(TD-SFDP)算法。Iwtd-AlgB算法利用外信息频率和距离系数的简单求和取代了迭代过程中的乘性运算操作;TD-SFDP算法结合外信息频率和翻转函数特性,对译码节点和有限域符号进行截断与划分,使得只有满足条件的节点和符号参与运算与翻转预测。仿真和数值结果显示,该文提出的两种算法在性能损失可控的前提下,可减少每次迭代的运算操作数,实现性能和复杂度之间的折中。
  • 图  1  $ {F}_{\rm{16}}(\rm{225,147})$多元准循环LDPC码译码性能

    图  2  $ {F}_{\rm{16}}(\rm{225,147})$多元准循环LDPC码平均迭代次数

    图  3  $ {F}_{\rm{16}}(\rm{255,175})$多元准循环LDPC码译码性能

    图  4  $ {F}_{\rm{16}}(\rm{255,175})$多元准循环LDPC码平均迭代次数

    表  1  Iwtd-AlgB算法

     初始化:令迭代次数$k = 0$,最大迭代次数为${I_{\max }}$,设置门限值
     $T$和汉明距离系${\theta _{d\left(z_j^{(k)},\;\sigma _{i,j}^{(k)}\right)} }$;
     译码迭代:当$k < {I_{\max }}$时,执行以下步骤
     步骤 1:计算硬判决序列${\underline {{z} } ^{(k)} } = \left(z_0^{(k)},z_1^{(k)}, ··· ,z_{n - 1}^{(k)}\right)$;
     步骤 2:计算伴随式${\underline {{s}} ^{(k)}}$,如果${\underline {{s} } ^{(k)} } = {\underline {{z} } ^{(k)} }{ {{H} }^{\rm{T} } } = \underline {{{\textit{0}}} }$,所有校
     验方程满足,退出迭代;
     步骤 3:对$0 \le j \le n - 1$和$i \in {M_j}$,统计$n\left(\sigma _{i,j}^{(k)}\right)$,计算
     $d\left(z_j^{(k)},\sigma _{i,j}^{(k)}\right)$,根据汉明距离选择确定系数${\theta _{d\left(z_j^{(k)},\sigma _{i,j}^{(k)}\right)} }$,根
     据式(5)更新得到${z^{(k + 1)}}$;
     步骤 4:执行$k \leftarrow k + 1$;
     输出:迭代译码结束,最终译码输出为
     $\;\;\;\;{\underline {{z} } ^{(k)} } = \left(z_0^{(k)},z_1^{(k)}, ··· ,z_{n - 1}^{(k)}\right)$。
    下载: 导出CSV

    表  3  译码算法每次迭代的计算复杂度比较

    算法每次迭代的运算操作数量
    IM//RMGAGMIA//RAIC//RC
    wBRB$\delta $$2\delta - m$$2\delta $$2\delta r$$\delta (2r + 1) - 3m$
    wtd-AlgB$\delta $$3\delta - m$$2\delta $$\delta $$\delta $
    Iwtd-AlgB0$3\delta - m$$2\delta $$2\delta $$\delta $
    P-SFDP0${\rm{2}}\gamma (\rho - 1)$$\gamma (2\rho {\rm{ - }}1)$$(\gamma \rho - \gamma + 1) \\ \times (\gamma r + 3\gamma + 5r + 1)$$(\gamma + r - 1) \times (\gamma \rho - \gamma + 1) \\+ 2(n - 1)$
    D-SFDP0$(\gamma \rho - \gamma + 1) \\ \times \gamma (\gamma + r) + 2\gamma (\rho - 1)$$\gamma (2\rho {\rm{ - }}1)$$(\gamma \rho - \gamma + 1) \\ \times ({\gamma ^2} + 2\gamma r + 4r + 2\gamma )$$(\gamma + r - 1) \times (\gamma \rho - \gamma + 1) \\+ 2(n - 1)$
    TD-SFDP0${n_{{T_1}}}\gamma {n_{{T_2}}} + 2\gamma (\rho - 1)$$\gamma (2\rho {\rm{ - }}1)$${n_{ {T_1} } }{n_{ {T_2} } }(r + \gamma + 1) \\ + {n_{ {T_1} } }(r{\rm{ + } }\gamma ) + n\gamma$${n_{ {T_1} } }({n_{ {T_2} } } + \gamma - 2) \\ + 2({n_{ {T_1} } } - 1)$
    备注:IM: 整数乘法;RM: 实数乘法;GA:有限域加法;GM:有限域乘法;IA:整数加法;RA:实数加法;IC:整数比较;RC:实数比较。
    下载: 导出CSV

    表  2  TD-SFDP算法

     初始化:令迭代次数$k = 0$,最大迭代次数为${I_{\max }}$,设置门限值
     ${T_1}$和${T_2}$以及汉明距离系数${\theta _{d\left(z_j^{(k)},\sigma _{i,j}^{(k)}\right)} }$;
     译码迭代:当$k < {I_{\max }}$时,执行以下步骤
     步骤 1:计算硬判决序列${\underline {{z} } ^{(k)} } = \left(z_0^{(k)},z_1^{(k)}, ··· ,z_{n - 1}^{(k)}\right)$;
     步骤 2:计算伴随式${\underline {{s}} ^{(k)}}$,如果${\underline {{s}} ^{(k)}} = {\underline {{z}} ^{(k)}}{{{H}}^{\rm{T}}} = \underline {{0}} $,所有校
     验方程满足,退出迭代;
     步骤 3:计算外信息频率$n(\sigma _{i,j}^{(k)})$,确定截断集合${{{J}}^{(k)}}$和${{S}}_j^{\left( k \right)}$,
     计算$\Delta E_j^{(k)}\left(z_j^{ * (k)},z_j^{(k)}\right)$, $\Delta E_{\max \_j}^{(k)}$, $\Delta E_{\max \_{p^{(k)}}}^{(k)}$, ${p^{(k)}}$以及
     $v_{{p^{\left( k \right)}}}^{\left( k \right)}$;
     步骤 4:执行$k \leftarrow k + 1$;
    输出:迭代译码结束,最终译码输出为
    $\;\;\;\;{\underline {{z} } ^{(k)} } = \left(z_0^{(k)},z_1^{(k)}, ··· ,z_{n - 1}^{(k)}\right)$。
    下载: 导出CSV

    表  4  ${F_{16}}(255,175)$多元LDPC码的每次迭代译码算法复杂度

    算法每次迭代的运算操作数量
    IM//RMGAGMIA//RAIC//RC
    wBRB$4080$$7905$$8160$$32640$$35955$
    wtd-AlgB$4080$$11985$$8160$$4080$$4080$
    Iwtd-AlgB$0$$11985$$8160$$8160$$4080$
    P-SFDP$0$$480$$496$$32053$$5087$
    D-SFDP$0$$77600$$496$$104112$$5087$
    TD-SFDP$0$$26880$$496$$42030$$4288$
    下载: 导出CSV
  • 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 (2q)[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
  • 加载中
图(4) / 表(4)
计量
  • 文章访问数:  1002
  • HTML全文浏览量:  451
  • PDF下载量:  74
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-12-18
  • 修回日期:  2020-11-23
  • 网络出版日期:  2020-11-26
  • 刊出日期:  2021-01-15

目录

    /

    返回文章
    返回