Abstract A t - $$\text {GHD}_k(s,v;\lambda )$$ GHD k ( s , v ; λ ) generalized Howell design is an $$s \times s$$ s × s array, each cell of which is either empty or contains a k -subset of elements of some set X of size v such that (i) each element of X appears exactly once in each row and in each column and (ii) no t -subset of elements from X appears in more than $$\lambda $$ λ cells. Computer-aided classification of such designs is here considered in the framework of permutation codes with specific properties. Among other things, it is shown that a 2- $$\text {GHD}_3(7,18;1)$$ GHD 3 ( 7 , 18 ; 1 ) exists and is unique; this settles the existence problem for 2- $$\text {GHD}_3(n+1,3n;1)$$ GHD 3 ( n + 1 , 3 n ; 1 ) .

Let$\textrm {S}(n,t,k)$be the maximum size of a code containing only vectors of the kth shell of the integer lattice$\mathbb {Z}^{n}$such that the inner product between distinct vectors does not exceed t. In this paper we compute lower bounds for$\textrm {S}(n,t,k)$for small values of n, t and k by carrying out computer searches for codes with prescribed automorphisms. We prescribe groups of signed permutation automorphisms acting transitively on the pairs of coordinates and coordinate values as well as other closely related groups of automorphisms. Several of the constructed codes lead to improved lower bounds for spherical codes.

LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of O(1), Θ(log* n), or Θ(n), and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: O(1), Θ(log* n), and Θ(n). However, given an LCL problem it is undecidable whether its complexity is Θ(log* n) or Θ(n) in 2-dimensional grids.

A q-ary code of length n, size M, and minimum distanced is called an (n,M,d)q code. An (n,qk,n - k + 1)qcode is called a maximum distance separable (MDS) code. In this paper, some MDS codes over small alphabets are classified. It is shown that every (k + d - 1, qk, d)qcode with k ≥ 3, d ≥ 3, q ∈ (5, 7} is equivalent to a linear code with the same parameters. This implies that the (6, 54, 3)5code and the (n, 7n-2, 3)7MDS codes for n ∈ (6, 7, 8} are unique. The classification of one-error-correcting 8-ary MDS codes is also finished; there are 14, 8, 4, and 4 equivalence classes of (n, 8n-2, 3)8codes for n = 6, 7, 8, and 9, respectively. One of the equivalence classes of perfect (9, 87, 3)8codes corresponds to the Hamming code and the other three are nonlinear codes for which there exists no previously known construction.

Best and Brouwer proved that triply-shortened and doubly-shortened binary Hamming codes (which have length 2m-4 and 2m-3, respectively) are optimal. Properties of such codes are here studied, determining among other things parameters of certain subcodes. A utilization of these properties makes a computer-aided classification of the optimal binary one-error-correcting codes of lengths 12 and 13 possible; there are 237 610 and 117 823 such codes, respectively (with 27 375 and 17 513 inequivalent extensions). This completes the classification of optimal binary one-error-correcting codes for all lengths up to 15. Some properties of the classified codes are further investigated. Finally, it is proved that for any m ≥ 4, there are optimal binary one-error-correcting codes of length 2m-4 and 2m-3 that cannot be lengthened to perfect codes of length 2m-1.

LetA(n,d) denote the maximum size of a binary code with lengthnand minimum distanced. It has been known for decades thatA(16,7) =A(17,8) = 36 or 37, that is, that the size of optimal 3-error-correcting binary codes of length 16 is either 36 or 37. By a recursive classification via subcodes and a clique search in the final stage, it is shown that the size of optimal such codes is 36.

A binary codeC⊆ F2nwith minimum distance at leastdand codewords of Hamming weightwis called an(n,d,w) constant weight code. The maximum size of an(n,d,w) constant weight code is denoted byA(n,d,w), and codes of this size are said to be optimal. In a computer-aided approach, optimal(n,d,w) constant weight codes are here classified up to equivalence ford=4,n≤ 12;d=6,n≤ 14;d=8,n≤ 17;d=10,n≤ 20 (with one exception);d=12,n≤ 23;d=14,n≤ 26;d=16,n≤ 28; andd=18,n≤ 28. Moreover, several new upper bounds onA(n,d,w) are obtained, leading among other things to the exact valuesA(12,4,5)=80,A(15,6,7)=69,A(18,8,7)=33,A(19,8,7)=52,A(19,8,8)=78, andA(20,8,8)=130 . SinceA(15,6,6)=70, this gives the first known example of parameters for whichA(n,d,w-1) >A(n,d,w) withw≤n/2. A scheme based on double counting is developed for validating the classification results.

A complete classification of the perfect binary one-error-correcting codes of length 15, as well as their extensions of length 16, was recently carried out in [P. R. J. O¿stergård and O. Pottonen, ¿The perfect binary one-error-correcting codes of length 15: Part I-Classification,¿IEEE Trans. Inf. Theoryvol. 55, pp. 4657-4660, 2009]. In the current accompanying work, the classified codes are studied in great detail, and their main properties are tabulated. The results include the fact that 33 of the 80 Steiner triple systems of order 15 occur in such codes. Further understanding is gained on full-rank codes via switching, as it turns out that all but two full-rank codes can be obtained through a series of such transformations from the Hamming code. Other topics studied include (non)systematic codes, embedded one-error-correcting codes, and defining sets of codes. A classification of certain mixed perfect codes is also obtained.

The minimum distance graph of a code has the codewords as vertices and edges exactly when the Hamming distance between two codewords equals the minimum distance of the code. A constructive proof for reconstructibility of an extended perfect binary one-error-correcting code from its minimum distance graph is presented. Consequently, inequivalent such codes have nonisomorphic minimum distance graphs. Moreover, it is shown that the automorphism group of a minimum distance graph is isomorphic to that of the corresponding code.

A complete classification of the perfect binary one-error-correcting codes of length 15 as well as their extensions of length 16 is presented. There are 5983 such inequivalent perfect codes and 2165 extended perfect codes. Efficient generation of these codes relies on the recent classification of Steiner quadruple systems of order 16. Utilizing a result of Blackmore, the optimal binary one-error-correcting codes of length 14 and the(15,1024,4)codes are also classified; there are 38 408 and 5983 such codes, respectively.

New uniquely decodable (UD) codes for 3-, 4-, and 5-user binary adder channels are obtained in a computer search. These codes improve the highest known rate of UD codes for such channels to (log2/600)6ap1.5381,1.75, and (log2/192)4ap1.8962, respectively

A code C/spl sube/Z/sup n//sub 2/, where Z/sub 2/={0,1}, has unidirectional covering radius R if R is the smallest integer so that any word in Z/sup n//sub 2/ can be obtained from at least one codeword c/spl isin/C by replacing either 1s by 0s in at most R coordinates or 0s by 1s in at most R coordinates. The minimum cardinality of such a code is denoted by E(n,R). Upper bounds on this function are here obtained by constructing codes using tabu search; lower bounds, on the other hand, are mainly obtained by integer programming and exhaustive search. Best known bounds on E(n,R) for n/spl les/13 and R/spl les/6 are tabulated.

Several methods for classifying self-orthogonal codes up to equivalence are presented. These methods are used to classify self-orthogonal codes with largest possible minimum distance over the fields $\mathbb{F}_3$ and $\mathbb{F}_4$ for lengths $n \leq 29$ and small dimensions (up to 6). Some properties of the classified codes are also presented. In particular, an extensive collection of quantum error-correcting codes is obtained.

A new uniquely decodable (UD) code pair for the two-user binary adder channel (BAC) is presented. This code pair leads to an improved bound for the zero-error capacity region of such a channel. The highest known rate for a UD code pair for the two-user BAC is thereby improved to (log/sub 2/240)/6/spl ap/1.3178. It is also demonstrated that the problem of finding UD code pairs for the closely related binary XOR channel is in one-to-one correspondence with a certain construction of binary one-error-correcting codes.

A tiling of $\F^n$ is a pair (V,A) of subsets of $\F^n$ such that every $x \in \F^n$ can be written in exactly one way as x = v + a with $v \in V$ and $a \in A$. A tiling (V,A) of $\F^n$ is said to be full-rank if $\rank(V)=\rank(A)=n$ and $\zero \in (V\! \cap A)$. It is known that every tiling (V,A)$ decomposes into smaller tilings that are either trivial or full rank. It is furthermore known that full-rank tilings of $\F^n$ exist for all $n \geq 10$ and do not exist for $n \leq 8$. The last case n= 9 is resolved in this paper, thereby proving that full-rank tilings of $\F^n$ exist if and only if $n \ge 10$. To establish this result, we use two different methods. The first method employs group characters to show that the sets V and A in a full-rank tiling (V,A) of $\F^9$ must have a certain structure. The second method is based on the classification of [14,5,3] binary linear codes and uses a fast algorithm for the exact cover problem. Both methods rely on a carefully designed exhaustive computer search to complete the proof.

Hermitian self-dual quaternary codes exist for all even lengths. The smallest length for which the maximum possible minimum distance of such codes is undetermined is 26; it is then either 8 or 10. By exhaustive computer search this case is settled; it is shown that minimum distance 10 is impossible for these parameters.

We classify all optimal linear [n,n/2,d] codes over F/sub 4/ up to length 18. In particular, we show that there is a unique optimal [12,6,6] code and three optimal [16,8,7] codes, up to equivalence.

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.

The problem of determining the maximum size of a ternary code is considered, under the restriction that each symbol should appear a given number of times in each codeword. Upper and lower bounds on the size of such codes under the Hamming metric are discussed, where the lower bounds follow from constructions of good codes. Some of the results are obtained by explicitly finding codes by computer search. A table of exact values and best known bounds on the maximum size for codes of length at most 10 is presented.

Let [n,n-r]/sub q/R denote a linear code over F/sub q/ with length n, codimension r, and covering radius R. We use a modification of constructions of [2q+1, 2q-3]/sub q/2 and [3q+1, 3q-5]/sub q/3 codes (q/spl ges/5) to produce infinite families of good codes with covering radius 2 and 3 and codimension tR.

The minimum number of codewords in a binary code with length n and covering radius R is denoted by K(n, R). The values of K(n, 1) are known up to length 8, and the corresponding optimal codes have been classified. It is known that 57/spl les/K(9, 1)/spl les/62. In the current work, the lower bound is improved to settle K(9, 1)=62. In the approach, which is computer-aided, possible distributions of codewords in subspaces are refined until each subspace is of dimension zero (consists of only one word). Repeatedly, a linear programming problem is solved considering only inequivalent distributions. A connection between this approach and weighted coverings is also presented; the computations give new results for such coverings as a by-product.

The maximum number of codewords in a binary code with length n and minimum distance d is denoted by A(n, d). By construction it is known that A(10, 3)/spl ges/72 and A(11, 3)/spl ges/144. These bounds have long been conjectured to be the exact values. This is here proved by classifying various codes of smaller length and lengthening these using backtracking and isomorphism rejection. There are 562 inequivalent codes attaining A(10, 3)=72 and 7398 inequivalent codes attaining A(11, 3)=144.

Upper and lower bounds are presented for the maximal possible size of mixed binary/ternary error-correcting codes. A table up to length 13 is included. The upper bounds are obtained by applying the linear programming bound to the product of two association schemes. The lower bounds arise from a number of different constructions.

Many of the fundamental coding problems can be represented as graph problems. These problems are often intrinsically difficult and unsolved even if the code length is relatively small. With the motivation to improve lower bounds on the sizes of constant weight codes and asymmetric codes, we suggest a few greedy algorithms and other heuristic methods, which result in new, record-breaking codes. Some of the heuristics used are based on tabu search and evolutionary algorithms. Tables of new codes are presented.

New codes of dimension 7 are presented which give improved bounds on the maximum possible minimum distance of ternary linear codes. These codes belong to the class of quasi-cyclic codes, and have been constructed using a stochastic optimization algorithm, tabu search. Thirty-two codes are given which improve or establish the current bounds for ternary codes. In addition, a table of upper and lower bounds for d/sub 3/(n, 7) is presented for n/spl les/240.

New constant weight codes are found by considering certain linear permutation groups. A code is obtained as a collection of orbits of words under such a group. This leads to a difficult optimization problem, where a stochastic search heuristic, tabu search, is used to find good solutions in a feasible amount of time. Nearly 40 new codes of length at most 28 are presented.

A matrix construction of nonlinear error-correcting codes is considered. It is shown how this construction and some related theorems can be applied to old codes to get new codes with minimum distance 3. In total 13 new binary single-error-correcting codes of length at most 511 are obtained.

A binary code $C \subseteq \mathbb{F}_2^n$ with M codewords is called an $( n,M,r,u )$ multiple covering of the farthest-off points (MCF) if the Hamming spheres of radius r centered at the codewords cover the whole space $\mathbb{F}_2^n $ and every $x \in \mathbb{F}_2^n $ such that $d( x,C ) = r$ is covered by at least $\mu $ codewords. The minimum possible cardinality $F( n,r,\mu )$ of such a code is studied and tables of upper bounds on $F ( n,r,\mu )$ for $n \leq 16,r \leq 4,\mu \leq 4$ are given.

The concept of (k, t)-subnormal covering codes, is discussed generalizing some of the earlier results. In a similar way, (k, t)-normal covering codes are defined. Using the results, including some new constructions, upper bounds for covering codes are improved. It is shown how simulated annealing can be used to find acceptable partitions for codes.>

A mixed code of covering radius 1 that has 60 codewords is constructed. This code is then used to show that K(10,1)>

New methods for constructing q-ary covering codes are presented. The author introduces the concepts of (p-) seminormal and strongly (p-) seminormal codes and shows how seminormal codes and punctured Hamming codes can be combined to construct new covering codes. Using these methods, upper bounds for ternary covering codes are improved. The new bounds are K/sub 3/