5.2 Representing symbols by bits  (Page 2/2)

Finding a minimal representation

A four-symbol alphabet produces stochastically independent outcomes with the following probabilities. $$(x_1)=\frac{1}{2}$$ $$(x_2)=\frac{1}{4}$$ $$(x_3)=\frac{1}{8}$$ $$(x_4)=\frac{1}{8}$$ and an entropy of 1.75 bits/symbol. Let's see if we can find a codebook for this four-letter alphabet that satisfies the Source CodingTheorem. The simplest code to try is known as the simple binary code : convert the symbol's index into a binary number and use the same number of bits for each symbol byincluding leading zeros where necessary.

As all symbols are represented by 2 bits, obviously the average number of bits per symbol is 2.Because the entropy equals $1.75$ bits, the simple binary code is not a minimal representation according to the source coding theorem.If we chose a codebook with differing number of bits for the symbols, a smaller average number of bits can indeed be obtained. The idea is to use shorter bit sequences for the symbols that occur more often , i.e., symbols that have a higher probability. One codebook like this is Now $\langle L()\rangle =1\frac{1}{2}+2\frac{1}{4}+3\frac{1}{8}+3\frac{1}{8}=1.75$ . We can reach the entropy limit! This should come as no surprise, as promised above, when $\lg p_n$ is an integer for all $n$ , the optimal code is easily found.

The simple binary code is, in this case, less efficient than theunequal-length code. Using the efficient code, we can transmit the symbolic-valued signal having this alphabet 12.5%faster. Furthermore, we know that no more efficient codebook can be found because of Shannon's source coding theorem.

Got questions? Get instant answers now!

Optimality of the ascii code

Let us return to the ASCII codes presented in . Is the 7-bit ASCII code optimal, i.e., is it a minimal representation? The 7-bit ASCII code assign an equal length (7-bit) to all characters it represents. Thus, it would be optimal if all of the 128 characters wereequiprobable, that is each character should have a probability of $\frac{1}{128}$ . To find out whether the characters really are equiprobable an analysis of all English texts would be needed. Such an analysis is difficult to do. However, the letter "E" is more probable than the letter "Z", so the equiprobable assumption does not hold, and the ASCII codeis not optimal.

(A technical note: We should take into account that in English text subsequent outcomes are not stochastically independent. To see this, assume the first letter to be "b", then it is more probable that the next letter is "e", than "z". In the case where the outcomesare not stochastically independent, the formulation we have given of Shannon's source coding theorem is no longer valid, to fix this, we should replace the entropy with the entropy rate, but we will not pursue this here).

Got questions? Get instant answers now!