Коды Фибоначи. Коды Грея
1
Реферат
по курсу “Теория информации и кодирования ”
Тема:
"СПЕЦИАЛЬНЫЕ КОДЫ"
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При
р = 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 | |
|
2
Как видно из таблицы 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(n)+ 1(n)= 1(n)+ 1(n-1)+ 1(n-2) т. е. равно 1 и перенос 1 в два младших разряда.
1(n)+ 1(n)= 1(n+1)+ 1(n-2) т. е. равно 0 и перенос 1 в два разряда - предыдущий и последующий.Коды Фибоначчи обладают рядом полезных свойств (например, избыточность и т. д.), позволяющих строить быстродействующие и помехоустойчивые АЦП (“фибоначчевые” АЦП), реализующих специальные алгоритмы преобразования. Коды Фибоначчи используются для диагностики ЭВМ, в цифровых фильтрах для улучшения спектрального состава сигнала за счет перекодировки и др. областях.
2. ДВОИЧНЫЙ ОТРАЖЕННЫЙ КОД. КОД ГРЕЯ
Код Грея отличается от двоичного кода тем, что при переходе к следующей кодовой комбинации изменяется только один элемент кодовой комбинации (табл. 3). Если при передаче сообщений с помощью кода Грея одновременно изменяется несколько разрядов кода, то это свидетельствует об ошибке, в этом состоит обнаруживающая способность кода Грея.
Код Грея, не взвешенный и непригоден для вычислительных операций без предварительного перевода в двоичный код.
Таблица 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 | 0000 0001 0011 0010 | |
| | 0110 0111 0101 0100 | |
| | 1100 1101 1111 1110 | |
| | 1010 1011 1001 1000 | |
|
Схема кодера Грея приведена на рис. 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;
a2 = a3 b2 =1 1 = 0;
a1 = a2 b1 =0 0 = 0;
a0 = a1 b0 =0 1 = 1;
ai = a4 a3 a2 a1 a0 = 11001
2. Переход осуществляется по алгоритму ai = - т. е. как сумма по модулю 2 всех предыдущих значений
Пример 2. Дана запись числа кодом Грея bi = 11001. При этом двоичная запись равна ai = 10101;
Правила перехода из двоичного кода и кода Грея к десятичной записи
Для двоичного кода:
Для кода Грея:
для нечетных “1” знак “+”, для четных “1” знак “-”.
Пример 3. Дана запись числа двоичным кодом ai = .
При этом десятичная запись равна
a10 = 125 + 124 + 122 +121 = 32+16+4+2 = 54.
Пример 4. Дана запись числа двоичным кодом ai =110110. Получить код Грея и преобразовать его в десятичную запись.
Получим код Грея
ai = 1 0 1 1 0
1 1 0 1 1 0
bi = 1 0 1 1 0 1.
Получим десятичную запись
b10 = 1(26-1)- 1(24-1)+ 1(23-1)- 1(21 -1) = 63-15+7-1=54.
Достоинство кода Грея: Простота перевода в двоичный код и обратно, а также к десятичной записи.
Применение кода Грея: Код Грея, чаще всего, используется для надежного перехода от аналогового представления информации к цифровой и обратно, т. е. в аналого-цифровых преобразователях (АЦП).
Список Литературы
1. Вернер М. Основы кодирования. -- М.: Техносфера, 2004.
2. Зюко А.Г. , Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. -368 с.
3. Кнут Дональд, Грэхем Роналд, Паташник Орен Конкретная математика. Основание информатики -- М.: Мир; Бином. Лаборатория знаний, 2006. -- С. 703.
4. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002. - 120с.
5. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И. Халкин, Е.В. Федоров и др. - М.: Высшая школа, 2001 г. - 383с.
6. Рудаков А. Н. Числа Фибоначчи и простота числа 2127-1 // Математическое Просвещение, третья серия. -- 2000. -- Т. 4.
7. Стахов А.П. Коды золотой пропорции. -М.: Радио и Связь, 1984.
8. Цапенко М.П. Измерительные информационные системы. - . - М.: Энергоатом издат, 2005. - 440с.