计算机科学 ›› 2019, Vol. 46 ›› Issue (11): 328-333.doi: 10.11896/jsjkx.181001871

• 交叉与前沿 • 上一篇    下一篇

基于查找表的ADMM译码算法中量化算法优化研究

刘华军1, 唐诗迪1, 张迪科2, 夏巧桥1   

  1. (华中师范大学物理科学与技术学院 武汉430079)1
    (武汉大学电子信息学院 武汉430072)2
  • 收稿日期:2018-10-09 出版日期:2019-11-15 发布日期:2019-11-14
  • 通讯作者: 夏巧桥(1987-),男,博士,讲师,主要研究方向为高速实时数据处理平台、LDPC等,E-mail:xqq2947759@163.com
  • 作者简介:刘华军(1994-),男,硕士,主要研究方向为高速实时数据处理平台、LDPC等;唐诗迪(1997-),男,主要研究方向为LDPC码的译码;张迪科(1994-),男,硕士,主要研究方向为信道编解码。
  • 基金资助:
    本文受国家自然科学基金项目(61501334),华中师范大学中央高校基本科研业务费(CCNU16A05028)资助。

Study on Optimization of Quantization Algorithm in ADMM Decoding Algorithm Based on Lookup Table

LIU Hua-jun1, TANG Shi-di1, ZHANG Di-ke2, XIA Qiao-qiao1   

  1. (School of Physical Science and Technology,Central China Normal University,Wuhan 430079,China)1
    (School of Electronic Information,Wuhan University,Wuhan 430072,China)2
  • Received:2018-10-09 Online:2019-11-15 Published:2019-11-14

摘要: 在基于ADMM的线性规划译码中,待投影向量向校验多胞体进行欧几里得投影计算是最复杂和耗时的部分。基于查找表的ADMM-LDPC译码算法通过简单的查表操作来替代复杂的投影运算,简化了投影过程,提升了算法的效率,但消耗了大量的内存资源。之后研究者提出了非均匀量化方法,该方法虽然极大地减少了内存消耗,但是所采用的量化方案的计算复杂度较高,从而使得该方法在量化段数较多的条件下难以实现。针对该问题,文中提出了一种新的非均匀量化方法。首先,针对不同的码字,在不同信噪比条件下,通过实验统计待投影向量中元素的分布特性,探究其分布规律,并设计相应的函数作为量化映射关系;然后,采用差分进化算法对函数的参数进行优化,从而得出在该函数下的最优量化方案,最终确定量化函数。仿真实验表明:与已有的量化方法相比,文中设计的非均匀量化方法具有不受量化段数、精度等因素影响的优点;且针对不同的码字,所提方法在高信噪比下均能达到0.05dB左右的性能增益。

关键词: ADMM惩罚译码, LDPC码, 查找表, 非均匀量化

Abstract: In the linear programming decoding based on ADMM,the Euclidean projection calculation of the projection vector to the check multi-cellular body is the most complex and time-consuming part.The ADMM-LDPC decoding algorithm based on look-up tables replace the time complexity of algorithm with simple table look-up operations to simplify the projection process and improve the efficiency of the algorithm,however it expends much memory consumption.La-ter,the researchers proposed the nonuniform quantization method,which can decrease the memory consumption effectively,but the computation complexity of the quantitative method is too high,so that the way is difficult to achieve when the number of segments is too much.For this problem,this paper proposed a new nonuniform quantization method.Firstly,for different code-words,the distribution characteristics of elements in the vector are calculated to be projected under different SNRs conditions by experiment,its distribution rules are explored and the corresponding function is designed as the quantitative mapping relation.Then,differential evolution algorithm is used to optimize the parameters of the function,the optimal quantization schema under the function is obtained,and the quantization function is finally determined.The simulation results show that,compared with the existing quantitative methods,the nonuniform method proposed in this paper has the advantage of not being affected by the number of quantization segment,precision and otherfactors.What’s more,it achieves about 0.05dB performance improvement for different code words in high SNRs.

Key words: LDPC codes, Look-up tables, Nonuniform quantization, Penalized ADMM decoder

中图分类号: 

  • TN911.22
[1]FELDMAN J.Decoding error-correcting codes via linear programming[D].Cambridge:MassachusettsInstitute of Technology,2003.
[2]FELDMAN J,WAINWRIGHT M J,KARGER D R.Using linearprogramming to decode binary linear codes[J].IEEE Transa-ctions on Information Theory,2005,51(3):954-972.
[3]BURSHTEIN D,GOLDENBERG I.Improved linear programming decoding of LDPC codes and bounds on the minimum and fractional distance[J].IEEE Transactions on Information Theory,2011,57(11):7386-7402.
[4]FELDMAN J,MALKIN T,SERVEDIO R A,et al.LP decoding corrects a constant fraction of errors[J].IEEE Transactions on Information Theory,2007,53(1):82-89.
[5]BARMAN S,LIU X S,DRAPER S C,et al.Decompositionmethods for large scale LP decoding[J].IEEE Transactions on Information Theory,2013,59(12):7870-7886.
[6]JIAO X P,WEI H Y,MU J J.Improved ADMM penalized decoder for irregular low-density parity-check codes[J].IEEE Communication Letters,2015,19(6):913-916.
[7]LIU X S,DRAPER S C.The ADMM Penalized Decoder for LDPC Codes[J].IEEE Transactions on Information Theory,2016,62(6):2966-2984.
[8]WANG B,MU J J,JIAO X P,et al.Improved Penalty Functions of ADMM Decoder for LDPC Codes[J].IEEE Communication Letters,2016,21(99):234-237.
[9]ZHANG X,SIEGEL P H.Efficient iterative LP decoding of LDPC codes with alternating direction method of multipliers[C]∥IEEE International Symposium on Information Theory.IEEE,2013:1501-1505.
[10]WEI H,BANIHASHEMI A H.An Iterative Check PolytopeProjection Algorithm for ADMM-Based LP Decoding of LDPC Codes[J].IEEE Communications Letters,2017,PP(99):1-1.
[11]ZHANG G,HEUSDENS R,KLEIJN W.Large scale LP decoding with low complexity[J].IEEE Communications Letters,2013,17(11):2152-2155.
[12]WASSON M,DRAPER S C.Hardware based projection ontothe parity polytope and probability simplex[C]∥Asilomar Conference on Signals,Systems and Computers.IEEE,2015:1015-1020.
[13]WEI H Y,JIAO X P,MU J J.Reduced-complexity linear programming decoding based on ADMM for LDPC codes[J].IEEE Communication Letters,2015,19(6):909-912.
[14]JIAO X P,MU J J,HE Y C,et al.Efficient ADMM Decoding of LDPC Codes Using Look-Up Tables[J].IEEE Transactions on Communications,2017,19(4):271-285.
[15]JIAO X,HE Y C,MU J,et al.Memory-Reduced Lookup Tables for Efficient ADMM Decoding of LDPC Codes[J].IEEE Signal Processing Letters,2018,25(99):1-1.
[16]DEBBABI I,GAL B L,KHOUJA N,et al.Fast ConvergingADMM Penalized Algorithm for LDPC Decoding[J].IEEE Communication Letters,2016,20(4):648-651.
[17]DEBBABI I,GAL B L,KHOUJA N,et al.Comparison of different schedulings for the ADMM based LDPC decoding[C]∥ International Symposium on Turbo Codes & Iterative Information Processing.IEEE,2016:51-55.
[18]STORN R,PRICE K.Differential Evolution-A Simple and Efficient Heuristic for global Optimization over Continuous Spaces[J].Journal of Global Optimization,1997,11(4):341-359.
[1] 王登天, 周华, 钱荷玥.
LDPC自适应最小和译码算法及其FPGA实现
LDPC Adaptive Minimum Sum Decoding Algorithm and Its FPGA Implementation
计算机科学, 2021, 48(6A): 608-612. https://doi.org/10.11896/jsjkx.200800134
[2] 杨雪菲, 郑东, 任方.
一种基于QC-LDPC码的数字签名算法
Digital Signature Algorithm Based on QC-LDPC Code
计算机科学, 2019, 46(6): 162-167. https://doi.org/10.11896/j.issn.1002-137X.2019.06.024
[3] 孟嘉慧, 赵旦峰, 田海.
面向5G的多元LDPC改进译码算法的仿真研究
Simulation Research on Improved Decoding Algorithm Based on Non-binary LDPC for 5G
计算机科学, 2018, 45(9): 141-145. https://doi.org/10.11896/j.issn.1002-137X.2018.09.022
[4] 张双悦, 李硕, 王红, 杨士元.
FPGA芯片的链结构LUT自测试方法研究
Study on Chain-based BIST Architecture of LUTs in FPGA
计算机科学, 2014, 41(5): 37-40. https://doi.org/10.11896/j.issn.1002-137X.2014.05.008
[5] 牛和昊,何元智.
有限长度LDPC码一种速率兼容删余算法
Rate-compatible Puncturing Algorithm for Finite-length LDPC Codes
计算机科学, 2013, 40(Z11): 29-31.
[6] 崔浩然,王 栋,陈 戈.
基于图像配准的光学触控系统触点校正
Contacts Calibration of Optical Touch System Based on Image Registration
计算机科学, 2012, 39(Z11): 369-371.
[7] 谢斐,蔡山,王德鑫,陈超.
四路摄像头协同多重触控系统标定方法
Calibration Methods for the Multi-touch System Based on Four Collaborative Cameras
计算机科学, 2011, 38(9): 253-256.
[8] 易轶虎,曲道奎,徐方.
基于参数查找表的肤色检测算法
Algorithm of Skin-tone Detection Based on Parameter Look-up Table
计算机科学, 2010, 37(3): 262-264.
[9] 孙蓉 刘景伟 王新梅.
基于流星余迹通信系统的低密度校验码的分析设计

计算机科学, 2008, 35(4): 78-81.
[10] .
二次同余序列构造规则LDPC码

计算机科学, 2006, 33(6): 291-292.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!