[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



Kode (Code) adalah sekumpulan rangkaian bit-bit



Codeword adalah representasi bit per simbol



Kode terdiri atas kumpulan codewords



Contoh: 110001011101

Letter/Symbol

Codeword

a1

0

a2

01

Code!

a3

11

(7 codewords) {0, 01, 11}, code!

[TTG4J3] Koding dan Kompresi

Introduction to Coding



Berdasarkan panjang kodenya, ada 2 jenis Kode: 1.

Fixed-Length Code

2.

Variable-Length Code





Setiap simbol atau karakter (letter)

direpresentasikan oleh codeword yang panjangnya tetap (fixed) 

Contoh: representasi ASCII



Setiap codeword memiliki panjang 8 bit



Banyaknya bit dalam sebuah pesan teks = banyaknya karakter * 8 bit [TTG4J3] Koding dan Kompresi




Umumnya kompresi tidak menggunakan Fixed-

length Code 

Fixed-Length Code menyebabkan jumlah simbol

yang dapat diencode menjadi terbatas 

5 bit Fixed-Length Code  berapa simbol?



Yaitu kode yang codewords-nya memiliki panjang berbedabeda  Digunakan untuk mengurangi jumlah bit yang diperlukan dalam merepresentasikan pesan teks  Prinsip dasar: 

 Simbol/karakter yang sering muncul -> codeword pendek  Simbol/karakter yang jarang muncul -> codeword panjang





Codeword sebuah simbol dapat berbeda pada pesan yang berbeda Rata-rata jumlah bit per symbol pada sebuah kode disebut rate of the code atau average length [TTG4J3] Koding dan Kompresi




Encode -> mengubah simbol/karakter pada message

menjadi kode 

Decode -> mengubah kembali kode ke

simbol/karakter awal 

Tahapan mendasar kompresi teks:

teks di-encode, lalu di-decode





Idealnya, setiap pesan dapat di-encode menjadi

kode yang memiliki karakterisitik: 1.

Memiliki codeword yang unik

2.

Tidak menyebabkan ambiguitas dalam men-decode

(Unique decodable) 3.

Instantaneous Decodable

4.

Average Length kecil





Terdapat message (pesan) yang mengandung 4

simbol a1, a2, a3, a4 dengan probabilitas masingmasing simbol di dalam pesan tersebut:

P(a1) = ½, P(a2) = ¼, P(a3) = P(a4) = 1/8 

Berapa entropi dari message tersebut? Apa artinya?





Misalkan message tersebut di-encode ke dalam

beberapa skema code sbb:



a1

a2

a3

a4

Code 1

0

0

1

10

Code 2

0

1

00

11

Code 3

0

01

011

0111

Code 4

0

10

110

111

Rata-rata panjang bit per simbol untuk masingmasing kode disebut Average Length kode tersebut [TTG4J3] Koding dan Kompresi




Average Length untuk kode di atas dihitung

menggunakan:

dengan:  L

= average length (bits/simbol atau bits/sampel)

 P(ai) = probabilitas simbol ai  n(ai) = panjang bit codewords yang merepresentasikan ai [TTG4J3] Koding dan Kompresi




a1

a2

a3

a4

Average Length

Code 1

0

0

1

10

1.125

Code 2

0

1

00

11

1.25

Code 3

0

01

011

0111

1.875

Code 4

0

10

110

111

1.75

Di antara 4 skema kode di atas, kode mana yang memiliki karakteristik ideal? [TTG4J3] Koding dan Kompresi




Ingat, karakterisitik kode ideal: 1.

Memiliki codeword yang unik

2.

Tidak menyebabkan ambiguitas dalam men-decode (Unique decodable)

3.

Instantaneous Decodable

4.

Average Length kecil



a1

a2

a3

a4

Average Length

Code 1

0

0

1

10

1.125

Code 2

0

1

00

11

1.25

Code 3

0

01

011

0111

1.875

Code 4

0

10

110

111

1.75



Code 1 = {0, 0, 1, 10}



Average length paling kecil, tetapi codewords tidak unik



a1 = a2  codeword tidak unik!



Code 1 tidak ideal, dapat menyebabkan ambiguitas



Misalkan string hasil encode: 11100100, hasil

decode?





Code 2 = {0, 1, 00, 11}



Codewords unik



Punya potensi masalah

a1

a2

a3

a4

Average Length

Code 1

0

0

1

10

1.125

Code 2

0

1

00

11

1.25

Code 3

0

01

011

0111

1.875

Code 4

0

10

110

111

1.75

Contoh: encode rangkaian simbol a2 a1 a1



•

Hasil encode 100

•

Hasil decode: a2 a1 a1 atau a2 a3 ?

Tidak unique decodable





Code 3 = {0, 01, 011, 0111}



Codewords unik



Unique decodable

a1

a2

a3

a4

Average Length

Code 1

0

0

1

10

1.125

Code 2

0

1

00

11

1.25

Code 3

0

01

011

0111

1.875

Code 4

0

10

110

111

1.75

 Semua codewords berawal ‘0’, yang membedakan adalah jumlah bit ‘1’  Contoh: 01100101011101011 didecode menjadi?



Bukan instantaneous code (Ketika mendapati codeword tertentu, belum dapat dipastikan bahwa codeword yang dimaksud adalah

codeword tersebut, harus menunggu bit selanjutnya)





Code 4 = { 0, 10, 110, 111}



Codewords unik



Unique decodable

a1

a2

a3

a4

Average Length

Code 1

0

0

1

10

1.125

Code 2

0

1

00

11

1.25

Code 3

0

01

011

0111

1.875

Code 4

0

10

110

111

1.75

 Tiga codewords berakhir ‘0’  Satu codeword terdiri atas 3 bit bernilai 1

 Contoh: 10011111010010 didecode menjadi?



Instantaneous code artinya kode tersebut dapat diencode secara langsung (instan) pada saat menemukan codewords yang sesuai tanpa perlu menunggu bit selanjutnya [TTG4J3] Koding dan Kompresi




Misalkan ada 2 buah codewords a dan b, dengan

panjang a = k bits, panjang b = n bits, dan k < n 

Jika k buah bit pertama dari b adalah a, maka  a adalah prefix dari b

 Sisa bit pada b disebut dangling suffix



Misal a = 010, b = 01011  a prefix dari b  dangling suffix = 11



1.

List semua codewords pada kode yang akan diuji

2.

Jika ada codeword yang menjadi prefix dari codeword lainnya, tambahkan dangling suffix tersebut ke list

3.

Lakukan kembali pengecekkan prefix pada langkah 2

4.

Pengecekkan berhenti jika: 1.

Dangling suffix yang harus ditambahkan merupakan codeword

 not unique decodability 2.

Tidak terjadi kondisi 1 dan tidak ada lagi penambahan dangling suffix yang unik  unique decodability [TTG4J3] Koding dan Kompresi




Diketahui code 5 dan code 6 sebagai berikut. Simbol a1 a2 a3



Codeword 0 01 11

Simbol a1 a2 a3

Codeword 0 01 10

Mana yang unique decodable?





Code 5 = {0, 01, 11}



Berdasarkan Unique Decodability Test: Unique Decodable



Contoh sampel:  Decode string berikut: 011111111111



Code 5 unique decodable, tetapi tidak instantaneous decodable [TTG4J3] Koding dan Kompresi




Code 6 = {0, 01, 10}



Berdasarkan Unique Decodability Test: Not Unique Decodable



Contoh sampel:  Decode string berikut: 01010101010101010



Code 6 Tidak unique decodable





Tentukan apakah kode-kode berikut unique

decodable atau tidak: 1.

{0, 01, 11, 111}

2.

{0, 01, 110, 111}

3.

{0, 10, 110, 111}

4.

{1, 10, 110, 111}





Berdasarkan unique decodability test, sebuah kode

tidak unique decodable jika terdapat dangling suffix yang merupakan codeword pada kode tersebut 

Langkah aman utk menjamin sebuah kode itu unique decodable adalah menghindari adanya dangling suffix



D. k. l => tidak ada codeword yang menjadi prefix codeword yang lain  prefix-free code! [TTG4J3] Koding dan Kompresi




Karakteristik instanteneous code hanya dipenuhi

oleh prefix-free code 

Prefix-Free code = unique decodable + instaneous

code  Kode Ideal !





Dapat direpresentasikan dalam bentuk pohon biner



Ciri khas: setiap simbol akan menjadi leaves nodes, tidak ada yang menjadi internal nodes





Prefix-free Code {01, 10, 11, 000, 001} 0

0

1

1

01



0

1

000

001

0 10

1

11

Jika ni = banyaknya codeword yang memiliki panjang bit i, maka:  n2 = 3 (pada level 2, ada 3 codeword)  n3 = 2 (pada level 3 ada 2 codeword





0

Code {0, 01, 011, 0111}  Bukan prefix-free code,

1 01

tapi unique decodable

1 011 1 0111



Code {0, 01, 11}

0

1

 Bukan prefix-free code,

tapi unique decodable

1

1

01

11





Teorema 1 Jika C adalah sebuah kode yang unique decodable yang terdiri atas N

buah codewords, maka panjang keseluruhan codewordsnya akan memenuhi ketidaksamaan:

 N = banyaknya codewords  lj = panjang codeword ke-j (dalam bit)

 ni = banyaknya codeword yang memiliki panjang bit i ,  b = base (dalam hal ini = 2)  M = panjang maksimum codeword (M buah bit)





{01, 10, 11, 000, 001}



{0, 01, 011, 0111}



{0, 01, 11, 111}



{1, 10, 110, 111}





Setiap unique-decodable-code, pasti memenuhi ketidaksamaan Kraft-McMillan  Bisa prefix-free code, atau  Bukan prefix-free code



Setiap kode yang tidak memenuhi ketidaksamaan Kraft-McMillan, pasti bukan unique-decodable-code



Setiap kode yang memenuhi ketidak samaan KraftMcMillan, belum tentu unique-decodable-code [TTG4J3] Koding dan Kompresi




{0, 01, 110, 111} 



Decode : 01111110

{1, 10, 110, 111} 

Decode: 10110110





Teorema 2 Untuk setiap himpunan codewords yang panjangnya memenuhi ketidaksamaan Kraft-McMillan yaitu

akan selalu dapat dibentuk prefix free-code dengan

panjang codewords yang memenuhi Kraft-McMillan tersebut. [TTG4J3] Koding dan Kompresi




Dengan kata lain, setiap prefix-free code pasti

memenuhi ketidaksamaan Kraft-McMillan, dan 

Untuk setiap komposisi panjang codeword pada

kode yang memenuhi ketidaksamaan KraftMcMillan, pasti dapat dibentuk prefix-fre-code





{0, 01, 110, 111}  Tidak unique decodable, tapi komposisi panjang codeword

pada kode tersebut memenuhi ketidaksamaan KM



{0, 10, 110, 111}  Prefix free code dengan komposisi panjang codeword

yang sama dengan kode di atas



1.

Diketahui kode {1, 10, 011, 100, 111, 0011, 1011}  Apakah unique decodable?  Apakah instantenoues code?  Dapatkah dibentuk prefix-free-code yang memiliki

komposisi panjang yang sama dengan codewords pada kode tersebut? Jika iya, buat prefix-free codenya.



2.

Diketahui sebuah code S = {1, 01, 001, 1010, 0111}  Apakah kita dapat membentuk prefix-free code dengan

komposisi panjang codeword yang sama dengan code S? Alasannya?  Jika dapat, sebutkan contoh prefix code-nya  Apakah S unique decodable?  Apakah S instantaneous code?



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

Recommend Documents