Click above to get retro games delivered to your door ever month!

 Decoding LZW GIF

 We will now see if we can regenerate the original data stream and
 duplicate the  table looking only at the output data stream generated by
 the  encoder on the previous page. The output data stream is:

          A B 6 8 B 10 9 A A C D 14 16 D C 8 ....

 The  docoding process is harder to see, but easier to implement,  than
 the encoding process. The data is taken in pairs, and a new code is
 assigned to each  pair. The prefix is the left side of the pair, and the
 suffix is  the color  that  the right side of the pair decomposes to from
 the  table.  The decomposition  is done by outputing the suffix of the
 code, and  using  the prefix  as the new code. The process repeats until
 the prefix is  a  single color, and it is output too. The output of the
 decomposition is pushed onto a  stack, and then poped off the stack to the
 display, which  restores  the original  order that the colors were seen by
 the encoder. We will  go  thru the  first  few entries in detail, which
 will hopefully  make  the  process clearer.

 The  first pair is (A B), so the prefix of code 6 is A and the  suffix is
  B, and 6 represents the string AB. The color A is sent to the display.

 The 2nd pair is (B 6), so the prefix of code 7 is B and the suffix  is the
  the last color in the decomposition of code 6. Code 6 decomposes into BA,
  so code 7 = BA, and has a suffix A. The color B is sent to the display.

 The 3rd pair is (6 8) and the next code is 8. How can we decompose  8. We
  know that the prefix of code 8 is 6, but we don't know the suffix. The
  answer  is that we use the suffix of the prefix code; A in this case
  since the suffix of 6 is A. Thus, code 8 = ABA and has a suffix A. We
  decompose 6 to get BA, which becomes AB when we pop it off the stack to
  the display.

 The 4th pair is (8 B), so code 9 has a prefix of 8 and a suffix of  B, and
  code  9  = ABAB. We output ABA to the stack, and pop  it  off  to the
  display as ABA.

 The 5th pair is (B 10) and the next code is 10. The prefix of code  10 is
  B  and the suffix is B (since the prefix is B). Code 10 =  BB,  and we
  output the prefix B to the display.

 The  6th  pair is (10 9) and the next code is 11. Thus the  prefix  of
  code  11 is 10 and the suffix is the last color in the decomposition of
  9, which is A.  Thus code 11 = BBA, And we output BB to the display.

 So  far, we have output the correct colors stream A B AB ABA B  BB  to the
 display, and have duplicated the codes 6 thru 11 in the encoder  table.
 This  process  is  repeated for the whole data stream  to  reconstruct
 the original  color stream and build a table identical to the one built by
 the encoder.  We start the table with codes 0-5 representing the 4 colors,
 the clear  code, and the end code. When we get to code 8, we must  increse
 the code  size  to  5 bits, etc.  See GIFDECOD.GIF for a flow  diagram  of
 the decoding process.