Near-Optimality of the Minimum Average Redundancy Code for Almost All Monotone Sources

この論文にアクセスする

この論文をさがす

著者

抄録

Consider the source coding problem of finding the optimal code, in the sense of average redundancy, for the class of <i>monotone sources with n symbols</i>. The solution of this problem, known as the M code, is the Huffman code for the average distribution of the monotone sources. In this paper, we evaluate the average redundancy of the M code (on the class of monotone sources), and compare it with that of the Huffman code. It is demonstrated that for large <i>n</i>, although the M code is a fixed code (i.e., the codewords are independent of the symbol probabilities) for all monotone sources, its average redundancy is very close to that of the Huffman code. Moreover, it is shown that when <i>n</i> is large, the M code is a near-optimal code not only in the sense of average redundancy, but also the redundancy of almost all monotone sources. In particular, the redundancy of the M code converges in probability to its average value (≅0.029). As a result, the maximum redundancy of the M code, which can be as large as log <i>n</i> - log ln <i>n</i>, <i>rarely</i> occurs.

収録刊行物

  • IEICE transactions on fundamentals of electronics, communications and computer sciences

    IEICE transactions on fundamentals of electronics, communications and computer sciences 94(11), 2092-2096, 2011-11-01

    一般社団法人 電子情報通信学会

参考文献:  7件中 1-7件 を表示

各種コード

  • NII論文ID(NAID)
    10030191446
  • NII書誌ID(NCID)
    AA10826239
  • 本文言語コード
    ENG
  • 資料種別
    ART
  • ISSN
    09168508
  • データ提供元
    CJP書誌  J-STAGE 
ページトップへ