Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Advances in Mathematics of Communications

Single-trial decoding of concatenated codes using fixed or adaptive erasing

Vladimir R. Sidorenko, Christian Senger, Martin Bossert, Victor Zyablov

Published Jan 1, 2010• 5 citations
Publisher

Abstract

We consider a concatenated code with designed distance dodi$/2$, based on an outer code with distance do and an inner code with distance di. To decode the inner code, we use a Bounded Minimum Distance decoder correcting up to (di$-1$)$/2$ errors. For decoding the outer code, we use a $\lambda$-Bounded Distance decoder correcting $\varepsilon$ errors and $\tau$ erasures if $\lambda\varepsilon+\tau \leq$do$-1$, where a real number $1dido$/(\lambda +1)$ if the number $\tau$ of erasures is fixed, and (dido$/2$)∗$(1-(\frac{\lambda-1}{\lambda})^2)$ for adaptive selection of $\tau$. The error-correcting radius quickly approaches dido$/2$ with decreasing $\lambda$. These results can be applied e.g. when punctured Reed-Solomon outer codes are used.

DOI
10.3934/amc.2010.4.49

Related papers

On multi-trial Forney-Kovalev decoding of concatenated codes

Anas Chaaban, Vladimir R. Sidorenko, Christian Senger

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

Advances in Mathematics of Communications•Jan 1, 2014•1 citation

Achieving the optimal guaranteed error correction rate in a simple concatenated coding scheme with single-trial decoding

Jos H. Weber, Khaled Abdel-Ghaffar

For a concatenated coding scheme using a single inner code, a single outer code, and an optimal single-trial decoding strategy, we study the guaranteed error correction rate, i.e., the number of correctable errors per transmitted symbol. In particular, it is investigated whether the optimal guaranteed error correction rate can be achieved by finite length codes or only be approached by an infinite sequence of codes of increasing lengths. It is shown that optimizing the guaranteed error correction rate for a given inner or outer code does not necessarily mean pushing the code rate to zero. Furthermore, to optimize the guaranteed error correction rate over all inner and outer codes of fixed dimensions and alphabets, the code rate of one (but not both) of these two codes should be pushed to zero.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•0 citations

Concatenated Codes

Ron M. Roth

In this chapter, we continue the discussion on concatenated codes, which was initiated in Section 5.4. The main message to be conveyed in this chapter is that by using concatenation, one can obtain codes with favorable asymptotic performance—in a sense to be quantified more precisely—while the complexity of constructing these codes and decoding them grows polynomially with the code length. We first present a decoding algorithm for concatenated codes, due to Forney. This algorithm, referred to as a generalized minimum distance (in short, GMD) decoder, corrects any error pattern whose Hamming weight is less than half the product of the minimum distances of the inner and outer codes (we recall that this product is a lower bound on the minimum distance of the respective concatenated code). A GMD decoder consists of a nearest-codeword decoder for the inner code, and a combined error–erasure decoder for the outer code. It then enumerates over a threshold value, marking the output of the inner decoder as erasure if that decoder returns an inner codeword whose Hamming distance from the respective received sub-word equals or exceeds that threshold. We show that under our assumption on the overall Hamming weight of the error word, there is at least one threshold for which the outer decoder recovers the correct codeword. If the outer code is taken as a GRS code, then a GMD decoder has an implementation with time complexity that is at most quadratic in the length of the concatenated code.

Cambridge University Press eBooks•Feb 23, 2006•0 citations

Optimal thresholds for GMD decoding with ℓ+1 over ℓ-extended Bounded Distance decoders

Christian Senger, Vladimir R. Sidorenko, Martin Bossert +1 more

We investigate threshold-based multi-trial decoding of concatenated codes with an inner Maximum-Likelihood decoder and an outer error/erasure ℓ+1/ℓ-extended Bounded Distance decoder, i.e. a decoder which corrects ε errors and τ erasures if ℓ+1/ ℓε+τ≤ do-1, where dois the minimum distance of the outer code and ℓ ∈ ℕ\{0}. This is a generalization of Forney's GMD decoding, which was considered only for ℓ = 1, i.e. outer Bounded Minimum Distance decoding. One important example for ℓ+1/ℓ-extended Bounded Distance decoders is decoding of ℓ-Interleaved Reed-Solomon codes. Our main contribution is a threshold location formula, which allows to optimally erase unreliable inner decoding results, for a given number of decoding trials and parameter ℓ. Thereby, the term optimal means that the residual codeword error probability of the concatenated code is minimized. We give an estimation of this probability for any number of decoding trials.

arXiv:1001.1106•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•4 citations

Decoding concatenated codes using soft information

Venkatesan Guruswami, Madhu Sudan

We present a decoding algorithm for concatenated codes when the outer code is a Reed-Solomon code and the inner code is arbitrary. "Soft" information on the reliability of various symbols is passed by the inner decodings and exploited in the Reed-Solomon decoding. This is the first analysis of such a soft algorithm that works for arbitrary inner codes; prior analyses could only, handle some special inner codes. Crucial to our analysis is a combinatorial result on the coset weight distribution of codes given only its minimum distance. Our result enables us to decode essentially up to the "Johnson radius" of a concatenated code when the outer distance is large (the Johnson radius is the "a priori list decoding radius" of a code as a function of its distance). As a consequence, we are able to present simple and efficient constructions of q-ary linear codes that are list decodable up to a fraction (1 - 1/q - /spl epsiv/) of errors and have rate /spl Omega/(/spl epsiv//sup 6/). Codes that can correct such a large fraction of errors have found numerous complexity-theoretic applications. The previous constructions of linear codes with a similar rate used algebraic-geometric codes and thus suffered from a complicated construction and slow decoding.

IEEE Conference on Computational Complexity (CCC)•Jun 25, 2003•16 citations

List decoding of concatenated codes: improved performance estimates

Alexander Barg, Andrew McGregor

An improved bound is proved on the list-decoding radius of a concatenated code relying upon a combination of (soft-decision) algebraic list decoding and generalized minimum distance (GMD) decoding in the outer level. This bound is further improved if the inner code is a random linear code.

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•0 citations
We consider a concatenated code with designed distance dodi/2/2/2, based on an outer code with distance do and an inner code with distance di. To decode the inner code, we use a Bounded Minimum Distance decoder correcting up to (di−1-1−1)/2/2/2 errors. For decoding the outer code, we use a λ\lambdaλ-Bounded Distance decoder correcting ε\varepsilonε errors and τ\tauτ erasures if λε+τ≤\lambda\varepsilon+\tau \leqλε+τ≤do−1-1−1, where a real number 1dido1dido1dido/(\lambda +1)ifthenumberif the numberifthenumber\tauoferasuresisfixed,and(dido of erasures is fixed, and (didooferasuresisfixed,and(dido/2)∗)∗)∗(1-(\frac{\lambda-1}{\lambda})^2)foradaptiveselectionoffor adaptive selection offoradaptiveselectionof\tau.Theerror−correctingradiusquicklyapproachesdido. The error-correcting radius quickly approaches dido.Theerror−correctingradiusquicklyapproachesdido/2withdecreasingwith decreasingwithdecreasing\lambda$. These results can be applied e.g. when punctured Reed-Solomon outer codes are used.
A concatenated code $\mathcal{C} $ based on an inner code with Hamming distance did^idi and an outer code with Hamming distance dod^odo is considered. An outer decoder that corrects ε\varepsilonε errors and θ\thetaθ erasures with high probability if λε+θ≤do−1,\lambda \varepsilon + \theta \le d^o - 1,λε+θ≤do−1, where a real number 1<λ≤21<\lambda\le 21<λ≤2 is the trade-off rate between errors and erasures for this decoder is used. In particular, an outer lll-punctured RS code, i.e., a code over the field Fql\mathbb{F}_{q^{l }}Fql​ of length no<qn^{o} < qno<q with locators taken from the sub-field Fq\mathbb{F}_{q}Fq​, where l∈{1,2,…}l\in \{1,2,\ldots\}l∈{1,2,…} is considered. In this case, the trade-off is given by λ=1+1/l\lambda=1+1/lλ=1+1/l. An mmm-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 λ=2\lambda=2λ=2) to the whole given range of λ\lambdaλ. For the fixed erasing strategy the error correcting radius approaches ρF≈dido2(1−l−m2)\rho_F\approx\frac{d^i d^o}{2}(1-\frac{l^{-m}}{2})ρF​≈2dido​(1−2l−m​) for large dod^odo. For the adaptive erasing strategy, the error correcting radius ρA≈dido2(1−l−2m)\rho_A\approx\frac{d^i d^o}{2}(1-l^{-2m})ρA​≈2dido​(1−l−2m) quickly approaches dido/2d^i d^o/2dido/2 if lll or mmm grows. The minimum number of trials required to reach an error correcting radius dido/2d^i d^o/2dido/2 is mA=12(log⁡ld+1)m_A=\frac{1}{2}\left(\log_ld+1\right)mA​=21​(logl​d+1). This means that 222 or 333 trials are sufficient in many practical cases if l>1l>1l>1.
For a concatenated coding scheme using a single inner code, a single outer code, and an optimal single-trial decoding strategy, we study the guaranteed error correction rate, i.e., the number of correctable errors per transmitted symbol. In particular, it is investigated whether the optimal guaranteed error correction rate can be achieved by finite length codes or only be approached by an infinite sequence of codes of increasing lengths. It is shown that optimizing the guaranteed error correction rate for a given inner or outer code does not necessarily mean pushing the code rate to zero. Furthermore, to optimize the guaranteed error correction rate over all inner and outer codes of fixed dimensions and alphabets, the code rate of one (but not both) of these two codes should be pushed to zero.
In this chapter, we continue the discussion on concatenated codes, which was initiated in Section 5.4. The main message to be conveyed in this chapter is that by using concatenation, one can obtain codes with favorable asymptotic performance—in a sense to be quantified more precisely—while the complexity of constructing these codes and decoding them grows polynomially with the code length. We first present a decoding algorithm for concatenated codes, due to Forney. This algorithm, referred to as a generalized minimum distance (in short, GMD) decoder, corrects any error pattern whose Hamming weight is less than half the product of the minimum distances of the inner and outer codes (we recall that this product is a lower bound on the minimum distance of the respective concatenated code). A GMD decoder consists of a nearest-codeword decoder for the inner code, and a combined error–erasure decoder for the outer code. It then enumerates over a threshold value, marking the output of the inner decoder as erasure if that decoder returns an inner codeword whose Hamming distance from the respective received sub-word equals or exceeds that threshold. We show that under our assumption on the overall Hamming weight of the error word, there is at least one threshold for which the outer decoder recovers the correct codeword. If the outer code is taken as a GRS code, then a GMD decoder has an implementation with time complexity that is at most quadratic in the length of the concatenated code.
We investigate threshold-based multi-trial decoding of concatenated codes with an inner Maximum-Likelihood decoder and an outer error/erasure ℓ+1/ℓ-extended Bounded Distance decoder, i.e. a decoder which corrects ε errors and τ erasures if ℓ+1/ ℓε+τ≤ do-1, where dois the minimum distance of the outer code and ℓ ∈ ℕ\{0}. This is a generalization of Forney's GMD decoding, which was considered only for ℓ = 1, i.e. outer Bounded Minimum Distance decoding. One important example for ℓ+1/ℓ-extended Bounded Distance decoders is decoding of ℓ-Interleaved Reed-Solomon codes. Our main contribution is a threshold location formula, which allows to optimally erase unreliable inner decoding results, for a given number of decoding trials and parameter ℓ. Thereby, the term optimal means that the residual codeword error probability of the concatenated code is minimized. We give an estimation of this probability for any number of decoding trials.
We present a decoding algorithm for concatenated codes when the outer code is a Reed-Solomon code and the inner code is arbitrary. "Soft" information on the reliability of various symbols is passed by the inner decodings and exploited in the Reed-Solomon decoding. This is the first analysis of such a soft algorithm that works for arbitrary inner codes; prior analyses could only, handle some special inner codes. Crucial to our analysis is a combinatorial result on the coset weight distribution of codes given only its minimum distance. Our result enables us to decode essentially up to the "Johnson radius" of a concatenated code when the outer distance is large (the Johnson radius is the "a priori list decoding radius" of a code as a function of its distance). As a consequence, we are able to present simple and efficient constructions of q-ary linear codes that are list decodable up to a fraction (1 - 1/q - /spl epsiv/) of errors and have rate /spl Omega/(/spl epsiv//sup 6/). Codes that can correct such a large fraction of errors have found numerous complexity-theoretic applications. The previous constructions of linear codes with a similar rate used algebraic-geometric codes and thus suffered from a complicated construction and slow decoding.