RANDOMIZED GENERATION OF ERROR CONTROL CODES WITH AUTOMATA AND TRANSDUCERS

• Tipo: Artigo em Revista Científica Internacional
• Data: 2018

Autores

Konstantinidis, S (Autor) Outra; Nelma Moreira (Autor) FCUP; Rogério Reis (Autor) FCUP

Revista

Título: RAIRO - Theoretical Informatics and Applications

Vol. 52

Páginas: 169-184

ISSN: 0988-3754

Editora: EDP Sciences

Indexação

ISI Web of Knowledge - 2 Citações

Scopus - 2 Citações

Outras Informações

ID Authenticus: P-00Q-94C

DOI: 10.1051/ita/2018015

Abstract (EN): We introduce the concept of an f-maximal error-detecting block code, for some parameter f 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, l and a specification of the errors permitted in some application, and generates an error-detecting, or error-correcting, block code of length l 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 16