PENDAHULUAN
Sistem komunikasi dirancang untuk mentransmisikan
informasi yang dibangkitkan oleh sumber ke beberapa tujuan. Sumber Informasi
mempunyai beberapa bentuk yang berbeda. Sebagai contoh, dalam radio
broadcasting, sumber biasanya sebuah sumber audio (suara atau musik). Dalam TV
broadcasting, sumber informasi biasanya sebuah sumber video yang keluarannya berupa
image bergerak. Output dari sumber-sumber ini adalah sinyal analog dan sumbernya
disebut sumber analog. Kontras dengan Komputer dan tempat penyimpanan data
(storage), seperti disk magnetic atau optical, menghasilkan output berupa sinyal
diskrit (biasanya
karakter binary atau ASCII) dan tentu sanya sumbernya disebut
sumber diskrit. Baik sumber analog maupun diskrit, sebuah komunikasi digital
dirancang untuk mentransmisikan informasi dalam bentuk digital. Sehingga
konsekuensinya keluaran dari sumber harus diubah dahulu menjadi bentuk keluaran
sumber digital yang biasanya dilakukan pada source encoder, yang keluarannya
dapat diasumsikan sebuah digit biner sekuensial.
Pada akhir 40-an dimana dimulainya tahun Teori Informasi,
ide pengembangan metode coding yang efisien baru dimulai dan
dikembangkan. Dimulainya penjelajahan Ide dari entropy, information content dan
redundansi. Salah satu ide yang popular adalah apabila probabilitas dari simbol
dalam suatu pesan diketahui, maka terdapat cara untuk mengkodekan simbol, sehingga
pesan memakan tempat yang lebih kecil. Model pertama yang muncul untuk kompresi sinyal digital adalah
Shannon-Fano Coding. Shannon dan Fano (1948) terus-menerus ,mengembangkan
algoritma ini yang menghasilkan codeword biner untuk setiap simbol (unik) yang
terdapat pada
data file.
Huffman coding [1952]
memakai hampir semua karakteristik dari Shannon-Fano coding. Huffman coding dapat menghasilkan kompresi data yang
efektif dengan mengurangkan jumlah redundansi dalam mengkoding simbol. Telah
dapat dibuktikan, bahwa Huffman Coding merukan metode fixed-length yang
paling efisien. Pada limabelas tahun terakhir, Huffman Coding telah digantikan
oleh arithmetic coding. Arithmetic coding melewatkan ide untuk
menggantikan sebuah simbol masukan dengan kode yang spesifik. Algoritma ini
menggantikan sebuah aliran simbol masukan dengan sebuah angka keluaran single
floating-point. Lebih banyak bit dibutuhkan dalam angka keluaran, maka semakin rumit
pesan yang diterima.
Algoritma Dictionary-based compression menggunakan metode yang sangat berbeda dalam mengkompres data. Algoritma ini menggantikan
string variable-length dari simbol menjadi sebuah token. Token
merupakan sebuah indek dalam susunan kata di kamus. Apabila token lebih kecil dari
susunan kata, maka tken akan menggantikan prase tersebut dan kompresi terjadi. Masih
banyak lagi metode dan algoritma kompresi, namun dalam makalah ini akan
dibahas mengenai metode kompresi dengan menggunakan Huffman, Shannon-Fano dan
Adaptif Huffman.
DASAR TEORI
Pandangan dasar dari source coding adalah menghilangkan
redundansi dari sumber. Source Coding menghasilkan data compresi dan mengurangi
rate dari transmisi. Pengurangan dari rate transmisi dapat mengurangi biaya
dari sambungan dan memberikan kemungkinan untuk pengguna berbagi dalam sambungan
yang sama. Secara umum kita dapat meng-kompres data tanpa menghilangkan
informasi (lossless source coding) atau mengkompress data dengan
adanya kehilangan informasi (loss source coding).
Teori Source Encoding merupakan salah satu dari ketiga
teorema dasar dari teori informasi yang diperkenalkan oleh Shannon (1948). Teori
Source Encoding mencanangkan sebuah limit dasar dari sebuah ukuran dimana keluaran
dari sebuah sumber informasi dapat dikompresi tanpa menyebabkan probabilitas
error yang besar. Kita telah mengetahui bahwa entropy dari sebuah sumber
informasi merupakan sebuah ukuran dari isi informasi pada sebuah sumber.
Sehingga, dari
pendapat teori source encoding bahwa entropy dari sebuah sumber
sangat penting.
Efisiensi dari sumber ditentukan oleh H(X)/H(X)max,
dimana pi merupakan probabilitas pada simbol ke-I, dan H(X) maksimum ketika sumber
mempunyai simbol probabilitas yang sama.
Teori Shannon Noiseless Source Coding menyatakan bahwa
nilai rata-rata dari simbol biner per keluaran sumber dapat digunakan untuk
mendekati entropi dari sumber. Dalam kata lain, efisiensi dari sumber dapat dihasilkan
dari source coding. Untuk sumber dengan probabilitas simbol yang sama, dan/atau secara
statistic tidak terikat satu dengan yang lain, maka dapat dipetakan (encode)
setiap simbol dalam sebuah codeword dengan panjang n.
Dalam makalah ini akan dibahas dan dianalisa source
encoding berdasarkan model matematis dari sumber informasi dan pengukuran kuantitatif
dari informasi yang dihasilkan oleh sumber.
Gambar 1. Klasifikasi dari beberapa teknik
kompresi
2.1 Algoritma Huffman Coding
Dalam Huffman Coding, panjang blok dari keluaran sumber
dipetakan dalam blok biner berdasarkan pajang variable. Cara seperti ini disebut
sebagai fixed to variable-length coding. Ide dasar dari cara Huffman ini adalah
memetakan mulai simbol yang paling banyak terdapat pada sebuah urutan sumber
sampai dengan yang jarring muncul menjadi urutan biner. Dalam variable-length
coding, sinkronisasi merupakan suatu masalah. Ini berarti harus terdapat satu cara
untuk memecahkan urutan biner yang diterima kedalam suatu codeword.
Seperti yang disebutkan diatas, bahwa ide dari Huffman
Coding adalam memilih panjang codeword dari yang paling besar probabilitasnya sampai
dengan urutan codeword yang paling kecil probabilitasnya. Apabila kita dapat
memetakan setiap keluaran sumber dari probabiltas pi ke sebuah codewortd dengan
panjang 1/pi dan pada saat yang bersamaan dapat memastikan bahwa dapat didekodekan
secara unik, kita dapat mecari rata-rata panjang kode H(x). Huffman Code
dapat mendekodekan secara unik dengan H(x) minimum, dan optimum pada keunikan dari kode-kode tersebut.
Algoritma dari Huffman encoding adalah :
1. Pengurutan keluaran sumber dimulai dari probabilitas paling
tinggi.
2. Menggabungkan 2 keluaran yang sama dekat kedalam satu keluaran
yang
probabilitasnya
merupakan jumlah dari probabilitas sebelumnya.
3. Apabila setelah dibagi masih terdapat 2 keluaran, maka lanjut
kelangkah
berikutnya, namun
apabila masih terdapat lebih dari 2, kembali ke langkah 1.
4. Memberikan nilai 0 dan 1 untuk kedua keluaran
5. Apabila sebuah keluaran merupakan hasil dari penggabungan 2
keluaran dari
langkah sebelumnya, maka
berikan tanda 0 dan 1 untuk codeword-nya,
ulangi sampai keluaran
merupakan satu keluaran yang berdiri sendiri.
2.2 Algoritma Shannon-Fano Encoding
Teknik coding Shannon Fano merupakan salah satu algoritma
pertama yang tujuannya adalah membuat code word dengan redundansi minimum. Ide
dasar dari membuat code word dengan variable-code length, seperti Huffman
codes, yang ditemukan beberapa tahun kemudian.
Seperti yang disebutkan di atas, Shannon Fano coding
didasarkan pada variable length-word, yang berarti beberapa simbol pada pesan
(yang akan dikodekan) direpresentasikan dengan code word yang lebih pendek
dari simbol yang ada di pesan. Semakin tinggi probabilitasnya, maka code word
semakin pendek. Dalam memperkirakan panjang setiap codeword maka dapat ditentukan
dari probabilitas setiap simbol yang direpresentasikan oleh codeword
tersebut. Shannon Fano coding menghasilkan codeword yang tidak sama panjang,
sehingga kode
tersebut bersifat unik dan dapat didekodekan.
Cara efisien lainnya dalam variable-length coding adalah
Shannon-Fano encoding. Prosedur dalam Shannon-Fano encoding adalah :
- Menyusun probabilitas simbol dari sumber dari yang paling tinggi ke yang paling rendah.
- Membagi menjadi 2 bagian yang sama besar, dan memberikan nilai 0 untuk bagian atas dan 1 untuk bagian bawah.
- Ulangi langkah ke 2, setiap pembagian dengan probabilitas yang sama sampai dengan tidak mungkin dibagi lagi
- Encode setiap simbol asli dari sumber menjadi urutan biner yang dibangkitkan oleh setiap proses pembagian tersebut.
2.3 Algoritma Adaptive Huffman Coding
Adaptive Huffman coding pertama kali diperkenalkan oleh
Faller dan Gallager (Faller 1973; Gallaber 1978). Knuth memberikan kontribusi dengan
peningkatan pada algoritmanya (Knuth 1985) dan menghasilkan algoritma yang
dikenal dengan algoritma FGK. Versi terbaru dari adaptive Huffman Coding
diperkenalkan oleh Vitter Vitter 1987). Semua metode yang ditemukan merupakan skema define-word
tabf menentukan mapping dari pesan sumber menjadi codeword didasari
pada perkiraan probabilitas pesan sumber. Kode bersifat adaptive, berganti sesuai
dengan perkiraan
optimalnya pada saat itu. Dalam hal ini, Adaptive Huffman Code
merespon lokalitas. Dalam pengertian, encoder mempelajari karakteristik dari sumber.
Dekoder harus mempelajari bersamaan dengan encoder dengan selalu memperbaharui
Huffman tree sehingga selalu sinkron dengan encoder.
Keuntungan lain dari system ini adalah kebutuhan akan lewatnya
data, data akan lewat hanya sekali (tanpa table statistic). Tentu saja,
metode one-pass tidak akan menarik apabila jumlah bit yang ditransmisikan lebih besar
dari metoda twopass. Namun, performa dari metode ini, dalam ruang lingkup jumlah bit
yang ditransmisikan, dapat lebih baik daripada static Huffman coding.
Permasalahan ini tidak kontradiktif dengan optimalisasi pada metode statis, karena
metode ini optimal hanya [ada metode yang mengasumsikan mapping berdasarkan
time-variant.
Kinerja dari metode adaptive dapat lebih buruk daripada metode
static. Metode adaptive Faller, Gallager dan Knuth merupakan dasar dari UNIX
utility compact. Kinerja compact ini termasuk bagus, karen factor kompresinya
mencapai 30-40% . Dasar dari algoritma FGK adalah adanya sibling (factor
turunan) property, didefinisikan oleh Gallager [Gallager 1978]: binary code tree
mempunyai sibling apabila setiap node )kecuali root) mempunyai sebuah sibling dan
apabila node-node tersebut dapat diurutkan dalam weight dengan setiap node
berhubungan dengan
siblingnya
masing-masing.
Gallager membuktikan bahwa sebuah code prefik biner merupakan Huffman
code jika dan hanya jika code tree mempunyai
sibling property. Dalam algoritma FGK, baik pengirim dan penerima
menangani
perubahan dinamis dari Huffman code tree. Daun dari setiap pohon Huffman
code
merepresentasikan pesan sumber dan berat dari setiap daun
merepresentasikan hitungan
frekuensi untuk setiap pesan. Pada titik manapun dalam satuan waktu, k dari
kemungkinan n pesan sumber terdapat pada susunan pesan.
Pada awalnya, the code tree consists of a single leaf
node, yang disebut 0- node. 0-node digunakan untuk menggambarkan pesan n-k yang tidak
digunakan. Untuk setiap pesan yang ditransmisikan, kedua bagian harus
menambahkan weight dan menghitung kembali code tree untuk mempertahankan simbling
property. Pada titik dalam satuan waktu dimana t pesan telah ditransmisikan. Pada
titik dimana t pesan telah ditransmisikan, k dari mereka berbeda, dan k
< n, pohon merupakan Huffman tree asli dengan daun sebanyak k+1, 1 yaitu k pesan dan
0-node. Apabila pesan ke (t+1) adalah salah satu dari k, maka
algoritma mentrasmisikan code ke
a(t+1), menaikkan counter dan menghitung kembali pohon. Apabila
terdapat pesan yang tidak digunakan, 0-node dipisah untuk membuat 2 pasang daun,
satu untuk a(t+1), dan siblingnya adalah 0-node yang baru. Sekali lagi
dalam proses ini, pohon diperhitungkan kembali. Dalam kasus ini, kode untuk 0-node
dikirimkan; sebagai tambahan, penerima harus memberitahukan pesan n-k mana yang tidak
digunakan yang muncul. Pada setiap node, penyimpanan perhitngan dari pesan
yang muncul dilakukan. Node diberikan nomor untuk mengindikasikan posisi
mereka dalam urutan
sibling propertinya. Pembaharuan dari pohon dapat dilakukan dalam
sebuah single traversal dari node a(t+1) sampai dengan root-nya. Traversal ini
harus meningkatkan perhitungan untuk node a(t+1) dan untuk setiap bagian
atas dari node tersebut. Node boleh berubah untuk memelihara sibling
property-nya, namun perubahan membutuhkan keterlibatan node pada path a(t+1) ke
root-nya.
ANALISA
4.1 Permasalahan yang Dianalisa
Untuk melakukan simulasi program kompresi data di Matlab,
kami hanya menggunakan file gambar bitmap (bmp) dengan jenis yang berbeda
satu sama lain. Namun pada dasarnya, file notepad.txt dan sound.wav juga dapat
dikompresi dengan program simulasi ini. Analisa proses kompresi pada makalah
ini hanya akan menjelaskan kompresi gambar. Analisa untuk jenis file suara dan
teks pada intinya adalah sama.
Permasalahan yang akan dianalisa adalah:
- Pengaruh banyaknya simbol terhadap gain kompresi.
- Pengaruh banyaknya frekuensi tiap simbol terhadap gain kompresi.
- Pengaruh nilai entropi terhadap gain kompresi.
- Kelebihan dari masing-masing metode kompresi yang digunakan dalam program simulasi.
- Kekurangan dari masing-masing metode kompresi yang digunakan dalam program simulasi.
Dari gambar diketahui bahwa kompleksitas masing-masing gambar berbeda. Putih.bmp mempunyai kompleksitas paling rendah dan fish.bmp mempunyai kompleksitas paling tinggi. Kompleksitas gambar ditentukan oleh banyaknya gradasi warna (gray level) setiap gambar. Banyaknya gray level menentukan banyaknya simbol yang harus dikodekan. Gambar hitam-putih (grayscale) dikodekan oleh 8 bit. Artinya akan ada 28 level warna hitam. Warna paling hitam disimbolkan dengan 0, sedangkan warna paling putih disimbolkan dengan 255.
Berikut adalah banyaknya graylevel dari masing-masing gambar:
Nama
File
|
Banyaknya
Gray Level
|
Putih.bmp
|
15
|
Gambar.bmp
|
72
|
Stone.bmp
|
60
|
Fish.bmp
|
237
|
Berikut adalah hasil dari kompresi:
Nama
File
|
Banyaknya
Gray Level
|
Putih.bmp
|
6
|
Gambar.bmp
|
4
|
Stone.bmp
|
12
|
Fish.bmp
|
17
|
Metode Huffman
Nama file
|
Entropi
|
Codelength
(before)
|
Codelength
(after)
|
Gain %
|
Putih.bmp
|
0.19693
|
42700 bits
|
6318 bits
|
85.2037
|
Gambar.bmp
|
2.40134
|
25200 bits
|
8799 bits
|
65.0833
|
Stone.bmp
|
3.15378
|
70000 bits
|
31914 bits
|
54.4086
|
Fish.bmp
|
6.87332
|
70000 bits
|
68599 bits
|
2.00143
|
Metode Shannon-Fano
Nama file
|
Entropi
|
Codelength
(before)
|
Codelength
(after)
|
Gain %
|
Putih.bmp
|
0.19693
|
42700 bits
|
6318 bits
|
85.2037
|
Gambar.bmp
|
2.40134
|
25200 bits
|
8816 bits
|
65.0159
|
Stone.bmp
|
3.15378
|
70000 bits
|
31977 bits
|
54.3186
|
Fish.bmp
|
6.87332
|
70000 bits
|
68770 bits
|
1.75714
|
Hasil pengkodean dari masing-masing file dapat dilihat di
lembar lampiran. Gambar putih.bmp memiliki entropi paling kecil (0,19693). Ini
berarti nilai informasi-nya sangat kecil, terbukti bahwa hampir semua simbol
pada putih.bmp adalah 255 (gray level 255) yang jumlahnya 5940. Jumlah simbol-simbol
lain tidak terlalu besar (lihat lampiran). Simbol dengan probabilitas
terbesar dikodekan hanya dengan 1 bit. Itu berarti semua graylevel 255 dikodekan dengan 1
bit. Simbol-simbol dengan probabilitas kecil, dikodekan dengan 6 bit. Sebelum dikodekan
dengan kode
Huffman, setiap simbol dikodekan dengan 8 bit. Karena itulah gain
kompresi yang didapat sangat tinggi (85,2%).
Berbeda dengan putih.bmp, fish.bmp mempunyai nilai entropi
yang tinggi (6,87). Ini dapat ditunjukan dari banyaknya simbol dengan
frekuensi yang hampir merata di setiap simbolnya (lihat lampiran). Karena itulah
fish.bmp hanya dapat dikompresi dengan gain 2 % (metode Huffman).
Bila kita perhatikan, gambar.bmp memiliki simbol lebih banyak dari
pada stone.bmp. Namun setelah dikompresi justru gambar.bmp yang paling
kecil hasilnya. Hal ini dikarenakan frekuensi dari setiap simbol pada gambar.bmp
kurang merata dibandingkan stone.bmp. Pada stone.bmp frekuensi dari masingmasing
simbol hampir sama (lihat lampiran).
Dari segi lamanya proses pengkodean, Huffman membutuhkan
waktu lebih lama dari Shannon-Fano. Ini disebabkan algoritma Huffman yang
lebih panjang dan kompleks daripada algoritma Shannon-Fano. Pada Huffman,
simbol-simbol harus diurutkan dari yang paling tinggi probabilitasnya hingga yang
paling rendah. Kemudian dua probabilitas terkecil dijumlahkan dan hasilnya
diurutkan kembali dari yang paling besar hingga yang paling kecil. Begitu seterusnya
sampai pada akhir penjumlahannya bernilai 1.
Sedangkan pada Shannon-Fano, simbol-simbol hanya satu kali
diurutkan dari yang probabilitasnya paling kecil hingga yang paling besar.
Kemudian dari urutan simbol-simbol tersebut dibagi dua kelompok berdasarkan
probabilitasnya. Kemudian hasilnya dibagi dua kelompok lagi. Begitu seterusnya hingga setiap
kelompok tidak dapat lagi dibagi dua (hanya tersisa 1 simbol). Bagaimana cara
komputer membaca dan membedakan deretan bit yang sudah dikodekan ?
Kita ambil contoh masukan dari user berupa teks “maulana”.
File ini disimpan lalu dikodekan dengan Huffman Code, hasilnya adalah:
Simbol Probabilitas Kode Huffman
m 1/7 100
a 3/7 0
u 1/7 101
l 1/7 110
n 1/7 111
Pada saat dikirimkan, urutan bitnya menjadi:
1 0 0 0 1 0 1 1 1 0 0 1 1 1 0
Dari urutan bit ini, komputer akan membaca bit yang
terdepan (paling kiri) hingga yang terbelakang (paling kanan). Selain membaca bit, komputer juga
akan membandingkan dengan tabel kode yang juga dikirimkan bersama data.
Apabila dalam pembacaan urutan bit lalu dibandingkan dengan tabelnya ada
kecocokan, maka komputer akan langsung menerjemahkannya ke dalam simbol
aslinya. Inilah yang disebut unique prefix. Contoh:
Iterasi 1 Komputer membaca bit 1
Komputer mencari di tabel apakah simbol untuk kode 1, ternyata
tidak ada.
Iterasi 2 Komputer membaca bit 1 0
Komputer mencari di tabel apakah simbol untuk kode 1 0, ternyata
tidak ada.
Iterasi 3 Komputer membaca bit 1 0 0
Komputer mencari di tabel apakah simbol untuk kode 1 0 0, ternyata simbol m.
Iterasi 4 Komputer membaca bit 0
Komputer mencari di tabel apakah simbol untuk kode 0, ternyata
simbol a.
dan seterusnya sampai semua kode berhasil diterjemahkan ke
simbolnya masing-masing.
4.2 Verifikasi Program
Untuk verifikasi kebenaran algoritma program, kita masukan data
dari user.txt yang
isinya berupa teks:
maulana
User.txt kemudian dibaca oleh program dan akan dihasilkan :
Simbol 97 108 109 110 117
Frekuensi 3 1 1 1 1
Ini artinya simbol a dinyatakan
dengan kode ASCII 1011101
(biner dari 97) dan begitu juga simbol-simbol yang lain dibaca dengan
kode ASCII. Dengan metode Huffman maka jalannya proses pengkodean adalah
sebagai berikut:
Hasil kode Huffman dari simbol-simbol di atas adalah:
Dengan demikian coding dengan program dan manual sama.
Berikut adalah perhitungan entropi dari masing-masing simbol:
Simbol a mempunyai probabilitas 3/7 maka besarnya entropi = (-3/7 )2log
3/7 = 0.5239
Simbol m mempunyai probabilitas 1/7 maka besarnya entropi = (-1/7 )2log
1/7 = 0.4011
Simbol u mempunyai probabilitas 1/7 maka besarnya entropi = (-1/7 )2log
1/7 = 0.4011
Simbol l mempunyai probabilitas 1/7 maka besarnya entropi = (-1/7 )2log
1/7 = 0.4011
Simbol n mempunyai probabilitas 1/7 maka besarnya entropi = (-1/7 )2log
1/7 = 0.4011
Jumlah entropi total adalah 2.1281.
KESIMPULAN
1. Banyaknya simbol dan frekuensi masing-masing simbol menentukan
nilai entropi
suatu data.
2. Nilai entropi menentukan gain kompresi.
3. Makin besar entropi, maka akan makin kecil gain yang diperoleh
pada saat
pengompresan suatu data.
4. Dengan file yang sama, Huffman menghasilkan gain kompresi yang
lebih baik
dibandingkan
Shannon-Fano.
5. Dengan file yang sama, Shannon-Fano membutuhkan waktu proses
kompresi
yang lebih cepat
dibandingkan Huffman.
6. Hasil kompresi akan dikirimkan ke tujuan berikut dengan tabel
kodenya untuk
proses dekoding.
Urutan biner hasil koding tidak akan salah di-dekodekan karena
setiap kode memiliki unique prefix.
DAFTAR PUSTAKA
1. Shanmugam, K. Sam,” Digital and Analog Communications
Systems”, John Wiley
& Sons, Inc.,1979.
2. Haykin, Simon,” An Introduction to Analog & Digital
Communications”, John
Wiley & Sons,
Inc.,1994
3. Internet, http://www.ics.uci.edu/~dan/pubs/
4. Internet, http://ics.uci.edu/~dan/pubs/Data
Compression.html
Tidak ada komentar:
Posting Komentar