共查询到20条相似文献,搜索用时 15 毫秒
1.
Etzion T. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1990,36(4):899-905
Two DC-free codes are presented with distance 2d , b ⩾1 length 2n +2r (d -1) for d ⩽3 and length 2n +2r (d -1)(2d -1) for d >3, where r is the least integer ⩾log2 (2n +1). For the first code l =4, c =2, and the asymptotic rate of this code is 0.7925. For the second code l =6, c =3, and the asymptotic rate of this code is 0.8858. Asymptotically, these rates achieve the channel capacity. For small values of n these codes do not achieve the best rate. As an example of codes of short length with good rate, the author presents a (30, 10, 6, 4) DC-free block code with 221 codewords. A construction is presented for which from a given code C 1 of length n , even weight, and distance 4, the author obtains a (4n , l , c , 4) DC-free block code C 2, where l is 4, 5 or 6, and c is not greater than n +1 (but usually significantly smaller). The codes obtained by this method have good rates for small lengths. The encoding and decoding procedures for all the codes are discussed 相似文献
2.
A new upper bound on the minimal distance of self-dual codes 总被引:9,自引:0,他引:9
Conway J.H. Sloane N.J.A. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1990,36(6):1319-1333
It is shown that the minimal distance d of a binary self-dual code of length n ⩾74 is at most 2[(n +6)/10]. This bound is a consequence of some new conditions on the weight enumerator of a self-dual code obtained by considering a particular translate of the code, called its shadow. These conditions also enable one to find the highest possible minimal distance of a self-dual code for all n ⩾60; to show that self-dual codes with d ⩽6 exist precisely for n ⩾22, with d ⩾8 exist precisely for n =24, 32 and n ⩾26, and with d ⩾10 exist precisely for n ⩾46; and to show that there are exactly eight self-dual codes of length 32 with d =8. Several of the self-dual codes of length 34 have trivial group (this appears to be the smallest length where this can happen) 相似文献
3.
Honkala H.S. Hamalainen H.O. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1991,37(2):372-375
The normality of binary codes is studied. The minimum cardinality of a binary code of length n with covering radius R is denoted by K (n ,R ). It is assumed that C is an (n ,M )R code, that is, a binary code of length n with M codewords and covering radius R . It is shown that if C is an (n ,M )1 code, then it is easy to find a normal (n ,M )1 code by changing C in a suitable way, and that all the optimal (n ,M )1 codes (i.e. those for which M =K (n ,1)) are normal and their every coordinate is acceptable. It is shown that if C is an abnormal (n ,M ) code, then n ⩾9, and an abnormal (9118)1 code which is the smallest abnormal code known at present, is constructed. Lower bounds on the minimum cardinality of a binary abnormal code of length n with covering radius 1 are derived, and it is shown that if an (n ,M )1 code is abnormal, then M ⩾96 相似文献
4.
On repeated-root cyclic codes 总被引:12,自引:0,他引:12
Castagnoli G. Massey J.L. Schoeller P.A. von Seemann N. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1991,37(2):337-342
A parity-check matrix for a q -ary repeated-root cyclic code is derived using the Hasse derivative. Then the minimum distance of a q -ary repeated-root cyclic code is expressed in terms of the minimum distance of a certain simple-root cyclic code. With the help of this result, several binary repeated-root cyclic codes of lengths up to n =62 are shown to contain the largest known number of codewords for their given length and minimum distance. The relative minimum distance d min/n of q -ary repeated-root cyclic codes of rate r ⩾R is proven to tend to zero as the largest multiplicity of a root of the generator g (x ) increases to infinity. It is further shown that repeated-root cycle codes cannot be asymptotically better than simple-root cyclic codes 相似文献
5.
Hou X.-D. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1990,36(3):683-685
Two upper bounds for the norm N (C ) of a binary linear code C with minimal weight d and covering radius R are given. The second of these bounds implies that C is normal if R =3 相似文献
6.
Alon N. Bergmann E.E. Coppersmith D. Odlyzko A.M. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1988,34(1):128-130
For n >0, d ⩾0, n ≡d (mod 2), let K (n , d ) denote the minimal cardinality of a family V of ±1 vectors of dimension n , such that for any ±1 vector w of dimension n there is a v ∈V such that |v - w |⩽d , where v -w is the usual scalar product of v and w . A generalization of a simple construction due to D.E. Knuth (1986) shows that K (n , d )⩽[n /(d +1)]. A linear algebra proof is given here that this construction is optimal, so that K (n , d )-[n /(d +1)] for all n ≡d (mod 2). This construction and its extensions have applications to communication theory, especially to the construction of signal sets for optical data links 相似文献
7.
Patapoutian A. Kumar P.V. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1992,38(4):1375-1382
A simple technique employing linear block codes to construct (d ,k ) error-correcting block codes is considered. This scheme allows asymptotically reliable transmission at rate R over a BSC channel with capacity C BSC provided R ⩽C d,k-(1+C BSC), where C d,k is the maximum entropy of a (d ,k ) source. For the same error-correcting capability, the loss in code rate incurred by a multiple-error correcting (d ,k ) code resulting from this scheme is no greater than that incurred by the parent linear block code. The single-error correcting code is asymptotically optimal. A modification allows the correction of single bit-shaft errors as well. Decoding can be accomplished using off-the-shelf decoders. A systematic (but suboptimal) encoding scheme and detailed case studies are provided 相似文献
8.
Ytrehus O. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1991,37(2):349-351
A binary, linear block code C with block length n and dimension n is commonly denoted by [n , k ] or, if its minimum distance is d , by [n , k ,d ]. The code's covering radius r (C ) can be defined as the smallest number r such that any binary column vector of length (n -k ) can be written as a sum of r or fewer columns of a parity-check matrix of C . An [n ,k ] code with covering radius r is denoted by [n ,k ]r . R.A. Brualdi et al., (1989) showed that l (m ,r ) is defined to be the smallest n such that an [n ,n -m ]r code exists. l (m ,2) is known for m ⩽6, while it is shown by Brualdi et al. that 17⩽l (7,2)⩽19. This lower bound is improved by A.R. Calderbank et al. (1988), where it is shown that [17,10]2 codes do not exist. The nonexistence of [18,11]2 codes is proved, so that l (7,2)=19. l [7.2)=19 is established by showing that [18,11]2 codes do not exist. It is also shown that [64,53]2 codes do not exist, implying that l (11,2)⩾65 相似文献
9.
Skorobogatov A.N. Vladut S.G. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1990,36(5):1051-1060
A decoding algorithm for algebraic-geometric codes arising from arbitrary algebraic curves is presented. This algorithm corrects any number of errors up to [(d -g-1)/2], where d is the designed distance of the code and g is the genus of the curve. The complexity of decoding equals σ(n 3) where n is the length of the code. Also presented is a modification of this algorithm, which in the case of elliptic and hyperelliptic curves is able to correct [(d -1)/2] errors. It is shown that for some codes based on plane curves the modified decoding algorithm corrects approximately d /2-g /4 errors. Asymptotically good q -ary codes with a polynomial construction and a polynomial decoding algorithm (for q⩾361 on some segment their parameters are better than the Gilbert-Varshamov bound) are obtained. A family of asymptotically good binary codes with polynomial construction and polynomial decoding is also obtained, whose parameters are better than the Blokh-Zyablov bound on the whole interval 0<σ<1/2 相似文献
10.
Metzner J.J. Kapturowski E.J. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1990,36(4):911-917
Code symbols are treated as vectors in an r -dimensional vector space F r over a field F . Given any ( n , k ) linear block code over F with minimum distance d , it is possible to derive an (n , k ) code with symbols over F r, also with minimum distance d , which can correct any pattern of d -2 or fewer symbol errors for which the symbol errors as vectors are linearly independent. This is about twice the bound on the number of errors guaranteed to be correctable. Furthermore, if the error vectors are linearly dependent and d -2 or fewer in number, the existence of dependence can always be detected. A decoding techinque is described for which complexity increases no greater than as n 3, for any choice of code. For the two applications considered, situations are described where the probability of the error patterns being linearly dependent decreases exponentially with r 相似文献
11.
Mao-Chao Lin 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1990,36(5):1139-1141
The author investigates the (n , k , d ⩾2t +1) binary linear codes, which are used for correcting error patterns of weight at most t and detecting other error patterns over a binary symmetric channel. In particular, for t =1, it is shown that there exists one code whose probability of undetected errors is upper-bounded by (n +1) [2n-k-n ]-1 when used on a binary symmetric channel with transition probability less than 2/n 相似文献
12.
Hou X.-D. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1990,36(4):895-899
Some new lower bounds on |C| for a binary linear [n , k ]R code C with n +1=t (R +1)-r (0⩽r <R +1, t >2 odd) or with n +1=t (R +1)-1(t >2 even) are obtained. These bounds improve the sphere covering bound considerably and give several new values and lower bounds for the function t [n , k ], the smallest covering radius of any [n , k ] code 相似文献
13.
Ehrhard D. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1993,39(3):743-751
A decoding algorithm for codes arising from algebraic curves explicitly constructable by Goppa's construction is presented. Any configuration up to the greatest integer less than or equal to (d *-1)/2 errors is corrected by the algorithm whenever d *⩾6g , where d * is the designed minimum distance of the code and g is the genus of the curve. The algorithm's complexity is at most O ((d *)2 n ), where n denotes the length of the code. Application to Hermitian codes and connections with well-known algorithms are explained 相似文献
14.
The trellis coding technique is applied to line-coded baseband digital transmission systems. For R =n /n +1(n =1,2,3) coding rates, a new codeword assignment model is proposed to accomplish basic requirements for line coding in which each length n binary data sequence is encoded into a length n +1 ternary (+,0,-) line codeword chosen among the code alphabet with 2n+2 elements. Assuming Viterbi decoding, the system error performance is improved by increasing the free Euclidean distance between coded sequences. A new algorithm is given for the calculation of the free distance between line-coded sequences so obtained. For R =1/2 and R =3/4 rates, the analytical error performance upper bounds are derived. The power spectral densities of the new line codes are also calculated and compared with those of known line codes 相似文献
15.
16.
Decoding geometric Goppa codes using an extra place 总被引:1,自引:0,他引:1
Porter S.C. Shen B.-Z. Pellikaan R. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1992,38(6):1663-1676
Decoding geometric Goppa codes can be reduced to solving the key congruence of a received word in an affine ring. If the codelength is smaller than the number of rational points on the curve, then this method can correct up to 1.2 (d *-L)/2-s errors, where d * is the designed minimum distance of the code and s is the Clifford defect. The affine ring with respect to a place P is the set of all rational functions which have no poles except at P , and it is somehow similar to a polynomial ring. For a special kind of geometric Goppa code, namely C Ω(D ,mP ), the decoding algorithm is reduced to solving the key equation in the affine ring, which can be carried out by the subresultant sequence in the affine ring with complexity O (n 3), where n is the length of codewords 相似文献
17.
Fast decoding of codes from algebraic plane curves 总被引:2,自引:0,他引:2
Justesen J. Larsen K.J. Jensen H.E. Hoholdt T. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1992,38(1):111-119
Improvement to an earlier decoding algorithm for codes from algebraic geometry is presented. For codes from an arbitrary regular plane curve the authors correct up to d */2-m 2 /8+m /4-9/8 errors, where d * is the designed distance of the code and m is the degree of the curve. The complexity of finding the error locator is O (n 7/3 ), where n is the length of the code. For codes from Hermitian curves the complexity of finding the error values, given the error locator, is O (n 2), and the same complexity can be obtained in the general case if only d */2-m 2/2 errors are corrected 相似文献
18.
Daskalov R.N. Kapralov S.N. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1992,38(6):1795-1796
Let an [n , k , d ]-code denote a binary linear code of length n , dimension k , and minimum distance at least d . Define d (n , k ) as the maximum value of d for which there exists a binary linear [n , k , d ]-code. T. Verhoeff (1989) has provided an updated table of bounds on d (n , k ) for 1⩽k ⩽n ⩽127. The authors improve on some of the upper bounds given in that table by proving the nonexistence of codes with certain parameters 相似文献
19.
Weight enumerators of self-dual codes 总被引:4,自引:0,他引:4
Brualdi R.A. Pless V.S. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1991,37(4):1222-1225
Some construction techniques for self-dual codes are investigated, and the authors construct a singly-even self-dual [48,24,10]-code with a weight enumerator that was not known to be attainable. It is shown that there exists a singly-even self-dual code C ' of length n =48 and minimum weight d =10 whose weight enumerator is prescribed in the work of J.H. Conway et al. (see ibid., vol.36, no.5, p.1319-33, 1990). Two self-dual codes of length n are called neighbors, provided their intersection is a code of dimension (n /2)-1. The code C' is a neighbor of the extended quadratic residue code of length 48 相似文献
20.
Janwa H. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1989,35(1):110-122
A Griesmer-like upper bound on the covering radius, R , is given. To the author's knowledge this is the only upper bound which explicitly depends on all three parameters n , k , and d . An upper bound on R for cyclic codes is then given which depends on the generator polynomial of the cyclic code and which, in many cases, leads to an improvement of the previous bound. An upper bound on the irreducible generator polynomial cyclic codes is also given. New interpretations and applications of the so-called Norse bounds and necessary and sufficient conditions to attain one of these bounds are provided. Generalizations of most of the results for codes over GF(q ) are outlined 相似文献