×

On multi-trial Forney-Kovalev decoding of concatenated codes. (English) Zbl 1283.94142

Summary: A concatenated code \(\mathcal{C}\) based on an inner code with Hamming distance \(d^{\mathrm{i}}\) and an outer code with Hamming distance \(d^{\mathrm{o}}\) is considered. An outer decoder that corrects \(\varepsilon\) errors and \(\theta\) erasures with high probability if \(\lambda_\varepsilon + \theta \leq d^{\mathrm{o}}-1\), where a real number \(1<\lambda\leq 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^{\mathrm o} < q\) with locators taken from the sub-field \(\mathbb{F}_{q}\), where \(l\in \{1,2,\dots\}\) 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 G. D. Forney jun. [Concatenated codes. M.I.T. Research Monograph, No. 37. Cambridge, Mass.: The M.I.T. Press (1966; Zbl 0264.94006)] and S. I. Kovalev [Probl. Inf. Transm. 22, 186–192 (1986); translation from Probl. Peredachi Inf. 22, No. 3, 35–42 (1986; Zbl 0614.94006)] (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^{\mathrm i} d^{\mathrm o}}{2}(1-\frac{l^{-m}}{2})\) for large \(d^{\mathrm o}\). For the adaptive erasing strategy, the error correcting radius \(\rho_A\approx\frac{d^{\mathrm i} d^{\mathrm o}}{2}(1-l^{-2m})\) quickly approaches \(d^{\mathrm i} d^{\mathrm o}/2\) if \(l\) or \(m\) grows. The minimum number of trials required to reach an error correcting radius \(d^{\mathrm i} d^{\mathrm 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\).

MSC:

94B35 Decoding
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. L. Blokh, <em>Linear Concatenated Codes</em> (in Russian),, Nauka (1982)
[2] A. Chaaban, <em>Some Aspects of Adaptive Decoding of Concatenated Codes</em>,, Master Thesis (2009)
[3] G. D. Forney Jr., <em>Concatenated Codes</em>,, MIT Press (1966)
[4] G. D. Forney Jr., Generalized minimum distance decoding,, IEEE Trans. Inf. Theory, 12, 125 (1966) · Zbl 0253.94007
[5] V. Guruswami, Improved decoding of Reed-Solomon and algebraic-geometry codes,, IEEE Trans. Inf. Theory, 45, 1757 (1999) · Zbl 0958.94036 · 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, 721 (1993) · Zbl 0861.94030 · doi:10.1109/18.490540
[7] S. I. Kovalev, Two classes of minimum generalized distance decoding algorithms,, Probl. Pered. Inform., 22, 35 (1986) · Zbl 0614.94006
[8] G. Schmidt, Collaborative decoding of interleaved Reed-Solomon codes and concatenated code designs,, IEEE Trans. Inf. Theory, 55, 2991 (2009) · Zbl 1367.94446 · doi:10.1109/TIT.2009.2021308
[9] C. Senger, <em>Generalized Minimum Distance Decoding with Arbitrary Error-Erasure Tradeoff</em>,, Dissertation (2011)
[10] C. Senger, Multi-trial decoding of concatenated codes using fixed thresholds,, Probl. Inform. Transm., 46, 127 (2010) · Zbl 1237.94141 · doi:10.1134/S0032946010020031
[11] C. Senger, Optimal thresholds for GMD decoding with (L+1)/L-extended bounded distance decoders,, in Proc. 2010 IEEE Intern. Symp. Inform. Theory (2010)
[12] C. Senger, On generalized minimum distance decoding thresholds for the AWGN channel,, in Proc. XII Int. Symp. Probl. Redund. Inf. Control Systems (2009)
[13] V. R. Sidorenko, On extended Forney-Kovalev GMD decoding,, in Proc. 2009 IEEE Intern. Symp. Inform. Theory (2009) · doi:10.1109/ISIT.2009.5205900
[14] V. R. Sidorenko, Single-trial decoding of concatenated codes using fixed or adaptive erasing,, Adv. Math. Commun., 4, 49 (2010) · Zbl 1190.94041 · doi:10.3934/amc.2010.4.49
[15] V. R. Sidorenko, Decoding punctured Reed-Solomon codes up to the Singleton bound,, in Proc. Int. ITG Conf. Source Channel Coding (2008)
[16] U. K. Sorger, A new Reed-Solomon code decoding algorithm based on Newton’s interpolation,, IEEE Trans. Inf. Theory, 39, 358 (1993) · Zbl 0776.94014 · doi:10.1109/18.212267
[17] M. Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound,, J. Complexity, 13, 180 (1997) · Zbl 0872.68026 · doi:10.1006/jcom.1997.0439
[18] J. H. Weber, Optimal decoding strategy for a simple concatenated coding scheme,, in IEEE Intern. Symp. Inform. Theory (1997) · doi:10.1109/ISIT.1997.613366
[19] J. H. Weber, Reduced GMD decoding,, IEEE Trans. Inf. Theory, 49, 1013 (2003) · Zbl 1063.94115 · doi:10.1109/TIT.2003.809504
[20] J. H. Weber, Asymptotic single-trial strategies for GMD decoding with arbitrary error-erasure tradeoff,, Probl. Inf. Transm., 48, 324 (2012) · Zbl 1312.94121 · doi:10.1134/S0032946012040023
[21] V. V. Zyablov, Optimization of concatenated decoding algorithms,, Probl. Pered. Inform., 9, 26 (1973) · Zbl 0326.94012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.