High-speed arithmetic compression coding using concurrent value updating

Claim 2

A machine-implementable method for recursively generating an arithmetically compressed binary number steam C(s.b) in high-to-low position magnitude order responsive to successive symbols b(i) from a binary symbol string s=b(1), b(2), . . . b(i), . . . , b(n), in a reduced number of operations per encoding cycle, comprising the steps of: writing the q-least-significant bits of C(s) and an internal variable T(s) into respective first and second shift registers; and ascertaining for each b(i) whether it constitutes a most-probable symbol (MPS); and deriving an integer k as a coding parameter indicative of an expectation for the least-probable symbol (LPS); characterized in that the method comprises the further steps of: concurrently incrementing the first register contents and decrementing the second register contents by 2 -k and left-shift normalizing both register contents if the second register contains a leading zero, if b(i) is an MPS; and left-shifting the first register contents by k positions and setting the second register contents to unity, if b(i) is an LPS.

Claim 3

An encoding apparatus for recursively altering a compressed bit stream representation of a string of binary symbols in a reduced number of operations per symbol encoding cycle comprising: a first (41) and second (59) shift register containing the q-least-significant bits of the compressed stream C(s) and an internal variable T(s); means (31, 33) for characterizing each received symbol as either a most-probable symbol (MPS) or a least-probable symbol (LPS); characterized in that the apparatus further comprises: means (9, 35, 39, 47) responsive to an LPS symbol characterization and to a parameter k whose values correspond to a predetermined source alphabet probability interval for shifting out the k-most-significant bits in the first register and zero-filling the k-least-significant bit positions therein, said means further including means for setting the second register contents to unity; and means (49, 63, 53, 55) for concurrently incrementing the first register contents by 2 -k and decrementing the second register contents by 2 -k , left-shift normalizing (67, 53, 55) both register contents if the second register contains a leading zero in response to an MPS symbol characterization and the parameter k.

Claim 4

An encoding apparatus for recursively altering a compressed bit stream representation of a string of binary symbols in a reduced number of operations per symbol encoding cycle comprising: a first (41) and second (59) shift register containing the q-least-significant bits of the compressed stream C(s) and an internal variable T(s); means (31, 33) for characterizing each received symbol as either a most-probable symbol (MPS) or a least-probable symbol (LPS); characterized in that the apparatus further comprises: means (9, 35, 39, 47) responsive to an LPS symbol characterization and to a parameter k whose values correspond to a predetermined source alphabet probability interval for shifting out the k-most-significant bits in the first register and zero-filling the k-least-significant bit positions therein, said means further including means for setting the second register contents to unity; and means (49, 63, 53, 55) for concurrently incrementing the first register contents by 2 -k and decrementing the second register contents by 2 -k , left-shift normalizing (67, 53, 55) both register contents if the second register contains a leading zero in response to an MPS symbol characterization and the parameter k.

Claim 5

An encoder for recursively generating an arithmetically compressed binary number stream C(sb) in high-to-low position magnitude order responsive to a binary character string, each character being identified as either a most-probable symbol (MPS) or a least-probable symbol (LPS) and having associated therewith a parameter k whose value corresponds to a predetermined source alphabet probability interval, comprising: a first- (41) and second- (59) shift register containing the q-least-significant bits of the compressed stream and an internal variable; characterized in that the encoder further comprises: means (9, 47, 39, 35) responsive to each ordered pair MPS, k for shifting out the k-most-significant bits and zero-filling the k-least-significant bits of the first register and setting (CLEAR) the second register contents to unity; and a first and second computation loop (49, 51, 53, 37; 63, 65, 55, 57) for additively combining 2 -k to the first register contents and subtractively combining 2 -k from the second register contents, said first and second loop including means (67, 53, 55) for left-shift normalizing both register contents if the second register contains a leading zero responsive to each ordered pair of LPS, k.

Claim 6

An encoder for recursively generating an arithmetically compressed binary number stream C(sb) in high-to-low position magnitude order responsive to a binary character string, each character being identified as either a most-probable symbol (MPS) or a least-probable symbol (LPS) and having associated therewith a parameter k whose value corresponds to a predetermined source alphabet probability interval, comprising: a first- (41) and second- (59) shift register containing the q-least-significant bits of the compressed stream and an internal variable; characterized in that the encoder further comprises: means (9, 47, 39, 35) responsive to each ordered pair MPS, k for shifting out the k-most-significant bits and zero-filling the k-least-significant bits of the first register and setting (CLEAR) the second register contents to unity; and a first and second computation loop (49, 51, 53, 37; 63, 65, 55, 57) for additively combining 2 -k to the first register contents and subtractively combining 2 -k from the second register contents, said first and second loop including means (67, 53, 55) for left-shift normalizing both register contents if the second register contains a leading zero responsive to each ordered pair of LPS, k.

Claim 7

A machine-implementable method for recursively generating successive symbols b(i) of a binary symbol string s=b(1), b(2), . . . b(i), . . . , b(n) responsive to successive high-to-low position magnitude order bits of an arithmetically compressed binary number stream C(s.b) using a reduced number of operations per decoding cycle, comprising the steps of: writing the q-most significant bits of C(s.b) and an internal variable T(s) into respective first and second shift registers; deriving an integer k(i) as a coding parameter indicative of an expectation that the decodable symbol is a least-probable symbol (LPS); characterized in that the method comprises the further steps of: concurrently decrementing the first and second register contents by 2 -k (i) ; testing the most-significant bit position of the first register; left-shift normalizing both register contents if the tested bit position is 1 and decoding the symbol as a most-probable symbol; and left-shifting the first register contents by k positions and setting the second register contents to unity if the tested bit position is a 0, and decoding the symbol as an LPS.

Claim 8

A machine-implementable method for recursively generating successive symbols b(i) of a binary symbol string s=b(1), b(2), . . . b(i), . . . , b(n) responsive to successive high-to-low position magnitude order bits of an arithmetically compressed binary number stream C(s.b) using a reduced number of operations per decoding cycle, comprising the steps of: writing the q-most significant bits of C(s.b) and an internal variable T(s) into respective first and second shift registers; deriving an integer k(i) as a coding parameter indicative of an expectation that the decodable symbol is a least-probable symbol (LPS); characterized in that the method comprises the further steps of: concurrently decrementing the first and second register contents by 2 -k (i) ; testing the most-significant bit position of the first register; left-shift normalizing both register contents if the tested bit position is 1 and decoding the symbol as a most-probable symbol; and left-shifting the first register contents by k positions and setting the second register contents to unity if the tested bit position is a 0, and decoding the symbol as an LPS.