Loading...

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 16921695 
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. Ln (X) of an optimal prefix code for the extended source Xn converges to the source entropy as n approaches infinity. However, the sequence Ln (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 Ln (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 Lkn (X) < Ln (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 Lkn (X) <= Ln (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 
Size  Format  
index.html   0Kb  HTML  445  View/Open 

在NTHUR中所有的資料項目都受到原著作權保護，僅提供學術研究及教育使用，敬請尊重著作權人之權益。若須利用於商業或營利，請先取得著作權人授權。
若發現本網站收錄之內容有侵害著作權人權益之情事，請權利人通知本網站管理者(smluo@lib.nthu.edu.tw)，管理者將立即採取移除該內容等補救措施。


與系統管理員聯絡

