Construction for binary asymmetric error-correcting codes (Corresp.)

A construction method of asymmetric error-correcting codes is proposed. In this method, at-fold asymmetric error-correcting code of lengthn-1is constructed by expurgating and puncturing anyt-fold symmetric error-correcting code of lengthn. These codes are designed for use on binary asymmetric channels, such as large-scale integration (LSI) memory protection, on which transition is one-way.     

Bounds and constructions for binary asymmetric error-correcting codes (Corresp.)

By use of known bounds on constant-weight binary codes, new uppper bounds are obtained on the cardinality of binary codes correcting asymmetric errors. Some constructions are exhibited that come close to these bounds. For single-error-correcting codes some constructions are derived from the Steiner systemS(5, 6,12), and for double-error-correcting codes some constructions are derived from the Nordstrom-Robinson code.     

New single-error-correcting codes

A matrix construction of nonlinear error-correcting codes is considered. It is shown how this construction and some related theorems can be applied to old codes to get new codes with minimum distance 3. In total 13 new binary single-error-correcting codes of length at most 511 are obtained     

Bounds on mixed binary/ternary codes

Upper and lower bounds are presented for the maximal possible size of mixed binary/ternary error-correcting codes. A table up to length 13 is included. The upper bounds are obtained by applying the linear programming bound to the product of two association schemes. The lower bounds arise from a number of different constructions     

Bounds and constructions for codes correcting unidirectional errors

A brief introduction is given on the theory of codes correcting unidirectional errors, in the context of symmetric and asymmetric error-correcting codes. Upper bounds on the size of a code of length n correcting t or fewer unidirectional errors are then derived. Methods in which codes correcting up to t unidirectional errors are constructed by expurgating t-fold asymmetric error-correcting codes or by expurgating and puncturing t -fold symmetric error-correcting codes are also presented. Finally, tables summarizing some results on the size of optimal unidirectional error-correcting codes which follow from these bounds and constructions are given     

Nonrandom binary superimposed codes

A binary superimposed code consists of a set of code words whose digit-by-digit Boolean sums(1 + 1 = 1)enjoy a prescribed level of distinguishability. These codes find their main application in the representation of document attributes within an information retrieval system, but might also be used as a basis for channel assignments to relieve congestion in crowded communications bands. In this paper some basic properties of nonrandom codes of this family are presented, and formulas and bounds relating the principal code parameters are derived. Finally, there are described several such code families based upon (1)q-nary conventional error-correcting codes, (2) combinatorial arrangements, such as block designs and Latin squares, (3) a graphical construction, and (4) the parity-check matrices of standard binary error-correcting codes.     

Computing the word-, symbol-, and bit-error rates for block error-correcting codes

In order to select error-correcting codes for various applications, their performances have to be determined. However, when targeting error-rate computations for block error-correcting codes, many required results are missing in the coding literature. Even in the simple case of binary codes and bounded-distance decoding, classical texts do not provide a bit-error rate (BER) expression taking into account both decoding errors and failures. In the case of nonbinary codes used to protect binary symbols, such as Reed-Solomon codes in many applications, there is no available result making realistic channel assumptions in order to derive BERs. Finally, for the more complex case of complete decoding, only some bounds are available, such as the union one. This paper presents new approximations of error rates for block error-correcting codes as a function of the channel BER (crossover probability). We extend an existing approximation in order to consider not only bounded-distance decoding, but also complete "nearest-neighbor" decoding. We also develop approximations able to deal with nonbinary codes. Combined with state-of-the-art approximations, these new results enable the computation of bit-, symbol-, and word-error rates in various decoding situations. They can consider separately errors related to erroneously decoded words and decoding failures, and they provide accurate estimates of error rates. As they do not require detailed information about the structure of codes, they are general enough to be used in simple comparisons between different codes, avoiding the need for simulations.     

二元Goppa码最小距离的新下限

二元Goppa码是一大类很有用的纠错码。但是如何求二元Goppa码的真正最小距离至今没有解决。本文将导出二元Goppa码最小距离的新下限,这个新下限改进了Y.Sugiyama等(1976)和作者(1983)文章的结果。本文的方法不难推广到其他Goppa码中去。     

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.     

On error-correcting balanced codes

Results are presented on families of balanced binary error-correcting codes that extend those in the literature. The idea is to consider balanced blocks as symbols over an alphabet and to construct error-correcting codes over that alphabet. Encoding and decoding procedures are presented. Several improvements to the general construction are discussed     

Asymptotic bounds on frameproof codes

We study the asymptotic behavior of frameproof codes. Some lower bounds are derived from the theory of error-correcting codes. In particular, the lower bound obtained directly by applying algebraic-geometry codes is improved by employing the Jacobian group structure of algebraic curves     

Short error-correcting codes

Theoretical bounds on the error-correcting capabilities of binary codes can be found for very long codes in terms of k/n and t/n. It is pointed out that these bounds are only valid for very long codes, and that the relationship between k/n and t/n is not a sufficient criterion for the practical value of short codes.     

On general Gilbert bounds

We define a distance measure for block codes used over memoryless channels and show that it is related to upper and lower bounds on the low-rate error probability in the same way as Hamming distance is for binary block codes used over the binary symmetric channel. We then prove general Gilbert bounds for block codes using this distance measure. Some new relationships between coding theory and rate-distortion theory are presented.     

Further results on the covering radius of codes

A number of upper and lower bounds are obtained forK(n, R), the minimal number of codewords in any binary code of lengthnand covering radiusR. Several new constructions are used to derive the upper bounds, including an amalgamated direct sum construction for nonlinear codes. This construction works best when applied to normal codes, and we give some new and stronger conditions which imply that a linear code is normal. An upper bound is given for the density of a covering code over any alphabet, and it is shown thatK(n + 2, R + 1) leq K(n, R)holds for sufficiently largen.     

A new lower bound for the minimum distance of binary Goppa codes

Binary Goppa codes are a large and powerful family of error-correcting codes. But how to find the true minimum distance of binary Goppa codes is not solved yet. In this paper a new lower bound for the minimum distance of binary Goppa codes is shown. This new lower bound improves the results in Y. Sugiyama (1976) and Feng Guiliang's (1983) papers. The method in this paper can be generalized to other Goppa codes easily.     

An updated table of minimum-distance bounds for binary linear codes

In 1973 Helgert and Sfinaff published a table of upper and lower bounds on the maximum minimum-distance for binary linear error-correcting codes up to length127. This article presents an updated table incorporating numerous improvements that have appeared since then. To simplify the updating task the author has developed a computer program that systematically investigates the consequences of each improvement by applying several well-known general code-construction techniques. This program also made it possible to check the original table. Furthermore, it offers a quick and reliable update service for future improvements.     

Some new binary codes correcting asymmetric/unidirectional errors

The authors give a tabulation of the numbers of codewords in new binary codes with the asymmetric/unidirectional error-correcting capabilities of 3, 4, 5, 6 for lengths 14, 15, . . . , 23. The new codes have greater sizes than the known codes for 14⩽n⩽23 and 3⩽t⩽6     

A new multilevel coding method using error-correcting codes

A new multilevel coding method that uses several error-correcting codes is proposed. The transmission symbols are constructed by combining symbols of codewords of these codes. Usually, these codes are binary error-correcting codes and have different error-correcting capabilities. For various channels, efficient systems can be obtained by choosing these codes appropriately. Encoding and decoding procedures for this method are relatively simple compared with those of other multilevel coding methods. In addition, this method makes effective use of soft-decisions to improve the performance of decoding. The decoding error probability is analyzed for multiphase modulation, and numerical comparisons to other multilevel coding systems are made. When equally complex systems are compared, the new system is superior to other multilevel coding systems.     

Error-Correcting Codes Against the Worst-Case Partial-Band Jammer

This paper provides performance analyses of a broad spectrum of error-correcting codes in an antijam communication system under worst-case partial-band noise jamming conditions. These analyses demonstrate the coding advantages available for systems operating with and without frequency diversity. Utilizing both the exact approach (where possible) and upper-bounding approaches (Chernoff and union bounds), the decoded bit error rates for typical error-correcting codes (binary andM-ary, block and convolutional) have been obtained, and these codes have been compared according to theE_{b}/N_{0}required to achieve a bit error rate of 10^-5. The best performance is achieved with the use ofM-ary signaling and optimum diversity withM-ary codes, such as Reed-Solomon block codes, dual-kconvolutional codes, convolutional orthogonal codes, or concatenated codes.     

Improved Gilbert-Varshamov bound for constrained systems

Nonconstructive existence results are obtained for block error-correcting codes whose codewords lie in a given constrained system. Each such system is defined as a set of words obtained by reading the labels of a finite directed labeled graph. For a prescribed constrained system and relative minimum distance δ, the new lower bounds on the rate of such codes improve on those derived recently by V.D. Kolesnik and V.Y. Krachkovsky (1991). The better bounds are achieved by considering a special subclass of sequences in the constrained system, namely, those having certain empirical statistics determined by δ