Anigif - Example GIF File - Image Coding

Image Coding

The image pixel colors, scanned horizontally from top left, are converted by LZW encoding to codes that are then mapped into bytes for storing in the file. For the sample image above the reversible mapping between 9-bit codes and bytes is shown below.

9-bit binary Bytes (hex) (hex) 00000000 00 100 0101000|1 51 028 111111|00 FC 0FF 00011|011 1B 103 0010|1000 28 102 011|10000 70 103 10|100000 A0 106 1|1000001 C1 107 10000011 83 00000001 01 101 0000000|1 01

A slight compression is evident: pixel colors defined initially by 15 bytes are exactly represented by 12 code bytes including control codes. The encoding process that produces the 9-bit codes is shown below. A local string accumulates pixel color numbers from the palette, with no output action as long as the local string can be found in a code table. There is special treatment of the first two pixels that arrive before the table grows from its initial size by additions of strings. After each output code, the local string is initialized to the latest pixel color (that could not be included in the output code).

Table 9-bit string --> code code Action #0 | 000h Initialize root table of 9-bit codes palette | : colors | : #255 | 0FFh clr | 100h end | 101h | 100h Clear Pixel Local | color Palette string | BLACK #40 28 | 028h 1st pixel always to output WHITE #255 FF | String found in table 28 FF | 102h Always add 1st string to table FF | Initialize local string WHITE #255 FF FF | String not found in table | 0FFh - output code for previous string FF FF | 103h - add latest string to table FF | - initialize local string WHITE #255 FF FF | String found in table BLACK #40 FF FF 28 | String not found in table | 103h - output code for previous string FF FF 28 | 104h - add latest string to table 28 | - initialize local string WHITE #255 28 FF | String found in table WHITE #255 28 FF FF | String not found in table | 102h - output code for previous string 28 FF FF | 105h - add latest string to table FF | - initialize local string WHITE #255 FF FF | String found in table WHITE #255 FF FF FF | String not found in table | 103h - output code for previous string FF FF FF | 106h - add latest string to table FF | - initialize local string WHITE #255 FF FF | String found in table WHITE #255 FF FF FF | String found in table WHITE #255 FF FF FF FF | String not found in table | 106h - output code for previous string FF FF FF FF| 107h - add latest string to table FF | - initialize local string WHITE #255 FF FF | String found in table WHITE #255 FF FF FF | String found in table WHITE #255 FF FF FF FF | String found in table No more pixels 107h - output code for last string 101h End

For clarity the table is shown above as being built of strings of increasing length. That scheme can function but the table consumes an unpredictable amount of memory. Memory can be saved in practice by noting that each new string to be stored consists of a previously stored string augmented by one character. It is economical to store at each address only two words: an existing address and one character.

The LZW algorithm requires a search of the table for each pixel. A linear search through up to 4096 addresses would make the coding slow. In practice the codes can be stored in order of numerical value; this allows each search to be done by a SAR (Successive Approximation Register, as used in some ADCs), with only 12 magnitude comparisons. For this efficiency an extra table is needed to convert between codes and actual memory addresses; the extra table upkeeping is needed only when a new code is stored which happens at much less than pixel rate.