6.20 Source coding theorem

The significance of an alphabet's entropy rests in how we can represent it with a sequence of bits . Bit sequences form the "coin of the realm" in digitalcommunications: they are the universal way of representing symbolic-valued signals. We convert back and forth betweensymbols to bit-sequences with what is known as a codebook : a table that associates symbols to bit sequences. In creating this table, we must be able to assign a unique bit sequence to each symbol so that we can go between symbol and bit sequences without error.

As we shall explore in some detail elsewhere, digital communication is the transmission of symbolic-valued signals from one place toanother. When faced with the problem, for example, of sending a file across the Internet, we must first represent eachcharacter by a bit sequence. Because we want to send the file quickly, we want to use as few bits as possible. However, wedon't want to use so few bits that the receiver cannot determine what each character was from the bit sequence. Forexample, we could use one bit for every character: File transmission would be fast but useless because the codebookcreates errors. Shannon proved in his monumental work what we call today the Source Coding Theorem . Let $B(a_k)$ denote the number of bits used to represent the symbol $a_k$ . The average number of bits $\langle B(A)\rangle$ required to represent the entire alphabet equals $\sum_{k=1}^K B(a_k)(a_k)$ . The Source Coding Theorem states that the average number of bits needed to accurately represent the alphabet need only to satisfy