Ph.D Thesis | |

Ph.D Student | Mounits Beniamin |
---|---|

Subject | Bounds on Sizes of Nonlinear Codes |

Department | Department of Applied Mathematics |

Supervisor | PROF. Tuvi Etzion |

Let *A(n,d)*
denote the maximum number of codewords in a binary code of length *n* and
minimum Hamming distance *d*. The main goal of this work is to find new
upper and lower bounds on *A(n,d)* which are better than the best known
bounds.

We start by
considering analytic upper bounds on sizes of codes. We examine upper bounds on
*A(n,d)* as a special case of upper bounds on the size of subsets in a
metric association scheme. We obtain new analytic upper bounds on sizes of
codes which depend on the distance distribution of the code. By upper bounding
distance distribution coefficients by means of bounds on constant weight codes,
we obtain a new bound which improves on the Johnson upper bound for unrestricted
codes which is the best known analytic upper bound for fixed *d* and large
values of *n*.

We continue by
considering Delsarte's linear programming bound. First, we strengthen some of
the Best's constraints on the distance distribution coefficients. This leads to
new record upper bounds on *A(n,d)* for small lengths. After that we consider
a polynomial approach which is equivalent to the Delsarte's bound. Finally, we
use linear programming to obtain upper bounds on combinations of distance
distribution coefficients from the analytic upper bounds derived via association
schemes for the case *d=3*. This leads to some new analytic upper bounds
on *A(n,3)* which improve on the best known bounds. The approach which we
developed can be applied to any metric association scheme. In addition to the
Hamming scheme we consider the Johnson scheme and obtain some new upper bounds
for constant weight codes.

Next, we turn our
attention to lower bounds on *A(n,3)*. A new construction is given that
uses the weight distribution of linear nonbinary Hamming code over *GF(q)*
to form a nonlinear binary single-error correcting codes.

Finally, we consider quasi-perfect codes with Hamming distance 4 and 5 and covering radius 2 and 3, respectively. Using the Blockwise Direct Sum construction we improve in some cases on the best known bounds on the length of the shortest and longest binary quasi-perfect codes with a given Hamming distance, covering radius, and redundancy. New family of asymptotically perfect codes is obtained with minimum distance 4 and covering radius 2. For quasi-perfect codes with distance 5 and covering radius 3 we give new recursive construction which extends significantly the range of lengths of known such codes.