US 4,286,256 A · Method and means for arithmetic coding utilizing a reduced number of operations

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.

Claims11

Dependent claims

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.

6 more elements

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.ltoreq.C;
and
sixth means for updating the contents of the first and second registers according as to whether either TA.ltoreq.C or TA>C.

6 more elements

Dependencies are inferred from the claim text.

Method and means for arithmetic coding utilizing a reduced number of operations

Life of this patent

Method and means for arithmetic coding utilizing a reduced number of operations

Life of this patent

Abstract

Claims11