A method of generating a compressed representation of a source data string

Claim 1

A method of generating a compressed representation R(comp) of a source data string STR, wherein: each symbol is taken from a finite set of m+1 symbols a₀ ...a m , said compressed representation being a numeric value within a given range and being generated recursively in successive cycles for successive symbols in the string, a probability value p(i) and a cumulative probability value S(i) being available for each symbol a i , said cumulative probability value being S(i) = p(0) + p(1) + ... + p(i-1) for i = 1...m, S(0) = 0, and using a pair of shift registers A and C each comprising ω binary digit positions, characterized by following steps: (a) initially setting the contents of the C register to all zeros and the contents of the A register to a predetermined value; and for each successive symbol a in the string: (b) determining a scaling factor K by taking the contents of the A register and eliminating all binary digits less significant than a predetermined binary one digit; (c) adding the value K · S(i) to the contents of the C register; (d) determining the contents of the A register (d1) if the symbol a i is not the symbol a m by inserting the vaule K · p(i) into the A register, or (d2) if the symbol a i is the symbol a m , by subtracting the value K · S(i) from the contents of the A register; (e) 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 with zeros; and (f) if the symbol a i were not the last symbol in string STR, repeating steps (b) to (e), or, if the symbol a i were the last symbol in string STR, shifting the contents of the C register by ω positions in said predetermined direction; whereby the sequence of binary digits shifted out of the C register constitutes said compressed representation R(comp) of the symbol string STR.

Claim 2

A method of generating a compressed representation R(comp) of a source data string STR, wherein: each symbol is taken from a finite set of m+1 symbols a₀ ...a m , said compressed representation being a numeric value within a given range and being generated recursively in successive cycles for successive symbols in the string, a probability value p(i) and a cumulative probability value S(i) being available for each symbol a i , said cumulative probability value being S(i) = p(0) + p(1) + ... + p(i-1) for i = 1...m, S(0) = 0, and using a pair of shift registers A and C each comprising ω binary digit positions, characterized by following steps: (a) initially setting the contents of the C register to all zeros and the contents of the A register to a predetermined value; and for each successive symbol a in the string: (b) determining a scaling factor K by taking the contents of the A register and eliminating all binary digits less significant than a predetermined binary one digit; (c) adding the value K · S(i) to the contents of the C register; (d) determining the contents of the A register (d1) if the symbol a i is not the symbol a m by inserting the vaule K · p(i) into the A register, or (d2) if the symbol a i is the symbol a m , by subtracting the value K · S(i) from the contents of the A register; (e) 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 with zeros; and (f) if the symbol a i were not the last symbol in string STR, repeating steps (b) to (e), or, if the symbol a i were the last symbol in string STR, shifting the contents of the C register by ω positions in said predetermined direction; whereby the sequence of binary digits shifted out of the C register constitutes said compressed representation R(comp) of the symbol string STR.

Claim 7

A method of decoding a compressed representation R(comp) of a source data string STR, wherein: each symbol is taken from a finite set of m+1 symbols a₀ ...a m , said compressed representation being a numeric value within a given range, a probability value p(i) and a cumulative probability value S(i) being available for each symbol a i , said cumulative probability value being S(i) = p(0) + p(1) + ... + p(i-1) for i = 1...m, S(0) = 0, and using a pair of shift registers A and C each comprising ω binary digit positions, characterized by following steps: (a) initially setting the contents of the C register to the ω most significant digits of the compressed representation R(comp), and the contents of the A register to a predetermined value; and decoding each successive symbol a i in the source data string STR by: (b) determining a scaling factor K by taking the contents of the A register and eliminating all binary digits less significant than a predetermined binary one digit; (c) determining the largest value of j such that C ≧ K · S(j) where: C is interpreted as a binary fraction with a binary point outside the C register adjacent to the most significant binary digit therein, and a j is the symbol output by the decoder at the current step; (d) determining the contents of the A register (d1) if the symbol a j is not the symbol a m by inserting the value K · p(j) into the A register, or (d2) if the symbol a j is the symbol a m , by subtracting the value K · S(j) from the contents of the A register; (e) subtracting the value K · S(j) from the contents of the C 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 zeros and filling the vacated positions in the C register with the corresponding number of most significant digits remaining in the compressed representation R(comp), and repeating steps (b) to (f) until R(comp) is empty.

Claim 8

A method of decoding a compressed representation R(comp) of a source data string STR, wherein: each symbol is taken from a finite set of m+1 symbols a₀ ...a m , said compressed representation being a numeric value within a given range, a probability value p(i) and a cumulative probability value S(i) being available for each symbol a i , said cumulative probability value being S(i) = p(0) + p(1) + ... + p(i-1) for i = 1...m, S(0) = 0, and using a pair of shift registers A and C each comprising ω binary digit positions, characterized by following steps: (a) initially setting the contents of the C register to the ω most significant digits of the compressed representation R(comp), and the contents of the A register to a predetermined value; and decoding each successive symbol a i in the source data string STR by: (b) determining a scaling factor K by taking the contents of the A register and eliminating all binary digits less significant than a predetermined binary one digit; (c) determining the largest value of j such that C ≧ K · S(j) where: C is interpreted as a binary fraction with a binary point outside the C register adjacent to the most significant binary digit therein, and a j is the symbol output by the decoder at the current step; (d) determining the contents of the A register (d1) if the symbol a j is not the symbol a m by inserting the value K · p(j) into the A register, or (d2) if the symbol a j is the symbol a m , by subtracting the value K · S(j) from the contents of the A register; (e) subtracting the value K · S(j) from the contents of the C 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 zeros and filling the vacated positions in the C register with the corresponding number of most significant digits remaining in the compressed representation R(comp), and repeating steps (b) to (f) until R(comp) is empty.