[TTG4J3] KODING DAN KOMPRESI
Oleh : Ledya Novamizanti Astri Novianty Prodi S1 Teknik Telekomunikasi Fakultas Teknik Elektro Universitas Telkom
Jika jumlah simbol pada source‐nya kecil, dan probabilitas kemunculan antara simbol sangat timpang, maka nilai probabilitas maksimum (pmax) bisa sangat besar dan kode huffman yang dihasilkan menjadi tidak efisien Alternatif solusi: Extended Huffman Coding Pada extended huffman coding, pengkodean blok simbol bersamaan dapat mengurangi redundansi dari kode Huffman. Dengan memblok n simbol bersamaan berarti ukuran simbol berubah dari m menjadi mn, dimana m adalah ukuran simbol semula.
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
2
Namun, jika probabilitas kemunculan simbol lebih tidak seimbang lagi, maka akan dibutuhkan bloking simbol bersamaan yang lebih banyak. Semakin banyak bloking simbol bersamaan, ukuran simbol akan meningkat secara eksponensial. Penyimpanan kode seperti ini membutuhkan memori yang mungkin tidak tersedia untuk banyak aplikasi. Skema Extended Huffman coding menjadi tidak praktis. Alternatif solusi: Arithmetic Coding [TTG4J3] Koding dan Kompresi
Arithmetic Coding
3
Prinsip dari arithmetic coding diusulkan oleh Peter Elias pada awal dekade 1960, dan diterbitkan dalam buku Abramson (1963), “Information Theory and Coding”, New York, McGraw‐Hill.
Pada arithmetic coding, dihasilkan sebuah nilai tag yang unik untuk sebuah sequence
Tag ini kemudian diberi kode biner yang unik [TTG4J3] Koding dan Kompresi
Arithmetic Coding
4
1. 2.
3. 4. 5. 6.
Set Current Interval [0,1), i = 1 Bagi Current Interval menjadi beberapa sub interval berdasarkan probabilitas simbol, satu sub interval mewakili satu simbol Baca simbol ke‐i pada message, identifikasi sub interval milik simbol tersebut Set Current Interval = sub interval simbol ke‐i Ulangi langkah 2‐4 hingga simbol terakhir pada message Tag sequence data adalah sebuah nilai pada Current Interval : 1. Batas bawah interval, atau 2. Rata‐rata arithmetic = (batas bawah + batas atas) / 2 [TTG4J3] Koding dan Kompresi
Arithmetic Coding
5
Diketahui source S = {A, B, C, #} dengan P={0.4, 0.3, 0.1, 0.2}. Tentukan nilai tag dari sequence ABBC# menggunakan arithmetic coding.
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
6
Diketahui source S = {A, B, C, #} dengan P={0.4, 0.3, 0.1, 0.2}. Message ABBC# Current Interval = [0, 1) Sub Interval = {0, .4, .7, .8, 1} 1. Simbol pertama : A yang menempati sub interval pertama yaitu [0, .4) Current interval = [0, .4)
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
7
Current interval = [0, .4) 2. Simbol kedua : B, yang menempati subinterval ke‐2 Sub Interval = [0+.4×(.4‐0), 0+.7×(.4‐0)) = [.16, .28) Current interval = [.16, .28) 3. Simbol ketiga : B, yang menempati subinterval ke‐2 Sub Interval = [.16+.4×(.28‐.16), .16+.7×(.28‐.16)) =[.208, .244) Current interval = [.208, .244) [TTG4J3] Koding dan Kompresi
Arithmetic Coding
8
Current interval = [.208, .244) 4. Simbol keempat : C, yg menempati subinterval ke‐3 Sub Interval = [.208+.7×(.244 ‐.208), .208+.8×(.244 ‐ .208)) = [.2332, .2368) Current interval = [.2332, .2368) 5. Simbol kelima : #, yang menempati subinterval ke‐4 Sub Interval = [.2332+.8×(.2368‐.2332), .2332+1×(.2368‐.2332)) = [.23608, .2368) Current Interval = [.23608,.2368) [TTG4J3] Koding dan Kompresi
Arithmetic Coding
9
Current Interval = [.23608,.2368) Tag sequence ABBC# adalah sebuah nilai pada interval [0.23608,0.2368), yaitu : Batas bawah interval : 0.23608, atau Rata‐rata arithmetic : (0.23608+0.2368)/2 =
0.23644
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
10
Ilustrasi pencarian nilai tag
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
11
Ringkasan dari pembagian current interval dari message ABBC# pada arithmetic coding
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
12
Diketahui source S = {A, B, C, #} dengan P={0.4, 0.3, 0.1, 0.2}. Decode codeword 0.23608 menggunakan arithmetic coding
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
13
Diketahui source S = {A, B, C, #} dengan P={0.4, 0.3, 0.1, 0.2}. Decode codeword 0.23608 Jawaban: Nilai Tag = 0.23608 Current Interval = [0,1) 1.
Sub Interval = {0, .4, .7, .8, 1) 0.23608 ada pada sub interval [0, .4) Æ simbol A Current Interval = [0, .4) [TTG4J3] Koding dan Kompresi
Arithmetic Coding
14
Current Interval = [0, .4) 2.
Sub Interval = {0, .16, .28, .32, .4} 0.23608 ada pada sub interval [.16, .28) Æ simbol B Current Interval = [.16, .28)
3.
Sub Interval = {.16, .208, .244, .256, .28} 0.23608 ada pada sub interval [.208, .244) Æ simbol B
Current Interval = [.208, .244)
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
15
Current Interval = [.208, .244) 4.
Sub Interval = {.208, .2224, 2332, .2368, .244} 0.23608 ada pd sub interval [2332, .2368) Æ simbol C
Current Interval = [2332, .2368) 5.
Sub Interval = {.2332, .23464, 23572, .23608, .2368} 0.23608 ada pada sub interval [.23608, .2368) Æ simbol #
Jadi hasil decoding codeword 0.23608, yaitu ABBC# [TTG4J3] Koding dan Kompresi
Arithmetic Coding
16
Decoding codeword 0.23608
Jadi hasil decoding codeword 0.23608, yaitu ABBC#
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
17
Diketahui source S = {a, b, c, #} dengan P = {0.3, 0.5, 0.1, 0.1}. Cari nilai tag untuk message “bca” menggunakan Arithmetic Coding? Kemudian decode nilai tag tersebut.
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
18
Secara teoritis tidak ada cara khusus Untuk praktis/implementasi, ada dua alternatif cara:
1. Decoder harus mengetahui banyaknya karakter
pada string yang diencode 2. Menggunakan simbol khusus untuk akhir pesan yang probabilitasnya juga dihitung
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
19
1.
Cari nilai tag
2.
Hitung probabilitas pesan yang diencode, P(x)
3.
Tentukan batasan truncating, dengan rumus:
4.
Kodekan nilai tag ke representasi biner
5.
Tentukan kode akhir biner berdasarkan batasan truncating [TTG4J3] Koding dan Kompresi
Arithmetic Coding
20
Diketahui source S = {A, B, C, #} dengan P={0.4, 0.3, 0.1, 0.2}. Tentukan binary code untuk message ABBC#
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
21
Diketahui source S = {A, B, C, #} dengan P={0.4, 0.3, 0.1, 0.2} Tentukan binary code untuk message ABBC# Jawaban : Nilai Tag = 0.23608 2. Probabilitas dari ABBC# , 1.
P(x) = p1p2p2p3p4 = .4×.3 ×.3 ×.1 ×.2 = .00072 [TTG4J3] Koding dan Kompresi
Arithmetic Coding
22
P(x) = 0.00072 3. Batasan truncating,
Representasi biner dari 0.23608 yaitu 0.001111000110 5. Binary code untuk message ABBC# sepanjang 12 bit, yaitu 001111000110 4.
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
23
Diketahui source A = {a, b, c, d} dengan P = {0.5, 0.25, 0.125, 0.125}. Tentukan binary code untuk masing‐masing simbol
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
24
Diketahui source A = {a, b, c, d} dengan P = {0.5, 0.25, 0.125, 0.125}
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
25
Diketahui source S = {a, b, c, #} dengan P = {0.3, 0.5, 0.1, 0.1}. Tentukan binary code untuk message bca.
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
26
Kendala untuk diimplementasikan: Semakin panjang message, maka range interval
akan semakin kecil Sementara komputer punya keterbatasan dalam hal presisi (cek batas floating point!)
Perlu ada modifikasi di dalam algoritma yang sedapat mungkin meminimalisir mengerucutnya range interval terus menerus Æ Algoritma Arithmetic Coding v.2 [TTG4J3] Koding dan Kompresi
Arithmetic Coding
27
1.
Adam Drozdek, Elements of Data Compression, Thomson Brooks/Cole, 2002
2.
Khalid Sayood, Introduction to Data Compression, Academic Press, 2000.
3.
T.M. Cover, J.A. Thomas, Elements of Information Theory, John Wiley&Sons.
4.
M. Nelson and J.‐L. Gailly. The Data Compression Book. M&T Books, CA, 1996.
5.
D. Salomon. Data Compression: The Complete Reference. Springer, 1998.
[TTG4J3] Koding dan Kompresi
Arithmetic Coding
28
