International Conference on Software, Telecommunications and Computer Networks (SoftCOM)

Low-rate LDPC convolutional codes with short constraint length

Marco Baldi, Giovanni Cancellieri

Published Sep 1, 2015• 5 citations

Abstract

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.

DOI: 10.1109/softcom.2015.7314104

Related papers

Design of spatially coupled LDPC codes based on symbolic hyper-graphs

Massimo Battaglioni, Marco Baldi, Giovanni Cancellieri

We consider a special family of spatially coupled low-density parity-check (LDPC) codes known as LDPC convolutional codes and propose a design technique based on symbolic hyper-graphs aimed at achieving good codes with small syndrome former memory order. We define conditions on the minimum syndrome former memory order that must be imposed in order to avoid short local cycles in the codes Tanner graphs and to achieve good minimum distance. Code design examples are provided, accompanied by error rate performance assessments based on Montecarlo simulations.

International Conference on Software, Telecommunications and Computer Networks (SoftCOM)Sep 1, 20161 citation

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

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

Time-invariant spatially coupled low-density parity-check codes with small constraint length

Marco Baldi, Massimo Battaglioni, Franco Chiaraluce +1 more

We consider a special family of spatially coupled low-density parity-check (SC-LDPC) codes, that is, time-invariant low-density parity-check convolutional (LDPCC) codes, which are known in the literature for a long time. Codes of this kind are usually designed by starting from quasi-cyclic (QC) block codes, and applying suitable unwrapping procedures. We show that, by directly designing the LDPCC code syndrome former matrix without the constraints of the underlying QC block code, it is possible to achieve smaller constraint lengths with respect to the best solutions available in the literature. We also find theoretical lower bounds on the syndrome former constraint length for codes with a specified minimum length of the local cycles in their Tanner graphs. For this purpose, we exploit a new approach based on a numerical representation of the syndrome former matrix, which generalizes over a technique we already used to study a special subclass of the codes here considered.

arXiv:1605.05560IEEE International Black Sea Conference on Communications and NetworkingJan 1, 20164 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 CommunicationsOct 1, 20202 citations

Type-III LDPC Convolutional Codes

Morteza Esmaeili, Mohammad Gholami

A class of geometrically structured quasi-cyclic low-density parity-check codes with a cylinder structure graph and girth 12 is considered. The parity-check matrix of such a code consists of blocks of zeros and cir-culant permutation matrices. A class of convolutional codes is assigned to these codes. The convolutional form generator matrix of these codes is obtained by elementary row and column operations. It is shown that the free distance of the obtained convolutional codes is equal to the minimum distance of their bock code counterparts.

Jan 1, 20091 citation