- I have the alphabet: $A=\{a,d,k,u\}$,
- The code: $c=110011100111010$
- An code words: $$ \begin{array}{|c|c|c|c|} \hline x \in A& a & d & k & u \\ \hline \gamma (x) & 001 & 110 & 11 & 10\\ \hline \end{array} $$
The Kraft's inequality is true: $(2^{-3})*2+(2^{-2})*2=\frac{3}{4} \le 1$
But it is not prefix code: (the code of $k$ is in the beginning of the code of $d$)
So how can I prove that there is an unique decoding for $c$?
I found this solution but dont understand it: (can it be transferred into graphics?)
$\gamma$ seems to be bijective
$M_0=\{001,110,11,10\}$
$M_1=\{M_0^{-1}M_0 \cup M_0^{-1}M_0=\{0\} \cup \{0\} = \{0\}\}$
$M_2=\{M_1^{-1} M_0 \cup M_0^{-1}M_1=\{01\} \cup \{\emptyset\} = \{01\}\}$
$M_3=\{M_2^{-1} M_0 \cup M_0^{-1}M_2=\{\emptyset\} \cup \{\emptyset\} = \{\emptyset\}\}$
$[\Rightarrow] \ \forall \ n \geq 4 \ \wedge n \in \mathbb{N}^+ \ \ M_n=\emptyset$
$\Rightarrow M_1 \cap M_0 = \emptyset; \ M_2 \cap M_0 = \emptyset; \ \forall n \geq 3 \ M_n \cap M_0 = \emptyset$
$\Rightarrow \gamma $ is decodable
If you're only interested in decoding bit strings of finite length, you can do it as follows.
Suppose we are given a bit string $D$ of finite length which comes from encoding a word $W$ over the alphabet $A$ according to the code in your question.
First, observe that any triple $001$ in $D$ must come from an $a.$ There's no other way to produce such a triple with your code. So we have located all the $a$s in $D$ and can split $D$ accordingly into pieces which are codes of words over the alphabet $\{d,k,u\}.$ Let's call such a (non-empty) piece $E.$ By looking at the codes of $d,k,u,$ we see that $E$ cannot contain two consecutive zeros, that it cannot start with $0,$ and that it must have an even number of $1$s (possibly none) at the end. Those $1$s at the end of $E$ must be the code of some word $k\cdots k$ (possibly empty). Let's discard those $1$s at the end of $E$ and call the remaining code $F.$ If $F$ is empty, we are done. If not, $F$ is of the form $$ F = (1^{m_1}0) \ldots (1^{m_k}0)\qquad with\ exponents\ m_1,\ldots,m_k\geq 1. $$ This follows from the properties of $E$ noted above. Each $0$ in $F$ must come from the end of the code word of either a $u$ or a $d.$ So we have located some boundaries of code words in $F,$ which means that in order to decode $F,$ we can decode each piece $1^{m_j}0$ separately. So let's consider such a piece $G = 1^m0$ with $m\geq1.$ By looking at the admissible code words, it's "very easy" to see that if $m$ is even, i.e. $m = 2r$ with $r\geq 1,$ then $G$ must be the code of $k^{r-1}d,$ and if $m$ is odd, i.e. $m = 2s+1$ with $s \geq 0,$ then $G$ must be the code of $k^su.$
All in all, we have uniquely decoded the given bit string $D.$