$35
CSE 534 Homework Set #2
Problem (1) (Digital Audio Coding – Masking tone)
Given that the level of a masking tone at the 8th band is 60 dB, and 10 msec after it stops, the
masking effect to the 9th band is 25 dB.
(a) What would MP3 do if the original signal at the 9th band is at 40 dB?
(b) What if the original signal is at 20 dB?
(c) How many bits should be allocated to the 9th band in (a) and (b) above?
Problem (2) (Information Theory – Entropy Coding)
(a) What is the entropy of the image below, where numbers (0, 20, 50, 99) denote the gray
level intensities?
99 99 99 99 99 99 99 99
20 20 20 20 20 20 20 20
0 0 0 0 0 0 0 0
0 0 50 50 50 50 0 0
0 0 50 50 50 50 0 0
0 0 50 50 50 50 0 0
0 0 50 50 50 50 0 0
0 0 0 0 0 0 0 0
(b) Show step by step how to construct the Huffman tree to encode the above four intensity
values in this image. Show the resulting code for each intensity value.
(c) What is the average number of bits needed for each pixel, using your Huffman code?
How does it compare to the entropy computed in (a)?
Problem (3) (Information Theory - Quantization)
Suppose the input source is Gaussian-distributed with zero mean and unit variance – that is,
the probability density function is defined as:
𝑓𝑋
(𝑥) =
1
√2𝜋
𝑒
−
𝑥
2
2
We wish to find a four-level Lloyd-Max quantizer. Let 𝒚𝑖 = [𝑦𝑖
0
, … , 𝑦𝑖
3
] and 𝒃𝑖 = [𝑏𝑖
0
, … , 𝑏𝑖
3
].
The initial reconstruction levels are set to 𝒚0 = [−2, −1, 1, 2]. This source is unbounded, so
the outer two boundaries are +∞ and −∞.
Follow the Lloyd-Max algorithm: the other boundary values are calculated as the mid-points
of the reconstruction values. We now have 𝒃0 = [ −∞, −1.5, 0, 1.5, ∞]. Continue another
iteration for 𝑖 = 1, using the Eq. (2) defined below and find 𝑦1
0
, 𝑦1
1
, 𝑦1
2
, 𝑦1
3
, using integration
shown in Equation (2). Also calculate the squared error 𝒅1: the difference between 𝒚1 and 𝒚0.
Repeat such calculations for three times and output the following parameters: 𝒃3, 𝒚3, and 𝒅3.
Equation (1): 𝑏𝑖
𝑗 =
𝑦𝑖
𝑗+1+𝑦𝑖
𝑗
2
Equation (2): 𝑦𝑖
𝑗 =
∫ 𝑥𝑓𝑋(𝑥)𝑑𝑥
𝑏
𝑖−1
𝑗
𝑏
𝑖−1
𝑗−1
∫ 𝑓𝑋(𝑥)𝑑𝑥
𝑏
𝑖−1
𝑗
𝑏
𝑖−1
𝑗−1
Reference 1: Lloyd-Max Quantizer Algorithm (in depth coverage) [Stuart P. Lloyd, “Least
Squares Quantization in PCM”, IEEE Trans. on Information Theory, Mar. 1982]
Reference 2: Book Chapter: Scalar Quantization (compact coverage); Uploaded to UBlearns.