Error detection in decimal numbers

The code described detects those errors people most frequently make when transmitting decimal numbers. N digit numbers are encoded by appending a check digit determined by a computation involving the N digits. N + 1 digit numbers are "checked" by another computation. If an N digit number is encoded, and then any single digit is altered or any adjacent pair of digits is interchanged, the "check" computation will detect the error. A possible application: X-rays in hospitals are often indexed by patient number. Physicians request X-rays by number. Errors are discovered only when the plate is pulled and found to correspond to the wrong patient. By then the requester may no longer be available to supply the correct number. If numbers were encoded, most errors would be detected at the time the request was made.     

Single-digit-correcting decimal codes

With codes using digits to a higher scale than binary, it is necessary to distinguish between the size of an error (e.g. measured in Lee distance) and the number of digits in error. But some of the principles of error-correcting binary codes can be used in the construction of single-digit-correcting decimal codes.     

Efficient error detection in Double Error Correction BCH codes for memory applications

To prevent soft errors from causing data corruption, memories are commonly protected with Error Correction Codes (ECCs). To minimize the impact of the ECC on memory complexity simple codes are commonly used. For example, Single Error Correction (SEC) codes, like Hamming codes are widely used. Power consumption can be reduced by first checking if the word has errors and then perform the rest of the decoding only when there are errors. This greatly reduces the average power consumption as most words will have no errors. In this paper an efficient error detection scheme for Double Error Correction (DEC) Bose–Chaudhuri–Hocquenghem (BCH) codes is presented. The scheme reduces the dynamic power consumption so that it is the same that for error detection in a SEC Hamming code.     

Grammar-based codes: a new class of universal lossless source codes

We investigate a type of lossless source code called a grammar-based code, which, in response to any input data string x over a fixed finite alphabet, selects a context-free grammar G_x representing x in the sense that x is the unique string belonging to the language generated by G_x. Lossless compression of x takes place indirectly via compression of the production rules of the grammar G_x. It is shown that, subject to some mild restrictions, a grammar-based code is a universal code with respect to the family of finite-state information sources over the finite alphabet. Redundancy bounds for grammar-based codes are established. Reduction rules for designing grammar-based codes are presented     

Error detecting capabilities of the shortened Hamming codes adoptedfor error detection in IEEE Standard 802.3

Investigates the error detecting capabilities of the shortened hamming codes adopted for error detection in IEEE Standard 802.3. These codes are also used for error detection in the data link layer of the Ethernet, a local area network. The authors compute the weight distributions for various code lengths. From the results, they show the probability of undetectable error and that of detectable error for a binary symmetric channel with bit-error rate 10^-5⩽ϵ⩽ 1/2. They also find the minimum distance of the shortened code of length n for 33 ⩽n ⩽12144 and the double-burst detecting capabilities     

On a class of cyclically permutable error-correcting codes

Cyclically permutable codes have error-correcting properties which are invariant under arbitrary cyclic permutation of any of their code words. This paper summarizes the results of an empirical investigation of certain of these codes, which have parameters not covered by a previous paper of E. N. Gilbert.^{1}These codes are thought to be nearly optimal. Estimates of the obtainable number of code words are given. The codes may be suitable for use in certain asynchronous multiplex communication systems.     

Weight distribution of a class of binary block codes formed from RCPC codes

In this paper, we study the weight enumerator and the numerical performance of a class of binary linear block codes formed from a family of rate-compatible punctured convolutional (RCPC) codes. Also, we present useful numerical results for a well-known family of RCPC codes.     

On a class of majority-logic decodable cyclic codes

A new infinite class of cyclic codes is studied. Codes of this class can be decoded in a step-by-step manner, using` majority logic. Some previously known codes fall in this class, and thus admit simpler decoding procedures. As random error-correcting codes, the codes are nearly as powerful as the Bose-Chaudhuri codes.     

A class of polynomial codes

We present a construction of linear codes from polynomials. It turns out that some new codes are obtained from our construction and improve parameters of Brouwer's table.     

Error control codes for QAM signalling

A class of block codes is described which exploits the properties of quadrature amplitude modulation signal constellations whose points lie on a square grid. The simplest codes in the class have block lengths 4 and 8 and offer coding gains of 3 dB and 4.5 dB, respectively.     

Error recovery for variable length codes

When an error occurs in the encoded bit stream produced by a variable length code, the decoder may lose synchronization. A state model for synchronization recovery is developed, and a method for determining the expected span of source symbols lost is presented. The performance of various codes with respect to error recovery is discussed. Two examples are given where equivalent optimal codes have a marked difference in their error recovery characteristics. Some open problems are indicated.     

On a new class of codes for identifying vertices in graphs

We investigate a new class of codes for the optimal covering of vertices in an undirected graph G such that any vertex in G can be uniquely identified by examining the vertices that cover it. We define a ball of radius t centered on a vertex υ to be the set of vertices in G that are at distance at most t from υ. The vertex υ is then said to cover itself and every other vertex in the ball with center υ. Our formal problem statement is as follows: given an undirected graph G and an integer t⩾1, find a (minimal) set C of vertices such that every vertex in G belongs to a unique set of balls of radius t centered at the vertices in C. The set of vertices thus obtained constitutes a code for vertex identification. We first develop topology-independent bounds on the size of C. We then develop methods for constructing C for several specific topologies such as binary cubes, nonbinary cubes, and trees. We also describe the identification of sets of vertices using covering codes that uniquely identify single vertices. We develop methods for constructing optimal topologies that yield identifying codes with a minimum number of codewords. Finally, we describe an application of the theory developed in this paper to fault diagnosis of multiprocessor systems     

Product accumulate codes: a class of codes with near-capacity performance and low decoding complexity

We propose a novel class of provably good codes which are a serial concatenation of a single-parity-check (SPC)-based product code, an interleaver, and a rate-1 recursive convolutional code. The proposed codes, termed product accumulate (PA) codes, are linear time encodable and linear time decodable. We show that the product code by itself does not have a positive threshold, but a PA code can provide arbitrarily low bit-error rate (BER) under both maximum-likelihood (ML) decoding and iterative decoding. Two message-passing decoding algorithms are proposed and it is shown that a particular update schedule for these message-passing algorithms is equivalent to conventional turbo decoding of the serial concatenated code, but with significantly lower complexity. Tight upper bounds on the ML performance using Divsalar's (1999) simple bound and thresholds under density evolution (DE) show that these codes are capable of performance within a few tenths of a decibel away from the Shannon limit. Simulation results confirm these claims and show that these codes provide performance similar to turbo codes but with significantly less decoding complexity and with a lower error floor. Hence, we propose PA codes as a class of prospective codes with good performance, low decoding complexity, regular structure, and flexible rate adaptivity for all rates above 1/2.     

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.     

Spectral characteristics of a class of DC free error-correctingtransmission codes

A class of DC free codes proposed by Herro (1987) is examined and given an alphabetic line code interpretation enabling the code spectra to be evaluated. These and also the disparity bounds are found to be strongly influenced by the choice of disparity modification vectors, appropriate new selection rules are introduced yielding improved run length and disparity characteristics     

Construction and decoding of a class of algebraic geometry codes

A class of codes derived from algebraic plane curves is constructed. The concepts and results from algebraic geometry that were used are explained in detail; no further knowledge of algebraic geometry is needed. Parameters, generator and parity-check matrices are given. The main result is a decoding algorithm which turns out to be a generalization of the Peterson algorithm for decoding BCH decoder codes     

The equivalence of rank permutation codes to a new class of binary codes (Corresp.)

An equivalence between the rank permutation codes and a new class of binary codes has been observed. A binary code may be generated by direct transformation of a permutation code. The binary codes are usually nonlinear and may be decoded by the inverse transformation and rank correlation of the equivalent permutation.     

The average binary weight-enumerator for a class of generalizedReed-Solomon codes

An explicit weight-enumerator for the set of binary expansions of a class of generalized Reed-Solomon codes is derived. This enumerator is then used to show that most of these binary codes are asymptotically good, and to bound the rates of self-intersecting codes     

Error performances of multi shift-register convolutional self-doubly-orthogonal codes

A class of orthogonal convolutional codes using a multi shift-register encoder and featuring self-doubly-orthogonal properties is analyzed under iterative decoding. The lower bounds of error performances of these codes can be approached within typically three to five iterations at moderate signal-to-noise ratios using either iterative threshold (TH) decoding or belief propagation (BP) decoding. Compared with iterative BP decoding, it is shown that iterative threshold decoding for these codes yields a much lower complexity at the same decoding latency.     

Single- and multiple-burst-correcting properties of a class of cyclic product codes

The direct product ofpsingle parity-check codes of block lengthsn_1,n_2, cdots ,n_pis a cyclic code of block lengthn_1 times n_2 times cdots times n_pwith(n_1 - 1) times (n_2 - 1) times cdots times (n_p - 1)information symbols per block, if the integersn_1,n_2 cdots ,n_pare relatively prime in pairs. A lower bound for the single-burst-correction (SBC) capability of these codes is obtained. Then, a detailed analysis is made forp = 3, and it is shown that the codes can correct one long burst or two short bursts of errors. A lower bound for the double-burst-correction (DBC) capability is derived, and a simple decoding algorithm is obtained. The generalization to correcting an arbitrary number of bursts is discussed.