Bounds on the size of codes

Thumbnail Image

Publication or External Link






In this dissertation we determine new bounds and properties of codes in

three different finite metric spaces, namely the ordered Hamming space, the

binary Hamming space, and the Johnson space.

The ordered Hamming space is a generalization of the Hamming space that

arises in several different problems of coding theory and numerical

integration. Structural properties of this space are well described in the

framework of Delsarte's theory of association schemes. Relying on this

theory, we perform a detailed study of polynomials related to the ordered

Hamming space and derive new asymptotic bounds on the size of codes in this

space which improve upon the estimates known earlier.

A related project concerns linear codes in the ordered Hamming space. We

define and analyze a class of near-optimal codes, called near-Maximum

Distance Separable codes. We determine the weight distribution and provide

constructions of such codes. Codes in the ordered Hamming space are dual to

a certain type of point distributions in the unit cube used in numerical

integration. We show that near-Maximum Distance Separable codes are

equivalently represented as certain near-optimal point distributions.

In the third part of our study we derive a new upper bound on the size of

a family of subsets of a finite set with restricted pairwise intersections,

which improves upon the well-known Frankl-Wilson upper bound. The new bound

is obtained by analyzing a refinement of the association scheme of the

Hamming space (the Terwilliger algebra) and intertwining functions of the

symmetric group.

Finally, in the fourth set of problems we determine new estimates on the

size of codes in the Johnson space. We also suggest a new approach to the

derivation of the well-known Johnson bound for codes in this space. Our

estimates are often valid in the region where the Johnson bound is vacuous.

We show that these methods are also applicable to the case of multiple

packings in the Hamming space (list-decodable codes). In this context we

recover the best known estimate on the size of list-decodable codes in

a new way.