Эта статья включает в себя список литературы , связанной литературы или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( Январь 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Системы счисления |
---|
Индусско-арабская система счисления |
Восточная Азия |
Американец |
По алфавиту |
Бывший |
|
Позиционные системы по основанию |
|
Нестандартные позиционные системы счисления |
|
Список систем счисления |
В математике и вычислениях кодирование Фибоначчи - это универсальный код [ необходима цитата ], который кодирует положительные целые числа в двоичные кодовые слова . Это один из примеров представления целых чисел на основе чисел Фибоначчи . Каждое кодовое слово заканчивается на «11» и не содержит других экземпляров «11» перед концом.
Код Фибоначчи тесно связан с представлением Цекендорфа , позиционной системой счисления, которая использует теорему Цекендорфа и обладает тем свойством, что ни одно число не имеет представления с последовательными единицами. Кодовое слово Фибоначчи для конкретного целого числа является в точности представлением Цекендорфа целого числа с обратным порядком цифр и добавленной в конец дополнительной цифрой «1».
Определение [ править ]
Для числа , если представить цифры кодового слова, представляющего, то мы имеем:
где F ( i ) - это i- е число Фибоначчи , и поэтому F ( i +2) - это i- е различное число Фибоначчи, начинающееся с . Последний бит всегда является добавленным битом 1 и не имеет разряда.
Можно показать, что такое кодирование уникально, и единственное вхождение «11» в любое кодовое слово находится в конце, то есть d ( k -1) и d ( k ). Предпоследний бит - это самый старший бит, а первый бит - младший бит. Также нельзя опускать ведущие нули, как, например, в десятичных числах.
Первые несколько кодов Фибоначчи показаны ниже, а также их так называемая подразумеваемая вероятность , значение для каждого числа, которое имеет код минимального размера в кодировании Фибоначчи.
Символ | Представление Фибоначчи | Кодовое слово Фибоначчи | Предполагаемая вероятность |
---|---|---|---|
1 | 11 | 1/4 | |
2 | 011 | 1/8 | |
3 | 0011 | 1/16 | |
4 | 1011 | 1/16 | |
5 | 00011 | 1/32 | |
6 | 10011 | 1/32 | |
7 | 01011 | 1/32 | |
8 | 000011 | 1/64 | |
9 | 100011 | 1/64 | |
10 | 010011 | 1/64 | |
11 | 001011 | 1/64 | |
12 | 101011 | 1/64 | |
13 | 0000011 | 1/128 | |
14 | 1000011 | 1/128 |
Чтобы закодировать целое число N :
- Найдите наибольшее число Фибоначчи, равное или меньшее N ; вычтите это число из N , отслеживая остаток.
- Если вычитаемое число было i- м числом Фибоначчи F ( i ), поместите 1 на место i −2 в кодовом слове (считая крайнюю левую цифру как место 0).
- Повторите предыдущие шаги, заменяя остаток на N , пока остаток не будет равен 0.
- Поставьте дополнительную 1 после крайней правой цифры кодового слова.
Чтобы декодировать кодовое слово, удалите последнюю цифру «1», присвойте оставшиеся значения 1,2,3,5,8,13 ... ( числа Фибоначчи ) битам в кодовом слове и просуммируйте значения биты "1".
Сравнение с другими универсальными кодами [ править ]
Кодирование Фибоначчи имеет полезное свойство, которое иногда делает его привлекательным по сравнению с другими универсальными кодами: это пример самосинхронизирующегося кода , упрощающего восстановление данных из поврежденного потока. В случае большинства других универсальных кодов, если изменяется один бит , никакие данные, которые идут после него, не будут правильно прочитаны. С другой стороны, при кодировании Фибоначчи измененный бит может привести к тому, что один токен будет считан как два или два токена будут считаться неправильно как один, но чтение «0» из потока остановит дальнейшее распространение ошибок. Поскольку единственный поток, в котором нет «0», это поток из «11» токенов, общее расстояние редактирования между потоком, поврежденным одной битовой ошибкой, и исходным потоком составляет не более трех.
Этот подход - кодирование с использованием последовательности символов, в которой запрещены некоторые шаблоны (например, «11»), можно свободно обобщать. [1]
Пример [ править ]
В следующей таблице показано, что число 65 представлено в кодировке Фибоначчи как 0100100011, поскольку 65 = 2 + 8 + 55 . Первые два числа Фибоначчи (0 и 1) не используются, и всегда добавляется дополнительное 1.
0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 год | 34 | 55 | - |
дополнительный | |||||||||||
- | - | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
Обобщения [ править ]
Кодировки Фибоначчи для положительных целых чисел представляют собой двоичные строки, которые заканчиваются на «11» и не содержат других экземпляров «11». Это можно обобщить на двоичные строки, которые заканчиваются N последовательными единицами и не содержат других экземпляров N последовательных единиц. Например, для N = 3 положительные целые числа кодируются как 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111,…. В этом случае количество кодировок как функция длины строки задается последовательностью чисел Трибоначчи .
Для общих ограничений, определяющих, какие символы разрешены после данного символа, максимальная скорость передачи информации может быть получена путем сначала нахождения оптимальных вероятностей перехода с использованием максимального энтропийного случайного блуждания , а затем использования энтропийного кодера (с переключаемым кодером с декодером) для кодирования сообщения как последовательность символов, удовлетворяющая найденным оптимальным вероятностям перехода.
См. Также [ править ]
- База золотого сечения
- Нумерация Островского
- Универсальный код
- Варикод , практическое применение
- Теорема цекендорфа
- Случайное блуждание с максимальной энтропией
Ссылки [ править ]
- ^ Дуда, Ярек (2007). «Оптимальное кодирование на дискретной решетке с трансляционными инвариантными ограничениями с использованием статистических алгоритмов». arXiv : 0710.3861 [ cs.IT ].
- Аллуш, Жан-Поль; Шаллит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . п. 105 . ISBN 978-0-521-82332-6. Zbl 1086.11015 .
- Fraenkel, Aviezri S .; Кляйн, Шмуэль Т. (1996). «Надежные универсальные полные коды для передачи и сжатия». Дискретная прикладная математика . 64 (1): 31–55. CiteSeerX 10.1.1.37.3064 . DOI : 10.1016 / 0166-218X (93) 00116-H . ISSN 0166-218X . Zbl 0874.94026 .
Дальнейшее чтение [ править ]
- Стахов А.П. (2009). Математика гармонии: от Евклида до современной математики и информатики . Сингапур: World Scientific Publishing .