Upper Bounds and Parity Considerations

Harry A. Mavromatis

François Arnault, Philippe Gaborit, Wouter Rozendaal +2 more

We investigate the minimum distance of structured binary Low-Density Parity-Check (LDPC) codes whose parity-check matrices are of the form $ [ \mathbf{C} \, \vert \, \mathbf{M}] $ where $ \mathbf{C} $ is circulant and of column weight $ 2 $, and $ \mathbf{M} $ has fixed column weight $ r \geq 3 $ and row weight at least $ 1 $. These codes are of interest because they are LDPC codes which come with a natural linear-time encoding algorithm. We show that the minimum distance of these codes is in $ O(n^{\frac{r-2}{r-1} + \epsilon}) $, where $ n $ is the code length and $ \epsilon > 0 $ is arbitrarily small. This improves the previously known upper bound in $ O(n^{\frac{r-1}{r}}) $ on the minimum distance of such codes. Additionally, we show that the new upper bound also applies to the class of repeat-accumulate codes.

Stefan Hollands, Ko Sanders

V. Canivell, Pere Seglar

Igal Sason, Shlomo Shitz Shamai

In this letter, we study improved upper bounds on the performance of low density parity check codes over binary-input additive white Gaussian noise channels, assuming that the codes are maximum-likelihood decoded. The results demonstrate the phenomenal performance of the low density parity check codes.

Eirik Rosnes, Marcel Ambroze, Martin Tomlinson

In this work, we present an upper bound on the minimum distance of array low-density parity-check (LDPC) codes. An array LDPC code is a quasi-cyclic LDPC code specified by two integers q and m, where q is an odd prime and m ≤ q. In the literature, the minimum distance of these codes (denoted by d(q,m)) has been thoroughly studied for m ≤ 5. Both exact results, for small values of q and m, and general (i.e., independent of q) bounds have been established. For m ≤ 6, the best known minimum distance upper bound, derived by Mittelholzer (IEEE Int. Symp. Inf. Theory, Jun./Jul. 2002), is d(q, 6) ≤ 32. In this work, we derive an improved upper bound of d(q, 6) ≤ 20 by using the concept of a template support matrix of a codeword. The bound is tight with high probability in the sense that we have not been able to find codewords of strictly lower weight for several values of q using a minimum distance probabilistic algorithm. Finally, we provide new specific minimum distance results for m ≤ 6 and low-to-moderate values of q ≤ 79.