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.     

The MMD codes are proper for error detection

The undetected error probability of a linear code used to detect errors on a symmetric channel is a function of the symbol error probability /spl epsi/ of the channel and involves the weight distribution of the code. The code is proper, if the undetected error probability increases monotonously in /spl epsi/. Proper codes are generally considered to perform well in error detection. We show in this correspondence that maximum minimum distance (MMD) codes are proper.     

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     

Some new hybrid ARQ techniques for high error rate conditions

Some new hybrid ARQ schemes for error control in communication systems are presented in which redundancy, achieved by retransmission of a code word, is exploited to facilitate correct code-word recovery. In the first two techniques, applicable to cases in which a code word detected in error is retransmitted several times consecutively, an error-correcting code is used in conjunction with a normal ARQ code to enhance performance even at high error rates. These two techniques have been modified to allow application to protocols in which only one copy is sent each time a code word must be transmitted. Theoretical analysis of the protocols shows that these techniques outperform similar ARQ schemes, particularly for high error rates.     

The upper error bound of a new near-optimal code

A code is implicitly constructed' from a lattice and its Dirichlet regions and, for Gaussian noise, the worst error probability of any code point is upperbounded in closed form by a chi-square distribution. The bound shows that fairly efficient codes can be obtained, particularly, at high signal-to-noise ratio (SNR) the bound approaches asymptotically the error bound of an optimal code. The derivation is by a promising new method in which the Minkowski-H!awka theorem of the geometry of numbers is used in place of the we!l-known random coding arguments.     

Forward error correction concatenated code in DWDM systems

The three concatenated coding schemes of the inner-outer type, the parallel type and the consecutive type to improve the current forward error correction (FEC)coding technologies are proposed for dense wavelengthdivision multiplexing (DWDM) systems, after introducing the development trend of DWDM optical communication systems. The concatenated code is theoretically analyzed.The theoretical analyses and simulation results show that inner-outer concatenated code has a greater redundancy and the decoding of parallel concatenated code is too complex. However, consecutive concatenated code is superior coding scheme with advantages such as better error correction performance, moderate redundancy and easy implementation, therefore it could be better used in high-speed and long-haul DWDM systems.     

An error control system with multiple-stage forward errorcorrections

A robust error control coding system is presented. This system is a cascaded FEC (forward error control) scheme supported by parity retransmissions for further error correction in the erroneous data words. The error performance and throughput efficiency of the system are analyzed. Two specific examples of the error control system are studied. The first example does not use an inner code, and the outer code, which is not interleaved, is a shortened code of the NASA standard RS code over GF(2⁸). The second example, as proposed for NASA uses the same shortened RS code as the base outer code C₂, except that it is interleaved to a depth of 2. It is shown that both examples provide high reliability and throughput efficiency even for high channel bit-error rates in the range of 10^-2     

An integrated error correction and detection system for digitalaudio broadcasting

Hybrid in-band on-channel digital audio broadcasting systems deliver digital audio signals in such a way that is backward compatible with existing analog FM transmission. We present a channel error correction and detection system that is well-suited for use with audio source coders, such as the so-called perceptual audio coder (PAC), that have error concealment/mitigation capabilities. Such error mitigation is quite beneficial for high quality audio signals. The proposed system involves an outer cyclic redundancy check (CRC) code that is concatenated with an inner convolutional code. The outer CRC code is used for error detection, providing flags to trigger the error mitigation routines of the audio decoder. The inner convolutional code consists of so-called complementary punctured-pair convolutional codes, which are specifically tailored to combat the unique adjacent channel interference characteristics of the FM band. We introduce a novel decoding method based on the so-called list Viterbi algorithm (LVA). This LVA-based decoding method, which may be viewed as a type of joint or integrated error correction and detection, exploits the concatenated structure of the channel code to provide enhanced decoding performance relative to decoding methods based on the conventional Viterbi algorithm (VA). We also present results of informal listening tests and other simulations on the Gaussian channel. These results include the preferred length of the outer CRC code for 96-kb/s audio coding and demonstrate that LVA-based decoding can significantly reduce the error flag rate relative to conventional VA-based decoding, resulting in dramatically improved decoded audio quality. Finally, we propose a number of methods for screening undetected errors in the audio domain     

Forward error correction for an atmospheric noise channel

Models for predicting the performance of error correcting codes on an atmospheric noise channel are presented and verified. Two Markov chains are used to model the memory of the atmospheric noise channel. The transition probabilities for these chains are derived from atmospheric noise error processes which were recorded at 306 kHz. The models are used to estimate the probability of codeword error, and these estimates are compared to codeword error rates which are obtained directly from the recorded error processes. The comparisons are made for the Golay code with a variety of bit interleaving depths, and a Reed-Solomon code with a variety of symbol interleaving depths. Both Markov channel models predict the actual performance of the codes with much greater accuracy than the binary symmetric channel. Results for binary convolutional codes are presented     

Worst-case error probability of a spread-spectrum system inenergy-limited interference

We consider a communication channel corrupted by thermal noise and by an unknown and arbitrary interference of bounded energy. For this channel, we derive a simple upper bound to the worst-case error probability suffered by a direct sequence (DS) communication system with error-correction coding, pseudorandom interleaving, and a correlation receiver. This bound is exponentially tight as the block length of the error correcting code becomes large. Numerical examples are given that illustrate the dependence of the bound on the choice of error correcting code, the type of interleaving used, and the relative energy of the Gaussian noise and arbitrary interference     

The worst case probability of undetected error for linear codes onthe local binomial channel

The worst case probability of undetected error for a linear [n,k:q] code used on a local binomial channel is studied. For the two most important cases it is determined in terms of the weight hierarchy of the code. The worst case probability of undetected error is determined explicitly for some classes of codes     

Correcting a specified set of likely error patterns

The main concern of this article is to find linear codes which will correct a set of arbitrary error patterns. Although linear codes which have been designed for correcting random error patterns and burst error patterns can be used, we would like to find codes which will correct a specified set of error patterns with the fewest possible redundant bits. Here, to reduce the complexity involved in finding the code with the smallest redundancy which can correct a specified set of error patterns, algebraic codes whose parity check matrix exhibits a particular structure are considered. If the number of redundant bits is T, the columns of the parity check matrix must be increasing powers of a field element in GF(2^T). Given a set of error patterns to be corrected, computations to determine the code rates possible for these type of codes and hence the redundancy for different codeword lengths are presented. Results for various sets of error patterns suggest that the redundancy of these algebraic codes is close to the minimum redundancy possible for the set of error patterns specified and for any codeword length     

Fast software implementation of error detection codes

Software implementations of error detection codes are considered to be slow compared to other parts of the communication system. This is especially true for powerful error detection codes such as CRC. However, we have found that powerful error detection codes can run surprisingly fast in software. We discuss techniques for, and measure the performance of, fast software implementation of the cyclic redundancy check (CRC), weighted sum codes (WSC), one's-complement checksum, Fletcher (1982) checksum, CXOR checksum, and block parity code. Instruction count alone does not determine the fastest error detection code. Our results show the computer memory hierarchy also affects performance. Although our experiments were performed on a Sun SPARCstation LX, many of the techniques and conclusions will apply to other processors and error detection codes. Given the performance of various error detection codes, a protocol designer can choose a code with the desired speed and error detection power that is appropriate for his network and application     

Encoding and decoding for the minimization of message symbol error rates in linear block codes

Given any fixed linear block code, the error rates for the message symbols depend both on the encoding function and on the decoding map. This research shows how to optimize the choice of a generator matrix and decoding map simultaneously to minimize the error rates for all message symbols. The model used assumes that the distribution of messages is flat and that the distribution of error vectors defining the channel is independent of the message transmitted. In addition, it is shown that, with proper choice of coset leaders, standard array decoding is optimal in this circumstance. The results generalize previously known results on unequal error protection and are sufficiently general to apply when a code is used for error detection only.     

Random codes: minimum distances and error exponents

Minimum distances, distance distributions, and error exponents on a binary-symmetric channel (BSC) are given for typical codes from Shannon's random code ensemble and for typical codes from a random linear code ensemble. A typical random code of length N and rate R is shown to have minimum distance N/spl delta//sub GV/(2R), where /spl delta//sub GV/(R) is the Gilbert-Varshamov (GV) relative distance at rate R, whereas a typical linear code (TLC) has minimum distance N/spl delta//sub GV/(R). Consequently, a TLC has a better error exponent on a BSC at low rates, namely, the expurgated error exponent.     

Mobile radio data transmission—Coding for error control

Error patterns recorded during mobile radio data transmission experiments in London have been used to assess what error control strategies are required to achieve reliable data communication. The performance of error detecting and correcting codes has been investigated and the effects of varying code parameters explored. Results are given for transmission at 462 MHz using data rates of 1200 b/s and 4800 b/s, and the advantages of using a high data rate are considered. Bit interleaving is shown to be a useful way of dispersing bursts of errors, greatly improving the performance of an error correcting code. Fairly simple coding techniques can give a performance which is adequate for many applications, and a high performance is readily possible.     

Repeated use of codes for error detection five times is bad

The undetected error probabilities of codes when used repeatedly to transmit sequences of messages are studied. It is shown that for any code whose rate is greater than zero but less than one, the coding scheme obtained by the repeated use of the code is bad, if used five times or more, and improper if used four times or more. Furthermore, the repeated use of any linear code, over an alphabet greater than five, more than once, is bad and improper     

Single error correcting and double error detecting coding scheme

A new coding technique for single error correction and double error detection in computer memory systems is proposed. The number of 1s in the parity check matrix for the proposed coding is fewer than all currently available codes for this purpose, except in two cases when they are almost equal to that obtained by Hsiao code. This results in simplified encoding and decoding circuitry for error detection and correction.     

Reduced-redundancy product codes for burst error correction

In a typical burst error correction application of a product code of n_v×n_h arrays, one uses an [n_h, n_h-r_h] code C_h that detects corrupted rows, and an [n_v, n_v-r_v] code C_v that is applied to the columns while regarding the detected corrupted rows as erasures. Although this conventional product code scheme offers very good error protection, it contains excessive redundancy, due to the fact that the code C_h provides the code C_v with information on many error patterns that exceed the correction capability of C_v. A coding scheme is proposed in which this excess redundancy is eliminated, resulting in significant savings in the overall redundancy compared to the conventional case, while offering the same error protection. The redundancy of the proposed scheme is n_hr_v+r_h(lnr_v+O(1))+r_v , where the parameters r_h and r_v are close in value to their counterparts in the conventional case, which has redundancy n_hr_v+n_vr_h-r_h r_v. In particular, when the codes C_h and C _v have the same rate and r_h≪n_h, the redundancy of the proposed scheme is close to one-half of that of the conventional product code counterpart. Variants of the scheme are presented for channels that are mostly bursty, and for channels with a combination of random errors and burst errors