Data compression system
AssigneeFreescale Semiconductor, Inc.
InventorPhillip M. Matthews
Life of this patent
Estimating the term…
Abstract
A data compression scheme implemented based on V.42bis implemented in hardware within mobile units of a cellular system is disclosed. The data compression scheme includes a number of hardware state machines that perform data compression and decompression functions. Additionally, a dictionary of codewords and character strings is organized according to keys and is implemented as a balanced binary tree.
Claims56
An encoding system adapted to encode data strings into codewords, the encoding system comprising:
- a first memory portion adapted to store a dictionary of data strings and codewords corresponding to the data strings, wherein the dictionary is implemented as a balanced binary tree;
- a second memory portion adapted to store a data string to be processed;
- and
- an encoder adapted to receive from the second memory portion the data string to be processed, to determine if a codeword corresponding to a portion of the data string to be processed is stored in the dictionary and to output a codeword corresponding to a data string previously found in the dictionary if the codeword corresponding to the portion of the data string to be processed is not stored in the dictionary, wherein the encoder is further adapted to balance the dictionary.
A decoding system adapted to decode codewords into data strings, the decoding system comprising:
- a memory adapted to store a dictionary of data strings and codewords corresponding to the data strings, wherein the dictionary is implemented as a balanced binary tree;
- an input buffer adapted to receive and store a set of codewords to be processed;
- and
- a decoder adapted to receive from the input buffer the set of codewords to be processed, to decode a first codeword into a first character string, to decode a second codeword into a second character string and to assign a third codeword to a combination of the first codeword and the second character string if a codeword corresponding to the combination of the first codeword and the second character string is not stored in the dictionary, wherein the decoder is further adapted to balance the dictionary.
An encoder adapted to operate with a first memory portion adapted to store a dictionary of data strings and codewords corresponding to the data strings, wherein the dictionary is implemented as a balanced binary tree, and a second memory portion adapted to receive and store a data string to be processed, the encoder comprising:
- a first hardware state machine adapted to receive from the second memory portion the data string to be processed;
- a second hardware state machine adapted to determine if a codeword corresponding to a portion of the data string to be processed is stored in the dictionary and to output a codeword corresponding to a data string previously found in the dictionary if the codeword corresponding to the portion of the data string to be processed is not stored in the dictionary;
- and
- a third hardware state machine adapted to balance the dictionary.
A decoder adapted to operate with a memory adapted to store a dictionary of data strings and codewords corresponding to the data strings, wherein the dictionary is implemented as a balanced binary tree, and an input buffer adapted to receive and store a set of codewords to be processed, the decoder comprising:
- a first hardware state machine adapted to receive from the input buffer the set of codewords to be processed;
- a second hardware state machine adapted to decode a first codeword into a first character string, to decode a second codeword into a second character string and to assign a third codeword to a combination of the first codeword and the second character string if a codeword corresponding to the combination of the first codeword and the second character string is not stored in the dictionary;
- and
- a third hardware state machine adapted to balance the dictionary.
Dependencies are inferred from the claim text.