Lab 1: Lossless coding of audio and still images
TaskThe goal of the lab is to make simple random models for some different signals (audio and images), calculate entropies for the models and calculate data rates given Huffman coding of the signals. You don't have to find the actual codewords in the Huffman codes, only the resulting rates are important.
The work should be done in groups of 1 or 2 students.
Examination of the lab is by written report.
Audio signalsThe audio signals consist of two music signals and one speech signal. The music signals are mono, sampled with 44.1 kHz sampling frequency and quantized to 8 bits/sample (256 levels). The speech signal is mono, sampled with 8 kHz sampling frequency and quantized to 8 bits/sample (256 levels).
In Matlab, WAV files can be easily read using the function audioread. It will return a vector of samples, scaled so that they take values between -1 and 1. To get integers between -128 and 127 just multiply the signal by 128.
Entropy estimationTo get an idea of what theoretical performance can be expected, you should estimate some entropies. The entropies to be estimated are H(Xi), H(Xi,Xi+1) (pair entropy) and H(Xi+1 | Xi) (conditional entropy), assuming that the signal can be viewed as a stationary process Xi.
Memoryless Huffman codingCalculate what data rate is achieved when simple Huffman coding of individual samples is done, independent of earlier samples.
If you don't want to write your own Huffman coder, you can use this function (read the program code to understand how it works).
Simple predictive codingIn order to take advantage of the memory (dependance) between neighbouring audio samples, you should do simple predictive coding. First you do a prediction pi and then Huffman coding of the prediction error di = xi-pi, where xi are the audio samples. Try the following two predictors:
- pi = xi-1
- pi = 2*xi-1-xi-2
Compare your data rates with the estimated entropies.
Also listen to the audio signals and comment on how the character of the audio affects the data rate.
Still imagesthe images are greyscale images quantized to 8 bits/pixel, ie each pixel can take values between 0 (black) and 255 (white). There are three images to test:
Entropy estimationTo get an idea of what theoretical performance can be expected, you should estimate some entropies. The entropies to be estimated are H(Xi,j), H(Xi,j,Xi+1,j), H(Xi,j,Xi,j+1) (pair entropy horizontally and vertically), H(Xi+1,j | Xi,j) and H(Xi,j+1 | Xi,j) (conditional entropy horizontally and vertically).
Memoryless Huffman codingCalculate what data rates are achieved when simple Huffman coding of individual pixels is done, independent of surrounding pixels.
Simple predictive codingIn order to take advantage of the memory (dependance) between neighbouring pixels, you should do simple predictive coding. First you do a prediction pij and then Huffman coding of the prediction error dij = xij-pij, where xij are the pixel values. Try the following three predictors:
- pi,j = xi-1,j
- pi,j = xi,j-1
- pi,j = xi-1,j+xi,j-1-xi-1,j-1
Compare the data rates with the estimated entropies.
Comment on how the content of the images affect the rates and entropies.
ExaminationExamination of the lab is by a short written report. Describe how you solved the problems and what your results are. Also include any program code you've written.
Send an electronic version of your report (in PDF format) to Harald. Give the name, person number and email adress of every group member.
DeadlineLab results are reported to Ladok at the same time as exam results, three times a year. If you want to get your points early, you should send in your report no later than May 27th.
Questions?If you have any questions about the lab, contact Harald.
Informationsansvarig: Harald Nautsch
Senast uppdaterad: 2019-03-25