Код Фибоначчи

Код Фибоначчи

Фибоначчиева система счислениясмешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т.д.

Число Запись
в ФСС
Код
Фибоначчи
0 0……0  
F2=1 1 11
F3=2 10 011
F4=3 100 0011
4 101 1011
F5=5 1000 00011
6 1001 10011
7 1010 01011
F6=8 10000 000011
Fn-1  101010 0101011 
Fn 10……00 00……011
Fn+1 10……01 10……011

Содержание

Представление натуральных чисел

Любому неотрицательному целому числу a = 0,\ 1,\ 2,\dots можно единственным образом представить через последовательность битов …εk…ε4ε3ε2: a = \sum_k \varepsilon_k F_k,\ \varepsilon_k = 0,1, причём последовательность {εk} содержит лишь конечное число единиц, и не имеет пар соседних единиц: \forall k\ge 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0). За исключением последнего свойства, данное представление аналогично двоичной системе счисления.

Обоснование

В основе лежит теорема Цеккендорфа — любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.

Доказательство существования легко провести по индукции. Любое целое число a\ge 1 попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого n\ge 2 верно неравенство: F_n \le a <  F_{n+1}. Таким образом, a = Fn + a', где a'=a-F_n\ <\ F_{n-1}, так что разложение числа a' уже не будет содержать слагаемого Fn − 1.

Использование в теории информации

На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчиуниверсальный код для натуральных чисел (1, 2, 3…), использующий последовательности битов. Поскольку комбинация 11 запрещена в Фибоначчиевой системы счисления, её можно использовать как маркер конца записи. Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз 1 (см. таблицу). То есть, кодовая последовательность имеет вид:

ε2ε3…εn1,

где n — номер самого старшего разряда с единицей.

Арифметика

При сложении чисел в позиционных системах счисления приходится выполнять перенос, то есть устранять последствия переполнения разряда. Например, в двоичной системе: 01 + 01 = 02 = 10. В фибоначчиевой системе дело обстоит намного сложнее. Во-первых, вес старших разрядов не является кратным весу разряда, из которого требуется перенос. При сложении двух единиц в одном разряде требуется перенос не только вправо, но и влево: 0200 = 1001. При переносе в отсутствующие разряды ε1 и ε0 следует помнить, что F1=1=F2 и F0=0. Во-вторых, требуется избавляться от соседних единиц: 011 = 100. Правило для раскрытия двоек является следствием этого равенства: 0200 = 0100 + 0011 = 0111 = 1001.

Обобщение на действительные числа

Похожее устройство имеет позиционная система счисления для действительных чисел, основанием которой служит золотое сечение \varphi = (1 + \sqrt{5})/2иррациональное число. Оказывается, что любое действительное число x из отрезка [0,1] допускает разложение в ряд через отрицательные степени золотого сечения:

x = \sum_{k=-1}^{-\infty} \varepsilon_k \varphi^k,\ \varepsilon_k = 0,1\ ,

где {εk} обладает тем же свойством отсутствия соседних единиц. Коэффициенты находятся последовательным сравнением x с \varphi^{-1} — золотым сечением отрезка [0,1], вычитанием \varphi^{-1} (если εk=1) и умножением на \varphi. Из этого нетрудно видеть, что любое неотрицательное действительное число допускает разложение:

a = \sum_{k=N-1}^{-\infty} \varepsilon_k \varphi^k\,,

где N таково, что a < \varphi^N. Разумеется, следует считать что \varepsilon_k = 0 для всех k \ge N.

Число Представление
через
степени \varphi
 1      1,
 2     10,01
 3    100,01
 4    101,01
 5   1000,1001
 6   1010,0001
 7  10000,0001
 8  10001,0001
 9  10010,0101
10  10100,0101
11  10101,0101
12 100000,101001
13 100010,001001
14 100100,001001

Эти формулы полностью аналогичны формулам для обычных позиционных систем с целыми основаниями. Оказывается, что любое неотрицательное целое число (и, более общо, всякий неотрицательный элемент кольца {\mathbb Z}+\varphi{\mathbb Z}) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения.[1]

Аналогия между числами Фибоначчи и степенями золотого сечения основана на одинаковой форме тождеств:

F_k = F_{k-1} + F_{k-2}\,,\ \varphi^k = \varphi^{k-1} + \varphi^{k-2}\,,

позволяющих устранение соседних единиц. Прямой связи между представлением натуральных чисел в системе золотого сечения и в фибоначчиевой не имеется.

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

Фибоначчиево «произведение»

Для целых чисел a = \sum_k \varepsilon_k F_k\ и b = \sum_l \zeta_l F_l\ можно определить «произведение»[2]

a\circ b = \sum_{k,l} \varepsilon_k \zeta_l F_{k+l},

формула для которого аналогична формуле умножения двоичных чисел.

Разумеется, данная операция не является настоящим умножением чисел, и выражается[3] формулой:

a\circ b =  3 a b  -  a [\varphi^{-2}(b+1)] -  b [\varphi^{-2}(a+1)]\ , где […] — целая часть.

Эта операция обладает ассоциативностью. Впервые на ассоциативность этой операции обратил внимание Дональд Кнут[4]. Следует отметить, что другое «произведение» \sum_{k,l} \varepsilon_k \zeta_l F_{k+l-2}, отличающееся лишь сдвигом на два разряда, уже не будет ассоциативно.

Источники

  1. en:Golden ratio base(англ.)
  2. последовательность A101330 в OEIS, en:Zeckendorf's theorem(англ.)
  3. Notes on the Fibonacci circle and arroba products(англ.)
  4. D. E. Knuth, Fibonacci multiplication, Appl. Math. Lett. 1 (1988), 57-60.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Код Фибоначчи" в других словарях:

  • Код да Винчи — Код да Винчи  это также название фильма 2006 года с Томом Хэнксом и Одри Тоту в главных ролях. Код да Винчи The Da Vinci Code …   Википедия

  • Код да Винчи (фильм) — Код да Винчи The Da Vinci Code Жанр триллер …   Википедия

  • Код Да Винчи (фильм) — Код да Винчи The Da Vinci Code Жанр триллер Режиссёр Рон Ховард Автор сценария Акива Голдсман …   Википедия

  • Код Хаффмана — Алгоритм Хаффмана  адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им …   Википедия

  • Код Хаффмена — Алгоритм Хаффмана (англ. Huffman) адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. В настоящее… …   Википедия

  • Код Шеннона-Фано — Алгоритм Шеннона Фано  один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже. Алгоритм… …   Википедия

  • Кодирование Фибоначчи — Фибоначчиева система счисления смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т.д. Число Запись в ФСС Код Фибоначчи 0 0……0   F2=1 1 …   Википедия

  • Числа Фибоначчи — Числа Фибоначчи  элементы числовой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … (последовательность A000045 в OEIS) в которой каждое последующее число равно сумме двух… …   Википедия

  • Универсальный код — для целых чисел в сжатии данных  префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределение вероятностей на целых числах, пока распределение  монотонно… …   Википедия

  • Универсальный код (сжатие данных) — Универсальный код для целых чисел в сжатии данных  префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределение вероятностей на целых числах, пока распространение … …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»