Row-weight Universal Algebraic Constructions of Girth-8 Quasi-Cyclic Low-Density Parity-Check Codes with Large Column Weights
-
摘要: 适合于任意行重(即行重普适(RWU))的无小环准循环(QC)低密度奇偶校验(LDPC)短码，对于LDPC码的理论研究和工程应用具有重要意义。具有行重普适特性且消除4环6环的现有构造方法，只能针对列重为3和4的情况提供QC-LDPC短码。该文在最大公约数(GCD)框架的基础上，对于列重为5和6的情况，提出了3种具有行重普适特性且消除4环6环的构造方法。与现有的行重普适方法相比，新方法提供的码长从目前的与行重呈4次方关系锐减至与行重呈3次方关系，因而可以为QC-LDPC码的复合构造和高级优化等需要较大列重基础码的场合提供行重普适的无4环无6环短码。此外，与基于计算机搜索的对称结构QC-LDPC码相比，新码不仅无需搜索、描述复杂度更低，而且具有更好的译码性能。Abstract: Short Quasi-Cyclic (QC) Low-Density Parity-Check (LDPC) codes without small cycles suitable for an arbitrary row weight (i.e., Row-Weight Universal (RWU)), are of great significance for both theoretical research and engineering application. Existing methods having RWU property and guaranteeing the nonexistence of 4-cycles and 6-cycles, can only offer short QC-LDPC codes for the column weights of 3 and 4. Based on the Greatest Common Divisor (GCD) framework, three new methods are proposed in this paper for the column weights of 5 and 6, which can possess RWU property and at the same time remove all 4-cycles and 6-cycles. Compared with existing methods with RWU property, the code lengths of the novel methods are sharply reduced from the fourth power of row weight to the third power of row weight. Therefore, the new methods can provide short RWU QC-LDPC codes without 4-cycles and 6-cycles for occasions where base codes with large column weights are required, such as composite constructions and advanced optimization pertaining to QC-LDPC codes. Moreover, compared with the search-based symmetric QC-LDPC codes, the new codes need no search, have lower description complexity, and exhibit better decoding performance.
-
表 1 定理1中的新构造所涉及3元组及其GCD指标
序号 原始3元组 简化后的3元组 GCD指标 1 $[0,2,2L{\text{ + }}1]$ - $2L + 1$ 2 $[0,2,3L]$ - $ \ge 3L{\text{/}}2$ 3 $[0,2,3L + 1]$ - $ \ge (3L + 1){\text{/}}2$ 4 $[0,2L + 1,3L]$ $({\text{R}})[0,L - 1,3L]$ $ \ge L$ 5 $[0,2L + 1,3L{\text{ + }}1]$ $({\text{R}})[0,L,3L{\text{ + }}1]$ $3L + 1$ 6 $[0,3L,3L{\text{ + }}1]$ $({\text{R}})[0,1,3L{\text{ + }}1]$ $3L + 1$ 7 $[2,2L + 1,3L]$ $({\text{S}})({\text{R}})[0,L - 1,3L - 2]$ $3L - 2$ 8 $[2,2L + 1,3L{\text{ + }}1]$ $({\text{S}})({\text{R}})[0,L,3L - 1]$ $3L - 1$ 9 $[2,3L,3L{\text{ + }}1]$ $({\text{S}})({\text{R}})[0,1,3L - 1]$ $3L - 1$ 10 $[2L + 1,3L,3L{\text{ + }}1]$ $({\text{S}})({\text{R}})[0,1,L]$ $L$ 
下载: 导出CSV
表 2 性质1所涉及的2元组及无4环的原因
序号 原始2元组 化简后的2元组 原因 1 $ [0,2] $ - 引理2 2 $ [0,2L + 1] $ - 引理2 3* $ [0,3L] $ - 需证明 4 $ [0,3L + 1] $ $ ({\text{D}})[0,1] $ 引理2 5 $ [2,2L + 1] $ $ ({\text{S}})[0,2L - 1] $ 引理2 6* $ [2,3L] $ $ ({\text{S}})[0,3L - 2] $ 需证明 7* $ [2,3L + 1] $ $ ({\text{S}})[0,3L - 1] $ 需证明 8 $ [2L + 1,3L] $ $ ({\text{S}})[0,L - 1] $ 引理2 9 $ [2L + 1,3L + 1] $ $ ({\text{S}})[0,L] $ 引理2 10 $ [3L,3L + 1] $ $ ({\text{S}})[0,1] $ 同序号4
下载: 导出CSV
表 3 性质1所涉及的3元组及无6环的原因
序号 原始3元组 简化后的3元组 原因 1 $[0,2,2L{\text{ + }}1]$ - 引理1 2 $[0,2,3L]$ - 引理3 3* $[0,2,3L + 1]$ - 需证明 4 $[0,2L + 1,3L]$ $ ({\text{R}})[0,L - 1,3L] $ 引理3 5 $[0,2L + 1,3L{\text{ + }}1]$ $ ({\text{R}})[0,L,3L + 1] $ 引理3 6 $[0,3L,3L{\text{ + }}1]$ $ ({\text{R}})[0,1,3L + 1] $ 引理3 7* $[2,2L + 1,3L]$ $ ({\text{S}})({\text{R}})[0,L - 1,3L - 2] $ 需证明 8 $[2,2L + 1,3L{\text{ + }}1]$ $ ({\text{S}})({\text{R}})[0,L,3L - 1] $ 引理3 9* $[2,3L,3L{\text{ + }}1]$ $ ({\text{S}})({\text{R}})[0,1,3L - 1] $ 需证明 10 $[2L + 1,3L,3L{\text{ + }}1]$ $ ({\text{S}})({\text{R}})[0,1,L] $ 引理1
下载: 导出CSV
表 4 定理2中的新构造所涉及3元组及其GCD指标
序号 原始3元组 化简后的3元组 GCD指标 1 $ [0,1,2L] $ - $ \begin{array}{*{20}{c}} {2L} \end{array} $ 2 $ [0,1,2L + 2] $ - $ \begin{array}{*{20}{c}} {2L + 2} \end{array} $ 3 $ [0,1,4L + 1] $ - $ \begin{array}{*{20}{c}} {4L + 1} \end{array} $ 4 $ [0,1,4L + 2] $ - $ \begin{array}{*{20}{c}} {4L + 2} \end{array} $ 5 $ [0,2L,2L + 2] $ $ ({\text{R}})[0,2,2L + 2] $ $ \begin{array}{*{20}{c}} {L + 1} \end{array} $ 6 $ [0,2L,4L + 1] $ - $ \begin{array}{*{20}{c}} {4L + 1} \end{array} $ 7 $ [0,2L,4L + 2] $ - $ \begin{array}{*{20}{c}} {2L + 1} \end{array} $ 8 $ [0,2L + 2,4L + 1] $ $ ({\text{R}})[0,2L - 1,4L + 1] $ $ \begin{array}{*{20}{c}} { \ge (4L + 1){\text{/}}3} \end{array} $ 9 $ [0,2L + 2,4L + 2] $ $ \begin{array}{*{20}{c}} {({\text{R}})[0,2L,4L + 2]} \end{array} $ 同序号7 10 $ [0,4L + 1,4L + 2] $ $ \begin{array}{*{20}{c}} {({\text{R}})[0,1,4L + 2]} \end{array} $ 同序号4 11 $ [1,2L,2L + 2] $ $ ({\text{S}})({\text{R}})[0,2,2L + 1] $ $ \begin{array}{*{20}{c}} {2L + 1} \end{array} $ 12 $ [1,2L,4L + 1] $ $ ({\text{S}})[0,2L - 1,4L] $ $ \begin{array}{*{20}{c}} {4L} \end{array} $ 13 $ [1,2L,4L + 2] $ $ ({\text{S}})[0,2L - 1,4L + 1] $ 同序号8 14 $ [1,2L + 2,4L + 1] $ $ \begin{array}{*{20}{c}} {({\text{S}})({\text{R}})[0,2L - 1,4L]} \end{array} $ 同序号12 15 $ [1,2L + 2,4L + 2] $ $ \begin{array}{*{20}{c}} {({\text{S}})({\text{R}})[0,2L,4L + 1]} \end{array} $ 同序号6 16 $ [1,4L + 1,4L + 2] $ $ \begin{array}{*{20}{c}} {({\text{S}})({\text{R}})[0,1,4L + 1]} \end{array} $ 同序号3 17 $ [2L,2L + 2,4L + 1] $ $ ({\text{S}})\begin{array}{*{20}{c}} {[0,2,2L + 1]} \end{array} $ 同序号11 18 $ [2L,2L + 2,4L + 2] $ $ ({\text{S}})\begin{array}{*{20}{c}} {[0,2,2L + 2]} \end{array} $ 同序号5 19 $ [2L,4L + 1,4L + 2] $ $ \begin{array}{*{20}{c}} {({\text{S}})({\text{R}})[0,1,2L + 2]} \end{array} $ 同序号2 20 $ [2L + 2,4L + 1,4L + 2] $ $({\text{S}})({\text{R}})[0,1,2L]$ 同序号1
下载: 导出CSV
表 5 定理3中的新构造所涉及3元组及其GCD指标
序号 原始3元组 化简后的3元组 GCD指标 1 $ [0,L,L + 1] $ $ ({\text{R}})[0,1,L + 1] $ $ \begin{array}{*{20}{c}} {L + 1} \end{array} $ 2 $ [0,L,3L + 1] $ - $ \begin{array}{*{20}{c}} {3L + 1} \end{array} $ 3 $ [0,L,3L + 2] $ - $ \begin{array}{*{20}{c}} { \ge (3L + 2){\text{/}}2} \end{array} $ 4 $ [0,L,4L + 2] $ - $ \begin{array}{*{20}{c}} { \ge 2L + 1} \end{array} $ 5 $ [0,L + 1,3L + 1] $ - $ \begin{array}{*{20}{c}} { \ge (3L + 1){\text{/}}2} \end{array} $ 6 $ [0,L + 1,3L + 2] $ - $ \begin{array}{*{20}{c}} {3L + 2} \end{array} $ 7 $ [0,L + 1,4L + 2] $ - $ \begin{array}{*{20}{c}} { \ge 2L + 1} \end{array} $ 8 $ [0,3L + 1,3L + 2] $ $ ({\text{R}})[0,1,3L + 2] $ $ \begin{array}{*{20}{c}} {3L + 2} \end{array} $ 9 $ [0,3L + 1,4L + 2] $ $ ({\text{R}})[0,L + 1,4L + 2] $ 同序号7 10 $ [0,3L + 2,4L + 2] $ $ ({\text{R}})[0,L,4L + 2] $ 同序号4 11 $ [L,L + 1,3L + 1] $ $ ({\text{S}})[0,1,2L + 1] $ $ \begin{array}{*{20}{c}} {2L + 1} \end{array} $ 12 $ [L,L + 1,3L + 2] $ $ ({\text{S}})[0,1,2L + 2] $ $ \begin{array}{*{20}{c}} {2L + 2} \end{array} $ 13 $ [L,L + 1,4L + 2] $ $ ({\text{S}})[0,1,3L + 2] $ 同序号8 14 $ [L,3L + 1,3L + 2] $ $ ({\text{S}})({\text{R}})[0,1,2L + 2] $ 同序号12 15 $ [L,3L + 1,4L + 2] $ $ ({\text{S}})({\text{R}})[0,L + 1,3L + 2] $ 同序号6 16 $ [L,3L + 2,4L + 2] $ $ ({\text{S}})({\text{R}})[0,L,3L + 2] $ 同序号3 17 $ [L + 1,3L + 1,3L + 2] $ $ ({\text{S}})({\text{R}})[0,1,2L + 1] $ 同序号11 18 $ [L + 1,3L + 1,4L + 2] $ $ ({\text{S}})({\text{R}})[0,L + 1,3L + 1] $ 同序号5 19 $ [L + 1,3L + 2,4L + 2] $ $ ({\text{S}})({\text{R}})[0,L,3L + 1] $ 同序号2 20 $ [3L + 1,3L + 2,4L + 2] $ $ ({\text{S}})[0,1,L + 1] $ 同序号1
下载: 导出CSV
-
[1] ZHANG Lintao and WANG Juhua. Construction of QC-LDPC codes from Sidon sequence using permutation and segmentation[J]. IEEE Communications Letters, 2022, 26(8): 1710–1714. doi: 10.1109/LCOMM.2022.3177511 [2] AMIRZADE F, SADEGHI M R, and PANARIO D. Construction of protograph-based LDPC codes with chordless short cycles[J]. IEEE Transactions on Information Theory, 2024, 70(1): 51–74. doi: 10.1109/TIT.2023.3307583 [3] SMARANDACHE R and MITCHELL D G M. A unifying framework to construct QC-LDPC Tanner graphs of desired girth[J]. IEEE Transactions on Information Theory, 2022, 68(9): 5802–5822. doi: 10.1109/TIT.2022.3170331 [4] VASIC B, PEDAGANI K, and IVKOVIC M. High-rate girth-eight low-density parity-check codes on rectangular integer lattices[J]. IEEE Transactions on Communications, 2004, 52(8): 1248–1252. doi: 10.1109/TCOMM.2004.833037 [5] FOSSORIER M P C. Quasic-cyclic low-density parity-check codes from circulant permutation matrices[J]. IEEE Transactions on Information Theory, 2004, 50(8): 1788–1793. doi: 10.1109/TIT.2004.831841 [6] BOCHAROVA I E, KUDRYASHOV B D, OVSYANNIKOV E P, et al. Design and analysis of NB QC-LDPC codes over small alphabets[J]. IEEE Transactions on Communications, 2022, 70(5): 2964–2976. doi: 10.1109/TCOMM.2022.3160176 [7] TASDIGHI A, BANIHASHEMI A H, and SADEGHI M R. Symmetrical constructions for regular girth-8 QC-LDPC codes[J]. IEEE Transactions on Communications, 2017, 65(1): 14–22. doi: 10.1109/TCOMM.2016.2617335 [8] 张国华, 王新梅. 围长至少为8的QC-LDPC码的新构造: 一种显式框架[J]. 电子学报, 2012, 40(2): 331–337. doi: 10.3969/j.issn.0372-2112.2012.02.020ZHANG Guohua and WANG Xinmei. Novel constructions of QC-LDPC codes with girth at least eight: an explicit framework[J]. Acta Electronica Sinica, 2012, 40(2): 331–337. doi: 10.3969/j.issn.0372-2112.2012.02.020 [9] ZHANG Jianhua and ZHANG Guohua. Deterministic girth-eight QC-LDPC codes with large column weight[J]. IEEE Communications Letters, 2014, 18(4): 656–659. doi: 10.1109/LCOMM.2014.030114.132853 [10] MAJDZADE M and GHOLAMI M. On the class of high-rate QC-LDPC codes with girth 8 from sequences satisfied in GCD condition[J]. IEEE Communications Letters, 2020, 24(7): 1391–1394. doi: 10.1109/LCOMM.2020.2983019 [11] TAO Xiongfei, CHEN Xin, and WANG Bifang. On the construction of QC-LDPC codes based on integer sequence with low error floor[J]. IEEE Communications Letters, 2022, 26(10): 2267–2271. doi: 10.1109/LCOMM.2022.3187435 [12] 张轶, 达新宇, 苏一栋. 利用等差数列构造大围长准循环低密度奇偶校验码[J]. 电子与信息学报, 2015, 37(2): 394–398. doi: 10.11999/JEIT140538ZHANG Yi, DA Xinyu, and SU Yidong. Construction of quasi-cyclic low-density parity-check codes with a large girth based on arithmetic progression[J]. Journal of Electronics & Information Technology, 2015, 37(2): 394–398. doi: 10.11999/JEIT140538 [13] 张国华, 陈超, 杨洋, 等. Girth-8 (3, L)-规则QC-LDPC码的一种确定性构造方法[J]. 电子与信息学报, 2010, 32(5): 1152–1156. doi: 10.3724/SP.J.1146.2009.00838ZHANG Guohua, CHEN Chao, YANG Yang, et al. Girth-8 (3, L)-regular QC-LDPC codes based on novel deterministic design technique[J]. Journal of Electronics & Information Technology, 2010, 32(5): 1152–1156. doi: 10.3724/SP.J.1146.2009.00838 [14] ZHANG Guohua, HU Yulin, FANG Yi, et al. Relation between GCD constraint and full-length row-multiplier QC-LDPC codes with girth eight[J]. IEEE Communications Letters, 2021, 25(9): 2820–2823. doi: 10.1109/LCOMM.2021.3096386 [15] ZHANG Yi and DA Xinyu. Construction of girth-eight QC-LDPC codes from arithmetic progression sequence with large column weight[J]. Electronics Letters, 2015, 51(16): 1257–1259. doi: 10.1049/el.2015.0389 [16] 张国华, 孙蓉, 王新梅. 围长为8的QC-LDPC码的显式构造及其在CRT方法中的应用[J]. 通信学报, 2012, 33(3): 171–176. doi: 1000-436X(2012)03-0171-06.ZHANG Guohua, SUN Rong, and WANG Xinmei. Explicit construction of girth-eight QC-LDPC codes and its application in CRT method[J]. Journal on Communications, 2012, 33(3): 171–176. doi: 1000-436X(2012)03-0171-06. [17] ZHANG Guohua, SUN Rong, and WANG Xinmei. Several explicit constructions for (3, L) QC-LDPC codes with girth at least eight[J]. IEEE Communications Letters, 2013, 17(9): 1822–1825. doi: 10.1109/LCOMM.2013.070913.130966 [18] KARIMI M and BANIHASHEMI A H. On the girth of quasi-cyclic protograph LDPC codes[J]. IEEE Transactions on Information Theory, 2013, 59(7): 4542–4552. doi: 10.1109/TIT.2013.2251395 [19] ZHANG Guohua, SUN Rong, and WANG Xinmei. Construction of girth-eight QC-LDPC codes from greatest common divisor[J]. IEEE Communications Letters, 2013, 17(2): 369–372. doi: 10.1109/LCOMM.2012.122012.122292 [20] WANG Juhua, ZHANG Jianhua, ZHOU Quan, et al. Full-length row-multiplier QC-LDPC codes with girth eight and short circulant sizes[J]. IEEE Access, 2023, 11: 22250–22265. doi: 10.1109/ACCESS.2023.3249464 [21] ZHANG Guohua, FANG Yi, and LIU Yuanhua. Automatic verification of GCD constraint for construction of girth-eight QC-LDPC codes[J]. IEEE Communications Letters, 2019, 23(9): 1453–1456. doi: 10.1109/LCOMM.2019.2925792 -
下载:
图(1) / 表(5)
计量
- 文章访问数: 69
- HTML全文浏览量: 10
- PDF下载量: 21
- 被引次数: 0
