A novel test for unique decipherability of codes
| dc.contributor.author | Falucskai, János | |
| dc.date.accessioned | 2012-02-22T08:52:52Z | |
| dc.date.available | 2012-02-22T08:52:52Z | |
| dc.date.issued | 2012-02-22 | |
| dc.date.year | 2011 | |
| dc.description.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. | en_US |
| dc.format.firstpage | 535 | en_US |
| dc.format.issue | 3-4 | en_US |
| dc.format.lastpage | 541 | en_US |
| dc.format.pages | 7 | en_US |
| dc.format.volume | 78 | en_US |
| dc.identifier.uri | http://hdl.handle.net/123456789/12 | |
| dc.language.iso | en | en_US |
| dc.subject | automaton | en_US |
| dc.subject | decipherability | en_US |
| dc.title | A novel test for unique decipherability of codes | en_US |
| dc.title.journal | Publicationes Mathematicae Debrecen | en_US |
| dc.type.class | Article | en_US |
| dc.type.specification | Scientific | en_US |