Реферат
по
курсу “Теория информации и кодирования ”
Тема:
"
СПЕЦИАЛЬНЫЕ КОДЫ
"
1. КОДЫ ФИБОНАЧЧИ
1.1 ЗОЛОТЫЕ ПРОПОРЦИИ
В математике существует большое количество иррациональных (несоизмеримых) чисел, т. е. обозначающих длину отрезка несоизмеримого с единицей масштаба. Ряд из них широко используется как в математике, так и в др. областях.
Например: Число 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 в два разряда - предыдущий и последующий.
Коды Фибоначчи обладают рядом полезных свойств (например, избыточность и т. д.), позволяющих строить быстродействующие и помехоустойчивые АЦП (“фибоначчевые” АЦП), реализующих специальные алгоритмы преобразования. Коды Фибоначчи используются для диагностики ЭВМ, в цифровых фильтрах для улучшения спектрального состава сигнала за счет перекодировки и др. областях.
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
= 1×25
+ 1×24
+ 1×22
+1×21
= 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с.