Existence of Perfect 4-Deletion-Correcting Codes with Length Six

By a T ^*(2, k, v)-code we mean a perfect4-deletion-correcting code of length 6 over an alphabet of size v, which is capable of correcting anycombination of up to 4 deletions and/or insertions of letters that occur in transmission of codewords. Thethird author (DCC Vol. 23, No. 1) presented a combinatorial construction for such codes and prove thata T ^*(2, 6, v)-code exists for all positive integers v 3 (mod 5), with 12 possible exceptions of v. In this paper, the notion of a directedgroup divisible quasidesign is introduced and used to show that a T ^*(2, 6,v)-code exists for all positive integers v 3 (mod 5), except possiblyfor v {173, 178, 203, 208}. The 12 missing cases for T ^*(2,6, v)-codes with v 3 (mod 5) are also provided, thereby the existenceproblem for T ^*(2, 6, v)-codes is almost complete.     

Switching Equivalence Classes of Perfect Codes

The authors present a 1-error correcting perfect code of length 15 and show that it is not switching equivalent to the Hamming code thereby settling a question of Avgustinovich and Solov'evaas96     

On Perfect Ternary Constant Weight Codes

We consider the space of ternary words of length n and fixed weight w with the usual Hamming distance. A sequence of perfect single error correcting codes in this space is constructed. We prove the nonexistence of such codes with other parameters than those of the sequence.     

Linear Perfect Codes and a Characterization of the Classical Designs

A new definition for the dimension of a combinatorial t-(v,k,) design over a finite field is proposed. The complementary designs of the hyperplanes in a finite projective or affine geometry, and the finite Desarguesian planes in particular, are characterized as the unique (up to isomorphism) designs with the given parameters and minimum dimension. This generalizes a well-known characterization of the binary hyperplane designs in terms of their minimum 2-rank. The proof utilizes the q-ary analogue of the Hamming code, and a group-theoretic characterization of the classical designs.     

混合长度为{4,5,6}的完备删位纠错码的存在性

依据刻画空间中向量间距离方式的不同,可定义不同的纠错码.Levenshtein定义了莱文斯坦距离,由此定义了删位纠错码.本文借助组合设计理论中的成对平衡设计以及初等数论的方法和技巧,给出参数为T{2,{4,5,6},v}的完备删位纠错码存在的两个必要条件,并确定了,当v≥4且v■{8,9,14}时,存在参数为T{2,{4,5,6},v}的完备删位纠错码.     

The Classification of Some Perfect Codes

Perfect 1-error correcting codes C in Z ₂ ⁿ , where n=2 ^m–1, are considered. Let ; denote the linear span of the words of C and let the rank of C be the dimension of the vector space . It is shown that if the rank of C is n–m+2 then C is equivalent to a code given by a construction of Phelps. These codes are, in case of rank n–m+2, described by a Hamming code H and a set of MDS-codes D _h , h H, over an alphabet with four symbols. The case of rank n–m+1 is much simpler: Any such code is a Vasil'ev code.     

On the Characterization of Linear Uniquely Decodable Codes

A Uniquely Decodable (UD) Code is a code such that any vector of the ambient space has a unique closest codeword. In this paper we begin a study of the structure of UD codes and identify perfect subcodes. In particular we determine all linear UD codes of covering radius 2.     

On Perfect Codes: Rank and Kernel

We establish upper and lower bounds on the rank and the dimension of the kernel of perfect binary codes. We also establish some results on the structure of perfect codes.     

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.     

Perfect 2-colorings of a hypercube

A coloring of the vertices of a graph is called perfect if the multiset of colors of all neighbors of a vertex depends only on its own color. We study the possible parameters of perfect 2-colorings of the n-dimensional cube. Some necessary conditions are obtained for existence of such colorings. A new recursive construction of such colorings is found, which produces colorings for all known and infinitely many new parameter sets.     

Three Constructions of Authentication Codes with Perfect Secrecy

In this paper, we present three algebraic constructions of authentication codes with secrecy. The first and the third class are optimal. Some of the codes in the second class are optimal, and others in the second class are asymptotically optimal. All authentication codes in the three classes provide perfect secrecy.     

Existence of T*(3, 4,v)‐codes

A word of length k over an alphabet Q of size v is a vector of length k with coordinates taken from Q. Let Q^*₄ be the set of all words of length 4 over Q. A T^*(3, 4, v)‐code over Q is a subset C^*? Q^*₄ such that every word of length 3 over Q occurs as a subword in exactly one word of C^*. Levenshtein has proved that a T^*(3, 4, vv)‐code exists for all even v. In this paper, the notion of a generalized candelabra t‐system is introduced and used to show that a T^*(3, 4, v)‐code exists for all odd v. Combining this with Levenshtein's result, the existence problem for a T^*(3,4, v)‐code is solved completely. © 2004 Wiley Periodicals, Inc. J Combin Designs 13: 42–53, 2005.     

Note on Perfect Forests in Digraphs

A spanning subgraph F of a graph G is called perfect if F is a forest, the degree of each vertex x in F is odd, and each tree of F is an induced subgraph of G. Alex Scott (Graphs Combin 17 (2001), 539–553) proved that every connected graph G contains a perfect forest if and only if G has an even number of vertices. We consider four generalizations to directed graphs of the concept of a perfect forest. While the problem of existence of the most straightforward one is NP‐hard, for the three others this problem is polynomial‐time solvable. Moreover, every digraph with only one strong component contains a directed forest of each of these three generalization types. One of our results extends Scott's theorem to digraphs in a nontrivial way.     

A Partition of the Hypercube into Maximally Nonparallel Hamming Codes

By using the Gold map, we construct a partition of the hypercube into cosets of Hamming codes such that for every two cosets the corresponding Hamming codes are maximally nonparallel, that is, their intersection cardinality is as small as possible to admit nonintersecting cosets.     

Ranks of q-Ary 1-Perfect Codes

The rank of a q-ary code C of length n, r(C), isthe dimension of the subspace spanned by C. We establish the existence of q-ary 1-perfectcodes of length for m 4 and r(C)= n – m + s for each s {1,,m}. This is a generalization of the binary case proved by Etzion and Vardy in[4].     

New Constructions for IPP Codes

Identifiable parent property (IPP) codes are introduced to provide protection against illegal producing of copyrighted digital material. In this paper we consider explicit construction methods for IPP codes by means of recursion techniques. The first method directly constructs IPP codes, whereas the second constructs perfect hash families that are then used to derive IPP codes. In fact, the first construction provides an infinite class of IPP codes having the best known asymptotic behavior. We also prove that this class has a traitor tracing algorithm with a runtime of O(M) in general, where M is the number of codewords.     

A New Class of Optimal 3-splitting Authentication Codes

The necessary condition for the existence of a (ν, 3× 3,1)-splitting BIBD is ν ≡ 1 (mod 54). In this paper, we show that the necessary condition is also sufficient with one possible exception of ν = 55. As its application, we obtain a new infinite class of optimal 3-splitting authentication codes. AMS Classification: 05B05, 94A62 An erratum to this article is available at .     

On Balanced Optimal Optical Orthogonal Codes

Variable‐weight optical orthogonal codes (OOCs) were introduced by G.‐C. Yang for multimedia optical CDMA systems with multiple quality of service (QoS) requirement. In this paper, by using incomplete difference matrices and perfect relative difference families, a balanced ‐OOC is obtained for every positive integer .     

Computing Linear Codes and Unitals

The 2-rank of any 2-(28,4,1) design (unital on 28 points) is known to be between 19 and 27. It is shown by the enumeration and analysis of certain binary linear codes that there are no unitals of 2-rank 20, and that there are exactly 4 isomorphism classes of unitals of 2-rank 21. Combined with previous results, this completes the classification of unitals on 28 points of 2-rank less than 22.