BAB 2 TINJAUAN PUSTAKA

BAB 2

TINJAUAN PUSTAKA

2.1 Definisi Data Data merupakan salah satu hal utama yang dikaji dalam masalah teknologi informasi. Penggunaan dan pemanfaatan data sudah mencakup banyak aspek. Berikut adalah pembahasan definisi data berdasarkan berbagai sumber. Data menggambarkan sebuah representasi fakta yang tersusun secara terstruktur, dengan kata lain bahwa “Generally, data represent a structured codification of single primary entities, as well as of transactions involving two or more primary entities .” (Vercellis, 2009: 6). Selain deskripsi dari sebuah fakta, data dapat pula merepresentasikan suatu objek sebagaimana dikemukakan oleh Wawan dan Munir (2006: 1) bahwa “Data adalah nilai yang merepresentasikan deskripsi dari suatu objek atau kejadian (event) “ Dengan demikian dapat dijelaskan kembali bahwa data merupakan suatu objek, kejadian, atau fakta yang terdokumentasikan dengan memiliki modifikasi terstruktur untuk suatu atau beberapa entitas.

2.2 Kompresi Data Teks

Kompresi data dalam bidang ilmu komputer, ilmu pengetahuan dan seni adalah sebuah penyajian informasi ke dalam bentuk yang lebih sederhana (Pu, 2006). Kompresi data atau source coding dalam ilmu komputer dan teori informasi adalah proses meng-encode informasi dengan menggunakan lebih sedikit bit dari suatu sumber yang belum di-encode melalui penggunaan skema pengkodean yang spesifik (Data Compression, 2009). Kompresi data dapat di artikan juga sebagai proses yang dapat mengubah sebuah aliran data masukan (sumber atau data asli) ke dalam aliran

Universitas Sumatera Utara

data yang lain (keluaran atau data yang dimampatkan) yang memiliki ukuran yang lebih kecil (Salomon, 2007).

Kompresi data sudah ada sejak puluhan tahun yg lalu. Kompresi data menjadi salah satu cabang Teori Informasi karena kompresi data berkecimpung dengan masalah redudancy dalam suatu informasi. Teori Informasi sendiri merupakan cabang dari ilmu matematika yang lahir pada akhir era 1940-an melalui kerja dari Claude Shannon di Laboratorium Bell. Bidang ini merupakan bidang yang berkecimpung dalam hal mengenai pengeloaan informasi, termasuk di dalamnya adalah bagaimana cara menyimpan dan mengkomunikasikan pesan.

Proses kompresi data didasarkan pada kenyataan bahwa pada hampir semua jenis data selalu terdapat pengulangan pada komponen data yang dimilikinya, misalnya didalam suatu teks kalimat akan terdapat pengulangan penggunaan huruf alphabet dari huruf a sampai dengan huruf z. Kompresi data melalui proses encoding berusaha untuk menghilangkan unsur pengulangan ini dengan mengubahnya sedemikian rupa sehingga ukuran data menjadi lebih kecil.

Kompresi data memberikan pengaruh yang cukup besar terhadap berbagai bidang studi sekarang ini. Hal ini terbukti bahwa kebutuhan untuk memampatkan data sudah dirasakan di masa lalu, bahkan sebelum kedatangan komputer. Ada banyak metode yang dikenal dalam kompresi data. Masing – masing metode memiliki ide yang berbeda – beda dengan jenis data yang berbeda serta hasil yang berbeda pula. Akan tetapi semua metode tersebut memiliki prinsip yang sama, yaitu menghilangkan redudancy yang ada dari data asli di dalam file sumber. Makin besar redudancy di dalam data makin tinggi pula tingkat keberhasilan kompresi data. Dengan demikian, istilah redudancy adalah konsep utama di dalam setiap penelitian pada kompresi data.

Kompresi data sangat populer sekarang ini karena dua alasan yaitu (Salomon, 2007) : 1. Orang – orang lebih suka mengumpulkan data. Tidak peduli seberapa besar media penyimpanan yang dimilikinya. Akan tetapi cepat atau lambat akan terjadi overflow.


2. Orang – orang benci menunggu waktu yang lama untuk memindahkan data. Misalnya ketika duduk di depan komputer untuk menunggu halaman Web terbuka atau men-download sebuah file.

Alasan mengapa kompresi data sangat dibutuhkan karena semakin banyak informasi saat ini yang digunakan dalam bentuk digital dan semakin lama ukuran yang dibutuhkan untuk menyajikan data tersebut semakin besar (Sayood, 2006). Secara garis besar klasifikasi metode kompresi data dapat dilihat pada gambar 2.1 dibawah ini. Data Compression

lossy

Lossless Run Length Coding

Entropy Coding

Dictionary

Huffman Coding, Arithmetic Coding, Comma Coding

Lempel Ziv Welch

Waveform Coding

Synthesis CELP

Time Domain Coding

Frequency Domain Coding

ADPCM, ADM

DCT, Sub – Band Coding

Transform Coding

LPC, RPE-LTP Fractal, Wavelet

JPEG, MPEG

Gambar 2.1 Klasifikasi dari beberapa teknik kompresi data (Sumber : Fauzi, 2009)

Kompresi data dapat dibagi ke dalam dua teknik yaitu lossess compression dan lossy compression.


2.1.1 Lossless Compression

Pada teknik ini tidak ada kehilangan informasi. Jika data dimampatkan secara lossless, data asli dapat direkontruksi kembali sama persis dari data yang telah dimampatkan, dengan kata lain data asli tetap sama sebelum dan sesudah pemampatan. secara umum teknik lossless digunakan untuk penerapan yang tidak bisa mentoleransi setiap perbedaan antara data asli dan data yang telah direkonstruksi. Data berbentuk tulisan misalnya file teks, harus dimampatkan menggunakan teknik lossless, karena kehilangan sebuah karakter saja dapat mengakibatkan kesalapahaman. Lossless compression disebut juga dengan reversible compression karena data asli bisa dikembalikan dengan sempurna. Akan tetapi rasio kompresinya sangat rendah, misalnya pada data teks, gambar seperti GIF dan PNG. Contoh metode ini adalah Shannon-Fano Coding, Huffman Coding, Arithmetic Coding dan lain sebagainya.

Rasio kompresi = ( ukuran file asli – ukuran file terkompresi x 100 % ) ukuran file asli

Gambar 2.2 Lossless compression (Sumber : Pu, 2006)

2.1.2 Lossy Compression

Pada teknik ini akan terjadi kehilangan sebagian informasi. Data yang telah dimampatkan dengan teknik ini secara umum tidak bisa direkonstruksi sama persis dari data aslinya. Di dalam banyak penerapan, rekonstruksi yang tepat bukan suatu


masalah. Sebagai contoh, ketika sebuah sample suara ditransmisikan, nilai eksak dari setiap sample suara belum tentu diperlukan. Tergantung pada yang memerlukan kualitas suara yang direkonstruksi, sehingga banyaknya jumlah informasi yang hilang di sekitar nilai dari setiap sample dapat ditoleransi.

Biasanya teknik ini membuang bagian-bagian data yang sebenarnya tidak begitu berguna, tidak begitu dirasakan, tidak begitu dilihat sehingga manusia masih beranggapan bahwa data tersebut masih bisa digunakan walaupun sudah dikompresi. Misalnya pada gambar dan MP3. Contoh metode ini adalah Transform Coding, Wavelet, dan lain-lain. Lossy compression disebut juga irreversible compression karena data asli mustahil untuk dikembalikan seperti semula. Kelebihan teknik ini adalah rasio kompresi yang tinggi dibanding metode lossless.

Gambar 2.3 Lossy compression (Sumber : Pu, 2006)

2.1.3 Teori Informasi dan Entropi

Istilah entropi pertama sekali digunakan dalam teori informasi yang dikembangkan sekitar tahun 1940 oleh Claude Shannon di laboratorium Bell. Istilah ini dipakai dalam bidang thermodinamika untuk menandai adannya sejumlah gangguan pada sistem

fisika.

Dalam

konteks

kompresi

data,

entropi

digunakan

untuk

merepresentasikan batas bawah (lower bound) dari jumlah rata – rata bit per satu nilai input yaitu rata – rata panjang codeword yang digunakan untuk mengkodekan input.


Teori informasi memanfaatkan terminologi entropi sebagai tolak ukur seberapa besar informasi yang dikodekan pada sebuah data. Entropi merupakan suatu ukuran informasi yang dikandung oleh suatu data dan digunakan sebagai ukuran untuk mengukur kemampuan kompresi dari data.

Input berupa himpunan simbol S = {s1, s2, s3, ..., sn} dengan probabilitas P = {p1, p2, p3, ..., pn} yang secara matematis dapat ditulis sebagai berikut.

Di mana : n = jumlah simbol pj = probabilitas simbol ke-j Misalkan terdapat rangkaian P = abaabcda dalam alphabet {a,b,c,d} maka didapatkan masing-masing probabilitas dari setiap simbol P(a) = 0.5 , P(b) = 0.25 , P(c) = 0.125 dan P(d) = 0.125. Untuk mengkompresi rangkaian data tersebut sebetulnya dapat dengan cara yang paling sederhana yaitu dengan menggunakan 2 bit per simbol {00, 01,10, 11} sehingga menghasilkan jumlah bit = 8 * 2 bit = 16 bit. Tetapi sesuai dengan rumus di atas entropi yang diperoleh adalah H(P) = (0.5, 0.25, 0.125, 0.125) = 0.5 x 1 + 0.25 x 2 + 2 x 0.125 x 3 = 1.75 bit. Dengan kata lain dibutuhkan rata – rata 1.75 bit untuk merepresentasikan data tersebut. Dari hasil tersebut maka didapatkan jumlah bit = 8 * 1.75 = 14 bit untuk mengkompresi rangkaian kata tersebut sehingga menghasilkan 2 bit lebih sedikit dibandingkan dengan cara yang paling sederhana.

Metode entropy coding adalah pengkodean data dengan BPS (Bit Per Simbol) untuk tiap alphabet yang mendekati nilai entropi, karena semakin dekat BPS dari alphabet tersebut dengan nilai entropi semakin efisien pula kode kompresi tersebut (Adityo, 2009). Pada penilitian ini metode entropy coding yang dibahas adalah Arithmetic Coding.


2.3 Teks File

Text file (disebut juga dengan flat file) adalah salah satu jenis file komputer yang tersusun dalam suatu urutan baris (Text File, 2009). Data teks biasanya diwakili oleh 8 bit kode ASCII (atau EBCDIC) (Pu, 2006). Akhir dari sebuah file teks sering ditandai dengan penempatan satu atau lebih karakter – karakter khusus yang dikenal dengan tanda end-of-file setelah baris terakhir di suatu file teks. File teks biasanya mempunyai jenis MIME (Multipurpose Internet Mail Extension) "text/plain", biasanya sebagai informasi tambahan yang menandakan suatu pengkodean. pada sistem operasi Windows, suatu file dikenal sebagai suatu file teks jika memiliki extention misalnya txt, rtf, doc dan lain - lain.

2.4 Citra Digital

Citra secara umum dapat didefinisikan sebagai fungsi intensitas cahaya dari suatu objek dalam dua dimensi f(x,y), dimana x dan y menyatakan koordinat spasial dan nilai f pada sembarang titik (x,y) sebanding dengan skala keabuan (brightness) dari citra pada titik tersebut, dengan demikian f(x,y) juga merupakan fungsi kontinu yang menyatakan tingkat intensitas citra pada titik itu (Suhendra, 2008: 1). Dalam bidang pengolahan citra (image processing), citra yang diolah adalah citra digital, yaitu citra kontinu yang telah diubah ke dalam bentuk diskrit, baik koordinat ruang maupun intensitas cahayanya.

Gambar 2.4 Ilustrasi citra dalam sistem koordinat piksel


Citra digital f(x,y) dapat dibayangkan sebagai sebuah matriks yang indeks baris dan kolomnya mengidentifikasikan sebuah titik pada citra dan nilai dari elemen matriks yang bersangkutan merupakan tingkat warna pada titik tersebut. Elemen tersebut disebut elemen citra, elemen gambar (picture elements), pixels, atau pels, dimana dua kata yang terakhir merupakan singkatan dari “picture elements”. Picture elements atau pixel dapat didefinisikan sebagai elemen terkecil dari sebuah citra digital yang menentukan resolusi citra tersebut. Semakin tinggi resolusi yang dihasilkan, semakin kecil ukuran pikselnya. Hal ini berarti bahwa citra yang diperoleh akan semakin halus.

Citra yang biasa dilihat adalah citra analog yang merupakan fungsi intensitas cahaya dalam bidang 2D. Bilangan-bilangan pembentuk intensitas pada citra analog berupa bilangan riil. Sedangkan citra digital merupakan hasil konversi bilangan tersebut ke bentuk diskrit. Jadi citra digital adalah representasi citra dalam bentuk diskrit, baik pada koordinat ruang maupun nilai intensitas cahayanya.

Citra digital dinyatakan dengan matriks berukuran N x M (baris/ tinggi = N, kolom/ lebar = M). Representasi citra digital sebagai matrik dua dimensi dengan ukuran N x M dapat diilustrasikan pada gambar berikut :

 f (0,0)  f (1,0)   . f ( x, y ) =  .   .   f ( N − 1,0)

f (0,1) f (1,1)

... ...

f ( N − 1,1) ...

f (0, M − 1)  f (1, M − 1)       f ( N − 1, M − 1)

Gambar 2.5 Matriks citra digital N x M


2.5 Pengolahan Citra

Pengolahan citra adalah kegiatan untuk memperbaiki kualitas citra agar mudah diinterpretasi oleh manusia/ mesin (komputer). Inputannya adalah citra dan keluarannya juga citra tapi dengan kualitas lebih baik daripada citra masukan sesuai dengan kebutuhan terhadap citra itu sendiri, misalnya citra warnanya kurang tajam, kabur (blurring), mengandung noise (misal bintik-bintik putih) dan lain-lain, sehingga perlu ada pemrosesan untuk memperbaiki citra karena citra tersebut menjadi sulit diinterpretasikan karena informasi yang disampaikan menjadi berkurang.

Menurut Wijaya dan Prijono (2007: 30), pengolahan citra digital dapat dilakukan dengan berbagai cara, adapun beberapa operasi dalam pengolahan citra antara lain: 1. Perbaikan citra (image restoration) 2. Peningkatan kualitas citra (image enhancement) 3. Registrasi citra (image registration) 4. Pemampatan data citra (image data compression) 5. Pemilahan citra (image segmentation)

Dalam Tugas Akhir ini, pengolahan citra digital difokuskan pada teknik kompresi citra, yaitu citra berwarna RGB format BMP.

2.6 Kompresi Citra Digital

Kompresi

Citra

adalah

proses

untuk

meminimalisasi

jumlah

bit

yang

merepresentasikan suatu citra sehingga ukuran data citra menjadi lebih kecil. Namun, seringkali kualitas gambar yang diperoleh jauh lebih buruk dari aslinya karena keinginan untuk memperoleh rasio kompresi yang tinggi. Pada dasarnya teknik kompresi citra digunakan pada proses transmisi data (data transmission) dan penyimpanan data (data storage). Kompresi citra banyak diaplikasikan dalam penyiaran televisi, penginderaan jarak jauh (remote sensing), komunikasi militer, radar, telekonferensi, pencitraan kedokteran, dan lain – lain.


Semakin besar ukuran citra, semakin besar memori yang dibutuhkan, namun kebanyakan citra mengandung duplikasi data, yaitu: 1. Suatu piksel memiliki intensitas yang sama dengan piksel tetangganya, sehingga penyimpanan piksel membutuhkan memori (space) yang lebih besar sehingga sangat memboroskan tempat. 2. Citra banyak mengandung bagian (region) yang sama sehingga bagian yang sama ini tidak perlu dikodekan berulang kali karena mubazir atau redundan. Contohnya: citra langit biru dengan beberapa awan putih yang memiliki banyak intensitas dan region yang sama.

Manfaat kompresi citra adalah: 1. Waktu pengiriman data pada saluran komunikasi data lebih singkat. Contoh: pengiriman gambar dari fax, videoconferencing, handphone, download dari internet, pengiriman data medis, pengiriman dari satelit, dan sebagainya. 2. Membutuhkan ruang memori dalam storage lebih sedikit daripada representasi citra yang tidak dikompresi.

Metode kompresi yang diharapkan dari sebuah kompresi citra adalah : 1. Proses kompresi dan dekompresinya cepat. Proses kompresi adalah citra dalam representasi tidak mampat dikodekan dengan representsi yang meminimumkan kebutuhan memori. Citra terkompresi disimpan dalam file dengan format tertentu misalnya JPEG (Joint Photographic Expert Group). Proses dekompresi adalah citra yang sudah dikompresi dikembalikan lagi (decoding) menjadi representasi yang tidak mampat. Diperlukan jika citra tersebut dikembalikan ke layar/ disimpan dalam format tidak mampat yaitu format bitmap (BMP). 2. Memori yang dibutuhkan seminimal mungkin Ukuran memori hasil kompresi juga bergantung pada citra itu sendiri, yaitu citra yang mengandung banyak elemen duplikasi biasanya berhasil dikompresi dengan memori yang lebih sedikit. Contoh: citra langit biru tanpa awan berhasil dikompresi dengan baik dibandingkan dengan citra pemandangan alam yang mengandung banyak objek.


3. Kualitas citra hasil kompresi harus bagus (fidelity) Informasi yang hilang akibat kompresi seharusnya seminimal mungkin sehingga kualitas hasil kompresi bagus. Tetapi biasanya kualitas kompresi bagus bila proses kompresi menghasilkan pengurangan memori yang tidak begitu besar, demikian sebaliknya. Dalam kompresi citra terdapat standar pengukuran error (galat) kompresi yaitu: 1. MSE (Mean Square Error), yaitu sigma dari jumlah error antara citra hasil kompresi dan citra asli.

Di mana:

I(x,y) adalah nilai piksel di citra asli. I’(x,y) adalah nilai piksel pada citra hasil kompresi. M, N adalah dimensi citra.

2. PSNR (Peak Signal to Noise Ratio), yaitu untuk mengukur kualitas hasil kompresi.

Nilai b merupakan nilai maksimum dari piksel citra yang digunakan. Nilai b pada Tugas Akhir ini adalah 255. Nilai MSE yang semakin rendah akan semakin baik, sedangkan semakin besar nilai PSNR, semakin bagus kualitas kompresi. PSNR memiliki satuan decibel (dB).

Contoh: Pada kompresi jenis lossless citra di rekonstruksi seperti citra aslinya tanpa kehilangan informasi, misalnya terdapat potongan citra 3 x 3 sebagai berikut:


2

8

3

2

8

3

2

1

1

2

1

1

2

2

2

2

2

2

Citra Asli

Citra Rekonstruksi

MSE = 1/9( 2-2 + 8-8 + 3-3 + 2-2 + 1-1 + 1-1 + 2-2 + 2-2 + 2-2 )2 =0

= infinite

4. Proses transfer dan penyimpanannya mudah. Kompresi citra sebaiknya dapat meminimalkan waktu pengiriman citra pada saluran komunikasi.

Secara umum proses kompresi dan dekompresi dapat dilihat pada gambar di bawah ini: Kompresi

Data Hasil Kompresi

Data Asli Dekompresi

Ukuran Data Asli

Ukuran Data Hasil Kompresi

Gambar 2.6 Alur kompresi-dekompresi data

Parameter-parameter citra yang penting dalam proses kompresi diantaranya adalah sebagai berikut : 1.

Resolusi Resolusi citra menyatakan ukuran panjang kali lebar dari sebuah citra.

Resolusi citra biasanya dinyatakan dalam satuan piksel-piksel. Semakin tinggi resolusi sebuah citra, semakin baik kualitas citra tersebut. Namun, tingginya resolusi


menyebabkan semakin banyaknya jumlah bit yang diperlukan untuk menyimpan dan mentransmisikan data citra tersebut 2.

Kedalaman Bit Kedalaman

bit

menyatakan

jumlah

bit

yang

diperlukan

untuk

merepresentasikan tiap piksel citra pada sebuah frame. Kedalaman bit biasanya dinyatakan dalam satuan bit / piksel. Semakin banyak jumlah bit yang digunakan untuk merepresentasikan sebuah citra, maka semakin baik kualitas citra tersebut 3.

Konsep Redundansi Redundansi merupakan suatu keadaan dimana representasi suatu elemen data

tidak bernilai signifikan dalam merepresentasikan keseluruhan data. Keadaan ini menyebabkan data keseluruhan dapat direpresentasikan secara lebih kompak dengan cara menghilangkan representasi dari sebuah elemen data yang redundan. Redundansi yang terdapat pada citra statis adalah redundansi spasial.

Ada beberapa pendekatan yang digunakan untuk kompresi citra: 1. Pendekatan statistik (statistical compression). 2. Pendekatan ruang (spatial compression). 3. Pendekatan kuantisasi (quantizing compression). 4. Pendekatan fraktal (fractal compression). 5. Pendekatan transformasi wavelet (wavelet compression). Pada Tugas Akhir ini kompresi citra akan menggunakan pendekatan statistik dengan menggunakan algoritma Arithmetic Coding.

2.7 Format Citra Bitmap (BMP)

Citra disimpan di dalam file dengan format tertentu. Format citra yang baku di lingkungan sistem operasi Microsoft Windows dan IBM OS/2 adalah file bitmap (BMP). Saat ini format BMP memang kalah populer dibandingkan format JPG atau GIF. Hal ini karena file citra BMP pada umumnya tidak dikompresi, sehingga ukuran filenya relatif lebih besar daripada file JPG maupun GIF. Hal ini juga menyebabkan format BMP sudah jarang digunakan.


Meskipun format BMP tidak mangkus dari segi ukuran berkas, namun format BMP memiliki kelebihan dari segi kualitas gambar. Citra dalam format BMP lebih bagus daripada citra dalam format yang lainnya, karena citra dalam format BMP umumnya tidak dimampatkan sehingga tidak ada informasi yang hilang. Terjemahan bebas bitmap adalah pemetaan bit, artinya nilai intensitas piksel di dalam citra dipetakan kesejumlah bit tertentu. Peta bit yang umum adalah 8, artinya setiap piksel panjangnya 8 bit. Delapan bit ini merepresentasikan nilai intensitas piksel. Dengan demikian ada sebanyak 28 = 256 derajat keabuan, mulai dari 0-255.

Citra dalam format BMP ada tiga macam: citra biner, citra berwarna, dan citra hitam-putih (grayscale). Citra biner hanya mempunyai dua nilai keabuan, yaitu nilai 0 dan 1. Oleh karena itu, 1 bit sudah cukup merepresentasikan nilai piksel. Citra berwarna adalah citra yang lebih umum. Warna yang terlihat pada citra bitmap merupakan kombinasi dari tiga warna dasar, yaitu mereh, hijau, dan biru. Setiap piksel disusun oleh tiga komponen warna: R (red), G (green), dan B (blue). Kombinasi dari ketiga warna RGB tersebut menghasilkan warna yang khas untuk piksel yang bersangkutan.

Pada citra 256 warna setiap piksel panjangnya 8 bit, tetapi komponen warna RGBnya disimpan di dalam tabel RGB yang disebut palet. Setiap komponen panjangnya 8 bit, jadi ada 256 nilai keabuan untuk warna merah, 256 nilai keabuan untuk warna hijau, 256 nilai keabuan untuk warna biru. Nilai setiap piksel tidak menyatakan derajat keabuan secara langsung, tetapi nilai piksel menyatakan indeks tabel RGB yang memuat nilai keabuan merah (R), nilai keabuan hijau (G), nilai keabuan biru (B) untuk masing-masing piksel yang bersangkutan. Namun pada citra hitam-putih, nilai R = G = B untuk menyatakan bahwa citra hitam putih hanya mempunyai satu kanal warna. Citra hitam putih umumnya adalah citra 8 bit.

Citra yang lebih kaya warna adalah citra 24 bit. Setiap piksel panjangnya 24 bit, karena setiap piksel langsung menyatakan komponen warna merah, komponen warna hijau, dan komponen warna biru. Masing-masing komponen panjangnya 8 bit. Citra 24 bit disebut juga citra 16 juta warna, karena citra ini mampu menghasilkan 224 = 16.777.216 kombinasi warna.


2.8 Arithmetic Coding

Arithmetic Coding memiliki sejarah yang sangat penting karena pada saat itu algoritma ini sukses menggantikan Huffman Coding selama 25 tahun. Arithmetic Coding memiliki kelebihan terutama ketika memproses kumpulan abjad yang relatif sedikit. Awalnya Arithmetic Coding diperkenalkan oleh Shannon, Fano dan Elias. Kemudian dikembangkan oleh Pasco (1976), Rissanene (1976, 1984) dan Langdon (1984). Tujuannya memberikan ide alternatif yang pada saat itu setiap proses pengkodean dilakukan dengan menggantikan setiap simbol masukan dengan suatu codeword (Pu, 2006). Sebagai gantinya, aliran simbol masukan digantikan dengan sebuah angka single floating point.

Pada umumnya, algoritma kompresi data didasarkan pada pemilihan cara melakukan penggantian satu atau lebih elemen-elemen yang sama dengan kode tertentu. Berbeda dengan cara tersebut, Arithmetic Coding menggantikan suatu deret simbol input dalam suatu file data dengan sebuah bilangan menggunakan proses aritmatika. Semakin panjang dan semakin kompleks pesan yang dikodekan, semakin banyak bit yang diperlukan untuk proses kompresi dan dekompresi data.

Output dari Arithmetic Coding ini adalah satu angka yang lebih kecil dari 1 dan lebih besar atau sama dengan 0. Angka ini secara unik dapat didekompresikan sehingga menghasilkan deretan simbol yang dipakai untuk menghasilkan angka tersebut

Dapat didefinisikan Arithmetic Coding adalah suatu bagian dari entropy encoding yang mengkonversi suatu data ke dalam bentuk data yang lain dengan lebih sering menggunakan sedikit bit dan jarang menggunakan lebih banyak bit karakter. Teknik pengkodean ini memisahkan pesan masukan ke dalam simbol dan menukar masing –

masing simbol dengan suatu floating-point. Arithmetic Coding

mengkodekan seluruh pesan ke dalam suatu bilangan pecahan n di mana ( 0.0 = n <1.0) (Arithmetic Coding, 2009).


Implementasi Arithmetic Coding harus memperhatikan kemampuan encoder dan decoder, yang umumnya mempunyai keterbatasan jumlah mantissa. Hal ini dapat menyebabkan kesalahan atau error apabila suatu Arithmetic Coding mempunyai kode dengan floating point yang sangat panjang. Sehingga diberikan solusi berupa modifikasi algoritma Arithmetic Coding dengan menggunakan bilangan integer. Modifikasi ini mampu mengatasi keterbatasan pengolahan floating point dalam melakukan kompresi dan dekompresi data. Modifikasi dengan bilang integer juga dipakai karena jumlah bit kodenya lebih sedikit dan mempercepat proses kompresi dan dekompresi data karena perhitungan integer jauh lebih cepat dari perhitungan floating point serta dapat diimplementasikan dalam program.

Misalkan S = {s1, s2, …, sn} adalah kumpulan simbol sumber dengan distribusi probabilitas kemunculan P = {p1, p2, …, pn}. Subinterval untuk masing-masing perulangan dapat berasal dari setiap simbol menurut probabilitas tersebut. Sebagai contoh, perulangan awal dari [0,1) dapat dibagi ke dalam n interval sebagai berikut :

[0, p1) [p1, p1 + p2) [p1 + p2, p1 + p2 + p3) . . . [p1 + p2 + p3 + ... + pn-1, p1 + p2 + p3 + ... + pn-1 + pn) dimana p1 + p2 + ... + pn = 1 untuk n simbol dalam abjad s1, s2, ..., sn secara berturut – turut. Jika simbol pertama yang dibaca adalah ke – i dari simbol si dalam abjad, maka batas kiri dari subinterval low adalah probabilitas kumulatif dari Pi = p1 + p2 + p3 + ... + pn-1 dan batas kanan high adalah low + Pi.

Panjang dari interval high – low kemudian dapat digunakan untuk menghitung satu dari beberapa interval pada perulangan berikutnya :


[low, low + (high - low) P1) [low + (high - low) P1, low + (high - low) P2) . . . [low + (high - low) Pn-1, low + (high - low) Pn) dimana probabilitas kumulatif seluruhnya adalah Pi = p1 + p2 + ... + pn = 1. Dengan menganggap suatu pesan sumber dengan kumpulan abjad (s1, s2, ..., sn) dan distribusi probabilitasnya (pl, p2 , ..., pn) serta diumpamakan panjang sumber itu adalah N maka dapat dilihat setiap perulangan dari beberapa subinterval pada gambar 2 :

(0)

1

0

High

Low (1) High

Low (2) Low

High

(3)

(N) Gambar 2.7 Perulangan setiap interval [low, high) sebanyak N (Sumber : Pu, 2006)

Berikut ini algoritma 2.1 untuk encoding dan algoritma 2.2 untuk decoding. Akan digunakan dua variabel low dan high untuk mendefinisikan interval [low, high) (Pu, 2006).


Algoritma 2.1 : 1: 2: 3: 4: 5: 6: 7: 8: 9:

low ← 0.0 high ← 1.0 while (simbol input masih ada) do ambil simbol input CodeRange ← high - low high ← low + CodeRange x high_range(s) low ← low + CodeRange x low_range(s) end while output low

Algoritma 2.2 : 1: 2: 3: 4: 5: 6: 7: 8:

ambil encoded symbol (ES) repeat cari range dari simbol yang melingkupi encoded symbol (ES) cetak simbol CodeRange ← high_range – low_range ES = ES – low_range ES = ES/CodeRange until simbol habis

2.9 Bahasa pemrograman Matlab

Matlab merupakan bahasa pemrograman yang hadir dengan fungsi dan karakteristik yang berbeda dengan bahasa pemrograman lain yang sudah ada lebih dahulu seperti Delphi, Basic maupun C++. Matlab merupakan bahasa pemrograman level tinggi yang dikhususkan untuk kebutuhan komputasi teknis, visualisasi dan pemrograman seperti komputasi matematik, analisis data, pengembangan algoritma, simulasi dan pemodelan dan grafik-grafik perhitungan. Kita bisa memanfaatkan kemampuan Matlab untuk menemukan solusi dari berbagai masalah numerik secara cepat, mulai hal yang paling dasar hingga yang kompleks, seperti mencari akar-akar polinomial, interpolasi dari sejumlah data, perhitungan dengan matriks, pengolahan sinyal, dan metoda numerik. Salah satu aspek yang sangat berguna dari Matlab ialah kemampuannya untuk menggambarkan berbagai jenis grafik, sehingga kita bisa memvisualisasikan data dan fungsi yang kompleks.


Gambar 2.8 Contoh tampilan matlab GUI

Matlab hadir dengan membawa warna yang berbeda. Hal ini karena matlab membawa keistimewaan dalam fungsi-fungsi matematika, fisika, statistik, dan visualisasi. Matlab dikembangkan oleh MathWorks, yang pada awalnya dibuat untuk memberikan kemudahan mengakses data matrik pada proyek LINPACK dan EISPACK. Saat ini matlab memiliki ratusan fungsi yang dapat digunakan sebagai problem solver mulai dari yang simple sampai masalah-masalah yang kompleks dari berbagai disiplin ilmu.


BAB 2 TINJAUAN PUSTAKA

Recommend Documents