Sıkıştırma Kodları

Sıkıştırma Kodları Bilgiyi, mesela bir resmi dijital olarak temsil etmek için, onu küçük parçalara ayırmamız gerekir. Böylece resmi renk sembollerinden oluşan bir dizi olarak gönderebiliriz. Ve her bir renk, bir kod vasıtasıyla birer sayı olarak ifade edilebilir. Şu problemi bir düşünün. Melis ve Haluk ikilik sistemde iletiler alıp gönderebiliyor. Ve sistemlerini kullanmak isteyen müşterilerinden bit başına 1 Kuruş talep ediyorlar. Bir ileti göndermek isteyen sıradan bir müşteri geliyor. Mesala 1000 sembol uzunluğunda. Mesajın anlamıysa kesinlikle bilinmiyor. Normal şartlarda bu mesaj, 2 bitlik standart kodla gönderilir. O da 2000 bit'lik bir ücretlendirme gerektirir. Fakat Melis ve Haluk müşteriyi önceden araştırmış ve iletideki her sembolün olasılığının farklı olduğu kanaatine varmıştır. Bu bilinen olasılıkları kullanarak iletiyi sıkıştırmaları, böylece kârlarını arttırmaları mümkün müdür? En uygun kodlama stratejisi nedir? En uygun kodlama stratejisini dünyaya kazandıran kişi 1952 tarihli meşhur makalesiyle David Huffman'dır. Fikir, en alttan başlayarak yukarı doğru oluşturulan ikilik bir ağaca dayanıyordu. Başlarken, tüm sembolleri en altta sıralıyoruz. Bunlara "düğüm" diyoruz. Sonra da olasılığı en düşük olan düğümleri buluyoruz. Yani bu durumda B ve C. Sonra bu ikisini tek bir düğümde birleştiriyor ve olasılıklarını topluyoruz. Ardından, en düşük olasılıklı iki düğümle işlemi tekrarlıyoruz. En tepede tek bir düğüm kalana dek birleştirmeye devam ediyoruz. Son olarak, ağacın dallarını herhangi bir sıralamayla 0 veya 1 olarak isimlendiriyoruz. Artık, her harfin kodu ağacın en tepesinden o harfe kadar uzanan yoldur. Mesela A'nın kodu, tek bir daldan ibarettir. Ki o da 1. Buna Huffman kodu adı verilir. Ve inceleyeceğimiz örnekler için Huffman kodlamasından daha iyisi yoktur. İsterseniz deneyin. Mesela D'nin kodunu tek bir 0'a indirgerseniz "011" şeklindeki bir mesaj DAA anlamına gelebileceği gibi sadece B anlamına da gelebilir. Dolayısıyla böyle bir kısaltmanın işe yaraması için harf aralıklarından faydalanmanız gerekir ki bu, iletim sırasındaki tüm tasarrufu çöpe atmak anlamına gelir. Peki kodumuz, 2000 bit'lik orijinal metni ne kadar sıkıştırabiliyor? Bunu tespit etmek için, basamak başına düşen ortalama bit sayısını hesapmamız gerek. Her kodun uzunluğunu olasılığıyla çarpıyoruz. Sonuçları topluyoruz. Ve sembol başına ortalama 1 virgül 75 bit'lik bir ortalama uzunluğa ulaşıyoruz. Yani Huffman kodlamasının 2000 bit'lik bir iletiyi 1750 bit'e sıkıştırabileceği beklenebilir. Claude Shannon , sıkıştırma limitinin daima ileti kaynağının entropisine eşit olacağını iddia eden ilk kişi oldu. Kaynağın entropisi, yani belirsizliği bilinen istatistiksel yapıya bağlı olarak artarsa, kaynağın sıkıştırılabilirliği de artar. Fakat eğer entropi öngörülmezliğe bağlı olarak artarsa kaynağın sıkıştırılabilirliği azalır. Eğer entropinin de ötesinde sıkıştırma oranlarına ulaşmak istiyorsak iletimizdeki bazı bilgileri feda etmek zorunda kalırız.