=========================preview======================
(ELEC331)[2011](f)final~ywangag^_73209.pdf
Back to ELEC331 Login to download
======================================================
Final (of ELEC4140), 8:30-11:30 AM, 16th of December 2011, in Room LG1

Remarks: (1) This exam is open ONLY to lecture-notes. (2) Do all five questions.

1. (8 pts) Given a set of 8 symbols S=[s1, s2, , s8], the entropy of S can be computed as


bits/symbol ....812)(log)()(iiispspSH

where p(si) denotes the probability of symbol si. We know that the Huffman coding is based on probabilities of all symbols. Now, try to find one probability distribution so that the corresponding Huffman coding achieves the coding efficiency at 100% exactly (refer to Page 5 of Chapter 2 to find out how the coding efficiency is defined). Compute the entropy for the distribution you found and design the Huffman code.

2. (8 pts) The 2-D discrete cosine transform (DCT) on an N.N image block x(m,n) is defined as (refer to Pages 15 and 17 of Chapter 5 to see more on DCT)


.....................NvnNumnmxvuvuXNnNm2)12(cos2)12(cos),()()(),(1010....

for and . Now, let us assume that the image block is changed as for all m and n where A is a constant. Find out what will happen on X(u,v) for each individual pair (u,v). 1,,0..Nu.
1,,0..Nv.
Anmxnmx..),(),(

3. (8 pts) Refer to Fig. P-3 that contains 10 training data. Please design the optimal VQ (based on these training data) whose codebook has only two codewords. You need to show all necessary steps, such as how do you choose the initial codewords, as well as all iterations.



x1


8 7 6 5 4 3 2 1















Fig. P-3










0 1 2 3 4 5 6 7 8

x0





Then, please code each of the following three new data using your VQ codebook: (2,3), (4,4), and (5,1); and calculate the corresponding quantization error.
4. (8 pts)Lets apply the new three-step search (NTSS) (the search region of 77) on a video sequence of CIF format (288.352), 4:4:4 color format, 30 frames/second, calculate how many MIPS (million instructions per second) are needed in the best and worse cases respectively (in NTSS), where each instruction is defined as +|x-y|, ignoring the boundary effect.



5. (8 pts) Suppose that we have a 44 image shown in Fig. P-5(a). Lets apply a filter bank to decompose this image according to the diagram shown in Fig. P-5(b). The two filters used in Box H or V are defined as and , respectively. Compute the output data from diagram shown in Fig. P-5(b). (Refer to Lecture Notes for understanding the details of Box H or V.) 11()1Hzz...
12()1Hzz....




1






2

a1

a4







3




4




6

5





7




a16

a13



Fig. P-5(a).

Fig. P-5(b).