Weighted Hamming metric structures

It is known that the binary generalized Goppa codes are perfect codes for the weighted Hamming metrics. In this paper, we present the existence of a weighted Hamming metric that admits a binary Hamming code (resp. an extended binary Hamming code) to be perfect code. For a special weighted Hamming metric, we also give some structures of a 2-perfect code, show how to construct a 2-perfect linear code and obtain the weight distribution of a 2-perfect code from the partial information of the code.     

Perfect codes from the dual point of view I

The two concepts dual code and parity check matrix for a linear perfect 1-error correcting binary code are generalized to the case of non-linear perfect codes. We show how this generalization can be used to enumerate some particular classes of perfect 1-error correcting binary codes. We also use it to give an answer to a problem of Avgustinovich: whether or not the kernel of every perfect 1-error correcting binary code is always contained in some Hamming code.     

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.     

Construction of binary LCD codes,ternary LCD codes and quaternary Hermitian LCD codes

We give two methods for constructing many linear complementary dual (LCD for short) codes from a given LCD code, by modifying some known methods for constructing self-dual codes. Using the methods, we construct binary LCD codes and quaternary Hermitian LCD codes, which improve the previously known lower bounds on the largest minimum weights.

     

张量积码的多重覆盖半径

码的多重覆盖半径是最近对码的通常覆盖半径的一个推广．本文研究了由两个二元线性码构成的张量积码的多重覆盖半径．并得到了该张量积码的多重覆盖半径的界．     

Some Hadamard matrices of order 32 and their binary codes

It is known that all doubly‐even self‐dual codes of lengths 8 or 16, and the extended Golay code, can be constructed from some binary Hadamard matrix of orders 8, 16, and 24, respectively. In this note, we demonstrate that every extremal doubly‐even self‐dual [32,16,8] code can be constructed from some binary Hadamard matrix of order 32. © 2004 Wiley Periodicals, Inc.     

Code generator matrices as RNG conditioners

We quantify precisely the distribution of the output of a binary random number generator (RNG) after conditioning with a binary linear code generator matrix by showing the connection between the Walsh spectrum of the resulting random variable and the weight distribution of the code. Previously known bounds on the performance of linear binary codes as entropy extractors can be derived by considering generator matrices as a selector of a subset of that spectrum. We also extend this framework to the case of non-binary codes.     

An improvement of the Griesmer bound for some small minimum distances

In this paper we give some lower and upper bounds for the smallest length n(k, d) of a binary linear code with dimension k and minimum distance d. The lower bounds improve the known ones for small d. In the last section we summarize what we know about n(8, d).     

Construction of binary and ternary self-orthogonal linear codes

We construct new binary and ternary self-orthogonal linear codes. In order to do this we use an equivalence between the existence of a self-orthogonal linear code with a prescribed minimum distance and the existence of a solution of a certain system of Diophantine linear equations. To reduce the size of the system of equations we restrict the search for solutions to solutions with special symmetry given by matrix groups. Using this method we found at least six new distance-optimal codes, which are all self-orthogonal.     

Construction of a (64, 2 37, 12) Code via Galois Rings

Certain nonlinear binary codes contain more codewords than any comparable linear code presently known. These include the Kerdock and Preparata codes, which exist for all lengths 4^m 16. At length 16 they coincide to give the Nordstrom-Robinson code. This paper constructs a nonlinear (64, 2₃₇, 12) code as the binary image, under the Gray map, of an extended cyclic code defined over the integers modulo 4 using Galois rings. The Nordstrom-Robinson code is defined in this same way, and like the Nordstrom-Robinson code, the new code is better than any linear code that is presently known.     

Self‐Dual Codes and the Nonexistence of a Quasi‐Symmetric 2‐(37,9,8) Design with Intersection Numbers 1 and 3

We prove that a certain binary linear code associated with the incidence matrix of a quasi‐symmetric 2‐(37, 9, 8) design with intersection numbers 1 and 3 must be contained in an extremal doubly even self‐dual code of length 40. Using the classification of extremal doubly even self‐dual codes of length 40, we show that a quasi‐symmetric 2‐(37, 9, 8) design with intersection numbers 1 and 3 does not exist.     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.     

Generating 2-Gray codes for ballot sequences in constant amortized time

We present a simple algorithm that generates a cyclic 2-Gray code for ballot sequences. The algorithm generates each ballot sequence in constant amortized time using a linear amount of space. This is the first known cyclic 2-Gray code for ballot sequences that achieves this time bound. In addition, the algorithm can be easily modified to output ballot sequences in binary reflected Gray code order in constant amortized time per string using a linear amount of space.     

Construction of Extremal Type II Codes over ℤ4

In this paper, we give a pseudo-random method to construct extremal Type II codes overℤ₄ . As an application, we give a number of new extremal Type II codes of lengths 24, 32 and 40, constructed from some extremal doubly-even self-dual binary codes. The extremal Type II codes of length 24 have the property that the supports of the codewords of Hamming weight 10 form 5−(24,10,36) designs. It is also shown that every extremal doubly-even self-dual binary code of length 32 can be considered as the residual code of an extremal Type II code over ℤ₄.     

An Enumeration of Binary Self-Dual Codes of Length 32

A binary self-dual code of length 2k is a (2k, k) binary linear code C with the property that every pair of codewords in C are orthogonal. Two self-dual codes, C ₁ and C ₂, are equivalent if and only if there is a permutation of the coordinates of C ₁ that takes C ₁ into C ₂. The automorphism group of a binary code C is the set of all permutations of the coordinates of C that takes C into itself.The main topic of this paper is the enumeration of inequivalent binary self-dual codes. We have developed algorithms that will take lists of inequivalent small codes and produce lists of larger codes where each inequivalent code occurs only a few times. We have defined a canonical form for codes that allowed us to eliminate the overenumeration. So we have lists of inequivalent binary self-dual codes of length up to 32. The enumeration of the length 32 codes is new. Our algorithm also finds the size of the automorphism group so that we can compute the number of distinct binary self-dual codes for a specific length. This number can also be found by counting and matches our total.     

Edge local complementation and equivalence of binary linear codes

Orbits of graphs under the operation edge local complementation (ELC) are defined. We show that the ELC orbit of a bipartite graph corresponds to the equivalence class of a binary linear code. The information sets and the minimum distance of a code can be derived from the corresponding ELC orbit. By extending earlier results on local complementation (LC) orbits, we classify the ELC orbits of all graphs on up to 12 vertices. We also give a new method for classifying binary linear codes, with running time comparable to the best known algorithm.     

Weight distributions and weight hierarchies of two classes of binary linear codes

Linear codes with a few weights can be applied to communication, consumer electronics and data storage system. In addition, the weight hierarchy of a linear code has many applications such as on the type II wire-tap channel, dealing with t-resilient functions and trellis or branch complexity of linear codes and so on. In this paper, we present a formula for computing the weight hierarchies of linear codes constructed by the generalized method of defining sets. Then, we construct two classes of binary linear codes with a few weights and determine their weight distributions and weight hierarchies completely. Some codes of them can be used in secret sharing schemes.     

On binary linear <Emphasis Type="Italic">r</Emphasis>-identifying codes

A subspace C of the binary Hamming space F ⁿ of length n is called a linear r-identifying code if for all vectors of F ⁿ the intersections of C and closed r-radius neighbourhoods are nonempty and different. In this paper, we give lower bounds for such linear codes. For radius r =  2, we give some general constructions. We give many (optimal) constructions which were found by a computer search. New constructions improve some previously known upper bounds for r-identifying codes in the case where linearity is not assumed.     

Improved decoding of affine-variety codes

General error locator polynomials are polynomials able to decode any correctable syndrome for a given linear code. Such polynomials are known to exist for all cyclic codes and for a large class of linear codes. We provide some decoding techniques for affine-variety codes using some multidimensional extensions of general error locator polynomials. We prove the existence of such polynomials for any correctable affine-variety code and hence for any linear code. We propose two main different approaches, that depend on the underlying geometry. We compute some interesting cases, including Hermitian codes. To prove our coding theory results, we develop a theory for special classes of zero-dimensional ideals, that can be considered generalizations of stratified ideals. Our improvement with respect to stratified ideals is twofold: we generalize from one variable to many variables and we introduce points with multiplicities.