Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP6125 Test

(Contribute 30% of marks to your final marks)

1. Consider the figure below, which shows a leaky bucket policer being fed by a stream of packets. The token buffer can hold at most two tokens, and is initially full at New tokens arrive at a rate of one token per slot. The output link speed is such that if two packets obtain tokens at the beginning of a time slot, they can both go to the output link in the same slot. The timing details of the system are as follows: (total: 28 marks)

a. Packets (if any) arrive at the beginning of the slot. Thus in the figure, packets 1, 2, and 3 arrive in slot 0. If there are already packets in the queue, then the arriving packets join the end of the queue. Packets proceed towards the front of the queue in a FIFO manner.

b. The packet queue can hold up to 3 packets, any packets arrive when the queue is full will be discarded.

c. After the arrivals have been added to the queue, if there are any queued packets, one or two of those packets (depending on the number of available tokens) will each remove a token from the token buffer and go to the output link during that slot. Thus, packets 1 and 2 each remove a token from the buffer (since there are initially two tokens) and go to the output link during slot 0.

d. A new token is added to the token buffer if it is not full, since the token generation rate is r = 1 token/slot.

e. Time then advances to the next time slot, and these steps repeat.

Answer the following questions:

1.1 For each time slot, identify the packets that are in the queue and the number of tokens in the bucket, immediately after the arrivals have been processed (step 1 above) but before any of the packets have passed through the queue and removed a token. Thus, for the time slot in the example above, packets 1, 2, and 3 are in the queue, and there are two tokens in the buffer. The last column indicates which packets appear on the output after the token(s) have been removed from the queue. Thus, for the time slot in the example above, packets 1 and 2 appear on the output link from the leaky buffer during slot 0. (12 marks, each black 0.5 mark)

output link from the leaky buffer during slot 0. (12 marks, each black 0.5 mark)

1.2 Repeat question 2.1, but assume token generation rate is r = 2 token/slot. Assume again that the bucket is initially full. (12 marks, each black 0.5 mark)

1.3 Is there any queue buffer overflow in question 2.1 and 2.2? if yes, how can you adjust the leaky bucket parameters (r and b) to eliminate the queue buffer overflow? Assume you cannot change the size of the packet queue size. (4 marks)

Yes, 2.1. and 2.2 has buffer overflow. Packet 6 is discarded. 2 marks

We can adjust b>=3 to solve the issue (suppose initially the bucket is full). 2 marks

2. Consider the figure below. A sender begins sending packetized audio periodically at t=1. The first packet arrives at the receiver at t=8. (Total 14 marks)

2.1 What are the delays (from sender to receiver, ignoring any playout delays) of packets 2 through 8? Note that each vertical and horizontal line segment in the figure has a length of 1, 2, or 3 time units. (5 marks)

The delay of packet 2 is 7 slots.
The delay of packet 3 is 9 slots.
The delay of packet 4 is 8 slots.
The delay of packet 5 is 7 slots.
The delay of packet 6 is 9 slots.
The delay of packet 7 is 8 slots.
The delay of packet 8 is > 8 slots.

 Each wrong deduct 0.5, no answer give 0 marks

2.2 If audio playout begins as soon as the first packet arrives at t=8 the receiver at which of the first eight packets sent will not arrive in time for playout? (3 marks)

Packets 3, 4, 6, 7, and 8 will not be received in time for their playout if playout begins

at t-8.

Each missing, wrong packet deduct 0.5 marks

2.3. If audio playout begins at t=9, which of the first eight packets sent will not arrive in time for playout? (3 marks)

Packets 3 and 6 will not be received in time for their playout if playout begins at t=9.

Each wrong packet deduct 1.5 marks

2.4What is the minimum playout delay at the receiver that results in all of the first eight packets arriving in time for their playout? (3 marks)

No packets will arrive after their playout time if playout time begins at t=10. 3 marks

3. The first 4x4 elements of Discrete Cosine Transform (DCT) transform coefficients F[u, v] of an 8 x 8 pixel block prior to quantisation and the luminance quantisation matrix q[u, v] is given in figure bellow. Total (12 Marks)

F (u,v) =

q(u,v)=

3.1.  Work out the quantized transform block using F'[u, v] = round ( F[u, v] / q[u, v] )  

 (8 marks)

3.2 Explain why the transformed coefficients can be compress (4 marks)?

The transformed coefficients have a lot of zeros at the right bottom parts, using RLE and zig-zag scan, the zeros are connected and easy to compress. (4 marks)

4. Suppose you are going to encode a String with only 4 symbols (letters) “A,B,C,D” using Huffman Coding. In the string, “A” appears 15 times, “B” 3 times, “C” 6 times, “D” 6 times (Total 26 marks)

4.1 Calculate the entropy of this String source. (6 marks)

Entropy formula 2 marks, calculation probability for each letter 2 marks, final result 2 marks

4.2 Working out the Huffman tree (by drawing) and Huffman code for each symbol. (8 marks)

Drawing tree correctly 4 marks, code for each letter 4 marks

4.3 Calculate the average bits needed to encode each symbol using Huffman Coding. (4 marks)

Formula to calculate all bits to all occurrence 2 marks, correct result 2 marks

4.4 Assume you are going to transmit a message “ABCA” using Arithmetic Encoding. Work out the Arithmetic code for the message “ABCA”. (use drawing and detailed calculation to explain your working steps) (8 marks)

Calculate range 2 marks, draw arithmetic steps 4 marks. Showing the final code 2 marks

5. Video coding: (Total 10 marks)

5.1 Briefly explain the concept of GOP and I, P, B frames.  (5 marks)

GoP 2 marks, IBP frame each 1 mark

5.2 Explain the concept of Motion Compensation, and why some frames can be predicted using future frames? (5 marks)

Motion compensation is detecting any object/pattern are appeared in previous or future frames. If yes, we can calculate the movement as motion vector. We can just save the motion vector to increase compression efficiency.  (3 marks)

Sometime a good object /pattern can not be found on the previous frame, but an be found on the next frame. That is the frame (B frame) can be recovered by previous and/or future I/P frame. (2 marks)

6 Audio coding (Total 10 marks)

6.1. What is SQNR, for CD audio it is 16 bits and 44.1KHz sampling rate, what is the SQNR of CD audio? (5 marks)

SQNR is signal to quantization noise ratio, it is represents the ratio of the signal to the quantization error.

For 16 bits CD audio enable a maximum SQNR = 96 dB.

SQNR definition 2 marks, formular to calculate 2 marks, result 1 mark

6.2 What is Differential PCM? Why DPCM can be transmitted at lower bit rate than PCM? (5 marks)

3 marks

Because only dn is transmitted and normally Dn is a small value. So that the transmitted bit can be decreased and save bit rate.

2 marks