算法课件Lecture11章节.pptVIP

Lecture 11Uniquely Decodable Code Related Notions Determining UDC Kraft Inequality Source Coding Source symbols Letters of alphabet, ASCII symbols, English dictionary, etc... Quantized voice Channel symbols In general there may be any limited number of channel symbols Typically {0,1} for a binary channel Morse Code Source Coding Objectives of source coding Uniquely decodable Compression Encode the source alphabet using the smallest average number of channel symbols Lossless compression Enables error free decoding Uniquely decodable without ambiguity Lossy compression Code may not be uniquely decodable, but with very high probability can be decoded correctly Uniquely Decodable Code Problem Input: A sequence (message) of source symbols Output: A sequence of channel symbols that can be uniquely and correctly decoded by a given source coding scheme. Application: Compression Communication in secret In encryption techniques A Simple Code with Ambiguity 我 们 和 好 分 手 吧 A Resulting Problem Given a coding scheme of the source symbols, how to verify if it is uniquely decodable or not? Related Notions alphabet: ? = {0, 1, …, ?-1} symbol or letter: an element of alphabet ? word: a sequence of symbols of finite length Code: a collection of words on a specified alphabet codeword: a word in a code message: a sequence of codewords Uniquely decodable code C: every message can be uniquely decomposed into the codewords in C {0, 10, 01} vs {0, 10, 11} Related Notions prefix and suffix: if w = ps, then p is prefix of w and s is suffix of w empty word: a word with length 0 suffix word: a non-empty word t is called a suffix word if there exist two messages C1C2…Cm and C1’C2’…Cn’ such that Ci, Cj’ are all codewords for 1 ? i ? m, 1 ? j ? n, and C1 ? C1’, t is the suffix of Cn’, C1C2…Cm t = C1’C2’…Cn’. A Key Lemma for Determining UDC A code C is uniquely decodable if and only if each suffix word is not a codeword in C. ? Suppose that a suffix word t is a codeword in C, acc