Modified Huffman

Mon, 08 Aug 2016 | Voice Gateways

MH is a combination of Huffman and Run Length Encoding types. Developed by David Huffman in 1952, Huffman coding specifies that short bit representations should be used for the most commonly occurring characters. So, the binary coding used to identify a character is inversely proportional to that character's frequency.

Using the alphabet as an example for Huffman encoding, commonly used letters such as T and E would be assigned a smaller bit pattern compared to letters that are rarely used such as X and Z. In the fax encoding world, there are groups of black and white pixels that make up a scan line. Applying Huffman encoding, commonly repeated black and white pixel groupings are given smaller bit representations.

Run Length Encoding (RLE), one of the simplest of all compression algorithms, takes advantage of repetitive data. These consecutive data values are broken into groupings known as runs and replaced with a count number and a value. Fax page images contain many runs of alternating black and white pixels that are a perfect fit for RLE. A simple but efficient encoding algorithm is achieved when RLE is combined with Huffman coding principles.

MH encoding uses special coding tables to compress the bits that compose a scan line. Detailed in ITU-T T.4, these tables are divided into two groupings, terminating codes and make-up codes.

NOTE You can download ITU-T Recommendation T.4 from http://www.itu.int/rec/T-REC-T4/.

Terminating codes address white and black run lengths from 0 to 63 bits with each scan line always beginning with a white run. If the scan line happens to start with a black pixel, a white run length of 0 is coded at the start of the scan line. Figure 2-28 provides an example of how a scan line is coded using MH.

Figure 2-28 MH Coding Example

: of 5 pixels

Because the terminating code tables only cover run lengths of less than 64 bits, make-up codes address longer run lengths. Make-up codes are defined for black and white runs in multiples of 64 bits, and they always precede the terminating codes.

For long run lengths, a scan line is first represented by the make-up code that is equal to or less than the required pixel run. The terminating code then follows the make-up code, addressing the difference in pixels between the required run length and the run covered by the make-up code. Figure 2-29 illustrates the coding of a pixel run that requires a make-up code.

Figure 2-29 MHScan Line Encoding Using a Make-Up Code

Single Scan Line of 1728 Pixels

Black Run White Run of 4 Pixels of 3 Pixels

White Run of 0 Pixels

Black Run of 2 Pixels

White Run of 1719 Pixels

00110101 011 1000 11 011000 01011000

Make-up Code of 1664 Pixels

Terminating Code of 55 Pixels

In addition to the scan line pixel information captured using the MH encoding method, additional bit patterns are needed to form a complete, transmittable scan line. One of these patterns is the unique end of line (EOL) bit sequence; the other is an optional fill pattern. Figure 2-30 shows how scan lines are composed of data, fill, and EOL bit segments.

Figure 2-30 Scan Line Data, Fill, and EOL Segments
AA/VWVW AAAAAAAA/ AAAAAAA/V AAAAAAAA/ AAAAAAAA/ AAAAAAA/V AAAAAAAA/ AAAAAAA/V	Multiple Scan Lines	Data - Binary encoded scan line information composed of black and white pixel runs. Fill - Optional, variable-length string of 0s for scan lines with small amounts of data. EOL - Unique bit pattern indicating the end of a scan line.

Data	Fill EOL Data EOL Data Fill EOL

Individual Scan Lines

The EOL pattern designates the end of a scan line. Consisting of eleven 0s followed by a 1 (000000000001), the EOL is a unique sequence that is never found within the actual scan line data. When a receiver encounters an EOL, the current line is ended and the next one below it starts. In addition, because EOL also allows for the decoding of each line independently, errors affecting a single line are not propagated to other scan lines.

At the end of the fax page, a series of six consecutive EOL patterns occur. Known as a return to control (RTC) signal, these EOLs serve as notification that the fax page has ended and that post-page messaging will now be sent using the V.21 modulation as specified in T.30.

The EOL is also the required pattern that serves as the beginning of the fax page. Figure 2-31 illustrates how EOLs designate the beginning and end of fax pages in addition to terminating each scan line.

Figure 2-31 EOL Bit Patterns Designating the Beginning and End of a Fax Page Fax Page Start (EOL)

EOL

Data

Fill

EOL

Data

Beginning of Fax Page Data

Modified READ

Defined in ITU-T Recommendation T.4, Modified Relative Element Address Designate (READ) or simply MR encoding, exploits the correlation between successive scan lines. Research has shown that a high percentage of consecutive scan lines only contain single pixel transitions to the right or left. Instead of compressing each line independently like MH does, MR establishes reference lines and then encodes any changes that occur between the reference line and the scan lines that follow.

MR encoding builds on the encoding algorithms already established by MH. In fact, reference lines found in MR are actually encoded using the MH algorithm. However, subsequent lines use MR encoding until the next MH encoded reference line is encountered. The parameter that defines how many MR encoded scan lines are present for each MH encoded reference line is known as K.

For normal resolution faxes, K is set to a value of 2 and K-1 is always defined as the number of lines that use 2-Dimensional (2-D), MR coding. The reference lines use 1-Dimenional (1-D) or MH encoding. With a K value of 2, reference lines are encoded every other scan line. Figure 2-33 illustrates the K parameter and how MR encoding appears for the values of K=2 and K=4. Note that K settings of 2 and 4 would never appear on the same page.

Figure 2-33 K Parameter for MR Encoding
	\
AAAAAAA/V AAAAAAAA/ AAAAAAAA/ AAAAAAAA/ AAAAAAAA/ AAAAAAA/V AAAAAAA/V AAAAAAAA/		<— Multiple Scan Lines


MH		MR	MH	MR

For Normal Fax Resolution with K=2

- 1 MH Reference Line

- 1 MR Encoded Line

For Normal Fax Resolution with K=2

- 1 MH Reference Line

- 1 MR Encoded Line

4 Total Scan Lines

For High Fax Resolutions with K=4

- 1 MH Reference Line

- 3 MR Encoded Lines

= 4

4 Total Scan Lines

Low K values prevent any errors in the reference line from propagating too far into subsequent scan lines. In much higher resolutions using MR encoding, the K value can be as high as 24.

As pixel elements change between a reference line and the subsequent scan line, MR defines parameters for determining how the pixel element changes are encoded. Figure 2-34 illustrates and defines these parameters.

Figure 2-34 MR Changing Pixel Element Parameters

Reference Line b1 b2 i I

Coding Line

Cisco Certified Expert

» Voice Gateways