טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentSilberstein Natalia
SubjectProperties of Codes in the Johnson Scheme
DepartmentDepartment of Applied Mathematics
Supervisor Professor Tuvi Etzion


Abstract

Codes which attain the sphere packing bound are called perfect codes. Perfect codes always draw the attention of coding theoreticians and mathematicians. The most important metrics in coding theory on which perfect codes are defined are the Hamming metric and the Johnson metric. While for the Hamming metric all perfect codes over finite fields are known, in the Johnson metric it was conjectured by Delsarte in 1970’s that there are no nontrivial perfect codes. The general nonexistence proof still remains the open problem.

Constant weight codes play an important role in various areas of coding theory. They serve as building blocks for general codes in the Hamming metric. One of the applications of constant weight codes is for obtaining bounds on the sizes of unrestricted codes.

In the same way as constant weight codes play a role in obtaining bounds on the size of unrestricted codes, doubly constant weight codes play an important role in obtaining bounds on the sizes of constant weight codes.

In this work we examine constant weight codes as well as doubly constant weight codes, and reduce the range of parameters in which perfect codes may exist in both cases.

We start with the constant weight codes. We introduce an improvement of Roos’ bound for 1-perfect codes, and present some new divisibility conditions, which are based on the connection between perfect codes in Johnson graph J(n,w) and block designs. Next, we consider binomial moments for perfect codes. We show which parameters can be excluded for 1-perfect codes. We examine 2-perfect codes in J(2w,w) and present necessary conditions for existence of such codes. We prove that there are no 2-perfect codes in J(2w,w) with length less then 2.5 1015.

Next we examine perfect doubly constant weight codes. We present properties of such codes that are similar to the properties of perfect codes in Johnson graph. We present a family of parameters for codes whose size of sphere divides the size of whole space. We then prove a bound on length of such codes, similarly to Roos’ bound for perfect codes in Johnson graph.

Finally we describe Steiner systems and doubly Steiner systems, which are strongly connected with the constant weight and doubly constant weight codes respectively. We provide an anticode-based proof of a bound on length of Steiner system, prove that doubly Steiner system is a diameter perfect code and present a bound on length of doubly Steiner system.