A novel test for unique decipherability of codes

dc.contributor.authorFalucskai, János
dc.date.accessioned2012-02-22T08:52:52Z
dc.date.available2012-02-22T08:52:52Z
dc.date.issued2012-02-22
dc.date.year2011
dc.description.abstractHaving 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.firstpage535en_US
dc.format.issue3-4en_US
dc.format.lastpage541en_US
dc.format.pages7en_US
dc.format.volume78en_US
dc.identifier.urihttp://hdl.handle.net/123456789/12
dc.language.isoenen_US
dc.subjectautomatonen_US
dc.subjectdecipherabilityen_US
dc.titleA novel test for unique decipherability of codesen_US
dc.title.journalPublicationes Mathematicae Debrecenen_US
dc.type.classArticleen_US
dc.type.specificationScientificen_US

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
4716-Falucskai-1.pdf
Size:
130.71 KB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
2.57 KB
Format:
Item-specific license agreed upon to submission
Description: