\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \newcommand{\E} {\mathrm{E}} \)
deepdream of a sidewalk
Show Question
Math and science::INF ML AI

Symbol codes

A binary symbol code \( C \) for an ensemble a probability space \( (\Omega, \mathcal{A}_x, \mathcal{P}_x) \) is a mapping from the range of events \( \mathcal{A}_x = \{a_1, ..., a_n\} \), to \( \{0, 1\}^+ \). Let \( x \in \mathcal{A}_x \). \( c(x) \) denotes the codeword corresponding to \( x \) and \( l(x) \) will denote its length, with shorthand \( l_i = l(a_i) \).

The extended code, denoted \( C^+ \), is a mapping from \( \mathcal{A}_x^+ \) to \( \{0,1\}^+ \) obtained by concatenation:

\[ c^+(x_1x_2...x_N) = c(x_1)c(x_2)...c(x_N) \]

A code \( C(X) \) is said to be uniquely decodable if, under the extended code \( C^+ \), no two distinct strings have the same encoding. So:

\[ \forall x,y \in \mathcal{A}_x^+, x \neq y \implies c^+(x) \neq c^+(y) \]

or equivalently:

\[ \forall x,y \in \mathcal{A}_x^+, c^+(x) = c^+(y) \implies x = y \]

A symbol code is a prefix code if no codeword is a prefix of any other codeword. A prefix code is also known as a self-punctuating or instantaneous code, as an encoded string can be decoded from left to right without having to look ahead to subsequent codewords. A prefix code is uniquely decodable.

The expected length \( L(C, X) \) of a symbol code \( C \) for ensemble \( X \) is:

\[ L(C,X) = \sum_{x \in \mathcal{A}_x} P(x)l(x) \]

Alternatively written as:

\[ L(C, X) = \sum_{i=1}^{I} p_il_i \]

Where \( I = |\mathcal{A}_x| \)