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.
Mots-clés : Randomized algorithm, output polynomial time algorithm, error control codes, maximal codes, synchronization errors, combinatorial channels
@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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ita/2018015/
[1] FAdo and GUItar: Tools for automata manipulation and visualization. In Proc. of CIAA 2009, Sydney, Australia, edited by Vol. 5642 of Lecture Notes in Computer Science. Springer-Verlag (2009) 65–74
, , , and ,[2] Transductions and Context-Free Languages.B.G. Teubner, Stuttgart (1979) | DOI | MR | Zbl
,[3] Computer construction of quasi-twisted two-weight codes. In Sixth International Workshop on Optimal Codes and Related Topics (2009) 62–68
,[4] Formal descriptions of code properties: decidability, complexity, implementation. Int. J. Found. Comput. Sci. 23 (2012) 67–85 | DOI | MR | Zbl
and ,[5] Tools for formal languages manipulation. Accessed in January 2016. Available at: http://fado.dcc.fc.up.pt/.
,[6] Optimal binary linear codes of length ≤ 30. In Proc. ofthe 1998 International Symposium on Information Theory (1998) 17 | DOI | MR | Zbl
,[7] On generating all maximal independent sets. Inf. Process. Lett. 27 (1988) 119–123 | DOI | MR | Zbl
, and ,[8] Solid codes. Elektron. Informationsverarbeit. Kybernetik. 26 (1990) 563–574 | Zbl
and ,[9] On the enumeration of minimal dominating sets and related notions. SIAM J. Discrete Math. 28 (2014) 1916–1929 | DOI | MR | Zbl
, , and ,[10] Implementation of code properties via transducers. In Proc. of CIAA 2016, edited by and . Vol. 9705 in Lecture Notes in Computer Science. Springer-Verlag (2016) 189–201 | MR
, , and ,[11] Maximal error-detecting capabilities of formal languages. J. Autom. Lang. Comb. 13 (2008) 55–71 | MR | Zbl
and ,[12] Finding error-correcting codes using computers. In Information Security, Coding Theory and Related Combinatorics (2011) 278–284 | MR | Zbl
,[13] Binary codes capable of correcting deletions, insertions, and reversals. Sov. Physi. Dokl. 10 (1966) 707–710 | MR | Zbl
,[14] Maximum number of words in codes without overlaps. Probl. Inform. Trans. 6 (1973) 355–357
,[15] Combinatorial problems motivated by comma-free codes. J. Comb. Des. 12 (2004) 184–196 | DOI | MR | Zbl
,[16] Elements of the Theory of Computation, 2nd ed. Prentice Hall (1998) | Zbl
and ,[17] Error control coding, 2nd ed. Pearson (2005)
and[18] Codes for deletion and insertion channels with segmented errors. In Proc. of ISIT, Nice, France, 2007 (2007) 846–849
and ,[19] The Theory of Error-Correcting Codes. Amsterdam (1977) | MR | Zbl
and ,[20] A survey of error-correcting codes for channels with symbol synchronization errors. IEEE Commun. Surv. Tutor. 12 (2010) 87–96 | DOI
, and ,[21] Probability and Computing. Cambridge University Press (2005) | DOI | MR | Zbl
and ,[22] Insertion/deletion detecting codes and the boundary problem. IEEE Trans. Inf. Theory 59 (2013) 5935–5943 | DOI | MR | Zbl
, and ,[23] Handbook of Coding Theory. Elsevier (1998)
and , editors.[24] a fast, compliant alternative implementation of the Python language. Available at: http://pypy.org (2017)
,[25] Handbook of Formal Languages, Vol. I. Springer-Verlag, Berlin (1997) | MR | Zbl
and ,[26] The Mathematical Theory of Communication. University of Illinois Press, Urbana (1949) | MR | Zbl
and ,[27] Free Monoids and Languages, 2nd ed. Hon Min Book Company, Taichung (1991) | MR | Zbl
,[28] A note on double insertion/deletion correcting codes. IEEE Trans. Inf. Theory 49 (2003) 269–273 | DOI | MR | Zbl
and ,Cité par Sources :