Коды Фибоначи. Коды Грея (47377)

Посмотреть архив целиком












Реферат

по курсу “Теория информации и кодирования ”


Тема:

"СПЕЦИАЛЬНЫЕ КОДЫ"


1. КОДЫ ФИБОНАЧЧИ


1.1 ЗОЛОТЫЕ ПРОПОРЦИИ


В математике существует большое количество иррациональных (несоизмеримых) чисел, т. е. обозначающих длину отрезка несоизмеримого с единицей масштаба. Ряд из них широко используется как в математике, так и в др. областях.

Например: Число  = 2R/D=3,14159… , которое представляет отношение длины окружности к ее диаметру. Число e = 2,71828… , при этом . Логарифмы с основанием e удобны для математических расчетов. Число 2 =1,44… , которое представляет отношение диагонали к стороне квадрата и ряд других чисел.

Особое иррациональное число  = (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=(15)/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 число 0(n) совпадает с двоичными разрядами 2n (табл. 1) .


Таблица 1

n

0

1

2

3

4

5

0(n)

1

2

4

8

16

32


При р = 1 число 0(n) совпадает с обычным рядом Фибоначчи:

1, 1, 2, 3, 5, 8, ...

При р = число 0(n) = 1 для любого n  0 равно:

1, 1, 1, 1, 1, 1, 1, 1, ...


1.3 КОДЫ ФИБОНАЧЧИ


Любое натуральное число N можно представить с помощью p-чисел Фибоначчи


(4)


где: ai {0, 1} - двоичная цифра i-го разряда; 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. 1(n)+ 1(n)= 1(n)+ 1(n-1)+ 1(n-2) т. е. равно 1 и перенос 1 в два младших разряда.

  2. 1(n)+ 1(n)= 1(n+1)+ 1(n-2) т. е. равно 0 и перенос 1 в два разряда - предыдущий и последующий.

Коды Фибоначчи обладают рядом полезных свойств (например, избыточность и т. д.), позволяющих строить быстродействующие и помехоустойчивые АЦП (“фибоначчевые” АЦП), реализующих специальные алгоритмы преобразования. Коды Фибоначчи используются для диагностики ЭВМ, в цифровых фильтрах для улучшения спектрального состава сигнала за счет перекодировки и др. областях.


Случайные файлы

Файл
14471-1.rtf
15350-1.rtf
ref-18157.doc
46416.rtf
2827-1.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.