Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Hardware-Based Data Compression Technique

IP.com Disclosure Number: IPCOM000043594D
Original Publication Date: 1984-Sep-01
Included in the Prior Art Database: 2005-Feb-05
Document File: 3 page(s) / 78K

Publishing Venue

IBM

Related People

Flores, AV: AUTHOR

Abstract

When data is being compressed, e.g., for communications purposes or for magnetic media storage, the leading technique is the use of Huffman encoding. The software implementation of this method, however, exhibits some disadvantages, primarily in the fact that time required for coding may offset the advantages gained from data compression. Addressing this problem, this article describes a hardware-based data compression/ expansion method which significantly reduces the amount of time required and is also transparent to the software used. Advantages of Huffman Encoding In the use of a given alphabet, some characters are more frequently employed in a particular application than others. For example, alphanumeric characters would be encountered more frequently than non-graphic characters in a text-processing application.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 3

Hardware-Based Data Compression Technique

When data is being compressed, e.g., for communications purposes or for magnetic media storage, the leading technique is the use of Huffman encoding. The software implementation of this method, however, exhibits some disadvantages, primarily in the fact that time required for coding may offset the advantages gained from data compression. Addressing this problem, this article describes a hardware-based data compression/ expansion method which significantly reduces the amount of time required and is also transparent to the software used. Advantages of Huffman Encoding In the use of a given alphabet, some characters are more frequently employed in a particular application than others. For example, alphanumeric characters would be encountered more frequently than non-graphic characters in a text-processing application. Acting on this phenomenon, Huffman encoding is a widely utilized method of representing frequently used characters by shorter bit strings than infrequently used characters. The overall effect on an alphabet of 256 characters, all represented by an 8-bit string, would be that that same alphabet of 256 characters would now consist of variable-length bit strings with lengths in the range of 4 to 12 bits. (Some techniques for implementing and improving upon data compression processes have previously been described [*]. A Hardware-Based Implementation Software implementations of Huffman encoding are widely used -- for example, to minimize time consumed in communicational processing of data or to conserve space on magnetic storage media. Unfortunately, such software implementations also tend to be somewhat time-consuming themselves, so that the time required for the encoding process may offset the time or space savings achieved by the advantages of compaction. Recognizing this problem, the expedient described in this article represents a hardware implementation of the Huffman encoding method, designed to significantly reduce the time consumed in encoding. The technique is schematically described in the figures. Fig. 1 presents a block diagram of the compression (encoding) logic. Fig. 2 provides a block diagram of the expansion (decoding) logic. For the purposes of this discussion, several basic assumptions are made: $ Encodings are intended for an alphabet of 256 characters represented by 8-bit strings.

$ There are 256 unique codings.

$ The logic provides a two-way mapping process

between the 8-bit alphabet and the variable-length

bit string alphabet (with a range of 4 to 12

bits). Encoding/Compression Process As input, the encoder logic accepts a character (8 bits in parallel) and produces a 16-bit word as output (Fig. 1). This 16-bit word consists of two fields.

One field represents the variable-length bit string resulting from the mapping from the fixed-length bit string alphabet into the variable-length bit string alphabet. The other field is a counter value which indicates the le...