Section 17.7. Case Study: FAX Compression for Transmission

17.7. Case Study: FAX Compression for Transmission

A FAX picture is scanned and compressed in two steps: run-length encoding and then Huffman encoding. First, the transmission of the digital line scan is replaced by the transmission of a quantity count of each of the successive runs of black or white elements.

Consider a document of standard size 8.5 inches by 11 inches. The picture is first partitioned into pixels . If the desired resolution is 200 x 200 pixels per square inch, the total number of pixels per picture is exactly 200 ² x (8.5 x 11) = 37,400,000 pixels.

Fax Process Algorithm

As mentioned earlier, processing a FAX picture requires both run-length coding and Huffman coding. Since black and white always alternate, no special characters are needed to specify that a run is black or white. Thus, the encoded data stream is a string of numbers indicating the lengths of the alternating black and white runs. The algorithm for the first phase is as follows .

1.	Identify the first row out of the n -row document.
2.	At any row i , start at the first pixel of the row. If the pixel is black, assign code 1; if the pixel is white, assign code 0.
3.	At any step of counting j , let X j be the number of consecutive 0s before a 1 appears. Then assign code C c X j 0 to this string of 0s. Do the same thing for 1s, and code it with C c X j 1.

At this point, the document is converted into a number of C _c X _j 0s and C _c X _j 1. In phase 2 of coding, we need the statistics on the frequencies of a certain run-length code in order to compress it further, using the Huffman algorithm. Table 17.3 shows practical statistics for a black-and-white FAX document.

Table 17.3. Statistics on frequency of occurrences for strings obtained after run-length coding for black-and-white FAX document

Number of Repeated Pixels ( C c X )	Huffman Code for White Pixels	Huffman Code for Black Pixels
C c 1	000111	010
C c 2	0011	01
C c 10	00011	1000011
C c 50	00111001	000001101111