Some new results on superimposed codes

A (w,r) cover‐free family is a family of subsets of a finite set such that no intersection of w members of the family is covered by a union of r others. A (w,r) superimposed code is the incidence matrix of such a family. Such a family also arises in cryptography as the concept of key distribution pattern. In the present paper, we give some new results on superimposed codes. First we construct superimposed codes from super‐simple designs which give us results better than superimposed codes constructed by other known methods. Next we prove the uniqueness of the (1,2) superimposed code of size 9 × 12, the (2,2) superimposed code of size 14 × 8, and the (2,3) superimposed code of size 30 × 10. Finally, we improve numerical values of upper bounds for the asymptotic rate of some (w,r) superimposed codes. © 2004 Wiley Periodicals, Inc.     

Gray code for derangements

We give a Gray code and constant average time generating algorithm for derangements, i.e., permutations with no fixed points. In our Gray code, each derangement is transformed into its successor either via one or two transpositions or a rotation of three elements. We generalize these results to permutations with number of fixed points bounded between two constants.     

The Covering Radius of Ternary Cyclic Codes with Length up to 25

The covering radius of all ternary cyclic codes of length up to 25 is given. Some of the results were obtained by computer and for others mathematical reasonings were applied. The minimal distances of all codes were recalculated.     

How to Build Robust Shared Control Systems

Previous researchers have designed shared control schemes with a view to minimising the likelihood that participants will conspire to perform an unauthorised act. But, human nature being what it is, systems inevitably fail; so shared control schemes should also be designed so that the police can identify conspirators after the fact. This requirement leads us to search for schemes with sparse access structures. We show how this can be done using ideas from coding theory. In particular, secret sharing schemes based on geometric codes whose dual [n,k,d] codes have d and n as their only nonzero weights are suitable. We determine their access structures and analyse their properties. We have found almost all of them, and established some relations among codes, designs and secret-sharing schemes.     

Codes with a Certain Weight-preserving Transitive Group of Automorphisms

We determine all linear codes C containing the constant code E, for which there is a weight-preserving group of semilinear automorphisms which acts transitively on the set of nontrivial cosets of E in C. Michael Giudici - The author holds an Australian Postdoctoral Fellowship.     

Enumeration of inequivalent irreducible Goppa codes

We consider irreducible Goppa codes over F_q of length qⁿ defined by polynomials of degree r, where q is a prime power and n,r are arbitrary positive integers. We obtain an upper bound on the number of such codes.     

The largest strongly consecutive repeat-free code

Answering a question of Körner and Simonyi, this paper gives a strongly consecutive repeat-free code of maximal size in [b]ⁿ.     

Algorithmic and explicit determination of the Lovász number for certain circulant graphs

We consider the problem of computing the Lovász theta function for circulant graphs C_n,J of degree four with n vertices and chord length J, 2?J?n. We present an algorithm that takes O(J) operations if J is an odd number, and O(n/J) operations if J is even. On the considered class of graphs our algorithm strongly outperforms the known algorithms for theta function computation. We also provide explicit formulas for the important special cases J=2 and J=3.