Variable-rate trellis source encoding

作     者：Yang, EH Zhang, Z 

作者机构：Univ Waterloo Dept Elect & Comp Engn Waterloo ON N2L 3G1 Canada Univ So Calif Dept Elect Engn Syst Inst Commun Sci Los Angeles CA 90089 USA 

出 版 物：《IEEE TRANSACTIONS ON INFORMATION THEORY》 (IEEE Trans. Inf. Theory)

年 卷 期：1999年第45卷第2期

页      面：586-608页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Sciences Foundation, (NCR 9508282) Natural Sciences and Engineering Research Council of Canada, NSERC, (RGPIN203035-98) University of Waterloo 

主　　题：arithmetic coding data compression quantization rate-distortion function stationary and ergodic sources variable-rate trellis source encoding 

摘      要：The fixed slope lossy algorithm derived from the kth-order adaptive arithmetic codeword length function is extended to the case of finite-state decoders or trellis-structured decoders. It is shown that when this algorithm is used to encode a stationary, ergodic source with a continuous alphabet, the Lagrangian performance (i.e., the resulting compression rate plus lambda times the resulting distortion) converges with probability one to a quantity computable as the infimum of an information-theoretic functional over a set of auxiliary random variables and reproduction levels, where lambda 0 and -lambda is designated to be the slope of the rate-distortion function R(D) of the source at some D;the quantity is close to R(D) + lambda D when the order k used in the arithmetic coding or the number of states in the decoders is large enough, An alternating minimization algorithm for computing the quantity is presented;this algorithm is based on a training sequence and in turn gives rise to a design algorithm for variable-rate trellis source codes, The resulting variable-rate trellis source codes are very efficient in low-rate regions (below 0.8 bits/sample), With k = 8, the mean-squared error encoding performance at the rate 1/2 bits/sample for memoryless Gaussian sources is comparable to that afforded by trellis-coded quantizers;with k = 8 and the number of states in the decoder = 32, the mean-squared error encoding performance at the rate 1/2 bits/sample for memoryless Laplacian sources is about 1 dB better than that afforded by the trellis-coded quantizers with 256 states, With k = 8 and the number of states in the decoder = 256, the mean-squared error encoding performance at the rates of a fraction of 1 bit/sample for highly dependent Gauss-Markov sources with correlation coefficient 0.9 is within about 0.6 dB of the distortion-rate function. Note that at such low rates, predictive coders usually perform poorly.