Parameters of Goppa codes revisited

We discuss parameters of Goppa (1970) codes, such as minimum distance, covering radius, distance distribution, and generalized Hamming weights. By a variation on the exponential sums method and combinatorial arguments, we sharpen known bounds on these parameters     

On relations between covering radius and dual distance

The covering radius of a code tells us how far in the sense of Hamming distance an arbitrary word of the ambient space can be from the code. For a few decades this parameter has been widely studied. We estimate the covering ratios of a code when the dual distance is known. We derive a new bound on covering radii of linear codes. It improves essentially on the previously known estimates in a certain wide range. We also study asymptotic bounds on the cardinality of constant weight codes     

Improving the Upper Bounds on the Covering Radii of Binary Reed–Muller Codes

By deriving bounds on character sums of Boolean functions and by using the characterizations, due to Kasami , of those elements of the Reed-Muller codes whose Hamming weights are smaller than twice and a half the minimum distance, we derive an improved upper bound on the covering radius of the Reed-Muller code of order 2, and we deduce improved upper bounds on the covering radii of the Reed-Muller codes of higher orders     

Covering radius, codimension, and dual-distance width

Upper bounds on the covering radius of codes with a given cardinality and a given dual-distance width are derived. Using an entirely new method, some results published by C. Delorme and P. Sole (1991) for linear codes are generalized, and results are derived for unrestricted codes that have no previous analogue. For some classes of codes, when the parameters lie within certain intervals, results improve asymptotically on the upper bounds published by A.A. Tietavainen (1990) relating the covering radius with the dual distance     

An Analysis of Blocking Switches Using Error Control Codes

We study the relationship between the degree of blocking and the amount of resource speedup necessary for blocking switches to possess the capabilities of nonblocking switches. We construct an analogy between switch configurations and the codewords of certain error control codes for which we use space covering ideas to derive relations between speedup and number of switch configurations. To derive the necessary speedup for nonblocking, we use two sphere packing bounds: the Hamming bound and the Gilbert-Varshamov bound. To construct nonblocking switches with a given speedup we use maximum distance separable codes. We consider both multicast and point to point scenarios.     

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.     

Combinatorial analysis of the minimum distance of turbo codes

In this paper, new upper bounds on the maximum attainable minimum Hamming distance of turbo codes with arbitrary-including the best-interleavers are established using a combinatorial approach. These upper bounds depend on the interleaver length, the code rate, and the scramblers employed in the encoder. Examples of the new bounds for particular turbo codes are given and discussed. The new bounds are tighter than all existing ones and prove that the minimum Hamming distance of turbo codes cannot asymptotically grow at a rate more than the third root of the codeword length     

Short codes with a given covering radius

The covering radius r of a code is the maximum distance from any vector in the space containing the code to the nearest codeword. The authors introduce a new function l(m,r), called the length function, which equals the smallest length of a binary code of codimension m and covering radius r. They investigate basic properties of the length function. Projective geometries over larger fields are used to construct families of codes which improve significantly the upper bound for l(m,2) obtained by amalgamation of Hamming codes. General methods are developed for ruling out the existence of codes of covering radius 2 with a given codimension and length resulting in lower bounds for l(m,2). A table is presented which gives the best results now known for l(m,r) with m⩽12 and r⩽12     

Bounds on distance distributions in codes of known size

We treat the problem of bounding components of the possible distance distributions of codes given the knowledge of their size and possibly minimum distance. Using the Beckner inequality from harmonic analysis, we derive upper bounds on distance distribution components which are sometimes better than earlier ones due to Ashikhmin, Barg, and Litsyn. We use an alternative approach to derive upper bounds on distance distributions in linear codes. As an application of the suggested estimates we get an upper bound on the undetected error probability for an arbitrary code of given size. We also use the new bounds to derive better upper estimates on the covering radius, as well as a lower bound on the error-probability threshold, as a function of the code's size and minimum distance.     

Improved multicovering bounds from linear inequalities and supercodes

The multicovering radii of a code are natural generalizations of the covering radius in which the goal is to cover all m-tuples of vectors for some m as cheaply as possible. In this correspondence, we describe several techniques for obtaining lower bounds on the sizes of codes achieving a given multicovering radius. Our main method is a generalization of the method of linear inequalities based on refined weight distributions of the code. We also obtain a linear upper bound on the 2-covering radius. We further study bounds on the sizes of codes with a given multicovering radius that are subcodes of a fixed code. We find, for example, constraints on parity checks for codes with small ordinary covering radius.     

Krawtchouk polynomials and universal bounds for codes and designsin Hamming spaces

Universal bounds for the cardinality of codes in the Hamming space F_rⁿ with a given minimum distance d and/or dual distance d' are stated. A self-contained proof of optimality of these bounds in the framework of the linear programming method is given. The necessary and sufficient conditions for attainability of the bounds are found. The parameters of codes satisfying these conditions are presented in a table. A new upper bound for the minimum distance of self-dual codes and a new lower bound for the crosscorrelation of half-linear codes are obtained     

Packing radius, covering radius, and dual distance

Tietaivainen (1991) derived an upper bound on the covering radius of codes as a function of the dual distance. This was generalized to the minimum distance, and to Q-polynomial association schemes by Levenshtein and Fazekas. Both proofs use a linear programming approach. In particular, Levenshtein and Fazekas (1990) use linear programming bounds for codes and designs. In this article, proofs relying solely on the orthogonality relations of Krawtchouk (1929), Lloyd, and, more generally, Krawtchouk-adjacent orthogonal polynomials are derived. As a by-product upper bounds on the minimum distance of formally self-dual binary codes are derived     

Combinatorial bounds for list decoding

Informally, an error-correcting code has "nice" list-decodability properties if every Hamming ball of "large" radius has a "small" number of codewords in it. We report linear codes with nontrivial list-decodability: i.e., codes of large rate that are nicely list-decodable, and codes of large distance that are not nicely list-decodable. Specifically, on the positive side, we show that there exist codes of rate R and block length n that have at most c codewords in every Hamming ball of radius H^-1(1-R-1/c)·n. This answers the main open question from the work of Elias (1957). This result also has consequences for the construction of concatenated codes of good rate that are list decodable from a large fraction of errors, improving previous results of Guruswami and Sudan (see IEEE Trans. Inform. Theory, vol.45, p.1757-67, Sept. 1999, and Proc. 32nd ACM Symp. Theory of Computing (STOC), Portland, OR, p. 181-190, May 2000) in this vein. Specifically, for every ε > 0, we present a polynomial time constructible asymptotically good family of binary codes of rate Ω(ε⁴) that can be list-decoded in polynomial time from up to a fraction (1/2-ε) of errors, using lists of size O(ε^-2). On the negative side, we show that for every δ and c, there exists τ < δ, c₁ > 0, and an infinite family of linear codes {C_i}_i such that if n_i denotes the block length of C_i, then C _i has minimum distance at least δ · n_i and contains more than c₁ · n_i^c codewords in some Hamming ball of radius τ · n_i. While this result is still far from known bounds on the list-decodability of linear codes, it is the first to bound the "radius for list-decodability by a polynomial-sized list" away from the minimum distance of the code     

Linear programming bounds for codes in grassmannian spaces

In this paper, we develop the linear programming method to obtain bounds for the cardinality of Grassmannian codes endowed with the chordal distance. We obtain a bound and its asymptotic version that generalize the well-known bound for codes in the real projective space obtained by Kabatyanskiy and Levenshtein, and improve the Hamming bound for sufficiently large minimal distances     

广义Hamming重量上,下界的对偶定理

本文给出了一种广义Ｈａｍｍｉｎｇ重量上、下界的对偶定理。即若给定一个码的对偶码的广义Ｈａｍｍｉｎｇ重量上界（或者下界），可以给出该码的广义Ｈａｍｍｉｎｇ重量上界（或者下界）。Ｈ．Ｓｔｉｃｈ－ｎｏｔｈ（１９９４）曾给出了迹码（如ＢＣＨ码和Ｇｏｐｐａ码的对偶码）的广义Ｈａｍｍｉｎｇ重量一种上、下界，如果采用本文结果就可以给出迹码的对偶码的广义Ｈａｍｍｉｎｇ重量一种上、下界。因此，本文的结果是Ｈ．Ｓｔｉｃｈｎｏｔｈ的结果的有益补充     

Optimal self-dual codes over F/sub 2//spl times/F/sub 2/ with respect to the Hamming weight

In this paper, we study optimal self-dual codes and type IV self-dual codes over the ring F/sub 2//spl times/F/sub 2/ of order 4. We give improved upper bounds on minimum Hamming and Lee weights for such codes. Using the bounds, we determine the highest minimum Hamming and Lee weights for such codes of lengths up to 30. We also construct optimal self-dual codes and type IV self-dual codes.     

Optimal binary vector quantization via enumeration of coveringcodes

Binary vector quantization (BVQ) refers to block coding of binary vectors under a fidelity measure. Covering codes were studied as a means of lattice BVQ. But a further source coding problem hidden in the equivalence of covering codes has seemingly eluded attention. Given a d-dimensional hypercube (code space), equivalent covering codes of the same covering radius but of different codewords have different expected BVQ distortions for a general probability mass function. Thus one can minimize, within the code equivalence, the expected distortion over all different covering codes. This leads a two-stage optimization scheme for BVQ design. First we use an optimal covering code to minimize the maximum per-vector distortion at a given rate. Then under the minmax constraint, we minimize the expected quantization distortion. This minmax constrained BVQ method (MCBVQ) controls both the maximum and average distortions, and hence improves subjective quality of compressed binary images, MCBVQ also avoids poor local minima that may trap the generalized Lloyd method. The [7,4] Hamming code and [8,4] extended Hamming code are found to be particularly suitable for MCBVQ on binary images. An efficient and simple algorithm is introduced to enumerate all distinct [7,4] Hamming/[8,4] extended Hamming codes and compute the corresponding expected distortions in optimal MCBVQ design. Furthermore, MCBVQ using linear covering codes has a compact codebook and a fast syndrome-encoding algorithm     

Improved Performance Upper Bounds for Terminated Convolutional Codes

In this letter, we propose tight performance upper bounds for convolutional codes terminated with an input sequence of finite length. To obtain the upper bounds, a weight enumerator is defined to represent the relation between the Hamming distance of the coded output and the Hamming distance of the input bits of the code. The upper bounds on frame error rate (FER) and average bit error rate (BER) are obtained from the weight enumerator. A simple method is presented to compute the weight enumerator of a terminated convolutional code based on a modified trellis diagram.     

Source and channel rate allocation for channel codes satisfying theGilbert-Varshamov or Tsfasman-Vladut-Zink bounds

We derive bounds for optimal rate allocation between source and channel coding for linear channel codes that meet the Gilbert-Varshamov or Tsfasman-Vladut-Zink (1984) bounds. Formulas giving the high resolution vector quantizer distortion of these systems are also derived. In addition, we give bounds on how far below the channel capacity the transmission rate should be for a given delay constraint. The bounds obtained depend on the relationship between channel code rate and relative minimum distance guaranteed by the Gilbert-Varshamov bound, and do not require sophisticated decoding beyond the error correction limit. We demonstrate that the end-to-end mean-squared error decays exponentially fast as a function of the overall transmission rate, which need not be the case for certain well-known structured codes such as Hamming codes     

关于Goppa码、BCH码的广义Hamming重量

本文研究了Goppa码、BCH码的广义Hamming重量,给出了Goppa码的广义Hamming重量的一个下界以及求该下界的一个算法;对于本原、狭义BCH码,给出了后面一些广义Hamming重量的确切值。