2008 Research Summary

Universal Quadratic Lower Bounds on Error Exponents (UL-BEE)

View Current Project Information

Cheng Chang and Anant Sahai

We consider the problem of block-size selection to achieve a desired probability of error for universal source coding with and without decoder side information. Previously, this question was studied in [1] for rates in the vicinity of entropy for known distributions using central-limit-theorem techniques. We are interested in all rates for unknown distributions and use error-exponent techniques. By adapting a technique of Gallager from the exercises of [2], we derive a universal lower bound to the source-coding error exponent that depends only on the alphabet size and is quadratic in the gap to entropy. Then the block-size selection problem can be solved as a natural. These results all agree with the previous central limit result in order. This shows that the large deviation principal can be used in the vicinity of a central limit if used properly.

[1]

D. Baron, M. A. Khojastepour, and R. G. Baraniuk, "Redundancy Rates of Slepian-Wolf Coding," 42nd Allerton Conference, 2004.

[2]

R. G. Gallager, Information Theory and Reliable Communication, John Wiley, New York, NY, 1971.