US4652856A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multiplication-free multi-alphabet arithmetic code
Assignee: International Business Machines Corp
•
Filing: 1986-02-04
•
Granted: 1987-03-24
•
Expires: 2006-02-04
Abstract
Abstract Method and apparatus which cyclically generate a compressed, arithmetically-coded binary stream in response to binary occurrence counts of symbols in an uncoded string. The symbols in the uncoded string are drawn from a multi-character alphabet which is not necessarily a binary one. Coding operations and hardware are simplified by deriving from the binary occurrence counts an estimate of the probability of each unencoded symbol at its precise lexical location. The probability estimation eliminates any requirement for division or multiplication by employing magnitude-shifting of the binary occurrence counts. The encoded stream is augmented by the estimated symbol probability at the same time that an internal variable is updated with an estimate of the portion of a probability interval remaining after coding the current symbol, the interval estimate being obtained from the left-shifted occurrence counts. Decoding is the dual of encoding. The unencoded symbol stream is extracted, symbol-by-symbol, by subtracting the estimated symbol probability that comes closest to, but does not exceed the magnitude of the compressed stream, re-estimating the symbol probabilities based upon the decoding, and testing the difference of the subtraction against the re-estimated probability.
Inventors
- 👤 Kottappuram M. A. Mohiuddin
- 👤 Jorma J. Rissanen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 10:17
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/4006
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
382 words
A method for recursive machine modification of a string C(s) of binary numbers to produce C(si) where C(si) is a compressed representation of and responsive to the next symbol i in a symbol string s, s being a concatenation of symbols drawn from an alphabet having at least two characters, 0, . . . m, C(si) being a number in the semi-open coding range (0,1), the coding range being subdivided into intervals during successive machine string modification cycles, each interval being defined by its lower bound C(s) and a parameter A(s) such that (C(s), C+ A(s)), said method being executable upon a pair of registers C and A, each having a finite dimension, w, comprising the steps of: (a) placing respective initial contents in registers A and C; (b) for the next symbol i in the string s, reading in binary symbol occurrence statistics for the portion of s preceding i, said occurrence statistics including n i , the count of occurrences of i, Q(i)=n 0 +n 1 + . . . +n i-1 , the sum of counts for the symbols 0, 1, . . . i-1 preceding i in said alphabet, Q(m)=n 0 +n 1 + . . . +n m-1 , the sum of counts for the symbols preceding m in the alphabet, and N, the count of all symbols in the portion, normalizing N to a predetermined range, and normalizing n.sub.(i), Q(i), and Q(m) based upon the normalized value of N, and (1) if the next symbol i is not m, adding the normalized value of Q(i) to C, replacing the contents of A with the normalized value of n i , and shifting C and A in a predetermined direction until the contents of A lie within a predetermined range, or (2) if the next symbol i is m, adding the normalized value of Q(m) to the contents of C, subtracting the normalized value of Q(m) from the contents of A, and shifting C and A in a predetermined direction until the contents of A lie within a predetermined range; and (c) if i is not the last symbol in s, then repeating step (b), or, if i is the last symbol in s, then shifting the contents of C in said predetermined direction by w positions.
Claim 2
Independent Claim
382 words
A method for recursive machine modification of a string C(s) of binary numbers to produce C(si) where C(si) is a compressed representation of and responsive to the next symbol i in a symbol string s, s being a concatenation of symbols drawn from an alphabet having at least two characters, 0, . . . m, C(si) being a number in the semi-open coding range (0,1), the coding range being subdivided into intervals during successive machine string modification cycles, each interval being defined by its lower bound C(s) and a parameter A(s) such that (C(s), C+ A(s)), said method being executable upon a pair of registers C and A, each having a finite dimension, w, comprising the steps of: (a) placing respective initial contents in registers A and C; (b) for the next symbol i in the string s, reading in binary symbol occurrence statistics for the portion of s preceding i, said occurrence statistics including n i , the count of occurrences of i, Q(i)=n 0 +n 1 + . . . +n i-1 , the sum of counts for the symbols 0, 1, . . . i-1 preceding i in said alphabet, Q(m)=n 0 +n 1 + . . . +n m-1 , the sum of counts for the symbols preceding m in the alphabet, and N, the count of all symbols in the portion, normalizing N to a predetermined range, and normalizing n.sub.(i), Q(i), and Q(m) based upon the normalized value of N, and (1) if the next symbol i is not m, adding the normalized value of Q(i) to C, replacing the contents of A with the normalized value of n i , and shifting C and A in a predetermined direction until the contents of A lie within a predetermined range, or (2) if the next symbol i is m, adding the normalized value of Q(m) to the contents of C, subtracting the normalized value of Q(m) from the contents of A, and shifting C and A in a predetermined direction until the contents of A lie within a predetermined range; and (c) if i is not the last symbol in s, then repeating step (b), or, if i is the last symbol in s, then shifting the contents of C in said predetermined direction by w positions.
Claim 3
Dependent Claim
40 words
The method of claim 1 further including, before the execution of steps (b)(1) or (b)(2), scaling the magnitudes of the normalized values of n.sub.(i), Q(i), and Q(m) by a predetermined amount unless Q(m) is less than the contents of A.
Claim 4
Dependent Claim
39 words
The method of claim 1 wherein said normalizing of the occurrence statistics N, n i , Q(i) and Q(m) includes register-shifting of said binary occurrence statistics in a predetermined direction corresponding to a direction of increasing register content magnitude.
Claim 5
Dependent Claim
32 words
The method of claim 2 wherein said normalizing of said binary occurrence statistics includes register-shifting said binary occurrence statistics in a predetermined direction corresponding to a direction of increasing register content magnitude.
Claim 6
Dependent Claim
36 words
The method of claim 1 wherein the predetermined range is from 0.11 binary to 1.1 binary , said initial C register contents are 0, and said initial A register contents are 1.00 . . . 00.
Claim 7
Independent Claim
236 words
A method for the cyclic machine modification of a binary number string C(s) to produce C(si), where C(si) is a compressed representation of and responsive to the next symbol b(i) from a binary symbol string s=b(1), b(2), . . . , b(i), . . . b(n), C(si) being a number in the semi-open coding range [0,1), the coding range being subdivided into intervals during successive machine string modification cycles, each interval being defined by its lower bound C(s) and a parameter A(s) such that (C(s), C(s)+ A(s)), said method being executable upon a pair of registers A and C, each being of finite width w, comprising the steps of: (a) placing respective initial contents in registers C and A; (b) reading in, incrementally counting, and ascertaining whether the next symbol b(i) is a least probable symbol (LPS) or a most probable symbol (MPS), and (1) if b(i) is the last symbol in s, shifting the contents of C left by w positions, or (2) if b(i) is LPS, replacing the contents of A by the normalized count of LPS and shifting both A and C left until the contents of A lie within a predetermined range, or (3) if b(i) is MPS, adding to C and subtracting from A the normalized count of MPS and shifting both A and C left until the contents of A lie within a predetermined range; and (c) repeating step (b).
Claim 8
Independent Claim
236 words
A method for the cyclic machine modification of a binary number string C(s) to produce C(si), where C(si) is a compressed representation of and responsive to the next symbol b(i) from a binary symbol string s=b(1), b(2), . . . , b(i), . . . b(n), C(si) being a number in the semi-open coding range [0,1), the coding range being subdivided into intervals during successive machine string modification cycles, each interval being defined by its lower bound C(s) and a parameter A(s) such that (C(s), C(s)+ A(s)), said method being executable upon a pair of registers A and C, each being of finite width w, comprising the steps of: (a) placing respective initial contents in registers C and A; (b) reading in, incrementally counting, and ascertaining whether the next symbol b(i) is a least probable symbol (LPS) or a most probable symbol (MPS), and (1) if b(i) is the last symbol in s, shifting the contents of C left by w positions, or (2) if b(i) is LPS, replacing the contents of A by the normalized count of LPS and shifting both A and C left until the contents of A lie within a predetermined range, or (3) if b(i) is MPS, adding to C and subtracting from A the normalized count of MPS and shifting both A and C left until the contents of A lie within a predetermined range; and (c) repeating step (b).
Claim 9
Dependent Claim
34 words
A method according to claim 6, wherein the predetermined range is from 0.75 to 1.50; and the C and A registers are respectively initialized to the value 0 and 1.00 . . . 00.
Claim 10
Dependent Claim
268 words
An arithmetic encoder responsive to a symbol string s which is a concatenation of symbols drawn from an alphabet having two or more characters 0, . . . , m, and to occurrence statistics n i , Q(i), Q(m), and N which correspond respectively to the count of occurrences of the symbol i, the sum of the counts n 0 through n i-1 , the sum of the counts n 0 through n m-1 , and the count of all symbols in the portion of the string s preceding the symbol i for recursively modifying a code string C(s) to produce C(si), where C(si) is a compressed representation of the string si and si is the string s followed by the symbol i, comprising: a first shift register containing the w-least-significant bits of C(si); a second shift register containing an interval coding variable; means responsive to N for normalizing n i , Q(i), and Q(m) based upon the normalization of N to a predetermined range; first arithmetic means for adding the normalized value of Q(i) to the contents of the first shift register if i≠m or for adding the normalized value of Q(m) to the contents of the first shift register if i=m; second arithmetic means for placing the normalized value of n i into the second shift register if i≠m or for subtracting the normalized value of Q(m) from the contents of the second register if i=m; and shift means for concurrently shifting the contents of the first and second registers in a predetermined direction until the contents of the second register lie within said predetermined range.
Claim 11
Dependent Claim
268 words
An arithmetic encoder responsive to a symbol string s which is a concatenation of symbols drawn from an alphabet having two or more characters 0, . . . , m, and to occurrence statistics n i , Q(i), Q(m), and N which correspond respectively to the count of occurrences of the symbol i, the sum of the counts n 0 through n i-1 , the sum of the counts n 0 through n m-1 , and the count of all symbols in the portion of the string s preceding the symbol i for recursively modifying a code string C(s) to produce C(si), where C(si) is a compressed representation of the string si and si is the string s followed by the symbol i, comprising: a first shift register containing the w-least-significant bits of C(si); a second shift register containing an interval coding variable; means responsive to N for normalizing n i , Q(i), and Q(m) based upon the normalization of N to a predetermined range; first arithmetic means for adding the normalized value of Q(i) to the contents of the first shift register if i≠m or for adding the normalized value of Q(m) to the contents of the first shift register if i=m; second arithmetic means for placing the normalized value of n i into the second shift register if i≠m or for subtracting the normalized value of Q(m) from the contents of the second register if i=m; and shift means for concurrently shifting the contents of the first and second registers in a predetermined direction until the contents of the second register lie within said predetermined range.
Claim 12
Dependent Claim
17 words
The arithmetic encoder of claim 8 wherein said predetermined range is (0.11 binary , 1.1 binary ).
Claim 13
Dependent Claim
16 words
The arithmetic encoder of claim 8 wherein said predetermined direction is a direction of increasing magnitude.
Claim 14
Dependent Claim
293 words
A decoder for deriving a symbol stream s, where s is a concatenation of symbols drawn from a multi-character alphabet 0, . . . , m, in response to an arithmetically-encoded symbol stream C(s) and to occurrence statistics n i , Q(i), Q(m), and N, which correspond respectively to the count of occurrences of the symbol i, the sum of the counts n 0 through n i-1 , the sum of the counts n 0 through n m-1 , and the count of all symbols in the portion of the string s preceding the symbol i for recursively modifying a code string C(s) to produce C(si), where C(si) is a compressed representation of the string si and si is the string s followed by the symbol i, comprising: a first shift register containing the w-most-significant bits of C(s); a second shift register containing an interval decoding variable; means responsive to N for normalizing n i , Q(i), and Q(m) based upon the normalization of N to a predetermined range; means for determining a symbol j in said alphabet such that the normalized value of Q(j)≦the contents of the first shift register; first arithmetic means for subtracting the normalized value of Q(j) from the contents of the first register; second arithmetic means for placing the normalized value of n j into the second register if j≠m or for subtracting the normalized value of Q(m) from the contents of the second register if j=m; and shift means for simultaneously shifting the contents of the first and second registers in a predetermined magnitude direction until the contents of the second register lie within said predetermined range and for shifting the next-most-significant portion of C(s) into the portion of the first register vacated by said simultaneous shifting.
Claim 15
Dependent Claim
293 words
A decoder for deriving a symbol stream s, where s is a concatenation of symbols drawn from a multi-character alphabet 0, . . . , m, in response to an arithmetically-encoded symbol stream C(s) and to occurrence statistics n i , Q(i), Q(m), and N, which correspond respectively to the count of occurrences of the symbol i, the sum of the counts n 0 through n i-1 , the sum of the counts n 0 through n m-1 , and the count of all symbols in the portion of the string s preceding the symbol i for recursively modifying a code string C(s) to produce C(si), where C(si) is a compressed representation of the string si and si is the string s followed by the symbol i, comprising: a first shift register containing the w-most-significant bits of C(s); a second shift register containing an interval decoding variable; means responsive to N for normalizing n i , Q(i), and Q(m) based upon the normalization of N to a predetermined range; means for determining a symbol j in said alphabet such that the normalized value of Q(j)≦the contents of the first shift register; first arithmetic means for subtracting the normalized value of Q(j) from the contents of the first register; second arithmetic means for placing the normalized value of n j into the second register if j≠m or for subtracting the normalized value of Q(m) from the contents of the second register if j=m; and shift means for simultaneously shifting the contents of the first and second registers in a predetermined magnitude direction until the contents of the second register lie within said predetermined range and for shifting the next-most-significant portion of C(s) into the portion of the first register vacated by said simultaneous shifting.
Claim 16
Dependent Claim
16 words
The decoder of claim 11 wherein said predetermined range is (0.11 binary , 1.1 binary ).
References Cited (Backward Citations)
US4122440A
Cited
US4259693A
Cited
US4286256A
Cited
US4295125A
Cited
US4420771A
Cited
US4467317A
Cited
US4494108A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1990-03-23 | 1990-09-22 | 1991-03-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1994-03-23 | 1994-09-22 | 1995-03-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1998-03-23 | 1998-09-22 | 1999-03-24 | $7700.00 | Window Closed / Lapsed |