3.7 Problems

3.7 Problems

1. 

In the linear quantiser of Figure 3.4, derive the quantisation characteristics in terms of inputs and outputs, for each of the following conditions:

1. th = q = 16

2. th = 0, q = 16.

2. 

The following eight-bit resolution luminance samples are DPCM encoded with the prediction of previous sample:

• 10, 14, 25, 240, 195, 32

If the quantisation is uniform with th = 0 and q = 8,

1. find the reconstructed samples (assume predictor is initialised to zero)

2. calculate the PSNR of the decoded samples.

3. 

A three-bit nonuniform quantiser is defined as:

input	output
if |x| ≤ 4	y = ±2
4 < |x| ≤ 10	y = ±6
10 < |x| ≤ 25	y = ±15
else	y = ±50

If the DPCM data of problem 2 are quantised with this quantiser, find the reconstructed samples and the resulting PSNR value.

4. 

A step function signal with the following eight-bit digitised values:

• 20; 20; 20; 20; 20; 231; 231; 231; 231; 231; 231; 231; 231; 231

is DPCM coded with the nonuniform quantiser of problem 3. Plot the reconstructed samples and identify the positions where slope overload and granular noise occur.

5. 

Determine the elements of the 8 × 8 orthonormal forward and inverse DCT transformation matrices.

6. 

Use the DCT matrix of problem 5 to code the following eight pixels:

35; 81; 190; 250; 200; 150; 100; 21

1. find the transform coefficients

2. why is only one AC coefficient significant?

3. reconstruct the pixels without any quantisation; comment on the reconstructed pixel values.

7. 

The DCT coefficients of problem 6 are linearly quantised with a linear and dead zone quantiser with a step size of th = q = 16. Find the PSNR of the reconstructed pixels.

8. 

Find the PSNR of the reconstructed pixels, if in problem 7 the following coefficients are retained for quantisation and the remaining coefficients are set to zero:

1. DC coefficient

2. DC and the second AC coefficient.

9. 

A 2 x 2 block of pixels in the current frame is matched against a similar size block in the previous frame, as shown in Figure 3.21, within a search window of ±2 pixels horizontally and ±1 pixel vertically. Find the best matched motion vector of the block, if the distortion criterion is based on:

1. mean-squared error

2. mean absolute error.

Figure 3.21: A block of 2 × 2 pixels in the current frame and its corresponding block in the previous frame shown in the shaded area

10. 

For a maximum motion speed of six pixels/frame:

1. calculate the number of operations required by the full search method

2. if each block contains 16 × 16 pixels, calculate the number of multiplications and additions, if the cost function was:

   1. mean-squared error (MSE)

   2. mean absolute error (MAE).

11. 

Repeat problem 10 for the following fast search methods:

1. TDL

2. TSS

3. CSA

4. OSA

12. 

Four symbols of a, b, c and d with probabilities p(a) = 0.2, p(b) = 0.45, p(c) = 0.3 and p(d) = 0.05 are Huffman coded. Derive the Huffman codes for these symbols and compare the average bit rate with that of the entropy.

13. 

In problem 12 a message comprising five symbols cbdad is Huffman coded

1. write down the generated bit stream for this message

2. if there is a single error in the:

   1. first bit

   2. third bit

   3. fifth bit

What is the decoded message in each case?

14. 

If the intervals of [0.0, 0.2), [0.2, 0.7), [0.7, 0.95) and [0.95, 1) are assigned for arithmetic coding of strings of a, b, c and d respectively, find the lower and upper values of the arithmetic coded string of cbcab.

15. 

With the interval of strings of a, b, c defined in problem 14, suppose the arithmetic decoder receives 0.83955:

1. decode the first three symbols of the message

2. decode the first five symbols of the message.

16. 

In arithmetic coding symbols can be decoded using the equation:

where R₀ is the received number and [L_n, U_n) is the interval of the nth symbol in the stream. Use this equation to decode the symbols in problem 15.

17. 

Find the binary arithmetic coding of string cbcab of problem 14.

18. 

Decimal numbers can be represented in binary form by their expansions in powers of 2^-1. Derive the first 11 binary digits of the decimal number 0.83955. Compare your results with that of problem 17.

19. 

The binary digits of the arithmetic coded string cbcab are corrupted at the:

1. first bit

2. third bit

3. fifth bit

Decode the first five symbols of the string in each case.

Answers

1. 

1. |x| ≤ 16; y = 0 16 < |x| ≤ 32; y = ±24 32 < |x| < 48; y = ±40 etc.

2. |x| ≤ 16; y = ±8 16 < |x| ≤ 32; y = ±24 32 < |x| ≤ 48; y = ±40 etc.

2. 

12 16 28 240 196 32 PSNR = 43.4 dB

3. 

6 12 27 77 127 77 PSNR = 10.7 dB

4. 

15 21 19 21 19 69 119 169 219 234 232 230 232 230

5. 

6. 

1. 364 15 -211 -26 -5 38 -2 -1

2. the basis vector of the second AC coefficient matches the input pixels

3. 35 82 190 250 200 150 101 23. Due to mismatch (approximating the cosine elements) some of the input pixels cannot be reconstructed, e.g. 81/82 and 100/101.

7. 

quantised coefficients:	360	0	-216	-24	0	40	0	0
reconstructed pixels: PSNR = 30 dB	30	70	185	250	204	153	104	27

8. 

reconstructed pixels: PSNR = 10.4 dB	128	128	128	128	128	128	128	128
reconstructed pixels: PSNR = 23.4 dB	28	87	169	227	227	169	87	28

9. 

1. mv(-1, -1)

2. mv(-1, -1)

10. 

1. 169

2. 1. multiplications = 256 × 169, additions = 511 × 169

   2. multiplications = 0, additions = 511 × 169

11. 

type	operations	Multiplications	additions
TDL	23	23 × 256	23 × 511
TSS	25	25 × 256	25 × 511
CSA	17	17 × 256	17 × 511
OSA	13	13 × 256	13 × 511

12. 

1. = 010,

2. = 1,

3. = 00,

4. = 011, av bits = 1.8, entropy = 1.72

13. 

1. cbdad = 001011010011

2. 1. 1st bit in error decoded string = babbad

   2. 3rd bit in error, decoded string = ccbbad

   3. 5th bit in error, decoded string = cbcbad

14. 

lower value = 0.83875, upper value = 0.841875

15. 

1. the first three symbols = cbc

2. the first five symbols = cbcab

16. 

the same as 15

17. 

11010110111

18. 

the same as 17

19. 

1. first bit in error = 0.01010110111 = 2^-2 + 2^-4 + 2^-6 + 2^-7 +2^-9 + 2^-10 + 2^-11 = 0.33935546875 which is decoded to string bbacb

2. similarly, with the third bit in error the decimal number would be 0.96435546875, decoded to dbacb

3. with the fifth bit in error, the decimal number is 0.87060546875 and it is decoded to string cbacb.