Optimal interleaving schemes for correcting two-dimensional cluster errors

We present an elementary theory of optimal interleaving schemes for correcting cluster errors in two-dimensional digital data. It is assumed that each data page contains a fixed number of, say n, codewords with each codeword consisting of m code symbols and capable of correcting a single random error (or erasure). The goal is to interleave the codewords in the m×n array such that different symbols from each codeword are separated as much as possible, and consequently, an arbitrary error burst with size up to t can be corrected for the largest possible value of t. We show that, for any given m, n, the maximum possible interleaving distance, or equivalently, the largest size of correctable error bursts in an m×n array, is given by if n?⌈m²/2⌉, and t=m+⌊(n-⌈m²/2⌉)/m⌋ if n?⌈m²/2⌉. Furthermore, we develop a simple cyclic shifting algorithm that can provide a systematic construction of an m×n optimal interleaving array for arbitrary m and n. This extends important earlier work on the complementary problem of constructing interleaving arrays that, given the burst size t, minimize the interleaving degree, that is, the number of different codewords in a 2-D (or 3-D) array such that any error burst with given size t can be corrected. Our interleaving scheme thus provides the maximum burst error correcting power without requiring prior knowledge of the size or shape of an error burst.     

On codewords in the dual code of classical generalised quadrangles and classical polar spaces

In [J.L. Kim, K. Mellinger, L. Storme, Small weight codewords in LDPC codes defined by (dual) classical generalised quadrangles, Des. Codes Cryptogr. 42 (1) (2007) 73-92], the codewords of small weight in the dual code of the code of points and lines of Q(4,q) are characterised. Inspired by this result, using geometrical arguments, we characterise the codewords of small weight in the dual code of the code of points and generators of Q⁺(5,q) and H(5,q²), and we present lower bounds on the weight of the codewords in the dual of the code of points and k-spaces of the classical polar spaces. Furthermore, we investigate the codewords with the largest weights in these codes, where for q even and k sufficiently small, we determine the maximum weight and characterise the codewords of maximum weight. Moreover, we show that there exists an interval such that for every even number w in this interval, there is a codeword in the dual code of Q⁺(5,q), q even, with weight w and we show that there is an empty interval in the weight distribution of the dual of the code of Q(4,q), q even. To prove this, we show that a blocking set of Q(4,q), q even, of size q²+1+r, where 0<r<(q+4)/6, contains an ovoid of Q(4,q), improving on [J. Eisfeld, L. Storme, T. Sz?nyi, P. Sziklai, Covers and blocking sets of classical generalised quadrangles, Discrete Math. 238 (2001) 35-51, Theorem 9].     

Intersections of q-ary perfect codes

The intersections of q-ary perfect codes are under study. We prove that there exist two q-ary perfect codes C ₁ and C ₂ of length N = qn + 1 such that |C ₁ ? C ₂| = k · |P _i |/p for each k ∈ {0,..., p · K ? 2, p · K}, where q = p ^r , p is prime, r ≥ 1, $n = \tfrac{{q^{m - 1} - 1}}{{q - 1}}$ , m ≥ 2, |P _i | = p ^nr(q?2)+n , and K = p ^{n(2r?1)?r(m?1)}. We show also that there exist two q-ary perfect codes of length N which are intersected by p ^nr(q?3)+n codewords.     

On the admissible families of components of hamming codes

In this paper, the properties of the i-components of Hamming codes are described. We suggest constructions of the admissible families of components of Hamming codes. Each q-ary code of length m and minimum distance 5 (for q = 3, the minimum distance is 3) is shown to embed in a q-ary 1-perfect code of length n = (q ^m − 1)/(q − 1). Moreover, each binary code of length m+k and minimum distance 3k + 3 embeds in a binary 1-perfect code of length n = 2 ^m − 1.     

New upper bounds for parent-identifying codes and traceability codes

In the last two decades, parent-identifying codes and traceability codes are introduced to prevent copyrighted digital data from unauthorized use. They have important applications in the scenarios like digital fingerprinting and broadcast encryption schemes. A major open problem in this research area is to determine the upper bounds for the cardinalities of these codes. In this paper we will focus on this theme. Consider a code of length N which is defined over an alphabet of size q. Let \(M_{IPPC}(N,q,t)\) and \(M_{TA}(N,q,t)\) denote the maximal cardinalities of t-parent-identifying codes and t-traceability codes, respectively, where t is known as the strength of the codes. We show \(M_{IPPC}(N,q,t)\le rq^{\lceil N/(v-1)\rceil }+(v-1-r)q^{\lfloor N/(v-1)\rfloor }\), where \(v=\lfloor (t/2+1)^2\rfloor \), \(0\le r\le v-2\) and \(N\equiv r \mod (v-1)\). This new bound improves two previously known bounds of Blackburn, and Alon and Stav. On the other hand, \(M_{TA}(N,q,t)\) is still not known for almost all t. In 2010, Blackburn, Etzion and Ng asked whether \(M_{TA}(N,q,t)\le cq^{\lceil N/t^2\rceil }\) or not, where c is a constant depending only on N, and they have shown the only known validity of this bound for \(t=2\). By using some complicated combinatorial counting arguments, we prove this bound for \(t=3\). This is the first non-trivial upper bound in the literature for traceability codes with strength three.     

Good equidistant codes constructed from certain combinatorial designs

An (n,M,d;q) code is called equidistant code if the Hamming distance between any two codewords is d. It was proved that for any equidistant (n,M,d;q) code, d?nM(q-1)/(M-1)q(=d_opt, say). A necessary condition for the existence of an optimal equidistant code is that d_opt be an integer. If d_opt is not an integer, i.e. the equidistant code is not optimal, then the code with d=⌊d_opt⌋ is called good equidistant code, which is obviously the best possible one among equidistant codes with parameters n,M and q. In this paper, some constructions of good equidistant codes from balanced arrays and nested BIB designs are described.     

Further results on the covering radius of small codes

The minimum number of codewords in a code with t ternary and b binary coordinates and covering radius R is denoted by K(t,b,R). In the paper, necessary and sufficient conditions for K(t,b,R)=M are given for M=6 and 7 by proving that there exist exactly three families of optimal codes with six codewords and two families of optimal codes with seven codewords. The cases M?5 were settled in an earlier study by the same authors. For binary codes, it is proved that K(0,2b+4,b)?9 for b?1. For ternary codes, it is shown that K(3t+2,0,2t)=9 for t?2. New upper bounds obtained include K(3t+4,0,2t)?36 for t?2. Thus, we have K(13,0,6)?36 (instead of 45, the previous best known upper bound).     

There exist Steiner triple systems of order 15 that do not occur in a perfect binary one‐error‐correcting code

The codewords at distance three from a particular codeword of a perfect binary one‐error‐correcting code (of length 2^m?1) form a Steiner triple system. It is a longstanding open problem whether every Steiner triple system of order 2^m?1 occurs in a perfect code. It turns out that this is not the case; relying on a classification of the Steiner quadruple systems of order 16 it is shown that the unique anti‐Pasch Steiner triple system of order 15 provides a counterexample. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 465–468, 2007     

On constant composition codes

A constant composition code over a k-ary alphabet has the property that the numbers of occurrences of the k symbols within a codeword is the same for each codeword. These specialize to constant weight codes in the binary case, and permutation codes in the case that each symbol occurs exactly once. Constant composition codes arise in powerline communication and balanced scheduling, and are used in the construction of permutation codes. In this paper, direct and recursive methods are developed for the construction of constant composition codes.     

On full-rank perfect codes over finite fields

We propose a construction of full-rank q-ary 1-perfect codes. This is a generalization of the construction of full-rank binary 1-perfect codes by Etzion and Vardy (1994). The properties of the i-components of q-ary Hamming codes are investigated, and the construction of full-rank q-ary 1-perfect codes is based on these properties. The switching construction of 1-perfect codes is generalized to the q-ary case. We propose a generalization of the notion of an i-component of a 1-perfect code and introduce the concept of an (i, σ)-component of a q-ary 1-perfect code. We also present a generalization of the Lindström–Schönheim construction of q-ary 1-perfect codes and provide a lower bound for the number of pairwise distinct q-ary 1-perfect codes of length n.     

Codes that attain minimum distance in every possible direction

The following problem motivated by investigation of databases is studied. Let be a q-ary code of length n with the properties that has minimum distance at least n − k + 1, and for any set of k − 1 coordinates there exist two codewords that agree exactly there. Let f(q, k)be the maximum n for which such a code exists. f(q, k)is bounded by linear functions of k and q, and the exact values for special k and qare determined.      

Bounds for Covering Codes over Large Alphabets

Let K_q(n,R) denote the minimum number of codewords in any q-ary code of length n and covering radius R. We collect lower and upper bounds for K_q(n,R) where 6 ≤ q ≤ 21 and R ≤ 3. For q ≤ 10, we consider lengths n ≤ 10, and for q ≥ 11, we consider n ≤ 8. This extends earlier results, which have been tabulated for 2 ≤ q ≤ 5. We survey known bounds and obtain some new results as well, also for s-surjective codes, which are closely related to covering codes and utilized in some of the constructions.AMS Classification: 94B75, 94B25, 94B65Gerzson Kéri - Supported in part by the Hungarian National Research Fund, Grant No. OTKA-T029572.Patric R. J. Östergård - Supported in part by the Academy of Finland, Grants No. 100500 and No. 202315.     

Classification and nonexistence results for linear codes with prescribed minimum distances

Starting from a linear [n, k, d] _q code with dual distance ${d^{\bot}}$ , we may construct an ${[n - d^\bot, k - d^\bot +1,\geq d]_q}$ code with dual distance at least ${\left\lceil\frac{d^\bot}{q}\right\rceil}$ using construction Y ₁. The inverse construction gives a rule for the classification of all [n, k, d] _q codes with dual distance ${d^{\bot}}$ by adding ${d^\bot}$ further columns to the parity check matrices of the smaller codes. Isomorph rejection is applied to guarantee a small search space for this iterative approach. Performing a complete search based on this observation, we are able to prove the nonexistence of linear codes for 16 open parameter sets [n, k, d] _q , q =  2, 3, 4, 5, 7, 8. These results imply 217 new upper bounds in the known tables for the minimum distance of linear codes and establish the exact value in 109 cases.     

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.     

Classes of optical orthogonal codes from arcs in root subspaces

We present new constructions for (n,w,λ) optical orthogonal codes (OOC) using techniques from finite projective geometry. In one case codewords correspond to (q-1)-arcs contained in Baer subspaces (and, in general, kth-root subspaces) of a projective space. In the other construction, we use sublines isomorphic to PG(2,q) lying in a projective plane isomorphic to PG(2,q^k), k>1. Our construction yields for each λ>1 an infinite family of OOCs which, in many cases, are asymptotically optimal with respect to the Johnson bound.     

A symmetric Roos bound for linear codes

The van Lint-Wilson AB-method yields a short proof of the Roos bound for the minimum distance of a cyclic code. We use the AB-method to obtain a different bound for the weights of a linear code. In contrast to the Roos bound, the role of the codes A and B in our bound is symmetric. We use the bound to prove the actual minimum distance for a class of dual BCH codes of length q²−1 over Fq. We give cyclic codes [63,38,16] and [65,40,16] over F₈ that are better than the known [63,38,15] and [65,40,15] codes.     

Extending MDS Codes

A q-ary (n, k)-MDS code, linear or not, satisfies n ≤ q + k − 1. A code meeting this bound is said to have maximum length. Using purely combinatorial methods we show that an MDS code with n = q + k − 2 can be uniquely extended to a maximum length code if and only if q is even. This result is best possible in the sense that there is, for example, a non-extendable 4-ary (5, 4)-MDS code. It may be that the proof of our result is as interesting as the result itself. We provide a simple necessary and sufficient condition for code extendability. In future work, this condition might be suitably modified to give an extendability condition for arbitrary (shorter) MDS codes.Received December 1, 2003     

On a Class of Traceability Codes

Traceability codes are designed to be used in schemes that protect copyrighted digital data against piracy. The main aim of this paper is to give an answer to a Staddon–Stinson–Wei's problem of the existence of traceability codes with q< w ² and b>q. We provide a large class of these codes constructed by using a new general construction method for q-ary codes.     

Multiple blocking sets in finite projective spaces and improvements to the Griesmer bound for linear codes

Belov, Logachev and Sandimirov construct linear codes of minimum distance d for roughly 1/q ^k/2 of the values of d < q ^k-1. In this article we shall prove that, for q = p prime and roughly \frac38{\frac{3}{8}}-th’s of the values of d < q ^k-1, there is no linear code meeting the Griesmer bound. This result uses Blokhuis’ theorem on the size of a t-fold blocking set in PG(2, p), p prime, which we generalise to higher dimensions. We also give more general lower bounds on the size of a t-fold blocking set in PG(δ, q), for arbitrary q and δ ≥ 3. It is known that from a linear code of dimension k with minimum distance d < q ^k-1 that meets the Griesmer bound one can construct a t-fold blocking set of PG(k−1, q). Here, we calculate explicit formulas relating t and d. Finally we show, using the generalised version of Blokhuis’ theorem, that nearly all linear codes over \mathbb F_p{{\mathbb F}_p} of dimension k with minimum distance d < q ^k-1, which meet the Griesmer bound, have codewords of weight at least d + p in subcodes, which contain codewords satisfying certain hypotheses on their supports.