Asilomar Conference on Signals, Systems and Computers (ACSSC)

A Chernoff type error bound for algebraic soft-decision decoding of Reed Solomon codes

N. Ratnakar, R. Koetter

Published Dec 22, 2003• 3 citations

Abstract

We present exponential upper bounds on the performance of algebraic soft-decision decoding algorithm in the decoding of Reed-Solomon codes for a symmetric channel. The symmetric channels are useful for computing the performance of the algebraic soft-decision decoding algorithm in regimes where the probability of error is low. In such regimes, these bounds are of particular interest since it is impractical to run simulations. The bounds are Chernoff-type error bounds.

DOI: 10.1109/acssc.2002.1197167

Related papers

Error exponents for two soft decision decoding algorithms of Reed-Muller codes

M. V. Burnashev, Ilya I. Dumer

Error exponents are studied for the recursive and majority decoding algorithms of general Reed-Muller codes RM(r, m) used on the AWGN channels. Both algorithms have low decoding complexity and substantially outperform bounded distance decoding in their error-correcting capabilities. We obtain asymptotically tight upper bounds on the output error rate that hold for both algorithms and can be used for any RM-code.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 20082 citations

On soft-decision iterative decoding algorithms by using algebraic decoding for RS codes

Hitoshi Tokushige, I. Hisadomi, Tadao Kasami

We consider an iterative decoding algorithm by using algebraic decoding for non-binary codes. In the decoding algorithm, algebraic decoding are carried out with respect to successively chosen input words, called the search centers. We present a new method for selecting sequences of search centers of algebraic decoding. Over the AWGN channel using BPSK signaling, we show simulation results on the error performances of the iterative decoding algorithms whose search centers are given by the proposed method, abbreviated IAD, for Reed-Solomon codes. From the simulation results, IAD provides considerably better error performance than GMD and CGA decoding with the same number of iterations.

GlobecomMar 22, 20043 citations

Error Exponents for Two Soft-Decision Decoding Algorithms of Reed–Muller Codes

M. V. Burnashev, Ilya I. Dumer

Error exponents are studied for recursive and majority decoding of general Reed-Muller (RM) codesRM(r,m) used on the additive white Gaussian noise (AWGN) channels. Both algorithms have low complexity and correct many error patterns whose weight exceeds half the code distance. Decoding consists of multiple consecutive steps, which repeatedly recalculate the input symbols and determine different information symbols using soft-decision majority voting. For any codeRM(r,m), we estimate the probabilities of the information symbols obtained in these recalculations and derive the analytical upper bounds for the block error rates of the recursive and majority decoding. In the case of a low noise, we also obtain the lower bounds and show that the upper bounds are tight. For a higher noise, these bounds closely approach our simulation results.

IEEE Transactions on Information TheoryAug 24, 20092 citations

Soft-Decision List Decoding with Linear Complexity for the First-Order Reed-Muller Codes

Ilya I. Dumer, Grigory A. Kabatiansky, Cédric Tavernier

Soft-decision decoding on a memoryless channel is considered for the first-order Reed-Muller codes RM (1, m) of length 2m. We assume that different positions j of the received binary vector y can be corrupted by the errors of varying weight wj. The generalized Hamming distance between vector y and any binary vector c is then defined as the sum of weighted differences wj|yj- cj| taken over all n positions. We obtain a tight upper bound LTon the number of codewords located within generalized Hamming distance T from vector y, and design a decoding algorithm that outputs this list of codewords with complexity O (n ln2LT). In particular, all possible error weights wjequal 1 if this combinatorial model is applied to a binary symmetric channel. In this case, the well known Green algorithm performs full maximum likelihood decoding of RM (1, m) and requires O (n ln2n) bit operations, whereas the Litsyn-Shekhovtsov algorithm operates within the bounded-distance decoding radius n/4-1 with linear complexity O(n). We close the performance-complexity gap between the two algorithms. Namely, for any fixed (0, ½), our algorithm outputs the complete list of codewords within the decoding radius n(½-) with linear complexity of order n ln2.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 20072 citations

Asymptotically optimal soft decision decoding algorithms for Hamming codes

C.-E.W. Sundberg

Asymptotically optimal soft decision decoding algorithms for d = 3 and d = 4 Hamming codes are given and analysed. Only error sequences with probability exponent larger than that of maximum-likelihood decoding are corrected. Upper bounds on the block error probability for the Gaussian channel are given.

Electronics LettersJan 20, 19777 citations

An upper bound on the effective error coefficient of two-stage decoding, and good two-level decompositions of some Reed-Muller codes

Jiantin Wu, Shu Hwa Lin, Tadao Kasami +2 more

An upper bound on the effective error coefficient of a two-level code with two-stage decoding is presented. This bound provides a guideline for constructing two-level codes to achieve a good trade-off between the error performance and decoding complexity. Based on this bound, good two-level decompositions of some Reed-Muller codes for two-stage decoding are found. Simulation results on the error performances of some Reed-Muller codes of lengths up to 64 with two-stage soft-decision suboptimum decoding based on their two-level decompositions are given.>

IEEE Transactions on CommunicationsFeb 1, 199413 citations