Friday, July 19, 2019

matematika diskrit- makalah kode huffman



MAKALAH KODE HUFFMAN
“UNTUK KOMPRESI PESAN”





Disusun oleh :
Nama   : Bayu Wira Saputra
NIM    : 17103025
Kelas   : S1 Sistem Informasi 01-A





PROGRAM STUDI SISTEM INFORMASI
FAKULTAS TEKNOLOGI INFORMATIKA DAN INDUSTRI
INSTITUT TEKNOLOGI TELKOM PURWOKERTO
2019


KATA PENGANTAR

Segala puji bagi Allah SWT yang telah memberikan nikmat serta hidayah-Nya terutama nikmat kesempatan dan kesehatan sehingga kami bis menyelesaikan makalah mata kuliah “Matematika diskrit”. Shalawat serta salam kita sampaikan kepada Nabi besar kita Muhammad SAW yang telah memberikan pedoman hidup yakni Al-Qur’an dan sunnah untuk keselamatan umat di dunia.
Makalah ini merupakan salah satu tugas mata kuliah Matematika diskrit di program studi Sistem Informasi Fakultas Teknologi Informatika dan Industri Pada IT Telkom Purwokerto. Selanjutnya penulis mengucapkan terima kasih yang sebesar-besarnya kepada Bapak Yogo selaku dosen mata kuliah Matematika Diskrit dan kepada segenap pihak yang telah memberikan bimbingan serta arahan selama penulisan makalah ini.
Penulis menyadari bahwa terdapat banyak kekurangan dalam penulisan makalah ini, maka dari itu penulis mengharapkan kritik dan saran yang membangun dari para pembaca demi kesempurnaan makalah ini.




Purwokerto, 16 Juni 2019 


Penyusun








DAFTAR ISI

COVER………………………………………………………………………....….i
KATAPENGANTAR……………………………………………………………..ii
DAFTAR ISI…………………………………………………...……..........……..iii
BAB I. PENDAHULUAN
1.1 LatarBelakang………………………………………….……..…………….....1
1.2 RumusanMasalah…………………………………….…..………............……2
1.3 Tujuan……………………………………………….……………….………..2

BAB II. DASAR TEORI
2.1  Definisi kodehuffman………………….….…………………………………3
2.2   Contoh soal KodeHuffman……..………….………….…………...………..4
2.3   Aplikasi Kode Human “Untuk Kompresi Pesan”…........................…….…...8
BAB III. PENUTUP
3.1  Kesimpulan.....................................................................................................15
3.2   DaftarPustaka................................................................................................15

 

 

 

 

 

 

 

 




BAB I

PENDAHULUAN



1.1    Latar Belakang

Dalam berkomunikasi, seseorang terkadang tidak pernah berpikir bagaimana terjadinya penyimpanan data, berapa besar tempat yang dibutuhkan untuk menyimpan data tersebut dan berapa lama waktu yang dibutuhkan dari mereka menulis sampai terkirimnya suatu pesan ketempat yang dituju.  Orang awam tidak pernah mau mengerti apa, mengapa dan bagaimana ilmu tentang pengiriman data dan penyimpanan data.

 Bagi mereka yang penting adalah apa yang mereka inginkan dapat terpenuhi dan dapat  dicapai dalam waktu yang singkat dan hasilnya akurat dan juga memuaskan Oleh karena itu kita sebagai ilmuwan kecil harus tanggap atas semua keadaan tersebut di atas, karena sebenarnya semua permasalahan di atas memang bukan permasalahan mereka. Tetapi permasalahan di atas adalah permasalahan kita, yang harus kita pecahkan sedemikian rupa, sesuai dengan ilmu pengetahuan yang kita miliki saat ini.  Dalam ilmu Komunikasi data, pesan yang dikirim kepada seseorang, seringkali ukurannya terlalu besar, sehingga membutuhkan tempat penyimpanan yang terlalu besar pula.

Demikian juga pesan yang terlalu besar, akan membutuhkan waktu pengiriman yang lebih lama bila dibandingkan dengan pesan yang berukuran relative lebih kecil. Dua masalah tersebut di atas, sebenarnya bisa diatasi dengan pengkodean pesan dengan tujuan agar isi pesan yang sebenarnya besar, bisa dibuat sesingkat mungkin sehingga waktu pengiriman yang mestinya lama bisa dibuat relatif lebih cepat dan tempat penyimpanan yang besar bisa dibuat relatif lebih efisien dibandingkan dengan sebelum dilakukan pengkodean.  Berdasarkan latarbelakang permasalahan di atas, maka penulis tertarik untuk melakukan pembahasan dan penulisan serta tata cara pemampatan data atau yang lebih terkenal dengan istilah kompresi data dengan mengambil judul Kode Huffman untuk pemampatan/Kompresi Data.





1.2    Rumusan Masalah

1.      Definisi dari kode huffman.

2.      Contoh soal kode huffman

3.      Aplikasi kode huffman yaitu dengan cara menggunakan kode Huffman untuk pemampatan atau Compression data agar permasalahan seperti diatas bisa teratasi dengan baik





1.3    Tujuan

1.      Mengetahui dan mempelajari definisi dari kode huffman.

2.      Contoh soal kode dari kode huffman.

3.      Menerapkan kode Huffman untuk memampatkan/mengkompresi data, agar dapat tercapai:

a. Ruang penyimpanan yang relative lebih kecil dibandingkan sebelumnya b. Waktu pengiriman pesan relative lebih cepat dibandingkan sebelumnya

































BAB II

PEMBAHASAN



2.1  Definisi kode huffman   

Algoritma Huffman merupakan algoritma yang dikembangkan oleh David A. Huffman yang digunakan untuk menemukan prefix code yang optimal dan dipublikasikan dalam sebuah paper “A Method for the Construction of Minimum-Redundancy Codes” pada tahun 1952.

Algoritma Huffman menggunakan prinsip pengkodean yang mirip dengan kode Morse, yaitu tiap karakter (simbol) dikodekan hanya dengan rangkaian beberapa bit, dimana karakter yang sering muncul dikodekan dengan rangkaian bit yang pendek dan karakter yang jarang muncul dikodekan dengan rangkaian bit yang lebih panjang. Berdasarkan tipe peta kode yang digunakan untuk mengubah pesan awal (isi data yang dimasukkan) menjadi sekumpulan code-word, algoritma Huffman termasuk ke dalam kelas algoritma yang menggunakan metode statik, yaitu metode yang selalu menggunakan peta kode yang sama. Metode ini membutuhkan dua fase (two-phase), yaitu fase pertama untuk menghitung probabilitas kemunculan tiap simbol dan menentukan peta kodenya, dan fase kedua untuk mengubah pesan menjadi kumpulan kode yang akan ditransmisikan.

Sedangkan berdasarkan teknik pengkodean simbol yang digunakan, algoritma Huffman menggunakan metode symbol-wise, yaitu metode yang menghitung kemunculan dari setiap simbol dalam satu waktu, dimana simbol yang sering muncul diberi kode lebih pendek dibandingkan dengan simbol yang jarang muncul.

















2.2  Contoh soal Kode Huffman

Metode dari Huffman code ini bisa kita lihat dari Contoh soal kode Huffman berikut:

Dimisalkan pada sebuah kalimat terdapat huruf-huruf yang muncul  dengan banyaknya kemunculan adalah sebagai berikut:



Huruf
Frekuensi 
a
5
b
7
c
10
d
14
e
20



Cara mencari kode huffman dijelaskan di bawah ini:
Di bawah ini terdapat contoh metode huffman tree atau disebut juga metode pengakaran dimana kita akan membuat suatu pola pengakaran pada pohon. Langkah pembentukan pohon huffman adalah sebagai berikut:

Untuk membuat Huffman Code pertama kita harus mengurutkan data frekuensi kemunculan dari yang trekecil seperti tabel diatas, lalu kita jumlah kan setiap data secara berpasangan dari yang terkecil:

maka kita mulai dengan menjumlahkan a dan b














Maka tabel berubah menjadi sebagai berikut:

Huruf
Frekuensi
c
10
ab
12
d
14
e
20



Dari tabel di atas kita kembali jumlahkan dua nilai terkecil..

c dan ab




Maka tabel berubah menjadi sebagai berikut:

Huruf
Frekuensi
d
14
e
20
abc
22



Dari tabel di atas kita kembali jumlahkan dua nilai terkecil..

 d dan e




Maka tabel berubah menjadi sebagai berikut:

Huruf
Frekuensi
abc
22
de
34



Dari tabel di atas kita kembali jumlahkan dua nilai terkecil..

abc dan de




Lalu, karena semua Huruf telah dijumlahkan, kita  tambahkan angka 0 dikiri setiap cabang, dan angka 1 dikanan setiap cabang, seperti gambar di bawah ini:




Dari data metode pengakaran Hufman tree di atas di dapatkan Codeword  untuk setiap huruf adalah sebagai berikut:

Huruf
CodeWord
a
000
b
100
c
10
d
01
e
11



Dari tabel diatas kita mendapatkan kode yang unik untuk setiap huruf dengan menggunakan Metoda Hufman Tree pada Hufman Code. 















































2.3  Aplikasi Kode Human “Untuk Kompresi Pesan”



1. Penerapan

Agar bisa menerapkan kode Huffmann, kita akan menguji coba dasar teori yang sudah dijelaskan di atas untuk diterapkan dalam suatu kalimat. Misalnya kalimatnya seperti di bawah ini: Gunakan kode Huffmann untuk mengkompres suatu pesan yang dikirimkan kepada seseorang dengan susunan kalimat sebagai berikut:  “ HARI INI KITA MAKAN SIANG DI MANA” 



Untuk mendapatkan kode Huffmann kita harus mengikuti langkah-langkah sesuai dengan petunjuk: 

1. Menentukan Probabilitas atau peluang dari kemunculan setiap karakter

2. Hasil penghitungannya diletakkan dalam table 

3. Membuat pohon biner 

4. Menentukan kode setiap karakter

5. Menghitung berapa banyaknya bit yang digunakan

6. Membandingkan hasil Kode Huffmann dengan kode ASCII  



Selanjutnya kita akan melakukan penghitungan satu per satu untuk setiap karakter :



Langkah Pertama: Menentukan kerapatan masing-masing karakter dalam susunan kalimat di atas Banyaknya huruf keseluruhan adalah = 27 karakter terdiri dari: 



Huruf “A” = 7, Huruf “I” = 6, Huruf “N”= 4, Huruf “M” = 2 , Huruf “K” = 2 , Huruf “H” = 1, Huruf “ R” = 1, Huruf “T” = 1, Huruf “ S” = 1, Huruf “G” = 1 dan Huruf “ D” = 1 Sehingga 



Langkah kedua: Menentukan probabilitas Masingmasing karakter adalah sebagai berikut 

Huruf “A” = 7/27, Huruf “I”= 6/27, Huruf ”N” = 4/27, Huruf “M” = 2/27, Huruf “K” = 2/27, Huruf “H” = 1/27, Huruf “R” = 1/27, Huruf “T” = 1/27, Huruf “S” = 1/27, Huruf “G” = 1/27, Huruf “ D” = 1/27.  

Apabila hasil tersebut ditabulasikan menjadi seperti pada tabel 3.



Langkah ketiga: Membuat tabel seperti Berikut: 

Tabel 3: Tabel Kerapatan dan Peluang untuk setiap karakter [2]


Langkah ke empat: Membuat pohon biner seperti pada Gambar 2 [3].



Langkah kelima: Ringkasan hasil pembuatan pohon biner untuk setiap karakter adalah sebagai berikut [3]:

 A = 00

 M = 110

 I  = 010

 K = 1110

 S = 0110

 H = 11110

 G = 01110 

 R = 111110

 D = 01111 

 T = 111111

 N = 10



Bila dibuat tabulasi bisa dinyatakan sebagai berikut: 



Tabel 4: Kode Huffman untuk Kerapatan dan Peluang setiap karakter 


Langkah keenam: Hasil rekapitulasi akhir adalah sebagai berikut [4]:



a. Banyaknya bit untuk Huruf  “ A “ =   2 * 7 = 14

b. Banyaknya bit untuk Huruf    I “  =  3 * 6  = 18

c. Banyaknya bit untuk Huruf  “ N “  =  2 * 4 =    8

d. Banyaknya bit untuk Huruf  “ M “ =  3 * 2 =    6

e. Banyaknya bit untuk Huruf  “ K “ =   4 * 2 =   8

f. Banyaknya bit untuk Huruf  “ H “ =  5 * 1  =   5

g. Banyaknya bit untuk Huruf  “ R “ =  6 * 1  =   6

h. Banyaknya bit untuk Huruf  “ T “ =   6 * 1 =   6

 i. Banyaknya bit untuk Huruf  “ S “ =   4 * 1 =   4

j. Banyaknya bit untuk Huruf  “ G “ =  5 * 1 =    5

k. Banyaknya bit untuk Huruf  “ D “ =   5 * 1 =   5



Hasil akhir secara keseluruhan:

 Kalimat yang di kodekan adalah: “HARI INI KITA MAKAN SIANG DI MANA” [5] Dengan Kode ASCII: 27 * 8 Bit = 216 Bit. Dengan Kode Huffmann 85 Bit adalah 85/216 * 100% = 39,35 %. Sehingga dengan kode Huffmann bisa  mengurangi beban lebih dari 60 %.

Kode Huffman Tidak Unik

Untuk membuktikan bahwa Kode Huffman tidak unik, bisa dilakukan dengan mambuat pohon biner seperti pada Gambar 3.













Dari pohon biner pada gambar 3 di atas, bila dibuat tabulasi bisa dinyatakan seperti pada tabel 5 berikut:



Tabel 5: Kode Huffman untuk Kerapatan dan Peluang setiap karakter dari gambar 3



Hasil rekapitulasi akhir adalah sebagai berikut:

a. Banyaknya bit untuk Huruf  “ A “ =   2 * 7 = 14

b. Banyaknya bit untuk Huruf    I “  =  2 * 6  = 12




Gambar 4. Contoh lain untuk membuktikan kode Huffman tidak uni





c. Banyaknya bit untuk Huruf  “ N “  =  3 * 2 = 6

d. Banyaknya bit untuk Huruf  “ M “ =  3 * 4 = 12

e. Banyaknya bit untuk Huruf  “ K “ =   2 * 4 = 8

f. Banyaknya bit untuk Huruf  “ H “ =  1 * 5  =   5

g. Banyaknya bit untuk Huruf  “ R “ =  1 * 5  = 5

h. Banyaknya bit untuk Huruf  “ T “ =   1 * 4 = 4

i. Banyaknya bit untuk Huruf  “ S “ =   1 * 5 =   5

j. Banyaknya bit untuk Huruf  “ G “ =  1 * 6 = 6

k. Banyaknya bit untuk Huruf  “ D “ =   1 * 6 = 6



Maka, perbandingan hasil akhir secara keseluruhan adalah dengan kode ASCII: 27 * 8 Bit = 216 Bit. Dengan Kode Huffmann 83 Bit adalah 83/216 * 100% = 38,43 %. Dengan demikian, kode Huffman terbukti mengurangi beban secara signifikan.



Contoh lain untuk membuktikan kode Huffman tidak unik diperlihatkan pada gambar 4.



Ringkasan hasil pembuatan pohon Biner untuk setiap karakter pada gambar 4 adalah sebagai berikut:

A = 00 

I = 10

N = 010

M = 110

K = 0110 

H  = 1110

S = 01110

R = 11110

G = 011110 

T = 11111

D = 011111





Tabel 6 berikut menunjukkan representasi kerapatan dan peluang kode Huffman dari gambar 4.


Hasil Rekapitulasi akhir adalah sebagai berikut:

a. Banyaknya bit untuk Huruf  “ A “ =   2 * 7 = 14

b. Banyaknya bit untuk Huruf    I “  =  2 * 6  = 12

c. Banyaknya bit untuk Huruf  “ N “  =  3 * 2 = 6

d. Banyaknya bit untuk Huruf  “ M “ =  3 * 4 = 12

e. Banyaknya bit untuk Huruf  “ K “ =   4 * 2 =   8

f. Banyaknya bit untuk Huruf  “ H “ =  4 * 1  =   4

g. Banyaknya bit untuk Huruf  “ R “ =  5 * 1  = 5

h. Banyaknya bit untuk Huruf  “ T “ =   5 * 1 = 5

i. Banyaknya bit untuk Huruf  “ S “ =   5 * 1 =   5

j. Banyaknya bit untuk Huruf  “ G “ =  6 * 1 = 6

k.  Banyaknya bit untuk Huruf  “ D “ =   6 * 1 = 6



Perhitungan hasilnya adalah sebagai berikut:

Dengan kode ASCII: 27 * 8 Bit = 216 Bit, dengan Kode Huffmann 93 Bit adalah 93/216 * 100% = 43,056 %.









BAB III

PENUTUP



3.1    Kesimpulan

Dari Hasil uji coba penerapan dan Penghitungan kode Huffman, maka dapat disimpulkan antara lain bahwa:

1.      Kode Huffmann benar-benar lebih sederhana bila di bandingkan dengan kode ASCII yang selama ini dipakai masyarakat umum.

2.      Dengan menggunakan kode Huffmann ternyata dapat mengurangi beban alias dapat mengkompres data lebih dari 50%.

3.      Penghitungan kode Huffmann tidak unik, tetapi bias bermacam –macam variasi dalam setiap kalimat yang dikodekan, tetapi semua hasil yang dicapai tetap lebih rendah dari pada kode ASCII.





3.2  Daftar Pustaka



3. 792-2135-1-SM.pdf









1 comment:

pengembangan aplikasi mobile (project managemen document)

Project Management Documentation (Business Case, Project Charter, Project Management Plan)              ...