Title | ||
---|---|---|
Channels with Synchronization/Substitution Errors and Computation of Error Control Codes. |
Abstract | ||
---|---|---|
We introduce the concept of an ff-maximal error-detecting block code, for some parameter ff{} between 0 and 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 constructing a maximal error-detecting code is a computationally hard problem. We present a randomized algorithm that takes as input two positive integers $N,ell$, a probability value ff, and a specification of the errors permitted in some application, and generates an error-detecting, or error-correcting, block code having up to $N$ codewords of length $ell$. If the algorithm finds less than $N$ codewords, then those codewords constitute a code that is ff-maximal with high probability. The error specification (also called channel) is modelled as a transducer, which allows one to model 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 channels. A methodological contribution is the presentation of how various desirable error combinations can be expressed formally and processed algorithmically. |
Year | Venue | Field |
---|---|---|
2016 | arXiv: Information Theory | Integer,Discrete mathematics,Randomized algorithm,Synchronization,Constant-weight code,Block code,Algorithm,Error detection and correction,Code (cryptography),Mathematics,Computation |
DocType | Volume | Citations |
Journal | abs/1601.06312 | 2 |
PageRank | References | Authors |
0.46 | 4 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stavros Konstantinidis | 1 | 283 | 31.10 |
Nelma Moreira | 2 | 180 | 33.98 |
Rogério Reis | 3 | 140 | 25.74 |