Method and system for efficient, multiplication-free arithmetic coding

Claim 1

In a data transmission system, a data compression system comprising: means for inputting a first set of data representing an alphabet of source symbols including a current symbol; means for generating for each source symbol an arithmetic representation of a successive subinterval within a predetermined interval, the width of each subinterval being equal to the width of the previous subinterval weighted by the current symbol's frequency of occurrence; means for approximating the width of a new subinterval with a single shift and add operation as a function of both the width of the current subinterval and a total count of source symbols in a statistical source model; and means for outputting a second set of data based on the arithmetic representations, whereby the second set of data is a compressed representation of the alphabet of source symbols.

Claim 3

A method for compressing data in a data transmission system including an "A" shift register and a "C" shift register each having w binary digit positions, the method comprising the steps of: (a) initially setting the contents of the "C" register to all zeroes and the contents of the "A" register to a predetermined value; (b) inputting a first set of data representing an alphabet of source symbols including a current symbol, an individual frequency value n i (s) and an accumulated frequency value r i (s) being available for each of the source symbols; and for each of the source symbols: (c) determining a scaling factor B as a function of the contents of the "A" register and a total count of source symbols in a statistical source model; (d) adding the value B*r i (s) to the contents of the "C" register; (e) determining the contents of the "A" register if the current symbol is not the last symbol of the alphabet of source symbols, by inserting the value B*n i (s) into the "A" register; or if the current symbol is the last symbol of the alphabet of source symbols, by subtracting the value B*r i (s) from the contents of the "A" register; (f) shifting both the "A" register and the " C" register in a predetermined direction until the contents of the "A" register lie within a predetermined range, filling the vacated positions in the "A" register with zeroes; and (g) if the current symbol is not the last symbol of the source symbols, repeating steps (c) through (f), or if the current symbol is the last symbol of the source symbols, shifting the contents of the "C" register by w positions in said predetermined direction; whereby the sequence of binary digits shifted out of the "C" register is a compressed representation of the source symbols.

Claim 4

A method for compressing data in a data transmission system including an "A" shift register and a "C" shift register each having w binary digit positions, the method comprising the steps of: (a) initially setting the contents of the "C" register to all zeroes and the contents of the "A" register to a predetermined value; (b) inputting a first set of data representing an alphabet of source symbols including a current symbol, an individual frequency value n i (s) and an accumulated frequency value r i (s) being available for each of the source symbols; and for each of the source symbols: (c) determining a scaling factor B as a function of the contents of the "A" register and a total count of source symbols in a statistical source model; (d) adding the value B*r i (s) to the contents of the "C" register; (e) determining the contents of the "A" register if the current symbol is not the last symbol of the alphabet of source symbols, by inserting the value B*n i (s) into the "A" register; or if the current symbol is the last symbol of the alphabet of source symbols, by subtracting the value B*r i (s) from the contents of the "A" register; (f) shifting both the "A" register and the " C" register in a predetermined direction until the contents of the "A" register lie within a predetermined range, filling the vacated positions in the "A" register with zeroes; and (g) if the current symbol is not the last symbol of the source symbols, repeating steps (c) through (f), or if the current symbol is the last symbol of the source symbols, shifting the contents of the "C" register by w positions in said predetermined direction; whereby the sequence of binary digits shifted out of the "C" register is a compressed representation of the source symbols.

Claim 8

A method for decompressing data which is a compressed representation of a number of source symbols in a data transmission system including an "A" shift register and a "C" shift register each having w binary digit positions, the method comprising the steps of: (a) inputting a first set of data which is a compressed representation of an alphabet of source symbols including a current symbol, an individual frequency value n i (s) and an accumulated frequency value r i (s) being available for each of the source symbols; (b) initially setting the contents of the "C" register to the w most significant digits of the compressed representation and the contents of the "A" register to a predetermined value; decoding each of the source symbols by: (c) determining a scaling factor B as a function of the contents of the "A" register and the number of source symbols; (d) determining the largest value of the symbol i such that B*r i ≦C, where ##EQU18## wherein i is the symbol output of the decoder at the current step; (e) determining the contents of the "A" register if the current symbol is not the last symbol of the alphabet of source symbols, by inserting the value B*n i (s) into the "A" register; or if the current symbol is the last symbol of the alphabet of source symbols, by subtracting the value B*r i (s) from the contents of the "A" register; (f) subtracting the value B*r i (s) from the contents of the "C" register; (g) shifting both the "A" register and the "C" register in a predetermined direction until the contents of the "A" register lie within a predetermined range, filling the vacated positions in the "A" register with zeroes, and filling the vacated positions in the "C" register with the corresponding number of most significant digits remaining of the compressed representation; and repeating steps (c) through (g) until no digits of the compressed representation remain.

Claim 9

A method for decompressing data which is a compressed representation of a number of source symbols in a data transmission system including an "A" shift register and a "C" shift register each having w binary digit positions, the method comprising the steps of: (a) inputting a first set of data which is a compressed representation of an alphabet of source symbols including a current symbol, an individual frequency value n i (s) and an accumulated frequency value r i (s) being available for each of the source symbols; (b) initially setting the contents of the "C" register to the w most significant digits of the compressed representation and the contents of the "A" register to a predetermined value; decoding each of the source symbols by: (c) determining a scaling factor B as a function of the contents of the "A" register and the number of source symbols; (d) determining the largest value of the symbol i such that B*r i ≦C, where ##EQU18## wherein i is the symbol output of the decoder at the current step; (e) determining the contents of the "A" register if the current symbol is not the last symbol of the alphabet of source symbols, by inserting the value B*n i (s) into the "A" register; or if the current symbol is the last symbol of the alphabet of source symbols, by subtracting the value B*r i (s) from the contents of the "A" register; (f) subtracting the value B*r i (s) from the contents of the "C" register; (g) shifting both the "A" register and the "C" register in a predetermined direction until the contents of the "A" register lie within a predetermined range, filling the vacated positions in the "A" register with zeroes, and filling the vacated positions in the "C" register with the corresponding number of most significant digits remaining of the compressed representation; and repeating steps (c) through (g) until no digits of the compressed representation remain.