New family of single-error correcting codes

A construction is given that combines an(n, M_1, d_1)code with an(n, M_2, d_2 = [frac{1}{2}(d_1 + 1)])code to form a(2n, M_1 M_2, d_1)code. This is used to construct a new family of nongroup single-error correcting codes of all lengthsnfrom2^mto 3 ·2^{m-1} - 1, for everym geq 3. These codes have more codewords than any group code of the same length and minimum distance. A number of other nongroup codes are also obtained. Examples of the new codes are (16,2560,3) and (16,36,7) codes, both having more codewords than any comparable group code.     

A superfast algorithm for single-error correction in rrns and hardware implementation

The modular algebraic structure of the residue number systems (RNS) leads to modularity and parallelism in the hardware implementation for the RNS-based arithmetic processor [1], [2]. Both modularity and parallelism are essential to fully utilize the very-large-scale integrated (VLSI) technology [3]. In this work, a superfast algorithm for correcting single residue errors in the RNS is developed with a slight increase in redundancy. Based on this algorithm and another recently proposed fast algorithm, two architectures are designed for their hardware implementation. The hardware complexity for this superfast algorithm isO(k) while the hardware complexity for previously known algorithms isO(k ²). The performance of this new technique is compared to the previously known techniques in terms of computational speed and other criteria.     

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.     

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     

Burst-error correction for randomly-chosen binary group codes

A method of burst-error correction is presented which works for a large class of codes. Any single burst of length up to somewhat less than one half the number of check digits can be corrected. The number of decoding computations per code word is proportional to the square of the code length for long codes. The code can be chosen in a random manner, except that several trials may sometimes be necessary in order to find a suitable code.     

Optimum shortened cyclic codes for burst-error correction

This paper is concerned with the construction of the most efficient shortened cyclic (pseudo-cyclic) codes that can correct every burst-error of lengthbor less. These codes have the maximum number of information digitskamong all shortened cyclic burst-bcodes with a given number of check digitsr. The search procedure described is readily programmable for computer execution and efficient particularly for the case whereris close to the theoretical minimum of2bcheck digits. For2 leq b leq 10, several optimum shortened cyclic codes in the above-mentioned sense have been found. Their code-lengths and generators are tabulated in this paper.     

The simplex codes and other even-weight binary linear codes for error correction

The probability of correct decoding on the binary-symmetric channel is studied. In particular, a class of codes with the same lengths and dimensions as the linear simplex codes, but with larger probability of correct decoding for all parameters p, 0 < p < 1/2, is given.     

New array codes for multiple phased burst correction

An optimal family of array codes over GF(q) for correcting multiple phased burst errors and erasures, where each phased burst corresponds to an erroneous or erased column in a code array, is introduced. As for erasures, these array codes have an efficient decoding algorithm which avoids multiplications (or divisions) over extension fields, replacing these operations with cyclic shifts of vectors over GF(q). The erasure decoding algorithm can be adapted easily to handle single column errors as well. The codes are characterized geometrically by means of parity constraints along certain diagonal lines in each code array, thus generalizing a previously known construction for the special case of two erasures. Algebraically, they can be interpreted as Reed-Solomon codes. When q is primitive in GF(q), the resulting codes become (conventional) Reed-Solomon codes of length P over GF(q^p-1), in which case the new erasure decoding technique can be incorporated into the Berlekamp-Massey algorithm, yielding a faster way to compute the values of any prescribed number of errors     

Optimal space-frequency Group codes for MIMO-OFDM system

Space-frequency (SF) group codes are designed for multiple-input multiple-output orthogonal frequency-division multiplexing (MIMO-OFDM) systems. A rather general channel model is assumed, where the channel is frequency-selective Rayleigh fading with arbitrary power-delay profile. It is shown that the SF group code has a symmetric distance structure like the space-time group code, if the group consists of diagonal matrices. A scenario where the multiple codewords are loaded onto the subcarriers of the OFDM system in parallel is considered. The optimality condition on the choice of subcarrier allocation is found, and an optimal subcarrier-allocation scheme is proposed. A transmit scheme where rotated versions of the same signal are transmitted from different transmit antennas is proposed, and it is shown that it satisfies the optimality condition. Then matrix groups are designed which guarantee that the resulting SF codes are full rank. Numerical comparisons with recently published techniques in the literature verify our improved performance.     

Optimal linear identifying codes

Identifying codes can be used to locate malfunctioning processors. We say that a code C of length n is a linear (1,/spl les/l)-identifying code if it is a subspace of F/sub 2//sup n/ and for all X,Y/spl sube/F/sub 2//sup n/ such that |X|, |Y|/spl les/l and X/spl ne/Y, we have /spl cup//sub x/spl isin/X/(B(x)/spl cap/C)/spl ne//spl cup/y/spl isin/Y(B(y)/spl cap/C). Strongly (1,/spl les/l)-identifying codes are a variant of identifying codes. We determine the cardinalities of optimal linear (1,/spl les/l)-identifying and strongly (1,/spl les/l)-identifying codes in Hamming spaces of any dimension for locating any at most l malfunctioning processors.     

Two-dimensional correction for min-sum decoding of irregular LDPC codes

Two-dimensional (2-D) correction schemes are proposed to improve the performance of conventional min-sum (MS) decoding of irregular low density parity check codes. An iterative procedure based on parallel differential optimization is presented to obtain the optimal 2-D factors. Both density evolution analysis and simulation show that the proposed method provides a comparable performance as belief propagation (BP) decoding while requiring less complexity. Interestingly, the new method exhibits a lower error floor than that of BP decoding. With respect to conventional MS and 1-D normalized MS decodings, the 2-D normalized MS offers a better performance. The 2-D offset MS decoding exhibits a similar behavior.     

Runlength limited codes for random and burst error correction

A product code approach to the design of multiple error correcting runlength limited codes is presented. In contrast to recent coding schemes of this type they are based entirely on binary coding operations and are therefore relatively simple to realise in hardware. A table of some illustrative codes is presented.<>     

Optimal codes for minimax criterion on error detection

Nonlinear quadratic codes that are optimal for the minimax error detection are presented. Characteristic functions for these codes are asymptotically bent. For a given block size n and the number of codewords |C|, these codes minimize max Q(e), e≠0, where Q(e) is the conditional error-masking probability, given the error pattern e. The codewords are blocks of n symbols from GF(q). Encoding and decoding procedures for the codes are described     

Optimal prefix codes for sources with two-sided geometricdistributions

A complete characterization of optimal prefix codes for off-centered, two-sided geometric distributions of the integers is presented. These distributions are often encountered in lossless image compression applications, as probabilistic models for image prediction residuals. The family of optimal codes described is an extension of the Golomb codes, which are optimal for one-sided geometric distributions. The new family of codes allows for encoding of prediction residuals at a complexity similar to that of Golomb codes, without recourse to the heuristic approximations frequently used when modifying a code designed for nonnegative integers so as to apply to the encoding of any integer. Optimal decision rules for choosing among a lower complexity subset of the optimal codes, given the distribution parameters, are also investigated, and the relative redundancy of the subset with respect to the full family of optimal codes is bounded     

Optimal codes (Corresp.)

Some known results on the nonexistence of linear optimal codes can be very easily proved using results on the weight distribution of such codes.     

LDPC码基于双修正因子的剩余度置信传播译码算法

通过对LDPC码的RBP和NWRBP译码算法进行研究,针对算法在译码过程中运算量过大,不利于在硬件上实现的问题,提出一种改进型的RBP和NWRBP译码算法。该算法在更新从检验节点到变量节点的信息时,采用最小和算法得出近似值,以此降低译码复杂度。同时,为了弥补近似值所带来的译码性能损失,引入乘性修正因子和加性修正因子来提高译码性能。     

Using codes for error correction and detection (Corresp.)

A linear codeCover GF(q)is good fort-error-correction and error detection ifP(C,t;epsilon) leq P(C,t;(q - 1)/q)for allepsilon, 0 leq epsilon leq (q - 1)/q, whereP(C, t; epsilon)is the probability of an undetected error after a codeword inCis transmitted over aq-ary symmetric channel with error probabilityepsilonand correction is performed for all error patterns withtor fewer errors. A sufficient condition for a code to be good is derived. This sufficient condition is easy to check, and examples to illustrate the method are given.     

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.     

Hybrid burst erasure correction of LDPC codes

In this letter, burst erasure correction of low density parity check codes based on a hybrid approach is presented. The proposed method preserves as much as possible the original low density representation and augments it by specific check sums judiciously selected.     

Optimal regular LDPC codes for the binary erasure channel

We prove that for any given R between 0 and 1 the best threshold value for a regular LDPC code of rate R with common variable degree v and common check degree c occurs when v is at least 3 and is minimal subject to the condition R=1-v/c.