Реферат: Коды Фибоначи. Коды Грея - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

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

Банк рефератов / Информатика, информационные технологии

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 766 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!

Узнайте стоимость написания уникальной работы













Реферат

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


Тема:

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


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 в два разряда - предыдущий и последующий.

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


2. ДВОИЧНЫЙ ОТРАЖЕННЫЙ КОД. КОД ГРЕЯ


Код Грея отличается от двоичного кода тем, что при переходе к следующей кодовой комбинации изменяется только один элемент кодовой комбинации (табл. 3).

Если при передаче сообщений с помощью кода Грея одновременно изменяется несколько разрядов кода, то это свидетельствует об ошибке, в этом состоит обнаруживающая способность кода Грея.

Код Грея, не взвешенный и непригоден для вычислительных операций без предварительного перевода в двоичный код.


Таблица 3

Если обозначить: ai - двоичный код;

bi - Код Грея, то правило перехода из двоичного кода к коду Грея имеет вид:


bi =ai ai+1


где - суммирование по mod 2 ai+1 - ai - со сдвигом на один разряд вправо.


Пример:

1) ai = 1 1 1 0 1

1 1 1 0 1

bi = 1 0 0 1 1


2) ai = 1 1 1 1

1 1 1 1

bi = 1 0 0 0

Число

Дв. Код

Код Грея

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 - значение старшего разряда двоичного числа.


ai bi

n n n n



n



Рис.2. Схема кодера Грея


RG


SRG


SM2








Пример 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с.



1Авиация и космонавтика
2Архитектура и строительство
3Астрономия
 
4Безопасность жизнедеятельности
5Биология
 
6Военная кафедра, гражданская оборона
 
7География, экономическая география
8Геология и геодезия
9Государственное регулирование и налоги
 
10Естествознание
 
11Журналистика
 
12Законодательство и право
13Адвокатура
14Административное право
15Арбитражное процессуальное право
16Банковское право
17Государство и право
18Гражданское право и процесс
19Жилищное право
20Законодательство зарубежных стран
21Земельное право
22Конституционное право
23Конституционное право зарубежных стран
24Международное право
25Муниципальное право
26Налоговое право
27Римское право
28Семейное право
29Таможенное право
30Трудовое право
31Уголовное право и процесс
32Финансовое право
33Хозяйственное право
34Экологическое право
35Юриспруденция
36Иностранные языки
37Информатика, информационные технологии
38Базы данных
39Компьютерные сети
40Программирование
41Искусство и культура
42Краеведение
43Культурология
44Музыка
45История
46Биографии
47Историческая личность
 
48Литература
 
49Маркетинг и реклама
50Математика
51Медицина и здоровье
52Менеджмент
53Антикризисное управление
54Делопроизводство и документооборот
55Логистика
 
56Педагогика
57Политология
58Правоохранительные органы
59Криминалистика и криминология
60Прочее
61Психология
62Юридическая психология
 
63Радиоэлектроника
64Религия
 
65Сельское хозяйство и землепользование
66Социология
67Страхование
 
68Технологии
69Материаловедение
70Машиностроение
71Металлургия
72Транспорт
73Туризм
 
74Физика
75Физкультура и спорт
76Философия
 
77Химия
 
78Экология, охрана природы
79Экономика и финансы
80Анализ хозяйственной деятельности
81Банковское дело и кредитование
82Биржевое дело
83Бухгалтерский учет и аудит
84История экономических учений
85Международные отношения
86Предпринимательство, бизнес, микроэкономика
87Финансы
88Ценные бумаги и фондовый рынок
89Экономика предприятия
90Экономико-математическое моделирование
91Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Говорят, что учитель – это профессия от Бога.
Жаль только, что зарплата от государства...
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по информатике и информационным технологиям "Коды Фибоначи. Коды Грея", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2017
Рейтинг@Mail.ru