共查询到20条相似文献,搜索用时 328 毫秒
1.
On the covering radius of codes 总被引:1,自引:0,他引:1
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1985,31(3):385-401
The covering radiusR of a code is the maximal distance of any vector from the code. This work gives a number of new results concerningt[n, k] , the minimal covering radius of any binary code of lengthn and dimensionk . For examplet[n, 4] andt[n, 5] are determined exactly, and reasonably tight bounds ont[n, k] are obtained for anyk whenn is large. These results are found by using several new constructions for codes with small covering radius. One construction, the amalgamated direct sum, involves a quantity called the norm of a code. Codes with normleq 2 R + 1 are called normal, and may be combined efficiently. The paper concludes with a table giving bounds ont[n, k] forn leq 64 . 相似文献
2.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1973,19(3):344-356
This paper presents a table of upper and lower bounds ond_{max} (n,k) , the maximum minimum distance over all binary, linear(n,k) error-correcting codes. The table is obtained by combining the best of the existing bounds ond_{max} (n,k) with the minimum distances of known codes and a variety of code-construction techniques. 相似文献
3.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1985,31(6):826-830
It is shown that the family ofq -ary generalized Reed-Solomon codes is identical to the family ofq -ary linear codes generated by matrices of the form[I|A] , whereI is the identity matrix, andA is a generalized Cauchy matrix. Using Cauchy matrices, a construction is shown of maximal triangular arrays over GF(q) , which are constant along diagonals in a Hankel matrix fashion, and with the property that every square subarray is a nonsingular matrix. By taking rectangular subarrays of the described triangles, it is possible to construct generator matrices[I|A] of maximum distance separable codes, whereA is a Hankel matrix. The parameters of the codes are(n,k,d) , for1 leq n leq q+ 1, 1 leq k leq n , andd=n-k+1 . 相似文献
4.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1986,32(3):349-354
An(n, k, d) linear code overF= GF(q) is said to be {em maximum distance separable} (MDS) ifd = n - k + 1 . It is shown that an(n, k, n - k + 1) generalized Reed-Solomon code such that2leq k leq n - lfloor (q - 1)/2 rfloor (k neq 3 {rm if} q is even) can be extended by one digit while preserving the MDS property if and only if the resulting extended code is also a generalized Reed-Solomon code. It follows that a generalized Reed-Solomon code withk in the above range can be {em uniquely} extended to a maximal MDS code of lengthq + 1 , and that generalized Reed-Solomon codes of lengthq + 1 and dimension2leq k leq lfloor q/2 rfloor + 2 (k neq 3 {rm if} q is even) do not have MDS extensions. Hence, in cases where the(q + 1, k) MDS code is essentially unique,(n, k) MDS codes withn > q + 1 do not exist. 相似文献
5.
Further results on the covering radius of codes 总被引:1,自引:0,他引:1
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1986,32(5):680-694
A number of upper and lower bounds are obtained forK(n, R) , the minimal number of codewords in any binary code of lengthn and 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 . 相似文献
6.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1984,30(2):395-403
For any(n, k, d) binary linear code, the Griesmer bound says thatn geq sum_{i=0}^{k-1} lceil d/2^{i} rceil , wherelceil x rceil denotes the smallest integergeq x . We consider codes meeting the Griesmer bound with equality. These codes have parametersleft( s(2^{k} - 1) - sum_{i=1}^{p} (2^{u_{i}} - 1), k, s2^{k-1} - sum_{i=1}^{p} 2^{u_{i} -1} right) , wherek > u_{1} > cdots > u_{p} geq 1 . We characterize all such codes whenp = 2 oru_{i-1}-u_{i} geq 2 for2 leq i leq p . 相似文献
7.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1981,27(5):548-555
An infinite sequence ofk -dimensional binary linear block codes is constructed with parametersn=2^{k}+2^{k-2}-15,d=2^{k-1}+2^{k-3}-8,k geq 7 . Fork geq 8 these codes are unique, while there are five nonisomorphic codes fork=7 . By shortening these codes in an appropriate way, one finds codes meeting the Griesmer bound for2^{k-1}+2^{k-3}-15 leq d leq 2^{k-1}+2^{k-3}-8; k geq 7 . 相似文献
8.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1986,32(6):854-857
New upper bounds on the redundancy of Huffman codes are provided. A bound that for2/9 leq P_{1} leq 0.4 is sharper than the bound of Gallager, when the probability of the most likely source letterP_{1} is the only known probability is presented. The improved bound is the tightest possible for1/3 leq P_{1} leq 0.4 . Upper bounds are presented on the redundancy of Huffman codes when the extreme probabilitiesP_{1} andP_{N} are known. 相似文献
9.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1987,33(4):601-605
It is proven that 100-percent efficient fixed-rate codes for run-length-limited (RLL)(d,k) and RLL charge-constrained(d, k; c) channels are possible in only two eases, namely(d,k; c)=(0,1;1) and(1,3;3) . Specifically, the binary Shannon capacity of RLL(d, k) constrained systems is shown to be irrational for all values of(d, k),0 leq d < k . For RLL charge-constrained systems with parameters(d, k;c) , the binary capacity is irrational for all values of(d, k; c),0 leq d < k,2c geq k + 1 , except(0,1; 1) and(1,3;3) , which both have binary capacity1/2 . 相似文献
10.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1986,32(5):706-709
Recently Kasami {em et al.} presented a linear programming approach to the weight distribution of binary linear codes [2]. Their approach to compute upper and lower bounds on the weight distribution of binary primitive BCH codes of length2^{m} - 1 withm geq 8 and designed distance2t + 1 with4 leq t leq 5 is improved. From these results, the relative deviation of the number of codewords of weightjleq 2^{m-1} from the binomial distribution2^{-mt} left( stackrel{2^{m}-1}{j} right) is shown to be less than 1 percent for the following cases: (1)t = 4, j geq 2t + 1 andm geq 16 ; (2)t = 4, j geq 2t + 3 and10 leq m leq 15 ; (3)t=4, j geq 2t+5 and8 leq m leq 9 ; (4)t=5,j geq 2t+ 1 andm geq 20 ; (5)t=5, j geq 2t+ 3 and12 leq m leq 19 ; (6)t=5, j geq 2t+ 5 and10 leq m leq 11 ; (7)t=5, j geq 2t + 7 andm=9 ; (8)t= 5, j geq 2t+ 9 andm = 8 . 相似文献
11.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1978,24(1):81-93
Improved bounds forA(n,d) , the maximum number of codewords in a (linear or nonlinear) binary code of word lengthn and minimum distanced , and forA(n,d,w) , the maximum number of binary vectors of lengthn , distanced , and constant weightw in the rangen leq 24 andd leq 10 are presented. Some of the new values areA 相似文献
12.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1984,30(3):480-484
Two algorithms are presented for the generation of full-length shift-register cycles, also referred to as de Bruijn sequences. The first algorithm generates2^{k cdot g(n,k) full cycles of length2^{n} , using3n + k cdot g(n, k) bits of storage, wherek is a free parameter in the range1 leq k leq 2^{((n-4)/2)} , andg(n, k) is of the order ofn - 2 log k . The second algorithm generates about2^{n^{2}/4} full cycles of length2^{n} , using aboutn^{2}/2 bits of storage. In both algorithms, the time required to produce the next bit from the lastn bits is close ton . A possible application to the construction of stream ciphers is indicated. 相似文献
13.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1977,23(5):618-620
A generalization of the standard burst error trapping decoder for(n,k) cyclic block codes is presented that will correct both ad -bit deletion(d leq D) and up to a(B - d) -bit additive noise error imbedded within a single error burst of lengthB -bits or less.B andD are design parameters of the decoder and are subject to the constraintD leq B < n - k . An efficient implementation of this decoder which contains(D + 1) detectors, each set to a specified deletion count is given. 相似文献
14.
Lower bounds for constant weight codes 总被引:1,自引:0,他引:1
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1980,26(1):37-43
LetA(n,2delta,w) denote the maximum number of codewords in any binary code of lengthn , constant weightw , and Hamming distance2delta Several lower bounds forA(n,2delta,w) are given. Forw anddelta fixed,A(n,2delta,w) geq n^{W-delta+l}/w! andA(n,4,w)sim n^{w-l}/w! asn rightarrow infty . In most cases these are better than the "Gilbert bound." Revised tables ofA(n,2 delta,w) are given in the rangen leq 24 anddelta leq 5 . 相似文献
15.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1984,30(6):872-877
Winograd's result concerning Elias' model of computation in the presence of noise can be stated without reference to computation. If a codevarphi: {0,1}^{k} rightarrow {0,1}^{n} is min-preserving(varphi (a wedge b) = varphi (a) wedge varphi (b) fora,b in {0,1}^{k}) andepsilon n -error correcting, then the ratek/n rightarrow 0 ask rightarrow infty . This result is improved and extended in two directions. begin{enumerate} item For min-preserving codes with {em fixed} maximal (and also average) error probability on a binary symmetric channel againk/n rightarrow 0 ask rightarrow infty (strong converses). item Second, codes with lattice properties without reference to computing are studied for their own sake. Already for monotone codes( varphi (a) leq varphi (b) fora leq b) the results in direction 1) hold for maximal errors. end{enumerate} These results provide examples of coding theorems in which entropy plays no role, and they can be reconsidered from the viewpoint of multiuser information theory. 相似文献
16.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1968,14(3):487-490
A linear code of block length n possessing minimum weight d has one code word of weight zero, and no other code words of weight less thand . The weight distribution of the code is given by the set of allW(j), d leq j leq n , describing the number of code words having a weight of exactlyj . Exact weight distributions are known for only a handful of linear codes. This paper presents an explicit upper bound uponW(j) as a function ofn, d , andj . The bound has general applicability to all linear codes. 相似文献
17.
Pil Lee 《Communications, IEEE Transactions on》1985,33(2):171-177
New, good (K, 1/N ) convolutional codes are tabulated for3 leq K leq 7 and2 leq N leq 8 , which were selected based on the criterion of minimizing the required signal-to-noise ratio (SNR) for given desired bit error rates (BER). A transfer function upper bound was used to find the BER performance. Partial searches were performed using the idea that "good codes generate good lower rate codes." The new codes save signal energy up to 0.4 dB compared to previously reported codes of the same parameters. 相似文献
18.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1979,25(1):118-121
A table of primitive binary idempotents of odd block lengthn, 7 leq n leq 511 , is presented. 相似文献
19.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1984,30(2):385-388
LetV be an(n, k, d) binary projective geometry code withn = (q^{m}-1)/(q - 1), q = 2^{s} , andd geq [(q^{m-r}-1)/(q - 1)] + 1 . This code isr -step majority-logic decodable. With reference to the GF(q^{m}) = {0, 1, alpha , alpha^{2} , cdots , alpha^{n(q-1)-1} } , the generator polynomialg(X) , ofV , hasalpha^{nu} as a root if and only ifnu has the formnu = i(q - 1) andmax_{0 leq l < s} W_{q}(2^{l} nu) leq (m - r - 1)(q - 1) , whereW_{q}(x) indicates the weight of the radix-q representation of the numberx . LetS be the set of nonzero numbersnu , such thatalpha^{nu} is a root ofg(X) . LetC_{1}, C_{2}, cdots, C_{nu} be the cyclotomic cosets such thatS is the union of these cosets. It is clear that the process of findingg(X) becomes simpler if we can find a representative from eachC_{i} , since we can then refer to a table, of irreducible factors, as given by, say, Peterson and Weldon. In this correspondence it was determined that the coset representatives for the cases ofm-r = 2 , withs = 2, 3 , andm-r=3 , withs=2 . 相似文献
20.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1978,24(5):627-628
Upper bounds on the covering radius of binary codes are studied. In particular it is shown that the covering radiusr_{m} of the first-order Reed-Muller code of lenglh2^{m} satisfies2^{m-l}-2^{lceil m/2 rceil -1} r_{m} leq 2^{m-1}-2^{m/2-1} . 相似文献