Meta-Fibonacci Codes:Efficient Universal Coding of Natural Numbers
| Autor: | Ricardo M. Campello de Souza, Bruno Tenório Ávila |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Block code
Prefix code Concatenated error correction code Code word Reed–Muller code 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Library and Information Sciences Kraft's inequality 01 natural sciences Linear code Computer Science Applications Combinatorics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Fibonacci word Information Systems Mathematics |
| Zdroj: | IEEE Transactions on Information Theory. 63:2357-2375 |
| ISSN: | 1557-9654 0018-9448 |
| DOI: | 10.1109/tit.2017.2663433 |
| Popis: | In this paper, we address the problem of the universal coding of natural numbers. A new numeration system is introduced, which is based on variable- $r$ meta-Fibonacci sequences and it is a generalization of the Zeckendorf numeration system. This new numeration system is used to construct binary, prefix-free, uniquely decodable universal codes called meta-Fibonacci codes . The main advantage of these codes is that they are parametrized by a sequence of numbers, the sequence o . By controlling the growth of the values of this sequence, we can control the length of the code word. This means that we can provide a general framework for building efficient universal coders for natural numbers. Such framework is applied to the upper bounds of the code word length defined by Leung-Yan-Cheong and Cover (1978), Levenshtein (1968), and Ahlswede (1997). There is no other code meeting these bounds. In each case, we build meta-Fibonacci codes and demonstrate that the upper bound of their code word length is satisfied up to an additive constant, thereby solving these open problems. The framework may be applied to other upper bounds that satisfy Kraft inequality. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|