Method for encoding and decoding a digital image

A method for decoding a data stream composed of variable-length binary data code words comprising the steps of:

• (a) generating a table to decode variable-length binary data code words by:
• (1) compiling a list comprising:
• (i) all bit strings to be decoded along with an indication that they are complete code words and an indication of their information content,
• (ii) the null bit string and all unique leading bit combinations in said code words along with an indication that said null bit string and said combinations are incomplete code words;
• (2) selecting a first binary value which will be used to cause a branch within the table;
• (3) sorting the bit strings of said list in ascending order, considering a null bit position as being less that the second binary value and the second binary value as being less than the first binary value;
• (4) forming a table of entries in the order indicated by the sorted list, each table entry containing an indication of whether the associated bit string is a complete or incomplete code word and either the information associated with the complete code word or, for incomplete code words, an indication of the location of the entry corresponding to the bit string associated with the current table entry with a bit of said first binary value appended to it;
• (b) decoding a code word by:
• (1) addressing the entry of said table corresponding to said null bit string;
• (2) examining the next bit in the data stream;
• (3) if said bit is of said first binary value, addressing a new entry of the decoding table as indicated by the table entry currently addressed;
• (4) if said bit is of said second binary value, addressing the next entry in the decoding table;
• (5) examining the newly addressed table entry to determine if a complete code word has been decoded;
• (6) if a complete code word has not been decoded, repeating the steps of examining and addressing for additional bits in the data stream until a complete code word has been decoded;
• (c) repeating said decoding step until all of the code words in the data stream have been decoded.

A method for analyzing a stream of binary data comprising the steps of:

• (a) dividing the stream into units containing a plurality of data bits;
• (b) examining a first unit of said stream by the steps of:
• (1) entering said first unit into the high-order bits of a register of equal or greater length;
• (2) appending a first trailing bit of a first binary value to the data bits in said unit and setting any additional trailing bits needed to fill said register to a second binary value;
• (3) examining the first bit in said unit to determine its binary value;
• (4) shifting said first bit out of said register and introducing a trailing bit of said second binary value;
• (4a) if said first bit is of said second binary value, outputting an indication of a bit of said second binary value in the data stream;
• (4b) if said first bit is of said first binary value, testing the remaining bits in the register;
• (4bi) if not all remaining bits are of said second binary value, outputting an indication of a bit of said first binary value in the data stream;
• (4bii) if all remaining bits are of said second binary value, outputting an indication that all of the data bits in said unit have been examined;
• (5) repeating said steps of examining and shifting until all data bits in said unit have been examined;
• (c) repeating said step of examining for all units of the data stream.

A system for generating a table to decode variable-length binary data code words comprising:

• means for compiling a list comprising:
• all bit strings to be decoded, along with an indication that they are complete code words and an indication of their information content, and
• the null bit string and all unique leading bit combinations in said code words, along with an indication that said null bit string and said combinations are incomplete code words;
• means for selecting a first binary value which will be used to cause a branch within the table;
• means for sorting the bit strings of said list in ascending order, considering a null bit position as being less than the second binary value and the second binary value as being less than the first binary value;
• means for forming a table of entries in the order indicated by the sorted list, each table entry containing an indication of whether the associated bit string is a complete or incomplete code word and either the information associated with the complete code word or, for incomplete code words, an indication of the location of the entry corresponding to the bit string associated with the current table entry with a bit of said first binary value appended to it.

A system for decoding a data stream composed of variable-length binary data code words comprising:

• (a) means for generating a table to decode variable-length binary data code words comprising:
• (1) means for compiling a list comprising:
• (i) all bit strings to be decoded, along with an indication that they are complete code words and an indication of their information content, and
• (ii) the null bit string and all unique leading bit combinations in said code words, along with an indication that said null bit string and said combinations are incomplete code words;
• (2) means for selecting a first binary value which will be used to cause a branch within the table;
• (3) means for sorting the bit strings of said list in ascending order, considering a null bit position as being less that the second binary value and the second binary value as being less than the first binary value;
• and
• (4) means for forming a table of entries in the order indicated by the sorted list, each table entry containing an indication of whether the associated bit string is a complete or incomplete code word and either the information associated with the complete code word or, for incomplete code words, an indication of the location of the entry corresponding to the bit string associated with the current table entry with a bit of said first binary value appended to it;
• (b) means for decoding a code word by the steps comprising:
• (1) addressing the entry of said table corresponding to said null bit string;
• (2) examining the next bit in the data stream;
• (3) if said bit is of said first binary value, addressing a new entry of the decoding table as indicated by the table entry currently addressed;
• (4) if said bit is of said second binary value, addressing the next entry in the decoding table;
• (5) examining the newly addressed table entry to determine if a complete code word has been decoded;
• and
• (6) if a complete code word has not been decoded, repeating the steps of examining and addressing for additional bits in the data stream until a complete code word has been decoded;
• and
• (c) means for repeatedly activating said decoding means until all of the code words in the data stream have been decoded.

A system for analyzing a stream of binary data comprising:

• (a) means for dividing the stream into units containing a plurality of data bits;
• (b) register means, including at least one register, for storing said data bits;
• (c) processing means for examining a first unit of said stream comprising:
• (1) means for entering said first unit into the high-order bits of a register of said register means, of equal or greater length than said first unit;
• (2) means for appending a first trailing bit of a first binary value to the data bits in said unit and setting any additional trailing bits needed to fill said register to a second binary value;
• (3) examining means for examining the first bit in said unit to determine its binary value;
• (4) shifting means for shifting said first bit out of said register and introducing a trailing bit of said second binary value;
• (4a) means for outputting an indication of a bit of said second binary value in the data stream, if said first bit is of said second binary value;
• (4b) means for testing the remaining bits in the register, if said first bit is of said first binary value;
• (4bi) means for outputting an indication of a bit of said first binary value in the data stream, if not all remaining bits are of said second binary value;
• (4bii) means for outputting an indication that all of the data bits in said unit have been examined, if all remaining bits are of said second binary value;
• and
• (5) means for repeatedly actuating said examining and shifting means until all data bits in said unit have been examined;
• and
• (d) means for repeatedly actuating said processing means for examining all units of the data stream.