Coded data generation or conversion – Digital code to digital code converters – Unnecessary data suppression
Reexamination Certificate
2005-04-12
2005-04-12
Jeanglaude, Jean Bruner (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Unnecessary data suppression
C341S050000, C341S106000
Reexamination Certificate
active
06879271
ABSTRACT:
We present a method and apparatus for performing adaptive data compression. An alphabet and vocabulary in the encoder and decoder is built adaptively and stored in a dictionary as symbols are to be encoded and decoded. Each time an unknown symbol is to be encoded by the encoder, the encoder adds the symbol to the dictionary and transmits it in plain in the encoded string. The code words transmitted by the encoder include symbols and indexes. The state of a prefix bit preceding the code word indicates whether the code word is a plain symbol or an index of a symbol or string of symbols stored in the dictionary. The decoder examines the prefix bit of each code word as it is received to determine if the code word stores a symbol in plain or in index. If the code word stores a symbol in plain, the decoder learns the symbol by adding a sequence of symbols resulting from the concatenation of previously decoded symbols and the first symbol of the currently decoded symbol and by adding the symbol to its dictionary. If the code word stores an index, the decoder decodes the code word by extracting the symbol or sequence of symbols stored in the dictionary at the respective index in the dictionary.
REFERENCES:
patent: 4558302 (1985-12-01), Welch
patent: 5049881 (1991-09-01), Gibson et al.
patent: 5373290 (1994-12-01), Lempel et al.
patent: 5389922 (1995-02-01), Seroussi et al.
patent: 5455576 (1995-10-01), Clark, II et al.
patent: 5469161 (1995-11-01), Bezek
patent: 5703581 (1997-12-01), Matias et al.
patent: 5903230 (1999-05-01), Masenas
patent: 6658097 (2003-12-01), Hofer et al.
Granville, F., “Lossless compression core hits 100 Mbytes/sec”,EDN, (Mar. 13, 1998).
Kjelsø, M., Gooch M., Jones S., “Performance evaluation of computer architectures with main memory data compression”,J. Systems Architecture, 45, pp. 571-590 (1999).
Núñnez, J. L., Jones, S., “The X-MatchPro 100 Mbytes/second FPGA-Based Lossless Data Compressor”, Electronic Systems Design Group, Loughborough University, Leicestershire, England (date), no date.
Jiang, J., Jones, S., “Design of Dynamic LZW Compression Algorithm”, Parallel and Novel Architectures Group, Dept. of Electrical and Electronic Engineering, University of Nottingham, (date), no date.
Pentakalos, O. I., Yesha, Y., “Online Data Compression in a Mass Storage File System”, Abstract #28, Computer Science Department, University of Maryland, Baltimore, Maryland (date), No date.
Burroughs, S.H. and Lattrell, T. R., “Data compression technology in ASIC cores”,J. Research and Development, 42(6), IBM (1998).
Craft, D.J.,“A fast hardware data compression algorithm and some algorithmic extensions”,J. Research and Development, 42(6), IBM (1998).
Kemp, T. M., et al., “A decompression core for PowerPC”,J. Research and Development, 42(6), IBM (1998).
Kampf, F. A., “Performance as a function of compression”,J. Research and Development, 42(6), IBM (1998).
Storer, J. A. and Szymanski T. G., “Data Compression via Textual Substitution”,J. of Association for Computing Machninery29(4): 928-951 (Apr. 1982).
Yokoo, H., “Improved Variations Relating the Ziv-Lempel and Welch-Type Algorithms for Sequential Data Compression”,IEEE Transactions on Information Theory, 38(1): 73-81 (Jan. 1992).
Ziv, J. and Lempel, A., “Compression of Individual Sequences via Variable-Rate Coding”,IEEE Transactions on Information Theory, IT-24 (5): 530-536 (Sept. 1978).
Welch, T. A., “A Technique for High-Performance Data Compression”, Sperry Research Center,Computer, 17(6): 8-10, (Jun. 1984).
Nelson, M. R., “LZW Data Compression”,Dr. Dobb's Journal, pp. 29-36 (Oct. 1989).
Bunton, S. and Borriello, G., “Practical Dictionary Management for Hardware Data Compression”,Communications of the ACM35(1): 95-104 (Jan. 1992).
Ouaissa, K., et al., “Adaptive limitation of the dictionary size in LZW data compression”,International Symposium on Information Theory, ISIT (1995).
Hamilton Brook Smith & Reynolds P.C.
Jeanglaude Jean Bruner
MOSAID Technologies Inc.
LandOfFree
Method and apparatus for adaptive data compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for adaptive data compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for adaptive data compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3414956