The tree at both the encoder and decoder consists of a single node, the NYT node. Therefore, the codeword for the very first symbol that appears is a previously agreed-upon fixed code. After the very first symbol, whenever we have to encode a symbol that is being encountered for the first time, we send the … Read more
The update procedure requires that the nodes be in a fixed order. This ordering is preserved by numbering the nodes. The largest node number is given to the root of the tree, and the smallest number is assigned to the NYT node. The numbers from the NYT node to the root of the tree are … Read more
Huffman coding requires knowledge of the probabilities of the source sequence. If this knowledge is not available, Huffman coding becomes a two-pass procedure: the statistics are collected in the first pass, and the source is encoded in the second pass. In order to convert this algorithm into a one-pass procedure, Faller [24] and Gallagher [23] … Read more
By performing the sorting procedure in a slightly different manner, we could have found a different Huffman code. In the first re-sort, we could place a4 higher in the list, as shown in Table 3.6. Now combine a1 and a3 into a1, which has a probability of 04. Sorting the alphabet a2, a4, a1 and … Read more
This technique was developed by David Huffman as part of a class assignment; the class was the first ever in the area of information theory and was taught by Robert Fano at MIT [22]. The codes generated using this technique or procedure are called Huffman codes. These codes are prefix codes and are optimum for … Read more
The test for unique decodability requires examining the dangling suffixes initially generated by codeword pairs in which one codeword is the prefix of the other. If the dangling suffix is itself a codeword, then the code is not uniquely decodable. One type of code in which we will never face the possibility of a dangling … Read more
The average length of the code is not the only important point in designing a “good” code. Consider the following example adapted from [10]. Suppose our source alphabet consists of four letters a1, a2, a3, and a4, with probabilities P(a1)= 1/ 2 , P(a2) = 1 /4 , and P(a3) = P(a4) = 1 /8 … Read more
One of the most popular ways of representing dependence in the data is through the use of Markov models, named after the Russian mathematician Andrei Andrevich Markov (1856– 1922). For models used in lossless compression, we use a specific type of Markov process called a discrete time Markov chain. The use of the Markov model … Read more
If we know something about the physics of the data generation process, we can use that information to construct a model. For example, in speech-related applications, knowledge about the physics of speech production can be used to construct a mathematical model for the sampled speech process. Sampled speech can then be encoded using this model … Read more