Arithmetic compression coding using interpolation for ambiguous symbols

Claim 1

An apparatus for arithmetically encoding a pattern of symbols including arithmetically encoding ambiguous symbols so as to effectuate a compressed code string thereof, said symbols in said pattern being taken from a finite symbol set, each symbol appearing in a position of said pattern, said compressed code string being a digital signal representation of a number based on the probabilities of said symbols appearing in a predetermined order in said pattern, comprising: first register means for receiving at least a portion of the pattern of symbols; second register means for storing and shifting out elements of the compressed code string of said pattern of symbols; means (FIG. 7 - 3,4,6) for determining predictable positions PP and unpredictable positions UP in the pattern in said first register means including means for evaluating a given first sub-pattern of the symbols in said first register positions in the vicinity of each first register position representing a context, a UP being defined when the register position sub pattern contains any one of a set of selected symbol sub patterns, and a PP being defined in all other cases; and means (FIG. 7 - 5) responsive to the prediction means for arithmetically encoding each symbol in the first register occupying a PP using the symbol's probability in the respective position or context and including means for arithmetically encoding each symbol in the register occupying a UP using the combined probability of a predetermined set of possible symbols which could appear in the respective positions, and placing the arithmetically encoded symbols in the second register means.

Claim 2

An apparatus for arithmetically encoding a pattern of symbols including arithmetically encoding ambiguous symbols so as to effectuate a compressed code string thereof, said symbols in said pattern being taken from a finite symbol set, each symbol appearing in a position of said pattern, said compressed code string being a digital signal representation of a number based on the probabilities of said symbols appearing in a predetermined order in said pattern, comprising: first register means for receiving at least a portion of the pattern of symbols; second register means for storing and shifting out elements of the compressed code string of said pattern of symbols; means (FIG. 7 - 3,4,6) for determining predictable positions PP and unpredictable positions UP in the pattern in said first register means including means for evaluating a given first sub-pattern of the symbols in said first register positions in the vicinity of each first register position representing a context, a UP being defined when the register position sub pattern contains any one of a set of selected symbol sub patterns, and a PP being defined in all other cases; and means (FIG. 7 - 5) responsive to the prediction means for arithmetically encoding each symbol in the first register occupying a PP using the symbol's probability in the respective position or context and including means for arithmetically encoding each symbol in the register occupying a UP using the combined probability of a predetermined set of possible symbols which could appear in the respective positions, and placing the arithmetically encoded symbols in the second register means.

Claim 4

A method for recursively mapping successive symbols drawn from a Markov source of predetermined order and finite alphabet from a first register into digital signals representative of a compression of the successive symbols and of a magnitude of an ever lengthening fraction in the bounded l0,1 interval in a second register, the mapping being a function of the instantaneous value of the fraction and predetermined occurrence statistics of the symbols in the alphabet and of the Markov source including the statistics of the current being encoded, comprising the steps of: (a) with respect to the current symbol resident in said first register, ascertaining whether its occurrence statistic lies within a predetermining range by referencing a memory stored table, and, providing auxiliary signal indication of a first kind (UP) if said statistic does so lie and auxiliary signal indication of a second kind (PP) otherwise; (b) for each signal indication of the first kind, interpolating a value to be appended to the ever lengthening fraction resident in the second register as an arithmetically encoded function of the instantaneous value of the fraction and the occurrence statistics of a predetermined number of adjacent successive symbols selectively positioned before or after the current symbol being encoded; and (c) for each signal indication of the second kind, appending digital signals indicative of a value to the ever lengthening fraction resident in the second register as an arithmetically encoded function of the instantaneous value of the fraction and the occurrence statistic of the current symbol being encoded.

Claim 5

A method for recursively mapping successive symbols drawn from a Markov source of predetermined order and finite alphabet from a first register into digital signals representative of a compression of the successive symbols and of a magnitude of an ever lengthening fraction in the bounded l0,1 interval in a second register, the mapping being a function of the instantaneous value of the fraction and predetermined occurrence statistics of the symbols in the alphabet and of the Markov source including the statistics of the current being encoded, comprising the steps of: (a) with respect to the current symbol resident in said first register, ascertaining whether its occurrence statistic lies within a predetermining range by referencing a memory stored table, and, providing auxiliary signal indication of a first kind (UP) if said statistic does so lie and auxiliary signal indication of a second kind (PP) otherwise; (b) for each signal indication of the first kind, interpolating a value to be appended to the ever lengthening fraction resident in the second register as an arithmetically encoded function of the instantaneous value of the fraction and the occurrence statistics of a predetermined number of adjacent successive symbols selectively positioned before or after the current symbol being encoded; and (c) for each signal indication of the second kind, appending digital signals indicative of a value to the ever lengthening fraction resident in the second register as an arithmetically encoded function of the instantaneous value of the fraction and the occurrence statistic of the current symbol being encoded.