Upper Bounds and Parity Considerations

Harry A. Mavromatis

Stefan Hollands, Ko Sanders

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.

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.

Scott Aaronson, Andris Ambainis, Kaspars Balodis +1 more