On optimal 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 binary (w,r) superimposed code is the incidence matrix of such a family. Such a family also arises in cryptography as a concept of key distribution patterns. In this paper, we develop a method of constructing superimposed codes and prove that some superimposed codes constructed in this way are optimal. © 2003 Wiley Periodicals, Inc. J Combin Designs 12: 79–71, 2004.     

Testing algebraic geometric codes

Property testing was initially studied from various motivations in 1990’s. A code C  GF (r)n is locally testable if there is a randomized algorithm which can distinguish with high possibility the codewords from a vector essentially far from the code by only accessing a very small (typically constant) number of the vector’s coordinates. The problem of testing codes was firstly studied by Blum, Luby and Rubinfeld and closely related to probabilistically checkable proofs (PCPs). How to characterize locally te...     

Super-simple (ν, 5, 5) Designs

Super-simple designs are useful in constructing codes and designs such as superimposed codes and perfect hash families. In this article, we investigate the existence of a super-simple (ν, 5, 5) balanced incomplete block design and show that such a design exists if and only if ν ≡ 1 (mod 4) and ν ≥ 17 except possibly when ν = 21. Applications of the results to optical orthogonal codes are also mentioned. Research supported by NSERC grant 239135-01.     

Splitting balanced incomplete block designs with block size 3 × 2

Splitting balanced incomplete block designs were first formulated by Ogata, Kurosawa, Stinson, and Saido recently in the investigation of authentication codes. This article investigates the existence of splitting balanced incomplete block designs, i.e., (v, 3k, λ)‐splitting BIBDs; we give the spectrum of (v, 3 × 2, λ)‐splitting BIBDs. As an application, we obtain an infinite class of 2‐splitting A‐codes. © 2004 Wiley Periodicals, Inc.     

Optimal binary covering codes of length 2j

The minimum size of a binary covering code of length n and covering radius r is denoted by K(n,r), and codes of this length are called optimal. For j > 0 and n = 2^j, it is known that K(n,1) = 2 · K(n?1,1) = 2^{n ? j}. Say that two binary words of length n form a duo if the Hamming distance between them is 1 or 2. In this paper, it is shown that each optimal binary covering code of length n = 2^j, j > 0, and covering radius 1 is the union of duos in just one way, and that the closed neighborhoods of the duos form a tiling of the set of binary words of length n. Methods of constructing such optimal codes from optimal covering codes of length n ? 1 (that is, perfect single‐error‐correcting codes) are discussed. The paper ends with the construction of an optimal covering code of length 16 that does not contain an extension of any optimal covering code of length 15. © 2005 Wiley Periodicals, Inc. J Combin Designs     

New classes of self-complementary codes and quasi-symmetric designs

We present a new technique for constructing binary error correcting codes and give some examples of codes that can be constructed via this method. Among the examples is an infinite family of self-complementary codes with parameters (2u ²−u, 8u ², u ²−u) that can be constructed whenever there exists a u × u Hadamard Matrix. These codes meet the Grey–Rankin bound and imply the existence of quasi-symmetric designs on 2u ²−u points.     

An Extension Theorem for Linear Codes

One of the first results one meets in coding theory is that a binary linear [n,k,d] code, whose minimum distance is odd, can be extended to an [n + 1, k, d + 1] code. This is one of the few elementary results about binary codes which does not obviously generalise to q-ary codes. The aim of this paper is to give a simple sufficient condition for a q-ary [n, k, d] code to be extendable to an [n + 1, k, d + 1] code. Applications will be given to the construction and classification of good codes, to proving the non- existence of certain codes, and also an application in finite geometry.     

Reed-Muller codes and Barnes-Wall lattices: Generalized multilevel constructions and representation over GF(2<Superscript><Emphasis Type="Italic">q</Emphasis></Superscript>)

Generalized multilevel constructions for binary RM(r,m) codes using projections onto GF(2 ^q ) are presented. These constructions exploit component codes over GF(2), GF(4),..., GF(2 ^q ) that are based on shorter Reed-Muller codes and set partitioning using partition chains of length-2 ^l codes. Using these constructions we derive multilevel constructions for the Barnes-Wall Λ(r,m) family of lattices which also use component codes over GF(2), GF(4),..., GF(2 ^q ) and set partitioning based on partition chains of length-2 ^l lattices. These constructions of Reed-Muller codes and Barnes-Wall lattices are readily applicable for their efficient decoding.      

Direct constructions of additive codes

A code is q^m‐ary q‐linear if its alphabet forms an m‐dimensional vector space over ??_q and the code is linear over ??_q. These additive codes form a natural generalization of linear codes. Our main results are direct constructions of certain families of additive codes. These comprise the additive generalization of the Kasami codes, an additive generalization of the Bose‐Bush construction of orthogonal arrays of strength 2 as well as a class of additive codes which are being used for deep space communication. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 207–216, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.20000     

The Structure of 1-Generator Quasi-Twisted Codes and New Linear Codes

One of the most important problems of coding theory is to construct codes with best possible minimum distances. Recently, quasi-cyclic (QC) codes have been proven to contain many such codes. In this paper, we consider quasi-twisted (QT) codes, which are generalizations of QC codes, and their structural properties and obtain new codes which improve minimum distances of best known linear codes over the finite fields GF(3) and GF(5). Moreover, we give a BCH-type bound on minimum distance for QT codes and give a sufficient condition for a QT code to be equivalent to a QC code.     

Optimal grid holey packings with block size 3 and 4

The notion of a grid holey packing (GHP) was first proposed for the construction of constant composite codes. For a GHP (k, 1; n ×  g) of type [w ₁, . . . , w _g ], where , the fundamental problem is to determine the packing number N([w ₁, . . . , w _g ], 1; n ×  g), that is, the maximum number of blocks in such a GHP. In this paper we determine completely the values of N([w ₁, . . . , w _g ], 1; n ×  g) in the case of block size .      

A numerical method for computing radially symmetric solutions of a dissipative nonlinear modified Klein‐Gordon equation

In this article we develop a finite‐difference scheme to approximate radially symmetric solutions of a dissipative nonlinear modified Klein‐Gordon equation subject to smooth initial conditions ? and ψ in an open sphere D around the origin, with constant internal and external damping coefficients—β and γ, respectively—, and nonlinear term of the form G′(w) = w^p, with p > 1 an odd number. The functions ? and ψ are radially symmetric in D, and ?, ψ, r?, and rψ are assumed to be small at infinity. We prove that our scheme is consistent order ??(Δt²) + ??(Δr²) for G′ identically equal to zero and provide a necessary condition for it to be stable order n. Part of our study will be devoted to compare the physical effects of β and γ. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005     

An improvement of discrete Tardos fingerprinting codes

It has been proven that the code lengths of Tardos’s collusion-secure fingerprinting codes are of theoretically minimal order with respect to the number of adversarial users (pirates). However, the code lengths can be further reduced as some preceding studies have revealed. In this article we improve a recent discrete variant of Tardos’s codes, and give a security proof of our codes under an assumption weaker than the original Marking Assumption. Our analysis shows that our codes have significantly shorter lengths than Tardos’s codes. For example, when c = 8, our code length is about 4.94% of Tardos’s code in a practical setting and about 4.62% in a certain limit case. Our code lengths for large c are asymptotically about 5.35% of Tardos’s codes. A part of this work was presented at 17th Applied Algebra, Algebraic Algorithms, and Error Correcting Codes (AAECC-17), Bangalore, India, December 16–20, 2007.     

Optimal doubly constant weight codes

A doubly constant weight code is a binary code of length n₁ + n₂, with constant weight w₁ + w₂, such that the weight of a codeword in the first n₁ coordinates is w₁. Such codes have applications in obtaining bounds on the sizes of constant weight codes with given minimum distance. Lower and upper bounds on the sizes of such codes are derived. In particular, we show tight connections between optimal codes and some known designs such as Howell designs, Kirkman squares, orthogonal arrays, Steiner systems, and large sets of Steiner systems. These optimal codes are natural generalization of Steiner systems and they are also called doubly Steiner systems. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 137–151, 2008     

Recursive constructions for optimal (n,4,2)‐OOCs

In [ 3 ], a general recursive construction for optical orthogonal codes is presented, that guarantees to approach the optimum asymptotically if the original families are asymptotically optimal. A challenging problem on OOCs is to obtain optimal OOCs, in particular with λ > 1. Recently we developed an algorithmic scheme based on the maximal clique problem (MCP) to search for optimal (n, 4, 2)‐OOCs for orders up to n = 44. In this paper, we concentrate on recursive constructions for optimal (n, 4, 2)‐OOCs. While “most” of the codewords can be constructed by general recursive techniques, there remains a gap in general between this and the optimal OOC. In some cases, this gap can be closed, giving recursive constructions for optimal (n, 4, 2)‐OOCs. This is predicated on reducing a series of recursive constructions for optimal (n, 4, 2)‐OOCs to a single, finite maximal clique problem. By solving these finite MCP problems, we can extend the general recursive construction for OOCs in [ 3 ] to obtain new recursive constructions that give an optimal (n · 2^x, 4, 2)‐OOC with x ≥ 3, if there exists a CSQS(n). © 2004 Wiley Periodicals, Inc.     

On Harmonic Weight Enumerators of Binary Codes

We define some new polynomials associated to a linear binary code and a harmonic function of degree k. The case k=0 is the usual weight enumerator of the code. When divided by (xy) ^k , they satisfy a MacWilliams type equality. When applied to certain harmonic functions constructed from Hahn polynomials, they can compute some information on the intersection numbers of the code. As an application, we classify the extremal even formally self-dual codes of length 12.     

A Class of Perfect Ternary Constant-Weight Codes

We construct a class of perfect ternary constant-weight codes of length 2 ^r , weight 2 ^r -1 and minimum distance 3. The codes have codewords. The construction is based on combining cosets of binary Hamming codes. As a special case, for r=2 the construction gives the subcode of the tetracode consisting of its nonzero codewords. By shortening the perfect codes, we get further optimal codes.     

Constructions of 2‐cover‐free families and related separating hash families

Cover‐free families (CFFs) were considered from different subjects by numerous researchers. In this article, we mainly consider explicit constructions of (2; d)‐cover‐free families. We also determine the size of optimal 2‐cover‐free‐families on 9, 10, and 11 points. Related separating hash families, which can be used to construct CFFs, are also discussed. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 423–440, 2006     

Some New Results on Optimal Codes Over F5

We present some results on almost maximum distance separable (AMDS) codes and Griesmer codes of dimension 4 over over the field of order 5. We prove that no AMDS code of length 13 and minimum distance 5 exists, and we give a classification of some AMDS codes. Moreover, we classify the projective strongly optimal Griesmer codes over F₅ of dimension 4 for some values of the minimum distance.     

Classification of binary covering codes

The minimum size of a binary covering code of length n and covering radius r is denoted by K (n, r) and corresponding codes are called optimal. In this article a classification up to equivalence of all optimal covering codes having either length at most 8 or cardinality at most 4 is completed. Moreover, we prove that K (9, 2) = 16. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 391–401, 2000