Weighted perfect codes in Lee metric

In this talk, we will present results about perfect weighted coverings of radius 1 in the Lee metric. Weighted coverings are a very natural generalization of many classes of codes. Perfect weighted coverings are well studied in the Hamming metric, but also in other contexts with different names, such as regular-sets, multiple coverings or [a, b]-dominating sets. In this talk, we present results of existence as well as of non-existence for perfect weighted coverings of radius one on the multidimensional grid graphs.     

Relative generalized Hamming weights of cyclic codes

Relative generalized Hamming weights (RGHWs) of a linear code with respect to a linear subcode determine the security of the linear ramp secret sharing scheme based on the linear codes. They can be used to express the information leakage of the secret when some keepers of shares are corrupted. Cyclic codes are an interesting type of linear codes and have wide applications in communication and storage systems. In this paper, we investigate the RGHWs of cyclic codes of two nonzeros with respect to its irreducible cyclic subcodes. We give two formulae for RGHWs of the cyclic codes. As applications of the formulae, explicit examples are computed. Moreover, RGHWs of cyclic codes in the examples are very large, comparing with the generalized Plotkin bound of RGHWs. So it guarantees very high security for the secret sharing scheme based on the dual codes.     

Non-binary irreducible quasi-cyclic parity-check subcodes of Goppa codes and extended Goppa codes

Designs, Codes and Cryptography - In this paper, we construct a family of non-binary irreducible quasi-cyclic parity-check subcodes of Goppa codes and extended Goppa codes. Moreover, we present a...     

Roos bound for skew cyclic codes in Hamming and rank metric

In this paper, a Roos like bound on the minimum distance for skew cyclic codes over a general field is provided. The result holds in the Hamming metric and in the rank metric. The proofs involve arithmetic properties of skew polynomials and an analysis of the rank of parity-check matrices. For the rank metric case, a way to arithmetically construct codes with a prescribed minimum rank distance, using the skew Roos bound, is also given. Moreover, some examples of MDS codes and MRD codes over finite fields are built, using the skew Roos bound.     

A generalized floor bound for the minimum distance of geometric Goppa codes

We prove a new bound for the minimum distance of geometric Goppa codes that generalizes two previous improved bounds. We include examples of the bound applied to one- and two-point codes over certain Suzuki and Hermitian curves.     

A generalized hypergreedy algorithm for weighted perfect matching

We give a generalization of the hypergreedy algorithm for minimum weight perfect matching on a complete edge weighted graph whose weights satisfy the triangle inequality. With a modified version of this algorithm we obtain a logn-approximate perfect matching heuristic for points in the Euclidean plane, inO(n log² n) time.This research was supported in part by the DIMACS Grant No. NSF-STC88-09648.This research was supported in part by the NSF under Grant No. CCR 88-07518.     

A necessary condition for the existence of perfect codes in Lie metric

A theorem of Lloyd is extended to the Lie metric case.     

Intersection of Hamming codes avoiding Hamming subcodes

We prove that given a binary Hamming code \({{\mathcal{H}}^n}\) of length n = 2 ^m ? 1, m ≥ 3, or equivalently a projective geometry PG(m ? 1, 2), there exist permutations \({\pi \in \mathcal{S}_n}\) , such that \({{\mathcal{H}}^n}\) and \({\pi({\mathcal{H}}^n)}\) do not have any Hamming subcode with the same support, or equivalently the corresponding projective geometries do not have any common flat. The introduced permutations are called AF permutations. We study some properties of these permutations and their relation with the well known APN functions.     

The relative generalized Hamming weight of linear q-ary codes and their subcodes

In this article, some properties of the relative generalized Hamming weight (RGHW) of linear codes and their subcodes are developed with techniques in finite projective geometry. The relative generalized Hamming weights of almost all 4-dimensional q-ary linear codes and their subcodes are determined.      

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.     

Weight distributions of geometric Goppa codes

The in general hard problem of computing weight distributions of linear codes is considered for the special class of algebraic-geometric codes, defined by Goppa in the early eighties. Known results restrict to codes from elliptic curves. We obtain results for curves of higher genus by expressing the weight distributions in terms of -series. The results include general properties of weight distributions, a method to describe and compute weight distributions, and worked out examples for curves of genus two and three.

     

The second generalized Hamming weight for two-point codes on a Hermitian curve

The aim of this article is the determination of the second generalized Hamming weight of any two-point code on a Hermitian curve of degree q + 1. The determination involves results of Coppens on base-point-free pencils on a plane curve. To avoid non- essential trouble, we assume that q > 4.      

On automorphism groups of certain Goppa codes

Goppa codes are linear codes arising from algebraic curves over finite fields. Sufficient conditions are given ensuring that all automorphisms of a Goppa code are inherited from the automorphism group of the curve. In some cases, these conditions are also necessary. The cases of curves with large automorphism groups, notably the Hermitian and the Deligne-Lusztig curves, are investigated in detail. This research was performed within the activity of GNSAGA of the Italian INDAM, with the financial support of the Italian Ministry MIUR, project “Strutture geometriche, combinatorica e loro applicazioni”, PRIN 2006–2007.     

Kernels of nonlinear Hamming codes

Given a binary code,C, of lengthn, thekernel of the code is defined to be the set of all vectors which leave the code invariant under translation. Throughout this paper, various properties of kernels will be considered. However, the main idea of this paper is to show the necessary and sufficient conditions for the existence of kernels of all possible sizes for nonlinear perfect binary codes.     

Hamming weights in irreducible cyclic codes

The objectives of this paper are to survey and extend earlier results on the weight distributions of irreducible cyclic codes, present a divisibility theorem and develop bounds on the weights in irreducible cyclic codes.