=========================preview======================
(ELEC4140)[2006](f)midterm~dli^_31043.pdf
Back to ELEC4140 Login to download
======================================================
Midterm (of ELEC331), 2nd of November, 2006
Remarks: (1) This is a closed exam. (2) Do all three problems.
1. (8 pts) Given a symbol set S =[s1, s2,", sN ] with N = 8 , the entropy of S can be computed as
N
H (S)= . p(si ) log2 p(si ) bits/symbol
i=1

where p(si ) denotes the probability of symbol si . We know that the Huffman coding is based on probabilities of all symbols. Try to find one probability distribution so that the corresponding Huffman coding achieves the coding efficiency at 100% exactly. Compute the entropy for the distribution you found.
Bonus (4 pts): Try to find a second probability distribution (different from the first one) so that the corresponding Huffman coding also achieves the coding efficiency at 100% exactly. Compute the entropy for the distribution you found.
2.
(6 pts) Suppose that there are X additions and Y multiplications to perform in order to compute a 1-D transform of N points. Now, lets apply this transform to an N N image block in the separate manner, i.e., first along the horizontal direction and then along the vertical direction (or vice versa). Please count how many additions and multiplications would be needed totally to compute the 2-D transform (on an N N image block).

3.
(6 pts) Fill in all entries in the table shown in the next page.