The Coding Problem The source alphabet A of n symbols a1 a2 an and a corresponding set of probability n estimates P p1 p2 pn are given such that p i 1 The coding problem consists of 1 deciding on a code giving a representation of each symbol ai of the alphabet using strings over a channel alphabet B which is usually 0 1 Code Source message f code words alphabet A alphabet B alphanumeric symbols Channel alphabet binary symbols A n B 2 The symbol ai may be drawn from a longer message M consisting of strings of source alphabet symbols but at this point we are considering the symbol ai in isolation Sometimes we will denote the source alphabet A by the integers 1 2 3 n Let the codewords for a particular coding algorithm be C c1 c2 cn with corresponding lengths of codewords being L l1 l2 ln Then the average code length l or the expected codeword length E C P is given by n E C P l p j l j j 1 Prefix free Code A code is said to have prefix property if no code word or bit pattern is a prefix of other code word Sometimes prefix free code is also called simply prefix code A code is said to be uniquely decodable or uniquely decipherable UD if the message for the code string if it exists can be recovered unambiguously The fundamental question is how short can we make the average code length so that the code is UD Consider the table below giving different codes for 8 symbols a1 a 2 a8 Example Codes probabilities Code A ai p ai a1 0 40 a2 Code B codes Code C Code D Code E Code F 000 0 010 0 0 1 0 15 001 1 011 011 01 001 a3 0 15 010 00 00 1010 011 011 a4 0 10 011 01 100 1011 0111 010 a5 0 10 100 10 101 10000 01111 0001 a6 0 05 101 11 110 10001 011111 00001 a7 0 04 110 000 1110 10010 0111111 000001 a8 0 01 111 001 1111 10011 01111111 000000 3 1 5 2 9 2 85 2 71 Avg length 1 2 55 Code A violates Morse s principle not efficient but instantaneously decodable Code B not uniquely decodable Code C Prefix code that violates Morse s principle Code D UD but not prefix Code E not instantaneously decodable need look ahead to decode not prefix Code F UD ID and Prefix and obeys Morse s principle Code D E and F are incomplete as there are prefixes over the channel alphabets that are not used For D all four prefixes 00 01 10 and 11 do not occur etc Code F is a minimum redundancy code which is also known as Huffman code which we will discuss later Note 1 Code A is optimal if all probabilities are the same each taking log 2 N bits where N is the number of symbols 2 See Section 2 4 p 29 Sayood Code 5 a 0 b 01 c 11 is not prefix not instantaneously decodable but is uniquely decodable Consider the string 01 11 11 11 11 11 11 11 11 There is only one way to decode this string which will not have leftover dangling bits But if we interpret this as 0 11 11 11 11 11 11 11 11 1 a dangling left over 1 will remain 3 See Section 2 4 p 29 Sayood Code 6 a 0 b 01 c 10 decodable in two different ways The sequence 0 10 10 10 10 10 10 10 10 acccccccc but can also be parsed as 01 01 01 01 01 01 01 01 0 bbbbbbbba Both are valid interpretation So it is not UD not prefix Exercise Find and justify a test for a UD code Note there is a whole family of codes that use bit fractional codes which are not illustrated here in this table For example arithmetic codes which we will discuss later A code is Distinct mapping f is one to one Block to Block ASCII EBCDIC Block to Variable or VLC variable length code Huffman Variable to Block Arithmetic Variable to Variable LZ family Obviously every prefix code is UD but the converse is not true as we have seen The Kraft McMillan Inequality If the code words are the leaf nodes of a binary tree the code satisfies the prefix condition In general this is true for any d ary tree with d symbols in the alphabet Why restrict to prefix code Is it possible to find shorter code if we do not impose prefix property Fortunately the answer to this is NO For any non prefix uniquely decodable code we can always find a prefix code with the same codeword lengths If each symbol 2 ai has a probability which is a negative power of 2 that is pi 2 ki then the selfinformation is I ai log pi k i a whole number So if we set li k i this results in average code length or the expected code length equal to Shannon s entropy bound and n hence cannot be further improved We also have 2 li 1 This led Kraft 1949 to i 1 formulate the famous Kraft inequality Theorem 1 A necessary condition for UD code Let C be a code with n codewords with lengths l1 l2 ln If C is uniquely decodable then n K C 2 li 1 i 1 McMillan 1956 extended this result and showed that if the Kraft inequality is satisfied for some code C then it is possible to find a UD prefix code C that will have exactly the same lengths of code words as those of C Theorem 2 A sufficient condition for prefix code Given a set of integers l1 l2 l n n that satisfy the inequality 2 li 1 we can always find a prefix code with codeword i 1 lengths l1 l2 l n This code is also uniquely decipherable Further more this relationship is invertible that is if n K C 2 li i 1 is greater than 1 the code cannot be a prefix free As a simple but obvious example if each code word has length 1 then K C n 2 and a prefix free code is possible only if n 2 The corresponding codes are 0 and 1 Formal proofs for Theorem 1 and 2 are given in pp 32 34 Sayood Simpler Proofs for Theorems 1 and 2 for the Prefix Code We prove the Theorem 1 by using a binary tree embedding technique Every prefix code can be represented in the paths of a binary tree Example to illustrate the proof l j 2 2 2 3 4 4 3 Proof Given a binary prefix code with word lengths l j we may embed it in a binary tree of depth L where L max l j since each of the prefix code must define a unique path in a binary tree This embedding assigns to each …