Кодирование Фибоначчи

Эта статья включает в себя список литературы , связанной литературы или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Январь 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Системы счисления
Индусско-арабская система счисления
Западный арабский Восточно-арабский Бенгальский Деванагари Гуджарати Гурмукхи Одиа Сингальский Тамильский Малаялам телугу Каннада Дзонгка тибетский Балийский Бирманский Яванский Кхмерский Лаосский Монгольский Тайский
Восточная Азия
Китайский Сучжоу Хоккиен Японский Корейский вьетнамский Тангутский Счетные стержни
Американец
Кактовик (инупиак)
По алфавиту
Абджад Армянский Ryabhaa Кириллица Geʽez Грузинский Греческий иврит Римский
Бывший
Эгейское море Чердак Вавилонский Брахми Чувашский Цистерцианский Египтянин Этрусский Глаголица Харости майя Муиска Pentimal Доисторический счет Счетные отметки Quipu
Позиционные системы по основанию
2 3 4 5 6 8 10 12 16 20 60
Нестандартные позиционные системы счисления
Биективная нумерация ( 1 ) Знаковое представление ( сбалансированное троичное ) смешанный ( факториал ) отрицательный Комплексно-базовая система ( 2 i ) Нецелое основание счисления ( φ ) Асимметричные системы счисления
Список систем счисления
v т е

В математике и вычислениях кодирование Фибоначчи - это универсальный код ^{[ необходима цитата ],} который кодирует положительные целые числа в двоичные кодовые слова . Это один из примеров представления целых чисел на основе чисел Фибоначчи . Каждое кодовое слово заканчивается на «11» и не содержит других экземпляров «11» перед концом.

Код Фибоначчи тесно связан с представлением Цекендорфа , позиционной системой счисления, которая использует теорему Цекендорфа и обладает тем свойством, что ни одно число не имеет представления с последовательными единицами. Кодовое слово Фибоначчи для определенного целого числа является в точности представлением Цекендорфа целого числа с обратным порядком цифр и добавленной в конец дополнительной цифрой «1».

Определение [ править ]

Для числа , если представить цифры кодового слова, представляющего, то мы имеем: ${\ Displaystyle N \!}$ ${\ Displaystyle d (0), d (1), \ ldots, d (k-1), d (k) \!}$ ${\ Displaystyle N \!}$

{\ Displaystyle N = \ сумма _ {я = 0} ^ {k-1} d (i) F (i + 2), {\ text {and}} d (k-1) = d (k) = 1 . \!}

где $F (i)$ - это $i-$ е число Фибоначчи , и поэтому $F (i +2)$ - это $i-$ е различное число Фибоначчи, начинающееся с . Последний бит всегда является добавленным битом 1 и не имеет разряда. ${\ displaystyle 1,2,3,5,8,13, \ ldots}$ ${\ displaystyle d (k)}$

Можно показать, что такое кодирование уникально, и единственное вхождение «11» в любом кодовом слове находится в конце, т.е. d ( k -1) и d ( k ). Предпоследний бит - это самый старший бит, а первый бит - младший бит. Также нельзя опускать ведущие нули, как, например, в десятичных числах.

Первые несколько кодов Фибоначчи показаны ниже, а также их так называемая подразумеваемая вероятность , значение для каждого числа, которое имеет код минимального размера в кодировании Фибоначчи.

Символ	Представление Фибоначчи	Кодовое слово Фибоначчи	Предполагаемая вероятность
1	${\ Displaystyle F (2)}$	11	1/4
2	${\ Displaystyle F (3)}$	011	1/8
3	${\ Displaystyle F (4)}$	0011	1/16
4	${\ Displaystyle F (2) + F (4)}$	1011	1/16
5	${\ Displaystyle F (5)}$	00011	1/32
6	${\ Displaystyle F (2) + F (5)}$	10011	1/32
7	${\ Displaystyle F (3) + F (5)}$	01011	1/32
8	${\ Displaystyle F (6)}$	000011	1/64
9	${\ Displaystyle F (2) + F (6)}$	100011	1/64
10	${\ Displaystyle F (3) + F (6)}$	010011	1/64
11	${\ Displaystyle F (4) + F (6)}$	001011	1/64
12	${\ Displaystyle F (2) + F (4) + F (6)}$	101011	1/64
13	${\ Displaystyle F (7)}$	0000011	1/128
14	${\ Displaystyle F (2) + F (7)}$	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	-
${\ Displaystyle F (0)}$	${\ Displaystyle F (1)}$	${\ Displaystyle F (2)}$	${\ Displaystyle F (3)}$	${\ Displaystyle F (4)}$	${\ Displaystyle F (5)}$	${\ Displaystyle F (6)}$	${\ Displaystyle F (7)}$	$F(8)$	$F(9)$	$F(10)$	дополнительный
-	-	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 .

[1] Дуда, Ярек (2007). «Оптимальное кодирование на дискретной решетке с трансляционными инвариантными ограничениями с использованием статистических алгоритмов». arXiv : 0710.3861 [ cs.IT ].