《L5-Source Coding(2).docx》由会员分享，可在线阅读，更多相关《L5-Source Coding(2).docx（16页珍藏版）》请在三一文库上搜索。
1、Fundamentals ofInformation TheoryLecture 5 Huffman Code, Huffman vs. Shannon,Shannon Competitive OptimalityCovers book: p9294, p96101,p107110, p8990Dr. Wu SThe Properties of a Particular Optimal Codepage 2Page 2Huffman Code with Examplea0.250.2500.2500.5501.0b0.250.250.450.451c0.200.211d0.150.30.3e0
2、.151page 3Page 3More ExamplesConsider a ternary code for the same random variable.a0.250.2501.01b0.250.2502c0.20.51d0.152e0.15page 4Page 4Huffman Code is Optimal Prefix Codepage 5Page 5Huffman Optimality Proofpage 6Page 6Huffman Optimality Proof (contd)page 7Page 7Most Efficient “Yes-No” Questionspa
3、ge 8Page 8Shannon Code vs. Huffman CodeFor individual symbols,we want to compare thecompetitive optimality.page 9Page 9Shannon Competitive Optimality (in General)By Kraft Inequalitypage 10Page 10Shannon Competitive Optimality (Dyadic)Since Shannon isoptimal nowRival code cannot be shorter than Shann
4、on more than half the time.page 11Page 11Shannon Competitive Optimality (Dyadic)abpage 12Page 12Shannon Competitive Optimality (Non-dyadic)Homeworkprove thiscorollary.Thomas M. Cover. “On the optimality of Huffman codes”. IEEE Trans. Information Theory. Vol. 37, No. 1, 1991:172174page 13Page 13Shannon Code with Wrong DistributionProof of this lower limit is similarpage 14Page 14Summarypage 15Page 15