Poor error correction codes are poor error detection codes (Corresp.)

We show that binary group codes that do not satisfy the asymptotic Varshamov-Gilbert bound have an undesirable characteristic when used as error detection codes for transmission over the binary symmetric channel.     

Parallel error correcting codes

We introduce the concept of "parallel error correcting" codes, the error correcting codes for parallel channels. Here, a parallel channel is a set of channels such that the additive error over a finite field occurs in one of its members at time T if the same error occurs in all members at the same time. The set of codewords of a parallel error correcting code has to be a product set, if the messages transmitted are from independent information sources. We present a simple construction of optimal parallel error correcting codes based on ordinary optimal error correcting codes and a construction of optimal linear parallel codes for independent sources based on optimal ordinary linear error correcting codes. The decoding algorithms for these codes are provided as well     

Decoding algebraic-geometric codes up to the designed minimumdistance

A simple decoding procedure for algebraic-geometric codes C _Ω(D,G) is presented. This decoding procedure is a generalization of Peterson's decoding procedure for the BCH codes. It can be used to correct any [(d*-1)/2] or fewer errors with complexity O(n³), where d * is the designed minimum distance of the algebraic-geometric code and n is the codelength     

On the equivalence of generalized concatenated codes andgeneralized error location codes

We show that the generator matrix of a generalized concatenated code (GCC code) of order L consists of L submatrices, where the lth submatrix is the Kronecker product of the generator matrices of the lth inner code and the lth outer code. In a similar way we show that the parity-check matrix of a generalized error location code (GEL code) of order L consists of L submatrices, where the lth submatrix is the Gronecker product of the parity-check matrices of the lth inner code and the lth outer code. Then we use these defining matrices to show that for any GCC code there exists an equivalent GEL code and vice versa     

Even-weighted codes for error detection

For a binary symmetric channel, a code V with only evenweighted words performs better than a corresponding code V? with both odd- and even-weighted words, from the point of the probability of undetected errors. We derive an estimate of the improvement in the performance.     

On the undetected error probability for binary codes

In this paper, the undetected error probability for binary codes is studied. First complementary codes are studied. Next, a new proof of Abdel-Ghaffar's (1997) lower bound on the undetected error probability is presented and some generalizations are given. Further, upper and lower bounds on the undetected error probability for binary constant weight codes are given, and asymptotic versions are studied.     

On ternary error correcting line codes

The authors present Markov diagrams and tables with the capacities in bits/symbol for input restricted ternary channels with various restrictions on maximum runlengths, digital sum variation, and transitions between extreme signal levels. They derive Gilbert-type lower bounds on the minimum Hamming and Euclidean distances achievable with ternary line codes of rates lower than the capacity of the corresponding input restricted channel. They present some single-symbol-error-correcting ternary line codes, found by computer search methods     

Turbo-codes: the ultimate error control codes?

Turbo-codes have attracted a great deal of interest since their discovery in 1993. This paper reviews the reasons for this, in particular their attainment of the ultimate limits of the capacity of a communication channel. The paper describes the two fundamental concepts on which they are based: concatenated coding and iterative decoding. This latter is the real `turbo-principle', which is the real secret of their remarkable performance. The paper also reviews the direction of research in this area since 1993, and shows that, far from bringing coding research to an end, turbo-codes have led to a renaissance. In particular, other applications of the `turbo-principle' have emerged, and these are discussed, along with the practical applications of turbo-codes that have appeared, from mobile radio to deep-space exploration     

On the decoder error probability of block codes

By using coding and combinational techniques, an explicit formula is derived which enumerates the complete weight distribution of decodable words of block codes using partially known weight distributions. Also, an approximation formula for nonbinary block codes is obtained. These results give exact and approximate expressions for the decoder error probability P_E(u) of block codes     

ERROR-DETECTING CODES AND UNDETECTED ERROR PROBABILITIES

The definition of good codes for error-detection is given. It is proved that a (n, k) linear block code in GF(q) are the good code for error-detection, if and only if its dual code is also. A series of new results about the good codes for error-detection are derived. New lower bounds for undetected error probabilities are obtained, which are relative to n and k only, and not the weight structure of the codes.     

Unequal error protection for convolutional codes

In this correspondence, unequal error-correcting capabilities of convolutional codes are studied. For errors in the information symbols and code symbols, the free input- and output-distances, respectively, serve as "unequal" counterparts to the free distance. When communication takes place close to or above the channel capacity the error bursts tend to be long and the free distance is not any longer useful as the measure of the error correcting capability. Thus, the active burst distance for a given output and the active burst distance for a given input are introduced as "unequal" counterparts to the active burst distance and improved estimates of the unequal error-correcting capabilities of convolutional codes are obtained and illustrated by examples. Finally, it is shown how to obtain unequal error protection for both information and code symbols using woven convolutional codes.     

Multilevel codes for unequal error protection

Two combined unequal error protection (UEP) coding and modulation schemes are proposed. The first method multiplexes different coded signal constellations, with each coded constellation providing a different level of error protection. In this method, a codeword specifies the multiplexing rule and the choice of the codeword from a fixed codebook is used to convey additional important information. The decoder determines the multiplexing rule before decoding the rest of the data. The second method is based on partitioning a signal constellation into disjoint subsets in which the most important data sequence is encoded, using most of the available redundancy, to specify a sequence of subsets. The partitioning and code construction is done to maximize the minimum Euclidean distance between two different valid subset sequences. This leads to ways of partitioning the signal constellations into subsets. The less important data selects a sequence of signal points to be transmitted from the subsets. A side benefit of the proposed set partitioning procedure is a reduction in the number of nearest neighbors, sometimes even over the uncoded signal constellation     

High-throughput error correcting space-time block codes

This letter investigates using an error correction code (ECC) to construct the space-time block code (STBC). Block ECCs over several Galois fields are considered. The resulting STBCs have significantly higher throughput and better performance than orthogonal STBCs, at the cost of increased decoding complexity.     

Turbo codes with unequal error protection

The authors present a new simple method for designing turbo codes with unequal error protection (UEP). An example is given to provide numerical evidence of its effectiveness     

Sparse-graph codes for quantum error correction

Sparse-graph codes appropriate for use in quantum error-correction are presented. Quantum error-correcting codes based on sparse graphs are of interest for three reasons. First, the best codes currently known for classical channels are based on sparse graphs. Second, sparse-graph codes keep the number of quantum interactions associated with the quantum error-correction process small: a constant number per quantum bit, independent of the block length. Third, sparse-graph codes often offer great flexibility with respect to block length and rate. We believe some of the codes we present are unsurpassed by previously published quantum error-correcting codes.     

Nonlinear space-time block codes designed for iterative decoding

Iterative decoding of space-time block codes (STBCs) and channel codes have shown to achieve very good performance. Using tools such as EXIT charts, the performance can be predicted and also used for design. However almost all work so far has concentrated on linear STBCs. Therefore nonlinear STBCs that are designed to work well with iterative decoding are investigated. It is shown that they can outperform linear STBCs since their characteristics are quite different when supplying a priori information from a channel decoder. Analysis, design rules and simulation results for the nonlinear codes are presented.     

Calculation of error probabilities for distance-invariant nonlinear error control codes

Expressions are given for the distance distribution of some nonlinear codes which enable error probabilities to be calculated using methods commonly associated with linear error control codes.<>     

Trellis source codes designed by conjugate gradient optimization

Time-invariant trellis codes for stationary, ergodic, discrete-time sources are designed by unconstrained, nonlinear optimization of the performance in a simulated source encoding with the Viterbi algorithm. A nonderivative conjugate directions algorithm and a conjugate gradient algorithm with restarts are applied to design low-constraint-length, unit-rate, binary codes for the memoryless Gaussian source. The latter algorithm is also used to design codes for the memoryless Laplacian source and a third-order autoregressive model for speech. Good codes are tabulated and compared to other known results on a performance versus complexity basis. Those for the Gaussian source are tested in a joint (tandem) trellis-coding system with known convolutional channel codes     

On error detection and error synchronization of reversible variable-length codes

Reversible variable-length codes (RVLCs) are not only prefix-free but also suffix-free codes. Due to the additional suffix-free condition, RVLCs are usually nonexhaustive codes. When a bit error occurs in a sentence from a nonexhaustive RVLC, it is possible that the corrupted sentence is not decodable. The error is said to be detected in this case. We present a model for analyzing the error detection and error synchronization characteristics of nonexhaustive VLCs. Six indices, the error detection probability, the mean and the variance of forward error detection delay length, the error synchronization probability, the mean and the variance of forward error synchronization delay length are formulated based on this model. When applying the proposed model to the case of nonexhaustive RVLCs, these formulations can be further simplified. Since RVLCs can be decoded in backward direction, the mean and the variance of backward error detection delay length, the mean and the variance of backward error synchronization delay length are also introduced as measures to examine the error detection and error synchronization characteristics of RVLCs. In addition, we found that error synchronization probabilities of RVLCs with minimum block distance greater than 1 are 0.     

Guest editorial capacity approaching codes

Since the introduction of Turbo Codes in 1993, it has become possible to design practical channel coding systems that operate close to capacity at moderate bit error rates (BERs) over the additive white Gaussian noise (AWGN) channel. There are two key ingredients in the design of such systems: (1) the use of simple component codes concatenated in such a way as to produce a random-like codeword weight distribution; and (2) the use of suboptimal iterative decoding algorithms that repeatedly exchange soft information and whose complexity grows only linearly with block length.