0.13 Coding  (Page 14/22)

There are two different problems that can keep a transmission system from reaching the Shannon limit.The first is that the source may not be coded with maximum entropy, and this will be discussed next in "Source Coding" . The second is when different symbols experience differentamounts of noise. Recall that the plausibility argument for the channel capacity rested on the idea of the average noise.When symbols encounter anything less than the average noise, then all is well, since the average distance between levels is greater than theaverage noise. But errors occur when symbols encountermore than the average amount of noise.(This is why there are so many errors in the right-hand plot of [link] .) Good coding schemes try to ensure that allsymbols experience (roughly) the average noise. This can be accomplished by grouping the symbols into clusters or blocksthat distribute the noise evenly among all the symbols in the block. Such error coding isdiscussed in "Channel Coding" .

Source coding

The results from "Entropy" suggest that, all else being equal, it is preferable to choose a code in which each symboloccurs with the same probability. But what if the symbols occur with widelyvarying frequencies? Recall that this was shown in "Redundancy" for English and other natural languages. There are two basic approaches.The first aggregates the letters into clusters, and provides a new (longer) code word for each cluster.If properly chosen, the new code words can occur with roughly the same probability. The second approachuses variable-length code words, assigning short codes to common letters like “e” and long codes to infrequentletters like “x.” Perhaps the most common variable-length code was that devised by Morse for telegraph operators,which used a sequence of “dots” and “dashes” (along with silences of various lengths) to represent the lettersof the alphabet.

Before discussing how source codes can be constructed, consider an example using the $N=4$ code from Example [link] (a) in which $p\left(x_1\right)=0.5$ , $p\left(x_2\right)=0.25$ , and $p\left(x_3\right)=p\left(x_4\right)=0.125$ . As shown earlier, the entropy of this source is $1.75$ bits/symbol, which means that there must be some way of coding thesource so that, on average, $1.75$ bits are used for each symbol. The naive approach to this source would use 2bits for each symbol, perhaps assigning

An alternative representation is

where more probable symbols use fewer bits, and less probable symbols require more.For instance, the string

(in which each element appears with the expected frequency) is coded as

This requires 14 bits to represent the 8 symbols. The average is $14/8=1.75$ bits per symbol, and so this coding is as good as possible,since it equals the entropy. In contrast, the naive code of [link] requires 16 bits to represent the 8 symbols for anaverage of 2 bits per symbol. One feature of the variable length code in [link] is that there is never any ambiguity about where it starts, since any occurrence of a 1 corresponds to the end of a symbol.The naive code requires knowledge of where the first symbol begins. For example, the string $01-10-11-00-1\_$ is very different from $\_0-11-01-10-01$ even though they contain the same bits in the same order.Codes for which the start and end are immediately recognizable are called instantaneous or prefix codes.