RAIRO-Theor. Inf. Appl.
Volume 52, Number 2-3-4, April–December 2018
8th Workshop on Non-classical Models of Automata and Applications (NCMA 2016)
|Page(s)||169 - 184|
|Published online||29 January 2019|
Randomized generation of error control codes with automata and transducers★
Department of Mathematics and Computing Science, Saint Mary’s University,
Nova Scotia, Canada.
2 CMUP & DCC, Faculdade de Ciências da Universidade do Porto, Rua do Campo Alegre, 4169-007 Porto, Portugal.
* Corresponding author: email@example.com
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.
Mathematics Subject Classification: 68Q45 / 68W20 / 94A40 / 94B25
Key words: Randomized algorithm / output polynomial time algorithm / error control codes / maximal codes / synchronization errors / combinatorial channels
© EDP Sciences, 2019
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.