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

Overlapped Statistics Memory Access for Decompression

IP.com Disclosure Number: IPCOM000042996D
Original Publication Date: 1984-Jun-01
Included in the Prior Art Database: 2005-Feb-04
Document File: 2 page(s) / 50K

Publishing Venue

IBM

Related People

Highbarger, ST: AUTHOR [+2]

Abstract

This invention relates to an apparatus for increasing the arithmetic encoding/decoding throughput. The increase is obtained by the concurrent accessing of a multi-ported RAM (random-access memory) for obtaining necessary statistical coding data on a lookahead basis. The binary coding methods for file compaction require statistics on the frequency of occurrence of patterns in bit streams in order to achieve compression. This entails the fetching of a statistic for each encoded or decoded bit. This requirement for providing a statistic on a bit basis represents a speed constraint. The statistics termed a skew are stored in a linearized tree arrangement of data. The requirement for coding a byte is to access each level of the tree only once every eight bits encoded.

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

Page 1 of 2

Overlapped Statistics Memory Access for Decompression

This invention relates to an apparatus for increasing the arithmetic encoding/decoding throughput. The increase is obtained by the concurrent accessing of a multi-ported RAM (random-access memory) for obtaining necessary statistical coding data on a lookahead basis. The binary coding methods for file compaction require statistics on the frequency of occurrence of patterns in bit streams in order to achieve compression. This entails the fetching of a statistic for each encoded or decoded bit. This requirement for providing a statistic on a bit basis represents a speed constraint. The statistics termed a skew are stored in a linearized tree arrangement of data. The requirement for coding a byte is to access each level of the tree only once every eight bits encoded. Since there is a delay of eight bit cycles between the use of a statistic on a byte basis, an opportunity exists for prefetching (looking ahead) in order to overlap the accessing of skews with the encoding or decoding of bits. Experience has shown that the decoding operation is the most time critical in that there exists a need to decode the bit at the ith level of the tree in order to calculate the tree address needed to decode the bit at the ith + first tree level. In the invention, it is necessary to split the statistics memory into independently accessible units. Each unit is accessed ahead of when the data is required even though the address bits...