Back to Search Start Over

Worst-case Redundancy of Optimal Binary AIFV Codes and Their Extended Codes.

Authors :
Hu, Weihua
Yamamoto, Hirosuke
Honda, Junya
Source :
IEEE Transactions on Information Theory. Aug2017, Vol. 63 Issue 8, p5074-5086. 13p.
Publication Year :
2017

Abstract

Binary almost instantaneous fixed-to-variable length (AIFV) codes are lossless codes that generalize the class of instantaneous fixed-to-variable length codes. The code uses two code trees and assigns source symbols to incomplete internal nodes as well as to leaves. AIFV codes are empirically shown to attain better compression ratio than Huffman codes. Nevertheless, an upper bound on the redundancy of optimal binary AIFV codes is only known to be 1, which is the same as the bound of Huffman codes. In this paper, the upper bound is improved to 1/2, which is shown to coincide with the worst-case redundancy of the codes. Along with this, the worst-case redundancy is derived for sources with p\max \geq 1 /2, where p\max is the probability of the most likely source symbol. In addition, we propose an extension of binary AIFV codes, which use $m$ code trees and allow at most $m$ -bit decoding delay. We show that the worst-case redundancy of the extended binary AIFV codes is $1/m$ for $m \leq 4$ . [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
00189448
Volume :
63
Issue :
8
Database :
Academic Search Index
Journal :
IEEE Transactions on Information Theory
Publication Type :
Academic Journal
Accession number :
124147912
Full Text :
https://doi.org/10.1109/TIT.2017.2694017