Kaynak Kodlama (source coding)

Tanımı

Tam adı Shannon'ın Kaynak Kodlama Kanıtlı Önermesi (source coding theoerm) olan kaynak kodlama, bir iletinin (message) bir iletişim hattından (communication channel) gönderilmeden önce kodlanması ile ilgilidir.

Kaynak kodlamaya iki nedenle ihtiyaç duyulur:

• Resimlerde yanyana renkler veya metinlerde yan yana sözcükler örneklerinde olduğu gibi yakın bilgiler birbirleri ile ilişkilidirler. Dolayısı ile bu bilgilerin olduğu gibi iletilmesi bazı bilgilerin birden çok kez gönderilmesi anlamına gelir. Bu nedenle bilgilerin mümkün olduğunca birbirlerinden bağımsız olmaları istenir.
• Ortalama şaşırtı, en yüksek değerini seçenekler birbiçim (uniform) olduğunda alır. Kodlanmayan bilgi genellikle birbiçim olmadığından gönderilen bilgi en yüksek (maximum) seviyede değildir. Bu nedenle seçeneklerin mümkün olduğunca birbiçim olmaları istenir.

Gürültüsüz (noiseless) bir hattın sığası (channel capacity), ikili düzen için bir saniyede iletişilen en fazla (maximum) ikili rakam (binary digit) sayısıdır. Uygulamada genellikle iletişilen bilgi seviyesi iletişilen ikili rakam seviyesinin çok altındadır. Kaynak kodlamanın amacı aradaki bu farkın azaltılması ve mümkün olduğunca hat sığasına yaklaşılmasıdır.

Örneğin, eşit olasılıklı 8 seçeneği olan bir oyunda ortalama şaşırtı değeri 3 ikildir ve her bir seçenek 3 ikili rakam ile kodlanabilir. Arka arkaya iki oyuna ilişkin bilgilerin sığası saniyede 6 ikili rakam olan bir hattan gönderilmesi durumunda hattın tüm sığası kullanılmış olur. Ancak uygulamada bunu başarmak çok mümkün olmamaktadır. Bunun yerine mümkün olan en yüksek değere ulaşmak hedeflenir.

Yukarıda verilen bilgiler ışığında önerme şu şekilde özetlenebilir:

• ε'un çok küçük bir değer olduğu varsayımıyla, ortalama şaşırtı (entropy) değeri H olan bir bilgiyi sığası S olan bir hattan saniyede ortalama S/H-ε oranında bilgi iletebilecek şekilde kaynağında kodlamak (encode) mümkündür.

S/H ulaşılabilecek en üst noktadır, kayıpsız durumu anlatır, en yüksek oran (maximum rate) olarak adlandırılır ve O ile gösterilir:

$$O=\frac{S}{H}$$

Uygulamada S/H oranına ulaşmak mümkün değildir ancak birinci önermeye göre ε küçüklüğünde bir kayıpla yani hat sığasına çok yakın bir değerle bu iletişim gerçekleştirilebilir.

Buradan yola çıkarak bir kodlamanın verimliliği (efficient) bilginin ortalama şaşırtı değerinin (H) bilgiyi kodlamak için kullanılan ortalama ikili rakam sayısına (U) bölümü olarak tanımlanır:

$$\mathrm{Verimlilik}=\frac{H}{U}$$

Özetle kaynak kodlamada bir seçeneğe ne uzunlukta bir kod atanması gerektiğinin göstergesi o seçeneğin olasılık değeri, ulaşılmaya çalışılan hedef ise ortalama şaşırtı değeridir.

Örnekler

Eşit olasılıklı 8 seçenek bulunan bir oyunda ortalama şaşırtı değeri 3 ikil ve her bir seçeneğin kodlanması için kullanılan ikili rakam sayısı 3'tür. Dolayısı ile kodlamanın verimliliği her bir ikili rakam için bir ikil (3/3=1) olur.

Bu örnekteki 8 eşit olasılıklı seçenek 6 olarak göncellendiğinde ortalama şaşırtı değeri log6=2,58 ikil olur. Ancak 6 seçeneğin kodlanabilmesi için yine 3 ikili rakam (2²=4, 2³=8) gerekir. Bu durumda verimlilik değeri 2,58/3=0,86'ya düşer.

Eşit olasılıklı 6 seçenekle 0,86'ya düşen verimlilik değerini yükseltmek için uygulanan yöntem paydadaki ortalama ikili rakam sayısını (U) düşürmektir. Bu ise birden çok oyunun sonucu birleştirilerek gerçekleştirilir. Örneğin arka arkaya oynanan 3 farklı oyunun sonuçları birleştirildiğinde toplam seçenek sayısı 6×6×6=216'ya çıkar. 216 seçeneği kodlamak için gerekli ikili rakam sayısı 8 (2⁷=128, 2⁸=256) olur. Bu, oyun başına düşen ikili rakam sayısının 8/3=2,66'ya düşmesi demektir. Sonuç olarak verimlilik değeri 2,58/2,66=0,97'ye yükselir.

Olasılıkların eşit olmadığı durumlarda izlenen yol daha farklıdır. 6 seçenekli örneğin seçeneklerinin olasılıklarının sırası ile 0,05, 0,1, 0,15, 0,2, 0,2, 0,3 olduğu varsayımı ile ortalama şaşırtı değeri:

$H\left(X\right)=\sum _{n=1}^{N}p\left(x_n\right){log}_2\frac{1}{p\left(x_n\right)}$

$H\left(X\right)=\mathrm{0,05}\times {log}_2\frac{1}{\mathrm{0,05}}+\mathrm{0,1}\times {log}_2\frac{1}{\mathrm{0,1}}+\mathrm{0,15}\times {log}_2\frac{1}{\mathrm{0,15}}+\mathrm{0,2}\times {log}_2\frac{1}{\mathrm{0,2}}+\mathrm{0,2}\times {log}_2\frac{1}{\mathrm{0,2}}+\mathrm{0,3}\times {log}_2\frac{1}{\mathrm{0,3}}$

$H\left(X\right)=\mathrm{2,41}\mathrm{ikil}$

Bu durumda verimlilik değeri 2,41/3=0,80'e düşer.

Olasılıkların eşit olmadığı bu gibi durumlarda uygulanan yöntem Huffman kodlaması benzeri bir sıkıştırma çözümyolu (compression algorithm) kullanmaktır. Yukarıda açıklandığı üzere, Huffman kodlamasını da içine alan kaynak kodlama çözümyollarında bir seçeneğe atanacak kodun uzunluğu, o seçeneğin olasılık değerini temel alan şaşırtı değerine bakarak belirlenir. Dolayısı ile sık kullanılan iletilere kısa, seyrek kullanılan iletilere uzun kodlar atanır.

Sonuç olarak yukarıdaki örneğe Huffman kodlaması uygulandığında Tablo 2'de verilen kodlar elde edilir:

Tablo 1: Soldan Sağa Kodlama

n	p(n)	Adım 1	Adım 2	Adım 3	Adım 4
1	0,30	0,30	0,30	0,40	0,60 (0)
2	0,20	0,20	0,30	0,30 (0)	0,40 (1)
3	0,20	0,20	0,20 (0)	0,30 (1)
4	0,15	0,15 (0)	0,20 (1)
5	0,10 (0)	0,15 (1)
6	0,05 (1)

Tablo 2: Sağdan Sola Okuma

n	p(n)	Kod	U(n)	p(n)U(n)
1	0,30	00	2	0,60
2	0,20	10	2	0,40
3	0,20	11	2	0,40
4	0,15	010	3	0,45
5	0,10	0110	4	0,40
6	0,05	0111	4	0,20
Ortalama İleti Uzunluğu (Uo)				2,45

Sonuç olarak Huffman kodlaması kullanılması durumunda verimlilik değeri 2,41/2,45=0,98 gibi oldukça yüksek bu değere çıkmaktadır.

Kaynakça

C. E. Shannon, “A mathematical theory of communication”, The Bell system technical journal, 27.3, 379-423, 1948.

J. V. Stone, “Information Theory: A Tutorial Introduction”, Sebtel Press, 2015.