Première Page

Titre
Entropy encoder/decoder including a context extractor
Revendications
  1. An encoder for encoding a supplied signal having a plurality of symbol values including,
    means for extracting a context dependent on a configuration of prior symbols of said supplied signal,
    probability estimator means being responsive to said supplied signal and said context for generating probability estimates of said supplied signal,
    entropy encoder means being responsive to said supplied signal and said probability estimates for generating an encoded version of said supplied signal,
    said means for extracting a context being
    characterized by
    said prior symbols being at prescribed lag intervals relative to a current symbol being encoded, and
    means responsive to said supplied signal for adaptively adjusting said configuration.
  2. An encoder as defined in claim 1 wherein said means for adaptively adjusting includes means for enabling adjustment of said configuration only at times when prescribed criteria based on correlation between signal values at said lag intervals are met.
  3. An encoder as defined in claim 1 further including means for interfacing said entropy encoder to a transmission media.
  4. An encoder as defined in claim 1 wherein said configuration includes a predetermined portion comprised of at least one of said lag intervals and an adjustable portion comprised of at least one floating lag interval in response to said supplied signal.
  5. An encoder as defined in claim 1 wherein said means for adaptively adjusting includes means for selecting said at least one floating lag interval from a predetermined set of candidate lag intervals.
  6. An encoder as defined in claim 5 wherein said means for selecting includes means for obtaining a measure of predictive value of each prior symbol at said lag intervals in said predetermined set of candidate lag intervals and means for selecting from said set of candidate lag intervals at least one of said lag intervals referencing a symbol having the greatest predictive value to be included as said floating predictor lag interval in said configuration.
  7. An encoder as defined in claim 6 wherein said means for obtaining a measure of predictive value includes means for obtaining a measure of correlation at each of said candidate lag intervals and wherein said means for selecting includes means for determining which at least one of said lag intervals in said set is to be included in said configuration based on said correlations.
  8. An encoder as defined in claim 7 wherein said means for determining identifies an at least one lag interval of said set of candidate lag intervals having the maximum correlation and further including means for incorporating said identified at least one lag interval into said configuration.
  9. An encoder as defined in claim 6 wherein said means for obtaining a measure of predictive value includes means for counting polarity coincidences between said current symbol and symbols at said candidate lag intervals and wherein said means for selecting is responsive to counts of said polarity coincidences to select as said at least on lag interval to be included in said configuration at least one of said candidate lag intervals having the maximum count of said polarity coincidences.
  10. A decoder for reconstructing an original signal having a plurality of symbol values from a compressed data signal including,
    means for extracting a context dependent on a configuration of prior symbols of a reconstructed signal,
    probability estimator means being responsive to said reconstructed signal and said context for generating probability estimates of said reconstructed signal,
    entropy decoder means being responsive to said compressed data signal and said probability estimates for generating a reconstructed version of the original signal,
    said means for extracting a context being,
    characterized by
    said prior symbols being at prescribed lag intervals relative to a current symbol being decoded, and
    means responsive to said reconstructed signal for adaptively adjusting said configuration.
  11. A decoder as defined in claim 10 wherein said means for adaptively adjusting includes means for enabling adjustment of said configuration only at time when prescribed criteria based on correlation between signal values at said lag intervals are met.
  12. A decoder as defined in claim 10 further including means for interfacing said entropy decoder means to a transmission media.
  13. A decoder as defined in claim 1 wherein said configuration includes a predetermined portion comprised of at least one of said lag intervals and an adjustable portion comprised of at least one floating lag interval determined in response to said supplied signal.
  14. A decoder as defined in claim 13 wherein said means for adaptively adjusting includes means for selecting said at least one floating lag interval from a predetermined set of candidate lag intervals.
  15. A decoder as defined in claim 14 wherein said means for selecting includes means for obtaining a measure of predictive value of each prior symbol at said lag intervals in said predetermined set of cadidate lag intervals and means for selecting from said set of candidate lag intervals at least one of said lag intervals referencing a symbol having the greatest predictive value to be included as said floating predictor lag interval in said configuration.
  16. A decoder as defined in claim 15 wherein said means for obtaining a measure of predictive value obtains a measure of correlation at each of said candidate lag intervals and wherein said means for selecting includes means for determining which at least one of said lag intervals in said set is to be included in said configuration based on said correlations.
  17. A decoder as defined in claim 16 wherein said means for determining identifies an at least one lag interval of said set of candidate lag intervals having the maximum correlation and further including means for incorporating said identified at least one lag interval into said configuration.
  18. A decoder as defined in claim 15 wherein said means for obtaining a measure of predictive value includes means for counting polarity coincidences between said current symbol and symbols at said candidate lag intervals and wherein said means for selecting is responsive to counts of said polarity coincidences to select as said at least one lag interval to be included in said configuration at least one of said candidate lag intervals having the maximum count.
  19. 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,
    said step of extracting a context being,
    characterized by
    said prior symbols being at prescribed lag intervals relative to said current symbol being encoded, and
    adaptively adjusting said configuration in response to said supplied signal.
  20. 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,
    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 extracting a context being,
    characterized by
    said prior symbols being at prescribed lag intervals relative to said current symbol being decoded, and
    adaptively adjusting said configuration in response to said supplied signal.
Abrégé
In entropy, e.g., arithmetic or adaptive Huffman, encoding/decoding a context based on prior symbols is needed to provide accurate predictions of symbols to be encoded/decoded. Encoding/decoding efficiency is improved by employing an adaptive context extractor. The adaptive context extractor automatically adjusts the configuration of the lag intervals used to define the context. This is realized by adaptively incorporating into the context configuration at least one lag interval found to have a "good" predictive value relative to the particular symbol stream being encoded/decoded. The context configuration adjustment is such that the at least one found lag interval is exchanged with the lag interval currently in an at least one so-called floating predictor position.
Références non-brevet
Citée par
US 5142283 (25 août 1992) Arithmetic compression coding using interpolation for ambiguous symbols
US 5210536 (11 mai 1993) Data compression/coding method and device for implementing said method
US 5298896 (29 mars 1994) Method and system for high order conditional entropy coding
US 5357250 (18 oct. 1994) Adaptive computation of symbol probabilities in n-ary strings
US 5396228 (7 mars 1995) Methods and apparatus for compressing and decompressing paging data
US 5406282 (11 avr. 1995) Data coding and decoding with improved efficiency
US 5414423 (9 mai 1995) Stabilization of probability estimates by conditioning on prior decisions of a given context
US 5543795 (6 août 1996) Hybrid analog-to-digital convertor for low power applications, such as use in an implantable medical device
US 5550540 (27 août 1996) Distributed coding and prediction by use of contexts
US 5563595 (8 oct. 1996) Method and apparatus for compressing data
US 5577132 (19 nov. 1996) Image coding/decoding device
US 5652581 (29 juil. 1997) Distributed coding and prediction by use of contexts
US 5652878 (29 juil. 1997) Method and apparatus for compressing data
US 5818369 (6 oct. 1998) Rapid entropy coding for data compression or decompression
US 5864308 (26 janv. 1999) System, coding section, arrangement, coding apparatus, and method
US 5903676 (11 mai 1999) Context-based, adaptive, lossless image codec
US 5936559 (10 août 1999) Method for optimizing data compression and throughput
US 5986591 (16 nov. 1999) Context tree algorithm method and system
US 6055338 (25 avr. 2000) Bi-level adaptive coding using a dual port memory and a context comparator
US 6058216 (2 mai 2000) Apparatus for encoding image data
US 6150966 (21 nov. 2000) System, coding section, arrangement, coding apparatus, and method
US 6269338 (31 juil. 2001) Data compression and expansion of an audio signal
US 6272256 (7 août 2001) Fast compression of periodic halftoned bitonal images
US 6275176 (14 août 2001) Arithmetic encoding/decoding of a digital information signal
US 6397205 (28 mai 2002) Document categorization and evaluation via cross-entrophy
US 6449393 (10 sept. 2002) Method and apparatus for data compression based on modeling schemes
US 6580833 (17 juin 2003) Apparatus and method for entropy coding
US 6625321 (23 sept. 2003) Embedded image coder with rate-distortion optimization
US 6714145 (30 mars 2004) Method and apparatus for integer-based encoding and decoding of bits
US 6757436 (29 juin 2004) Methods and apparatus for data compression based on modeling schemes
US 6757440 (29 juin 2004) Methods and apparatus for data compression
US 6778965 (17 août 2004) Data compression and expansion of an audio signal
US 6944347 (13 sept. 2005) Image compression and restoring method for binary images
US 7058231 (6 juin 2006) Methods and apparatus for data compression with a hybrid context
US 7076109 (11 juil. 2006) System and method of automatically determining the dominant periodicity in sequential binary data
US 7095343 (22 août 2006) code compression algorithms and architectures for embedded systems
US 7161507 (9 janv. 2007) Fast, practically optimal entropy coding
US 7225136 (29 mai 2007) Data compression and expansion of an audio signal
US 7265691 (4 sept. 2007) Modeling for enumerative encoding
US 7319417 (15 janv. 2008) Compression using multiple Markov chain modeling
US 7460721 (2 déc. 2008) Methods and apparatus for data compression with a hybrid context
Examinateurs
William M. Shoop, Jr.
Sharon D. Logan
Inventeurs
Christodoulos Chamzas, West Long Branch NJ
Donald L. Duttweiler, Rumson NJ
Ayant-droit
AT&T Bell Laboratories, Murray Hill NJ
Date d’enregistrement
28 juil. 1989
Date de publication
11 juin 1991
Date d'expiration prévue
28 juil. 2009
Mandataires
Thomas Stafford
Numéro de dépôt
07386537
IPC
H03M 734
Classification des États-Unis
341/107
341/51
Domaine de recherche
341/107
341/50
341/51
358/426
358/430
Références brevet
US 4494108 (janv., 1985) Langdon, Jr. et al. 341/51
US 4633490 (déc., 1986) Goertzel et al. 375/122
US 4881075 (nov., 1989) Weng 341/51 X
US 4891643 (janv., 1990) Mitchell et al. 341/51 X