Dalil Shannon Mengenai Lossless Source Coding

Dalil Shannon mengenai Lossless Source Coding berdasarkan pada konsep dari block coding. Untuk mengilustrasikan konsep tersebut, diperkenalkan suatu sumber informasi khusus dimana suatu alphabet terdiri atas hanya dua huruf:

            Di sini, huruf ‘a’ dan ‘b’ sama-sama mempunyai kemungkinan untuk muncul. Bagaimanapun juga, misalkan ‘a’ muncul dalam karakter sebelumnya, probabilitas ‘a’ untuk muncul lagi dalam karakter saat ini adalah 0,9. Sama halnya dengan ‘b’ muncul sebagai karakter sebelumnya, probabilitas ‘b’ akan muncul sekali lagi sebagai karakter saat ini adalah 0,9. Ini dikenal sebagai Binary Symmetric Markov Source.

            Suatu urutan block code ke-n merupakan suatu pemetaan yang ditetapkan untuk tiap blok dari karakter berurutan n dalam suatu untaian bit dengan panjang yang beragam. Contoh berikut mengilustrasikan konsep ini:

1.         First-Order Block Code. Tiap karakter dipetakan sebagai suatu bit tunggal. 

		Codeword
a	0.5	0
b	0.5	1
R =1 bit/character

Contoh:
 

Sebagai catatan 24 bit dipakai untuk merepresentasi 24 karakter − rata-rata 1 bit / karakter.

2.         Second-Order Block Code.  Tiap pasangan karakter dipetakan dengan satu, dua, atau tiga bit.

		Codeword
aa	0.45	0
bb	0.45	10
ab	0.05	110
ba	0.05	111
R=0.825 bits/character

Contoh:

Sebagai catatan 20 bit dipakai untuk merepresentasi 24 karakter − rata-rata 0,83 bit / karakter.

3.         Third-Order Block Code. Triplet dari karakter dipetakan dengan satu urutan bit dengan panjang mulai dari satu hingga enam. 

		Codeword
aaa	0.405	0
bbb	0.405	10
aab	0.045	1100
abb	0.045	1101
bba	0.045	1110
baa	0.045	11110
aba	0.005	111110
bab	0.005	111111
R=0.68 bits/character

Contoh:

Sebagai catatan 17 bit dipakai untuk merepresentasi 24 karakter − rata-rata 0,71 bit / karakter.

Dengan catatan:

1. Nilai tingkat yang ditunjukkan pada tabel dikalkulasi dengan persamaan:

                                                                  ................................................... (2.8)

dimana l(Bn) adalah panjang dari codeword untuk block B_n.

2. Semakin tinggi urutan, maka semakin rendah laju berarti semakin baik kompresinya.
3. Kode yang dipakai sebagai contoh di atas merupakan kode Huffman.
4. Code Table yang ditampilkan merupakan data terkompresi yang diturunkan dari data asli. Semua contoh yang ditampilkan merupakan lossless.

Dalil:   Misalkan R_n*  adalah laju untuk urutan ke-n dari kode kompresi data lossless yang optimal (dalam bit / karakter). Maka:

                                                                                                                                  (2.9)

Dikarenakan baik upper dan lower bound dari R_n*  mendekati entropy rate. H maka n menuju ketakterhinggaan, maka:

                          ................................................... (2.10)

Jadi, dalil ditetapkan bahwa entropy rate adalah laju untuk kode kompresi data lossless optimal. Limit yang berada sepanjang sumber diistilah sebagai stationary.

 Next Pages...