Ph.D Thesis

Ph.D StudentMounits Beniamin
SubjectBounds on Sizes of Nonlinear Codes
DepartmentDepartment 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.