🚀 go-pugleaf

DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

THEORY SEMINAR

                    -Wednesday, Oct. 7, 1992

Xiaolin  Wu, Department of Computer Science, University
of   Western   Ontario   will  speak  on  "Optimal  Bit
Allocation".

TIME:                 1:30-2:30 p.m.

ROOM:                 DC 1304

ABSTRACT

We  consider a fundamental problem in data compression:
how  to  encod random variables X , 1 <= i <= M, (X 's can be
                                 i           i
scalars  and/or  vectors),  with  B  bits  for  minimum
distortion.    For  each  X ,  we  design  its  optimal
                           i
quantizer  Q for different bit rates, and allocate B
            i
bits  to M quantizers Q , 1 <= i <= M, in such a way that the
                       i
total  distortion of these quantizers is minimized.  We
                    2
will  give  an  O(MB )  algorithm  to  compute  optimal
integer-constrained   bit  allocation,  and  a  pseudo-
polynomial  algorithm  for  optimal  bit  allocation in
general  setting.   We will also discuss how greedy bit
allocation   and   branch-and-bound  technique  can  be
combined  to  reduce  the  expected  time complexity of
optimal   bit   allocation   for  significantly  biased
distributions   of  X ,  which  is  a  common  case  in
                     i
practice.