围长为8的较大列重准循环低密度奇偶校验码的行重普适代数构造

张国华; 秦煜; 娄蒙娟; 方毅

doi:10.11999/JEIT231111

围长为8的较大列重准循环低密度奇偶校验码的行重普适代数构造

doi: 10.11999/JEIT231111

张国华¹,
秦煜¹,
娄蒙娟¹,
方毅^2, ,

1.
西安邮电大学西安 710121
2.
广东工业大学广州 510006

基金项目: 国家自然科学基金(62322106, 62071131)，广东省国际科技合作项目(2022A0505050070)

详细信息

作者简介:
张国华：男，研究员，研究方向为信道编码理论与应用

秦煜：男，硕士生，研究方向为LDPC码的构造方法

娄蒙娟：女，硕士生，研究方向为LDPC码的构造方法

方毅：男，教授，研究方向为通信与存储系统中的信道编码

通讯作者:
方毅　fangyi@gdut.edu.cn

中图分类号: TN911.22
计量
- 文章访问数: 200
- HTML全文浏览量: 71
- PDF下载量: 42
- 被引次数: 0
出版历程
- 收稿日期: 2023-10-12
- 修回日期: 2024-01-25
- 网络出版日期: 2024-02-07
- 刊出日期: 2024-07-29

Row-weight Universal Algebraic Constructions of Girth-8 Quasi-Cyclic Low-Density Parity-Check Codes with Large Column Weights

1.
Xi’an University of Posts and Telecommunications, Xi’an 710121, China
2.
Guangdong University of Technology, Guangzhou 510006, China

Funds: The National Natural Science Foundation of China (62322106, 62071131), International Collaborative Research Program of Guangdong Science and Technology Department (2022A0505050070)

摘要

摘要: 适合于任意行重(即行重普适(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.
- Low-Density Parity-Check (LDPC) codes /
- Quasi-Cyclic(QC) /
- Girth /
- Greatest Common Divisor (GCD)

HTML全文

图 1 新码与对称结构码的译码性能对比

下载: 全尺寸图片幻灯片

表 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

参考文献(21)

[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.020. ZHANG 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/JEIT140538. ZHANG 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.00838. ZHANG 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.