English  |  正體中文  |  简体中文  |  Items with full text/Total items : 54367/62174 (87%)
Visitors : 14272197      Online Users : 111
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTHU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    National Tsing Hua University Institutional Repository > 電機資訊學院 > 電機工程學系 > 期刊論文 >  On the expected codeword length per symbol of optimal prefix codes for extended sources

    Please use this identifier to cite or link to this item: http://nthur.lib.nthu.edu.tw/dspace/handle/987654321/71333

    Title: On the expected codeword length per symbol of optimal prefix codes for extended sources
    Authors: Cheng J
    教師: 鄭傑
    Date: 2009
    Publisher: Institute of Electrical and Electronics Engineers (IEEE)
    Relation: IEEE TRANSACTIONS ON INFORMATION THEORY, Institute of Electrical and Electronics Engineers, Volume 55, Issue 4, APR 2009, Pages 1692-1695
    Keywords: Extended sources
    Huffman codes
    minimum codeword length
    optimal codes
    prefix codes
    Abstract: Given a discrete memoryless source X, it is well known that the expected codeword length per symbol. L-n (X) of an optimal prefix code for the extended source X-n converges to the source entropy as n approaches infinity. However, the sequence L-n (X) need not be monotonic in n, which implies that the coding efficiency cannot be increased by simply encoding a larger block of source symbols (unless the block length is appropriately chosen). As the encoding and decoding complexity increases exponentially with the block length, from a practical perspective it is useful to know when an increase in the block length guarantees a decrease in the expected codeword length per symbol. While this paper does not provide a complete answer to that question, we give some properties of L-n (X) and obtain for each n >= 1 and nondyadic p(1)(n) (p(1) is the probability of the most likely source symbol) an integer k* for which L-kn (X) < L-n (X) for all k >= k*, implying that the coding efficiency of encoding blocks of length k(n) is higher than that of encoding blocks of length it for all k >= k*. This question is simpler in part because L-kn (X) <= L-n (X) is guaranteed for all it >= 1 and k >= 1, but our results distinguish scenarios where increasing the multiplicative factor guarantees strict improvement. These results extend and generalize those by Montgomery and Kumar.
    Relation Link: http://www.ieee.org/
    URI: http://nthur.lib.nthu.edu.tw/dspace/handle/987654321/71333
    Appears in Collections:[電機工程學系] 期刊論文

    Files in This Item:

    File Description SizeFormat


    SFX Query


    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback