Title

Vlsi Algorithms For Data-Compression

Title - Alternative

Comput. Syst. Sci. Eng.

Abstract

Data compression is the reduction of redundancy in data representation in order to decrease storage and communication costs. Data compression techniques have been used in practice primarily through software implementations which do not meet the speed and performance requirements of current and future systems. In this paper we present a new class of efficient hardware algorithms for data compression and decompression that can provide speeds that are an order of magnitude higher than currently obtainable encoding speeds. Our algorithms for the Huffman compression scheme works on the principle of propagation of a token on the reverse binary tree constructed from the original codes. We show how the same principles can be used to develop hardware algorithms to implement the multi-group compression and decompression methods. Finally, a simple circuit that can be used to implement the run-length and header compression methods is described. The algorithms are suitable for VLSI implementation, and data transformation can be done 'on-the-fly'. Based on a prototype VLSI implementation of a compression chip, the algorithms yield an estimated compression rate of 10 M characters per second.

Publication Title

Computing Systems

Volume

6

Issue/Number

4

Publication Date

1-1-1991

Document Type

Article

Language

English

First Page

238

Last Page

253

WOS Identifier

WOS:A1991GM22300004

ISSN

0267-6192

Share

COinS