Optimal and almost optimal variable-to-fixed length codes: renewal theory and divide-and-conquer recurrences
Wednesday, February 23, 2011
The purpose of this talk is to discuss and analyze two variable-to-fixed coding schemes, the Tunstall code and the Boncelet code, in particular we provide asymptotics for the redundancy and central limit theorems for the phrase lengths. Both coding algorithms can be analyzed with the help of proper divide-and-conquer recurrences, however, they are of slightly different nature and their (asymptotic) solution require different mathematical techniques. Whereas we can apply renewal theory for the Tunstall code we need a subtle analysis with Dirichlet series and Mellin-Perron techniques to handle the Boncelet code.
This is joint work withWojciech Szpankowski.
Professor, TU Wien