圍長為8的較大列重準循環(huán)低密度奇偶校驗碼的行重普適代數構造

張國華; 秦煜; 婁蒙娟; 方毅

doi:10.11999/JEIT231111

圍長為8的較大列重準循環(huán)低密度奇偶校驗碼的行重普適代數構造

doi: 10.11999/JEIT231111 cstr: 32379.14.JEIT231111

張國華¹,
秦煜¹,
婁蒙娟¹,
方毅^2, ,

1.
西安郵電大學西安 710121
2.
廣東工業(yè)大學廣州 510006

基金項目: 國家自然科學基金(62322106, 62071131)，廣東省國際科技合作項目(2022A0505050070)

詳細信息

作者簡介:
張國華：男，研究員，研究方向為信道編碼理論與應用

秦煜：男，碩士生，研究方向為LDPC碼的構造方法

婁蒙娟：女，碩士生，研究方向為LDPC碼的構造方法

方毅：男，教授，研究方向為通信與存儲系統(tǒng)中的信道編碼

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

中圖分類號: TN911.22
計量
- 文章訪問數: 323
- HTML全文瀏覽量: 135
- PDF下載量: 52
- 被引次數: 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))的無小環(huán)準循環(huán)(QC)低密度奇偶校驗(LDPC)短碼，對于LDPC碼的理論研究和工程應用具有重要意義。具有行重普適特性且消除4環(huán)6環(huán)的現有構造方法，只能針對列重為3和4的情況提供QC-LDPC短碼。該文在最大公約數(GCD)框架的基礎上，對于列重為5和6的情況，提出了3種具有行重普適特性且消除4環(huán)6環(huán)的構造方法。與現有的行重普適方法相比，新方法提供的碼長從目前的與行重呈4次方關系銳減至與行重呈3次方關系，因而可以為QC-LDPC碼的復合構造和高級優(yōu)化等需要較大列重基礎碼的場合提供行重普適的無4環(huán)無6環(huán)短碼。此外，與基于計算機搜索的對稱結構QC-LDPC碼相比，新碼不僅無需搜索、描述復雜度更低，而且具有更好的譯碼性能。
- 低密度奇偶校驗碼 /
- 準循環(huán) /
- 圍長 /
- 最大公約數
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環(huán)的原因

序號	原始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環(huán)的原因

序號	原始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]	張軼, 達新宇, 蘇一棟. 利用等差數列構造大圍長準循環(huán)低密度奇偶校驗碼[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)-規(guī)則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.