1 EE.5351 Digital Video Coding Instructor: K.R.Rao Test #1 (Open Book & Open Notes) June 20, 2006 Student Name: ______________ Student ID: ______________2 1. [15 points] Symbol Probability S1 0.3 S2 0.1 S3 0.35 S4 0.25 (a). Find Huffman code, the Huffman code tree and redundancy (b). Find minimum variance Huffman code, the minimum variance Huffman code tree and redundancy. (c). Comment on the difference between (a) and (b) 2. [15 points] For an alphabet A={a1, a2, a3} with probabilities P(a1)=0.3, P(a2)=0.6, P(a3)=0.1, design a 3-bit Tunstall code. 3. [15 points] Given the probability model in the following table, find the real valued tag for the sequence S1S1S2S3S2. Symbol Probability S1 0.2 S2 0.3 S3 0.534. [20 points] A sequence is encoded using the LZW algorithm and the initial dictionary shown in the table below: Index Entry 1 a 2 b 3 r 4 t The output of the LZW encoder is the following sequence: 3 1 4 6 8 4 2 1 2 5 10 6 11 13 6 Decode this sequence. 5. [15 points] A sequence is encoded using LZ77 algorithm, Given that C(a)=1, C( )=2, C(r)=3, and C(t)=4, decode the following sequence of triples: b <0,0,3> <0,0,1> <0,0,4> <2,6,2> <3,2,2> <0,0,3> <6,4,4> <9,5,4> Assume that the size of the window is 20 and the size of the look-ahead buffer is 10. 6. [20 points] Given a initial dictionary consisting of letters a b r y , encode following message using LZW algorithm: b a b a r a r r a y b y b a r r a y a r b a y b b b b b Index Entry 1 a 2 b 3 r 4 y 5