Error bounds for repeat-accumulate codes decoded via linear programming

Idan Goldenberg; David Burshtein

doi:10.3934/amc.2011.5.555

Article Contents

2011, Volume 5, Issue 4: 555-570. Doi: 10.3934/amc.2011.5.555

This issue Previous Article Next Article Codes over $\mathbb{Z}_{2^k}$, Gray map and self-dual codes

Error bounds for repeat-accumulate codes decoded via linear programming

Idan Goldenberg^1, and
David Burshtein^1,

1.
School of Electrical Engineering, Tel-Aviv University, Tel-Aviv 69978

Received: December 31, 2009

Revised: August 31, 2011

Published: October 2011

Abstract Related Papers Cited by

Abstract

We examine regular and irregular repeat-accumulate (RA) codes with repetition degrees which are all even. For these codes and with a particular choice of an interleaver, we give an upper bound on the decoding error probability of a linear-programming based decoder which is an inverse polynomial in the block length. Our bound is valid for any memoryless, binary-input, output-symmetric (MBIOS) channel. This result generalizes the bound derived by Feldman et al., which was for regular RA($2$) codes.

Keywords:

Mathematics Subject Classification: 68P30, 94B70, 90C05.

Citation:

Related Papers

Cited by

References

[1]	C. Berrou, A. Glavieux and P. Thitimajshima, Near Shannon limit errorcorrecting coding and decoding: turbo codes, in "Proc. 1993 IEEE International Conference on Communications,'' Geneva, Switzerland, (1993), 1064-1070.doi: 10.1109/ICC.1993.397441.
[2]	N. Biggs, Constructions for cubic graphs with large girth, Electronic J. Combinatorics, 5 (1998), #A1.
[3]	D. Burshtein, Iterative approximate linear programming decoding of LDPC codes with linear complexity, IEEE Trans. Inform. Theory, 55 (2009), 4835-4859.doi: 10.1109/TIT.2009.2030477.
[4]	C. Daskalakis, A. G. Dimakis, R. M. Karp and M. J. Wainwright, Probabilistic analysis of linear programming decoding, IEEE Trans. Inform. Theory, 54 (2008), 3565-3578.doi: 10.1109/TIT.2008.926452.
[5]	D. Divsalar, H. Jin and R. J. McEliece, Coding theorems for Turbo-like codes, in "36th Allerton Conference on Communications, Control, and Computing,'' (1998), 201-210.
[6]	P. Erdős and H. Sachs, Reguläre Graphen gegebene Taillenweite mit minimaler Knotenzahl, Wiss. Z. Univ. Hall Martin Luther Univ. Halle-Wittenberg Math. Natur. Reine, 12 (1963), 251-257.
[7]	J. Feldman, "Decoding Error-Correcting Codes via Linear Programming'', Ph.D thesis, MIT, 2003.
[8]	J. Feldman and D. R. Karger, Decoding turbo-like codes via linear programming, in "Proc. 43rd annual IEEE Symposium on Foundations of Computer Science (FOCS),'' (2002).doi: 10.1109/SFCS.2002.1181948.
[9]	J. Feldman, T. Malkin, R. A. Servedio, C. Stein and M. J. Wainwright, LP decoding corrects a constant fraction of errors, IEEE Trans. Inform. Theory, 53 (2007), 82-89.doi: 10.1109/TIT.2006.887523.
[10]	J. Feldman, M. J. Wainwright and D. R. Karger, Using linear programming to decode binary linear codes, IEEE Trans. Inform. Theory, 51 (2005), 954-972.doi: 10.1109/TIT.2004.842696.
[11]	R. G. Gallager, "Low-Density Parity-Check Codes,'' MIT Press, Cambridge, MA, USA, 1963.
[12]	N. Halabi and G. Even, Improved bounds on the word error probability of RA($2$) codes with linear-programming-based decoding, IEEE Trans. Inform. Theory, 51 (2005), 265-280.doi: 10.1109/TIT.2004.839509.
[13]	H. Jin and R. J. McEliece, Irregular repeat-accumlate codes, in "Proceedings Second International Conference on Turbo Codes and Related Topics,'' Brest, France, (2000), 1-8.
[14]	H. D. Pfister, I. Sason and R. Urbanke, Capacity-achieving ensembles for the binary erasure channel with bounded complexity, IEEE Trans. Inform. Theory, 51 (2005), 2352-2379.doi: 10.1109/TIT.2005.850079.
[15]	R. Smarandache and P. O. Vontobel, Pseudo-codeword analysis of Tanner fraphs from projective and Euclidean planes, IEEE Trans. Inform. Theory, 53 (2007), 2376-2393.doi: 10.1109/TIT.2007.899563.
[16]	P. O. Vontobel and R. Koetter, Lower bounds on the minimum pseudoweight of linear codes, in "Proceedings of the 2004 International Symposium on Information Theory,'' (2004).
[17]	P. O. Vontobel and R. Koetter, Towards low-complexity linear-programming decoding, in "Proc. 4th Int. Symposium on Turbo Codes and Related Topics,'' Munich, Germany, (2006); preprint, arXiv:cs/0602088v1