=========================preview======================
(ELEC331)[2010](f)final~ywangag^_55178.pdf
Back to ELEC331 Login to download
======================================================
Final (of ELEC331), 16:30-18:30, 11th of December 2010, in Room LG1
Remarks: (1) This exam is open ONLY to lecture-notes. (2) Choose one between 2 and 3, but do all others.
1. (10 pts) Suppose that we have source (which contains N symbols). The entropy of S can be computed as ],,,[21NsssS..
bits/symbol ....NiiispspSH12)(log)()(
(a) Prove that the entropy will be maximal if and only if all symbols are equally probable, i.e., . Calculate this maximum entropy. )()()(21Nspspsp....
(Hints: and .) ...Niisp11)(
dxxdfxfdxxfd)()(1)(log2.
(b) Construct a special distribution for so that the resulted entropy will be minimal. Calculate this minimum entropy.
2. (10 pts) Lets consider an image patch shown in Fig. P-2. It is seen that all pixel values are equal to - a constant. Now, lets apply 1-D DCT to each column (i.e., 4-point DCT to the first column, 3-point DCT to the second column, 2-point DCT to the third column, and 1-point DCT to the fourth column, respectively). Since each column is a constant line, only the DC component remains non-zero after the DCT. (i) Compute the DC component for each column, , , , and . Next, lets apply a 4-point 1-D (horizontal) DCT to the resulting four DC components (one from each column), and we will find that there are some non-zero AC components. In order to avoid these non-zero AC components, we need to scale , , , and before applying the second DCT, i.e., use a scaling factor , , , and to multiply , , , and , respectively. (ii) Find the scaling factors , , , and so that all AC components become zero. a
1DC
2DC
3DC
4DC
4DC
1.
2.
3.
4.
2DC
3DC
4DC
1DC
a
a
a
a
0
1-D DCT
0
0
a
a
a
0
0
a
a
0
a
Fig. P-2.
Tips: The -point DCT matrix is defined as with N
..NNvucC..,
................0/20/1,2)12(cos,uNuNsNuvscuuvu.
3. (10 pts) Refer to the butterfly structure on Page 28 of Chapter 5 (on Transform Coding) and the definition of ck, k = 1, , 7, on Page 23 of the same chapter, count how many multiplications and how many additions are exactly used in the implementation. Then, lets focus on a single butterfly with the input-output relation given as follows:
(3.1) ....................1010cossinsincosxxyy....
Obviously, there are 4 multiplications and 2 additions in the straightforward implementation. Now, can you derive an equivalent implementation so that the number of multiplications is reduced to 3? Show your implementation structure in details and also count how many additions are used in your new structure. Finally, can you further reduce the number of multiplications?
4. (10 pts) We know that the 3-step search (3SS or TSS) algorithm for motion estimation is applicable to the search region of 77.