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

International Conference on Systems, Signals and Image Processing

Girth analysis of polynomial-based time-invariant LDPC convolutional codes

Hua Ren Zhou, Norbert Goertz

Published Apr 11, 2012• 8 citations
OpenAlex

Abstract

Low-Density Parity-Check convolutional codes (LDPCccs) can be efficiently decoded by a pipelined sub-optimal Sum Product Algorithm. The latter may suffer, however, from convergence problems, due to cycles in the Tanner graph. To improve the decoding performance, we analyze the cycle properties, based on the connections between monomials in the polynomial syndrome former (transposed parity-check matrix in polynomial form) of time-invariant LDPCccs. Due to specific structures in the polynomial syndrome former, some cycles are unavoidable no matter what monomials are placed in the polynomial syndrome former. It is shown that large-weight entries in the polynomial syndrome former lead to small girth, while monomial or empty entries, which can break short unavoidable cycles, may result in large girth. A novel algorithm is proposed to generate “good” LDPCccs with respect to their cycle properties: destructive structures in the polynomial syndrome former leading to small girth are systematically avoided.

Related papers

Unavoidable Cycles in Polynomial-Based Time-Invariant LDPC Convolutional Codes

Hua Ren Zhou, Norbert Goertz

Low-Density Parity-Check convolutional codes (LD- PCccs) are very interesting for practical error-correction coding in wireless transmission as they have excellent performance and at the same time they allow for variable block size with low complexity encoding and decoding. As for all LDPC codes that are decoded by the sub-optimal (but highly efficient) Sum Product Algorithm, the cycles in the code graph are very important for the practical performance of the coding scheme. Time-invariant LDPCccs can be defined by a polynomial syndrome former (transposed parity-check matrix in polynomial form), that can be derived from corresponding Quasi-Cyclic (QC) LDPC block codes. Given the polynomial syndrome former with certain structures, unavoidable cycles with lengths ranging from 6 to 12 will be shown to exist. We provide some rules for designing good codes with respect to the shortest cycle in the code-graph, the girth of the code, which is a crucial parameter for its decoding performance.

Wireless Conference - Sustainable Wireless Technologies , European•Apr 27, 2011•5 citations

Cycle analysis of time-variant LDPC convolutional codes

Hua Ren Zhou, Norbert Goertz

Time-variant Low-Density Parity-Check convolutional codes (LDPCccs) can be derived from unwrapping Quasi-Cyclic (QC) LDPC block codes. Rather than analyzing cycles in a large-scale time-domain parity check matrix, we propose a new way to describe cycle properties in compact form by a “polynomial syndrome former”, i.e., a syndrome former in an equivalent polynomial representation. According to the relationship of cycle structures between time- and polynomial-domain syndrome formers, we present a cycle counter algorithm to analyze cycle properties in time-variant LDPCccs as well as in time-invariant LDPCccs.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2010•8 citations

Cycle analysis of time-invariant LDPC convolutional codes

Hua Ren Zhou, Norbert Goertz

Time-invariant low-density parity-check convolutional codes (LDPCccs) can be constructed from a polynomial form of a parity-check matrix that defines quasi-cyclic LDPC block codes based on circulant matrices. Based on this polynomial matrix, we discuss the relationships between the polynomial domain and the time domain parity-check and syndrome former matrices with respect to cycle properties. We present a novel, simple way to describe cycles in the polynomial version of the syndrome former matrix and we exploit this concept in a new cycle counting algorithm.

•Jan 1, 2010•13 citations

Analysis and elimination of short cycles in LDPC convolutional codes

Ziqin Su, Qiaoyong Qiu, Hua Ren Zhou

Time-invariant low-density parity-check convolutional codes (TI LDPC-CCs) can be represented by a polynomial-domain parity-check matrix derived from the corresponding quasi-cyclic (QC) LDPC block codes (LDPC-BCs), while time-varying (TV) LDPC-CCs can be obtained by unwrapping the parity-check matrices of LDPC-BCs. The cycle enumerators for TI and TV LDPC-CCs are compared. Based on the analysis of the graphical structures of short cycles in HT(D), we introduce a method of designing the polynomial syndrome former matrix HCRT(D) for LDPC-CCs. It eliminates short cycles and shows improved decoding performance on an additive white Gaussian noise (AWGN) channel with lower bit error ratio (BER) curves.

IEEE International Conference on Computer and Communications (ICCC)•Oct 1, 2016•3 citations

Design and Analysis of LDPC Convolutional Codes

Arvind Sridharan

Low-density parity-check (LDPC) block codes invented by Gallager in 1962 achieve exceptional error performance on a wide variety of communication channels. LDPC convolutional codes are the convolutional counterparts of LDPC block codes. This dissertation describes techniques for the design of LDPC convolutional codes, and analyzes their distance properties and iterative decoding convergence thresholds. The construction of time invariant LDPC convolutional codes by unwrapping the Tanner graph of algebraically constructed quasi-cyclic LDPC codes is described. The convolutional codes outperform the quasi-cyclic codes from which they are derived. The design of parity-check matrices for time invariant LDPC convolutional codes by the polynomial extension of a base matrix is proposed. An upper bound on free distance, proving that time invariant LDPC codes are not asymptotically good, is obtained. The Tanner graph is used to describe a pipelined message passing based iterative decoder for LDPC convolutional codes that outputs decoding results continuously. The performance of LDPC block and convolutional codes are compared for fixed decoding parameters like computational complexity, processor complexity, and decoding delay. In each case, the LDPC convolutional code performance is at least as good as that of LDPC block codes. An analog circuit to implement pipelined decoding of LDPC convolutional codes is proposed. The distance properties of a permutation matrix based (time varying) ensemble of (J,K) regular LDPC convolutional codes is investigated. It is proved that these codes (for J > 2) have free distance increasing linearly with constraint length, i.e., they are asymptotically good. Further, the asymptotic free distance to constraint length ratio for the convolutional codes is several times larger than the minimum distance to block length ratio for corresponding LDPC block codes. Iterative decoding of terminated LDPC convolutional codes, based on the ensemble mentioned above, is analyzed, assuming transmission over a binary erasure channel. The structured irregularity of the codes leads to significantly better convergence thresholds compared to corresponding LDPC block codes. At the calculated thresholds, both the bit and block error probability can be made arbitrarily small. The results obtained suggest that the thresholds approach capacity with increasing J.

•Sep 15, 2022•30 citations

Ensemble of high performance structured binary convolutional LDPC codes with moderate rates

Liwei Mu

An algebraic construction methodology is proposed to design binary time-invariant convolutional low-density parity-check (LDPC) codes. Assisted by a proposed partial search algorithm, the polynomialform parity-check matrix of the time-invariant convolutional LDPC code is derived by combining some special codewords of an (n, 2, n - 1) code. The achieved convolutional LDPC codes possess the characteristics of comparatively large girth and given syndrome former memory. The objective of our design is to enable the time-invariant convolutional LDPC codes the advantages of excellent error performance and fast encoding. In particular, the error performance of the proposed convolutional LDPC code with small constraint length is superior to most existing convolutional LDPC codes.

China Communications•Oct 1, 2020•2 citations
Low-Density Parity-Check convolutional codes (LDPCccs) can be efficiently decoded by a pipelined sub-optimal Sum Product Algorithm. The latter may suffer, however, from convergence problems, due to cycles in the Tanner graph. To improve the decoding performance, we analyze the cycle properties, based on the connections between monomials in the polynomial syndrome former (transposed parity-check matrix in polynomial form) of time-invariant LDPCccs. Due to specific structures in the polynomial syndrome former, some cycles are unavoidable no matter what monomials are placed in the polynomial syndrome former. It is shown that large-weight entries in the polynomial syndrome former lead to small girth, while monomial or empty entries, which can break short unavoidable cycles, may result in large girth. A novel algorithm is proposed to generate “good” LDPCccs with respect to their cycle properties: destructive structures in the polynomial syndrome former leading to small girth are systematically avoided.
Low-Density Parity-Check convolutional codes (LD- PCccs) are very interesting for practical error-correction coding in wireless transmission as they have excellent performance and at the same time they allow for variable block size with low complexity encoding and decoding. As for all LDPC codes that are decoded by the sub-optimal (but highly efficient) Sum Product Algorithm, the cycles in the code graph are very important for the practical performance of the coding scheme. Time-invariant LDPCccs can be defined by a polynomial syndrome former (transposed parity-check matrix in polynomial form), that can be derived from corresponding Quasi-Cyclic (QC) LDPC block codes. Given the polynomial syndrome former with certain structures, unavoidable cycles with lengths ranging from 6 to 12 will be shown to exist. We provide some rules for designing good codes with respect to the shortest cycle in the code-graph, the girth of the code, which is a crucial parameter for its decoding performance.
Time-variant Low-Density Parity-Check convolutional codes (LDPCccs) can be derived from unwrapping Quasi-Cyclic (QC) LDPC block codes. Rather than analyzing cycles in a large-scale time-domain parity check matrix, we propose a new way to describe cycle properties in compact form by a “polynomial syndrome former”, i.e., a syndrome former in an equivalent polynomial representation. According to the relationship of cycle structures between time- and polynomial-domain syndrome formers, we present a cycle counter algorithm to analyze cycle properties in time-variant LDPCccs as well as in time-invariant LDPCccs.
Time-invariant low-density parity-check convolutional codes (LDPCccs) can be constructed from a polynomial form of a parity-check matrix that defines quasi-cyclic LDPC block codes based on circulant matrices. Based on this polynomial matrix, we discuss the relationships between the polynomial domain and the time domain parity-check and syndrome former matrices with respect to cycle properties. We present a novel, simple way to describe cycles in the polynomial version of the syndrome former matrix and we exploit this concept in a new cycle counting algorithm.
Time-invariant low-density parity-check convolutional codes (TI LDPC-CCs) can be represented by a polynomial-domain parity-check matrix derived from the corresponding quasi-cyclic (QC) LDPC block codes (LDPC-BCs), while time-varying (TV) LDPC-CCs can be obtained by unwrapping the parity-check matrices of LDPC-BCs. The cycle enumerators for TI and TV LDPC-CCs are compared. Based on the analysis of the graphical structures of short cycles in HT(D), we introduce a method of designing the polynomial syndrome former matrix HCRT(D) for LDPC-CCs. It eliminates short cycles and shows improved decoding performance on an additive white Gaussian noise (AWGN) channel with lower bit error ratio (BER) curves.
Low-density parity-check (LDPC) block codes invented by Gallager in 1962 achieve exceptional error performance on a wide variety of communication channels. LDPC convolutional codes are the convolutional counterparts of LDPC block codes. This dissertation describes techniques for the design of LDPC convolutional codes, and analyzes their distance properties and iterative decoding convergence thresholds. The construction of time invariant LDPC convolutional codes by unwrapping the Tanner graph of algebraically constructed quasi-cyclic LDPC codes is described. The convolutional codes outperform the quasi-cyclic codes from which they are derived. The design of parity-check matrices for time invariant LDPC convolutional codes by the polynomial extension of a base matrix is proposed. An upper bound on free distance, proving that time invariant LDPC codes are not asymptotically good, is obtained. The Tanner graph is used to describe a pipelined message passing based iterative decoder for LDPC convolutional codes that outputs decoding results continuously. The performance of LDPC block and convolutional codes are compared for fixed decoding parameters like computational complexity, processor complexity, and decoding delay. In each case, the LDPC convolutional code performance is at least as good as that of LDPC block codes. An analog circuit to implement pipelined decoding of LDPC convolutional codes is proposed. The distance properties of a permutation matrix based (time varying) ensemble of (J,K) regular LDPC convolutional codes is investigated. It is proved that these codes (for J > 2) have free distance increasing linearly with constraint length, i.e., they are asymptotically good. Further, the asymptotic free distance to constraint length ratio for the convolutional codes is several times larger than the minimum distance to block length ratio for corresponding LDPC block codes. Iterative decoding of terminated LDPC convolutional codes, based on the ensemble mentioned above, is analyzed, assuming transmission over a binary erasure channel. The structured irregularity of the codes leads to significantly better convergence thresholds compared to corresponding LDPC block codes. At the calculated thresholds, both the bit and block error probability can be made arbitrarily small. The results obtained suggest that the thresholds approach capacity with increasing J.
An algebraic construction methodology is proposed to design binary time-invariant convolutional low-density parity-check (LDPC) codes. Assisted by a proposed partial search algorithm, the polynomialform parity-check matrix of the time-invariant convolutional LDPC code is derived by combining some special codewords of an (n, 2, n - 1) code. The achieved convolutional LDPC codes possess the characteristics of comparatively large girth and given syndrome former memory. The objective of our design is to enable the time-invariant convolutional LDPC codes the advantages of excellent error performance and fast encoding. In particular, the error performance of the proposed convolutional LDPC code with small constraint length is superior to most existing convolutional LDPC codes.