I'm reading Cover's "Elements of Information Theory" and I have a problem with the definition of uniquely decodable code.

A code is said to be singular if there exist two elements that map to the same string. In other case it is said to be non singular.

Let $C$ be a code. The extension of $C$ is the homomorphism $C^{*}$ between $\chi$ and $D$ with respect to concatenation that is, $C(x_1 > \cdots x_n) = C(x_1) \cdots C(x_n)$.

Let $C$ be a code. $C$ is uniquely decodable if its extension $C^{*}$ is non-singular.

According to the last definition the extension of a code is itself a code but as it has domain $\chi^{*}$ where $\chi \subseteq \mathbb{R}$ (that last statement is mine).

How can I view the extension as a code?

  • 1
    $\begingroup$ Why did $\mathbb{R}$ show up? $\endgroup$ – Yuval Filmus Oct 10 '16 at 13:24

Cover and Thomas are using here the following definition of a code: given a domain $D$ and an alphabet $A$, a code is a mapping from $D$ to $A^*$. That is, a code assigns every element of $D$ a word over $A$. The extension of the code is a code from $D^*$ to $A^*$ defined by concatenation.

For example, let $D = \{a,b\}$ and $A = \{0,1\}$, and consider the code $C$ given by $C(a) = 0$, $C(b) = 00$. Its extension $C^*$ is a function from $\{a,b\}^*$ to $\{0,1\}^*$ obtained by replacing each $a$ by $0$ and each $b$ by $00$. For example, $C^*(ab) = C(a)C(b) = 000$. Since $C^*(ba) = C(b)C(a) = 000$ as well, the code $C^*$ is singular.

A code $C$ is uniquely decodable if there do not exist two sets of words $x_1\ldots x_n$ and $y_1\ldots y_m$ such that $C(x_1)\ldots C(x_n) = C(y_1)\ldots C(y_m)$. This is exactly the same as saying that $C^*$ is non-singular, since the condition is completely equivalent to $C^*(x_1\ldots x_n) = C^*(y_1\ldots y_n)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.