Turbo encoding and decoding of Reed-Solomon codes through binary decomposition and self-concatenation

This paper presents a two-stage turbo-coding scheme for Reed-Solomon (RS) codes through binary decomposition and self-concatenation. In this scheme, the binary image of an RS code over GF(2/sup m/) is first decomposed into a set of binary component codes with relatively small trellis complexities. Then the RS code is formatted as a self-concatenated code with itself as the outer code and the binary component codes as the inner codes in a turbo-coding arrangement. In decoding, the inner codes are decoded with turbo decoding and the outer code is decoded with either an algebraic decoding algorithm or a reliability-based decoding algorithm. The outer and inner decoders interact during each decoding iteration. For RS codes of lengths up to 255, the proposed two-stage coding scheme is practically implementable and provides a significant coding gain over conventional algebraic and reliability-based decoding algorithms.     

Linear codes with Pless structures

Extended Golay codes possess certain two-level structures which are important for decoding the codes. However, these ideal structures are not limited to Golay codes. Here, the structures are generalised to other linear codes. Among which are a binary (20. 9, 7) code, a binary (32, 16, 8) code, a binary (40, 20, 8) code and a ternary (18, 9, 6) code. Similar to the Golay codes, there are also efficient decoding algorithms for these codes, which are sufficiently simple to enable decoding the derived codes by hand calculations     

Decoding binary two-error correcting cyclic codes with Zechlogarithms

A decoding method for binary two-error correcting cyclic codes whose generator polynomials have at most two irreducible factors is presented. This class includes binary narrow-sense BCH codes with designed distance 5. The decoding algorithm uses the Zech logarithm for the finite field in which the roots of the code lie     

Estimating the fraction of erasure patterns correctable by linear codes

The conditional probability (fraction) of the successful decoding of erasure patterns of high (greater than the code distance) weights is investigated for linear codes with the partially known or unknown weight spectra of code words. The estimated conditional probabilities and the methods used to calculate them refer to arbitrary binary linear codes and binary Hamming, Panchenko, and Bose–Chaudhuri–Hocquenghem (BCH) codes, including their extended and shortened forms. Error detection probabilities are estimated under erasure-correction conditions. The product-code decoding algorithms involving the correction of high weight erasures by means of component Hamming, Panchenko, and BCH codes are proposed, and the upper estimate of decoding failure probability is presented.     

Two Bit-Flipping Decoding Algorithms for Low-Density Parity-Check Codes

In this letter, a low complexity decoding algorithm for binary linear block codes is applied to low-density paritycheck (LDPC) codes and improvements are described, namely an extension to soft-decision decoding and a loop detection mechanism. For soft decoding, only one real-valued addition per code symbol is needed, while the remaining operations are only binary as in the hard decision case. The decoding performance is considerably increased by the loop detection. Simulation results are used to compare the performance with other known decoding strategies for LDPC codes, with the result that the presented algorithms offer excellent performances at smaller complexity.     

A Decomposition Theory for Binary Linear Codes

The decomposition theory of matroids initiated by Paul Seymour in the 1980s has had an enormous impact on research in matroid theory. This theory, when applied to matrices over the binary field, yields a powerful decomposition theory for binary linear codes. In this paper, we give an overview of this code decomposition theory, and discuss some of its implications in the context of the recently discovered formulation of maximum-likelihood (ML) decoding of a binary linear code over a binary-input discrete memoryless channel as a linear programming problem. We translate matroid-theoretic results of Grotschel and Truemper from the combinatorial optimization literature to give examples of nontrivial families of codes for which the ML decoding problem can be solved in time polynomial in the length of the code. One such family is that consisting of codes for which the codeword polytope is identical to the Koetter-Vontobel fundamental polytope derived from the entire dual code C^perp. However, we also show that such families of codes are not good in a coding-theoretic sense-either their dimension or their minimum distance must grow sublinearly with code length. As a consequence, we have that decoding by linear programming, when applied to good codes, cannot avoid failing occasionally due to the presence of pseudocode words.     

A new class of linear codes with two-level structure

The binary extended Golay code has a two-level structure, which can be used in the decoding of the code. However, such structure is not limited to the Golay code, in fact, several binary linear codes can be constructed by a projective method which is related to the structure. In this correspondence, the binary (4n,n 2k, ≥min(8, n,2d)) linear codes are resulted from quaternary (n,k,d) linear block codes. Based on the structure, the efficient maximum likelihood decoding algorithms can be presented correspondingly for the derived codes.     

Error-resilient decoding of context-based adaptive binary arithmetic codes

This paper addresses the problem of error-resilient decoding of bitstreams produced by the CABAC (context-based adaptive binary arithmetic coding) algorithm used in the H.264 video coding standard. The paper describes a maximum a posteriori (MAP) estimation algorithm improving the CABAC decoding performances in the presence of transmission errors. Methods improving the re-synchronization and error detection capabilities of the decoder are then described. A variant of the CABAC algorithm supporting error detection based on a forbidden interval is presented. The performances of the decoding algorithm are first assessed with theoretical sources and by considering different binarization codes. They are compared against those obtained with Exp-Golomb codes and with a transmission chain making use of an error-correcting code. The approach has been integrated in an H.264/MPEG-4 AVC video coder and decoder. The PSNR gains obtained are discussed.     

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     

On the computation of the performance probabilities for block codeswith a bounded-distance decoding rule

When a block code is used on a discrete memoryless channel with an incomplete decoding rule that is based on a generalized distance, the probability of decoding failure, the probability of erroneous decoding, and the expected number of symbol decoding errors can be expressed in terms of the generalized weight enumerator polynomials of the code. For the symmetric erasure channel, numerically stable methods to compute these probabilities or expectations are proposed for binary codes whose distance distributions are known, and for linear maximum distance separable (MDS) codes. The method for linear MDS codes saves the computation of the weight distribution and yields upper bounds for the probability of erroneous decoding and for the symbol error rate by the cumulative binomial distribution. Numerical examples include a triple-error-correcting Bose-Chaudhuri-Hocquenghem (BCH) code of length 63 and a Reed-Solomon code of length 1023 and minimum distance 31     

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.     

Decoding binary block codes onQ-ary output channels

This paper presents an algebraic technique for decoding binary block codes in situations where the demodulator quantizes the received signal space intoQ > 2regions. The method, referred to as weighted erasure decoding (WED), is applicable in principle to any block code for which a binary decoding procedure is known.     

Generalized LDPC codes and generalized stopping sets

A generalized low-density parity check code (GLDPC) is a low-density parity check code in which the constraint nodes of the code graph are block codes, rather than single parity checks. In this paper, we study GLDPC codes which have BCH or Reed-Solomon codes as subcodes under bounded distance decoding (BDD). The performance of the proposed scheme is investigated in the limit case of an infinite length (cycle free) code used over a binary erasure channel (BEC) and the corresponding thresholds for iterative decoding are derived. The performance of the proposed scheme for finite code lengths over a BEC is investigated as well. Structures responsible for decoding failures are defined and a theoretical analysis over the ensemble of GLDPC codes which yields exact bit and block error rates of the ensemble average is derived. Unfortunately this study shows that GLDPC codes do not compare favorably with their LDPC counterpart over the BEC. Fortunately, it is also shown that under certain conditions, objects identified in the analysis of GLDPC codes over a BEC and the corresponding theoretical results remain useful to derive tight lower bounds on the performance of GLDPC codes over a binary symmetric channel (BSC). Simulation results show that the proposed method yields competitive performance with a good decoding complexity trade-off for the BSC.     

Two topics on linear unequal error protection codes: Bounds on their length and cyclic code classes

It is possible for a linear block code to provide more protection for selected positions in the input message words than is guaranteed by the minimum distance of the code. Linear codes having this property are called linear unequal error protection (LUEP) codes. Bounds on the length of a LUEP code that ensures a given unequal error protection are derived. A majority decoding method for certain classes of cyclic binary UEP codes is treated. A list of short (i.e., of length less than 16) binary LUEP codes of optimal (i.e., minimal) length and a list of all cyclic binary UEP codes of length less than 40 are included.     

Undetected error probabilities of binary primitive BCH codes forboth error correction and detection

We investigate the undetected error probabilities for bounded-distance decoding of binary primitive BCH codes when they are used for both error correction and detection on a binary symmetric channel. We show that the undetected error probability of binary linear codes can be simplified and quantified if the weight distribution of the code is binomial-like. We obtain bounds on the undetected error probability of binary primitive BCH codes by applying the result to the code and show that the bounds are quantified by the deviation factor of the true weight distribution from the binomial-like weight distribution     

Single error correcting and multiple unidirectional error detecting cyclic an arithmetic codes

We present cyclic AN arithmetic codes capable of single error correction and multiple unidirectional error detection. These codes can be used throughout a fault-tolerant computer, and they eliminate the need for encoding/decoding circuits and code translation circuits. We use criteria for the determination of the unidirectional error detection capability for a given AN code, and we present a new error correction/detection scheme.     

Binary multilevel coset codes based on Reed-Muller codes

We study the construction and decoding of binary multilevel coset codes. This construction, originally introduced by Blokh and Zyablov in 1974 and by Zinov'ev in 1976, shows remarkable analogies with most recent schemes of coded modulations. Basic elements of the construction are an inner code, head of a partition chain having suitable distance properties, and a set of outer codes, generally nonbinary. For each partition level there is an outer code whose alphabet has the same order of the partition: in this way it is possible to associate every partition subset to a code symbol. It is well known that these codes can be efficiently decoded by the so called “multistage decoding.” We show that good codes (in terms of performance/complexity) can be constructed using Reed-Muller (RM) codes as inner codes. To this aim RM codes are revisited in the framework of the above construction and decoding techniques. In particular we describe a family of decoders for RM codes which include Forney's (1988) and Hemmati's (1989) decoders as special cases. Finally, we present some examples of efficient binary codes based on RM codes, and assess their performance via computer simulation     

On (n, n-1) convolutional codes with low trellis complexity

We show that the state complexity profile of a convolutional code C is the same as that of the reciprocal of the dual code of C in case that minimal encoders for both codes are used. Then, we propose an optimum permutation for any given (n, n-1) binary convolutional code that will yield an equivalent code with the lowest state complexity. With this permutation, we are able to find many (n, n-1) binary convolutional codes which are better than punctured convolutional codes of the same code rate and memory size by either lower decoding complexity or better weight spectra     

Correcting capabilities of binary irregular LDPC code under low-complexity iterative decoding algorithm

This paper deals with the irregular binary low-density parity-check (LDPC) codes and two iterative low-complexity decoding algorithms. The first one is the majority error-correcting decoding algorithm, and the second one is iterative erasure-correcting decoding algorithm. The lower bounds on correcting capabilities (the guaranteed corrected error and erasure fraction respectively) of irregular LDPC code under decoding (error and erasure correcting respectively) algorithms with low-complexity were represented. These lower bounds were obtained as a result of analysis of Tanner graph representation of irregular LDPC code. The numerical results, obtained at the end of the paper for proposed lower-bounds achieved similar results for the previously known best lower-bounds for regular LDPC codes and were represented for the first time for the irregular LDPC codes.     

Maximum likelihood soft decoding of binary block codes and decodersfor the Golay codes

Maximum-likelihood soft-decision decoding of linear block codes is addressed. A binary multiple-check generalization of the Wagner rule is presented, and two methods for its implementation, one of which resembles the suboptimal Forney-Chase algorithms, are described. Besides efficient soft decoding of small codes, the generalized rule enables utilization of subspaces of a wide variety, thereby yielding maximum-likelihood decoders with substantially reduced computational complexity for some larger binary codes. More sophisticated choice and exploitation of the structure of both a subspace and the coset representatives are demonstrated for the (24, 12) Golay code, yielding a computational gain factor of about 2 with respect to previous methods. A ternary single-check version of the Wagner rule is applied for efficient soft decoding of the (12, 6) ternary Golay code