January 2021

Show a practical situation where compression speed is more important than compression ratio. Decode the string alf_eats_alfalfa by using the encoding results from Exercise 3.10. Assume a two-symbol alphabet with the symbols a and b. Show the first few steps for encoding and decoding the string “ababab…”.

Repeat this calculation for the six pixels 90, 95, 100, 80, 90, and 85. Discuss your results. This variant of DPCM is commonly used for audio compression. In ADPCM the quantization step size adapts to the changing frequency of the sound being compressed. The predictor also has to adapt itself and recalculate the weights according

Scan the 8×8 bitmap of Figure 4.159 using a Hilbert curve and calculate the runs of identical pixels and compare them to the runs produced by RLE. A space-filling curve completely fills up part of space by passing through every point in that part. It does that by changing direction repeatedly. We will only discuss

Show an example of a space-filling curve in one dimension. Several such curves are known and all are defined recursively. A typical definition starts with a simple curve C0, shows how to use it to construct another, more complex curve C1, and defines the final, space-filling curve as the limit of the sequence of curves

Use Table 4.170 to compute the node number of the H4 node whose coordinates are (13, 6). The second approach to Hilbert curve traversal uses Table Ans.43. Orientation #2 of the H2 curve shown in Figure 4.162(b) is traversed in order 1223. The same orientation of the H3 curve of Figure 4.162(c) is traversed in

Show how to apply this method to traversing orientation #1 of Hi. A MATLAB function hilbert.m to compute the traversal of the curve is available at [Matlab 99]. It was written by Daniel Leo Lau (dllau@engr.uky.edu). The call hilbert(4) produces the 4 × 4 matrix 5 6 9 10 4 7 8 11 3 2 13 12  0

What string identifies the gray area of Figure 4.171c. Instead of constantly saying “quadrant, sub quadrant, or sub subquadrant,” we use the term “sub square” throughout this section. In Figure 4.173, state 2 of the graph is represented in terms of itself and of state 4. Show how to represent it in terms of itself

Complete this reconstruction. Before getting to the details of the compression, it may be interesting to understand why Equation (8.1) reconstructs S from L. The following arguments explain why this process works: 1. T is constructed such that F[T[i]] = L[i] for i = 0, . . . , n. 2. A look at the sorted matrix

Show how how T is used to create the encoder’s main output, L and I. Implementing the decoder is straightforward, because there is no need to create n×n matrices. The decoder inputs bits that are Huffman codes. It uses them to create the codes of C, decompressing each as it is created, with inverse move-to-front,

Encode the 64-bit input stream of Exercise 8.12 using the codes of Table 8.25. Encode the 64-bit input stream of Exercise 8.12 using the codes of Table 8.26. This section and the previous one suggest that any number system can be used to construct codes for the run lengths of zero groups. However, number systems