| Paper ID | D5-S1-T2.1 |
| Paper Title |
Efficient Codebook Constructions of AIVF Codes |
| Authors |
Yulong You, Sian-Jheng Lin, University of Science and Technology of China~(USTC), China |
| Session |
D5-S1-T2: Variable-Length Codes |
| Chaired Session: |
Friday, 16 July, 22:00 - 22:20 |
| Engagement Session: |
Friday, 16 July, 22:20 - 22:40 |
| Abstract |
The almost instantaneous variable-to-fixed (AIVF) code is a class of non-prefix codes that parses data sequences into some fixed-length codewords. Recently, the dictionary construction of optimal AIVF code is proposed via a dynamic programming algorithm. However, the algorithm has time complexity O(AM^2) in both single- and multiple-tree modes, where A denotes the alphabet size, and M denotes the dictionary size. In this paper, we present a greedy-like algorithm to construct the codebook. In particular, the proposed algorithm has time complexity O(M) in single-tree mode and O(AM) in multiple-tree mode.
|
