Optimal entropy-constrained scalar quantization of a uniform source

被引:48
作者
György, A
Linder, T
机构
[1] Queens Univ, Dept Math & Stat, Kingston, ON K7L 3N6, Canada
[2] Tech Univ Budapest, Dept Comp Sci & Informat Theory, Budapest, Hungary
关键词
constrained optimization; difference distortion measures; entropy coding; scalar quantization; uniform source;
D O I
10.1109/18.887885
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Optimal scalar quantization subject to an entropy constraint is studied for a wide class of difference distortion measures including rth-power distortions with r > 0. It is proved that if the source is uniformly distributed over an interval, then for any entropy constraint R (in nats), an optimal quantizer has N = [e(R)] interval cells such that N - 1 cells have equal length d and orle cell has length c less than or equal to d. The cell lengths are uniquely determined by the requirement that the entropy constraint is satisfied with equality. Based on this result, a parametric representation of the minimum achievable distortion D-h(R) as a function of the entropy constraint R is obtained for a uniform source. The D-h(R) curve turns out to be nonconvex in general. Moreover, for the squared-error distortion it is shown that D-h(R) is a piecewise-concave function, and that a scaler quantizer achieving the loser convex hull of D-h(R) exists only at rates R = log N, where N is a positive integer.
引用
收藏
页码:2704 / 2711
页数:8
相关论文
共 14 条
[1]   OPTIMUM QUANTIZERS AND PERMUTATION CODES [J].
BERGER, T .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1972, 18 (06) :759-+
[2]   ENTROPY-CONSTRAINED VECTOR QUANTIZATION [J].
CHOU, PA ;
LOOKABAUGH, T ;
GRAY, RM .
IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 1989, 37 (01) :31-42
[3]   When optimal entropy-constrained quantizers have only a finite number of codewords [J].
Chou, PA ;
Betts, BJ .
1998 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY - PROCEEDINGS, 1998, :97-97
[4]   OPTIMUM QUANTIZER PERFORMANCE FOR A CLASS OF NON-GAUSSIAN MEMORYLESS SOURCES [J].
FARVARDIN, N ;
MODESTINO, JW .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1984, 30 (03) :485-497
[5]   ASYMPTOTICALLY EFFICIENT QUANTIZING [J].
GISH, H ;
PIERCE, JN .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1968, 14 (05) :676-+
[6]  
Gray R. M., 1990, Source Coding Theory
[7]  
GYORGY A, 2000, UNPUB STRUCTURE OPTI
[8]  
Hardy G.H., 1959, INEQUALITIES
[9]   NEW RESULTS ON OPTIMAL ENTROPY-CONSTRAINED QUANTIZATION [J].
KIEFFER, JC ;
JAHNS, TM ;
OBULJEN, VA .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1988, 34 (05) :1250-1258
[10]  
Luenberger D.G., 1984, LINEAR NONLINEAR PRO