共查询到20条相似文献,搜索用时 31 毫秒
1.
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) 相似文献
2.
Augot D. Charpin P. Sendrier N. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1992,38(3):960-973
Primitive binary cyclic codes of length n =2m are considered. A BCH code with designed distance δ is denoted B (n ,δ). A BCH code is always a narrow-sense BCH code. A codeword is identified with its locator polynomial, whose coefficients are the symmetric functions of the locators. The definition of the code by its zeros-set involves some properties for the power sums of the locators. Moreover, the symmetric functions and the power sums of the locators are related to Newton's identities. An algebraic point of view is presented in order to prove or disprove the existence of words of a given weight in a code. The principal result is the true minimum distance of some BCH codes of length 255 and 511. which were not known. The minimum weight codewords of the codes B (n 2h -1) are studied. It is proved that the set of the minimum weight codewords of the BCH code B (n ,2m-2-1) equals the set of the minimum weight codewords of the punctured Reed-Muller code of length n and order 2, for any m 相似文献
3.
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 相似文献
4.
The coding scheme uses a set of n convolutional codes multiplexed into an inner code and a (n ,n -1) single-parity-check code serving as the outer code. Each of the inner convolutional codes is decoded independently, with maximum-likelihood decoding being achieved using n parallel implementations of the Viterbi algorithm. The Viterbi decoding is followed by additional outer soft-decision single-parity-check decoding. Considering n =12 and the set of short constraint length K =3, rate 1/2 convolutional codes, it is shown that the performance of the concatenated scheme is comparable to the performance of the constraint length K =7, rate 1/2 convolutional code with standard soft-decision Viterbi decoding. Simulation results are presented for the K =3, rate 1/2 as well as for the punctured K =3, rate 2/3 and rate 3/4 inner convolutional codes. The performance of the proposed concatenated scheme using a set of K =7, rate 1/2 inner convolutional codes is given 相似文献
5.
6.
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 相似文献
7.
Repeated-root cyclic codes 总被引:11,自引:0,他引:11
van Lint J.H. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1991,37(2):343-345
In the theory of cyclic codes, it is common practice to require that (n ,q )=1, where n is the word length and F q is the alphabet. It is shown that the even weight subcodes of the shortened binary Hamming codes form a sequence of repeated-root cyclic codes that are optimal. In nearly all other cases, one does not find good cyclic codes by dropping the usual restriction that n and q must be relatively prime. This statement is based on an analysis for lengths up to 100. A theorem shows why this was to be expected, but it also leads to low-complexity decoding methods. This is an advantage, especially for the codes that are not much worse than corresponding codes of odd length. It is demonstrated that a binary cyclic code of length 2n (n odd) can be obtained from two cyclic codes of length n by the well-known | u |u +v | construction. This leads to an infinite sequence of optimal cyclic codes with distance 4. Furthermore, it is shown that low-complexity decoding methods can be used for these codes. The structure theorem generalizes to other characteristics and to other lengths. Some comparisons of the methods using earlier examples are given 相似文献
8.
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 相似文献
9.
Cheung K.-M. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1990,36(5):1149-1153
An explicit formula is derived that enumerates the complete weight distribution of an (n , k , d ) linear code using a partially known weight distribution. An approximation formula for the weight distribution of q -ary linear (n , k , d ) codes is also derived. It is shown that, for a given q -ary linear (n , k , d ) code, the ratio of the number of codewords of weight u to the number of words of weight u approaches the constant Q =q -(n-k) as u becomes large. The error term is a decreasing function of the minimum weight of the dual. The results are also valid for nonlinear (n , M , d ) codes with the minimum weight of the dual replaced by the dual distance 相似文献
10.
Pseudocyclic maximum-distance-separable codes 总被引:1,自引:0,他引:1
Krishna A. Sarwate D.V. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1990,36(4):880-884
The (n , k ) pseudocyclic maximum-distance-separable (MDS) codes modulo (x n- a ) over GF(q ) are considered. Suppose that n is a divisor of q +1. If n is odd, pseudocyclic MDS codes exist for all k . However, if n is even, nontrivial pseudocyclic MDS codes exist for odd k (but not for even k ) if a is a quadratic residue in GF(q ), and they exist for even k (but not for odd k ) if a is not a quadratic residue in GF(q ). Also considered is the case when n is a divisor of q -1, and it is shown that pseudocyclic MDS codes exist if and only if the multiplicative order of a divides (q -1)/n , and that when this condition is satisfied, such codes exist for all k . If the condition is not satisfied, every pseudocyclic code of length n is the result of interleaving a shorter pseudocyclic code 相似文献
11.
The authors present a general technique for computing P e for all possible shortened versions of cyclic codes generated by any given polynomial. The technique is recursive, i.e. computes P e for a given code block length n from that of the code block length n -1. The proposed computation technique for determining P e does not require knowledge of the code weight distributions. For a generator polynomial of degree r , and |g | nonzero coefficients, the technique yields P e for all code block lengths up to length n in time complexity O (n |g |2r+|g|). Channels with variable bit error probabilities can be analyzed with the same complexity. This enables the performance of the code generator polynomials to be analyzed for burst errors 相似文献
12.
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 相似文献
13.
van Zanten A.J. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1991,37(4):1229-1233
A number system is developed for the conversion of natural numbers to the codewords of the Gray code G (n ,k ) of length n and weight k , and vice versa. The focus is on the subcode G (n ,k ) of G (n ) consisting of those words of G (n ) with precisely k 1-bits, 0<k <n . This code is called the constant weight Gray code of length n and weight k . As an application sharp lower and upper bounds are derived for the value of |i -j |, where i and j are indices of codewords g i and g j of G (n ,k ) such that they differ in precisely 2 m bits 相似文献
14.
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 相似文献
15.
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 相似文献
16.
Hou X.-D. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1991,37(2):378-379
Whether quasi-perfect codes are normal is addressed. Let C be a code of length n , dimension k , covering radius R , and minimal distance d . It is proved that C is normal if d ⩾2R -1. Hence all quasi-perfect codes are normal. Consequently, any [n ,k ]R binary linear code with minimal distance d ⩾2R -1 is normal 相似文献
17.
18.
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 相似文献
19.
Roth R.M. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1991,37(2):328-336
A μ-[n ×n ,k ] array code C over a field F is a k -dimensional linear space of n ×n matrices over F such that every nonzero matrix in C has rank ⩾μ. It is first shown that the dimension of such array codes must satisfy the Singleton-like bound k ⩽n (n -μ+1). A family of so-called maximum-rank μ-[n ×n ,k =n ( n -μ+1)] array codes is then constructed over every finite field F and for every n and μ, 1⩽μ⩽n . A decoding algorithm is presented for retrieving every Γ∈C , given a received array Γ+E , where rank (E )+1⩽(μ-1)/2. Maximum-rank array codes can be used for decoding crisscross errors in n ×n bit arrays, where the erroneous bits are confined to a number t of rows or columns (or both). This construction proves to be optimal also for this model of errors. It is shown that the behavior of linear spaces of matrices is quite unique compared with the more general case of linear spaces of n ×n . . .×n hyper-arrays 相似文献
20.
A t -EC/AUED code is constructed by appending a single check symbol from an alphabet S to each word of an n -bit binary t -EC code of even weight. Conditions are derived for the construction of S and a procedure is given which, for some values of t , n , leads to codes with fewer check bits than known codes with equivalent properties 相似文献