[TTG4J3] KODING DAN KOMPRESI. Oleh : Ledya Novamizanti Astri Novianty. Prodi S1 Teknik Telekomunikasi Fakultas Teknik Elektro Universitas Telkom

[TTG4J3] KODING DAN KOMPRESI

Oleh : Ledya Novamizanti Astri Novianty Prodi S1 Teknik Telekomunikasi Fakultas Teknik Elektro Universitas Telkom

Untuk meng‐encode integer positif, dapat digunakan diantaranya: 1. Unary Code 2. Golomb Code

Asumsi yang digunakan adalah semakin besar nilai integer, probabilitas kemunculannya semakin kecil.

[TTG4J3] Koding dan Kompresi

Golomb & Tunstall Codes

2

Pengkodean integer yang paling sederhana

Untuk integer positif bernilai n, unary code‐nya adalah n buah ‘1’ diikuti oleh ‘0’

Contoh: Unary Code untuk 4 = 11110 Unary Code untuk 7 = 11111110



3

Golomb Code dari nilai integer positif n adalah gabungan representasi bit codeword q dan r , dimana : 1. Nilai q, yaitu 2. Nilai r, yaitu

q bernilai 1, 2, … dan dinyatakan dalam unary code r bernilai 0, 1, 2, …, m‐1 Nilai parameter m > 0 ditentukan di awal



4

a)

Jika m adalah kelipatan pangkat 2 Panjang bit codeword r , yaitu

bits

Codeword r = representasi biner dari nilai r Contoh: Misalkan diketahui m = 4 dan r = 3, Maka panjang bit codeword r = = 2 bits Sehingga codeword r = 11 [TTG4J3] Koding dan Kompresi


5

b)

Jika m bukan kelipatan pangkat 2 Codeword r ditentukan oleh batasan representasi s, dengan perhitungan s = Jika nilai r < s, maka: ▪ Panjang bit codeword r , yaitu bits ▪ Codeword r = representasi biner dari nilai r Jika nilai r >= s, maka: ▪ Panjang bit codeword r , yaitu bits ▪ Codeword r = representasi biner dari atau r + s [TTG4J3] Koding dan Kompresi


6

Tentukan Golomb Code untuk integer 9, menggunakan parameter m = 5



7

Diketahui n=9, m=5 Golomb Code dari n adalah gabungan representasi bit codeword q dan r , dimana :

1. 2.

Æ Unary Code untuk 1 yaitu 10 .



8

Diketahui n=9, m=5 Diperoleh q=10 dan r=4 m=5 bukan kelipatan pangkat 2. Maka : . r > s, maka panjang bit codeword : Codeword r = representasi biner dari r+s = 4+3 = 7, sebanyak 3 bit yaitu 111 Golomb Code dari 9 adalah gabungan representasi bit codeword q dan r , yaitu 10111



9

Tentukan Golomb Code untuk integer 21 menggunakan parameter m = 5 2. Lakukan hal yang sama dengan parameter m = 6 3. Tentukan golomb code untuk nilai integer 0 – 16 dengan nilai m = 6 1.



10



11

Panjang codeword sama, tetapi setiap codeword merepresentasikan jumlah simbol yang berbeda Contoh Kode Tunstall 2 bit:

Sequence

Codeword

AAA

00

AAB

01

AB

10

B

11

Maksimum banyaknya codeword dari n‐bit kode Tunstall yaitu 2n [TTG4J3] Koding dan Kompresi


12

Stressing algoritma Tunstall Code adalah menentukan rangkaian/sequence simbol untuk setiap codeword, bukan menentukan codewordnya! Menentukan codewordnya mudah karena fixed‐ length. Tinggal membinerkan nilai desimal mulai dari 0 s.d 2n ‐ 1 secara berurut Misal, untuk tunstall code 2 bit, kodenya = {00, 01, 10, 11} Pertanyaannya adalah, ‘00’ merepresentasikan sequence apa? ‘01’? ‘10’? ‘11’?



13

1.

2.

3.

Misalkan terdapat N simbol pada source {a1, a2, a3, …, aN}, dengan probabilitasnya masing‐masing. Urutkan berdasarkan probabilitas secara descending Hitung nilai K sebagai batas pengulangan, dengan ketidaksamaan N + K(N‐1) ≤ 2n , dimana n=panjang bit yang diinginkan, N=jumlah simbol). Pilih Kmaks Lakukan langkah berikut sebanyak K kali: 1. Keluarkan simbol dengan probabilitas tertinggi 2. Rangkai simbol tersebut dengan setiap simbol yang ada di dalam source termasuk dirinya sendiri. Banyaknya sequence simbol menjadi N + (N‐1) [TTG4J3] Koding dan Kompresi


14

Diketahui string AAABAABAABAABAAA. Encode string tersebut menggunakan Tunstall Code 2 bit.



15

Diketahui string AAABAABAABAABAAA. Jumlah simbol, N=2 Encodekan menggunakan Tunstall Code 2 bit, maka panjang bit yang diinginkan, n=2. 1. Urutkan symbol secara descending :

2.

Hitung nilai K: N + K(N‐1) ≤ 2n , 2 + K(2‐1) ≤ 22, K≤2. Diperoleh Kmaks=2 [TTG4J3] Koding dan Kompresi


16

Iterasi #1

Iterasi #2



17

Diperoleh Tunstall Code 2 bit : Sequence

Codeword

B

00

AB

01

AAA

10

AAB

11

String :

Hasil encoding :



18

Apakah kode berikut ini Tunstall Code 2 bit? Sequence AAA ABA AB B

Codeword 00 01 10 11



19

Desainlah Tunstall Code 3 bit untuk source {A,B,C} , dengan P(A) = 0.6, P(B) = 0.3, dan P(C)= 0.1.



20

Diketahui : Jumlah simbol, N=3. Panjang bit yang diinginkan, n=3. 1. Urutkan symbol secara descending :

2.

Hitung nilai K: N + K(N‐1) ≤ 2n , 3 + K(3‐1) ≤ 23, 2K≤2. Diperoleh Kmaks=2 [TTG4J3] Koding dan Kompresi


21

Iterasi #1

Iterasi #2



22

Diperoleh Tunstall Code 3 bit : Sequence

Codeword

B

000

C

001

AB

010

AC

011

AAA

100

AAB

101

AAC

110



23

Desain Tunstall Code 3 bit untuk source {a,b,c} dengan P(a) = 0.3, P(b) = 0.5, P(c)=0.2 2. Desain Tunstall Code 4 bit untuk source {a,b,c,d} dengan P(a) = 0.2, P(b) = 0.3, P(c)=0.1, P(d) = 0.4 1.



24

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.



25

[TTG4J3] KODING DAN KOMPRESI. Oleh : Ledya Novamizanti Astri Novianty. Prodi S1 Teknik Telekomunikasi Fakultas Teknik Elektro Universitas Telkom

Recommend Documents