Fixed-Length Binary Codes

Fixed-length codes — also known as block codes in source coding — assign every symbol of a source alphabet the same binary codeword length. They form the simplest coding scheme, trading off compression for uniformity and ease of decoding.

Definition link

Let $\Sigma = \lbrace \sigma_1, \sigma_2, …, \sigma_n \rbrace$ be a source alphabet of size $n$. A fixed-length binary code uses codewords of length

$$ L = \lceil \log_2 n \rceil $$

bits each. The encoding function is

$$ f\colon \Sigma \longrightarrow \lbrace 0,1 \rbrace ^ L $$

where $f$ is injective, mapping each $\sigma_i$ to a unique bit-string of length $L$.

Example link

Suppose $\Sigma = \lbrace A,B,C,D,E \rbrace$, so $n = 5$. Then

$$ L = \lceil \log_2 5 \rceil = 3 $$

The eight possible 3-bit strings are

$$ 000,~ 001,~ 010,~ 011,~ 100,~ 101,~ 110,~ 111 $$

One possible mapping is

$$ A \rightarrow 000,~ B \rightarrow 001,~ C \rightarrow 010,~ D \rightarrow 011,~ E \rightarrow 100 $$