Huffman Coding

03.20 Endicka E Prakarsa No comments

Pada tahun 1951, David A. Huffman dalam kelas Informasi Teori di MIT diberikan pilihan untuk

membuat sebuah term paper atau mengikuti ujian akhir. Pada saat itu pilihan term paper yang diberikan

profesor Robert M. Fano adalah tentang menemukan kode biner yang paling efisien. Tidak dapat membuktikan kode apapun yang paling efisien, Huffman hampir menyerah dan mulai belajar untuk

mengikuti ujian akhir saja, ketika ia menemukan ide untuk menggunakan pohon biner dengan pengurutan berdasarkan kekerapan dan berhasil membuktikan bahwa cara ini adalah yang paling efisien.

Apa yang dilakukan Huffman melampaui profesornya sendiri, yang bekerja sama dengan pencipta bidang teori informasi Claude Shannon mengembangkan kode yang mirip. Huffman menghindari kesalahan besar dari kode Shannon-Fano yang kurang optimal dengan membangun pohon binernya dari bawah ke atas dan bukan dari atas ke. Makalah berjudul “A Method for the Construction of Minimum Redundancy Codes” tersebut lalu dipublikasikan oleh Huffman pada tahun 1952 dalam sebuah jurnal profesional untuk Institute of Radio Engineers.

CONTOH :
Terdapat sumber lima lambang dengan kemungkinan 0.3, 0.2, 0.2, 0.2, 0.1.
Entropy dari sumber ini adalah H = −[0.3 log 0.3 + (3 × 0.2) log 0.2 + 0.1 log 0.1] = 2.246.
Terdapat dua phase dalam menyusun kode huffman yaitu :
a). reduction phase

merupakan phase pengurangan, dimana bila terdapat beberapa simbol kemudian 2 simbol yang memiliki probabilitas paling kecil digabungkan menjadi satu simbol dengan probabilitas sama dengan jumlah probabilitas dari kedua simbol tersebut. Simbol hasil reduksi kemudian diperlakukan seperti simbol yang lain dan dilakukan reduksi lagi hingga mendapatkan 2 buah simbol dengan probabilitas yang tinggi.

Contoh

Terdapat beberapa simbol dengan peluang :

S1 = 0.3, S2 = 0.2, S3 = 0.2, S4 = 0.2, S5 = 0.1

Jika dilakukan reduction phase maka :

S1 = 0.3, S2 = 0.3, S3 = 0.2, S4 = 0.2

Kemudian

S1 = 0.4, S2 = 0.3, S3 = 0.3

Dan

S1 = 0.6, S2 = 0.4

Gambar diagramnya seperti berikut ini :

b). splitting phase

Merupakan phase pembalikan dari reductions phase. Dua simbol dengan probabilitas tinggi hasil reductions phase direpresentasikan kedalam satu komponen dengan code 1 dan O. Kemudian ambil mundur simbol sebelumnya dan representasikan kedalam dua komponen dengan code 00, 01, 10 dan 11. Begitu seterusnya hingga semua simbol sebelum direduksi telah direpesentasikan kedalam code.

Contoh

Hasil splitting phase dari simbol simbol diatas :

0.6 = 0, 0.4 = 1

Kemudian

0.4 = 1, 0.3 = 00, 0.3 = 01

Kemudian

0.3 = 00, 0.3 = 01, 0.2 = 10, 0.2 = 11

Dan

0.3 = 00, 0.2 = 10, 0.2 = 11, 0.2 = 0.10, 0.1 = 011

Gambar diagramnya seperti berikut ini :

Dengan panjang rata rata nya (L)

L = (2 × 0.3) + (2 × 0.2) + (2 × 0.2) + (3 × 0.2) + (3 ×0 .1) = 2.3

Representasi dari Huffman Code tree contoh diatas adalah :

Posted in: MULTIMEDIA