January 2021

Actually, there is something special about 10. We use base-10 numbers because we have ten fingers. There is also something special about the use of 2 as the basis for a number system. What is it? Given a decimal (base 10) or a ternary (base 3) number with k digits, a natural question is; how much information […]

How many bits does it take to express the information included in one trit? We now turn to a transmitter, a piece of hardware that can transmit data over a communications line (a channel). In practice, such a transmitter sends binary data (a modem is a good example). However, in order to obtain general results,

How does the number of groups increase when the group size increases from s bits to s + n bits? A more complex approach to image compression by Huffman coding is to create several complete sets of Huffman codes. If the group size is, e.g., eight bits, then several sets of 256 codes are generated. When a symbol S is to

The group 3 code for a run length of five black pels (0011) is also the prefix of the codes for run lengths of 61, 62, and 63 white pels. Explain this. The Group 3 code has no error correction, but many errors can be detected. Because of the nature of the Huffman code, even

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).