Kodlama Kuramında Lineer Programlama Sınırı

Abstract

Kodlama kuramında “bir kodun içereceği kodsözcüğü sayısı en fazla kaç olabilir?” sorusu, belki de, cevabı aranan en önemli sorudur. Bu sorudan sonra “maksimum sayıda kodsözcüğü içeren bir kod nasıl inşa edilir?” sorusu akla gelir. Bir kodun içerdiği eleman sayısına ilişkin çeşitli alt ve üst sınırlar geliştirilmeye çalışılmıştır. Bunlardan ilki 1950’de Hamming tarafından ortaya konan “Küre Paketi Sınırı”dır. Bu sınır geliştirilen ilk üst sınır olup birçok sınıra temel oluşturmaktadır. Bilinen en iyi üst sınırlar bu çalışmanın temelini oluşturan “Lineer Programlama Sınırı”nı esas alarak geliştirilmiştir. Bu nedenle bu sınır, kodlama kuramının kod sınırlarını içeren araştırma alanlarında çok önemli bir yer tutmaktadır. Philippe Delsarte, sonlu cisimler üzerinde minimum uzaklıktaki kodların içerdiği sözcük sayısı için bir sınır belirleme işlemini, bir lineer programlama problemi olarak ele almıştır. Bu teknik, bir kodun çeşitli ağırlıktaki kodsözcüklerinin sayısı ile inşa edilen ağırlık sayaçları ve Krawtchouk Polinomları’nın kuramı ile desteklenmiştir. Çalışmanın belli bölümlerinde bir kodun ağırlık sayacı ile kodun dualinin ağırlık sayacı arasındaki bağlantıyı veren MacWilliams Eşitlikleri ve Lineer Pogramlama Sınırı’nın temelini oluşturan Delsarte Teoremi açıklanmaktadır. Lineer programlama tekniklerinin, yukarıda sözü edilen konularla birleştirilmesi sonucu “LP Sınırı” ortaya çıkmıştır. Bu sınırın en verimli sonuçlar veren sınır olduğu bilinmektedir. Çalışmanın son bölümünde uygulamalarıyla bu sınır değerlendirilmektedir.

In coding theory, the question that is “how many codewords can a code contain at most?” may be the one most commonly searched. One can state another which is more general. “How can we construct the code containing maximum number of codewords for given n and d ?”. Though these questions are not solved, a large variety of lower and upper bounds were developed. The first upper bound introduced by Hamming in 1950 is called “Sphere Packing Bound”. Most of the bounds are based on this bound. The best known upper bounds are based on “the linear programming bound” which is the origin of this study. That’s why, LP Bound takes an important role in the field of researches of the bounds on codes. The process of determining a bound of a size of a code with minimum distance over finite fields was considered as a linear programming problem by Philippe Delsarte. The theory of this method includes the weight enumators and the Krawtchouk Polynomials. This study contains the idea of MacWilliams Identities which give a connection between a weight enumator of a code and a weight enumator of its dual. It also mentions about Delsarte’s Theorem that generates the Linear Programming Bound. By using the theories mentioned above and the techniques for linear programming, LP Bound has been developed. This bound is famous for its giving efficient solutions. The last chapter of this study contains the idea of the LP Bound with its applications.