Коды Фибоначи Коды Грея

В математике существует большое количество иррациональных (несоизмеримых) чисел, т. е. обозначающих длину отрезка несоизмеримого с единицей масштаба. Ряд из них широко используется как в математике, так и в др. областях.
Например: Число p = 2 p R/D=3,14159 … , которое представляет отношение длины окружности к ее диаметру. Число e = 2,71828 … , при этом . Логарифмы с основанием e удобны для математических расчетов. Число Ö 2 =1,44 … , которое представляет отношение диагонали к стороне квадрата и ряд других чисел.
Особое иррациональное число a = (1+ Ö 5)/2 = 1,61803, которое называется золотая пропорция или золотое сечение и является результатом решения задачи деления отрезка в крайнем и среднем отношении (рис. 1)
A C B
о o o
Рис. 1 Деление отрезка
Если задан отрезок AB то необходимо найти такую точку C , чтобы выполнялось условие AB/CB = CB/AC.
Обозначим: x = CB/AC ; (CB+AC)/CB = 1+1/x = x .
При этом x2 –x–1 = 0 . Корни этого уравнения равны: x1,2 =(1 ± Ö 5)/2 .
Положительный корень называется золотой пропорцией , а точка C - золотым сечением. Золотая пропорция обладает рядом уникальных свойств.
Пропорция 1,61... использовалась в архитектуре, художественных произведениях, музыке с античных времен. С этим числом связан ореол мистики, таинственности, божества и т.д.
В последнее десятилетие эта пропорция нашла свое применение в ЭВМ, АЦП-ЦАП, измерениях и т. д.
1.2 ЧИСЛА ФИБОНАЧЧИ
С золотым сечением тесно связаны числа Фибоначчи открытые итальянским математиком Леонардо из Пизы (Фибоначчи) в XIII веке, которые вычислены по формуле:
(1)
Эти числа представляют ряд: 1, 1, 2, 3, 5, 8, 13, 21...
Отношение соседних чисел Фибоначчи 1/1, 2/1, 3/2, 5/3, 8/5, 13/8, 21/13 ... в пределе стремится к золотой пропорции
. (2)
Числа Фибоначчи обладают еще рядом полезных свойств. Например, остатки от деления чисел Фибоначчи на 2 образуют последовательность: 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ... и т. д.
Обобщенные числа Фибоначчи или p -числа Фибоначчи вычисляются по рекуррентной формуле:
(3)
Где p = 0, 1, 2, 3, … . При р = 0 число j 0 (n) совпадает с двоичными разрядами 2n (табл. 1).
Таблица 1
n 0 1 2 3 4 5
j 0 (n) 1 2 4 8 16 32
При р = 1 число j 0 (n) совпадает с обычным рядом Фибоначчи:
1, 1, 2, 3, 5, 8, ...
При р = число j 0 (n) = 1 для любого n ³ 0 равно:
1, 1, 1, 1, 1, 1, 1, 1, ...
1.3 КОДЫ ФИБОНАЧЧИ
Любое натуральное число N можно представить с помощью p -чисел Фибоначчи
(4)
где: ai Î{0, 1} - двоичная цифра i -го разряда; j p (i) - вес i -го разряда;
Любое натуральное число N можно представить также следующим способом:

(5)
Такое представление чисел N называется p -кодом Фибоначчи. Каждому p Î{ 0, 1, 2, …, ¥} соответствует свой код, т. е. их число бесконечно.
При p = 0 p -код Фибоначчи совпадает с двоичным кодом.
Для 1-кода Фибоначчи кодовые комбинации имеют вид:
Таблица 2

N
KK Вес порядка
5 4 3 2 1
0 A0 0 0 0 0 0
1 A1 0 0 0 0 1
1 A2 0 0 0 1 0
2 A3 0 0 0 1 1
2 A4 0 0 1 0 0
3 A5 0 0 1 0 1
3 A6 0 0 1 1 0
4 A7 0 0 1 1 1
3 A8 0 1 0 0 0
4 A9 1 0 0 0 1
4 A10 0 1 0 1 0
5 A11 0 1 0 1 1
5 A12 0 1 1 0 0
6 A13 0 1 1 0 1
6 А14 0 1 1 1 0
7 А15 0 1 1 1 1
N KK
Вес порядка
5 4 3 2 1
5 A16 1 0 0 0 0
6 A17 1 0 0 0 1
6 А18 1 0 0 1 0
7 A19 1 0 0 1 1
7 A20 1 0 1 0 0
8 A21 1 0 1 0 1
8 A22 1 0 1 1 0
9 A23 1 0 1 1 1
8 A24 1 1 0 0 0
9 A25 1 1 0 0 1
9 A26 1 1 0 1 0
10 A27 1 1 0 1 1
10 A28 1 1 1 0 0
11 A29 1 1 1 0 1
11 A30 1 1 1 1 0
12 А31 1 1 1 1 1

Как видно из таблицы 5 разрядным 1-кодом Фибоначчи можно закодировать 13 натуральных чисел от 0 до 12, при этом каждому числу соответствует множество комбинаций.
Коды Фибоначчи образуют соответствующую систему счисления с набором арифметических операций.
Сложение: Вычитание:
0+0 = 0; 0- 0 = 0;
0+1 = 1; 1 -1 = 0;
1+0 = 1; 1 -0 = 1;
1+1 = 111; 10-1 = 1;
1+1 = 1001; 110 -1 = 11;
1000-1 = 111.
При сложении 2-х единиц может быть:
1. j 1 (n)+ j 1 (n)= j 1 (n)+ j 1 (n-1)+ j 1 (n-2) т. е. равно 1 и перенос 1 в два младших разряда.
2. j 1 (n)+ j 1 (n)= j 1 (n+1)+ j 1 (n-2) т. е. равно 0 и перенос 1 в два разряда - предыдущий и последующий.
Коды Фибоначчи обладают рядом полезных свойств (например, избыточность и т. д.), позволяющих строить быстродействующие и помехоустойчивые АЦП (“фибоначчевые” АЦП), реализующих специальные алгоритмы преобразования. Коды Фибоначчи используются для диагностики ЭВМ, в цифровых фильтрах для улучшения спектрального состава сигнала за счет перекодировки и др. областях.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию