共查询到20条相似文献,搜索用时 46 毫秒
1.
Levy-dit-Vehel F. Litsyn S. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1997,43(6):1811-1819
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 相似文献
2.
On relations between covering radius and dual distance 总被引:1,自引:0,他引:1
Ashikhmin A.E. Honkala I.S. Laibonen T.K. Litsyn S.N. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1999,45(6):1808-1816
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 相似文献
3.
Carlet C. Mesnager S. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2007,53(1):162-173
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 相似文献
4.
Sole P. Stokes P. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1993,39(4):1195-1203
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 相似文献
5.
Koksal C.E. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2007,53(8):2892-2897
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. 相似文献
6.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1973,19(5):661-666
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. 相似文献
7.
Combinatorial analysis of the minimum distance of turbo codes 总被引:2,自引:0,他引:2
Breiling M. Huber J.B. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2001,47(7):2737-2750
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 相似文献
8.
Short codes with a given covering radius 总被引:1,自引:0,他引:1
Brualdi R.A. Pless V.S. Wilson R.M. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1989,35(1):99-109
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 相似文献
9.
Ashikhmin A.E. Cohen G.D. Krivelevich M. Litsyn S.N. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2005,51(1):250-258
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. 相似文献
10.
Klapper A. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2004,50(3):532-536
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. 相似文献
11.
Levenshtein V.I. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1995,41(5):1303-1321
Universal bounds for the cardinality of codes in the Hamming space Frn 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 相似文献
12.
Sole P. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1995,41(1):268-272
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 相似文献
13.
Guruswami V. Hastad J. Sudan M. Zuckerman D. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2002,48(5):1021-1034
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 Ω(ε4) 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 τ < δ, c1 > 0, and an infinite family of linear codes {Ci}i such that if ni denotes the block length of Ci, then C i has minimum distance at least δ · ni and contains more than c1 · nic codewords in some Hamming ball of radius τ · ni. 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 相似文献
14.
Linear programming bounds for codes in grassmannian spaces 总被引:2,自引:0,他引:2
Bachoc C. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2006,52(5):2111-2125
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 相似文献
15.
广义Hamming重量上,下界的对偶定理 总被引:3,自引:0,他引:3
本文给出了一种广义Hamming重量上、下界的对偶定理。即若给定一个码的对偶码的广义Hamming重量上界(或者下界),可以给出该码的广义Hamming重量上界(或者下界)。H.Stich-noth(1994)曾给出了迹码(如BCH码和Goppa码的对偶码)的广义Hamming重量一种上、下界,如果采用本文结果就可以给出迹码的对偶码的广义Hamming重量一种上、下界。因此,本文的结果是H.Stichnoth的结果的有益补充 相似文献
16.
Betsumiya K. Harada M. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2004,50(2):356-358
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. 相似文献
17.
Xiaolin Wu 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1997,43(2):638-645
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 相似文献
18.
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. 相似文献
19.
Mehes A. Zeger K. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2000,46(6):2133-2151
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 相似文献
20.
关于Goppa码、BCH码的广义Hamming重量 总被引:1,自引:0,他引:1
本文研究了Goppa码、BCH码的广义Hamming重量,给出了Goppa码的广义Hamming重量的一个下界以及求该下界的一个算法;对于本原、狭义BCH码,给出了后面一些广义Hamming重量的确切值。 相似文献