IEEE International Symposium on Information Theory (ISIT)

Quasi-Cyclic Protograph-Based Raptor-Like LDPC Codes With Girth 6 and Shortest Length

Farzane Amirzade, Mohammad‐Reza Sadeghi, Daniel Panario

Published Jul 12, 2021• 6 citations

Abstract

We consider multiple-edge QC-LDPC codes with a base matrix of large size. We propose a new method, the degree reduction method, to obtain exponent matrices of these codes which considerably reduces the complexity of the search algorithm. We also provide a necessary and sufficient condition to avoid 4-cycles from occurrence in the Tanner graph of codes obtained using our method. Then, we apply our method to quasi-cyclic protograph-based Raptor-Like LDPC (QC-PBRL-LDPC) codes whose base matrices are multiple-edge. Numerical results show that as a consequence of this study we can obtain the minimum lifting degree of QC-PBRL-LDPC codes with girth at least 6. Thus, the lengths of the obtained codes are much smaller than those of their counterpart short-length codes in the literature.

DOI: 10.1109/isit45174.2021.9518125

Related papers

Analytical Lower Bound on the Lifting Degree of Multiple-Edge QC-LDPC Codes With Girth 6

Mohammad‐Reza Sadeghi, Farzane Amirzade

Multiple-edge protographs have some advantages over single-edge protographs, such as potentially having larger minimum Hamming distance. However, most of results in the literature are related to the construction of single-edge quasi-cyclic low-density parity-check codes (QC-LDPC) codes and little research has been done for the construction of multiple-edge QC-LDPC codes. In this letter, for the first time, necessary and sufficient conditions for the exponent matrices to have multiple-edge QC-LDPC codes with girth 6 are provided. As a consequence of this letter, a lower bound on the lifting degree of regular and irregular multiple-edge QC-LDPC codes with girth 6 is derived. We also present QC-LDPC codes whose lifting degrees meet our proposed lower bound. These codes have shorter lengths compared with single-edge QC-LDPC codes. Another contribution of this letter is presenting a technique to reduce the size of the search space to find these codes.

IEEE Communications LettersMay 29, 201824 citations

Trade-Based LDPC Codes

Farzane Amirzade, Daniel Panario, Mohammad‐Reza Sadeghi

LDPC codes based on multi-edge protographs potentially have larger minimum distances compared to their counterparts, single-edge protographs. However, considering different features of their Tanner graph, such as short cycles, girth and other graphical structures, is harder than for Tanner graphs from single-edge protographs. Here, we provide a novel approach to construct the parity-check matrix of an LDPC code which is based on trades obtained from block designs. We employ our method to construct multi-edge quasi-cyclic (QC) LDPC codes.We use those trade-based matrices to define base matrices of multi-edge protographs. The construction of exponent matrices corresponding to these base matrices has less complexity than the ones proposed in the literature. We prove that these base matrices result in QC-LDPC codes with smaller lower bounds on the lifting degree than existing ones.

arXiv:2107.07466IEEE International Symposium on Information Theory (ISIT)Jun 26, 20224 citations

Design of Protograph-Based Quasi-Cyclic Spatially Coupled Ldpc Codes

Shuoshuo Wang, Zhanji Wu, Qihao Wu

In this paper, we deal with time-varing quasi-cyclic (QC) spatially-coupled (SC) low-density parity-check (LDPC) codes by lifting the coupled protographs. The construction method of girth-6 protographs for any code rate is proposed. We provide a theoretical lower bound on the syndrome former constraint length under condition of the protographs without 4-cycles in their Tanner graphs. Then we use periodic QC lifting method to search the QC-SC-LDPC matrices with larger girth based on the protographs. The minimum dimension size of QC-SC-LDPC codes is given to count the girth of QC-SC-LDPC codes with a semi- infinite binary-check matrix structure. The performance of such constructed codes with lower complexity and delay is superior to the LDPC block codes.

IEEE Wireless Communications and Networking Conference Workshops (WCNCW)Apr 1, 20202 citations

On the Girth of Quasi-Cyclic Protograph LDPC Codes

M. Karimi, Amir H. Banihashemi

In this paper, we study the relationships between the girth of the Tanner graph of a quasi-cyclic (QC) protograph low-density parity-check (LDPC) code, the lifting degree, and the size and the structure of the base graph. As a result, for a given base graph, we derive a lower bound on the lifting degree as a necessary condition for the lifted graph to have a certain girth. This also provides an upper bound on the girth of the family of graphs lifted from a given base graph with a given lifting degree. The upper bounds derived here, which are applicable to both regular and irregular base graphs with no parallel edges, are in some cases more general and in some other cases tighter than the existing bounds. The results presented in this work can be used to design cyclic liftings with relatively small degree and relatively large girth. As an example, we present new QC protograph LDPC code constructions with girth 8 using fully connected base graphs. These constructions provide upper bounds on the lifting degree required for achieving girth 8 using fully connected base graphs.

IEEE Transactions on Information TheoryMar 6, 201389 citations

Lower Bounds on the Lifting Degree of QC-LDPC Codes by Difference Matrices

Farzane Amirzade, Mohammad‐Reza Sadeghi

In this paper, we define two “difference matrices” which correspond to an exponent matrix. We present necessary and sufficient conditions for these difference matrices to have quasi-cyclic low-density parity-check codes (QC-LDPC) codes with a certain girth. We achieve all non-isomorphic QC-LDPC codes with the shortest length, girth 6, the column weight, m = 4, and the row weight, 5 ≤ n ≤ 11. Moreover, a method to obtain an exponent matrix with girth 10 is presented which reduces the complexity of the search algorithm. If the first row and the first column of the exponent matrix are all-zero, then by applying our method we do not need to test Fossorier's lemma to avoid 6-cycles and 8-cycles. For girth 10, we also provide a lower bound on the lifting degree which is tighter than the existing bound. For girth 12, a new lower bound on the lifting degree is achieved.

IEEE AccessJan 1, 201828 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.3906IEEE Transactions on Information TheoryJun 14, 201330 citations