Cheap and Secure Web Hosting Provider : See Now

The extension of a code is itself a code

, , No Comments
Problem Detail: 

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?

Asked By : Rodrigo
Answered By : Yuval Filmus

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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/64441

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback