Back to results
US 7,256,715 B1Granted
Data compression using dummy codes
AssigneeAltera Corporation
InventorMartin Langhammer
Life of this patent
Estimating the term…
Abstract
Received data is compressed according to an algorithm, which is a modification of the conventional LZW algorithm. A limited number of hash values are formed, and a code memory is searched at locations corresponding to the hash values. If all of the locations contains a valid code, but none of them contains a valid code corresponding to a potential new code, a dummy code is created, and a counter, which indicates the number of codes created, is incremented. The algorithm can be implemented in parallel in hardware.
Claims19
A method of compressing received data, the received data comprising a string of characters, the method comprising:
- identifying a previously encoded data string comprising at least one character in said received data, as a potential new prefix string;
- identifying a character immediately following said previously encoded data string as a potential new append character;
- forming a plurality of hash values from said potential new prefix string and said potential new append character;
- using said plurality of hash values to identify a corresponding plurality of storage locations in a code memory, and to access said corresponding plurality of storage locations in said code memory;
- determining whether said corresponding plurality of storage locations in said code memory contain valid code values and, if said corresponding plurality of storage locations contain valid codes, determining whether said corresponding plurality of storage locations contain valid codes comprising said potential new prefix string and said potential new append character;
- if one of said corresponding plurality of storage locations contains a valid code comprising said potential new prefix string and said potential new append character, identifying said potential new prefix string and said potential new append character as an additional previously encoded data string;
- if none of said corresponding plurality of storage locations contains a valid code comprising said potential new prefix string and said potential new append character, and if one or more of said corresponding plurality of storage locations does not contain a valid code, creating a new code comprising said potential new prefix string and said potential new append character, storing said new code at a selected one of said one or more of said corresponding plurality of storage locations, and incrementing a counter which indicates the number of codes created;
- and
- if all of said corresponding plurality of storage locations contains a valid code, but none of said corresponding plurality of storage locations contains a valid code comprising said potential new prefix string and said potential new append character, creating a dummy code comprising said potential new prefix string and said potential new append character, and incrementing said counter which indicates the number of codes created.
6 more elements
A device for compressing received data, the received data comprising a string of characters, the device comprising:
- logic for identifying a previously encoded data string comprising at least one character in said received data, as a potential new prefix string;
- logic for identifying a character immediately following said previously encoded data string as a potential new append character;
- a hash generator for forming a plurality of hash values from said potential new prefix string and said potential new append character;
- a code memory, comprising a plurality of storage locations, for storing a corresponding plurality of codes, wherein each of said plurality of hash values accesses a corresponding storage location in said code memory;
- and
- logic circuitry, for determining whether said corresponding plurality of storage locations in said code memory contain valid code values and, if said corresponding plurality of storage locations contain valid codes, determining whether said corresponding plurality of storage locations contain valid codes comprising said potential new prefix string and said potential new append character,
- wherein, if one of said corresponding plurality of storage locations contains a valid code comprising said potential new prefix string and said potential new append character, said logic circuitry identifies said potential new prefix string and said potential new append character as an additional previously encoded data string;
- wherein, if none of said corresponding plurality of storage locations contains a valid code comprising said potential new prefix string and said potential new append character, and if one or more of said corresponding plurality of storage locations does not contain a valid code, said logic circuitry creates a new code comprising said potential new prefix string and said potential new append character, stores said new code at a selected one of said one or more of said corresponding plurality of storage locations, and increments a counter which indicates the number of codes created;
- and
- wherein, if all of said corresponding plurality of storage locations contains a valid code, but none of said corresponding plurality of storage locations contains a valid code comprising said potential new prefix string and said potential new append character, said logic circuitry creates a dummy code comprising said potential new prefix string and said potential new append character, and increments said counter which indicates the number of codes created.
7 more elements
Dependencies are inferred from the claim text.