A novel test for unique decipherability of codes
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.