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

Decompaction

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

Publishing Venue

IBM

Related People

Peake, JW: AUTHOR

Abstract

This article describes a method for decoding minimum redundancy Huffman codes used in the compaction of character and image data. The method uses Programmable Logic Arrays (PLAs) to reduce the complexity and improve performance over other decoding methods. Compaction is used to decrease the amount of data storage required for character or image data. Each character or image is represented by a string of data bits formed by concatenating variable length codewords (Huffman minimum redundancy codes) that describes how the data is to be reconstructed to form the original character or image. Although compaction reduces the amount of storage required to contain this type of data, it requires reconstruction. Reconstruction or decompaction has three requirements.

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 40% of the total text.

Page 1 of 3

Decompaction

This article describes a method for decoding minimum redundancy Huffman codes used in the compaction of character and image data. The method uses Programmable Logic Arrays (PLAs) to reduce the complexity and improve performance over other decoding methods. Compaction is used to decrease the amount of data storage required for character or image data. Each character or image is represented by a string of data bits formed by concatenating variable length codewords (Huffman minimum redundancy codes) that describes how the data is to be reconstructed to form the original character or image. Although compaction reduces the amount of storage required to contain this type of data, it requires reconstruction. Reconstruction or decompaction has three requirements. First, the method must be able to separate each variable length codeword from the concatenated bit string. Next, each codeword needs to be decoded into reconstruction information. Lastly, the reconstruction information is used to recreate the original bit image of the character or image the compacted bit string represents. This article deals with the first and second requirements. A description of Huffman coding fundamentals is not included here but can be found in [1,2]. Basic to the discussion of Huffman encoding and decoding is the concept that the method can be thought of as a 'state tree', where the end points represent encoded symbols and each branch level represents a bit in the codeword. Each codeword in the bit string can be decoded by examining each bit of the compacted bit string in a serial fashion. As each bit is examined, a branch in a state tree occurs, eventually leading to the symbol or reconstruction information the codeword represents. Each codeword is decoded in this way until there are no remaining bits in the compacted bit string. The PLA Method The method to be described has the advantages of high speed decoding, elimination of the wasted address locations, and ease of implementation. The PLA method uses a sample of the compacted bit string that is the length of the maximum codeword. The sample is an input to the 'AND' terms of a programmable logic array. A logic array has the capability of only considering selected bits in the 'AND' array and activating the 'OR' array only when the selected input bits match those indicated by the 'AND' array. Each unique Huffman codeword is assigned a product term and 'AND' term bits to match the assigned codeword (Fig. 1). Each product term needs only to be concerned with the length of its particular codeword since the rest of the sample bits are not considered by the 'AND' array and can be thought of as "don't care" terms. For each codeword, one and only one 'AND' array product term will match for one activating input into the 'OR' array term. The 'OR' array contains the decoded reconstruction information and the length of the codeword (Fig. 1). Fig. 2 is a block diagram of how PLAs are used to construct a d...