Data compression system
First Claim
Patent Images
1. 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.
9 Assignments
0 Petitions
Accused Products
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.
-
Citations
56 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. 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. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. 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. - View Dependent Claims (36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46)
-
-
47. 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. - View Dependent Claims (48, 49, 50, 51, 52, 53, 54, 55, 56)
-
Specification