arXiv:2001.07969 · IEEE International Symposium on Information Theory (ISIT)

Construction of Rate (n — 1 )/n Non-Binary LDPC Convolutional Codes via Difference Triangle Sets

Gianira N. Alfarano, Julia Lieb, Joachim Rosenthal

Published Jun 1, 2020• 2 citations

Abstract

This paper provides a construction of non-binary LDPC convolutional codes, which generalizes the work of Robinson and Bernstein. The sets of integers forming an (n - 1,w)- difference triangle set are used as supports of the columns of rate (n - 1)/n convolutional codes. If the field size is large enough, the Tanner graph associated to the sliding parity-check matrix of the code is free from 4 and 6-cycles not satisfying the full rank condition. This is important for improving the performance of a code and avoiding the presence of low-weight codewords and absorbing sets. The parameters of the convolutional code are shown to be determined by the parameters of the underlying difference triangle set. In particular, the free distance of the code is related to w and the degree of the code is linked to the "scope" of the difference triangle set. Hence, the problem of finding families of difference triangle set with minimum scope is equivalent to find convolutional codes with small degree.

DOI: 10.1109/isit44484.2020.9174510

Related papers

Analysis of LDPC convolutional codes derived from LDPC block codes

Alí Emre Pusane

LDPC convolutional codes have been shown to be capable of achieving the same capacity-approaching performance as LDPC block codes with iterative message passing decoding. In this dissertation, we present several methods of deriving families of time-varying and time-invariant LDPC convolutional codes from LDPC block codes. We demonstrate that the derived LDPC convolutional codes significantly outperform the underlying LDPC block codes, and we investigate the reasons for these 'convolutional gains'. It is well known that cycles in the Tanner graph representation of a sparse code affect the iterative decoding algorithm, with short cycles generally pushing its performance further away from optimum. Hence it is common practice to design codes that do not contain short cycles, so as to obtain independent messages in at least the initial iterations of the decoding process. We show that the derived LDPC convolutional codes have better graph-cycle properties than their block code counterparts. In particular, we show that the unwrapping process that is used to derive LDPC convolutional codes from LDPC block codes can 'break' some cycles of the underlying LDPC block code, but cannot create any shorter cycles. We prove that any cycle in an LDPC convolutional code always maps to a cycle of the same or smaller length in the underlying LDPC block code. Minimum distance is an important code design parameter when the channel quality is high, since codewords that are minimum distance apart are the most likely to cause errors with ML or near-ML decoding. In this case, the minimum distance determines the so-called error floor behavior in the performance curve corresponding to high channel signal-to-noise ratios. Thus studying the minimum distance properties of a code family gives insight into its error floor behavior. We use asymptotic methods to calculate a lower bound on the free distance of several ensembles of asymptotically good LDPC convolutional codes derived from protograph-based LDPC block codes. Further, we show that the free distance to constraint length ratio of the LDPC convolutional codes exceeds the minimum distance to block length ratio of the corresponding LDPC block codes. Message-passing iterative decoders for LDPC block codes are known to be subject to decoding failures due to so-called pseudo-codewords. These failures can cause the large signal-to-noise ratio performance of message-passing iterative decoding to be worse than that predicted by the maximum-likelihood decoding union bound. We address the pseudo-codeword problem from the convolutional code perspective. In particular, we show that the minimum pseudo-weight of an LDPC convolutional code is at least as large as the minimum pseudo-weight of an underlying LDPC block code. This result, which parallels a well-known relationship between the minimum Hamming weight of convolutional codes and the minimum Hamming weight of their quasi-cyclic counterparts, is due to the fact that every pseudo-codeword in the LDPC convolutional code induces a pseudo-codeword in the LDPC block code with pseudo-weight no larger than that of the convolutional pseudo-codeword. More generally, we demonstrate a difference in the weight spectra of LDPC block and convolutional codes that leads to improved performance at low-to-moderate signal-to-noise ratios for the convolutional codes, a conclusion supported by simulation results.

Sep 15, 20221 citation

A Class of Low-Density Parity-Check Convolutional Codes Based on Difference Families

Yucheng He, Christian Cardinal, David Haccoun

An algebraic construction for a class of low-density parity-check (LDPC) convolutional codes is presented on the basis of difference families associated with the code generator matrix. It can be shown that these codes have girth of at least 10 on the Tanner graph which is independent of either the size of the code generator matrix or the minimum Hamming distance of the codes. The code construction guarantees the independence of the messages exchanged in the belief propagation decoding process during two successive decoding iterations. Computer simulations show that over the additive white Gaussian noise channel, the best error performance of these codes at moderate signal-to- noise ratio values is practically obtained using only three to five iterations.

International Conference on CommunicationsJan 1, 20082 citations

Low-rate LDPC convolutional codes with short constraint length

Marco Baldi, Giovanni Cancellieri

We study a family of LDPC convolutional codes having code rate of the type 1/a, and analyze their minimum distance and local cycles length properties. We consider some low weight codewords that are known from the literature, and are easily obtained from the symbolic parity-check matrix of these codes. Starting from the structure of such codewords, we follow a twofold approach: i) we exploit graph-based techniques to design these codes with the aim to maximize their minimum distance while keeping the syndrome former constraint length as small as possible and ii) we provide a simple form for their generator matrices that allows to perform exhaustive searches through which we verify that the code design actually reaches its target. We also estimate the normalized minimum distance multiplicity for the codes we consider, and introduce the notion of symbolic graphs as a new tool to study the code properties.

International Conference on Software, Telecommunications and Computer Networks (SoftCOM)Sep 1, 20155 citations

Computing the Minimum Distance of Nonbinary LDPC Codes

Lei Liu, Jie Huang, Wuyang Zhou +1 more

Finding the minimum distance of low-density-parity-check (LDPC) codes is an NP-hard problem. Different from all existing works that focus on binary LDPC codes, we in this paper aim to compute the minimum distance of nonbinary LDPC codes, motivated by the fact that operating in a large Galois field provides one important degree of freedom to achieve both good waterfall and error-floor performance. Our method is based on the existing nearest nonzero codeword search (NNCS) method, but several modifications are incorporated for nonbinary LDPC codes, including the modified error impulse pattern, the dithering method, and the nonbinary decoder. Numerical results on the estimated minimum distances show that a code's minimum distance can be increased by careful selection of nonzero elements of the parity check matrix, or by increasing the mean column weight, or by increasing the size of the Galois field. These results support observations that have been made based on simulated performance in the literature. Finally, we provide an upper bound on the minimum distance for nonbinary quasi-cyclic LDPC codes.

IEEE Transactions on CommunicationsJul 1, 20128 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, 202230 citations

Construction of nonbinary quasi-cyclic LDPC cycle codes based on singer perfect difference set

Chao Chen, Baoming Bai, Xinmei Wang

A low-density parity-check (LDPC) code whose parity-check matrix consists of weight-2 columns is known as a cycle code. In this letter, we propose a construction of nonbinary quasi-cyclic (QC) LDPC cycle codes based on Singer perfect difference set. The Tanner graph has girth 12 and the code length achieves the Gallager lower bound. We further show that constructed codes have exactly a minimum symbol Hamming distance 6. Simulation results show that the proposed codes perform better than random nonbinary LDPC cycle codes.

IEEE Communications LettersFeb 1, 201027 citations