Non-uniform quantization

The next step after the voice is non-uniform quantization. The basic ideal of this quantization is coarsely quantize the large input and finely quantize the smaller input as ear is less sensitive to change at higher amplitude. 

This is the plot of the data sampled by the recorder:

In order to compare non-uniform quantization with uniform one, first we applied uniform quantization to the signal:

From the picture above we can see that the shape of the wave generally kept.

Then we applied nonuniform quantization:

The picture above shows the result of Mu quantization. The shape this really different from the original data. However, there is nothing wrong here. Nonuniform quantization, different from uniform quantization, need an extra step, that is expansion. The expanded data are showed in the picture below and this time it looks much more like the original data.

The picture below shows the distortion of the two quantization method. The latter one represent the nonuniform quantization's distortion. We can see that the non-uniform one will have a less distortion.

11

Testing for infinite precision arithmetic coding

The arithmetic coding was finished recently and this blog is to show the testing of the code.

Since the algorithm of the code was assumed to be infinite precision which means the computer may be out of order if the input is too large, some short inputs were applied as examples to show the correctness of the codes.

1.    For the first example, the inputs are as follow:

A= [0 1 2]; ‘A’ gives the voltages of the voice signal given by the dictionary.

          P= [0.2 0.4 0.4]; ‘P’ gives the probabilities corresponds to the values in A.

          in= [2 1 0]; ‘in’ is input needs to be encoded.

          code=[1 0 1 1 0 0]; ‘code’ is the input to be decoded.

Encoder

The function of encoder is defined as:

And the result was showed as an array with the inputs:

The output [1 0 1 1 0 0] is the binary code for ‘210’ and to be transmitted.

Decoder

The function of decoder is defined as:

And the result was showed as an array with the inputs:

The input of the encoder is identical to the output of the decoder which means the encoder and decoder worked well and matches with each other.

2.    For the second example, the inputs are:

A= [0 1 2 3]; ‘A’ gives the voltages of the voice signal given by the dictionary.

          P= [0.05 0.05 0.5 0.4]; ‘P’ gives the probabilities corresponds to the values in A.

          in= [2 3 2 0]; ‘in’ is input needs to be encoded.

         code=[0 1 1 0 1 1 0 0 0]; ‘code’ is the input to be decoded.

Encoder

And the result was showed as an array with the inputs:

The output [0 1 1 0 1 1 0 0 0] is the binary code for ‘2320’ and to be transmitted.

Decoder

And the result was showed as an array with the inputs:

The input of the encoder is identical to the output of the decoder which means the encoder and decoder worked well and matches with each other.

After the testing of the two examples, the functions of the codes are proved to be correct. However, infinite precision arithmetic coding can only be applied with short input. consequently, it is not able to solve practical problems. 

Week 5

Week 4

This week, we have finish implementing the Huffman encoder and the decoder.

Demonstration of the encoder:

This is the function used to test the encoder:

After running the code, the result is showed below:

In this case, the coding efficiency is 100%(entropy/average length*100%), which is really high. However, in practical situation, the efficiency is not possible to reach 100%.

This is the sequence need to be encode.

The dictionary was established by the function wrote last week.

The output code is shown in the following chart:

The encoded sequence will be transmitted through channel. At the receiver end, the code will be received and should be decoded according to the dictionary.

Following is a test of the decoder:

Add the decoder.

Since the actualsig is generated randomly, hence, when running the code again, the actualsig will be different from the previous encode one. Here we involved 'isequal' function. We only need to make sure that the code before encode and after decode are same. 'isequal' will return 1 if decode and actualsig are same. 

After running the program, it returns 1, which means this function works.

week3

This week, we still focus on the dictionary establishment. Last week, the function has past a test with very small amount of data. However, when we try to test is with a very large amount of data(data from 2 second recording with 44100Hz sampling rate), it will cost more than 5 minutes to generate the dictionary, which will make this program have no practical value. Then we try to improve the algorithm.

The algorithm we use in last week is a direct apply of the basic ideal of Huffman coding involved nested cell. Cell is a data type in Matlab, which can contain many types of other data. For the nested cell used in last weeks function, the top level of the cell may have a length of 88200, and each element of this cell will contain a other CELL with length of 88200 and the second level of cell contains a vector in each of its term. This means the program need to process a 88200^2 of vectors and this will cost a huge amount of computing resource.

However, after a further study of the Huffman code, the symbol it self are not very important during the coding, only the index of the symbols need to be considered. Hence, the problem of nested cell was solved.

After editing and improve of the code, 2 second of voice data will cost only about 0.5 second. If this coding method was combined with high performance hardware, it will have a considerable practical value.

Besides, establish the dictionary, we also continued to design the encode and decode method, but it still not finish yet. Hence there is no result can be showed here.

Huffman coding

the history of Huffman coding

David A. Huffman had a great idea of an algorithm deal with the optimal code of given probability.

The Huffman coding is an entropy encoding algorithm used for lossless data compression, this method developed in 1952 paper " A method for the Construction of Minimum-Redundancy Codes".

procedure of Binary Huffman coding procedure

1. Sort the probability of all source symbols in a descending order.

2. Merge the last two into a new symbol, add their probabilities.

3. Repeat the above steps until only one root left.

4. Code assignment: Traverse the tree from the root to each leaf node, assign 0 to the top branch and 1 to the bottom branch.


(The Huffman algorithm works from leaves to the root of the code tree)

Limitations of Huffman Codes:

- Fixed source probability is required.

- For online computation, one needs extra bits to encode the table.

Application of Huffman codes:

Applications: Huffman Codes are often used

as a “back-end” to other compression 

methods. For example, MP3, JPEG and MPEG

have a “front-end” model (lossy compression) 

and quantisation followed by Huffman coding.

*D.A. Huffman, "A Method for the Construction of Minimum-
Redundancy Codes", Proceedings of the I.R.E., September 1952,

pp 1098–1102. Huffman's original article.