On multi-trial Forney-Kovalev decoding of concatenated codes

Anas Chaaban; Vladimir Sidorenko; Christian Senger

doi:10.3934/amc.2014.8.1

Article Contents

2014, Volume 8, Issue 1: 1-20. Doi: 10.3934/amc.2014.8.1

This issue Previous Article Next Article Special bent and near-bent functions

On multi-trial Forney-Kovalev decoding of concatenated codes

1.
DCS, Ruhr-Universität Bochum, Universitätsstraße 150, 44780 Bochum
2.
TAIT, Ulm University, Albert-Einstein-Allee 43, 89081, Ulm
3.
ECE, University of Toronto, 10 King's College Road, Toronto M5S 3G4, ON

Received: January 2011

Revised: June 2013

Published: February 2014

Abstract / Introduction Related Papers Cited by

Abstract

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

Keywords:

Mathematics Subject Classification: 94B35.

Citation:

Related Papers

Cited by

References

[1]	E. L. Blokh and V. V. Zyablov, Linear Concatenated Codes (in Russian), Nauka, 1982.
[2]	A. Chaaban, Some Aspects of Adaptive Decoding of Concatenated Codes, Master Thesis, Ulm University, 2009.
[3]	G. D. Forney Jr., Concatenated Codes, MIT Press, Cambridge, MA, 1966.
[4]	G. D. Forney Jr., Generalized minimum distance decoding, IEEE Trans. Inf. Theory, 12 (1966), 125-131.
[5]	V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Trans. Inf. Theory, 45 (1999), 1757-1767.doi: 10.1109/18.782097.
[6]	R. Kötter, Fast generalized minimum-distance decoding of algebraic-geometry and Reed-Solomon codes, IEEE Trans. Inf. Theory, 42 (1993), 721-737.doi: 10.1109/18.490540.
[7]	S. I. Kovalev, Two classes of minimum generalized distance decoding algorithms, Probl. Pered. Inform., 22 (1986), 35-42.
[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-3012.doi: 10.1109/TIT.2009.2021308.
[9]	C. Senger, Generalized Minimum Distance Decoding with Arbitrary Error-Erasure Tradeoff, Dissertation, Ulm University, 2011.
[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-141.doi: 10.1134/S0032946010020031.
[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, Austin, TX, 2010.
[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, St. Petersburg, 2009.
[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, Seoul, 2009.doi: 10.1109/ISIT.2009.5205900.
[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-60.doi: 10.3934/amc.2010.4.49.
[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, Ulm, 2008.
[16]	U. K. Sorger, A new Reed-Solomon code decoding algorithm based on Newton's interpolation, IEEE Trans. Inf. Theory, 39 (1993), 358-365.doi: 10.1109/18.212267.
[17]	M. Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound, J. Complexity, 13 (1997), 180-193.doi: 10.1006/jcom.1997.0439.
[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, Ulm, 1997.doi: 10.1109/ISIT.1997.613366.
[19]	J. H. Weber and K. A. S. Abdel-Ghaffar, Reduced GMD decoding, IEEE Trans. Inf. Theory, 49 (2003), 1013-1027.doi: 10.1109/TIT.2003.809504.
[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-333.doi: 10.1134/S0032946012040023.
[21]	V. V. Zyablov, Optimization of concatenated decoding algorithms, Probl. Pered. Inform., 9 (1973), 26-32.