Abstract

Data compression is the reduction of redundancy m data representation in order to decrease storage and communication costs. Data compression techniques have been used in practice primarily through software implementations which fail to meet the speed and performance requirements of current and future systems. This Ph.D. dissertation presents a set of hardware algorithms for compression and decompression techniques and the results of detailed simulations performed to quantify the effects of incorporating such hardware in various architectural environments. A new pipelined algorithm for data compression applicable to static binary encoding schemes is presented. A fast hardware algorithm for decompression that uses a balanced binary tree structure to eliminate code storage tables is introduced. Hardware algorithms are presented for the multi-group compression technique, ii run-length encoding method and an enhanced version of arithmetic coding scheme. These algorithms are suitable for VLSI implementation and can provide speeds that are an order of magnitude higher than currently obtainable encoding speeds. The design and implementation of a prototype compression chip for the Huffman's encoding scheme is presented. The chip yields an estimated compression rate of 10 million characters per second. The effect of employing compression hardware on the performance of a general purpose computer system and a special purpose back-end multiprocessor machine is analyzed by constructing detailed simulation models. Simulation results establish that our VLSI chips for compression and decompression cause significant improvements in system performance.

Graduation Date

1988

Semester

Summer

Advisor

Mukherjee, Amar

Degree

Doctor of Philosophy (Ph.D.)

College

College of Arts and Sciences

Department

Computer Science

Format

PDF

Pages

178 p.

Language

English

Rights

Public Domain

Length of Campus-only Access

None

Access Status

Masters Thesis (Open Access)

Identifier

DP0025762

Subjects

Arts and Sciences -- Dissertations, Academic; Dissertations, Academic -- Arts and Sciences

Share

COinS