Patent US4286256A successfully refreshed from Google Patents.
US4286256A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and means for arithmetic coding utilizing a reduced number of operations
Assignee: International Business Machines Corp
•
Filing: 1979-11-28
•
Granted: 1981-08-25
•
Expires: 1999-11-28
Abstract
Abstract A method and means of arithmetic coding of conditional binary sources permitting instantaneous decoding and minimizing the number of encoding operations per iteration. A single shift and subtract operation for each encoding cycle can be achieved if an integer valued parameter representative of a probability interval embracing each source symbol relative frequency is used for string encoding and control. If the symbol being encoded is the most probable, then nothing is added to the arithmetic code string. However, an internal variable is updated by replacing it with an augend amount. If the updated internal variable has a leading zero, then both it and the code string are shifted left by one position. If the symbol being encoded is the least probable, then a computed augend is added to the code string and the code string is shifted by an amount equal to the integer valued parameter.
Inventors
- 👤 Glen G. Langdon, Jr.
- 👤 Jorma J. Rissanen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 23:32
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/4006
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
221 words
In an apparatus for generating an instantaneous FIFO binary arithmetic code string C(sb) recursively formed by the high-to-low order pairwise combining of digits of a decodable set of relatively shifted finite binary number strings C(s), A(sb) responsive to each binary symbol b in the symbol string s; q of the lowest order bits of each string being combined during each recursion, wherein the improvement comprises: a first (201 FIG. 7) and second (17 FIG. 3) register means for storing respectively at least q of the lowest order bits of C(s) and a number string T(s); first means (2,3 FIG. 2; FIG. 6) responsive to each applied symbol b for obtaining an integer valued parameter k indicative of its relative frequency; second means (FIG. 3) responsive to each symbol b and parameter k for forming A(sb), T(sb) such that: T(sb) or A(sb)=T(s)[1-2.sup.-k ] third means (3,39,31,24) for forming a code string shift amount (SA) either of magnitude k when b is a first-bit value (b(1)=1) or of a second magnitude according to the value in a designated bit position (msb) in the second register; and fourth means (6,7,203,205,207) responsive to the shift amount and A(sb) for combining A(sb) with C(s) in the first register (201) to form C(sb) and for left shifting (6,205) the first register contents according to the shift amount.
Claim 2
Dependent Claim
221 words
In an apparatus for generating an instantaneous FIFO binary arithmetic code string C(sb) recursively formed by the high-to-low order pairwise combining of digits of a decodable set of relatively shifted finite binary number strings C(s), A(sb) responsive to each binary symbol b in the symbol string s; q of the lowest order bits of each string being combined during each recursion, wherein the improvement comprises: a first (201 FIG. 7) and second (17 FIG. 3) register means for storing respectively at least q of the lowest order bits of C(s) and a number string T(s); first means (2,3 FIG. 2; FIG. 6) responsive to each applied symbol b for obtaining an integer valued parameter k indicative of its relative frequency; second means (FIG. 3) responsive to each symbol b and parameter k for forming A(sb), T(sb) such that: T(sb) or A(sb)=T(s)[1-2.sup.-k ] third means (3,39,31,24) for forming a code string shift amount (SA) either of magnitude k when b is a first-bit value (b(1)=1) or of a second magnitude according to the value in a designated bit position (msb) in the second register; and fourth means (6,7,203,205,207) responsive to the shift amount and A(sb) for combining A(sb) with C(s) in the first register (201) to form C(sb) and for left shifting (6,205) the first register contents according to the shift amount.
Claim 3
Dependent Claim
44 words
In an apparatus according to claim 1, wherein the second means include: means (3,18,19) for right-shifting a copy of the second register (17) contents by k positions; means (18,20-28) for subtracting the shifted copied contents T(s) 2 -k from the unshifted second register contents.
Claim 4
Dependent Claim
155 words
In the second means according to claim 2, wherein: the means for right-shifting the second register contents includes: a barrel shifter (19) having a right-hand spill output (20), an input adapted to receive n bits in parallel from the second register (17); a shift controller; and an n bit parallel output means (22); the means for subtracting the shifted contents from the unshifted contents of the second register include: a binary adder (26) having a first n bit parallel input from the second register; and means (23, 24) for complementing the output from the barrel shifter and applying said complemented output as a second input to the binary adder; said means for forming a shift amount includes: a circuit (39) coupling the first means output and a predetermined value source (29,54,38), the circuit selecting the first means output or the value source according to whether the symbol b is the least or most probable (31).
Claim 5
Dependent Claim
69 words
In an apparatus according to claim 1, wherein the apparatus further comprises: means (12) for detecting the presence of n consecutive characters of a first kind (1's) in the code string C(sb) after each recursive string formation interval; and means responsive to the detection of n characters of the first kind for increasing the combined string length by at least one position and for inserting a control character therein.
Claim 6
Dependent Claim
69 words
In an apparatus according to claim 1, wherein said first means (FIG. 6) includes: memory means for storing the least probable symbol identity and the counterpart integer parameter k and the most probable symbol identity and the counterpart integer parameter k at distinct locations; and means for accessing the least or most probable symbol identity and associated parameter k values responsive to the binary symbol value b applied thereto.
Claim 7
Dependent Claim
67 words
In the fourth means according to claim 1, wherein: the means for combining A(sb) with C(s) in the first register (201) includes: an adder (203) having a discrete sum (11) and carry (9) outputs; the means for left shifting the first register contents includes: a barrel shifter (205) coupling the sum output from the adder and left shifting responsive to the shift amount control (6) applied thereto.
Claim 8
Dependent Claim
185 words
In an apparatus for reconstructing a binary symbol string s=b(1) b(2) . . .b(i) . . .b(n) from an instantaneous FIFO binary arithmetic code C, wherein the improvement comprises: a first (54 FIG. 5) and a second (55 FIG. 5) register means for storing respective at least q of the lowest order bits of C and a number string T; first means (48-51 FIG. 4, FIG. 6) responsive to each decoded symbol b(i) for obtaining an integer valued parameter k indicative of its relative frequency of occurrence; second means (FIG. 5) for forming a test augend (TA) yielding: TA=T[1-2.sup.-k ]; third means (54,46,92) for carry modifying the contents of the second register; fourth means (65-72) for generating the sign and magnitude difference between the trial augend TA and the carry modified second register contents C; fifth means (50,79,93) for generating the symbol b(i) as having a first binary value (0) if TA>C and for generating b(i) having a second binary value (1) if TA≦C; and sixth means for updating the contents of the first and second registers according as to whether either TA≦C or TA>C.
Claim 9
Dependent Claim
185 words
In an apparatus for reconstructing a binary symbol string s=b(1) b(2) . . .b(i) . . .b(n) from an instantaneous FIFO binary arithmetic code C, wherein the improvement comprises: a first (54 FIG. 5) and a second (55 FIG. 5) register means for storing respective at least q of the lowest order bits of C and a number string T; first means (48-51 FIG. 4, FIG. 6) responsive to each decoded symbol b(i) for obtaining an integer valued parameter k indicative of its relative frequency of occurrence; second means (FIG. 5) for forming a test augend (TA) yielding: TA=T[1-2.sup.-k ]; third means (54,46,92) for carry modifying the contents of the second register; fourth means (65-72) for generating the sign and magnitude difference between the trial augend TA and the carry modified second register contents C; fifth means (50,79,93) for generating the symbol b(i) as having a first binary value (0) if TA>C and for generating b(i) having a second binary value (1) if TA≦C; and sixth means for updating the contents of the first and second registers according as to whether either TA≦C or TA>C.
Claim 10
Dependent Claim
41 words
In an apparatus according to claim 7, wherein the second means include: means (16,49,57) for right-shifting a copy of the second register contents by k positions; and means (56,58,60) for subtracting the shifted copied contents from the unshifted second register contents.
Claim 11
Dependent Claim
68 words
In an apparatus according to claim 7, wherein said first means (FIG. 6) includes: memory means for storing the least probable symbol identity and the counterpart integer parameter k, and the most probable symbol identity and the counterpart integer parameter k at distinct locations; and means for accessing the least or most probable symbol identity and associated parameter k responsive to the binary symbol value b applied thereto.
Claim 12
Dependent Claim
86 words
In an apparatus according to claim 7, wherein the sixth means for updating the contents of the first and second registers includes: means (84) for shifting the difference output from the fourth means (68,69) k positions to the left and appending the left-most k bits from the code string applied to the apparatus; means (79) for selectively inserting the output of the third means (92) or the shifted and appended string form insertion into the first register according as to the value of the symbol decoded.
Claim 13
Dependent Claim
34 words
In an apparatus according to claims 1 or 7, wherein the integer valued parameter k is inversely proportional to the relative frequency of occurrence of the least probable symbol in a binary source alphabet.
References Cited (Backward Citations)
US4122440A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1984-08-24 | 1985-02-23 | 1985-08-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1988-08-24 | 1989-02-23 | 1989-08-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1992-08-24 | 1993-02-23 | 1993-08-25 | $7700.00 | Window Closed / Lapsed |