Kodlama kuramında lineer programlama sınırı
The linear programming bound in coding theory
Yazar: GÖZDE ŞARKBÜLBÜLÜ
Danışman: PROF.DR. EROL BALKANAY ; Y.DOÇ.DR. RECEP KORKMAZ
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Ana Bilim Dalı
Derece: Yüksek Lisans, 2006
Konu: Matematik = Mathematics

Özet:
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 ?maksimumsayıda kodsözcüğü içeren bir kod nasıl inşa edilir?? sorusu akla gelir. Bir kodun içerdiğieleman sayısına ilişkin çeşitli alt ve üst sınırlar geliştirilmeye çalışılmıştır. Bunlardan ilki1950'de Hamming tarafından ortaya konan ?Küre Paketi Sınırı?dır. Bu sınır geliştirilenilk ü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 ProgramlamaSınırı?nı esas alarak geliştirilmiştir. Bu nedenle bu sınır, kodlama kuramının kodsı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üksayısı için bir sınır belirleme işlemini, bir lineer programlama problemi olarak elealmıştır. Bu teknik, bir kodun çeşitli ağırlıktaki kodsözcüklerinin sayısı ile inşa edilenağı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ıntemelini oluşturan Delsarte Teoremi açıklanmaktadır. Lineer programlamatekniklerinin, 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ınson bölümünde uygulamalarıyla bu sınır değerlendirilmektedir.Anahtar Kelimeler: Kod, lineer kodlar, sonlu cisimler, ağırlık sayaçları, KrawtchoukPolinomu, MacWilliams Eşitlikleri, Delsarte Teoremi, lineer programlama sınırı.

Abstract:
In coding theory, the question that is ?how many codewords can a code contain atmost?? may be the one most commonly searched. One can state another which is moregeneral. ?How can we construct the code containing maximum number of codewords forgiven n and d ??. Though these questions are not solved, a large variety of lower andupper bounds were developed. The first upper bound introduced by Hamming in 1950 iscalled ?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 isthe origin of this study. That?s why, LP Bound takes an important role in the field ofresearches of the bounds on codes.The process of determining a bound of a size of a code with minimum distance overfinite fields was considered as a linear programming problem by Philippe Delsarte. Thetheory of this method includes the weight enumators and the Krawtchouk Polynomials.This study contains the idea of MacWilliams Identities which give a connection betweena weight enumator of a code and a weight enumator of its dual. It also mentions aboutDelsarte?s Theorem that generates the Linear Programming Bound. By using thetheories mentioned above and the techniques for linear programming, LP Bound hasbeen developed. This bound is famous for its giving efficient solutions. The last chapterof this study contains the idea of the LP Bound with its applications.Keywords: Code, linear codes, finite fields, weight enumerators, KrawtchoukPolynomials, MacWilliams Identities, Delsarte?s Theorem, linear programming bound.