高级搜索

留言板

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

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

针对极化码置信度传播算法的低复杂度早期停止准则

张小军 李娜 董雁飞 崔建明 郭华

张小军, 李娜, 董雁飞, 崔建明, 郭华. 针对极化码置信度传播算法的低复杂度早期停止准则[J]. 电子与信息学报, 2021, 43(1): 77-84. doi: 10.11999/JEIT200355
引用本文: 张小军, 李娜, 董雁飞, 崔建明, 郭华. 针对极化码置信度传播算法的低复杂度早期停止准则[J]. 电子与信息学报, 2021, 43(1): 77-84. doi: 10.11999/JEIT200355
Xiaojun ZHANG, Na LI, Yanfei DONG, Jianming CUI, Hua GUO. Low-complexity Early Stopping Criterion for Belief Propagation Decoding of Polar Codes[J]. Journal of Electronics & Information Technology, 2021, 43(1): 77-84. doi: 10.11999/JEIT200355
Citation: Xiaojun ZHANG, Na LI, Yanfei DONG, Jianming CUI, Hua GUO. Low-complexity Early Stopping Criterion for Belief Propagation Decoding of Polar Codes[J]. Journal of Electronics & Information Technology, 2021, 43(1): 77-84. doi: 10.11999/JEIT200355

针对极化码置信度传播算法的低复杂度早期停止准则

doi: 10.11999/JEIT200355
基金项目: 山东省自然科学基金联合基金(ZR2019LZH001),山东省重点研发计划(2019GGX101066),山东省高等学校青创科技计划(2019KJN020, 2019KJN024),泰山学者计划
详细信息
    作者简介:

    张小军:男,1980年生,副教授,研究方向为信道编译码

    李娜:女,1996年生,硕士生,研究方向为极化码译码

    董雁飞:男,1991年生,博士生,研究方向为极化码译码

    崔建明:男,1969年生,副教授,研究方向为信道编译码

    郭华:男,1977年生,讲师,研究方向为电路设计

    通讯作者:

    张小军 zhangxiaojun@sdust.edu.cn

  • 中图分类号: TN911.22

Low-complexity Early Stopping Criterion for Belief Propagation Decoding of Polar Codes

Funds: The Joint Fund of Natural Science Foundation of Shandong Province (ZR2019LZH001), The Shandong Key Research and Development Project (2019GGX101066), The Excellent Youth Innovation Team of Shandong Province Higher Education (2019KJN020, 2019KJN024), The Taishan Scholar Program of Shandong Province
  • 摘要: 针对极化码译码延迟较高的问题, 该文提出了一种针对置信度传播算法的早期停止准则,通过监测码字估值$\hat x$的收敛性来终止译码。该准则利用高斯近似分析选取码字中Q个出错概率较小的比特构成比较空间,由于比较的位数较少,且仅采用异或和或运算,其计算复杂度较低。与基于信息序列估值$\hat u$的方案不同,提出的准则在计算$\hat u$之前已完成检测,不会导致额外的译码延迟。仿真和FPGA综合结果表明: 该准则相对于G-Matrix, 最坏信息位(WIB)和冻结位误码率(FBER)可有效节省硬件资源;当最大迭代次数设置为40次时,相比于G-Matrix准则,复杂度下降的代价是平均迭代次数在3.5 dB处上升了29.98%,相比于WIB和FBER方案,平均迭代次数分别减少39.44%和27.67%。
  • 图  1  (8, 4)极化码的因子图

    图  2  ${T_d}$, ${T_u}$${T_x}$的大小关系

    图  3  $\hat x$中符号变化和$\hat u$中错误位数

    图  4  (8, 4)极化码的Tanner图

    图  5  不同迭代终止准则的极化码译码性能比较

    图  6  不同迭代终止准则的平均迭代次数比较

    图  7  X-tolerance的硬件结构

    图  8  采用X-tolerance的BP译码流程

    算法1 (N, K) X-tolerance BP译码器
     (1) 输入:
     (2) 信道输出:${\rm{ LLR}}\left( { {r_i} } \right)$
     (3) 冻结位集合:$ A^C$
     (4) 比较空间:S
     (5) 初始化:
     (6) 设定$ {I_{\max }}$和X
     (7) For 每个节点的传播信息$ L_{i,j}^t$和$ R_{i,j}^t$
     (8)  if $ (j = = 1)$ & $ \left( {i \in {A^C}} \right)$ $ R_{i,1}^t = \infty $对于t=0, 1,···, Imax
     (9)  else if $ (j = = 1 + n)$ $L_{i,n + 1}^t = {\rm{LLR}}\left( { {r_i} } \right)$对于t=0, 1,···,
         Imax x
     (10)  else $ L_{i,j}^0 = R_{i,j}^0 = 0$
     (11) 迭代过程:
     (12) While $ t < {I_{\max }}$ do
     (13) 根据(1)更新每个节点的$ L_{i,j}^t$ and $ R_{i,j}^t$
     (14) 更新 $ \hat x_1^N$
     (15)  if $ R_{i,n + 1}^t > 0$ then $ {{\hat x}_i} = 0$
     (16)  else $ {{\hat x}_i} = 1$
     (17) end while
     (18) 提前停止准则:
     (19)  if (17) 成立 then
     (20) 迭代终止
     (21)  else $ t=t+1$
     (22) 输出:$ \hat u_1^N = \left( {{{\hat u}_1},{{\hat u}_2}, ··· ,{{\hat u}_N}} \right)$
    下载: 导出CSV

    表  1  早期停止准则的计算复杂度比较

    停止准则G-MatrixWIBFBERX-tolerance
    Q=N/8Q=N/16
    加法运算2NM+2N/8M+N/16
    比较运算3N1
    异或(XOR)NlogNN/8N/16N/8N/16
    或(OR)X+N/8X+N/16
    下载: 导出CSV

    表  2  不同早期停止准则的综合结果

    停止准则G-MatrixWIBFBERX-tolerance
    Q=128 X=2Q=64 X=3
    ALMs30265182012605027
    Registers307333021013168
    下载: 导出CSV
  • https://www.oulu.fi/university/news/6g-white-paper, 2019.
    ARIKAN E. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[J]. IEEE Transactions on Information Theory, 2009, 55(7): 3051–3071. doi: 10.1109/TIT.2009.2021379
    刘建航, 何怡静, 李世宝, 等. 基于预译码的极化码最大似然简化连续消除译码算法[J]. 电子与信息学报, 2019, 41(4): 959–966. doi: 10.11999/JEIT180324

    LIU Jianhang, HE Jingyi, LI Shibao, et al. Pre-decoding based maximum-likelihood simplified successive-cancellation decoding of polar codes[J]. Journal of Electronics &Information Technology, 2019, 41(4): 959–966. doi: 10.11999/JEIT180324
    郭锐, 王美洁, 王杰. 基于缩短极化码的MLC NAND Flash差错控制技术研究[J]. 电子与信息学报, 2017, 39(7): 1658–1665. doi: 10.11999/JEIT160864

    GUO Rui, WANG Meijie, and WANG Jie. Research on the MLC Nand flash error control technology based on polar codes[J]. Journal of Electronics &Information Technology, 2017, 39(7): 1658–1665. doi: 10.11999/JEIT160864
    LAY K T and CHANG C H. Enhanced successive cancellation for decoding of polar codes with very low latency through multiple parity checks[C]. The 4th International Conference on Intelligent Green Building and Smart Grid, Yichang, China, 2019: 366–370. doi: 10.1109/IGBSG.2019.8886186.
    YUAN Bo and PARHI K K. Early stopping criteria for energy-efficient low-latency belief-propagation polar code decoders[J]. IEEE Transactions on Signal Processing, 2014, 62(24): 6496–6506. doi: 10.1109/tsp.2014.2366712
    YAN Yongli, ZHANG Xuanxuan, and WU Bin. Simplified early stopping criterion for belief-propagation polar code decoder based on frozen bits[J]. IEEE Access, 2019, 7: 134691–134696. doi: 10.1109/ACCESS.2019.2940135
    CHOI S and YOO H. Area-efficient early-termination technique for belief-propagation polar decoders[J]. Electronics, 2019, 8(9): 1001. doi: 10.3390/electronics8091001
    REN Yuanrui, ZHANG Chuan, LIU Xing, et al. Efficient early termination schemes for belief-propagation decoding of polar codes[C]. The 11th IEEE International Conference on ASIC, Chengdu, China, 2015: 1–4. doi: 10.1109/ASICON.2015.7517046.
    SIMSEK C and TURK K. Simplified early stopping criterion for belief-propagation polar code decoders[J]. IEEE Communications Letters, 2016, 20(8): 1515–1518. doi: 10.1109/LCOMM.2016.2580514
    SIMSEK C and TURK K. Hardware optimization for belief propagation polar code decoder with early stopping criteria using high-speed parallel-prefix ling adder[C]. The 40th International Conference on Telecommunications and Signal Processing, Barcelona, Spain, 2017: 182–185. doi: 10.1109/TSP.2017.8075964.
    ALBAYRAK C, SIMSEK C, and TURK K. Low-complexity early termination method for rateless soft decoder[J]. IEEE Communications Letters, 2017, 21(11): 2356–2359. doi: 10.1109/LCOMM.2017.2740207
    ZHANG Qingshuang, LIU Aijun, and TONG Xinhai. Early stopping criterion for belief propagation polar decoder based on frozen bits[J]. Electronics Letters, 2017, 53(24): 1576–1578. doi: 10.1049/el.2017.3316
    GIARD P, BALATSOUKAS-STIMMING A, and BURG A. On the tradeoff between accuracy and complexity in blind detection of polar codes[C]. The 10th IEEE International Symposium on Turbo Codes & Iterative Information Processing, Hongkong, China, 2018: 1–5. doi: 10.1109/ISTC.2018.8625366.
    CHUNG S Y, RICHARDSON T J, and URBANKE R L. Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation[J]. IEEE Transactions on Information Theory, 2001, 47(2): 657–670. doi: 10.1109/18.910580
    梁昌洪, 李龙, 史小卫. 标准正态分布的简洁闭式[J]. 西安电子科技大学学报: 自然科学版, 2003, 30(3): 289–292. doi: 10.3969/j.issn.1001-2400.2003.03.001

    LIANG Changhong, LI Long, and SHI Xiaowei. A compact closed form of standard normal distribution[J]. Journal of Xidian University, 2003, 30(3): 289–292. doi: 10.3969/j.issn.1001-2400.2003.03.001
  • 加载中
图(8) / 表(3)
计量
  • 文章访问数:  893
  • HTML全文浏览量:  265
  • PDF下载量:  56
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-05-08
  • 修回日期:  2020-10-01
  • 网络出版日期:  2020-10-13
  • 刊出日期:  2021-01-15

目录

    /

    返回文章
    返回