solusi quiz#2 -...
TRANSCRIPT
SOLUSI QUIZ#2
Soal:
Untuk nomor 1-3, diketahui pesan string “jaya berjaya”
1. Dengan menggunakan Standard Huffman coding, codeword untuk simbol spasi adalah 1110
2. Redundancy yang diperoleh hasil pengkodean huffman untuk string di atas adalah (lengkap dengan
satuan) 0,081 bits/sample
3. Rasio kompresi yang dihasilkan menggunakan standar huffman coding untuk string di atas adalah
66,67% (dalam prosen)
Pembahasan:
1. P(j) = 2/12, P(a) = 4/12, P(y) = 2/12, P(_) = P(b) = P(e) = P(r) = 1/12
Ingat kesepakatan rulenya: probabilitas descending, jika sama nilainya maka indeks huruf descending
juga (asumsi indeks spasi itu sebelum indeks huruf ‘a’).
j 2/12
a 4/12
y 2/12
r 1/12
e 1/12
b 1/12
_ 1/12
x1 2/12
j 2/12
a 4/12
y 2/12
r 1/12
e 1/12
x1 2/12
x2 2/12
j 2/12
a 4/12
y 2/12
x1 2/12
x2 2/12
x3 4/12
x3 4/12
a 4/12
j 2/12
y 2/12 x4 4/12
x3 4/12
a 4/12
x4 4/12
x5 8/12
x5 8/12
a 4/12
1
‘1’
‘1’
‘1’
‘1’
‘1’
‘1’
‘0’
‘0’
‘0’
‘0’
‘0’
‘0’
Maka kita akan dapatkan codeword sbb:
a = 0 e = 1100
y = 101 b = 1111
j = 100 _ = 1110
r = 1101
2. Entropi pesan “jaya berjaya” adalah sbb.
𝐻 = −[𝑃(𝑗) ∗ log2 𝑃(𝑗) + 𝑃(𝑎) ∗ log2 𝑃(𝑎) + 𝑃(𝑦) ∗ log2 𝑃(𝑦) + 𝑃(_) ∗ log2 𝑃(_) + 𝑃(𝑏)
∗ log2 𝑃(𝑏) + 𝑃(𝑒) ∗ log2 𝑃(𝑒) + 𝑃(𝑟) ∗ log2 𝑃(𝑟)]
= − [2
12∗ log2
2
12+
4
12∗ log2
4
12+
2
12∗ log2
2
12+
1
12∗ log2
1
12+
1
12∗ log2
1
12+
1
12∗ log2
1
12+
1
12∗
log21
12]
= − [1
6∗ (−2,585) +
1
3∗ (−1,585) +
1
6∗ (−2,585) +
1
12∗ (−3,585) +
1
12∗ (−3,585) +
1
12
∗ (−3,585) +1
12∗ (−3,585)]
= −(−0,431 − 0,528 − 0,431 − 0,299 − 0,299 − 0,299 − 0,299)
SOLUSI QUIZ#2
= 2,586 𝑏𝑖𝑡/𝑠𝑎𝑚𝑝𝑙𝑒
Jika ni menunjukkan panjang bit karakter i, maka Average Length kode yang dihasilkan oleh Huffman
Coding di atas adalah sbb.
𝐴𝑣. 𝐿𝑒𝑛𝑔𝑡ℎ = 𝑃(𝑗) ∗ 𝑛𝑗 + 𝑃(𝑎) ∗ 𝑛𝑎 + 𝑃(𝑦) ∗ 𝑛𝑦 + 𝑃(_) ∗ 𝑛_ + 𝑃(𝑏) ∗ 𝑛𝑏 + 𝑃(𝑒) ∗ 𝑛𝑒 + 𝑃(𝑟) ∗ 𝑛𝑟
= 2
12∗ 3 +
4
12∗ 1 +
2
12∗ 3 +
1
12∗ 4 +
1
12∗ 4 +
1
12∗ 4 +
1
12∗ 4
= 6 + 4 + 6 + 4 + 4 + 4 + 4
12=
32
12
= 2,667 𝑏𝑖𝑡/𝑠𝑎𝑚𝑝𝑙𝑒
Maka Redundancy kode Huffman yang dihasilkan adalah:
𝑅𝑒𝑑𝑢𝑛𝑑𝑎𝑛𝑐𝑦 = 𝐴𝑣. 𝐿𝑒𝑛𝑔𝑡ℎ − 𝐸𝑛𝑡𝑟𝑜𝑝𝑖 =(2,667 − 2,586)𝑏𝑖𝑡𝑠
𝑠𝑎𝑚𝑝𝑙𝑒= 0,081 𝑏𝑖𝑡𝑠/𝑠𝑎𝑚𝑝𝑙𝑒
3. Sebelum dikompresi, ukuran data pesan “jaya berjaya” adalah 12 x 8 bits = 96 bits.
Setelah dikompresi, ukuran data pesan “jaya berjaya” dihitung sbb.
𝑢𝑘𝑢𝑟𝑎𝑛 𝑑𝑎𝑡𝑎 = ∑ 𝑓𝑖 ∗ 𝑛𝑖
dengan fi = frekuensi/banyaknya kemunculan karakter i,
ni = panjang bit codeword yang mereresentasikan karakter i
Maka setelah kompresi, ukuran datanya:
𝑢𝑘𝑢𝑟𝑎𝑛 𝑑𝑎𝑡𝑎 = 𝑓𝑗 ∗ 𝑛𝑗 + 𝑓𝑎 ∗ 𝑛𝑎 + 𝑓𝑦 ∗ 𝑛𝑦 + 𝑓_ ∗ 𝑛_ + 𝑓𝑏 ∗ 𝑛𝑏 + 𝑓𝑒 ∗ 𝑛𝑒 + 𝑓𝑟 ∗ 𝑛𝑟
= 2 ∗ 3 + 4 ∗ 1 + 2 ∗ 3 + 1 ∗ 4 + 1 ∗ 4 + 1 ∗ 4 + 1 ∗ 4 = 6 + 8 + 6 + 4 + 4 + 4 + 4
= 32 𝑏𝑖𝑡𝑠
Maka rasio kompresi dalam % adalah sbb.
𝑟𝑎𝑠𝑖𝑜 𝑘𝑜𝑚𝑝𝑟𝑒𝑠𝑖 = 𝑏𝑒𝑠𝑎𝑟 𝑑𝑎𝑡𝑎 𝑡𝑒𝑟𝑒𝑑𝑢𝑘𝑠𝑖
𝑑𝑎𝑡𝑎 𝑠𝑒𝑏𝑒𝑙𝑢𝑚 𝑘𝑜𝑚𝑝𝑟𝑒𝑠𝑖× 100% =
96 − 32
96× 100%
= 64
96× 100% = 66,67%
Jadi besar rasio kompresi yang dihasilkan jika pesan “jaya berjaya” dikompresi menggunakan Huffman
Coding adalah 66,67%.
SOLUSI QUIZ#2
Soal:
Untuk nomor 4-5 digunakan string source “mana makan malam”
4. Average length kode yang dihasilkan dari Minimum Huffman Coding adalah 2,375 bits/sample
(lengkap dengan satuannya)
5. Redundancy yang dihasilkan dari Shanon Fano Coding adalah 0,094 bits/sample (lengkap dengan
satuannya)
Pembahasan:
4. P(m) = 4/16, P(a) = 6/16, P(n) = 2/16, P(_) = 2/16, P(k) = P(l) = 1/16
Menggunakan Minimum Variance Huffman Coding, ingat kesepakatan rulenya: probabilitas descending,
jika sama nilainya maka indeks huruf descending juga (asumsi indeks spasi itu sebelum indeks huruf ‘a’).
n 2/16
a 6/16
m 4/16
_ 2/16
l 1/16
k 1/16
x1 2/16‘1’
‘0’
a 6/16
m 4/16
x1 2/16
n 2/16
_ 2/16
x2 4/16‘1’
‘0’
a 6/16
x2 4/16
m 4/16
x1 2/16
x3 6/16‘1’
‘0’
x3 6/16
a 6/16
x2 4/16
x4 10/16‘1’
‘0’
x4 10/16
x3 6/16
1‘1’
‘0’
Maka kita akan dapatkan codeword sbb:
a = 11 _ = 100
m = 01 l = 001
n = 101 k = 000
Jika ni menunjukkan panjang bit karakter i, maka Average Length kode yang dihasilkan oleh Minimum
Variance Huffman Coding di atas adalah sbb.
𝐴𝑣. 𝐿𝑒𝑛𝑔𝑡ℎ = 𝑃(𝑚) ∗ 𝑛𝑚 + 𝑃(𝑎) ∗ 𝑛𝑎 + 𝑃(𝑛) ∗ 𝑛𝑛 + 𝑃(_) ∗ 𝑛_ + 𝑃(𝑘) ∗ 𝑛𝑘 + 𝑃(𝑙) ∗ 𝑛𝑙
= 4
16∗ 2 +
6
16∗ 2 +
2
16∗ 3 +
2
16∗ 3 +
1
16∗ 3 +
1
16∗ 3
= 8 + 12 + 6 + 6 + 3 + 3
16=
38
16
= 2,375 𝑏𝑖𝑡/𝑠𝑎𝑚𝑝𝑙𝑒
5. P(m) = 4/16, P(a) = 6/16, P(n) = 2/16, P(_) = 2/16, P(k) = P(l) = 1/16
Menggunakan Shannon-Fano Coding, ingat kesepakatan rulenya: probabilitas descending, jika sama
nilainya maka indeks huruf ascending (asumsi indeks spasi itu sebelum indeks huruf ‘a’).
SOLUSI QUIZ#2
a6/16
l1/16
k1/16
n2/16
_2/16
m4/16
a6/16
m4/16
l1/16
k1/16
n2/16
_2/16
a6/16
m4/16
n2/16
_2/16
l1/16
k1/16
_2/16
n2/16
k1/16
l1/16
Maka kita akan dapatkan codeword sbb:
a = 00 _ = 100
m = 01 l = 111
n = 101 k = 110
Untuk menghitug Redundancy, maka kita perlu menghitung entropi message “mana makan malam”
terlebih dahulu.
Entropi pesan “mana makan malam” adalah sbb.
𝐻 = −[𝑃(𝑚) ∗ log2 𝑃(𝑚) + 𝑃(𝑎) ∗ log2 𝑃(𝑎) + 𝑃(𝑛) ∗ log2 𝑃(𝑛) + 𝑃(_) ∗ log2 𝑃(_) + 𝑃(𝑘)
∗ log2 𝑃(𝑘) + 𝑃(𝑙) ∗ log2 𝑃(𝑙)]
= − [4
16∗ log2
4
16+
6
16∗ log2
6
16+
2
16∗ log2
2
16+
2
16∗ log2
2
16+
1
16∗ log2
1
16+
1
16∗ log2
1
16]
= − [1
4∗ (−2) +
3
8∗ (−1,415) +
1
8∗ (−3) +
1
8∗ (−3) +
1
16∗ (−4) +
1
16∗ (−4)]
= −(−0,5 − 0,531 − 0,375 − 0,375 − 0,25 − 0,25)
= 2,281 𝑏𝑖𝑡/𝑠𝑎𝑚𝑝𝑙𝑒
Jika ni menunjukkan panjang bit karakter i, maka Average Length kode yang dihasilkan oleh Shannon-
Fano Coding di atas adalah sbb.
𝐴𝑣. 𝐿𝑒𝑛𝑔𝑡ℎ = 𝑃(𝑚) ∗ 𝑛𝑚 + 𝑃(𝑎) ∗ 𝑛𝑎 + 𝑃(𝑛) ∗ 𝑛𝑛 + 𝑃(_) ∗ 𝑛_ + 𝑃(𝑘) ∗ 𝑛𝑘 + 𝑃(𝑙) ∗ 𝑛𝑙
= 4
16∗ 2 +
6
16∗ 2 +
2
16∗ 3 +
2
16∗ 3 +
1
16∗ 3 +
1
16∗ 3
= 8 + 12 + 6 + 6 + 3 + 3
16=
38
16
= 2,375 𝑏𝑖𝑡/𝑠𝑎𝑚𝑝𝑙𝑒
Maka Redundancy kode Shannon-Fano yang dihasilkan adalah:
𝑅𝑒𝑑𝑢𝑛𝑑𝑎𝑛𝑐𝑦 = 𝐴𝑣. 𝐿𝑒𝑛𝑔𝑡ℎ − 𝐸𝑛𝑡𝑟𝑜𝑝𝑖 =(2,375 − 2,281)𝑏𝑖𝑡𝑠
𝑠𝑎𝑚𝑝𝑙𝑒= 0,094 𝑏𝑖𝑡𝑠/𝑠𝑎𝑚𝑝𝑙𝑒
SOLUSI QUIZ#2
Soal:
Untuk nomor 6-8, terdapat source A = {a, w, y, z} dengan probabilitas setiap simbol adalah: P(a) = 0.7, P(w)
= 0.1, P(y) = 0.15, dan P(z) = 0.05.
6. Jika digunakan Extended Huffman Coding 2 simbol, diperoleh rangkaian (sequence) simbol baru
sebanyak 16 simbol.
7. Besar probabilitas simbol wa adalah 0,07
8. Codeword untuk simbol wa adalah 1110
Pembahasan:
6. Menggunakan Extended Huffman Coding pada prinsipnya algoritma yang digunakan persis sama dengan
standard Huffman Coding, hanya representasi simbol yang akan dicarikan codewordnya yang berbeda.
Pada Extended Huffman Coding 2 simbol, simbol yang akan dicarikan codewordnya merupakan
sequence atau rangkaian 2 simbol yang ada pada source.
Jadi untuk source A = {a, w, y, z}, akan diperoleh 4 x 4 buah = 16 buah sequence simbol, yaitu {aa, aw,
ay, az, wa, ww, wy, wz, ya, yw, yy, yz, za, zw, zy, zz}.
Probabilitas masing-masing sequence simbol adalah sebagai berikut.
Sequence simbol Probabilitas Sequence simbol Probabilitas
aa 0,7 x 0,7 = 0,49 ya 0,15 x 0,7 = 0,105
aw 0,7 x 0,1 = 0,07 yw 0,15 x 0,1 = 0,015
ay 0,7 x 0,15 = 0,105 yy 0,15 x 0,15 = 0,0225
az 0,7 x 0,05 = 0,035 yz 0,15 x 0,05 = 0,0075
wa 0,1 x 0,7 = 0,07 za 0,05 x 0,7 = 0,035
ww 0,1 x 0,1 = 0,01 zw 0,05 x 0,1 = 0,005
wy 0,1 x 0,15 = 0,015 zy 0,05 x 0,15 = 0,0075
wz 0,1 x 0,05 = 0,005 zz 0,05 x 0,05 = 0,0025
Menggunakan Extended Huffman Coding, ingat pada prinsipnya sama dengan standard Huffman Coding,
kesepakatan rulenya: probabilitas descending, jika sama nilainya maka indeks huruf descending juga
(asumsi indeks spasi itu sebelum indeks huruf ‘a’).
SOLUSI QUIZ#2
ay 0.105
aa 0.49
ya 0.105
x1 0.0075‘1’
‘0’
x2 0.0125‘1’
‘0’
x3 0.015‘1’
‘0’
x4 0.0225‘1’
‘0’
wa 0.07
aw 0.07
az 0.035
za 0.035
yy 0.0225
yw 0.015
wy 0.015
ww 0.01
zy 0.0075
yz 0.0075
zw 0.005
wz 0.005
zz 0.0025
ay 0.105
aa 0.49
ya 0.105
wa 0.07
aw 0.07
az 0.035
za 0.035
yy 0.0225
yw 0.015
wy 0.015
ww 0.01
zy 0.0075
yz 0.0075
x1 0.0075
zw 0.005
ww 0.01
zy 0.0075
yz 0.0075
ay 0.105
aa 0.49
ya 0.105
wa 0.07
aw 0.07
az 0.035
za 0.035
yy 0.0225
yw 0.015
wy 0.015
x2 0.0125
ww 0.01
ay 0.105
aa 0.49
ya 0.105
wa 0.07
aw 0.07
az 0.035
za 0.035
yy 0.0225
yw 0.015
wy 0.015
x2 0.0125
x3 0.015
yw 0.015
wy 0.015
ay 0.105
aa 0.49
ya 0.105
wa 0.07
aw 0.07
az 0.035
za 0.035
yy 0.0225
x4 0.0225
x3 0.015
yy 0.0225
ay 0.105
aa 0.49
ya 0.105
wa 0.07
aw 0.07
az 0.035
za 0.035
x5 0.03
x4 0.0225
yw 0.015‘1’
‘0’
x5 0.03
‘1’
‘0’
x6 0.0375
ay 0.105
aa 0.49
ya 0.105
wa 0.07
aw 0.07
az 0.035
za 0.035
x6 0.0375
yy 0.0225
x5 0.03
SOLUSI QUIZ#2
‘1’
‘0’
x7 0.0525
ay 0.105
aa 0.49
ya 0.105
wa 0.07
aw 0.07
az 0.035
za 0.035
x6 0.0375
yy 0.0225
x5 0.03
ay 0.105
aa 0.49
ya 0.105
wa 0.07
aw 0.07
x7 0.0525
az 0.035
za 0.035
x6 0.0375
‘1’
‘0’
x8 0.07
ay 0.105
aa 0.49
ya 0.105
wa 0.07
aw 0.07
x8 0.07
x7 0.0525
x6 0.0375
‘1’
‘0’
x9 0.09
ay 0.105
aa 0.49
ya 0.105
x9 0.09
wa 0.07
aw 0.07
x8 0.07
‘1’
‘0’
x10 0.14
aa 0.49
x10 0.14
ay 0.105
ya 0.105
x9 0.09
wa 0.07
‘1’
‘0’
x11 0.16
aa 0.49
x11 0.16
x10 0.14
ay 0.105
ya 0.105‘1’
‘0’
x12 0.21
aa 0.49
x12 0.21
x11 0.16
x10 0.14
‘1’
‘0’
x13 0.3
aa 0.49
x13 0.3
x12 0.21
‘1’
‘0’
x14 0.51
x14 0.51
aa 0.49
1‘1’
‘0’
Maka kita akan dapatkan codeword sbb:
aa = 0 ya = 101
aw = 1101 yw = 111100
ay = 100 yy = 111110
az = 11000 yz = 11111100
wa = 1110 za = 11001
ww = 1111010 zw = 11110110
wy = 1111111 zy =11111101
wz = 111101111 zz = 111101110
SOLUSI QUIZ#2
Soal:
9. Diketahui string AABCAABCAABCAABC, jika direpresentasikan ke dalam Tunstall Code 3 bit, akan
dihasilkan sequence simbol sebanyak 7 buah, yaitu C, AA, AB, AC, BA, BB, dan BC.
Pembahasan:
P(A) = 8/16 = ½ , P(B) = 4/16 = ¼ , P(C) = 4/16 = ¼
Source data terdiri atas 3 simbol yaitu A, B, dan C (urutan indeks didasarkan alphabetical order), maka N=3.
Jika digunakan Tunstall Coding 3 bit, maka n=3. Sehingga nilai integer K (batas pengulangan) adalah sbb.
𝑁 + 𝐾 ∗ (𝑁 − 1) ≤ 2𝑛
3 + 𝐾 ∗ (3 − 1) ≤ 23
3 + 2𝐾 ≤ 8
2𝐾 ≤ 8 − 3
2𝐾 ≤ 5
𝐾 ≤ 2,5
K adalah nilai integer maksimum, sehingga diperoleh K = 2. Ini berarti banyaknya pengulangan (iterasi)
adalah 2x, atau banyaknya simbol yang dikeluarkan/dicoret adalah 2 buah.
Karena nilai K = 2, maka total banyaknya simbol yang dihasilkan (= banyaknya codeword yang dihasilkan)
adalah sbb.
𝑁 + 𝐾 ∗ (𝑁 − 1) = 3 + 2 ∗ (3 − 1) = 3 + 2 ∗ 2 = 3 + 4 = 7 𝑏𝑢𝑎ℎ 𝑠𝑖𝑚𝑏𝑜𝑙
Karena pada soal tidak hanya ditanyakan banyaknya simbol yang dihasilkan, maka tetap perlu menjalankan
algoritma Tunstall Codingnya untuk mengetahui list simbol yang dihasilkan.
Tunstall Coding:
SOLUSI QUIZ#2
Perhatikan rule yang dipakai untuk “mengeluarkan” simbol
Simbol yang “dikeluarkan” adalah simbol dengan probabilitas
tertinggi
Jika ada lebih dari 1 simbol yang probabilitasnya sama-sama
tertinggi, maka pilih simbol yang paling dulu muncul di dalam
list simbol
Simbol yang “dikeluarkan” kemudian dirangkaikan dengan
setiap simbol pada source asli secara berurutan sesuai
dengan urutan indeks atau alphabetical ordernya.
Pada soal ini, simbol pada source adalah huruf A, B, C
(urutannya berdasarkan alphabetical order), maka simbol
yang “dikeluarkan” dirangkaikan dengan A-B-C secara
berurutan satu per satu.
Jadi pada Tunstall Coding 3 bit di atas, akan diperoleh 7 buah sequence simbol, yaitu C, AA, AB, AC, BA, BB,
dan BC. Sehingga pesan AABCAABCAABCAABC akan diidentifikasi sebagai rangkaian simbol AA-BC-AA-BC-
AA-BC-AA-BC.
Penentuan codeword untuk ketujuh simbol di atas adalah dengan memplot fixed-length codeword 3 bit
mulai dari 000 – 111 (diambil 7 buah), yaitu sbb.
Sequence Simbol Codeword
C 000
AA 001
AB 010
AC 011
BA 100
BB 101
BC 110
A
Sequence Simbol
Probabilitas
B
C
½
¼
¼
AA
AB
AC
½ * ½ = ¼
½ * ¼ = 1/8
½ * ¼ = 1/8
BA
BB
BC ¼ * ¼ = 1/16
¼ * ¼ = 1/16
¼ * ½ = 1/8
SOLUSI QUIZ#2
Soal:
Untuk nomor 10-11, terdapat string “ada ada saja”.
10. Jika didesain Tunstall Code 4 bit untuk string di atas, maka batasan pengulangan K akan bernilai 2 dan
akan dihasilkan codeword Tunstall sebanyak 13 buah.
11. Average length yang dihasilkan adalah 4 bits/simbol (lengkap dengan satuannya)
Pembahasan:
10. Simbol yang ada pada source data adalah {_, a, d, j, s}, asumsi indeks spasi lebih awal daripada
alphabet, sehingga N = 5.
Untuk Tunstall Code 4 bit, maka n = 3. Sehingga nilai K dapat dihitung sbb.
𝑁 + 𝐾 ∗ (𝑁 − 1) ≤ 2𝑛
5 + 𝐾 ∗ (5 − 1) ≤ 24
5 + 4𝐾 ≤ 16
4𝐾 ≤ 16 − 5
4𝐾 ≤ 11
𝐾 ≤ 2,75
K adalah nilai integer maksimum, sehingga diperoleh K = 2.
Karena nilai K = 2, maka total banyaknya simbol yang dihasilkan (= banyaknya codeword yang
dihasilkan) adalah sbb.
𝑁 + 𝐾 ∗ (𝑁 − 1) = 5 + 2 ∗ (5 − 1) = 5 + 2 ∗ 4 = 5 + 8 = 13 𝑏𝑢𝑎ℎ 𝑠𝑖𝑚𝑏𝑜𝑙
Karena pada soal yang ditanyakan hanya banyaknya codeword Tunstall yang dihasilkan, maka cukup
melakukan perhitungan sampai sini, tidak perlu menjalankan algoritma Tunstall Codingnya.
11. Karena Tunstall Code adalah fix-length code, maka untuk Tunstall Code 4 bit pasti memiliki average
length 4 bits/simbol.
SOLUSI QUIZ#2
Soal:
12. Binary code untuk nilai integer 26 menggunakan Golomb Code dengan parameter m = 5 adalah
11111001
Pembahasan:
12. Untuk nilai integer 26 dan nilai m = 5, diperoleh nilai q dan r sbb.
𝑞 = 26 𝑑𝑖𝑣 5 = 5
𝑟 = 26 𝑚𝑜𝑑 5 = 1
Maka codeword untuk q = 111110 (menggunakan unary code).
Untuk menentukan codeword r, maka dilakukan langkah-langkah perhitungan sbb.
Karena nilai m = 5 bukan merupakan bilangan kelipatan pangkat 2, maka codeword r ditentukan
oleh batasan representasi s, yaitu:
𝑠 = 2⌈log2 𝑚⌉ − 𝑚 = 2⌈log2 5⌉ − 5 = 23 − 5 = 8 − 5 = 3
Karena nilai r = 1 dan nilai s = 3, maka r < s, sehingga:
Panjang bit codeword r = ⌊log2 𝑚⌋ = ⌊log2 5⌋ = 2 𝑏𝑖𝑡𝑠
Codeword r = representasi biner dari r = representasi biner dari 1 = 01 (perhatikan panjangnya 2
bit)
Jadi Golomb Code untuk nilai integer 26 adalah penggabungan codeword q dan codeword r yaitu
11111001.
SOLUSI QUIZ#2
Soal:
Untuk nomor 13-17, terdapat message “32”.
13. Jika nilai “32” tersebut disimpan dalam bentuk string tanpa kompresi, jumlah bit yang diperlukan
untuk merepresentasikan pesan tersebut adalah 16 bits.
14. Jika nilai “32” tersebut disimpan dalam bentuk tipe data integer (asumsi data integer disimpan dalam
16 bit), jumlah bit yang diperlukan untuk merepresentasikan pesan tersebut adalah 16 bits.
15. Jika nilai “32” tersebut dikompresi dengan golomb coding dengan parameter m = 5, jumlah bit yang
diperlukan untuk merepresentasikan pesan tersebut adalah 9 bits.
16. Rasio kompresi yang dihasilkan oleh Golomb Code dibandingkan representasi String ASCII adalah
43,75% (dalam prosen)
17. Rasio kompresi yang dihasilkan oleh Golomb Code dibandingkan representasi integer adalah 43,75%
(dalam prosen)
Pembahasan:
13. Jika nilai “32” disimpan dalam bentuk string, berarti nilai “32” diidentifikasi sebagai rangkaian 2 buah
karakter yang masing-masingnya direpresentasikan dalam bentuk ASCII yaitu 8 bits per karakter.
Sehingga jumlah bit yang merepresentasikan nilai “32” tersebut adalah 2 x 8 bits = 16 bits.
14. Jika nilai “32” disimpan dalam bentuk tipe data integer (asumsi data integer disimpan dalam 16 bit),
maka jumlah bit yang merepresentasikan nilai “32” tersebut adalah 16 bits. Perhatikan bahwa nilai
“32” diidentifikasi sebagai 1 buah data integer.
15. Jika nilai “32” dikompresi dengan golomb coding menggunakan parameter m = 5, maka representasi
codewordnya ditentukan sbb.
𝑞 = 32 𝑑𝑖𝑣 5 = 6
𝑟 = 32 𝑚𝑜𝑑 5 = 2
Maka codeword untuk q = 1111110 (menggunakan unary code).
Untuk menentukan codeword r, maka dilakukan langkah-langkah perhitungan sbb.
Karena nilai m = 5 bukan merupakan bilangan kelipatan pangkat 2, maka codeword r ditentukan
oleh batasan representasi s, yaitu:
𝑠 = 2⌈log2 𝑚⌉ − 𝑚 = 2⌈log2 5⌉ − 5 = 23 − 5 = 8 − 5 = 3
Karena nilai r = 2 dan nilai s = 3, maka r < s, sehingga:
Panjang bit codeword r = ⌊log2 𝑚⌋ = ⌊log2 5⌋ = 2 𝑏𝑖𝑡𝑠
Codeword r = representasi biner dari r = representasi biner dari 2 = 10 (perhatikan panjangnya 2
bit)
Jadi Golomb Code untuk nilai integer 32 adalah penggabungan codeword q dan codeword r yaitu
111111010, dengan total banyaknya bits adalah 9 bits.
16. Rasio kompresi yang dihasilkan oleh Golomb Code dibandingkan representasi String ASCII untuk nilai
“32” adalah sbb.
Data sebelum kompresi (representasi ASCII) = 16 bits
Data setelah kompresi (Golomb Coding) = 9 bits
𝑅𝑎𝑠𝑖𝑜 𝑘𝑜𝑚𝑝𝑟𝑒𝑠𝑖 = 𝑑𝑎𝑡𝑎 𝑦𝑎𝑛𝑔 𝑡𝑒𝑟𝑒𝑑𝑢𝑘𝑠𝑖
𝑑𝑎𝑡𝑎 𝑎𝑤𝑎𝑙 𝑠𝑒𝑏𝑒𝑙𝑢𝑚 𝑘𝑜𝑚𝑝𝑟𝑒𝑠𝑖× 100% =
16 − 9 𝑏𝑖𝑡𝑠
16 𝑏𝑖𝑡𝑠× 100% = 43,75%
17. Rasio kompresi yang dihasilkan oleh Golomb Code dibandingkan representasi integer untuk nilai “32”
adalah sbb.
SOLUSI QUIZ#2
Data sebelum kompresi (representasi integer) = 16 bits
Data setelah kompresi (Golomb Coding) = 9 bits
Karena jumlah bitsnya sama dengan nomor 16, maka diperoleh rasio kompresi yang sama yaitu
43,75%.