Messages, Symbols, and Codes

Define sources, alphabets, messages, encoders, decoders, and binary codewords; compare fixed and variable lengths; and use prefix-free trees and the Kraft inequality to guarantee unambiguous decoding.

A message is a sequence of symbols produced by a source. A code represents that sequence in another form so that it can be stored or transmitted. Before asking how short a representation can be, we must state which messages are possible, which distinctions the receiver must preserve, and how the receiver will know where one codeword ends and the next begins.

Sources Produce Symbols and Messages

An alphabet is the set of symbols that may appear. For a binary source the alphabet is $\{0,1\}$ . For a four-symbol source it might be $\mathcal A=\{A,B,C,D\}$ . A source is the process or probability model that selects symbols from the alphabet. A message is a finite sequence of the selected symbols, such as $ABACA$ .

The symbols need not be written letters. They may represent pixels, audio samples, DNA bases, measurement categories, class labels, or tokens in a language model. Information theory ignores many physical details so that the same reasoning can apply to each case. It still requires a precise alphabet and a clear statement of what counts as one message.

If an alphabet contains $m$ symbols, then there are $m^n$ possible messages of length $n$ when every position may contain any symbol. A three-symbol alphabet therefore produces

3^4=81

possible messages of length four. This count concerns possibilities, not their probabilities. A source may make some of the $81$ messages much more likely than others.

Exercise: Count possible messages

A sensor alphabet is $\{\text{low},\text{normal},\text{high}\}$ . If a message contains exactly four readings and every reading may take any of the three values, how many different messages are possible?

Check the number of messages

Compute it first, then check your number.

HintChoose one symbol at each position

There are three choices at each of four positions, so use the multiplication rule.

SolutionFour positions produce eighty-one messages

Each position has three possible symbols. The number of length-four messages is therefore $3\times3\times3\times3=3^4=81$ .

Encoding and Decoding Must Agree

A codeword is the representation assigned to a source symbol or source sequence. An encoder maps a source message $x$ to an encoded representation $C(x)$ . A decoder maps that representation back to a reconstruction:

\hat{x}=D(C(x)).

“X hat equals D of C of x.” The encoder first converts $x$ into a code. The decoder then converts that code into the reconstructed message $\hat{x}$ .

For exact, or lossless, reconstruction, every valid message must satisfy

D(C(x))=x.

Different messages cannot then share the same complete encoded representation. If $C(x_1)=C(x_2)$ for two different messages, the decoder sees the same input in both cases and cannot know which original to return.

This condition also shows why sender and receiver must share the code. Suppose the sender uses $A\mapsto0$ and $B\mapsto1$ , while the receiver mistakenly uses $A\mapsto1$ and $B\mapsto0$ . The bits may arrive without error, yet the message will still be decoded incorrectly.

Exercise: Detect a mismatched codebook

The sender uses $A\mapsto0$ and $B\mapsto1$ , but the receiver uses $A\mapsto1$ and $B\mapsto0$ . The sender encodes $AB$ as 01. What message will the receiver decode?

Choose the decoded message

$AB$

$BA$

$AA$

Select one choice, then check.

HintUse the receiver's mapping

The receiver interprets 0 as $B$ and 1 as $A$ .

SolutionDifferent codebooks produce a different message

Under the receiver's codebook, 0 decodes to $B$ and 1 decodes to $A$ . The received message is therefore $BA$ , not the sender's $AB$ . Correctly transmitted bits are insufficient when the two sides disagree about their meaning.

Fixed-Length Binary Codes

With two bits, four source symbols can use the code:

Source symbol	Codeword
$A$	`00`
$B$	`01`
$C$	`10`
$D$	`11`

A bit is a binary digit, either 0 or 1. Every source symbol in this code costs two bits. A message of ten symbols therefore costs twenty bits, regardless of which symbols occur.

More generally, $b$ bits provide $2^b$ different binary strings. A fixed-length binary code for $m$ possible source symbols needs at least

b=\lceil\log_2m\rceil

bits per symbol. The ceiling rounds up because an individual codeword has a whole number of bits. For $m=5$ , two bits provide only four codewords, while three bits provide eight. Three codewords remain unused, but three bits are still necessary.

“The codeword length is the ceiling of log base two of the alphabet size.” It is the smallest whole number of binary choices that can distinguish all $m$ source symbols.

Fixed-length codewords are easy to separate. If every codeword has length three, the decoder reads the bit stream in groups of three. No delimiter is needed as long as the decoder knows where the encoded stream begins.

Exercise: Find a fixed codeword length

A source has five possible symbols. What is the smallest fixed number of bits needed for each symbol?

Check the codeword length

Compute it first, then check your number.

HintCompare powers of two

Two bits provide four codewords; three bits provide eight.

SolutionFive symbols require three bits

Since $2^2=4<5$ but $2^3=8\geq5$ , the smallest fixed codeword length is $3$ bits. The three unused binary strings do not reduce that required length.

Probabilities Guide Variable-Length Codes

Fixed-length codes ignore how often symbols occur. If $A$ is common and $D$ is rare, a variable-length code can give $A$ a short codeword and $D$ a longer one:

Source symbol	Probability	Codeword	Length
$A$	$1/2$	`0`	$1$
$B$	$1/4$	`10`	$2$
$C$	$1/8$	`110`	$3$
$D$	$1/8$	`111`	$3$

The expected, or long-run average, codeword length is

\begin{aligned} L &=\sum_{x\in\mathcal A}p(x)\ell(x)\\ &=\frac12(1)+\frac14(2)+\frac18(3)+\frac18(3)\\ &=1.75\text{ bits per source symbol}, \end{aligned}

where $\ell(x)$ is the length of the codeword for $x$ . The corresponding fixed-length code used two bits per symbol, so this code saves an average of $0.25$ bit per source symbol. It does not make every encoded message shorter: a message containing many rare symbols may become longer. The saving is an average under the stated source probabilities.

“L equals the sum, over source symbols x, of the probability of x times the codeword length of x.” Frequent symbols contribute to the average more often, which is why assigning them shorter codewords can help.

Exercise: Calculate expected code length

A source emits $X$ with probability $0.75$ and $Y$ with probability $0.25$ . Their codeword lengths are $1$ and $3$ bits. What is the expected length per source symbol?

Check the expected length

Compute it first, then check your number.

HintWeight each length by its probability

Calculate $0.75(1)+0.25(3)$ .

SolutionAverage the lengths using source probabilities

The expected length is $L=0.75(1)+0.25(3)=0.75+0.75=1.5$ bits per source symbol. The more common symbol contributes its short length on three quarters of source outputs.

Prefix-Free Codes Mark Their Own Boundaries

The variable-length code above is prefix-free: no complete codeword is the beginning, or prefix, of another complete codeword. A decoder can therefore read from left to right and stop as soon as it reaches a complete codeword. The stream 010111 splits uniquely as

0 | 10 | 111

and decodes to $ABD$ .

Without a suitable boundary rule, decoding can be ambiguous. Consider

A\mapsto0,\qquad B\mapsto01,\qquad C\mapsto1.

The bit string 01 could represent the one-symbol message $B$ or the two-symbol message $AC$ . This code is not uniquely decodable. Prefix-free coding is a convenient stronger condition that prevents such ambiguity immediately.

A prefix-free binary code can be drawn as a tree. Moving along a 0 or 1 edge leads to another node, and each source symbol occupies a leaf. A leaf cannot be an ancestor of another leaf, which is the tree version of the prefix condition.

Exercise: Decode a prefix-free message

Using $A\mapsto0$ , $B\mapsto10$ , $C\mapsto110$ , and $D\mapsto111$ , which message is represented by 110010?

Choose the decoded message

$CAB$

$CAD$

$DAB$

Select one choice, then check.

HintReturn to the root after each leaf

The first complete codeword is 110. Decode it, return to the tree root, and continue with the remaining bits.

SolutionSplit at complete codewords

The unique split is 110 | 0 | 10, which maps to $C$ , $A$ , and $B$ . The decoded message is therefore $CAB$ .

Codeword Lengths Cannot Be Chosen Freely

For binary prefix-free codeword lengths $\ell_1,\ldots,\ell_m$ , the Kraft inequality requires

\sum_{i=1}^{m}2^{-\ell_i}\leq1.

“The sum of two to the negative codeword length, over all codewords, is at most one.” Each term measures the fraction of leaves at that depth consumed by a codeword and all of the descendants that codeword prevents us from using.

For lengths $1,2,3,3$ , the sum is

2^{-1}+2^{-2}+2^{-3}+2^{-3} =\frac12+\frac14+\frac18+\frac18=1.

The prefix tree is full. By contrast, lengths $1,1,2$ give $1/2+1/2+1/4=1.25$ , so no binary prefix-free code can have those lengths. The inequality checks whether a set of lengths can fit in a prefix tree; it does not by itself assign symbols to codewords.

Exercise: Check whether codeword lengths can fit

Can a binary prefix-free code have lengths $1,2,2$ ?

Check the Kraft inequality

Yes

Select one choice, then check.

HintAdd the occupied tree fractions

Calculate $2^{-1}+2^{-2}+2^{-2}$ and compare the result with $1$ .

SolutionThe lengths exactly fill a binary prefix tree

The Kraft sum is $2^{-1}+2^{-2}+2^{-2}=1/2+1/4+1/4=1$ . It satisfies the inequality, so such a prefix-free code exists; for example, 0, 10, and 11.

From Code Length to Information

Coding turns the need to distinguish messages into a measurable length. Fixed-length codes depend only on the number of possible symbols. Variable-length codes can use source probabilities to reduce expected length, but they must remain decodable. Prefix-free codes provide clear boundaries, and the Kraft inequality states which collections of binary lengths can fit.

These ideas prepare two separate questions. First, what if the decoder must recover the source exactly, and what if a controlled approximation is enough? The next lesson answers that question through lossless and lossy compression. Afterward, self-information will connect an outcome's probability to its ideal code length, and entropy will average that quantity over the source.