Efficient maximum-likelihood decoding of Q-ary modulatedReed-Muller codes

We derive an efficient soft-decision maximum-likelihood decoding algorithm for a class of Q-ary phase-shift keyed peak-to-average power ratio limited codes for orthogonal frequency division modulation, by generalizing the fast Hadamard transform decoding of first-order Reed-Muller codes     

Soft-decision majority decoding of Reed-Muller codes

We present a new soft-decision majority decoding algorithm for Reed-Muller codes RM(r,m). First, the reliabilities of 2^m transmitted symbols are recalculated into the reliabilities of 2^m-r parity checks that represent each information bit. In turn, information bits are obtained by the weighted majority that gives more weight to more reliable parity checks. It is proven that for long low-rate codes RM(r,m), our soft-decision algorithm outperforms its conventional hard-decision counterpart by 10 log₁₀(π/2)≈2 dB at any given output error probability. For fixed code rate R and m→∞, our algorithm increases almost 2^r/2 times the correcting capability of soft-decision bounded distance decoding     

Suboptimum decoding of decomposable block codes

To decode a long block code with a large minimum distance by maximum likelihood decoding is practically impossible because the decoding complexity is simply enormous. However, if a code can be decomposed into constituent codes with smaller dimensions and simpler structure, it is possible to devise a practical and yet efficient scheme to decode the code. This paper investigates a class of decomposable codes, their distance and structural properties. It is shown that this class includes several classes of well-known and efficient codes as subclasses. Several methods for constructing decomposable codes or decomposing codes are presented. A two-stage (soft-decision or hard-decision) decoding scheme for decomposable codes, their translates or unions of translates is devised, and its error performance is analyzed for an AWGN channel. The two-stage soft-decision decoding is suboptimum. Error performances of some specific decomposable codes based on the proposed two-stage soft-decision decoding are evaluated. It is shown that the proposed two-stage suboptimum decoding scheme provides an excellent trade-off between the error performance and decoding complexity for codes of moderate and long block length     

Iterative algebraic soft-decision list decoding of Reed-Solomon codes

In this paper, we present an iterative soft-decision decoding algorithm for Reed-Solomon (RS) codes offering both complexity and performance advantages over previously known decoding algorithms. Our algorithm is a list decoding algorithm which combines two powerful soft-decision decoding techniques which were previously regarded in the literature as competitive, namely, the Koetter-Vardy algebraic soft-decision decoding algorithm and belief-propagation based on adaptive parity-check matrices, recently proposed by Jiang and Narayanan. Building on the Jiang-Narayanan algorithm, we present a belief-propagation-based algorithm with a significant reduction in computational complexity. We introduce the concept of using a belief-propagation-based decoder to enhance the soft-input information prior to decoding with an algebraic soft-decision decoder. Our algorithm can also be viewed as an interpolation multiplicity assignment scheme for algebraic soft-decision decoding of RS codes.     

Soft-decision list decoding of hermitian codes

This paper proposes the first complete soft-decision list decoding algorithm for Hermitian codes based on the Koetter- Vardy's Reed-Solomon code decoding algorithm. For Hermitian codes, interpolation processes trivariate polynomials which are defined over the pole basis of a Hermitian curve. In this paper, the interpolated zero condition of a trivariate polynomial with respect to a multiplicity matrix M is redefined followed by a proof of the validity of the soft-decision scheme. This paper also introduces a new stopping criterion for the algorithm that tranforms the reliability matrix ? to the multiplicity matrix M. Geometric characterisation of the trivariate monomial decoding region is investigated, resulting in an asymptotic optimal performance bound for the soft-decision decoder. By defining the weighted degree upper bound of the interpolated polynomial, two complexity reducing modifications are introduced for the soft-decision scheme: elimination of unnecessary interpolated polynomials and pre-calculation of the coefficients that relate the pole basis monomials to the zero basis functions of a Hermitian curve. Our simulation results and analyses show that soft-decision list decoding of Hermitian code can outperform Koetter-Vardy decoding of Reed-Solomon code which is defined in a larger finite field, but with less decoding complexity.     

A* decoding of block codes

The A* algorithm is applied to maximum-likelihood soft-decision decoding of binary linear block codes. This paper gives a tutorial on the A* algorithm, compares the decoding complexity with that of exhaustive search and Viterbi decoding algorithms, and presents performance curves obtained for several codes     

Efficient decoding algorithms for generalized Reed-Muller codes

Previously, a class of generalized Reed-Muller (RM) codes has been suggested for use in orthogonal frequency-division multiplexing. These codes offer error correcting capability combined with substantially reduced peak-to mean power ratios. A number of approaches to decoding these codes have already been developed. Here, we present low complexity, suboptimal alternatives which are inspired by the classical Reed decoding algorithm for binary RM codes. We simulate these new algorithms along with the existing decoding algorithms using additive white Gaussian noise and two-path fading models for a particular choice of code. The simulations show that one of our new algorithms outperforms all existing suboptimal algorithms and offers performance that is within 0.5 dB of maximum-likelihood decoding, yet has complexity comparable to or lower than existing decoding approaches     

Applications of algebraic soft-decision decoding of Reed-Solomon codes

Efficient soft-decision decoding of Reed-Solomon (RS) codes is made possible by the Koetter-Vardy (KV) algorithm which consists of a front-end to the interpolation-based Guruswami-Sudan (GS) list decoding algorithm. This paper approaches the soft-decision KV algorithm from the point of view of a communications systems designer who wants to know what benefits the algorithm can give, and how the extra complexity introduced by soft decoding can be managed at the systems level. We show how to reduce the computational complexity and memory requirements of the soft-decision front-end. Applications to wireless communications over Rayleigh fading channels and magnetic recording channels are proposed. For a high-rate RS(255,239) code, 2-3 dB of soft-decision gain is possible over a Rayleigh fading channel using 16-quadrature amplitude modulation. For shorter codes and at lower rates, the gain can be as large as 9 dB. To lower the complexity of decoding on the systems level, the redecoding architecture is explored, which uses only the appropriate amount of complexity to decode each packet. An error-detection criterion based on the properties of the KV decoder is proposed for the redecoding architecture. Queueing analysis verifies the practicality of the redecoding architecture by showing that only a modestly sized RAM buffer is required.     

Exponential error bounds for algebraic soft-decision decoding of Reed-Solomon codes

Algebraic soft-decision decoding of Reed-Solomon codes is a promising technique for exploiting reliability information in the decoding process. While the algorithmic aspects of the decoding algorithm are reasonably well understood and, in particular, complexity is polynomially bounded in the length of the code, the performance analysis has relied almost entirely on simulation results. Analytical exponential error bounds that can be used to tightly bound the performance of Reed-Solomon codes under algebraic soft-decision decoding are presented in this paper. The analysis is used in a number of examples and several extensions and consequences of the results are presented.     

New decoding algorithm for Reed - Muller codes (Corresp.)

We interpret Reed-Muller codes in terms of superimposition and present a new decoding algorithm for Reed-Muller codes. Before presenting this algorithm, we propose a decoding algorithm for a class of simple iterated codes (SI codes) that will play an important role in our new decoding algorithm. Finally, we compare our algorithm with the conventional algorithm for the cyclic Reed-Muller codes from the standpoint of decoding delay.     

Soft-decision decoding of Reed-Muller codes: a simplified algorithm

Soft-decision decoding is considered for general Reed-Muller (RM) codes of length n and distance d used over a memoryless channel. A recursive decoding algorithm is designed and its decoding threshold is derived for long RM codes. The algorithm has complexity of order nlnn and corrects most error patterns of the Euclidean weight of order radicn/lnn, instead of the decoding threshold radicd/2 of the bounded distance decoding. Also, for long RM codes of fixed rate R, the new algorithm increases 4/pi times the decoding threshold of its hard-decision counterpart     

Algebraic soft-decision decoding of Reed-Solomon codes

A polynomial-time soft-decision decoding algorithm for Reed-Solomon codes is developed. This list-decoding algorithm is algebraic in nature and builds upon the interpolation procedure proposed by Guruswami and Sudan(see ibid., vol.45, p.1757-67, Sept. 1999) for hard-decision decoding. Algebraic soft-decision decoding is achieved by means of converting the probabilistic reliability information into a set of interpolation points, along with their multiplicities. The proposed conversion procedure is shown to be asymptotically optimal for a certain probabilistic model. The resulting soft-decoding algorithm significantly outperforms both the Guruswami-Sudan decoding and the generalized minimum distance (GMD) decoding of Reed-Solomon codes, while maintaining a complexity that is polynomial in the length of the code. Asymptotic analysis for alarge number of interpolation points is presented, leading to a geo- metric characterization of the decoding regions of the proposed algorithm. It is then shown that the asymptotic performance can be approached as closely as desired with a list size that does not depend on the length of the code.     

Soft-decision decoding of binary linear block codes using reducedbreadth-first search algorithms

The article discusses soft-decision decoding of binary linear block codes using the t-algorithm and its variants. New variants of the basic algorithm are presented that reduce the decoding complexity using a threshold adaptive to the signal-to-noise ratio and address the variable decoding complexity by either limiting the memory or using a generalized M-algorithm with a nonconstant state profile     

The Z4-linearity of Kerdock, Preparata, Goethals, andrelated codes

Certain notorious nonlinear binary codes contain more codewords than any known linear code. These include the codes constructed by Nordstrom-Robinson (1967), Kerdock (1972), Preparata (1968), Goethals (1974), and Delsarte-Goethals (1975). It is shown here that all these codes can be very simply constructed as binary images under the Gray map of linear codes over Z₄, the integers mod 4 (although this requires a slight modification of the Preparata and Goethals codes). The construction implies that all these binary codes are distance invariant. Duality in the Z₄ domain implies that the binary images have dual weight distributions. The Kerdock and “Preparata” codes are duals over Z₄-and the Nordstrom-Robinson code is self-dual-which explains why their weight distributions are dual to each other. The Kerdock and “Preparata” codes are Z₄-analogues of first-order Reed-Muller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z₄, which greatly simplifies encoding and decoding. An algebraic hard-decision decoding algorithm is given for the “Preparata” code and a Hadamard-transform soft-decision decoding algorithm for the I(Kerdock code. Binary first- and second-order Reed-Muller codes are also linear over Z₄ , but extended Hamming codes of length n⩾32 and the Golay code are not. Using Z₄-linearity, a new family of distance regular graphs are constructed on the cosets of the “Preparata” code     

Performance of sphere decoding of block codes

A sphere decoder searches for the closest lattice point within a certain search radius. The search radius provides a tradeoff between performance and complexity. We focus on analyzing the performance of sphere decoding of linear block codes. We analyze the performance of soft-decision sphere decoding on AWGN channels and a variety of modulation schemes. A hard-decision sphere decoder is a bounded distance decoder with the corresponding decoding radius. We analyze the performance of hard-decision sphere decoding on binary and q-ary symmetric channels. An upper bound on the performance of maximum-likelihood decoding of linear codes defined over F_q (e.g. Reed- Solomon codes) and transmitted over q-ary symmetric channels is derived and used in the analysis.We then discuss sphere decoding of general block codes or lattices with arbitrary modulation schemes. The tradeoff between the performance and complexity of a sphere decoder is then discussed.     

Recursive decoding and its performance for low-rate Reed-Muller codes

Recursive decoding techniques are considered for Reed-Muller (RM) codes of growing length n and fixed order r. An algorithm is designed that has complexity of order nlogn and corrects most error patterns of weight up to n(1/2-/spl epsiv/) given that /spl epsiv/ exceeds n/sup -1/2r/. This improves the asymptotic bounds known for decoding RM codes with nonexponential complexity. To evaluate decoding capability, we develop a probabilistic technique that disintegrates decoding into a sequence of recursive steps. Although dependent, subsequent outputs can be tightly evaluated under the assumption that all preceding decodings are correct. In turn, this allows us to employ second-order analysis and find the error weights for which the decoding error probability vanishes on the entire sequence of decoding steps as the code length n grows.     

Suboptimal SISO decoding of systematic binary algebraic block codes

Previous work on concatenated single parity-check codes has yielded exceptionally good performance despite, or perhaps because of, their weak algebraic structure. In this article, maximum a posteriori single parity-check decoders are applied to the decoding of systematic binary algebraic block codes. Results for a range of Hamming codes show good performance compared to soft-decision brute force (maximum-likelihood) and algebraic decoding. The decoding complexity of the proposed technique grows only linearly with increasing block length.     

DC-free error-control block codes

DC-free codes and error-control (EC) codes are widely used in digital transmission and storage systems. To improve system performance in terms of code rate, bit-error rate (BER), and low-frequency suppression, and to provide a flexible tradeoff between these parameters, this paper introduces a new class of codes with both dc-control and EC capability. The new codes integrate dc-free encoding and EC encoding, and are decoded by first applying standard EC decoding techniques prior to dc-free decoding, thereby avoiding the drawbacks that arise when dc-free decoding precedes EC decoding. The dc-free code property is introduced into standard EC codes through multimode coding techniques, at the cost of minor loss in BER performance on the additive white Gaussian noise channel, and some increase in implementation complexity, particularly at the encoder. This paper demonstrates that a wide variety of EC block codes can be integrated into this dc-free coding structure, including binary cyclic codes, binary primitive BCH codes, Reed-Solomon codes, Reed-Muller codes, and some capacity-approaching EC block codes, such as low-density parity-check codes and product codes with iterative decoding. Performance of the new dc-free EC block codes is presented.     

Application of circulant matrices to the construction and decodingof linear codes

The Fourier transform technique is used to analyze and construct several families of double-circulant codes. The minimum distance of the resulting codes is lower-bounded by 2√r and can be decoded easily employing the standard BCH decoding algorithm or the majority-logic decoder of Reed-Muller codes. A decoding procedure for Reed-Solomon codes is presented, based on a representation of the parity-check matrix by circulant blocks. The decoding procedure inherits both the (relatively low) time complexity of the Berlekamp-Massey algorithm and the hardware simplicity characteristic of Blahut's algorithm. The procedure makes use of the encoding circuit together with a reduced version of Blahut's decoder     

Multilevel block codes for Rayleigh-fading channels

New multilevel block codes for Rayleigh-fading channels are presented. At high signal-to-noise ratios (SNRs), the proposed block codes can achieve better bit error performance over TCM codes, optimum for fading channels, with comparable decoder complexity and bandwidth efficiency. The code construction is based on variant length binary component block codes. As component codes for the 8-PSK multilevel block construction, the authors propose two modified forms of Reed-Muller codes giving a good trade-off between the decoder complexity and the effective code rates. Code design criteria are derived from the error performance analysis. Multistage decoding shows very slight degradation of bit error performance relative to the maximum likelihood algorithm