Advanced Search
Article Contents
Article Contents

Error bounds for repeat-accumulate codes decoded via linear programming

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: 68P30, 94B70, 90C05.


    \begin{equation} \\ \end{equation}
  • [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.


    N. Biggs, Constructions for cubic graphs with large girth, Electronic J. Combinatorics, 5 (1998), #A1.


    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.


    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.


    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.


    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.


    J. Feldman, "Decoding Error-Correcting Codes via Linear Programming'', Ph.D thesis, MIT, 2003.


    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.


    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.


    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.


    R. G. Gallager, "Low-Density Parity-Check Codes,'' MIT Press, Cambridge, MA, USA, 1963.


    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.


    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.


    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.


    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.


    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).


    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

  • 加载中

Article Metrics

HTML views() PDF downloads(121) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint