February  2014, 8(1): 1-20. doi: 10.3934/amc.2014.8.1

On multi-trial Forney-Kovalev decoding of concatenated codes

1. 

DCS, Ruhr-Universität Bochum, Universitätsstraße 150, 44780 Bochum, Germany

2. 

TAIT, Ulm University, Albert-Einstein-Allee 43, 89081, Ulm

3. 

ECE, University of Toronto, 10 King's College Road, Toronto M5S 3G4, ON, Canada

Received  January 2011 Revised  June 2013 Published  January 2014

A concatenated code $\mathcal{C} $ based on an inner code with Hamming distance $d^i$ and an outer code with Hamming distance $d^o$ is considered. An outer decoder that corrects $\varepsilon$ errors and $\theta$ erasures with high probability if $\lambda \varepsilon + \theta \le d^o - 1,$ where a real number $1<\lambda\le 2$ is the trade-off rate between errors and erasures for this decoder is used. In particular, an outer $l$-punctured RS code, i.e., a code over the field $\mathbb{F}_{q^{l }}$ of length $n^{o} < q$ with locators taken from the sub-field $\mathbb{F}_{q}$, where $l\in \{1,2,\ldots\}$ is considered. In this case, the trade-off is given by $\lambda=1+1/l$. An $m$-trial decoder, where after inner decoding, in each trial we erase an incremental number of symbols and decode using the outer decoder is proposed. The optimal erasing strategy and the error correcting radii of both fixed and adaptive erasing decoders are given.
    Our approach extends results of Forney and Kovalev (obtained for $\lambda=2$) to the whole given range of $\lambda$. For the fixed erasing strategy the error correcting radius approaches $\rho_F\approx\frac{d^i d^o}{2}(1-\frac{l^{-m}}{2})$ for large $d^o$. For the adaptive erasing strategy, the error correcting radius $\rho_A\approx\frac{d^i d^o}{2}(1-l^{-2m})$ quickly approaches $d^i d^o/2$ if $l$ or $m$ grows. The minimum number of trials required to reach an error correcting radius $d^i d^o/2$ is $m_A=\frac{1}{2}\left(\log_ld+1\right)$. This means that $2$ or $3$ trials are sufficient in many practical cases if $l>1$.
Citation: Anas Chaaban, Vladimir Sidorenko, Christian Senger. On multi-trial Forney-Kovalev decoding of concatenated codes. Advances in Mathematics of Communications, 2014, 8 (1) : 1-20. doi: 10.3934/amc.2014.8.1
References:
[1]

E. L. Blokh and V. V. Zyablov, Linear Concatenated Codes (in Russian),, Nauka, (1982).   Google Scholar

[2]

A. Chaaban, Some Aspects of Adaptive Decoding of Concatenated Codes,, Master Thesis, (2009).   Google Scholar

[3]

G. D. Forney Jr., Concatenated Codes,, MIT Press, (1966).   Google Scholar

[4]

G. D. Forney Jr., Generalized minimum distance decoding,, IEEE Trans. Inf. Theory, 12 (1966), 125.   Google Scholar

[5]

V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes,, IEEE Trans. Inf. Theory, 45 (1999), 1757.  doi: 10.1109/18.782097.  Google Scholar

[6]

R. Kötter, Fast generalized minimum-distance decoding of algebraic-geometry and Reed-Solomon codes,, IEEE Trans. Inf. Theory, 42 (1993), 721.  doi: 10.1109/18.490540.  Google Scholar

[7]

S. I. Kovalev, Two classes of minimum generalized distance decoding algorithms,, Probl. Pered. Inform., 22 (1986), 35.   Google Scholar

[8]

G. Schmidt, V. R. Sidorenko and M. Bossert, Collaborative decoding of interleaved Reed-Solomon codes and concatenated code designs,, IEEE Trans. Inf. Theory, 55 (2009), 2991.  doi: 10.1109/TIT.2009.2021308.  Google Scholar

[9]

C. Senger, Generalized Minimum Distance Decoding with Arbitrary Error-Erasure Tradeoff,, Dissertation, (2011).   Google Scholar

[10]

C. Senger, V. R. Sidorenko, M. Bossert and V. Zyablov, Multi-trial decoding of concatenated codes using fixed thresholds,, Probl. Inform. Transm., 46 (2010), 127.  doi: 10.1134/S0032946010020031.  Google Scholar

[11]

C. Senger, V. R. Sidorenko, M. Bossert and V. Zyablov, Optimal thresholds for GMD decoding with (L+1)/L-extended bounded distance decoders,, in Proc. 2010 IEEE Intern. Symp. Inform. Theory, (2010).   Google Scholar

[12]

C. Senger, V. R. Sidorenko and V. Zyablov, On generalized minimum distance decoding thresholds for the AWGN channel,, in Proc. XII Int. Symp. Probl. Redund. Inf. Control Systems, (2009).   Google Scholar

[13]

V. R. Sidorenko, A. Chaaban, C. Senger and M. Bossert, On extended Forney-Kovalev GMD decoding,, in Proc. 2009 IEEE Intern. Symp. Inform. Theory, (2009).  doi: 10.1109/ISIT.2009.5205900.  Google Scholar

[14]

V. R. Sidorenko, C. Senger, M. Bossert and V. Zyablov, Single-trial decoding of concatenated codes using fixed or adaptive erasing,, Adv. Math. Commun., 4 (2010), 49.  doi: 10.3934/amc.2010.4.49.  Google Scholar

[15]

V. R. Sidorenko, G. Schmidt and M. Bossert, Decoding punctured Reed-Solomon codes up to the Singleton bound,, in Proc. Int. ITG Conf. Source Channel Coding, (2008).   Google Scholar

[16]

U. K. Sorger, A new Reed-Solomon code decoding algorithm based on Newton's interpolation,, IEEE Trans. Inf. Theory, 39 (1993), 358.  doi: 10.1109/18.212267.  Google Scholar

[17]

M. Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound,, J. Complexity, 13 (1997), 180.  doi: 10.1006/jcom.1997.0439.  Google Scholar

[18]

J. H. Weber and K. A. S. Abdel-Ghaffar, Optimal decoding strategy for a simple concatenated coding scheme,, in IEEE Intern. Symp. Inform. Theory, (1997).  doi: 10.1109/ISIT.1997.613366.  Google Scholar

[19]

J. H. Weber and K. A. S. Abdel-Ghaffar, Reduced GMD decoding,, IEEE Trans. Inf. Theory, 49 (2003), 1013.  doi: 10.1109/TIT.2003.809504.  Google Scholar

[20]

J. H. Weber, V. R. Sidorenko, C. Senger and K. A. S. Abdel-Ghaffar, Asymptotic single-trial strategies for GMD decoding with arbitrary error-erasure tradeoff,, Probl. Inf. Transm., 48 (2012), 324.  doi: 10.1134/S0032946012040023.  Google Scholar

[21]

V. V. Zyablov, Optimization of concatenated decoding algorithms,, Probl. Pered. Inform., 9 (1973), 26.   Google Scholar

show all references

References:
[1]

E. L. Blokh and V. V. Zyablov, Linear Concatenated Codes (in Russian),, Nauka, (1982).   Google Scholar

[2]

A. Chaaban, Some Aspects of Adaptive Decoding of Concatenated Codes,, Master Thesis, (2009).   Google Scholar

[3]

G. D. Forney Jr., Concatenated Codes,, MIT Press, (1966).   Google Scholar

[4]

G. D. Forney Jr., Generalized minimum distance decoding,, IEEE Trans. Inf. Theory, 12 (1966), 125.   Google Scholar

[5]

V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes,, IEEE Trans. Inf. Theory, 45 (1999), 1757.  doi: 10.1109/18.782097.  Google Scholar

[6]

R. Kötter, Fast generalized minimum-distance decoding of algebraic-geometry and Reed-Solomon codes,, IEEE Trans. Inf. Theory, 42 (1993), 721.  doi: 10.1109/18.490540.  Google Scholar

[7]

S. I. Kovalev, Two classes of minimum generalized distance decoding algorithms,, Probl. Pered. Inform., 22 (1986), 35.   Google Scholar

[8]

G. Schmidt, V. R. Sidorenko and M. Bossert, Collaborative decoding of interleaved Reed-Solomon codes and concatenated code designs,, IEEE Trans. Inf. Theory, 55 (2009), 2991.  doi: 10.1109/TIT.2009.2021308.  Google Scholar

[9]

C. Senger, Generalized Minimum Distance Decoding with Arbitrary Error-Erasure Tradeoff,, Dissertation, (2011).   Google Scholar

[10]

C. Senger, V. R. Sidorenko, M. Bossert and V. Zyablov, Multi-trial decoding of concatenated codes using fixed thresholds,, Probl. Inform. Transm., 46 (2010), 127.  doi: 10.1134/S0032946010020031.  Google Scholar

[11]

C. Senger, V. R. Sidorenko, M. Bossert and V. Zyablov, Optimal thresholds for GMD decoding with (L+1)/L-extended bounded distance decoders,, in Proc. 2010 IEEE Intern. Symp. Inform. Theory, (2010).   Google Scholar

[12]

C. Senger, V. R. Sidorenko and V. Zyablov, On generalized minimum distance decoding thresholds for the AWGN channel,, in Proc. XII Int. Symp. Probl. Redund. Inf. Control Systems, (2009).   Google Scholar

[13]

V. R. Sidorenko, A. Chaaban, C. Senger and M. Bossert, On extended Forney-Kovalev GMD decoding,, in Proc. 2009 IEEE Intern. Symp. Inform. Theory, (2009).  doi: 10.1109/ISIT.2009.5205900.  Google Scholar

[14]

V. R. Sidorenko, C. Senger, M. Bossert and V. Zyablov, Single-trial decoding of concatenated codes using fixed or adaptive erasing,, Adv. Math. Commun., 4 (2010), 49.  doi: 10.3934/amc.2010.4.49.  Google Scholar

[15]

V. R. Sidorenko, G. Schmidt and M. Bossert, Decoding punctured Reed-Solomon codes up to the Singleton bound,, in Proc. Int. ITG Conf. Source Channel Coding, (2008).   Google Scholar

[16]

U. K. Sorger, A new Reed-Solomon code decoding algorithm based on Newton's interpolation,, IEEE Trans. Inf. Theory, 39 (1993), 358.  doi: 10.1109/18.212267.  Google Scholar

[17]

M. Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound,, J. Complexity, 13 (1997), 180.  doi: 10.1006/jcom.1997.0439.  Google Scholar

[18]

J. H. Weber and K. A. S. Abdel-Ghaffar, Optimal decoding strategy for a simple concatenated coding scheme,, in IEEE Intern. Symp. Inform. Theory, (1997).  doi: 10.1109/ISIT.1997.613366.  Google Scholar

[19]

J. H. Weber and K. A. S. Abdel-Ghaffar, Reduced GMD decoding,, IEEE Trans. Inf. Theory, 49 (2003), 1013.  doi: 10.1109/TIT.2003.809504.  Google Scholar

[20]

J. H. Weber, V. R. Sidorenko, C. Senger and K. A. S. Abdel-Ghaffar, Asymptotic single-trial strategies for GMD decoding with arbitrary error-erasure tradeoff,, Probl. Inf. Transm., 48 (2012), 324.  doi: 10.1134/S0032946012040023.  Google Scholar

[21]

V. V. Zyablov, Optimization of concatenated decoding algorithms,, Probl. Pered. Inform., 9 (1973), 26.   Google Scholar

[1]

Vladimir Sidorenko, Christian Senger, Martin Bossert, Victor Zyablov. Single-trial decoding of concatenated codes using fixed or adaptive erasing. Advances in Mathematics of Communications, 2010, 4 (1) : 49-60. doi: 10.3934/amc.2010.4.49

[2]

Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83

[9]

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

[10]

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

[11]

Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179

[12]

Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419

[13]

Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485

[14]

Alexey Frolov, Victor Zyablov. On the multiple threshold decoding of LDPC codes over GF(q). Advances in Mathematics of Communications, 2017, 11 (1) : 123-137. doi: 10.3934/amc.2017007

[15]

Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259

[16]

Jonas Eriksson. A weight-based characterization of the set of correctable error patterns under list-of-2 decoding. Advances in Mathematics of Communications, 2007, 1 (3) : 331-356. doi: 10.3934/amc.2007.1.331

[17]

Robert F. Bailey, John N. Bray. Decoding the Mathieu group M12. Advances in Mathematics of Communications, 2007, 1 (4) : 477-487. doi: 10.3934/amc.2007.1.477

[18]

Deren Han, Hai Yang, Xiaoming Yuan. A practical trial-and-error implementation of marginal-cost pricing on networks. Journal of Industrial & Management Optimization, 2010, 6 (2) : 299-313. doi: 10.3934/jimo.2010.6.299

[19]

Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311

[20]

Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer. The secrecy capacity of the arbitrarily varying wiretap channel under list decoding. Advances in Mathematics of Communications, 2019, 13 (1) : 11-39. doi: 10.3934/amc.2019002

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (9)
  • HTML views (0)
  • Cited by (0)

[Back to Top]