Lecture 7: Source Coding And Kraft Inequality
Lecture 7: Source Coding and Kraft Inequality Codes Kraft inequality and consequencesDr. Yao Xie, ECE587, Information Theory, Duke University
Horse Racing!"# "%"&'()%*& ,%Dr. Yao Xie, ECE587, Information Theory, Duke University1
pi1/21/41/81/161/641/641/641/64EliCode 10000010100111001011101113H(X) Code 201011011101111001111011111101111112pi log pi 2bitsHow to find the best code?Dr. Yao Xie, ECE587, Information Theory, Duke University2
Codes Source code C for a random variable X isC(x) : X D D : set of finite-length strings of symbol from D-ary alphabet D Code length: l(x) Example: C(red) 00, C(blue) 11, X {red, blue}, D {0, 1}Dr. Yao Xie, ECE587, Information Theory, Duke University3
Morse’s code (1836) A code for English alphabet of four symbols Developed for electric telegraph system D {dot, dash, letter space, word space} Short sequences represent frequent letters Long sequences represent infrequent letterDr. Yao Xie, ECE587, Information Theory, Duke University4
Dr. Yao Xie, ECE587, Information Theory, Duke University5
Source coding applications Magnetic recording: cassette, hardrive, USB. Speech compression Compact disk (CD) Image compression: JPEGStill an active area of research: Solid state hard drive Sensor network: distributed source codingDr. Yao Xie, ECE587, Information Theory, Duke University6
What defines a good code Non-singular:x ̸ x′ C(x) ̸ C(x′) non-singular enough to describe a single RV X When we send sequences of value of X, without “comma” can we stilluniquely decode Uniquely decodable if extension of the code is nonsingularC(x1)C(x2) · · · C(xn)Dr. Yao Xie, ECE587, Information Theory, Duke University7
100110UniquelydecoablePrefix100011110010110111 Uniquely decodable if only one possible source string producing it However, we have to look at entire string to determine Prefix code (instantaneous code): no codeword is a prefix of any othercodeDr. Yao Xie, ECE587, Information Theory, Duke University8
antaneouscodesDr. Yao Xie, ECE587, Information Theory, Duke University9
Expected code length Expected length L(C) of a source code C(x) for X with pdf p(x)L(C) p(x)l(x)x X We wish to construct instantaneous codes of minimum expected lengthDr. Yao Xie, ECE587, Information Theory, Duke University10
Kraft inequality By Kraft in 1949 Coded over alphabet size D m codes with length l1, . . . , lm The code length of all instantaneous code must satisfy Kraft inequalitym D li 1i 1 Given l1, . . . , lm satisfy Kraft, can construct instantaneous code Can be extended to uniquely decodable code (McMillan inequality)Dr. Yao Xie, ECE587, Information Theory, Duke University11
Proof of Kraft inequality Consider D-ary tree Each codeword is represented by a leaf node Path from the root traces out the symbol Prefix code: no codeword is an ancestor of any other codeword on thetree Each code eliminates its descendants as codewordsDr. Yao Xie, ECE587, Information Theory, Duke University12
0Root10110111Dr. Yao Xie, ECE587, Information Theory, Duke University13
lmax be the length of longest codeword A codeword at level li has Dlmax li descendants Descendant sets must be disjoint: Dlmax li Dlmax D li 1 Converse: if l1, . . . , lmax satisfy Kraft inequality, can label first node atdepth l1, remove its descendants. Can extend to infinite prefix code lmax Dr. Yao Xie, ECE587, Information Theory, Duke University14
Optimal expected code length One application of Kraft inequality Expected code length of D-ary is lower bounded by entropy:L HD (X)Proof:L HD (X) pili pi logD1pi1 D(p r) logD 0c ri D li /D lj , c D li 1jDr. Yao Xie, ECE587, Information Theory, Duke University15
Achieve minimum code length if– c 1: Kraft inequality is equality– ri pi: approximated pdf using D-ary alphabet is exact How to construct such an optimal code? Finding the D-adic distribution that is closet to distribution of X Construct the code by converse of Kraft inequalityDr. Yao Xie, ECE587, Information Theory, Duke University16
Construction of optimal codes Finding the D-adic distribution that is closet to distribution of X isimpractical because finding the closest D-adic distribution is not obvious Good suboptimal procedure– Shannon-Fano coding– Arithmetic coding Optimal procedure: Huffman codingDr. Yao Xie, ECE587, Information Theory, Duke University17
First step: finding optimal code length Solving optimization problemminimizelisubject tom i 1m pi liD li 1.i 1 Solve using Lagrangian multiplierJ m pili λ(i 1Dr. Yao Xie, ECE587, Information Theory, Duke Universitym D li 1)i 118
Solution:li logD pi. Achieves the lower bound: L pili pi logD pi HD (X). Problem: logD pi may not be an integer! Rounding upli ⌈ logD pi⌉.may not be optimal. Usable code constructions?Dr. Yao Xie, ECE587, Information Theory, Duke University19
Summary Nonsingular Uniquely decodable Instantaneous codes Kraft inequality for Instantaneous code Entropy is lower bound on expected code lengthDr. Yao Xie, ECE587, Information Theory, Duke University20
Lecture 7: Source Coding and Kraft Inequality Codes Kraft inequality and consequences Dr. Yao Xie, ECE587, Information Theory, Duke University
Introduction of Chemical Reaction Engineering Introduction about Chemical Engineering 0:31:15 0:31:09. Lecture 14 Lecture 15 Lecture 16 Lecture 17 Lecture 18 Lecture 19 Lecture 20 Lecture 21 Lecture 22 Lecture 23 Lecture 24 Lecture 25 Lecture 26 Lecture 27 Lecture 28 Lecture
Lecture 1: A Beginner's Guide Lecture 2: Introduction to Programming Lecture 3: Introduction to C, structure of C programming Lecture 4: Elements of C Lecture 5: Variables, Statements, Expressions Lecture 6: Input-Output in C Lecture 7: Formatted Input-Output Lecture 8: Operators Lecture 9: Operators continued
Source Coding Techniques 1. Fixed Length Coding In fixed length coding technique all symbols assigned with equal length because the coding don’t take the probability in account. The benefit of the fixed length code is ease of applied (easy in coding and decoding) Example1: Let x { x 1,x 2, ,x 16} where pi 1/16 for all i , find ζ
Lecture 1: Introduction and Orientation. Lecture 2: Overview of Electronic Materials . Lecture 3: Free electron Fermi gas . Lecture 4: Energy bands . Lecture 5: Carrier Concentration in Semiconductors . Lecture 6: Shallow dopants and Deep -level traps . Lecture 7: Silicon Materials . Lecture 8: Oxidation. Lecture
TOEFL Listening Lecture 35 184 TOEFL Listening Lecture 36 189 TOEFL Listening Lecture 37 194 TOEFL Listening Lecture 38 199 TOEFL Listening Lecture 39 204 TOEFL Listening Lecture 40 209 TOEFL Listening Lecture 41 214 TOEFL Listening Lecture 42 219 TOEFL Listening Lecture 43 225 COPYRIGHT 2016
Partial Di erential Equations MSO-203-B T. Muthukumar tmk@iitk.ac.in November 14, 2019 T. Muthukumar tmk@iitk.ac.in Partial Di erential EquationsMSO-203-B November 14, 2019 1/193 1 First Week Lecture One Lecture Two Lecture Three Lecture Four 2 Second Week Lecture Five Lecture Six 3 Third Week Lecture Seven Lecture Eight 4 Fourth Week Lecture .
8 Bernd Girod: EE368b Image and Video Compression Introduction no. 15 Outline EE368b n Some fundamental results of information theory n Scalar quantization and vector quantization n Human visual perception n Predictive coding n Transform coding n Resolution pyramids and subband coding n Interframe coding n Motion estimation n Motion compensated coding n Coding standards JPEG, H.261, H.263 and MPEG
Coding ClinicReferences 1 Injury and Poisoning Coding Clinic 4Q 2008 ICD-9-CM Official Guidelines for Coding and Reporting Effective October 1, 2008 Chapter 17: Injury and Poisoning (800-999) Coding of Injuries When coding injuries, assign separate codes for ea
