Unisys Corporation

Albert B Cooper

Terry A Welch, Deceased

Robert A Pressman

William D Maimone

Mark T Starr

Carl R Faix

Craig J Mento

A matrix of single input OR-gates correspond to respective codes to be assigned to strings. The inputs of the OR-gates are coupled to respective outputs of a code decoder that is responsive to a fetched input code. The locations of a character and level table, respectively accessible by the code decoder outputs, store the extension characters of extended strings recorded in the decompressor. Outputs of OR-gates are selectively coupled to code decoder outputs through a matrix switch to sequentially couple OR-gate outputs to OR-gate inputs so that the characters of a string corresponding to the input code are provided from accessed locations of the table. An update extended string is recorded by coupling the output of the OR-gate corresponding to the next assignable code to the code decoder output corresponding to the previously received code. The first character of the string corresponding to the current code is stored in the table location accessible by the next assignable code.

Data decompressor utilizing sequentially coupled logic elements

A matrix of AND-gates correspond to respective codes to be assigned to strings. The outputs of the AND-gates are selectively coupled to prefix code inputs of the AND-gates through a prefix code matrix switch. A plurality of characters from the input stream are fetched into an input character buffer and applied through respective character decoders and selectively through a character matrix switch to character inputs of the AND-gates. An AND-gate-corresponding to a code assigned to a string that is the longest match to the plurality of fetched characters is thereby enabled. Update extended strings are recorded in the AND-gates, an extended string comprising a longest matching string extended by the data character following the longest matching string. A virtual level is assigned to an AND-gate indicative of the number of characters of the string recorded thereby, the virtual level being one greater than the level that had been assigned to the AND-gate corresponding to the longest match. The virtual level is also indicative of the stage of the input character buffer holding the character following the longest match. An AND-gate is reassigned to an extended string to be recorded when further codes are unavailable for assignment and the output of the AND-gate is not coupled to the prefix code input of another AND-gate.

Data compressor with string code reassignment utilizing switched input coincidence elements

A matrix of AND-gates correspond to respective codes to be assigned to strings. The outputs of the AND-gates are selectively coupled to prefix code inputs of the AND-gates through a prefix code matrix switch. A plurality of characters from the input stream are fetched into an input character buffer and applied through respective character decoders and selectively through a character matrix switch to character inputs of the AND-gates. An AND-gate corresponding to a code assigned to a string that is the longest match to the plurality of fetched characters is thereby enabled. An update extended string is recorded in the AND-gate corresponding to the next code to be assigned by coupling, through the prefix code matrix switch, the output of the AND-gate corresponding to the longest matching string to the prefix code input of the AND-gate corresponding to the next code to be assigned. The character decoder output representing the fetched character following the longest matching string is coupled, through the character matrix switch, to the character input of the AND-gate corresponding to the next code to be assigned. A virtual level is assigned to an AND-gate indicative of the number of characters of the string recorded by the AND-gate. The virtual level that is assigned to the AND-gate recording the update extended string is one greater than the level that had been assigned to the AND-gate corresponding to the longest match. The virtual level is also indicative of the stage of the input character buffer holding the character following the longest match.

Data compressor utilizing switched input coincidence elements arranged in virtual levels

The disclosed compressor utilizes a plurality of prefix tables corresponding to respective prefix codes. A string is stored by storing the code associated with the string in a prefix table corresponding to the code of the string prefix at a prefix table location corresponding to the extension character of the string. The input data character stream is searched by comparing the input stream to the stored strings to determine the longest match therewith. The code associated with the longest match is outputted so as to provide the output stream of compressed codes. The stored strings are updated by inserting an extended string into the prefix tables, the extended string comprising the longest match extended by the next data character in the input stream following the longest match, the extended string being stored in the prefix table corresponding to the code of the longest match, a code being assigned to the extended string. A code is deleted from a prefix table for reassignment to an extended string to be inserted when further codes are unavailable for assignment. A code is selected for reassignment when the prefix table corresponding to the code is empty or has not been established.

Prefix table implemented data compression method and apparatus utilizing string code reassignment

A data compressor for compressing an input stream of data characters into an output stream of compressed codes includes a plurality of AND-gates corresponding to a respective plurality of codes to be assigned to strings. Each string comprises a prefix string, having an associated prefix code, and an extension character. An AND-gate has a prefix code input and a character input for enabling the AND-gate, the energized output of an AND-gate providing a representation of the code corresponding thereto. The compressor includes a first matrix switch for selectively coupling the provided representations of codes corresponding to the AND-gates to the prefix code inputs of the AND-gates and a second matrix switch for selectively coupling representations of data characters fetched from the input stream to the character inputs of the AND-gates. Data characters are sequentially fetched from the input stream so as to sequentially enable AND-gates until a last data character is fetched that does not result in an enabled AND-gate. The code is output that corresponds to the last enabled AND-gate, thereby providing the stream of compressed codes.

Data compressor utilizing switched input coincidence elements

A data compressor includes a plurality of tandem coupled stages, each stage comprising a matrix of AND-gates and a matrix switch. An AND-gate has inputs responsive, respectively, to a representation of a prefix code and a representation of a character for energizing the AND-gate output. The AND-gate outputs are coupled, respectively, to the inputs of the matrix switch and the matrix switch outputs have respective string codes assigned thereto. The matrix switch is controllable for coupling any one of the matrix switch inputs to a selected one of the matrix switch outputs. Energization of an AND-gate output coupled to a matrix switch output provides a representation of the code assigned thereto. The provided representations of codes assigned to the AND-gates of a stage are coupled to the prefix code inputs of the AND-gates of the next following stage. A plurality of input characters are fetched into an input buffer and the characters in the buffer stages are applied to respective character decoders at the compressor stages. The outputs of the character decoder at each stage are applied to the character inputs of the AND-gates of the stage.

Data compression apparatus and method utilizing tandem coupled matrices

The data compressor utilizes a plurality of subdictionaries arranged in levels for storing strings of data characters. The subdictionary at the first level stores two character strings and a subdictionary at a subsequent level stores strings that are one character longer than the strings stored in the subdictionary at the level prior thereto. A plurality of data characters are fetched from the input into an input buffer and applied to the respective levels. The subdictionary at a level is searched for the string comprising the string matched at the prior level extended by the fetched character applied to the level. The string code of a string matched at a level is cascaded to the next level. The longest match with the fetched characters is determined by one of the fetched characters resulting in a mismatch at one of the levels. The string code associated with the longest match is output. An extended string comprising the longest match extended by the fetched character that resulted in the mismatch is inserted into the subdictionary at the mismatching level.

Data compression method and apparatus utilizing cascaded subdictionaries

A data decompressor for decompressing an input stream of compressed codes to recover an output stream of data characters corresponding thereto. A plurality of character tables corresponding to respective characters store strings of data characters, the stored strings having respective string codes associated therewith. A string comprises a prefix string of at least one character followed by an extension character. A string is stored in the character tables by storing the code associated with the string prefix in the character table corresponding to the string extension character at a character table location corresponding to the string code of the string. The character tables are accessed with a currently received compressed code so as to recover a string corresponding thereto and the characters of the recovered string are output. An extended string is inserting into the character tables comprising the string corresponding to the compressed code received previously to the currently received compressed code extended by the first character of the recovered string, the extended string being stored in the character tables by storing the previously received compressed code in the character table corresponding to the first character of the recovered string at the character table location corresponding to the string code assigned to the extended string. A directory linking the string codes to respective character tables in which the strings corresponding to the string codes are stored is utilized in accessing a stored string.

Character table implemented data decompression method and apparatus

A new LZW compressor implementation architecture utilizes a plurality of prefix tables corresponding to respective prefix codes. A string is stored by storing the code associated with the string in a prefix table corresponding to the code of the string prefix at a prefix table location corresponding to the extension character of the string. A search for the longest matching string is performed by determining if the prefix table location is empty corresponding to the currently fetched character in the prefix table associated with the code of the currently matched string. If the location is not empty, it is storing the code of the string comprising the currently matched string extended by the currently fetched character. This string code is used as the next match with which to continue the search with the next fetched character. When the location is empty, the longest match has been determined to be the currently matched string. The stored strings are updated by storing the next available string code in the empty location.

Prefix table implemented data compression method and apparatus

The data compressor utilizes a plurality of character tables arranged in levels for storing strings of data characters, the character tables corresponding to respective characters of the alphabet. A string is stored by storing the string code associated with the string in a character table corresponding to the extension character of the string in a location of the character table corresponding to the code of the string prefix. The character tables at the first level store 2-character strings and the character tables at a subsequent level store strings that are one character longer than the strings stored in the character tables at the level prior thereto.

Data compression method and apparatus utilizing cascaded character tables

A data compressor includes a matrix of AND-gates corresponding to a respective plurality of strings. An AND-gate has inputs responsive, respectively, to a representation of a prefix code and a representation of a fetched character for energizing the AND-gate output. The AND-gate outputs are coupled, respectively, to the inputs of a matrix switch and the matrix switch outputs have respective string codes assigned thereto. The matrix switch is controllable for coupling any one of the matrix switch inputs to a selected one of the matrix switch outputs. Energization of an AND-gate output coupled to a matrix switch output provides a representation of the code assigned thereto. A prefix decoder responsive to the provided representations of codes assigned to the matrix switch outputs provides decoder outputs to the prefix code inputs of the AND-gates. A character decoder responsive to fetched characters provides decoder outputs to the character inputs of the AND-gates.

Matrix implemented data compression apparatus and method

An LZW compressor implementation architecture utilizes a plurality of limited length character tables corresponding to the respective characters of the alphabet. A string is stored by storing the code associated with the string in the character table corresponding to the extension character of the string at a character table location corresponding to the code of the string prefix. A character table is created when the character corresponding thereto is first encountered in the input. The input data character stream is searched by comparing the input stream to the stored strings to determine longest matches therewith. The codes associated with the longest matched strings are outputted so as to provide an output stream of compressed codes. The respective lengths of the character tables are limited in accordance with the frequency of occurrence of the characters of the alphabet. If a character table is limited in length to a number of strings less than a predetermined threshold, the character table is excluded from creation. The stored strings are updated by inserting extended strings into the character tables, terminating storage into a character table when the table is full. Additionally, an extended string is excluded from storage when the appropriate character table therefor is excluded from creation. The code counter assigning the string codes is not incremented when an extended string is not stored.

Data compression method and apparatus implemented with limited length character tables and compact string code utilization

A decompressor recovers and outputs a stream of data characters corresponding to an input stream of compressed codes. The decompressor includes a dictionary that stores strings of data characters having respective codes associated therewith. A currently received compressed code accesses the dictionary to recover a string and the decompressor outputs the characters of the recovered string so as to provide the output stream of data characters. An extended string is inserted into the dictionary that comprises the string corresponding to the previously received code extended by the first character of the recovered string. A code is assigned to the stored extended string. The decompressor maintains counts of inserted extended strings that have the same extension character for respective characters of the alphabet. The inserting of an extended string into the dictionary and the assigning of a code thereto are bypassed for an extended string having a particular extension character when the count of such strings attains an associated predetermined limit. Additionally, extended string insertion and code assignment are bypassed for an extended string having an extension character that is denoted as an excluded character.

Data decompressor for use with a data compressor implemented with limited length character tables and compact string codes

A new LZW compressor implementation architecture utilizes a plurality of character tables corresponding to the respective characters of the alphabet. A string is stored by storing the code associated with the string in the character table corresponding to the extension character of the string at a character table location corresponding to the code of the string prefix. A search for the longest matching string is performed by determining if the character table location is empty corresponding to the code of the currently matched string in the character table associated with the currently fetched character. If the location is not empty, it is storing the code of the string comprising the currently matched string extended by the currently fetched character. This string code is used as the next match with which to continue the search with the next fetched character. When the location is empty, the longest match has been determined to be the currently matched string. The stored strings are updated by storing the next available string code in the empty location.

Character table implemented data compression method and apparatus

A new LZW compressor implementation architecture utilizes a plurality of limited length character tables corresponding to the respective characters of the alphabet. A string is stored by storing the code associated with the string in the character table corresponding to the extension character of the string at a character table location corresponding to the code of the string prefix. A character table is created when the character corresponding thereto is first encountered in the input. The input data character stream is searched by comparing the input stream to the stored strings to determine longest matches therewith. The codes associated with the longest matched strings are outputted so as to provide an output stream of compressed codes. The respective lengths of the character tables are limited in accordance with the frequency of occurrence of the characters of the alphabet. If a character table is limited in length to a number of strings less than a predetermined threshold, the character table is excluded from creation. The stored strings are updated by inserting extended strings into the character tables, terminating storage into a character table when the table is full. Additionally, an extended string is excluded from storage when the appropriate character table therefor is excluded from creation.

Growing community of inventors

New York, NY, United States of America

Albert B Cooper