modul i - suyatno.dosen.akademitelkom.ac.id fileteknik kompresi oleh suyatno budiharjo page 1 modul...
TRANSCRIPT
Teknik Kompresi oleh Suyatno Budiharjo Page 1
MODUL I TEORI INFORMASI
1.1. Definisi Kode merupakan pemetaan dari sumber pesan (source messages) ke dalam kode kata (codewords). Sumber pesan merupakan satuan dasar yang didalamnya terdapat string atau karakter yang direpresentasikan secara terpisah. Contoh : Source message
Code word
source message
Code word
aa 000 A 0 bbb 001 b 1 cccc 010 C 10 ddddd 011 d 11 Eeeeee 100 E 100 fffffff 101 F 101 gggggggg 110 G 110 Space 111 Space 111
1.2. Encoding vs Kompresi Encoding adalah proses pencuplikan dan penterjemahan dari sinyal analog ke representasi biner (digital) Kompresi adalah proses pereduksian jumlah bit yang dibutuhkan untuk merepresentasikan sinyal secara digital.
1.3. PCM : Pulse Code Modulation Merupakan Metode encoding yang paling sederhana Hal ini bukan hanya untuk sinyal bicara (speech) tetapi
speech hanya merupakan area penggunaan yang utama dari PCM
Bit rate yang diperlukan untuk mentrasmisikan kode dengan PCM adalah 64 Kbps atau 128 Kbps
Konversi Analog ke Digital : 1. Sampling 2. Kuantisasi
Teknik Kompresi oleh Suyatno Budiharjo Page 2
3. Pembangkitan Code-word Mengapa sinyal analog perlu dikonversi ke digital ? Bukankah dalam real world, sinyal informasi adalah sinyal analog?
Gambar 1.1. Diagram blok ADC
1.4. Digital Audio : Sampling
Merupakan proses pengambilan sampel dari sinyal analog. Secara teori dapat dilakukan dengan cara mengalikan sinyal analog dengan deretan pulsa (impulse train), tetapi hal ini tidak dapat direalisasikan. Mengapa ? Dalam prakteknya sampling dapat dilakukan dengan pengalian dengan sebuah clock. Sebagai ilustrasi adalah gambar 1.2 berikut ini :
Gambar 1.2. Perbandingan sinyal analog dengan sinyal
tersampling 1.5. Coder : Konverter Analog ke Digital Kuantisasi merupakan penentuan level kuantum dari masing-masing sampel analog secara individu. Lihat gambar 1.2 (c). Pembangkitan code-word menyatakan proses penggantian nilai terkuantisasi oleh kode biner sebuah code word. Sebelum melakukan sampling, pada gambar 1.3 terdapat prefilter, yang berfungsi untuk membatasi band informasi, biasanya digunakan filter analog pelolos frekuensi rendah (LPF). Mengapa band informasi perlu dibatasi ?
Teknik Kompresi oleh Suyatno Budiharjo Page 3
Panjang code word menyatakan banyaknya bit yang diperlukan untuk merepresentasikan sampel sinyal. Dan hal ini tergantung banyaknya level dari Quantizer. Dimana hubungan antara code word length dengan level Quantizer adalah :
LQ 2 level
Q
ba : step size atau interval kuantisasi
b = batas bawah a = batas atas
L = panjang code word
Gambar 1.3. Blok Diagram pembangkitan code-word
1.6. Decoder Konversi digital ke analog Dilakukan dengan cara Low pass filtering Proses rekonstruksi dilakukan dengan Sample and Hold Sample & Hold ekivalen dengan konvolusi
menggunakan fungsi rectangular. Identik dengan proses filtering dengan respon frekuensi
fungsi sinc. Interpolasi merupakan perubahan sample rate dari
sinyal digital ke arah yang lebih tinggi. (lawannya desimasi)
Interpolasi = upsample + LP filter Interpolasi atau oversampling dapat dilakukan untuk
mempermudah kerja filter.
Teknik Kompresi oleh Suyatno Budiharjo Page 4
Codec = Coder + Decoder 1.7. Coding Linier dan Logaritmis Bagaimana mengkuantisasi sampel : Coding Linier : penterjemahan secara langsung Coding logaritmis :
- penterjemahan secara logaritmik - frekuensi tinggi dinyatakan dengan presisi (ketelitian)
yang lebih rendah Mengapa ?
- Perbandingan sinyal dengan derau (SNR) adalah lebih besar dibanding uniform.
- Noise dalam SNR disebabkan oleh error kuantisasi. - Paling banyak digunakan dalam pengkodean telepon
(speech) Mengapa ?
1.8. Voice PCM telephony ITU G.711 Pengkodean logaritmis :
-law digunakan oleh Amerika Utara dan Jepang
1log
1log xy
A-law digunakan oleh Eropa dan belahan dunia yang lainnya.
11,
log1
log1
10,
log1
xAA
Ax
Ax
A
Ax
y
dimana :
V
vx , v = harga sesaat, dan V = harga maksimum
dengan nilai 100 dan 6,87A
Teknik Kompresi oleh Suyatno Budiharjo Page 5
Teorema Nyquist :
Laju pencuplikan lebih dari atau sama dengan dua kali frekuensi maksimum sinyal
Target : 3.5 kHz, Sampling : 8 kHz (satu sampel setiap 125 s)
1.9. Rekomendasi G.711 Panjang code word adalah 8 bit
Banyaknya level kuantisasi =82 level.
Pengkodean logaritmis ekivalen dengan pengkodean linier 14-bit pada kualitas perceptual yang sama.
Total laju bit : 64 kbps ? Standar yang lain yang termasuk didalamnya :
- Differential Pulse Code Modulation (DPCM) dan Adaptive DPCM (ADPCM)
- Kompresi
Gambar 1.4. Jarak Antar sampel untuk fs = 8 kHz
1.10. Audio Kualitas CD CD – DA : Compact Disc – Digital Audio Representasi digital memberikan kekebalan terhadap
derau dan bebas reproduksibilitas error Pengkodean linier (dengan alasan historis) karena
pengkodean ini dirancang tidak hanya untuk sinyal bicara. Sekarang, pengkodean tidak linier telah digunakan dan
memberikan data yang lebih kecil 20 – 25 % untuk kualitas perceptual yang sama.
Laju pencuplikan : 44.1 kHz Dengan waktu = 23 s per sampel
Teknik Kompresi oleh Suyatno Budiharjo Page 6
Panjang code word = 16 bit. Dua kanal = kiri kanan (stereo) Total : 1,411 Mbps
Gambar 1.5. Jarak antarsampel dengan fs = 44.1 kHz
1.11. Mengapa Kompresi Motivasi kompresi sinyal : Dunia digital mengalami pertumbuhan yang sangat cepat : Sinyal diperoleh secara digital Sinyal analog dikonversi ke digital Mengapa kompresi data ? Sinyal digital (Image, Speech, etc.) dapat : Dapat disimpan (direkam, diarsipkan) dalam media digital
(piringan komputer) Dapat ditransmisikan secara lokal maupun jarah jauh
melalui link komunikasi digital (telekomunikasi, serat optik)
Dapat diarsipkan dalam basis data publik (ftp, web) Dapat diolah oleh komputer :
- diagnosis / keputusan berbantukan komputer - pencarian otomatis untuk pola tertentu - pencarian konteks - huruf tebal atau tanda interesting suspicious regions - focus pada daerah tertentu dari intensitas citra - Pengolahan sinyal secara statistik :
a. enhancement / restoration b. denoising
Teknik Kompresi oleh Suyatno Budiharjo Page 7
c. klasifikasi d. regresi / estimasi / prediksi e. ekstraksi ciri / pengenalan pola f. filtering
Kompresi dibutuhkan untuk transmisi yang efesien : - mengirimkan lebih banyak data dalam bandwidth yang
tersedia - mengirimkan data yang sama dalam bandwitdh yang
lebih kecil - lebih banyak user pada bandwitdh dan media
penyimpanan yang sama - dapat menyimpan lebih banyak data - dapat mengkompresi untuk penyimpanan lokal,
meletakkan detailnya pada media yang lebih murah.
Juga bermanfaat untuk rekonstruksi progresif, pengiriman scalable, browsing dan sebagai front end dalam pengolahan sinyal lainnya. Ke depan : mengkombinasikan kompresi dan pengolahan subsequent user tertentu. Kasus : Meminimalkan bit rate CD-ROM: 648 MB atau 72 menit dari suara kualitas CD stereo tanpa kompresi. Catatan : - CD Quality : 44 100 Hz, 16 bit, Stereo 172 kbps (141.120
kbps) - Radio Quality : 22 050 Hz, 8 bit, Mono 22 kbps - Telephone Quality : 11 025 Hz, 8 bit Mono 11 kbps CD-ROM tersebut sama dengan 30 detik TV digital kualitas studio tanpa kompresi. Sehingga untuk 90 menit video (movie) memerlukan sekitar 120 GB, yang kira-kira sama dengan 189 CD-ROM. Kita perlu kompresi !!
Kompresi Lossless atau Lossy Ide Umum :
Teknik Kompresi oleh Suyatno Budiharjo Page 8
Beberapa informasi berisi redundansi (informasi yang berlebihan). Apakah semua informasi dibutuhkan ? Tergantung pada viewer target dan final Kompresi tanpa cacat (Lossless) Pengkodean tanpa derau, tanpa cacat, invertible, entropy, data compaction - seluruh informasi disimpan dan kompresi adalah
reversible. - dapat secara sempurna recover data asli (jika tanpa bit
error transmisi atau penyimpanan) - variabel length binary codewords (atau tanpa kompresi) - hanya bekerja untuk sumber digital Ide Dasar : mengkodekan simbol yang mempunyai peluang tinggi ke dalam deretan binary yang pendek, simbol dengan peluang rendah ke dalam deretan binary yang panjang, sehingga bahwa rata-rata terminimalisasi. Kompresi dengan cacat (Lossy)
Beberapa informasi “dibuang” didasarkan pada respon perceptual dari observer. Dan kompresi adalah irreversible atau non invertible, ada informasi yang hilang. Kerugiannya : Berkurangnya informasi dan kualitas, tetapi jika cukup jumlah bitnya, maka cacat tidak kelihatan. Keuntungannya: Memungkinkan kompresi yang lebih besar (umumnya 6:1 to 16:1 ,80:1 to 100:1 dijanjikan dalam beberapa aplikasi) Tujuan desain : memperoleh kualitas sebaik mungkin untuk bits yang tersedia. Big issue : sebaik mungkin Contoh: DPCM, ADPCM, transform coding, LPC, H.26*, PEG, MPEG, EZW, SPHIT, CREW, StackRun Konteks Kompresi - kompresi biasanya bagian dari sistem umum untuk akuisisi, transmisi, penyimpanan dan tampilan data.
Teknik Kompresi oleh Suyatno Budiharjo Page 9
- Konversi analog ke Digital dan akuisisi digital - Qualitas dan penggunaan dari citra digital termodifikasi. Entropy Encoding - Sumber dari data tidak dimasukan ke dalam
penghitungan ketika sedang melakukan kompresi. - Pembuangan pengulangan deretan - Pengkodean secara statistik atau berdasarkan informasi
statistik dari data - Lossless dan reversible Source Encoding - Data ditransformasikan berdasarkan pada sumber dan
karakteristiknya yang diketahui. - Lossy atau lossless Contoh : - membuang bagian diam dalam sebuah deretan sinyal
audio - mendapatkan blok yang dipakai bersama dalam dua
frame dari video Klasifikasi : - Transform Coding - Differential Coding - Kuantisasi Vektor Catatan : Entropy Coding dan Source Encoding dapat digabungkan Penekanan perulangan sequence - Penekanan nol atau blank (kosong) : Sebuah deretan dari n successive zeroes digantikan
dengan sebuah karakter tertentu diikuti oleh angka dari n - Run-length encoding : sama seperti diatas tetapi karakter yang menggantikan
juga dimasukkan ke dalam kode. jumlah dari kejadian sekuensial harus lebih tinggi
dibandingkan 3.
Statistical Encoding
Teknik Kompresi oleh Suyatno Budiharjo
- Deretan dari data yang terjadi paling sering menggunakan kode paling pendek
- Sebuah buku kode dibangkitkan seperti dalam kelebihan huruf (sandi) morse
- Atau secara dinamik selama encoding - Dua kelompok dari Encoding : Substitusi pola Huffman Encoding Pattern Substitution Digunakan ketika mengkodekan teks : - kata yang sering digunakan digantikan dengan code word
yang lebih pendek : “Multimedia” digantikan dengan “*M” dan “Network”
dengan “*N”
Transform Encoding - Beberapa data lebih mudah dikompresi dalam kawasan
frekuensi. - Data dipindahkan dari domain spasial atau temporal ke
dalam domain frekuensi.
Gambar 1.6. Sinyal hasil transformasi
Transformasi : - Transformasi secara matematis menggambarkan suatu
sinyal dapat dinyatakan dengan sinyal yang lainnya.- Sinyal dapat didekomposisikan menjadi beberapa sinyal
yang lainnya. - Memetakan suatu fungsi kedalam fungsi yang lain.- Lossy atau Lossless
Page 10
Deretan dari data yang terjadi paling sering menggunakan
Sebuah buku kode dibangkitkan seperti dalam kelebihan
kata yang sering digunakan digantikan dengan code word
digantikan dengan “*M” dan “Network”
Beberapa data lebih mudah dikompresi dalam kawasan
Data dipindahkan dari domain spasial atau temporal ke
Transformasi secara matematis menggambarkan suatu sinyal dapat dinyatakan dengan sinyal yang lainnya. Sinyal dapat didekomposisikan menjadi beberapa sinyal
Memetakan suatu fungsi kedalam fungsi yang lain.
Teknik Kompresi oleh Suyatno Budiharjo Page 11
- Beberapa frekuensi dikodekan dengan presisi yang lebih rendah atau dibuang secara keseluruhan
- Beberapa transformasi yang sering digunakan : Fourier, DCT, wavelet, Karhunen-Loeve, Hadamard, Walsh, Sine, Hartley, Fractal yang umumnya dilakukan secara digital.
- Discrete Cosine Transform – DCT : digunakan ketika mengkodekan gambar
Mengapa melakukan transformasi ? Beberapa alasan: - Transformasi yang baik cenderung mengumpulkan energi
ke dalam koefisien yang sedikit, mengijinkan beberapa sampel untuk dikuantisasikan ke dalam bit 0 tanpa mempengaruhi kualitas.
- Transformasi yang baik cenderung mendekorelasikan (mereduksi ketergantungan linier) sejumlah koefisien, menyebabkan Quantizer skalar menjadi lebih efisien (Teori Rakyat)
- Transformasi yang baik, secara efektif mengembangkan sinyal dalam fungsi basis (Intuisi matematik)
- Mata dan Telinga cenderung sensitif terhadap perubahan dalam domain frekuensi, sehingga pengkodean dalam domain frekuensi mengijinkan penggunaan ukuran distorsi didasarkan pada persepsi.