On unique decoding from insertion errors
| Autor: | Kayvon Mazooji |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Code word 020206 networking & telecommunications 02 engineering and technology Sequential decoding 01 natural sciences Upper and lower bounds Set (abstract data type) 010104 statistics & probability Position (vector) 0202 electrical engineering electronic engineering information engineering Code (cryptography) 0101 mathematics Algorithm Decoding methods Word (computer architecture) Computer Science::Information Theory Mathematics |
| Zdroj: | ISIT |
| Popis: | For any code, the set of received words generated by insertion errors is infinitely large. We prove that infinitely many of these words are uniquely decodable. We proceed to analyze how often unique decoding from insertions occurs for arbitrary codes. These questions are relevant because insertion errors frequently occur in synchronization and DNA, a medium which is beginning to be used for long term data storage. For a codeword c of length n, we are interested in two particular measures. The first is the probability of unique decoding when t insertions occur, if each distinct length n + t received word is output with equal probability. The second is the probability of unique decoding when t sequential insertions occur, and each insertion position and element are selected uniformly at random. This paper attempts to better understand the behavior of the measures for arbitrary codewords, placing a particular emphasis on limiting behavior as t or n increases. Our most substantial contribution is the derivation of upper bounds on both measures, which are mathematically related to Levenshtein's reconstruction problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|