16.36: Communication Systems Engineering Lecture 5: Source Coding Eytan Modiano
Eytan Modiano Slide 1 16.36: Communication Systems Engineering Lecture 5: Source Coding Eytan Modiano
Source coding Source Encode Channel Alphabet alphabet Source symbols Letters of alphabet, ASClI symbols, English dictionary, etc... Quantized voice Channel symbols In general can have an arbitrary number of channel symbols Typically [0, 1]for a binary channel Objectives of source coding Unique decodability Compression Encode the alphabet using the smallest average number of channel symbols
Eytan Modiano Slide 2 Source coding • Source symbols – Letters of alphabet, ASCII symbols, English dictionary, etc... – Quantized voice • Channel symbols – In general can have an arbitrary number of channel symbols Typically {0,1} for a binary channel • Objectives of source coding – Unique decodability – Compression Encode the alphabet using the smallest average number of channel symbols Source Alphabet {a1..aN} Encode Channel Alphabet {c1..cN}
Compression Lossless compression Enables error free decoding Unique decodability without ambiguity · Lossy compression Code may not be uniquely decodable, but with very high probability can be decoded correctly
Eytan Modiano Slide 3 Compression • Lossless compression – Enables error free decoding – Unique decodability without ambiguity • Lossy compression – Code may not be uniquely decodable, but with very high probability can be decoded correctly
Prefix(free) codes a prefix code is a code in which no codeword is a prefix of any other codeword Prefix codes are uniquely decodable Prefix codes are instantaneously decodable The following important inequality applies to prefix codes and in general to all uniquely decodable codes Kraft Inequality Let n,.. n, be the lengths of codewords in a prefix or any Uniquely decodable)code. Then, 2<1
Eytan Modiano Slide 4 Prefix (free) codes • A prefix code is a code in which no codeword is a prefix of any other codeword – Prefix codes are uniquely decodable – Prefix codes are instantaneously decodable • The following important inequality applies to prefix codes and in general to all uniquely decodable codes Kraft Inequality Let n1…nk be the lengths of codewords in a prefix (or any Uniquely decodable) code. Then, 2 1 1 − = ∑ ≤ n i k i
Proof of Kraft Inequality Proof only for prefix codes Can be extended for all uniquely decodable codes Map codewords onto a binary tree Codewords must be leaves on the tree A codeword of length n; is a leaf at depth n; ° Let nk2nk1…≥n1B> depth of tree=nk In a binary tree of depth nk, up to 2nk leaves are possible(if all leaves are at depth nk Each leaf at depth n, <n eliminates a fraction 1/2n of the leaves at depth nk=>eliminates 2nK-n of the leaves at depth nk Hence 22"→∑2"≤
Eytan Modiano Slide 5 Proof of Kraft Inequality • Proof only for prefix codes – Can be extended for all uniquely decodable codes • Map codewords onto a binary tree – Codewords must be leaves on the tree – A codeword of length ni is a leaf at depth ni • Let n k ≥ nk-1 … ≥ n1 => depth of tree = n k – In a binary tree of depth n k, up to 2nk leaves are possible (if all leaves are at depth n k) – Each leaf at depth ni < nk eliminates a fraction 1/2ni of the leaves at depth nk => eliminates 2nk -ni of the leaves at depth n k – Hence, 2 2 21 1 1 n n i k n n i k k − i k i = − = ∑ ∑ ≤⇒ ≤