Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

Cycle Analysis and Construction of Protographs for QC LDPC Codes With Girth Larger Than 12

Sunghwan Kim, Jong‐Seon No, Habong Chung, Dong‐Joon Shin

Published Jun 1, 2007• 7 citations
Publisher

Abstract

A quasi-cyclic (QC) low-density parity-check (LDPC) code can be viewed as the protograph code with circulant permutation matrices. In this paper, we find all the subgraph patterns of protographs of QC LDPC codes having inevitable cycles of length 2i,i= 6,7,8,9,10, i.e., the cycles existing regardless of the shift values of circulants. It is also derived that if the girth of the protograph is 2g,gges 2, its protograph code cannot have the inevitable cycles of length smaller than 6g. Based on these subgraph patterns, we propose new combinatorial construction methods of the protographs, whose protograph codes can have girth larger than or equal to 14.

DOI
10.1109/isit.2007.4557555

Related papers

Quasi-Cyclic Low-Density Parity-Check Codes With Girth Larger Than 121212

Sunghwan Kim, Jong‐Seon No, Habong Chung +1 more

A quasi-cyclic (QC) low-density parity-check (LDPC) code can be viewed as the protograph code with circulant permutation matrices (or circulants). In this correspondence, we find all the subgraph patterns of protographs of QC LDPC codes having inevitable cycles of length 2i, i = 6, 7, 8, 9,10, i.e., the cycles that always exist regardless of the shift values of circulants. It is also derived that if the girth of the protograph is 2g, g > 2, its protograph code cannot have the inevitable cycles of length smaller than 6g. Based on these subgraph patterns, we propose new combinatorial construction methods of the protographs, whose protograph codes can have girth larger than or equal to 14 or 18. We also propose a couple of shift value assigning rules for circulants of a QC LDPC code guaranteeing the girth 14.

IEEE Transactions on Information Theory•Aug 1, 2007•95 citations

Protograph Codes with Circulant Permutation Matrices

Sunghwan Kim, Min‐Ho Jang, Jong‐Seon No +2 more

A quasi-cyclic (QC) low-density parity-check (LDPC) code can be viewed as the protograph code with circulant permutation matrices. In this paper, we find all the subgraph patterns of protographs of QC LDPC codes having inevitable cycles of length 2i, i = 6, 7, 8, 9, 10, i.e., the cycles existing regardless of the shift values of circulants. It is also derived that if the girth of the protograph is 2g, g ≥ 2, its protograph code cannot have the inevitable cycles of length smaller than 6g.

한국통신학회 학술대회논문집•Jun 1, 2005•4 citations

Cycle Analysis in Expanded QC LDPC Codes

Xiao Rong Gao, Nan Zhang

A quasi-cyclic (QC) low-density parity-check (LDPC) code can be viewed as the protograph code with circulant permutation matrices. In this paper, we use permutation matrices to form protograph LDPC codes. In protograph LDPC codes, we present cycle relationships of the mother matrix and the protograph LDPC code. It is derived that the girth of a protograph LDPC code is no smaller than its mother matrix .And cycles in the protograph LDPC codes are uniquely induced by the cycles in its mother matrix.

•Jan 1, 2011•0 citations

1Design of Multiple-Edge Protographs for QC LDPC Codes Avoiding Short Inevitable Cycles

Hosung Park Seokbeom Hong

There have been lots of efforts on the construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes with large girth. However, most of them are focused on protographs with single edges and little research has been done for the construction of QC LDPC codes lifted from protographs with multiple edges. Compared to single-edge protographs, multiple-edge protographs have benefits such that QC LDPC codes lifted from them can potentially have larger minimum Hamming distance. In this paper, all subgraph patterns of multiple-edge protographs, which prevent QC LDPC codes from having large girth by inducing inevitable cycles, are fully investigated based on graph-theoretic approach. By using combinatorial designs, a systematic construction method of multiple-edge protographs is proposed for regular QC LDPC codes with girth at least 12 and also other method is proposed for regular QC LDPC codes with girth at least 14. A construction algorithm of QC LDPC codes by lifting multiple-edge protographs is proposed and it is shown that the resulting QC LDPC codes have larger upper bounds on the minimum Hamming distance than those lifted from single-edge protographs. Simulation results are provided to compare the performance of the proposed QC LDPC codes, the progressive edge-growth (PEG) LDPC codes, and the PEG QC LDPC codes.

•Jan 1, 2014•26 citations

Design of Multiple-Edge Protographs for QC LDPC Codes Avoiding Short Inevitable Cycles

Hosung Park, Seokbeom Hong, Jong-Seon No +1 more

There have been lots of efforts on the construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes with large girth. However, most of them focus on protographs with single edges and little research has been done for the construction of QC LDPC codes lifted from protographs with multiple (i.e., parallel) edges. Compared to single-edge protographs, multiple-edge protographs have benefits such that QC LDPC codes lifted from them can potentially have larger minimum Hamming distance. In this paper, all subgraph patterns of multiple-edge protographs, which prevent QC LDPC codes from having large girth by inducing inevitable cycles, are fully investigated based on a graph-theoretic approach. By using combinatorial designs, a systematic construction method of multiple-edge protographs is proposed for regular QC LDPC codes with girth at least 12 and another method is proposed for regular QC LDPC codes with girth at least 14. Moreover, a construction algorithm of QC LDPC codes based on certain liftings of multiple-edge protographs is proposed and it is shown that the resulting QC LDPC codes have larger upper bounds on the minimum Hamming distance than those lifted from single-edge protographs. Simulation results are provided to compare the performance of the proposed QC LDPC codes with progressive edge-growth (PEG) LDPC codes and with PEG QC LDPC codes.

arXiv:1210.3906•IEEE Transactions on Information Theory•Jun 14, 2013•30 citations

Protograph design for QC LDPC codes with large girth

Hosung Park, Seokbeom Hong, Jong‐Seon No +1 more

In this paper, all subgraph patterns of protographs which prevent quasi-cyclic (QC) low-density parity-check (LDPC) codes from having large girth are searched in allowance with multiple edges based on graph theoretic approach. A systematic construction of protograph with multiple edges using combinatorial design is proposed for QC LDPC codes with girth larger than or equal to 12.

International Conference on Information and Communication Technology Convergence (ICTC)•Nov 1, 2010•1 citation
A quasi-cyclic (QC) low-density parity-check (LDPC) code can be viewed as the protograph code with circulant permutation matrices. In this paper, we find all the subgraph patterns of protographs of QC LDPC codes having inevitable cycles of length 2i,i= 6,7,8,9,10, i.e., the cycles existing regardless of the shift values of circulants. It is also derived that if the girth of the protograph is 2g,gges 2, its protograph code cannot have the inevitable cycles of length smaller than 6g. Based on these subgraph patterns, we propose new combinatorial construction methods of the protographs, whose protograph codes can have girth larger than or equal to 14.
A quasi-cyclic (QC) low-density parity-check (LDPC) code can be viewed as the protograph code with circulant permutation matrices (or circulants). In this correspondence, we find all the subgraph patterns of protographs of QC LDPC codes having inevitable cycles of length 2i, i = 6, 7, 8, 9,10, i.e., the cycles that always exist regardless of the shift values of circulants. It is also derived that if the girth of the protograph is 2g, g > 2, its protograph code cannot have the inevitable cycles of length smaller than 6g. Based on these subgraph patterns, we propose new combinatorial construction methods of the protographs, whose protograph codes can have girth larger than or equal to 14 or 18. We also propose a couple of shift value assigning rules for circulants of a QC LDPC code guaranteeing the girth 14.
A quasi-cyclic (QC) low-density parity-check (LDPC) code can be viewed as the protograph code with circulant permutation matrices. In this paper, we use permutation matrices to form protograph LDPC codes. In protograph LDPC codes, we present cycle relationships of the mother matrix and the protograph LDPC code. It is derived that the girth of a protograph LDPC code is no smaller than its mother matrix .And cycles in the protograph LDPC codes are uniquely induced by the cycles in its mother matrix.
There have been lots of efforts on the construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes with large girth. However, most of them are focused on protographs with single edges and little research has been done for the construction of QC LDPC codes lifted from protographs with multiple edges. Compared to single-edge protographs, multiple-edge protographs have benefits such that QC LDPC codes lifted from them can potentially have larger minimum Hamming distance. In this paper, all subgraph patterns of multiple-edge protographs, which prevent QC LDPC codes from having large girth by inducing inevitable cycles, are fully investigated based on graph-theoretic approach. By using combinatorial designs, a systematic construction method of multiple-edge protographs is proposed for regular QC LDPC codes with girth at least 12 and also other method is proposed for regular QC LDPC codes with girth at least 14. A construction algorithm of QC LDPC codes by lifting multiple-edge protographs is proposed and it is shown that the resulting QC LDPC codes have larger upper bounds on the minimum Hamming distance than those lifted from single-edge protographs. Simulation results are provided to compare the performance of the proposed QC LDPC codes, the progressive edge-growth (PEG) LDPC codes, and the PEG QC LDPC codes.
There have been lots of efforts on the construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes with large girth. However, most of them focus on protographs with single edges and little research has been done for the construction of QC LDPC codes lifted from protographs with multiple (i.e., parallel) edges. Compared to single-edge protographs, multiple-edge protographs have benefits such that QC LDPC codes lifted from them can potentially have larger minimum Hamming distance. In this paper, all subgraph patterns of multiple-edge protographs, which prevent QC LDPC codes from having large girth by inducing inevitable cycles, are fully investigated based on a graph-theoretic approach. By using combinatorial designs, a systematic construction method of multiple-edge protographs is proposed for regular QC LDPC codes with girth at least 12 and another method is proposed for regular QC LDPC codes with girth at least 14. Moreover, a construction algorithm of QC LDPC codes based on certain liftings of multiple-edge protographs is proposed and it is shown that the resulting QC LDPC codes have larger upper bounds on the minimum Hamming distance than those lifted from single-edge protographs. Simulation results are provided to compare the performance of the proposed QC LDPC codes with progressive edge-growth (PEG) LDPC codes and with PEG QC LDPC codes.