A novel test for unique decipherability of codes

Abstract

Having a set $C$ of codewords $w_i$ we have to decide whether there are two or more sequences of codewords which form the same chain of characters of codewords. A code $C$ is \emph{UD (uniquely decipherable)} code, if every message has at most one factorization with respect to code $C$, that is, if $x_1x_2\cdots x_n=y_1y_2\cdots y_m$ holds, where $x_1,x_2,\dots , x_n, y_1, y_2,\dots, y_m \in C$, then $n=m$ and $x_1=y_1,\dots, x_n=y_n$. We have developed an algorithm that solves this problem by using finite automata in \cite{Fal01}. In this paper we suppose that there is no empty string in the set of coded messages. Thus, we investigate the language $C^+$. In these cases the automata have more states, but we get more applicable results. A code C is UD (uniquely decipherable) code, if every message has at most one factorization with respect to code C, that is, if x1x2 . . . xn = y1y2 . . . ym holds, where x1, x2, . . . , xn, y1, y2, . . . , ym 2 C, then n = m and x1 = y1, . . . , xn = yn. We have developed an algorithm that solves this problem by using finite automata in [1]. In this paper we suppose that there is no empty string in the set of coded messages. Thus, we investigate the language C+. In these cases the automata have more states, but we get more applicable results.