VLSI algorithms and architectures for data compression

Despite the fact that the memory cost has decreased drastically over the past few years, the data storage requirements and data processing applications are growing explosively. Data compression methods are used to reduce the redundancy in data representation in order to decrease the storage requirements and communication costs. To take advantage of the VLSI technology, application-specific hardware algorithms and architectures for real-time systems with data parallelism would have to be developed as standard components for communication and storage.

In this dissertation, we develop a new memory-based architecture for multibit encoding and decoding of Huffman-type tree-based codes such that multiple number of bits can be encoded or decoded in one clock cycle. We present simulation results that lead to the design and implementation of a memory-based VLSI CODEC architecture. We also develop new parallel algorithms for image decorrelation schemes and present the design of a VLSI chip which implements one of these algorithms.

We develop a new paradigm of data compression called the "compressed pattern matching". The basic concept of compressed pattern matching is to search a pattern in compressed data without explicitly decompressing it. The problem becomes more crucial when the pattern is not fully specified, i.e. the pattern may consist of wild card characters. We present a set of hardware algorithms and design of a VLSI chip for compressed pattern matching using Huffman-type tree-based codes. The pattern can be fully or partially specified. We adopt the concept of these hardware algorithms for compressed pattern matching to join two compressed relational databases and present the detail simulation results. We will also formulate the compressed pattern matching problem for LZ-codes and we will show with an example that the compressed pattern search in arithmetic codes is not possible.

Finally, we will propose a variation of the LZW algorithm for text compression using a new data structure for on-line binary representation of the trie to represent a dictionary. This binary representation of the trie data structure can be mapped into memory for fast encoding and decoding of text and we propose a possible hardware architecture for implementation of a VLSI chip.