Temel Kodlama Teorisi [pdf]

• Bu kitap, kodlama teorisinin temel kavramlarını ve modern gelişmelerini kapsamlı biçimde derler
• Hata düzeltme kodlarının temel ilkelerini, çeşitli kod yapılarını ve sınırlarını, ayrıca gerçek dünyadaki uygulama alanlarını ele alır
• Shannon teorisi ve Hamming kodları başta olmak üzere Reed-Solomon gibi pratikte yaygın kullanılan kodları ayrıntılı biçimde açıklar
• Hashing, grup testi, biyometrik bilgi koruma gibi modern BT sistemlerindeki uygulama örneklerini de sistematik olarak sunar
• Ekler, alıştırmalar ve kaynakça dahil edilerek hem öğrenciler hem de uygulayıcılar için etkili bir başvuru kitabı olarak yapılandırılmıştır

---

Önsöz

• Bu kitap, Venkatesan Guruswami, Atri Rudra ve Madhu Sudan'ın kodlama teorisi ders notlarına dayanır
• University of Washington, CMU, University at Buffalo SUNY, Harvard ve MIT gibi kurumlarda verilen derslerin içeriği temel alınmıştır
• NSF CAREER grant CCF-0844796 tarafından desteklenmiştir
• Yazarların görüşleri ve sonuçları, NSF'nin resmî tutumunu temsil etmez
• Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License ile kullanılabilir

İçindekiler Özeti

Bölüm 1: Temel Sorular

• Kodlama teorisinin amacı, temel tanımlar ve kodlar
• Hata düzeltme ve kod mesafesi kavramı, Hamming kodları ve sınırlar
• Kod ailelerinin sınıflandırılması ile alıştırmalar ve kaynakça

Kısım I: Temeller

• Lineer kodlar, sonlu cisimler, vektör uzayı gibi matematiksel yapıların tanıtımı
• Hamming kodlarının verimli çözümü ve dual kodların açıklanması
• Alıştırmalar ve kaynakça içerir

Bölüm 3: Olasılık ve q-ary Entropi Fonksiyonu

• Olasılık kuramının temelleri, olasılıksal yöntem ve q-ary entropi fonksiyonunun anlaşılması
• İlgili alıştırmalar ve kaynakça sunulur

Kısım II: Kombinatorik

• Hamming, Gilbert-Varshamov, Singleton, Plotkin gibi kod sınırları ve limitlerin açıklanması
• Reed-Solomon kodları, polinomlar ve sonlu cisim uygulamaları
• Shannon'un gürültü modeli ve bilgi iletiminin sınırları, Hamming ile karşılaştırma
• Liste çözme, Johnson Bound, liste çözme kapasitesi gibi genişletmeler
• Elias-Bassalygo, lineer programlama sınırları gibi yeni limit yaklaşımları

Kısım III: Çeşitli Kod Yapıları

• Polinom tabanlı kodlar ve ikili alan uygulamaları, genel kod yapıları
• Kod birleştirme (concatenation), Zyablov Bound, gelişmiş birleştirme teknikleri ve özet
• Expander grafikleri ve Expander kodları, mesafe güçlendirme ve uygulama örnekleri

Kısım IV: Algoritmalar

• Reed-Solomon, Reed-Muller ve birleştirilmiş kodlar için verimli çözme yöntemleri
• BSCp kanal kapasitesine ulaşma yöntemleri ile iç/dış kod yapıları
• Polar kodlar, Polarization ilkesi ve encoder/decoder uygulaması, liste çözme yetenekleri
• Doğrusal zamanlı kodlama ve yerel onarım yapılabilen kodların açıklanması

Kısım V: Uygulamalar

• Hashing kuramı ve çakışma önleme, neredeyse evrensel hash fonksiyonları, veri sahipliği kanıtı
• Biyometrik kimlik doğrulamada (parmak izi) koruma için Fuzzy Vault kavramı
• Grup testinin (Group Testing) formelleştirilmesi, sınırlar ve veri akışı algoritmalarındaki uygulamalar
• Kodlama problemlerinin karmaşıklığı: en yakın codeword problemi, ön işleme tabanlı çözme, yaklaşıklama, minimum mesafe problemi vb.
• Hesaplama karmaşıklığını destekleyen konular olarak iletişim karmaşıklığı, rastgeleleştirme, Pseudorandomness, Hardcore Predicates, ortalama zorluktaki problemler vb. ele alınır

Ekler

• Sembol tablosu, yararlı eşitsizlikler ve eşitlikler, asimptotik gösterim, algoritmalar ve karmaşıklık için temel arka plan
• Cebirsel algoritmalar, sonlu cisimler ve polinom işlemlerine giriş
• Bilgi teorisinin ana kavramları: entropi, koşullu entropi, karşılıklı bilgi vb. derlenir

Özellikler ve Kullanım Değeri

• Modern telekomünikasyon, veri depolama, kriptografik sistemler gibi alanlarda kritik öneme sahip hata düzeltme algoritmaları için kuramsal arka planı ve pratik uygulama yöntemlerini kapsamlı biçimde sunar
• Temel kavramlardan güncel eğilimlere ve gerçek uygulamalara kadar düzenlenmiş içeriğiyle yeni geliştiricilere, araştırmacılara ve BT profesyonellerine geniş kapsamlı bilgi aktarır
• Her bölümde alıştırmalar ve kaynakça bulunması, öğrenme ve öz yönlendirmeli çalışma açısından avantaj sağlar
• Creative Commons lisansı kapsamında akademik ve ticari olmayan amaçlarla serbestçe kullanılabilir

[GN⁺]

Hacker News görüşü

• Claude Shannon'ın "The Mathematical Theory of Communication" eserinin, derin bir matematik altyapısı olmadan da herkesin okuyabileceği kadar anlaşılır anlatılmış, bilgi teorisinin temel metni olduğunu vurgulamak isterim bağlantı

  • Shannon'ın matematiksel düşünme biçimine başlamak için gerçekten çok iyi bir isim olduğunu söylemek isterim. Bilgi entropisi kavramını ilk başta herhangi bir anlam yüklemeden, yalnızca gerekli özelliklerden yola çıkarak türetti. Şaşırtıcı olan, bu şekilde adeta tesadüfen oluşturulan tanımın fizikteki termodinamik entropiyle neredeyse çakışmasıdır; bunu fark edip adını veren de Von Neumann'dı. Matematik çoğu zaman "bu kuralları sağlaması gerekiyorsa" diye başlayan mantıksal bir ilerleyiş izler; birçok kişinin onu zor bulmasının nedenlerinden biri de budur. Shannon'ın makalesi yalnızca kodlama teorisinin iskeletini kurdu, gerçek uygulama ayrıntıları makalede yer almıyor. Ben geçmişte bir startup'ta bu makalenin kitaplaştırılmış sürümünü birlikte okuduğumuz bir kitap kulübü yürütmüştüm; bilgi teorisini ve genel olarak matematiği anlamak açısından gerçekten çok iyi bir deneyimdi, tavsiye ederim

• Kayıpsız sıkıştırma alanı üretken yapay zeka ile yakından ilişkili olduğu için biraz daha içerik eklenirse ilginç olabilir. Kayıpsız sıkıştırma ile makine öğrenmesi arasındaki bağlantıyı iyi tanıtan bir doktora tezini önermek isterim bağlantı

  • Bunu illa kayıpsız sıkıştırma ile sınırlamak da gerekmiyor. Aslında neredeyse tüm makine öğrenmesi bir tür sıkıştırma, çoğunlukla da kayıplı sıkıştırma, olarak anlaşılabilir. Örneğin yalnızca semantik embedding'leri kanaldan gönderirseniz, gerçek metnin tamamı olmasa bile embedding değerlerinin içinde işi yapmaya yetecek kadar bilgi bulunur. Veri sınıflandırma da sonuçta, veriden yalnızca genel kategorilerin örtük temsilini bırakıp geri kalanını atma sürecidir. Üretken yapay zekada ise tam da 'kayıplı sıkıştırma' yaptığımız için sistemler iyi çalışır. Bilgiyi bilerek atıp aradaki boşlukların çıkarımla doldurulmasını gerektirmek, genelleme için yolu açar. Kayıpsız bir LLM pratik kullanım açısından aslında pek ilgi çekici değildir. Yine de önerdiğim makale, makine öğrenmesi alanında nadir görülen biçimde kayıpsız sıkıştırmayı ele aldığı için oldukça özeldir

• Yakın zamanda hazırlanmış iyi bir kaynak olarak <i>Information Theory: From Coding to Learning</i> adlı bir ders kitabı var. Çevrimiçi PDF sürümü de mevcut, bakmak faydalı olabilir bağlantı

  • David MacKay'in <i>Information Theory, Inference, and Learning Algorithms</i> kitabını da önermek isterim bağlantı

• "Coding"in burada ne anlama geldiğini soranlara yanıt olarak, buradaki coding, bilginin bir gösterimden başka bir gösterime dönüştürüldüğü encoding/decoding işlemlerini ifade eder. Bu tür sistemlere code denir ve bilgi aktarımı sırasında girişime, bozulmaya veya dinlenmeye karşı dayanıklı olacak şekilde tasarlanırlar. Yani coding, veri sıkıştırma, şifreleme, hata tespiti ve düzeltme, veri iletimi ve depolama gibi birçok alanda kullanılır bağlantı

  • Özellikle bahsi geçen kitap, error correcting code konusuna odaklanıyor. Mesaj iletilirken kaybolan kısımların geri kazanılabilmesi için ek veri eklenir. Çözülmesi gereken zorluk, en az ek yük ve makul hesaplama süresi içinde yeterli hatayı düzeltebilecek ek veriyi tasarlamaktır. Bu tür teknikler WiFi, sabit diskler, QR kodları ve RAM gibi son derece farklı alanlarda gerçekten kullanılıyor. Örneğin ECC RAM'deki ECC tam olarak error correcting code anlamına gelir. Son dönemde DDR5'te kısmen zorunlu hale gelmiş bir teknolojidir

• CS alanında ücretsiz e-kitap paylaşma havası varken, Jeff E.'nin Algorithms kitabını da güçlü biçimde tavsiye etmek isterim. Algoritma öğrenen ya da bilgisini tazelemek isteyen herkes için mutlaka okunması gereken bir kitaptır bağlantı

• Bu kitabın birkaç bölümünü okudum ve gerçekten çok memnunum. Önümüzdeki birkaç hafta, belki birkaç ay boyunca yavaş yavaş okumayı planlıyorum

• Bilgi teorisi ve kodlama teorisini daha derinlemesine çalışmak istiyorsanız, şu kaynakları da önermek isterim. Error correcting code için "W. Wesley Peterson ve E. J. Weldon, Jr.'ın Error-Correcting Codes"; soyut cebir, özellikle cisim teorisi, içinse "Oscar Zariski ve Pierre Samuel'in Commutative Algebra" faydalı olabilir

  • LaTeX komutları burada çalışmıyor

• Başlangıç seviyesindekilere önermek isteyeceğim birkaç kitap şunlar:

  1. John R. Pierce'ın <i>An Introduction to Information Theory, Symbols, Signals and Noise</i> - kavramları anlamak ve sezgi geliştirmek için iyi bir klasik. Aynı yazarın diğer kitapları da harika
  2. James V. Stone'un <i>Information Theory: A Tutorial Introduction</i> - kolay okunan ve iyi bir giriş kitabı. Yazarın yazdığı diğer tutorial'lar da faydalı
  3. Stefan Moser ve Po-ning chen'in <i>A Student's Guide to Coding and Information Theory</i> - kısa ve açık bir rehber; aynı serideki diğer kitaplar da önerilmeye değer

• Biri ne zaman "bu zorunlu" dese, bölümde ilgili konuyu sadece hafifçe tatmış biri olarak benim için bu her zaman biraz ürkütücü bir an oluyor

  • Bu dersteki 'zorunlu' ifadesi, tüm bilgisayar mühendisliği öğrencilerinin mutlaka bilmesi gereken bir içerikten çok, kodlama teorisinin özünü taşıdığı anlamına geliyor. Kitabın ortak yazarlarından biri bizim okulda bu dersi bizzat veriyor ve bu ders matematiksel içeriği ezici derecede yoğun olan ileri seviye bir seçmeli ders. Dört yıllık bilgisayar bilimi programında çoğunlukla son sınıftaki çok az sayıda öğrenci alıyor; çevremde bu dersi alan arkadaşlarımın hepsi matematiksel ispatları seven kişilerdi. Dersi de sevdiler

  • Üzerinde "zorunlu" ya da "giriş" yazıyorsa, sizi oldukça yoğun bir ders kitabının beklediğinin habercisidir