[ttg4j3] koding dan kompresi · [ttg4j3] koding dan kompresi introduction to coding kode (code)...

[TTG4J3] KODING DAN KOMPRESI

Prodi S1 Teknik TelekomunikasiFakultas Teknik Elektro

Universitas Telkom

Oleh :Ledya Novamizanti

Astri Novianty

[TTG4J3] Koding dan Kompresi Introduction to Coding

Kode (Code) adalah sekumpulan rangkaian bit-bit

Codeword adalah representasi bit per simbol

Kode terdiri atas kumpulan codewords

Contoh:

Letter/Symbol Codeword

a1 0

a2 01

a3 11

Code!(7 codewords)

{0, 01, 11}, code!

110001011101


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


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 berbeda-

beda

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


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 masing-

masing 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:

Rata-rata panjang bit per simbol untuk masing-

masing kode disebut Average Length kode tersebut

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


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


Di antara 4 skema kode di atas, kode mana yang

memiliki karakteristik ideal?

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


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


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 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 2 = {0, 1, 00, 11}

Codewords unik

Punya potensi masalah

Contoh: encode rangkaian simbol a2 a1 a1

• Hasil encode 100

• Hasil decode: a2 a1 a1 atau a2 a3 ?

Tidak unique decodable


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 3 = {0, 01, 011, 0111}

Codewords unik

Unique decodable

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 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 4 = { 0, 10, 110, 111}

Codewords unik

Unique decodable

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


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


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


Diketahui code 5 dan code 6 sebagai berikut.

Mana yang unique decodable?

Simbol Codeword

a1 0

a2 01

a3 11

Simbol Codeword

a1 0

a2 01

a3 10


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


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!


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}

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

1

11

1

0

0

0

0

111001

001000


Code {0, 01, 011, 0111}

Bukan prefix-free code,

tapi unique decodable

Code {0, 01, 11}

Bukan prefix-free code,

tapi unique decodable

1

0

0111

011

011

1

1

11

0

1101


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 Kraft-

McMillan, belum tentu unique-decodable-code


{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.


Dengan kata lain, setiap prefix-free code pasti

memenuhi ketidaksamaan Kraft-McMillan, dan

Untuk setiap komposisi panjang codeword pada

kode yang memenuhi ketidaksamaan Kraft-

McMillan, 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 · [ttg4j3] koding dan kompresi introduction to coding kode (code)...

Documents