American Institute of Mathematical Sciences

Advanced
November  2011, 5(4): 555-570. doi: 10.3934/amc.2011.5.555

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, Israel, Israel

Received  January 2010 Revised  September 2011 Published  November 2011

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: error performance., linear-programming (LP) decoding, repeat-accumulate codes, upper bound, Coding theory.
Mathematics Subject Classification: 68P30, 94B70, 90C0.
Citation: Idan Goldenberg, David Burshtein. Error bounds for repeat-accumulate codes decoded via linear programming. Advances in Mathematics of Communications, 2011, 5 (4) : 555-570. doi: 10.3934/amc.2011.5.555
References:
[1]

C. Berrou, A. Glavieux and P. Thitimajshima, Near Shannon limit errorcorrecting coding and decoding: turbo codes,, in, (1993), 1064.  doi: 10.1109/ICC.1993.397441.  Google Scholar

[2]

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

[3]

D. Burshtein, Iterative approximate linear programming decoding of LDPC codes with linear complexity,, IEEE Trans. Inform. Theory, 55 (2009), 4835.  doi: 10.1109/TIT.2009.2030477.  Google Scholar

[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.  doi: 10.1109/TIT.2008.926452.  Google Scholar

[5]

D. Divsalar, H. Jin and R. J. McEliece, Coding theorems for Turbo-like codes,, in, (1998), 201.   Google Scholar

[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.   Google Scholar

[7]

J. Feldman, "Decoding Error-Correcting Codes via Linear Programming'',, Ph.D thesis, (2003).   Google Scholar

[8]

J. Feldman and D. R. Karger, Decoding turbo-like codes via linear programming,, in, (2002).  doi: 10.1109/SFCS.2002.1181948.  Google Scholar

[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.  doi: 10.1109/TIT.2006.887523.  Google Scholar

[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.  doi: 10.1109/TIT.2004.842696.  Google Scholar

[11]

R. G. Gallager, "Low-Density Parity-Check Codes,'', MIT Press, (1963).   Google Scholar

[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.  doi: 10.1109/TIT.2004.839509.  Google Scholar

[13]

H. Jin and R. J. McEliece, Irregular repeat-accumlate codes,, in, (2000), 1.   Google Scholar

[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.  doi: 10.1109/TIT.2005.850079.  Google Scholar

[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.  doi: 10.1109/TIT.2007.899563.  Google Scholar

[16]

P. O. Vontobel and R. Koetter, Lower bounds on the minimum pseudoweight of linear codes,, in, (2004).   Google Scholar

[17]

P. O. Vontobel and R. Koetter, Towards low-complexity linear-programming decoding,, in, (2006).   Google Scholar

show all references

References:
[1]

C. Berrou, A. Glavieux and P. Thitimajshima, Near Shannon limit errorcorrecting coding and decoding: turbo codes,, in, (1993), 1064.  doi: 10.1109/ICC.1993.397441.  Google Scholar

[2]

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

[3]

D. Burshtein, Iterative approximate linear programming decoding of LDPC codes with linear complexity,, IEEE Trans. Inform. Theory, 55 (2009), 4835.  doi: 10.1109/TIT.2009.2030477.  Google Scholar

[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.  doi: 10.1109/TIT.2008.926452.  Google Scholar

[5]

D. Divsalar, H. Jin and R. J. McEliece, Coding theorems for Turbo-like codes,, in, (1998), 201.   Google Scholar

[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.   Google Scholar

[7]

J. Feldman, "Decoding Error-Correcting Codes via Linear Programming'',, Ph.D thesis, (2003).   Google Scholar

[8]

J. Feldman and D. R. Karger, Decoding turbo-like codes via linear programming,, in, (2002).  doi: 10.1109/SFCS.2002.1181948.  Google Scholar

[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.  doi: 10.1109/TIT.2006.887523.  Google Scholar

[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.  doi: 10.1109/TIT.2004.842696.  Google Scholar

[11]

R. G. Gallager, "Low-Density Parity-Check Codes,'', MIT Press, (1963).   Google Scholar

[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.  doi: 10.1109/TIT.2004.839509.  Google Scholar

[13]

H. Jin and R. J. McEliece, Irregular repeat-accumlate codes,, in, (2000), 1.   Google Scholar

[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.  doi: 10.1109/TIT.2005.850079.  Google Scholar

[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.  doi: 10.1109/TIT.2007.899563.  Google Scholar

[16]

P. O. Vontobel and R. Koetter, Lower bounds on the minimum pseudoweight of linear codes,, in, (2004).   Google Scholar

[17]

P. O. Vontobel and R. Koetter, Towards low-complexity linear-programming decoding,, in, (2006).   Google Scholar

[1]

Beniamin Mounits, Tuvi Etzion, Simon Litsyn. New upper bounds on codes via association schemes and linear programming. Advances in Mathematics of Communications, 2007, 1 (2) : 173-195. doi: 10.3934/amc.2007.1.173
[2]

Sun-Sig Byun, Hongbin Chen, Mijoung Kim, Lihe Wang. Lp regularity theory for linear elliptic systems. Discrete & Continuous Dynamical Systems - A, 2007, 18 (1) : 121-134. doi: 10.3934/dcds.2007.18.121
[3]

Yael Ben-Haim, Simon Litsyn. A new upper bound on the rate of non-binary codes. Advances in Mathematics of Communications, 2007, 1 (1) : 83-92. doi: 10.3934/amc.2007.1.83
[4]

Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323
[5]

Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2020, 14 (2) : 333-357. doi: 10.3934/amc.2020024
[6]

J. De Beule, K. Metsch, L. Storme. Characterization results on weighted minihypers and on linear codes meeting the Griesmer bound. Advances in Mathematics of Communications, 2008, 2 (3) : 261-272. doi: 10.3934/amc.2008.2.261
[7]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007
[8]

Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443
[9]

Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505
[10]

Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433
[11]

Min Ye, Alexander Barg. Polar codes for distributed hierarchical source coding. Advances in Mathematics of Communications, 2015, 9 (1) : 87-103. doi: 10.3934/amc.2015.9.87
[12]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[13]

Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385
[14]

Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83
[15]

Carla Mascia, Giancarlo Rinaldo, Massimiliano Sala. Hilbert quasi-polynomial for order domains and application to coding theory. Advances in Mathematics of Communications, 2018, 12 (2) : 287-301. doi: 10.3934/amc.2018018
[16]

Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $ k $-error linear complexity for $ p^n $-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018
[17]

Alain Miranville, Xiaoming Wang. Upper bound on the dimension of the attractor for nonhomogeneous Navier-Stokes equations. Discrete & Continuous Dynamical Systems - A, 1996, 2 (1) : 95-110. doi: 10.3934/dcds.1996.2.95
[18]

Gang Meng. The optimal upper bound for the first eigenvalue of the fourth order equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (12) : 6369-6382. doi: 10.3934/dcds.2017276
[19]

S. E. Kuznetsov. An upper bound for positive solutions of the equation \Delta u=u^\alpha. Electronic Research Announcements, 2004, 10: 103-112.

[20]

Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (36)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences