高级搜索

基于预译码的极化码最大似然简化连续消除译码算法

刘建航 何怡静 李世宝 卢丽金 邓云强

引用本文: 刘建航, 何怡静, 李世宝, 卢丽金, 邓云强. 基于预译码的极化码最大似然简化连续消除译码算法[J]. 电子与信息学报, 2019, 41(4): 959-966. doi: 10.11999/JEIT180324 shu
Citation:  Jianhang LIU, Yijing HE, Shibao LI, Lijin LU, Yunqiang DENG. Pre-decoding Based Maximum-likelihood Simplified Successive-cancellation Decoding of Polar Codes[J]. Journal of Electronics and Information Technology, 2019, 41(4): 959-966. doi: 10.11999/JEIT180324 shu

基于预译码的极化码最大似然简化连续消除译码算法

    作者简介: 刘建航: 男,1978年生,副教授、博士,研究方向为信道编码,移动互联网;
    何怡静: 女,1994年生,硕士生,研究方向为信道编码;
    李世宝: 男,1978年生,副教授,研究方向为移动计算;
    卢丽金: 女,1992年生,硕士生,研究方向为信道编码;
    邓云强: 男,1993年生,硕士生,研究方向为信道编码
    通讯作者: 刘建航,liujianhang@upc.edu.cn
  • 基金项目: 国家自然科学基金青年基金(61601519, 61872385),中央高校基本科研业务费专项资金(18CX02134A, 18CX02137A, 18CX02133A)

摘要: 针对极化码译码串行输出造成较大译码时延的问题,该文提出一种基于预译码的最大似然简化连续消除译码算法。首先对译码树节点存储的似然值进行符号提取并分组处理,得到符号向量组;然后比较符号向量组与该节点的某些信息位的取值情况,发现向量组中储存的正负符号分布规律与该节点的中间信息位的取值具有一一对应的关系;在此基础上对组合码中间的1~2 bit进行预译码;最后结合最大似然译码方法估计组合码中的剩余信息位,从而得到最终的译码结果。仿真结果表明:在不影响误码性能的情况下,所提算法与已有的算法相比可有效降低译码时延。

English

    1. [1]

      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–3073 doi: 10.1109/TIT.2009.2021379

    2. [2]

      İŞCAN O, BÖHNKE R, and XU Wen. Shaped polar codes for higher order modulation[J]. IEEE Communications Letters, 2018, 22(2): 252–255 doi: 10.1109/LCOMM.2017.2766621

    3. [3]

      郭锐, 王美洁, 王杰. 基于缩短极化码的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

    4. [4]

      GULCU T C and BARG A. Achieving secrecy capacity of the wiretap channel and broadcast channel with a confidential component[J]. IEEE Transactions on Information Theory, 2017, 63(2): 1311–1324 doi: 10.1109/TIT.2016.2631223

    5. [5]

      朱鸿斌, 戴胜辰, 康凯, 等. 改进型极化码混合自动请求重传法[J]. 电子与信息学报, 2017, 39(5): 1136–1141 doi: 10.11999/JEIT160736
      ZHU Hongbin, DAI Shengchen, KANG Kai, et al. An improved HARQ scheme with polar codes[J]. Journal of Electronics &Information Technology, 2017, 39(5): 1136–1141 doi: 10.11999/JEIT160736

    6. [6]

      LEROUX C, RAYMOND A J, SARKIS G, et al. A semi-parallel successive-cancellation decoder for polar codes[J]. IEEE Transactions on Signal Processing, 2013, 61(2): 289–299 doi: 10.1109/TSP.2012.2223693

    7. [7]

      HUSMANN C, NIKOLAOU P C, and NIKITOPOULOS K. Reduced latency ML polar decoding via multiple sphere-decoding tree searches[J]. IEEE Transactions on Vehicular Technology, 2018, 67(2): 1835–1839 doi: 10.1109/TVT.2017.2761262

    8. [8]

      HASHEMI S A, CONDO C, and GROSS W J. A fast polar code list decoder architecture based on sphere decoding[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2016, 63(12): 2368–2380 doi: 10.1109/TCSI.2016.2619324

    9. [9]

      ALAMDA-YAZDI A and KSCHISCHANG F R. A simplified successive-cancellation decoder for polar codes[J]. IEEE Communications Letters, 2011, 15(12): 1378–1380 doi: 10.1109/LCOMM.2011.101811.111480

    10. [10]

      SARKIS G, GIARD P, VARDY A, et al. Fast polar decoders: algorithm and implementation[J]. IEEE Journal on Selected Areas in Communications, 2014, 32(5): 946–957 doi: 10.1109/JSAC.2014.140514

    11. [11]

      HANIF M and ARDAKANI M. Fast successive-cancellation decoding of polar codes: identification and decoding of new nodes[J]. IEEE Communications Letters, 2017, 21(11): 2360–2363 doi: 10.1109/LCOMM.2017.2740305

    12. [12]

      HUANG Zhiliang, DIAO Chunjuan, DAI Jianxin, et al. An improvement of modified successive-cancellation decoder for polar codes[J]. IEEE Communications Letters, 2013, 17(12): 2360–2363 doi: 10.1109/LCOMM.2013.110413.132136

    13. [13]

      CHOI J and PARK I C. Improved successive-cancellation decoding of polar codes based on recursive syndrome decomposition[J]. IEEE Communications Letters, 2017, 21(11): 2344–2347 doi: 10.1109/LCOMM.2017.2730860

    14. [14]

      YOO H and PARK I C. Efficient pruning for successive-cancellation decoding of polar codes[J]. IEEE Communications Letters, 2016, 20(12): 2362–2365 doi: 10.1109/LCOMM.2016.2607167

    15. [15]

      SARKIS G and GROSS W J. Increasing the throughput of polar decoders[J]. IEEE Communications Letters, 2013, 17(4): 725–728 doi: 10.1109/LCOMM.2013.021213.121633

    16. [16]

      CHASE D. Class of algorithms for decoding block codes with channel measurement information[J]. IEEE Transactions on Information Theory, 1972, 18(1): 170–182 doi: 10.1109/TIT.1972.1054746

    1. [1]

      王晓涛, 钱骅, 康凯. 基于Viterbi-双向搜索的咬尾码最大似然译码算法. 电子与信息学报, 2013, 35(5): 1017-1022.

    2. [2]

      王琼, 罗亚洁, 李思舫. 基于分段循环冗余校验的极化码自适应连续取消列表译码算法. 电子与信息学报, 2019, 41(7): 1572-1578.

    3. [3]

      王晓涛, 刘振华. 基于可信位置排序的咬尾卷积码译码算法. 电子与信息学报, 2015, 37(7): 1575-1579.

    4. [4]

      曹阳, 张晗, 涂巧玲, 李小红, 彭小峰. 基于分段凿孔的极化码级联方案. 电子与信息学报, 2018, 40(8): 1941-1948.

    5. [5]

      郭锐, 王美洁, 王杰. 基于缩短极化码的MLC NAND Flash差错控制技术研究. 电子与信息学报, 2017, 39(7): 1658-1665.

    6. [6]

      朱鸿斌, 戴胜辰, 康凯, 钱骅. 改进型极化码混合自动请求重传法. 电子与信息学报, 2017, 39(5): 1136-1141.

    7. [7]

      易鸣, 季新生, 黄开枝, 金梁, 王婧. 面向物理层安全的一种打孔极化编码方法. 电子与信息学报, 2014, 36(12): 2835-2841.

    8. [8]

      吕卓, 李建东, 李维英. 空时网格码的联合迭代最大似然估计和译码. 电子与信息学报, 2006, 28(8): 1350-1353.

    9. [9]

      武岩波, 朱敏. 一种用于水声通信的喷泉码最大似然译码方法. 电子与信息学报, 2016, 38(2): 288-293.

    10. [10]

      袁航剑, 洪一帆, 罗武, 蒋伟. 一种码片内多径参数的最大似然估计算法. 电子与信息学报, 2012, 34(10): 2326-2330.

    11. [11]

      曹敏, 尹虹, 王国栋, 李际平. 基于SCCC结构非相干MAP译码的简化算法. 电子与信息学报, 2010, 32(10): 2526-2530.

    12. [12]

      张忠培, 周亮. 一种Turbo码译码的矩阵算法. 电子与信息学报, 2002, 24(2): 266-271.

    13. [13]

      张玉良, 陈晓敏. [256,252]RS扩展码的快速译码算法. 电子与信息学报, 2005, 27(12): 1947-1951.

    14. [14]

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

    15. [15]

      刘东华, 唐朝京. 用于Turbo迭代译码的log-MAP算法的简化. 电子与信息学报, 2001, 23(12): 1340-1347.

    16. [16]

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

    17. [17]

      任品毅, 令洁, 汪瑞. V-BLAST系统中一种基于噪声分析的简化最大似然检测算法. 电子与信息学报, 2010, 32(3): 539-543.

    18. [18]

      解辉, 王丰华, 黄知涛. 基于最大似然检测的(n,1,m)卷积码盲识别方法. 电子与信息学报, 2013, 35(7): 1671-1676.

    19. [19]

      马建峰, 王育民. 分组码的格图结构和译码. 电子与信息学报, 1997, 19(2): 209-213.

    20. [20]

      任剑, 肖国镇. 基于FIA的代数几何码的译码. 电子与信息学报, 1995, 17(5): 492-499.

  • 图 1  SC及SSC译码算法对应的译码树

    图 2  L-REP节点预译码设计

    图 3  PDM-SSC译码框架

    图 4  L-REP节点和L-BiREP节点结构

    图 5  SSC, ML-SSC与PDM-SSC译码算法的误码率和误帧率

    表 1  ${u_{{\rm{mid}}1}}$${u_{{\rm{mid}}0}}$对应${{x}}_{vi}^0$${{x}}_{vi}^1$的取值情况

    ${u_{{\rm{mid}}1}}$${u_{{\rm{mid}}0}}$${{x}}_{vi}^0$${{x}}_{vi}^1$
    00$\left[ {\begin{array}{*{20}{c}} 1&1 \end{array}} \right]$/$\left[ {\begin{array}{*{20}{c}} 0&0 \end{array}} \right]$$\left[ {\begin{array}{*{20}{c}} 1&1 \end{array}} \right]$/$\left[ {\begin{array}{*{20}{c}} 0&0 \end{array}} \right]$
    01$\left[ {\begin{array}{*{20}{c}} 0&1 \end{array}} \right]$/$\left[ {\begin{array}{*{20}{c}} 1&0 \end{array}} \right]$$\left[ {\begin{array}{*{20}{c}} 0&1 \end{array}} \right]$/$\left[ {\begin{array}{*{20}{c}} 1&0 \end{array}} \right]$
    10$\left[ {\begin{array}{*{20}{c}} 0&1 \end{array}} \right]$/$\left[ {\begin{array}{*{20}{c}} 1&0 \end{array}} \right]$$\left[ {\begin{array}{*{20}{c}} 1&1 \end{array}} \right]$/$\left[ {\begin{array}{*{20}{c}} 0&0 \end{array}} \right]$
    11$\left[ {\begin{array}{*{20}{c}} 1&1 \end{array}} \right]$/$\left[ {\begin{array}{*{20}{c}} 0&0 \end{array}} \right]$$\left[ {\begin{array}{*{20}{c}} 0&1 \end{array}} \right]$/$\left[ {\begin{array}{*{20}{c}} 1&0 \end{array}} \right]$
    下载: 导出CSV

    表 2  P个计算单元下L-REP节点和L-BiREP节点的译码时延

    算法L-REP节点的译码时延L-BiREP节点的译码时延
    SSC$ \ge {\log _2}{N_v} + {\tau _r} + 2$$ \ge {\log _2}{N_v} + {\tau _r} + 1$
    ML-SSC$\left( {{2^{{k_v} + 1}} + 1} \right)\left( {{N_v} - 1} \right)/P$$\left( {{2^{{k_v} + 2}} + 1} \right)\left( {{N_v} - 1} \right)/P$
    PDM-SSC$\left( {\left( {{2^{{k_v}}} + 1} \right)\left( {{N_v} - 1} \right) + 1} \right)/P$$\left( {\left( {{2^{{k_v}}} + 1} \right)\left( {{N_v} - 1} \right) + 1} \right)/P$
    下载: 导出CSV

    表 3  P=256, R=0.5时,本文算法与SSC算法时延情况对比

    算法码长时延(时间周期)时延增益(%)
    SSC2048817
    327686973
    PDM-SSC204860625.8
    32768573117.8
    下载: 导出CSV

    表 4  P=256, N=32768时,本文算法与ML-SSC算法时延情况对比

    算法码率译码节点个数时延(时间周期)时延增益(%)
    ML-SSC0.5696679
    0.9603470
    PDM-SSC0.5148573114.2
    0.9114282218.7
    下载: 导出CSV
  • 加载中
图(5)表(4)
计量
  • PDF下载量:  19
  • 文章访问数:  335
  • HTML全文浏览量:  130
文章相关
  • 通讯作者:  刘建航, liujianhang@upc.edu.cn
  • 收稿日期:  2018-04-11
  • 录用日期:  2019-01-17
  • 网络出版日期:  2019-01-30
  • 刊出日期:  2019-04-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章