Hi Everyone,

Post your solutions to the Oct 31 In-Class Exercise to this thread.

Best,

Chris

//Yaoyan Xi

a)Delta_List:

89 12 11 10 8 15

b) r-code

89 = 0000001 011001 12 = 0001 100 11 = 0001 011 10 = 0001 010 8 = 0001 000 15 = 0001 111

c) Golomb code N = 200, Nt = 6 M_opt =ceiling of -log(394/200)/log(194/200) = ceiling of 22.26 = 23

<nowiki> posting list -> [89, 101, 112, 122, 130, 145] (a) Δ-list -> [89, 12, 11, 10, 8, 15] (b) γ-code -> [0000001 011001, 0001 100, 0001 011, 0001 010, 0001 000, 0001 111] (c) N = 200 , Nt = 6 Nt/N = 6/200 = 0.03 M = ceil -log2 (2-0.03)/log2(1-0.03) = ceil 22.26 = 23

q(89)= 3, r(89)=19 -> 0001 10011 
q(12)= 0, r(12)=12  -> 1 1100
q(11)= 0, r(11)=11   -> 1 1011
q(10)= 0, r(10)=10 -> 1 1010
q(8)= 0, r(8)=8      -> 1 1000
q(15)= 0, r(15)=15 -> 1 1111

</nowiki>

<pre> a) [89, 12, 11, 10, 8, 15] b) 89 -> 101 1001 -> 000001 011001 12 -> 1100 -> 001 100 11 -> 1011 -> 001 011 10 -> 1010 -> 001 010 8 -> 1000 -> 001 000 15 -> 1111 -> 001 111 c) M = log(2 - 6/200) / -log(1 - 6/200) = 22.26 -> 23 q(89) + 1 = (89 - 1) / 23 + 1 -> 3 + 1 -> 0001 r(89) = (89 - 1) % 23 -> 19 -> 1 0011 q(12) + 1 = (12 - 1) / 23 + 1 -> 0 + 1 -> 1 r(12) = (12 - 1) % 23 = 11 -> 1011 q(11) + 1 = (11 - 1) / 23 + 1 -> 0 + 1 -> 1 r(11) = (11 - 1) % 23 = 10 -> 1010 q(10) + 1 = (10 - 1) / 23 + 1 -> 0 + 1 -> 1 r(10) = (10 - 1) % 23 = 9 -> 1001 q(8) + 1 = (8 - 1) / 23 + 1 -> 0 + 1 -> 1 r(8) = (8 - 1) % 23 = 7 -> 0111 q(15) + 1 = (15 - 1) / 23 + 1 -> 0 + 1 -> 1 r(15) = (15 - 1) % 23 = 14 -> 1110 </pre>

delta list = 89, 12, 11, 10, 8, 15

gamma code 0000001011001 0001100 0001011 0001010 0001000 0001111

Golumb code

M = -log(2-0.03) / log(1-0.03) = -log(1.97) /log(0.97) = - 0.295 / -0.0133 = ceil(22.18) = 23

q(k) = floor(k-1/M), r(k) = (k-1) mod M

k . q(k) . r(k) . Golomb Code 89 3 19 0001 10011 12 . 0 12 1 1011 11 . 0 11 1 1010 10 0 10 1 1001 8 0 8 1 0111 15 0 15 1 1110

<pre> a) Δ-list = [89, 12, 11, 10, 8, 15] b) γ-code 89 0000001 011001 12 0001 100 11 0001 011 10 0001 1010 8 0001 000 15 0001 111

c) Golomb code M_opt= [(log⁡(2- N_t/N))/(-log⁡(1- N_t/N))]= [(log⁡(2- 6/200))/(-log⁡(1- 6/200))]=22.26=23 q(k)= (k-1)/M,r(k)=(k-1)modM q(89)= 3,r(89)=19 q(12)= 0,r(12)=12 q(11)= 0,r(11)=11 q(10)= 0,r(10)=10 q(8)= 0,r(8)=8 q(15)= 0,r(15)=15 89 0001 10011 12 1 1100 11 1 1011 10 1 1010 8 1 1000 15 1 1111

</pre>

<pre> (a) Δ(L) = [89, 12, 11, 10, 8, 15] (b) [0000001 011001, 0001 100, 0001 011, 0001 010, 0001 000, 0001 111] (c) M = ceil (log(1.97) / -log(.97)) = 23 q(k) = floor((k-1) / M) q(89) = 3 q(12) = 0 q(11) = 0 q(10) = 0 q(8) = 0 q(15) = 0

r(k) = (k-1) mod M r(89) = 19 r(12) = 11 r(11) = 10 r(10) = 9 r(8) = 7 r(15) = 14

Golomb code = q(k+1) in unary followed by r(k) in binary 00001 0011 01 011 01 010 01 001 01 11 01 110 </pre>

1. Δ-list = [89, 12, 11, 10, 8, 15]
2. γ-code for the above

89 - 0000001011001

12 - 0001100

11 - 0001011

10 - 0001010

8 - 0001000

15 - 0001111

γ-code - 0000001011001 0001100 0001011 0001010 0001000 0001111

Edit -- The Golomb code for the number 89 is 0001 10011