atial, Temporal, and Statistical Redundancy Huffman Coding The simplest and most commonly seen form of variable-length coding is Huffman; its use is not restricted by patents as arithmetic coding is. To generate a Huffman code requires adhesion to three simple rules: 1. Rank-order the symbols according to their probability of occurrence. 2. Merge the two symbols with the least probability to form a composite symbol and recompute the rank ordering. Trace a path from the root to each leaf node, noting the direction taken at each node. Table 3.3 shows the symbol set EASYZ in the first column, and the probability of occur- rence in the second. The table is used to create the tree shown in Figure 3.13. When the tree has been created, move from right to left and write down a 1 or a 0 depending on which path is taken at each fork. As can be seen in this simple example, symbols that have low probability are often assigned long codewords, leading to inefficiencies. Techniques to overcome this include modified Huffman code (Ghanbari, 1999) or a 2D/3D version of Huffman coding. Arithmetic Coding The principal difficulty of Huffman coding is that it becomes very inefficient if the probabil- ity of the symbol becomes high in part because of its ability to assign only an integer number of bits. Arithmetic coding creates a code string that represents a fractional value, meaning it is not bound by the integer restrictions of Huffman and can achieve theoretical entropy for a given data source. Arithmetic coding is heavily bound by patents, which often restrict its use. Using the same data contained in Table 3.3, the probabilities are arranged into Table 3.3 Characters for Coding and Their Probabilities Symbol Probability Code Symbol Probability 00 A 0.32 010 S 0.20 Fig. 3.13 Huffman tree created from Table 3.3. Chapter 3 Digital Video Transmission Fig. 3.14 Cumulative density function for the symbol set in Table 3.3. 0.6304 0.6944 Fig. 3.15 Coding of the codeword sequence ASZ. 0.69312 E 0.6944 interval between 0 and 1; in other w