高级搜索

留言板

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

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

低秩循环矩阵的构造方法及其关联的多元LDPC码

徐恒舟 朱海 冯丹 张博 周慢杰

徐恒舟, 朱海, 冯丹, 张博, 周慢杰. 低秩循环矩阵的构造方法及其关联的多元LDPC码[J]. 电子与信息学报. doi: 10.11999/JEIT200351
引用本文: 徐恒舟, 朱海, 冯丹, 张博, 周慢杰. 低秩循环矩阵的构造方法及其关联的多元LDPC码[J]. 电子与信息学报. doi: 10.11999/JEIT200351
Hengzhou XU, Hai ZHU, Dan FENG, Bo ZHANG, Manjie ZHOU. Construction of Low-rank Circulant Matrices and Their Associated Nonbinary LDPC Codes[J]. Journal of Electronics and Information Technology. doi: 10.11999/JEIT200351
Citation: Hengzhou XU, Hai ZHU, Dan FENG, Bo ZHANG, Manjie ZHOU. Construction of Low-rank Circulant Matrices and Their Associated Nonbinary LDPC Codes[J]. Journal of Electronics and Information Technology. doi: 10.11999/JEIT200351

低秩循环矩阵的构造方法及其关联的多元LDPC码

doi: 10.11999/JEIT200351
基金项目: 国家自然科学基金(61801527),河南省高等学校青年骨干教师培养计划(2018GGJS137),河南省高等学校重点科研项目(20A510017),河南省自然科学基金项目(202300410523),陕西省高校科协青年人才托举计划项目(20200116),陕西省教育厅科研计划项目资助(20JK0918)
详细信息
    作者简介:

    徐恒舟:男,1987年生,讲师,主要研究方向为组合设计与编码理论、信息论等

    朱海:男,1978年生,教授,主要研究方向为信道编码、云计算、无线网络技术等

    冯丹:女,1989年生,讲师,主要研究方向为编码调制、MIMO等

    张博:男,1982年生,副教授,主要研究方向为信息论、信道编码等

    周慢杰:女,1985年生,助教,主要研究方向为LDPC编码理论及信息教育技术等

    通讯作者:

    朱海 zhu_sea@163.com

  • 中图分类号: TN911.22

Construction of Low-rank Circulant Matrices and Their Associated Nonbinary LDPC Codes

Funds: The National Natural Science Foundation of China (61801527), The Training Program for Young Core Instructor of Henan Universities (2018GGJS137), The Key Scientific Research Projects of Henan Educational Committee (20A510017), The Natural Science Foundation of Henan (202300410523), The Project of Youth Talent Lift Program of Shaanxi Association for Science and Technology (20200116), The Scientific Research Program Funded by Shaanxi Provincial Education Department (20JK0918)
  • 摘要: 在图像处理中,低秩矩阵的冗余信息可用于图像恢复和图像特征提取,而在迭代译码中,校验矩阵的冗余行可以加快译码收敛速度。该文研究一类易于硬件实现的低秩循环矩阵。首先将循环矩阵转换为位置集合,并基于同构理论简化了位置集合的搜索空间,从而基于比特移位方法提出了循环矩阵的构造方法。考虑非零域元素的列赋值与矩阵秩之间的关系,选取Tanner图中没有长度为4的环的循环矩阵,基于非零域元素的列赋值思想提出了不同阶数、不同码率的多元LDPC码构造方法。数值仿真结果表明,与基于PEG算法构造的二元LDPC码比较,所构造的多元LDPC码在BPSK调制方式下在误码字率10–5附近有0.9 dB的增益;在与高阶调制相结合时,有更大的性能提升。此外,所构造的多元LDPC码在迭代5次与50次下的性能几乎一致,这为低时延高可靠通信提供了一种有效的候选编码方案。
  • 图  1  循环矩阵C中的4-环结构

    图  2  GF(64)上的(31, 15)LDPC码和基于PEG算法构造的二元(186, 90)LDPC码在不同迭代次数下的误码字率性能比较

    图  3  GF(64)上的(31, 15)LDPC码和基于PEG算法构造的二元(186, 90)LDPC码在高阶调制下的误码字率性能比较

    图  4  GF(4), GF(32)和GF(128)上的(31, 15)LDPC码在迭代5次和50次下的误码字率性能

    表  1  算法1:秩小于R的循环矩阵搜索算法

     输入:阈值R,循环矩阵的行(或列)数L,行(或列)重m
     输出:位置集合S及其秩。
     (1) repeat
     (2) 基于比特移位方法按照组合顺序产生位置集合$S = \left\{ {{s_1}\left( { = 0} \right),{s_2},{s_3}, ··· ,{s_m}} \right\}$,其中对于$1 < l \le m$,${s_{l - 1}} < {s_l}$和$0 < {s_l} < L$;
     (3) 根据位置集合S生成大小为$L \times L$的二元循环矩阵C
     (4) 计算循环矩阵C的秩r
     (5) 如果r小于R,存储位置集合S,并记录它的秩为r,并打印输出集合S和秩r(注意,如果多个位置集合的秩相同,则只存储第1个位置集
       合,其他不再存储);
     (6) until (全部找到秩从1到R的位置集合,或${s_m} - {s_1} = m - 2$)
    下载: 导出CSV

    表  2  基于算法1搜索的部分循环矩阵

    行/列数行/列重位置集合行/列数行/列重位置集合
    933{0, 3, 6}30410{0, 5, 15, 20}
    1234{0, 4, 8}3248{0, 8, 16, 24}
    1535{0, 5, 10}3649{0, 9, 18, 27}
    1836{0, 6, 12}40410{0, 10, 20, 30}
    2137{0, 7, 14}42414{0, 7, 21, 28}
    2438{0, 8, 16}44411{0, 11, 22, 33}
    2739{0, 9, 18}48412{0, 12, 24, 36}
    30310{0, 10, 20}2555{0, 5, 10, 15, 20}
    33311{0, 11, 22}3056{0, 6, 12, 18, 24}
    39313{0, 13, 26}3557{0, 7, 14, 21, 28}
    42314{0, 14, 28}4058{0, 8, 16, 24, 32}
    45315{0, 15, 30}4559{0, 9, 18, 27, 36}
    48316{0, 16, 32}50510{0, 10, 20, 30, 40}
    842{0, 2, 4, 6}39612{0, 1, 13, 14, 26, 27}
    1243{0, 3, 6, 9}4267{0, 7, 14, 21, 28, 35}
    1644{0, 4, 8, 12}42612{0, 2, 14, 16, 28, 30}
    1846{0, 3, 9, 12}45610{0, 5, 15, 20, 30, 35}
    2045{0, 5, 10, 15}45612{0, 3, 15, 18, 30, 33}
    2446{0, 6, 12, 18}4868{0, 8, 16, 24, 32, 40}
    2747{0, 7, 14, 21}48612{0, 4, 16, 20, 32, 36}
    下载: 导出CSV

    表  3  算法2:检验循环矩阵C中是否存在4-环的算法

     输入:循环矩阵C的位置集合$S = \left\{ {{s_1},{s_2}, ··· ,{s_m}} \right\}$,循环矩阵的行(或列)数L
     输出:是否存在4-环。
     (1) 根据位置集合$S = \left\{ {{s_1},{s_2}, ··· ,{s_m}} \right\}$得到差集$D = \left\{ {d \in {Z_L}|d = {s_i} - {s_j}\left( {{\rm{mod}} \; L} \right),1 \le i \le m,1 \le j \le m,i \ne j} \right\}$;
     (2) 计算差集D中元素的个数,或者检查集合$E = \left\{ {e|e = {d_i} + {d_j}\left( {{\rm{mod}} \; L} \right),i \ne j,{d_i} \in D,{d_j} \in D,} \right\}$中是否有零元素;
     (3) 如果差集D中元素的个数小于$C_m^2$,或者集合E中有零元素,直接输出“存在4-环”;否则,输出“不存在4-环”。
    下载: 导出CSV

    表  4  不包含4-环的循环矩阵位置集合

    行/列数行/列重位置集合行/列数行/列重位置集合
    734{0, 1, 3}39527{0, 1, 5, 8, 25}
    1438{0, 2, 6}42520{0, 2, 8, 28, 32}
    21312{0, 3, 9}45535{0, 1, 3, 10, 15}
    49328{0, 7, 21}63530{0, 3, 12, 42, 48}
    56332{0, 8, 24}93548{0, 3, 9, 21, 45}
    60344{0, 4, 16}45628{0, 1, 3, 12, 19, 40}
    63336{0, 9, 27}48639{0, 1, 3, 7, 12, 33}
    70340{0, 10, 30}60639{0, 1, 5, 28, 49, 52}
    84348{0, 12, 36}63632{0, 1, 3, 7, 15, 31}
    91352{0, 13, 39}65648{0, 1, 3, 30, 43, 51}
    1548{0, 1, 3, 7}84660{0, 1, 5, 8, 21, 40}
    21414{0, 1, 3, 8}85660{0, 1, 5, 21, 62, 79}
    30416{0, 2, 6, 14}90656{0, 2, 6, 24, 38, 80}
    45424{0, 3, 9, 21}51743{0, 1, 3, 9, 21, 37, 47}
    75440{0, 5, 15, 35}57739{0, 1, 3, 13, 36, 43, 52}
    90448{0, 6, 18, 42}62747{0, 1, 3, 10, 14, 39, 57}
    91475{0, 1, 6, 17}63739{0, 1, 3, 18, 34, 54, 58}
    21510{0, 1, 4, 14, 16}63826{0, 1, 3, 7, 15, 20, 31, 41}
    31516{0, 1, 3, 7, 15}85848{0, 1, 3, 7, 15, 31, 42, 63}
    下载: 导出CSV
  • [1] 赵亚军, 郁光辉, 徐汉青. 6G移动通信网络: 愿景、挑战与关键技术[J]. 中国科学: 信息科学, 2019, 49(8): 963–987. doi:  10.1360/N112019-00033

    ZHAO Yajun, YU Guanghui, and XU Hanqing. 6G mobile communication networks: Vision, challenges, and key technologies[J]. Scientia Sinica Informationis, 2019, 49(8): 963–987. doi:  10.1360/N112019-00033
    [2] LIU Yanfang, OLMOS P M, and MITCHELL D G M. Generalized LDPC codes for ultra reliable low latency communication in 5G and beyond[J]. IEEE Access, 2018, 6: 72002–72014. doi:  10.1109/ACCESS.2018.2880997
    [3] CHEN Chao, BAI Baoming, SHI Guangming, et al. Nonbinary LDPC codes on cages: Structural property and code optimization[J]. IEEE Transactions on Communications, 2015, 63(2): 364–375. doi:  10.1109/TCOMM.2014.2387341
    [4] ZHU Min, GUO Quan, BAI Baoming, et al. Reliability-based joint detection-decoding algorithm for nonbinary LDPC-coded modulation systems[J]. IEEE Transactions on Communications, 2016, 64(1): 2–14. doi:  10.1109/TCOMM.2015.2487454
    [5] 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
    [6] HUANG Qin, SONG Liyuan, and WANG Zulin. Set message-passing decoding algorithms for regular non-binary LDPC codes[J]. IEEE Transactions on Communications, 2017, 65(12): 5110–5122. doi:  10.1109/TCOMM.2017.2746101
    [7] ZHANG Mu, CAI Kui, HUANG Qin, et al. On bit-level decoding of nonbinary LDPC codes[J]. IEEE Transactions on Communications, 2018, 66(9): 3736–3748. doi:  10.1109/TCOMM.2018.2827994
    [8] WIJEKOON V B, VITERBO E, HONG Yi, et al. A novel graph expansion and a decoding algorithm for NB-LDPC codes[J]. IEEE Transactions on Communications, 2020, 68(3): 1358–1369. doi:  10.1109/TCOMM.2019.2961884
    [9] HUANG Qin, LIU Keke, and WANG Zulin. Low-density arrays of circulant matrices: Rank and row-redundancy, and QC-LDPC codes[C]. 2012 IEEE International Symposium on Information Theory, Cambridge, USA, 2012: 3073–3077. doi:  10.1109/ISIT.2012.6284127.
    [10] 李骜, 刘鑫, 陈德运, 等. 基于低秩表示的鲁棒判别特征子空间学习模型[J]. 电子与信息学报, 2020, 42(5): 1223–1230. doi:  10.11999/JEIT190164

    LI Ao, LIU Xin, CHEN Deyun, et al. Robust discriminative feature subspace learning based on low rank representation[J]. Journal of Electronics &Information Technology, 2020, 42(5): 1223–1230. doi:  10.11999/JEIT190164
    [11] 彭义刚, 索津莉, 戴琼海, 等. 从压缩传感到低秩矩阵恢复: 理论与应用[J]. 自动化学报, 2013, 39(7): 981–994. doi:  10.3724/SP.J.1004.2013.00981

    PENG Yigang, SUO Jinli, DAI Qionghai, et al. From compressed sensing to low-rank matrix recovery: Theory and applications[J]. ACTA Automatica Sinica, 2013, 39(7): 981–994. doi:  10.3724/SP.J.1004.2013.00981
    [12] 陈容, 陈岚, WAHLA A H. 基于公式递推法的可变计算位宽的循环冗余校验设计与实现[J]. 电子与信息学报, 2020, 42(5): 1261–1267. doi:  10.11999/JEIT190503

    CHEN Rong, CHEN Lan, and WAHLA A H. Design and implementation of cyclic redundancy check with variable computing width based on formula recursive algorithm[J]. Journal of Electronics &Information Technology, 2020, 42(5): 1261–1267. doi:  10.11999/JEIT190503
    [13] RYAN W E and LIN Shu. Channel Codes: Classical and Modern[M]. New York, USA: Cambridge University Press, 2009: 448–578.
    [14] CHEN Chao, BAI Baoming, and WANG Xinmei. Construction of quasi-cyclic LDPC codes based on a two-dimensional MDS code[J]. IEEE Communications Letters, 2010, 14(5): 447–449. doi:  10.1109/LCOMM.2010.05.100008
    [15] XU Hengzhou, BAI Baoming, ZHU Min, et al. Construction of short-block nonbinary LDPC codes based on cyclic codes[J]. China Communications, 2017, 14(8): 1–9. doi:  10.1109/CC.2017.8014342
    [16] 陈智雄, 苑津莎. 基于多重置换阵的满秩结构化LDPC码构造方法[J]. 电子学报, 2012, 40(2): 313–318. doi:  10.3969/j.issn.0372-2112.2012.02.017

    CHEN Zhixiong and YUAN Jinsha. Construction of structure LDPC codes with full rank based on multi-permutation matrix[J]. Acta Electronica Sinica, 2012, 40(2): 313–318. doi:  10.3969/j.issn.0372-2112.2012.02.017
    [17] TANNER R. A recursive approach to low complexity codes[J]. IEEE Transactions on Information Theory, 1981, 27(5): 533–547. doi:  10.1109/TIT.1981.1056404
    [18] XIAO Xin, VASIĆ B, LIN Shu, et al. Reed-Solomon based quasi-cyclic LDPC codes: Designs, girth, cycle structure, and reduction of short cycles[J]. IEEE Transactions on Communications, 2019, 67(8): 5275–5286. doi:  10.1109/TCOMM.2019.2916605
    [19] XU Hengzhou, FENG Dan, SUN Cheng, et al. Algebraic-based nonbinary ldpc codes with flexible field orders and code rates[J]. China Communications, 2017, 14(4): 111–119. doi:  10.1109/CC.2017.7927569
    [20] HU Xiaoyu, ELEFTHERIOU E, and ARNOLD D M. Regular and irregular progressive edge-growth tanner graphs[J]. IEEE Transactions on Information Theory, 2005, 51(1): 386–398. doi:  10.1109/TIT.2004.839541
    [21] POLYANSKIY Y, POOR H V, and VERDU S. Channel coding rate in the finite blocklength regime[J]. IEEE Transactions on Information Theory, 2010, 56(5): 2307–2359. doi:  10.1109/TIT.2010.2043769
  • [1] 张琳, 陈炳均, 吴志强.  基于矩阵低秩估计的可靠多载波差分混沌键控接收机, 电子与信息学报. 2020, 42(0): 1-8. doi: 10.11999/JEIT200349
    [2] 杨洋, 方勇, 单博炜.  非平稳信道下LDPC码低复杂度滑窗置信传播联合信道估计与译码算法, 电子与信息学报. 2020, 42(0): 1-9. doi: 10.11999/JEIT200406
    [3] 张天骐, 王俊霞, 江晓磊, 全盛荣.  基于校验矩阵匹配的循环码参数盲识别算法, 电子与信息学报. 2017, 39(4): 901-907. doi: 10.11999/JEIT160575
    [4] 黎相成, 陈海强, 梁奇, 孙友明, 万海斌, 覃团发.  基于二元译码信息的迭代大数逻辑LDPC译码算法及其量化优化, 电子与信息学报. 2017, 39(4): 873-880. doi: 10.11999/JEIT160563
    [5] 范亚楠, 王丽冲, 姚秀娟, 孟新.  一种交叠的Shuffled-BP LDPC译码算法, 电子与信息学报. 2016, 38(11): 2908-2915. doi: 10.11999/JEIT151477
    [6] 兰亚柱, 杨海钢, 林郁.  面向DVB-S2标准LDPC码的高效编码结构, 电子与信息学报. 2016, 38(7): 1781-1787. doi: 10.11999/JEIT151198
    [7] 张轶, 达新宇, 苏一栋.  利用等差数列构造大围长准循环低密度奇偶校验码, 电子与信息学报. 2015, 37(2): 394-398. doi: 10.11999/JEIT140538
    [8] 杨民, 张文彦, 钟杰, 吴杰.  准循环多进制LDPC码构造, 电子与信息学报. 2013, 35(2): 297-302. doi: 10.3724/SP.J.1146.2012.00403
    [9] 张高远, 周亮, 苏伟伟, 文红.  基于平均幅度的LDPC码加权比特翻转译码算法, 电子与信息学报. 2013, 35(11): 2572-2578. doi: 10.3724/SP.J.1146.2012.01728
    [10] 章坚武, 颜欢, 包建荣.  一种基于伪循环MDS码的准循环LDPC码构造方法, 电子与信息学报. 2012, 34(2): 410-415. doi: 10.3724/SP.J.1146.2011.00786
    [11] 袁瑞佳, 白宝明.  基于FPGA的LDPC码编译码器联合设计, 电子与信息学报. 2012, 34(1): 38-44. doi: 10.3724/SP.J.1146.2011.00539
    [12] 戚肖克, 李宇, 黄海宁.  可逆QC-LDPC码的构造及其在水声通信系统中的性能, 电子与信息学报. 2012, 34(8): 1986-1992. doi: 10.3724/SP.J.1146.2011.01373
    [13] 陈紫强, 欧阳缮, 肖海林.  解码前传半双工中继信道下协作LDPC码设计, 电子与信息学报. 2011, 33(11): 2610-2615. doi: 10.3724/SP.J.1146.2011.00323
    [14] 苏和光, 夏树涛.  一种新的码率兼容LDPC码打孔方案, 电子与信息学报. 2011, 33(10): 2334-2339. doi: 10.3724/SP.J.1146.2010.01202
    [15] 郭琨, 黑勇, 周玉梅, 乔树山.  一种应用于不可分层LDPC码的并行分层译码算法, 电子与信息学报. 2010, 32(8): 1956-1960. doi: 10.3724/SP.J.1146.2009.01160
    [16] 敬龙江, 林竞力, 朱维乐.  一种高码率低复杂度准循环LDPC码设计研究, 电子与信息学报. 2008, 30(6): 1385-1389. doi: 10.3724/SP.J.1146.2006.01738
    [17] 乔华, 管武, 董明科, 项海格.  一种基于循环移位矩阵的LDPC码构造方法, 电子与信息学报. 2008, 30(10): 2384-2387. doi: 10.3724/SP.J.1146.2007.00526
    [18] 车书玲, 李坪, 王新梅.  一种基于PPM的LDPC编译码方案, 电子与信息学报. 2008, 30(11): 2630-2633. doi: 10.3724/SP.J.1146.2007.00693
    [19] 刘建权, 刘永山, 徐友云, 蔡跃明.  基于循环转置单位矩阵条件填充的LDPC码构造方法, 电子与信息学报. 2007, 29(12): 2902-2906. doi: 10.3724/SP.J.1146.2006.00646
    [20] 杜伟章, 王新梅.  基于GF(qN)上秩距离码的校验矩阵的验证方案, 电子与信息学报. 2001, 23(9): 841-846.
  • 加载中
  • 图(4) / 表ll (4)
    计量
    • 文章访问数:  27
    • HTML全文浏览量:  2
    • PDF下载量:  8
    • 被引次数: 0
    出版历程
    • 收稿日期:  2020-05-08
    • 修回日期:  2020-10-26
    • 网络出版日期:  2020-11-19

    目录

      /

      返回文章
      返回

      官方微信,欢迎关注