A Parallel Architecture for Giga Bit Lossless Data Compression

Abstract

The thesis proposes a high speed data compression architecture for multi-purpose communication applications. The architecture is a systolic array design for hardware implementation, and LZ 77 has been implemented as compression algorithm. Compression is achieved by reducing redundancy inherent in data, by comparing input data stream with previously encoded and transmitted bits. Design has been further optimized by carrying out searches in parallel, and future searches of data stream are carried out in same clock cycle increasing throughput to manifolds. The architecture has been further pipelined to reduce the critical time and further enhance throughputs exceeding 10 Gbits / sec. The motivation for research is the ever-increasing development in the field of digital communication. Requirements of information transfer as well as storage transferred have increased many folds in last many years. The communication bandwidth, although trying to match the pace of information increase has always been lagging behind, and there has always been a mis-match between the two. And both communication bandwidth and memories are quite expensive and cannot be increased just to match to the ever-growing information across networks. This necessitates measures to reduce the amount of information that needs to be transferred or stored, and hence, the basis of Data Compression. Various techniques varying from statistical to dictionary based methods exist in literature with a view to remove redundancies in data and achieve data compression. The techniques have been successfully implemented both across software and hardware platforms with far-reaching results. The choice of LZ 77 Algorithm, the simplest of dictionary based schemes, with a systolic architecture, owing to its inherent promising advantages of speed, error-resistant and simplicity forms the basis of this research.