Huffman Coding

Huffman Coding adalah jenis source coding yang paling efisien. Berikut adalah algoritma sederhana dari Huffman Coding:

  1. alokasikan dua sumber informasi yang memiliki peluang kemunculan terkecil ke codeword terpanjang yang perbedaan keduanya terletak di simbol terakhir,
  2. tambahkan peluang kemunculan dua sumber di  (1) sehingga menjadi satu sumber informasi yang baru, lalu lakukan hal sama pada no. (1) ke semua sumber informasi yang ada

Berikut adalah contoh Huffman Coding dari contoh pada artikel encoding (part1: noiseless coding):

Contoh Huffman Coding
Contoh Huffman Coding

Dari contoh diatas, kita bisa menghitung nilai panjang codeword rata-rata sebagai berikut:

AveCodeLen = \sum\limits_{i = 1}^{n} p_{i} l_{i}

 AveCodeLen = (2/17) \times 3 + (2/17) \times 3 + (5/17) \times 2 + (8/17) \times 1 = 1.76

sehingga kita dapatkan panjang codeword rata-rata yang hampir mendekati batas minimalnya, yaitu mendekati nilai Entropy-nya = 1.75.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s