Коды Фибоначи Коды Грея (стр. 1 из 2)
Реферат
по курсу “Теория информации и кодирования ”
Тема:
"СПЕЦИАЛЬНЫЕ КОДЫ"
1. КОДЫ ФИБОНАЧЧИ
1.1 ЗОЛОТЫЕ ПРОПОРЦИИ
В математике существует большое количество иррациональных (несоизмеримых) чисел, т. е. обозначающих длину отрезка несоизмеримого с единицей масштаба. Ряд из них широко используется как в математике, так и в др. областях.
Например: Число p = 2pR/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 число j0(n) совпадает с двоичными разрядами 2n (табл. 1).
Таблица 1
| n | 0 | 1 | 2 | 3 | 4 | 5 |
| j0(n) | 1 | 2 | 4 | 8 | 16 | 32 |
При р = 1 число j0(n) совпадает с обычным рядом Фибоначчи:
1, 1, 2, 3, 5, 8, ...
При р = 
число j0(n) = 1 для любого n ³ 0 равно:
1, 1, 1, 1, 1, 1, 1, 1, ...
1.3 КОДЫ ФИБОНАЧЧИ
Любое натуральное число N можно представить с помощью p-чисел Фибоначчи
(4)где: ai Î{0, 1} - двоичная цифра i-го разряда; jp(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. j1(n)+j1(n)=j1(n)+j1(n-1)+j1(n-2) т. е. равно 1 и перенос 1 в два младших разряда.
2. j1(n)+j1(n)=j1(n+1)+j1(n-2) т. е. равно 0 и перенос 1 в два разряда - предыдущий и последующий.
Коды Фибоначчи обладают рядом полезных свойств (например, избыточность и т. д.), позволяющих строить быстродействующие и помехоустойчивые АЦП (“фибоначчевые” АЦП), реализующих специальные алгоритмы преобразования. Коды Фибоначчи используются для диагностики ЭВМ, в цифровых фильтрах для улучшения спектрального состава сигнала за счет перекодировки и др. областях.
2. ДВОИЧНЫЙ ОТРАЖЕННЫЙ КОД. КОД ГРЕЯ
Код Грея отличается от двоичного кода тем, что при переходе к следующей кодовой комбинации изменяется только один элемент кодовой комбинации (табл. 3).
Если при передаче сообщений с помощью кода Грея одновременно изменяется несколько разрядов кода, то это свидетельствует об ошибке, в этом состоит обнаруживающая способность кода Грея.
Код Грея, не взвешенный и непригоден для вычислительных операций без предварительного перевода в двоичный код.
| Число | Дв. Код | Код Грея |
  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 | 0000000100110010 |
| 0110011101010100 | ||
| 1100110111111110 | ||
| 1010101110011000 |
Схема кодера Грея приведена на рис. 2. Как видно из кодер Грея реализуется с помощью регистра RG, сдвигового регистра SRG и сумматора по модулю 2 SM2.
Правила перехода из кода Грея в двоичный код. Существует несколько способов перехода.
1. Используется следующий алгоритм:
an-1 = bn-1;
ai = ai+1 
bi .
где an-1- значение старшего разряда двоичного числа.
 |
Пример 1. Дана запись числа кодом Грея bi= 10101 ®b4 b3 b2 b1 b0получить двоичную запись. Используя приведенные выше формулы, получим
a4 = b4= 1 ;
a3 = a4 b3=1
0 = 1;