Soft-decision decoding of Reed-Muller codes as generalized multipleconcatenated codes

Constructs Reed-Muller codes by generalized multiple concatenation of binary block codes of length 2. As a consequence of this construction, a new decoding procedure is derived that uses soft-decision information. The algorithm is designed for low decoding complexity and is applicable to all Reed-Muller codes. It gives better decoding performance than soft-decision bounded-distance decoding. Its decoding complexity is much lower than that of maximum-likelihood trellis decoding of Reed-Muller codes, especially for long 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     

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     

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     

Class of majority decodable real-number codes

A majority decoding algorithm for a class of real-number codes is presented. Majority decoding has been a relatively simple and fast decoding technique for codes over finite fields. When applied to decode real-number codes, the robustness of the majority decoding to the presence of background noise, which is usually an annoying problem for existing decoding algorithms for real-number codes, is its most prominent property. The presented class of real-number codes has generator matrices similar to those of the binary Reed-Muller codes and is decoded by similar majority logic     

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     

一种改进的二阶Reed-Muller译码算法

研究了一种改进的RM译码算法—改进的Sidel,nikov-Pershakov算法(简称SP算法),详细叙述了原始算法的原理以及改进算法的译码步骤,并对两种算法进行了仿真实现,对它们的译码性能和算法复杂度进行了比较。改进的译码算法复杂度略优于原始算法,而改进后的算法的译码性能明显优于原始算法。     

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     

Concatenated Reed-Muller codes for unequal error protection

We present a new coding scheme that combines the advantages of a product-like concatenation of Reed-Muller codes with so-called iterative “turbo” decoding and provides powerful unequal error protection abilities. It is shown that various levels of error protection can be realized using a sophisticated encoding scheme for Reed-Muller codes. A discussion of this code construction, the resulting distance profile between the different levels and the iterative decoding scheme is given. The results are very promising and impressively confirm the unequal error protection capabilities of the presented coding scheme     

Maximum likelihood decoding of certain Reed - Muller codes (Corresp.)

We present an efficient maximum likelihood decoding algorithm for the punctured binary Reed-Muller code of order(m - 3)and length2^{m} - 1, M geq 3, and we give formulas for the weight distribution of coset leaders of such codes.     

Simple MAP decoding of first-order Reed-Muller and Hamming codes

A maximum a posteriori (MAP) probability decoder of a block code minimizes the probability of error for each transmitted symbol separately. The standard way of implementing MAP decoding of a linear code is the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm, which is based on a trellis representation of the code. The complexity of the BCJR algorithm for the first-order Reed-Muller (RM-1) codes and Hamming codes is proportional to n/sup 2/, where n is the code's length. In this correspondence, we present new MAP decoding algorithms for binary and nonbinary RM-1 and Hamming codes. The proposed algorithms have complexities proportional to q/sup 2/n log/sub q/n, where q is the alphabet size. In particular, for the binary codes this yields complexity of order n log n.     

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.     

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     

Closest coset decoding of |u|u+v| codes

The general concept of closest coset decoding (CCD) is presented, and a soft-decoding technique for block codes that is based on partitioning a code into a subcode and its cosets is described. The computational complexity of the CCD algorithm is significantly less than that required if a maximum-likelihood detector (MLD) is used. A set-partitioning procedure and details of the CCD algorithm for soft decoding of |u|u+v| codes are presented. Upper bounds on the bit-error-rate (BER) performance of the proposed algorithm are combined, and numerical results and computer simulation tests for the BER performance of second-order Reed-Muller codes of length 16 and 32 are presented. The algorithm is a suboptimum decoding scheme and, in the range of signal-to-noise-power-density ratios of interest, its BER performance is only a few tenths of a dB inferior to the performance of the MLD for the codes examined     

A Performance Comparison of Polar Codes and Reed-Muller Codes

Polar coding is a code construction method that can be used to construct capacity-achieving codes for binary-input channels with certain symmetries. Polar coding may be considered as a generalization of Reed-Muller (RM) coding. Here, we demonstrate the performance advantages of polar codes over RM codes under belief-propagation decoding.     

On the construction of a class of majority-logic decodable codes

The attractiveness of majority-logic decoding is its simple implementation. Several classes of majority-logic decodable block codes have been discovered for the past two decades. In this paper, a method of constructing a new class of majority-logic decodable block codes is presented. Each code in this class is formed by combining majority-logic decodable codes of shorter lengths. A procedure for orthogonalizing codes of this class is formulated. For each code, a lower bound on the number of correctable errors with majority-logic decoding is obtained. An upper bound on the number of orthogonalization steps for decoding each code is derived. Several majority-logic decodable codes that have more information digits than the Reed-Muller codes of the same length and the same minimum distance are found. Some results presented in this paper are extensions of the results of Lin and Weldon [11] and Gore [12] on the majority-logic decoding of direct product codes.     

Some applications of Good's theorem (Corresp.)

Three applications of a theorem of I. J. Good are made: a simplification of the fast Hadamard transform algorithm of R.R. Green used in the decoding of first-order Reed-Muller codes, a simple proof of the well-known Parseval formula, and an application to the discrete one-dimensional Fourier transform.     

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.     

Performance of Reed-Muller codes and a maximum-likelihood decodingalgorithm for OFDM

The performance of Reed-Muller encoding and a maximum-likelihood decoding algorithm for orthogonal frequency-division multiplexing is presented. The example codes have a tightly bounded peak-to-mean envelope power ratio, while simultaneously enabling powerful error correction. We present a maximum-likelihood decoder that makes use of a distance-preserving map and multiple fast Hadamard transforms. Its operation is described in detail and its performance is assessed under realistic channel conditions