Geodesic
Randomized generation of error control codes with automata and transducers
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 169-184

Voir la notice de l'article provenant de la source Numdam

We introduce the concept of an -maximal error-detecting block code, for some parameter in (0,1), in order to formalize the situation where a block code is close to maximal with respect to being error-detecting. Our motivation for this is that it is computationally hard to decide whether an error-detecting block code is maximal. We present an output-polynomial time randomized algorithm that takes as input two positive integers N, ℓ and a specification of the errors permitted in some application, and generates an error-detecting, or error-correcting, block code of length ℓ that is 99%-maximal, or contains N words with a high likelihood. We model error specifications as (nondeterministic) transducers, which allow one to represent any rational combination of substitution and synchronization errors. We also present some elements of our implementation of various error-detecting properties and their associated methods. Then, we show several tests of the implemented randomized algorithm on various error specifications. A methodological contribution is the presentation of how various desirable error combinations can be expressed formally and processed algorithmically.

DOI : 10.1051/ita/2018015
Classification : 68Q45, 68W20, 94A40, 94B25
Keywords: Randomized algorithm, output polynomial time algorithm, error control codes, maximal codes, synchronization errors, combinatorial channels

Konstantinidis, Stavros 1 ; Moreira, Nelma 1 ; Reis, Rogério 1

1 
@article{ITA_2018__52_2-3-4_169_0,
     author = {Konstantinidis, Stavros and Moreira, Nelma and Reis, Rog\'erio},
     editor = {Bordihn, Henning and Nagy, Benedek and Vaszil, Gy\"orgy},
     title = {Randomized generation of error control codes with automata and transducers},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {169--184},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {2-3-4},
     year = {2018},
     doi = {10.1051/ita/2018015},
     mrnumber = {3915308},
     zbl = {1423.68260},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2018015/}
}
TY  - JOUR
AU  - Konstantinidis, Stavros
AU  - Moreira, Nelma
AU  - Reis, Rogério
ED  - Bordihn, Henning
ED  - Nagy, Benedek
ED  - Vaszil, György
TI  - Randomized generation of error control codes with automata and transducers
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2018
SP  - 169
EP  - 184
VL  - 52
IS  - 2-3-4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2018015/
DO  - 10.1051/ita/2018015
LA  - en
ID  - ITA_2018__52_2-3-4_169_0
ER  - 
%0 Journal Article
%A Konstantinidis, Stavros
%A Moreira, Nelma
%A Reis, Rogério
%E Bordihn, Henning
%E Nagy, Benedek
%E Vaszil, György
%T Randomized generation of error control codes with automata and transducers
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2018
%P 169-184
%V 52
%N 2-3-4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2018015/
%R 10.1051/ita/2018015
%G en
%F ITA_2018__52_2-3-4_169_0
Konstantinidis, Stavros; Moreira, Nelma; Reis, Rogério. Randomized generation of error control codes with automata and transducers. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 169-184. doi: 10.1051/ita/2018015

Cité par Sources :