Browse Prior Art Database

Arithmetic Compression Code Control Parameter Approximation

IP.com Disclosure Number: IPCOM000052052D
Original Publication Date: 1981-Apr-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 3 page(s) / 49K

Publishing Venue

IBM

Related People

Helman, DR: AUTHOR [+3]

Abstract

This invention relates to a method for ascertaining the nearest integer value of a control parameter k (skew parameter) used in arithmetic compression coding as derived from the counts of the ones and zeros of an input bit stream. This approximation starts with the observation that the ratio of the number of counts of the least probable symbol (lps) to the total symbol count is approximately equal to 2/-k/. It is desired that the count be converted into k without actual division. In contrast, the prior method [*] used a difference in leading zeros between the count of the number of the zeros and the count of the number of ones in order to approximate k. The method of this invention is to initially approximate k and utilize it as a running incrementable/decrementable parameter.

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

Page 1 of 3

Arithmetic Compression Code Control Parameter Approximation

This invention relates to a method for ascertaining the nearest integer value of a control parameter k (skew parameter) used in arithmetic compression coding as derived from the counts of the ones and zeros of an input bit stream. This approximation starts with the observation that the ratio of the number of counts of the least probable symbol (lps) to the total symbol count is approximately equal to 2/-k/. It is desired that the count be converted into k without actual division. In contrast, the prior method [*] used a difference in leading zeros between the count of the number of the zeros and the count of the number of ones in order to approximate k. The method of this invention is to initially approximate k and utilize it as a running incrementable/decrementable parameter. In this case, k is decremented in inverse relation to an increase in the count of the least probable symbols. Alternatively, k is incremented due to a decrease in the count of the least probable symbol. In this invention, let n(lps) denote the smaller of the two counts, and n(mps) denote the larger of the two counts. k is selected such that if n(T) is the total count, then 2/-2/ approximates the ratio n(lps)/n(T).

The following constraints are imposed upon these relations. First, n(lps) is restricted to a small variation so that only n(mps) need be used to approximate the skew number k. Second, simple conditions are defined for incrementing or decrementing k; these conditions are independent of its magnitude. Third, a decrementing role involving a simple halving based only upon n(lps) is invoked.

For purposes of illustration, the value of n(lps) is limited to 3, 4, or 5. When the count reaches the value of 6, it is returned to "3", and the magnitude of n(mps) is halved.

Let skew k be given. The value of k should be altered (increased) only when the new n(mps) contrasts with the old n(mps) as follows: old n(mps): 0 0 0 0 0 1 1 1 1 1 1 1

new n(mps): 0 0 0 0 1 0 0 0 0 0 0 0

(Condition for incrementing k from 5 to 6).

In the general case, the old n(mps) is 2/k+1/-1, and the new n(mps) is 2/k/+1. The value of the new n(mps) has one less leading "0" than the old n(mps). This can be detected by the bitwise AND of corresponding bits in the old and new n(mps), and then ORing together the bits of the output or result of the AND operation for a fina...