What is the compression ratio for runs of length one (i.e., strictly alternating pels)? The T4 standard also allows for fill bits to be inserted between the data bits and the EOL. This is done in cases where a pause is necessary, or where the total number of bits transmitted for a scan line must […]

Show an example of a common binary file where different parts may have different bit distributions. As a result, relatively short contexts, in the range of 2 to 10, are used in practice. Any practical algorithm requires a carefully designed data structure that provides fast search and easy update, while holding many thousands of symbols

The escape is just a symbol of the alphabet, reserved to indicate a context switch. What if the data uses every symbol in the alphabet and none can be reserved? A common example is image compression, where a pixel is represented by a byte (256 grayscales or colors). Since pixels can have any values between

What is the number of order-2 and order-3 contexts for an alphabet of size  = 256? Explain the numbers 1/11 and 10/20. Order 0 consists of the five different symbols asnim seen in the input string, followed by an escape, which is assigned frequency 5. Thus, probabilities range from 4/19 (for a) to 5/19 (for the

Suppose that Case 4 has actually occurred (i.e., the 15th symbol to be input was a d). Show the new state of the order-0 contexts. Suppose that Case 4 has actually occurred and the 16th symbol is also a d. How many bits would it take to encode this second d? Show how the results

How can the decoder identify the end marker? When the search algorithm arrives at the right end of the buffer, it shifts the buffer to the left and inputs the next character into the rightmost position of the buffer. The decoder is the reverse of the encoder (symmetric compression).

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