Optimal quaternary linear codes of dimension five

Let d_q(n,k) be the maximum possible minimum Hamming distance of a q-ary [n,k,d]-code for given values of n and k. It is proved that d₄ (33,5)=22, d₄(49,5)=34, d₄ (131,5)=96, d₄(142,5)=104, d₄(147,5)=108, d ₄(152,5)=112, d₄(158,5)=116, d₄(176,5)⩾129, d₄(180,5)⩾132, d₄(190,5)⩾140, d₄(195,5)=144, d₄(200,5)=148, d₄(205,5)=152, d₄(216,5)=160, d₄(227,5)=168, d₄(232,5)=172, d₄(237,5)=176, d₄(240,5)=178, d₄(242,5)=180, and d₄(247,5)=184. A survey of the results of recent work on bounds for quaternary linear codes in dimensions four and five is made and a table with lower and upper bounds for d₄(n,5) is presented     

On the structure of linear codes with covering radius two and three

We obtain new bounds on l(m,r), the minimum length of a linear code with codimension m and covering radius r. All bounds are derived in a uniform way. We employ results from coding theory, some earlier results on covering codes, and combinatorial arguments. We prove the following bounds: l(6, 2)=13, l(7,2)=19, l(8,2)⩾25, l(9,2)⩾34, l(2m-l,2)⩾2^m+1 for m⩾3, l(14,2)⩾182, l(16,2)⩾363, l(18,2)⩾725, l(20,2)⩾1449, l(22,2)⩾2897, l(24,2)⩾5794, l(9,3)⩾17, l(10,3)⩾21, l(12,3)⩾31, l(13,3)⩾38     

The nonexistence of some five-dimensional quaternary linear codes

Let n₄(k, d) be the smallest integer n, such that a quaternary linear [n, k, d; 4]-code exists. It is proved that n₄ (5, 20)=30, n₄(5, 42)⩾59, n₄(5, 45)⩾63, n₄(5, 64)⩾88, n₄(5, 80)=109, n₄(5, 140)⩾189, n₄(5, 143)⩾193, n₄ (5, 168)⩾226, n₄(5, 180)⩾242, n₄(5, 183)⩾246, n₄(5, 187)=251     

Some results on the covering radii of Reed-Muller codes

Let R(r,m) be the rth-order Reed-Muller code of length 2^m and let ρ(r,m ) be its covering radius. R(2,7), R(2,8), R (3,7), and R(4,8) are among those smallest Reed-Muller codes whose covering radii are not known. New bounds for the covering radii of these four codes are obtained. The results are ρ(2,7)⩾40, ρ(2,8)⩾84, 20⩽ρ(3,7)⩽23, and ρ(4,8)⩾22. Noncomputer proofs for the known results that ρ(2,6)=18 and that R(1,5) is normal are given     

Disproof of a conjecture on the existence of balanced optimal covering codes

The minimum number of codewords in a binary code with length n and covering radius R is denoted by K(n,R), and corresponding codes are called optimal. A code with M words is said to be balanced in a given coordinate if the number of 0's and 1's in this coordinate are at least /spl lfloor/M/2/spl rfloor/. A code is balanced if it is balanced in all coordinates. It has been conjectured that among optimal covering codes with given parameters there is at least one balanced code. By using a computational method for classifying covering codes, it is shown that there is no balanced code attaining K(9,1)=62.     

New single asymmetric error-correcting codes

New single asymmetric error-correcting codes are proposed. These codes are better than existing codes when the code length n is greater than 10, except for n=12 and n=15. In many cases one can construct a code C containing at least [2ⁿ/n] codewords. It is known that a code with |C|⩾[2ⁿ/(n+1)] can be easily obtained. It should be noted that the proposed codes for n=12 and n=15 are also the best known codes that can be explicitly constructed, since the best of the existing codes for these values of n are based on combinatorial arguments. Useful partitions of binary vectors are also presented     

Some bounds for the minimum length of binary linear codes ofdimension nine

We prove the nonexistence of binary [69,9,32] codes and construct codes with parameters [76,9,34],[297,9,146], and [300,9,148]. These results show that n(9,32)=70, n(9,34)⩽76,n(9,146)=297, and n(9,148)=300, where n(k,d) denotes the smallest value of n for which there exists an [n,k,d] binary code. We also present some codes of minimum distance 32 and some related codes     

On the undetected error probability of nonlinear binary constantweight codes

The undetected error probability (UEP) of binary (n, 2δ, m) nonlinear constant weight codes over the binary symmetric channel (BSC) is investigated, where n is the blocklength, m is the weight of codeword and 2δ is the minimum distance of the codes. The distance distribution of the (n, 2, m) nonlinear constant weight codes is evaluated. It is proven in this paper that the (5, 2, 2) code, (5, 2, 3) code, (6, 2, 3) code, (7, 2, 4) code, (7, 2, 3) code and (8, 2, 4) code are the only proper error-detecting codes in the (n, 2, m) nonlinear constant weight codes for n⩾5, in the sense that their UEP is increased monotonically with the channel error rate p, of course all these proper codes are m-out-of-n codes. Furthermore, it is conjectured that except for the cases of n⩽4δ, there are no proper error-detecting binary (n, 2δ, m) nonlinear constant weight codes, for n>8 and δ⩾1     

Certain group codes

Codes are presented for certain combinations of word length n and minimum distance d. Specifically, the codes are for n = 34, d = 13; n = 38, d = 13; n = 28, d = 11; n = 30, d = 11; n = 24, d = 9; n = 26, d = 9. These codes compare favorably with Bose-Chaudhuri codes as regards the number of words.     

No binary quadratic residue code of length 8m-1 is quasi-perfect

The class of binary quadratic residue (QR) codes of length n=8m-1 contains two perfect codes. These are the (7,4,3) Hamming code and the (23,12,7) Golay code. However, it is proved in the present paper that there are no quasi-perfect QR codes of length 8m-1. Finally, this result is generalized to all binary self-dual codes of length N>72     

Binary [18,11]2 codes do not exist-Nor do [64,53]2 codes

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     

A note on the method of poles for code construction

The method of poles is a method for constructing a rate 1:1 finite state code from K-ary data into a constrained channel S, where S is recognized by a given local automaton and S has capacity at least log(k). We characterize those automata to which the method of poles applies in the case where h(S)=log(k). The code produced by the method of poles has a sliding-block decoder. We also give an upper bound on the window length of the decoder that applies when h(S)⩾log(k)     

Upper bounds for constant-weight codes

Let A(n,d,w) denote the maximum possible number of codewords in an (n,d,w) constant-weight binary code. We improve upon the best known upper bounds on A(n,d,w) in numerous instances for n⩽24 and d⩽12, which is the parameter range of existing tables. Most improvements occur for d=8, 10, where we reduce the upper bounds in more than half of the unresolved cases. We also extend the existing tables up to n⩽28 and d⩽14. To obtain these results, we develop new techniques and introduce new classes of codes. We derive a number of general bounds on A(n,d,w) by means of mapping constant-weight codes into Euclidean space. This approach produces, among other results, a bound on A(n,d,w) that is tighter than the Johnson bound. A similar improvement over the best known bounds for doubly-constant-weight codes, studied by Johnson and Levenshtein, is obtained in the same way. Furthermore, we introduce the concept of doubly-bounded-weight codes, which may be thought of as a generalization of the doubly-constant-weight codes. Subsequently, a class of Euclidean-space codes, called zonal codes, is introduced, and a bound on the size of such codes is established. This is used to derive bounds for doubly-bounded-weight codes, which are in turn used to derive bounds on A(n,d,w). We also develop a universal method to establish constraints that augment the Delsarte inequalities for constant-weight codes, used in the linear programming bound. In addition, we present a detailed survey of known upper bounds for constant-weight codes, and sharpen these bounds in several cases. All these bounds, along with all known dependencies among them, are then combined in a coherent framework that is amenable to analysis by computer. This improves the bounds on A(n,d,w) even further for a large number of instances of n, d, and w     

Constructions of error-correcting DC-free block codes

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 ⩾log₂ (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 2²¹ codewords. A construction is presented for which from a given code C ₁ of length n, even weight, and distance 4, the author obtains a (4n, l, c, 4) DC-free block code C₂, 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     

The extended Nadler code is unique (Corresp.)

Constructions for a 32-word binary code of length 12 and minimum distance 5 were given by Nadler in 1962 and van Lint in 1972. These codes are not equivalent as their distance distributions are not the same. That their extended codes of length 13 are equivalent is proved. It is shown that up to a permutation of the coordinates, there is an essentially unique way to construct the extended code. This unique extended code contains only two inequivalent punctured codes of length 12.     

Heterostructure devices using self-aligned p-type diffused ohmiccontacts

Describes the use of a p-type refractory ohmic contact in ohmic self-aligned devices. The contacts are based on self-aligned diffusion of zinc-doped tungsten film. The diffusion is nearly isotropic in the vicinity of silicon nitride sidewalls, allowing self-alignment of ohmic contacts with emitters and gates. Low-resistance contacts (<10^-6 Ω·cm²) are formed both to GaAs and GaAlAs, and the lifetime of the diffused region is superior to that obtained from implantation. Heterostructure bipolar transistors (HBTs) showing high current gains (⩾50 at 2×10³ A·cm^-2 and ⩾200 at 1×10⁵ A·cm^-2 with micrometer-sized emitter widths) and p-channel GaAs gate heterostructure field-effect transistors (HFETs) showing high transconductances (78 mS/mm at 2.2-μm gate length) have been fabricated using this contact     

On extremal self-dual ternary codes of lengths 28 to 40

The extremal self-dual ternary codes of lengths 28, 32, and 36 with monomial automorphisms of prime order r⩾5 and of length 40 with monomial automorphisms of prime order r>5 are enumerated. For each length and prime considered, all inequivalent extremal codes with an automorphism of that order are found     

Achieving the designed error capacity in decodingalgebraic-geometric codes

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*)² n), where n denotes the length of the code. Application to Hermitian codes and connections with well-known algorithms are explained     

Characterization of quaternary extremal codes of lengths 18 and 20

We prove that, up to equivalence, there is a unique extremal quaternary Hermitian self-dual code of length 18, and that there are two inequivalent extremal quaternary Hermitian self-dual codes of length 20