Front Page

Title
Adaptive probability estimator for entropy encoding/decoding
Claims
  1. An adaptive probability estimator for generating probability estimates of a supplied signal having a plurality of symbol values in a supplied context to be used in entropy encoding/decoding, comprising:
    a source of the supplied signal;
    means for obtaining representations of accumulated occurrences of individual symbol values of said supplied signal in said supplied context; and
    means responsive to said representations of accumulated occurrences for adjusting a rate of adaptation of the adaptive probability estimator in accordance with a prescribed criterion, said means for adjusting including means for obtaining at least a first prescribed characteristic of said representations of accumulated occurrences and means responsive to said first prescribed characteristic for proportionately adjusting said representations of accumulated occurrences when said first prescribed characteristic meets said prescribed criterion.
  2. The adaptive probability estimator as defined in claim 1 wherein said at least first prescribed characteristic is dependent on one of said representations of individual representations of accumulated occurrences associated with a symbol value that has occurred least often in said supplied context.
  3. The adaptive probability estimator as defined in claim 1 wherein said at least first prescribed characteristic is the minimum one of said individual representations of accumulated occurrences.
  4. The adaptive probability estimator as defined in claim 3 wherein said first prescribed criterion comprises said at least prescribed characteristic exceeding a first threshold.
  5. The adaptive probability estimator as defined in claim 1 further including means for obtaining an at least second prescribed characteristic of said representations of accumulated occurrences and means for utilizing said at least second characteristic to limit values of said individual representations of accumulated occurrences.
  6. The adaptive probability estimator as defined in claim 5 wherein said at least prescribed second characteristic is one of said representations of accumulated occurrences having a maximum value in said supplied context and said means for utilizing said at least second prescribed characteristic includes means responsive to said at least second prescribed characteristic to limit said representations of accumulated occurrences when said at least second prescribed characteristic exceeds a second threshold.
  7. An adaptive encoder for encoding a supplied signal having a plurality of symbol value including,
    a source of the supplied signal,
    means for extracting a context of the supplied signal,
    adaptive probability estimator means supplied with said signal and said context for generating probability estimates of the supplied signal,
    entropy encoder means supplied with said signal and responsive to said probability estimates for generating an encoded version of said supplied signal,
    means for interfacing said encoded version as an output to a medium,
    said adaptive probability estimator means being characterized by
    means for obtaining representations of accumulated occurrences of individual symbol values of said supplied signal in said supplied context, and
    means responsive to said representations of accumulated occurrences for adjusting a rate of adaptation of the adaptive probability estimator in accordance with a prescribed criterion, said means for adjusting including means for obtaining at least a first prescribed characteristic of said representations of accumulated occurrences and means responsive to said first prescribed characteristic for proportionately adjusting said representations of accumulated occurrences when said first prescribed characteristic meets said prescribed criterion.
  8. The adaptive encoder as defined in claim 7 wherein said at least first prescribed characteristic is dependent on one of said individual representations of accumulated occurrences associated with a symbol value that has occurred least often in said supplied context.
  9. The adaptive encoder as defined in claim 7 wherein said at least first prescribed characteristic is the minimum one of said individual representations of accumulated occurrences.
  10. The adaptive encoder as defined in claim 9 wherein said prescribed criterion comprises said at least first prescribed characteristic exceeding a first threshold.
  11. The adaptive encoder as defined in claim 7 further including means for obtaining an at least second prescribed characteristic of said representations of accumulated occurrences and means for utilizing said at least second characteristic to limit values of said individual representations of accumulated occurrences.
  12. The adaptive encoder as defined in claim 11 wherein said at least second prescribed characteristic is one of said representations of accumulated occurrences having a maximum value in said supplied context and said means for utilizing said at least second prescribed characteristic includes means responsive to said at least second prescribed characteristic to limit said representations of accumulated occurrences when said at least second prescribed characteristic exceeds a second threshold.
  13. The adaptive encoder as defined in claim 7 wherein said means for interfacing said encoded version to a medium includes means for interfacing the encoder to a transmission line.
  14. An adaptive decoder for reconstructing an original signal having a plurality of symbol values from a compressed data signal including,
    means for interfacing to a medium for obtaining the compressed data signal,
    means for determining a context for the symbol to be reconstructed,
    adaptive probability estimator means supplied with a reconstructed signal and said context for generating probability estimates of the reconstructed signal,
    entropy decoder means supplied with said compressed data signal and responsive to said probability estimates for reconstructing an original signal,
    said adaptive probability estimator means being characterized by
    means for obtaining representations of accumulated occurrences of individual symbol values of said supplied signal is said supplied context, and
    means responsive to said representations of accumulated occurrences for adjusting a rate of adaptation of the adaptive probability estimator in accordance with a prescribed criterion, said means for adjusting including means for obtaining at least a first prescribed characteristic of said representations of accumulated occurrences and means responsive to said first prescribed characteristic for proportionately adjusting said representations of accumulated occurrences when said first prescribed characteristic meets said prescribed criterion.
  15. The adaptive decoder as defined in claim 14 wherein said at least first prescribed characteristic is dependent on one of said individual representations of accumulated occurrences associated with a symbol value that has occurred least often in said supplied context.
  16. The adaptive decoder as defined in claim 14 wherein said at least first prescribed characteristic is the minimum one of said individual representations of accumulated occurrences.
  17. The adaptive decoder as defined in claim 16 wherein said prescribed criterion comprises said at least first prescribed characteristic exceeding a first threshold.
  18. The adaptive decoder as defined in claim 14 further including means for obtaining an at least second prescribed characteristic of said representations of accumulated occurrences and means for utilizing said at least second prescribed characteristic to limit values of said individual representations of accumulated occurrences.
  19. The adaptive decoder as defined in claim 18 wherein said at least second prescribed characteristic is one of said representations of accumulated occurrences having a maximum value in said supplied context and said means for utilizing said at least second prescribed characteristic includes means responsive to said at least second prescribed characteristic to limit said representations of accumulated occurrences when said at least second prescribed characteristic exceeds a second threshold.
  20. The adaptive decoder as defined in claim 14 wherein said means for interfacing includes means for interfacing to a transmission line.
  21. A method of encoding a supplied signal having a plurality of symbol values including the steps of,
    extracting a context from said supplied signal dependent on a configuration of prior symbols of said supplied signal,
    generating probability estimates of said supplied signal in response to said supplied signal and said context,
    entropy encoding said supplied signal in response to said supplied signal and said probability estimates to generate an encoded version of said supplied signal,
    interfacing said encoded version to a medium,
    said step of generating probability estimates being
    characterized by
    obtaining representations of accumulated occurrences of individual symbol values of said supplied signal in said context, and
    adaptively adjusting a rate of adaptation in generating said probability estimates in response to said representations of accumulated occurrences in accordance with a prescribed criterion, said step of adaptively adjusting including the steps of obtaining at least a first prescribed characteristic of said representations of accumulated occurrences and in response to said first prescribed characteristic proportionately adjusting said representations of accumulated occurrences when said prescribed characteristic meets said first prescribed criterion.
  22. A method of decoding a compressed data signal representative of an encoded version of an original supplied signal to obtain a reconstructed signal having a plurality of symbol values including the steps of,
    interfacing to a medium for obtaining the compressed data signal,
    extracting a context from a reconstructed signal dependent on a configuration of prior symbols of said reconstructed signal,
    generating probability estimates of said reconstructed signal in response to said reconstructed signal and said context,
    entropy decoding said compressed data signal in response to said compressed data signal and said probability estimates to generate said reconstructed signal version of the original signal,
    said step of generating probability estimates being
    characterized by
    obtaining representations of accumulated occurrences of individual symbol values of said supplied signal in said context, and
    adaptively adjusting a rate of adaptation in generating said probability estimates in response to said representations of accumulated occurrences in accordance with a prescribed criterion, said step of adaptively adjusting including the steps of obtaining at least a first prescribed characteristic of said representations of accumulated occurrences and in response to said prescribed characteristic proportionately adjusting said representations of accumulated occurrences when said prescribed characteristic meets said first prescribed criterion.
  23. An adaptive probability estimator for generating probability estimates of a supplied signal having a plurality of symbol values in a supplied context to be used in entropy encoding/decoding, comprising:
    a source of the supplied signal;
    means for obtaining a representation of a number of occurrences of a symbol value of said supplied signal in said supplied context which has occurred least often; and
    means responsive to said obtained representation for adjusting a rate of adaptation of the adaptive probability estimator in accordance with a prescribed criterion, said means for adjusting including means responsive to said obtained representation for proportionately adjusting said obtained representation when said prescribed criterion is met.
  24. An adaptive encoder for encoding a supplied signal having a plurality of symbol values including,
    a source of the supplied signal,
    means for extracting a context of said supplied signal,
    adaptive probability estimator means supplied with said signal from said source and said context for generating probability estimates of the supplied signal,
    entropy encoder means supplied with said signal from said source and responsive to said probability estimates for generating an encoded version of said supplied signal, and
    means for interfacing said encoded version as an output to a medium,
    said adaptive probability estimator means being characterized by
    means for obtaining a representation of a number of occurrences of a symbol value of said supplied signal in said supplied context which has occurred least often, and
    means responsive to said obtained representation for adjusting a rate of adaptation of the adaptive probability estimator in accordance with a prescribed criterion, said means for adjusting including means responsive to said obtained representation for proportionately adjusting said obtained representation when said prescribed criterion is met.
  25. An adaptive decoder for reconstructing an original signal having a plurality of symbol values from a compressed data signal including,
    means for obtaining the compressed data signal from a medium,
    means for determining a context for the symbol to be reconstructed,
    adaptive probability estimator means supplied with a reconstructed signal and said context for generating probability estimates of the reconstructed signal,
    entropy decoder means supplied with said obtained compressed data signal and responsive to said probability estimates for reconstructing an original signal,
    said adaptive probability estimator means being
    characterized by
    means for obtaining a representation of a number of occurrences of a symbol value of said reconstructed signal in said context which has occurred least often, and
    means responsive to said obtained representation for adjusting a rate of adaptation of the probability estimator in accordance with a prescribed criterion, said means for adjusting including means responsive to said obtained representation for proportionately adjusting said obtained representation when said prescribed criterion is met.
  26. A method of encoding a supplied signal having a plurality of symbol values including the steps of,
    obtaining symbol values of said supplied signal from a signal source,
    extracting a context from said supplied signal dependent on a configuration of prior symbols of said supplied signal,
    generating probability estimates of said supplied signal in response to said supplied signal and said context,
    entropy encoding said symbols of the supplied signal in response to said supplied signal and said probability estimates to generate an encoded version of said supplied signal,
    supplying said encoded version to a medium,
    said step of generating probability estimates being
    characterized by
    obtaining a representation of a number of occurrences of a symbol value of said supplied signal in said context which has occurred least often, and
    adaptively adjusting a rate of adaptation in generating said probability estimates in accordance with a prescribed criterion in response to said obtained representation by proportionately adjusting said obtained representation when said criterion is met.
  27. A method of decoding a compressed data signal representative of an encoded version of an original supplied signal to obtain a reconstructed signal having a plurality of symbol values including the steps of,
    obtaining a compressed data signal from a medium,
    extracting a context from a reconstructed signal dependent on a configuration of prior symbols of said reconstructed signal,
    generating probability estimates of said reconstructed signal in response to said reconstructed signal and said context,
    entropy decoding said obtained compressed data signal in response to said compressed data signal and said probability estimates to generate said reconstructed signal version of the original signal,
    said step of generating probability estimates being
    characterized by
    obtaining a representation of a number of occurrences of a symbol value of said reconstructed signal in said context which has occurred least often, and
    adaptively adjusting a rate of adaptation in generating said probability estimates in accordance with a prescribed criterion in response to said obtained representation by proportionately adjusting said obtained representation when said criterion is met.
Abstract
In entropy, e.g. arithmetic, encoding and decoding, probability estimates are needed of symbols to be encoded and subsequently decoded. More accurate probability estimates are obtained by controllably adjusting the adaptation rate of an adaptive probability estimator. The adaptation rate is optimized by matching it to the actual probability values being estimated. In particular, the adaptation rate is optimized to be proportional to the inverse of the smallest value probability being estimated. Consequently, if the probability values being estimated are not small a "fast" adaption rate is realized and if the probability values being estimated are small a necessarily slower adaptation rate is realized.
Non-Patent References
Referenced By
US 5210536 (May 11, 1993) Data compression/coding method and device for implementing said method
US 5309381 (May 3, 1994) Probability estimation table apparatus
US 5357250 (Oct 18, 1994) Adaptive computation of symbol probabilities in n-ary strings
US 5396228 (Mar 7, 1995) Methods and apparatus for compressing and decompressing paging data
US 5414423 (May 9, 1995) Stabilization of probability estimates by conditioning on prior decisions of a given context
US 5473385 (Dec 5, 1995) Clock correction in a video data decoder using video synchronization signals
US 5533051 (Jul 2, 1996) Method for data compression
US 5543795 (Aug 6, 1996) Hybrid analog-to-digital convertor for low power applications, such as use in an implantable medical device
US 5563595 (Oct 8, 1996) Method and apparatus for compressing data
US 5652878 (Jul 29, 1997) Method and apparatus for compressing data
US 5703907 (Dec 30, 1997) Method for data compression
US 5710562 (Jan 20, 1998) Method and apparatus for compressing arbitrary data
US 5736947 (Apr 7, 1998) Digital information encoding device, digital information decoding device, digital information encoding/decoding device, digital information encoding method, and digital information decoding method
US 5737345 (Apr 7, 1998) Method for arithmetic decoding
US 5781136 (Jul 14, 1998) Digital information encoding device, digital information decoding device, digital information encoding/decoding device, digital information encoding method, and digital information decoding method
US 5818369 (Oct 6, 1998) Rapid entropy coding for data compression or decompression
US 5864308 (Jan 26, 1999) System, coding section, arrangement, coding apparatus, and method
US 5986591 (Nov 16, 1999) Context tree algorithm method and system
US 6025932 (Feb 15, 2000) Digital information encoding apparatus, digital information encoding/decoding apparatus, digital information encoding method, and digital information decoding method
US 6055338 (Apr 25, 2000) Bi-level adaptive coding using a dual port memory and a context comparator
US 6058216 (May 2, 2000) Apparatus for encoding image data
US 6150966 (Nov 21, 2000) System, coding section, arrangement, coding apparatus, and method
US 6259388 (Jul 10, 2001) Multiplication-free arithmetic coding
US 6411231 (Jun 25, 2002) Encoding, decoding, and probability estimation method
US 6580833 (Jun 17, 2003) Apparatus and method for entropy coding
US 6714145 (Mar 30, 2004) Method and apparatus for integer-based encoding and decoding of bits
US 7161507 (Jan 9, 2007) Fast, practically optimal entropy coding
US 7233622 (Jun 19, 2007) Reduced complexity efficient binarization method and/or circuit for motion vector residuals
US 7265691 (Sep 4, 2007) Modeling for enumerative encoding
US 7319417 (Jan 15, 2008) Compression using multiple Markov chain modeling
US 7664267 (Feb 16, 2010) Bit based arithmetic coding using variable size key cipher
US 7688895 (Mar 30, 2010) Method and/or circuit for binary arithmetic decoding decisions before termination
US 7710297 (May 4, 2010) Method and apparatus for entropy coding and decoding
US 7793099 (Sep 7, 2010) Method and system for encryption of file characteristics of .ZIP files
US 7821430 (Oct 26, 2010) Arithmetic decoding apparatus
US 7844579 (Nov 30, 2010) System and method for manipulating and managing computer archive files
US 7890465 (Feb 15, 2011) Systems and methods for manipulating and managing computer archive files
US 7895434 (Feb 22, 2011) Method and system for multiple asymmetric encryption of .ZIP files
US 8090942 (Jan 3, 2012) Method and system for asymmetrically encrypting .ZIP files
US 8176155 (May 8, 2012) Remote network management system
US 8225108 (Jul 17, 2012) Method and system for mixed symmetric and asymmetric encryption of .ZIP files
US 8230482 (Jul 24, 2012) System and method for manipulating and managing computer archive files
Examiners
Benjamin R. Fuller
Nancy Le
Inventors
Donald L. Duttweiler, Rumson NJ
Assignees
AT&T Bell Laboratories, Murray Hill NJ
Filing Date
Jun 1, 1989
Publication Date
Jun 18, 1991
Predicted Expiry Date
Calculated by Patent Lens and does not include factors such as terminal disclaimers etc.
Jun 1, 2009
Agents
Thomas Stafford
Application Number
07359559
IPC
H03M 700
US Classification
341/107
341/51
341/76
358/135
375/27
Field Of Search
341/107
341/51
341/76
358/135
375/27
Patent References
US 4122440 (Oct, 1978) Langdon, Jr. et al. 341/51
US 4475227 (Oct, 1984) Belfield 375/27
US 4592070 (May, 1986) Chow et al. 375/27
US 4633490 (Dec, 1986) Goertzel 375/122
US 4689606 (Aug, 1987) Sato 341/107
US 4725885 (Feb, 1988) Gonzales 358/135
US 4745474 (May, 1988) Schiff 375/27
US 4749983 (Jun, 1988) Langdon, Jr. 341/51
US 4821290 (Apr, 1989) Hingorani et al. 341/76
US 4933883 (Jun, 1990) Pennebaker et al. 341/107
US 4935882 (Jun, 1990) Pennebaker et al. 364/554