Abstract

A method and apparatus for performing entropy coding and decoding of a sequence of coded symbols representative of, for example, a speech, audio or video signal, in which variable-size vectors are coded and decoded based on radix arithmetic. The encoding technique uses a first radix and the numerical values of individual symbols to be coded, in order to determine the length of a first subsequence of symbols, which is then coded with use of a single (a first) combined symbol, and uses a second radix and the numerical values of other individual symbols to be coded, in order to determine the length of a second subsequence of symbols, which is then also coded with a single (a second) combined symbol, wherein the length of the first and second subsequences of symbols are also based on the size of the set from which the combined symbols are selected. The number of symbols in the first subsequence and the second subsequence are unequal--that is, the vectors (i.e., subsequences) which are combined for coding have a variable size. The first radix and the second radix may be equal and fixed to a predetermined value, or they may each be determined based on the corresponding subsequence of symbols to be coded. Correspondingly, the decoding technique of the present invention determines from the bit stream the number of symbols which have been coded with use of a single combined symbol (i.e., the length of a coded subsequence), and based on that number, on the combined symbol itself, and on a given radix (which may be fixed or may also be determined from the bit stream), determines the values of the individual symbols which were coded together as the combined symbol.

Other References

• D. Huffman, "A Method For The Construction Of Minimum Redundancy Codes," Proc. IRE 40, pp. 1098-01191, 1952
• G. V. Cormack, et al., "Algorithms For Adaptive Huffman Codes," Inf. Proc. Letters, 18, Mar., 1984, pp. 159-165
• J. Rissanen, et al., "Arithmetic Coding," IBM J. Res. 23, 2 (Mar.), pp. 149-162, 1979
• A. Moffat, et al., "Arithmetic Coding Revisited," ACM Trans., On Information Systems, vol. 16, No. 3, Jul. 1998, pp. 256-294
• S. A. Savari, et al., "Generalized Tunstall Codes For Sources With Memory," IEEE Trans. IT, vol. 43, No. 2, pp. 658-667, Mar. 1997
• M. A. Gerzon, et al., "The MLP Lossless Compression System," AES 17^th, Int. Conf. on High Qual. Audio Coding, pp. 1-15, Sep. 1999
• P. Craven, et al., "Lossless Coding For Audio Discs," J. Audio Eng. Soc., vol. 44, No. 9 pp. 706-720, Sep. 1996
• P.A. Chou, et al., "Entropy-Constrained Vector Quantization," IEEE Trans. Acoust, Sp. and Sig. Proc. 37(1), pp. 31-42, Jan. 1989
• J. Ziv, et al., "A Universal Algorithm For Sequential Data Compression," IEEE Trans. Inf. Theor., vol. IT-23, No. 3, pp. 337-343, 1997
• J. P. Pincen, et al., "Subband/Transform Coding Using Filter Bank Designs Based On Time Domain Aliasing Cancellation," IACSSP '87, pp. 2161-2167, 1987
• N. Iwakami, et al., High-Quality Audio Coding At Less Than 64 Kbps Using Transform-Domain Wighted Interleave Vector Quantization (Twin VVQ), ICASSP '95, pp. 3095-3098, 1995
• S. R. Quackenbush, et al., "Noiseless Coding Of Quantized Spectral Components In MPEG-2 Advanced Audio Coding," IEEE Workshop On Applications Of Signal Processing To Audio And Acoustics, WASPAA '97, Session 3. Paper No. 3, 1997
• S. Deligne, "Language Modeling By Variable Length Sequences: Theoretical Formulation And Evaluation Of Multigrams," ICASSP '95 pp. 169-172, 1995
• F. Bimbot, et al., "Variable-Length Sequence Modeling: Multi-Grams", IEEE Signal Processing Letters, vol. 2, No. 6, Jun. 1995
• S. Roucus, et al., "Stochastic Segment Modelling Using The Estimate-Maximize Algorithm," ICASSP '88 pp. 127-130, 199