Advances in Mathematics of Communications (AMC)

On multi-trial Forney-Kovalev decoding of concatenated codes

Pages: 1 - 20, Volume 8, Issue 1, February 2014      doi:10.3934/amc.2014.8.1

       Abstract        References        Full Text (456.9K)       Related Articles       

Anas Chaaban - DCS, Ruhr-Universität Bochum, Universitätsstraße 150, 44780 Bochum, Germany (email)
Vladimir Sidorenko - TAIT, Ulm University, Albert-Einstein-Allee 43, 89081, Ulm, Germany (email)
Christian Senger - ECE, University of Toronto, 10 King's College Road, Toronto M5S 3G4, ON, Canada (email)

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:  Multi-trial decoding, concatenated codes, GMD decoding, error correcting radius, fixed erasing, adaptive erasing.
Mathematics Subject Classification:  94B35.

Received: January 2011;      Revised: June 2013;      Available Online: January 2014.