The 2018 International Symposium on Information Theory and Its Applications (ISITA2018)


Session Number:We-AM-1-3



A Consideration on Classification of Extended Binary Memoryless Sources Under Which Distinct Huffman Codes Are Constructed

Nozomi Miya,  Takahiro Yoshida,  Hajime Jinushi,  


Publication Date:2018/10/18

Online ISSN:2188-5079


PDF download


Distinct Huffman codes, i.e., distinct codeword sets obtained by Huffman’s algorithm are constructed for the n-th degree extended binary memoryless sources whose alphabet is {0, 1}n if (n, p) varies, where p ? 1/2 denotes the probability that symbol 0 occurs. For a fixed n ? 2, sufficient conditions with respect to p constructing a part of all distinct Huffman codes have been shown. Necessary conditions with respect to p, constructing such Huffman codes have also been shown. However, sufficient conditions corresponding to some but not all such distinct Huffman codes are equivalent to necessary conditions. In this work, we tighten necessary conditions and discuss whether or not sufficient conditions are equivalent to necessary conditions corresponding to other distinct Huffman codes. In addition, we present examples in which sufficient conditions are or are not equivalent to necessary conditions.