Abstract
It is possible to improve upon Tunstall coding using a collection of multiple parse trees. The best such results so far are Iwata and Yamamoto's maximum cost AIVF codes. The most efficient algorithm for designing such codes is an iterative one that could run in exponential time. In this paper, we show that this problem fits into the framework of a newly developed technique that uses linear programming with the Ellipsoid method to solve the minimum cost Markov chain problem. This permits constructing maximum cost AIVF codes in (weakly) polynomial time.
| Original language | English |
|---|---|
| Title of host publication | 2024 IEEE International Symposium on Information Theory, ISIT 2024 - Proceedings |
| Publisher | Institute of Electrical and Electronics Engineers Inc. |
| Pages | 67-72 |
| Number of pages | 6 |
| ISBN (Electronic) | 9798350382846 |
| DOIs | |
| Publication status | Published - 2024 |
| Externally published | Yes |
| Event | 2024 IEEE International Symposium on Information Theory, ISIT 2024 - Athens, Greece Duration: 7 Jul 2024 → 12 Jul 2024 |
Publication series
| Name | IEEE International Symposium on Information Theory - Proceedings |
|---|---|
| ISSN (Print) | 2157-8095 |
Conference
| Conference | 2024 IEEE International Symposium on Information Theory, ISIT 2024 |
|---|---|
| Country/Territory | Greece |
| City | Athens |
| Period | 7/07/24 → 12/07/24 |
Bibliographical note
Publisher Copyright:© 2024 IEEE.