On Upper Bounds for Minimum Distance and Covering Radius of Non-binary Codes

We consider upper bounds on two fundamental parameters of a code; minimum distance and covering radius. New upper bounds on the covering radius of non-binary linear codes are derived by generalizing a method due to S. Litsyn and A. Tietäväinen lt:newu and combining it with a new upper bound on the asymptotic information rate of non-binary codes. The upper bound on the information rate is an application of a shortening method of a code and is an analogue of the Shannon-Gallager-Berlekamp straight line bound on error probability. These results improve on the best presently known asymptotic upper bounds on minimum distance and covering radius of non-binary codes in certain intervals.     

On t-Covering Arrays

This paper concerns construction methods for t-covering arrays. Firstly, a construction method using perfect hash families is discussed by combining with recursion techniques and error-correcting codes. In particular, by using algebraic-geometric codes for this method we obtain infinite families of t-covering arrays which are proved to be better than currently known probabilistic bounds for covering arrays. Secondly, inspired from a result of Roux [16] and also from a recent result of Chateauneuf and Kreher [6] for 3-covering arrays, we present several explicit constructions for t-covering arrays, which can be viewed as generalizations of their results for t-covering arrays.     

Randomized post-optimization of covering arrays

The construction of covering arrays with the fewest rows remains a challenging problem. Most computational and recursive constructions result in extensive repetition of coverage. While some is necessary, some is not. By reducing the repeated coverage, metaheuristic search techniques typically outperform simpler computational methods, but they have been applied in a limited set of cases. Time constraints often prevent them from finding an array of competitive size. We examine a different approach. Having used a simple computation or construction to find a covering array, we employ a post-optimization technique that repeatedly adjusts the array in an attempt to reduce its number of rows. At every stage the array retains full coverage. We demonstrate its value on a collection of previously best known arrays by eliminating, in some cases, 10% of their rows. In the well-studied case of strength two with twenty factors having ten values each, post-optimization produces a covering array with only 162 rows, improving on a wide variety of computational and combinatorial methods. We identify certain important features of covering arrays for which post-optimization is successful.     

Asymptotic and constructive methods for covering perfect hash families and covering arrays

Covering perfect hash families represent certain covering arrays compactly. Applying two probabilistic methods to covering perfect hash families improves upon the asymptotic upper bound for the minimum number of rows in a covering array with v symbols, k columns, and strength t. One bound can be realized by a randomized polynomial time construction algorithm using column resampling, while the other can be met by a deterministic polynomial time conditional expectation algorithm. Computational results are developed for both techniques. Further, a random extension algorithm further improves on the best known sizes for covering arrays in practice. An extensive set of computations with column resampling and random extension yields explicit constructions when \(k \le 75\) for strength seven, \(k \le 200\) for strength six, \(k \le 600\) for strength five, and \(k \le 2500\) for strength four. When \(v > 3\), almost all known explicit constructions are improved upon. For strength \(t=3\), restrictions on the covering perfect hash family ensure the presence of redundant rows in the covering array, which can be removed. Using restrictions and random extension, computations for \(t=3\) and \(k \le 10{,}000\) again improve upon known explicit constructions in the majority of cases. Computations for strengths three and four demonstrate that a conditional expectation algorithm can produce further improvements at the expense of a larger time and storage investment.     

Constructing strength three covering arrays with augmented annealing

A covering arrayCA(N;t,k,v) is an N×k array such that every N×t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. One application of these objects is to generate software test suites to cover all t-sets of component interactions. Methods for construction of covering arrays for software testing have focused on two main areas. The first is finding new algebraic and combinatorial constructions that produce smaller covering arrays. The second is refining computational search algorithms to find smaller covering arrays more quickly. In this paper, we examine some new cut-and-paste techniques for strength three covering arrays that combine recursive combinatorial constructions with computational search; when simulated annealing is the base method, this is augmented annealing. This method leverages the computational efficiency and optimality of size obtained through combinatorial constructions while benefiting from the generality of a heuristic search. We present a few examples of specific constructions and provide new bounds for some strength three covering arrays.     

Linear covering codes and error-correcting codes for limited-magnitude errors

The concepts of a linear covering code and a covering set for the limited-magnitude-error channel are introduced. A number of covering-set constructions, as well as some bounds, are given. In particular, optimal constructions are given for some cases involving small-magnitude errors. A problem of Stein is partially solved for these cases. Optimal packing sets and the corresponding error-correcting codes are also considered for some small-magnitude errors.     

New Constructions of Covering Codes

Coveringcode constructions obtaining new codes from starting ones weredeveloped during last years. In this work we propose new constructionsof such kind. New linear and nonlinear covering codes and aninfinite families of those are obtained with the help of constructionsproposed. A table of new upper bounds on the length functionis given.     

A New Table of Binary/Ternary Mixed Covering Codes

A table of upper bounds for K3,2(n1,n2;R), the minimum number of codewords in a covering code with n1 ternary coordinates, n2 binary coordinates, and covering radius R, in the range n = n1 + n2 13, R 3, is presented. Explicit constructions of codes are given to prove the new bounds and verify old bounds. These binary/ternary covering codes can be used as systems for the football pool game. The results include a new binary code with covering radius 1 proving K2(13,1) 736, and the following upper bound for the football pool problem for 9 matches: K3(9,1) 1356.     

Bounds for the Multicovering Radii of Reed-Muller Codes with Applications to Stream Ciphers

The multicovering radii of a code are recentgeneralizations of the covering radius of a code. For positivem, the m-covering radius of C is the leastradius t such that everym-tuple of vectors is contained in at least one ball of radiust centered at some codeword. In this paper upper bounds arefound for the multicovering radii of first order Reed-Muller codes. These bounds generalize the well-known Norse bounds for the classicalcovering radii of first order Reed-Muller codes. They are exactin some cases. These bounds are then used to prove the existence of secure families of keystreams against a general class of cryptanalytic attacks. This solves the open question that gave rise to the study ofmulticovering radii of codes.     

On the state of strength‐three covering arrays

A covering array of size N, strength t, degree k, and order υ is a k × N array on υ symbols in which every t × N subarray contains every possible t × 1 column at least once. We present explicit constructions, constructive upper bounds on the size of various covering arrays, and compare our results with those of a commercial product. Applications of covering arrays include software testing, drug screening, and data compression. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 217–238, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10002     

On the Covering Radius of Ternary Extremal Self-Dual Codes

In this paper, we investigate the covering radius of ternary extremal self-dual codes. The covering radii of all ternary extremal self-dual codes of lengths up to 20 were previously known. The complete coset weight distributions of the two inequivalent extremal self-dual codes of length 24 are determined. As a consequence, it is shown that every extremal ternary self-dual code of length up to 24 has covering radius which meets the Delsarte bound. The first example of a ternary extremal self-dual code with covering radius which does not meet the Delsarte bound is also found. It is worth mentioning that the found code is of length 32.     

Covering Arrays of Strength Three

A covering array of size N, degree k, order v and strength t is a k × N array with entries from a set of v symbols such that in any t × N subarray every t × 1 column occurs at least once. Covering arrays have been studied for their applications to drug screening and software testing. We present explicit constructions and give constructive upper bounds for the size of a covering array of strength three.     

Super-visible codes

Upper bounds and constructions are given for super-visible codes. These are linear codes with the property that all words of minimum weight form a basis of the code. Optimal super-visible codes are summarized for small lengths and minimum distances.     

Minimal degree liftings in characteristic 2

In this paper we analyze liftings of hyperelliptic curves over perfect fields in characteristic 2 to curves over rings of Witt vectors. This theory can be applied to construct error-correcting codes; lifts of points with minimal degrees are likely to yield the best codes, and these are the main focus of the paper. We find upper and lower bounds for their degrees, give conditions to achieve the lower bounds and analyze the existence of lifts of the Frobenius. Finally, we exhibit explicit computations for genus 2 and show codes obtained using this theory.     

Linear codes with covering radius 3

The shortest possible length of a q-ary linear code of covering radius R and codimension r is called the length function and is denoted by ℓ _q (r, R). Constructions of codes with covering radius 3 are here developed, which improve best known upper bounds on ℓ _q (r, 3). General constructions are given and upper bounds on ℓ _q (r, 3) for q = 3, 4, 5, 7 and r ≤ 24 are tabulated.     

Covering Sequences of Boolean Functions and Their Cryptographic Significance

We introduce the notion of covering sequence of a Boolean function, related to the derivatives of the function. We give complete characterizations of balancedness, correlation immunity and resiliency of Boolean functions by means of their covering sequences. By considering particular covering sequences, we define subclasses of (correlation-immune) resilient functions. We derive upper bounds on their algebraic degrees and on their nonlinearities. We give constructions of resilient functions belonging to these classes. We show that they achieve the best known trade-off between order of resiliency, nonlinearity and algebraic degree.     

Ternary Covering Codes Derived from BCH Codes

It is shown how ternary BCH codes can be lengthened to get linear codes with covering radius 2. The family obtained has the ternary Golay code as its first code, contains codes with record-breaking parameters, and has a good asymptotic behavior. The ternary Golay code is further used to obtain short proofs for the best known upper bounds for the football pool problem for 11 and 12 matches.     

Constructions of almost secure frameproof codes with applications to fingerprinting schemes

This paper presents explicit constructions of fingerprinting codes. The proposed constructions use a class of codes called almost secure frameproof codes. An almost secure frameproof code is a relaxed version of a secure frameproof code, which in turn is the same as a separating code. This relaxed version is the object of our interest because it gives rise to fingerprinting codes of higher rate than fingerprinting codes derived from separating codes. The construction of almost secure frameproof codes discussed here is based on weakly biased arrays, a class of combinatorial objects tightly related to weakly dependent random variables.     

Energy Minimization and Flux Domain Structure in the Intermediate State of a Type-I Superconductor

The intermediate state of a type-I superconductor involves a fine-scale mixture of normal and superconducting domains. We take the viewpoint, due to Landau, that the realizable domain patterns are (local) minima of a nonconvex variational problem. We examine the scaling law of the minimum energy and the qualitative properties of domain patterns achieving that law. Our analysis is restricted to the simplest possible case: a superconducting plate in a transverse magnetic field. Our methods include explicit geometric constructions leading to upper bounds and ansatz-free inequalities leading to lower bounds. The problem is unexpectedly rich when the applied field is near-zero or near-critical. In these regimes there are two small parameters, and the ground state patterns depend on the relation between them.