Referat.me

Название: Коды Фибоначи Коды Грея

Вид работы: реферат

Рубрика: Информатика

Размер файла: 70.96 Kb

Скачать файл: referat.me-129860.docx

Краткое описание работы: Реферат по курсу “Теория информации и кодирования ” Тема: "СПЕЦИАЛЬНЫЕ КОДЫ" 1. КОДЫ ФИБОНАЧЧИ 1.1 ЗОЛОТЫЕ ПРОПОРЦИИ В математике существует большое количество иррациональных (несоизмеримых) чисел, т. е. обозначающих длину отрезка несоизмеримого с единицей масштаба. Ряд из них широко используется как в математике, так и в др. областях.

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

Реферат

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

Тема:

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

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).

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

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

Если обозначить: 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

Таблица 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с.

Похожие работы

  • Примеры выполнения заданий по программированию

    1. Переведите данное число из десятичной системы счисления в двоично-десятичную. В двоично-десятичном представлении каждая цифра числа кодируется по

  • Интерполяция 3

    Интерполяция Интерполя́ция интерполи́рование вычислительной математике способ нахождения промежуточных значений величины по имеющемуся

  • Кодирование текстовой информации

    Кодирование текстовой информации Начиная с конца 60-х годов, компьютеры все больше стали использоваться для обработки текстовой информации, и в настоящее время основная доля персональных компьютеров в мире (и большая часть времени) занята обработкой именно текстовой информации. Современный компьютер может обрабатывать числовую, текстовую, графическую, звуковую и видео информацию.

  • Лабораторные работы по программированию

    Лабораторная работа №1. Тема: Обучение работе на УМК. Цель: Научиться работать на УМК. Приборы: Учебный микропроцессорный комплекс (УМК). Ход работы.

  • Аналого цифровое и цифро аналоговое преобразование сигналов

    Курс: Теория информации и кодирования Тема: АНАЛОГО-ЦИФРОВОЕ И ЦИФРО-АНАЛОГОВОЕ ПРЕОБРАЗОВАНИЕ СИГНАЛОВ СОДЕРЖАНИЕ ВВЕДЕНИЕ ХАРАКТЕРИСТИКИ ПРЕОБРАЗОВАТЕЛЕЙ

  • Циклические коды понятие и сущность

    Задание Рассматривается циклический код (7,4) для исправления однократной ошибки. Заданы: а(х) – информационная часть передаваемой кодовой комбинации,

  • Лабораторная работа по Информатике

    Лабораторная работа № 1.1 Цель работы Научиться измерять информацию, решать задачи на определение количества и объема информации. Ход работы Задание № 1

  • Кодирование технико-экономической информации

    ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 1 (3) КОДИРОВАНИЕ ТЕХНИКО-ЭКОНОМИЧЕСКОЙ ИНФОРМАЦИИ Цель занятия: научиться составлять коды различных объектов стандартизации по классификаторам ЕСКД, ОКП, ОКОНХ, ОКПДТР

  • Кодирование информации Код Рида-Малера

    Министерство образования и науки Украины ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к курсовому проекту на тему "Кодирование информации. Код Рида-Малера " по курсу "Кодирование и защита информации"

  • Математическая теория информации

    Механизм передачи информации, ее количество и критерии измерения. Единицы информации в зависимости от основания логарифма. Основные свойства и характеристики количества информации, ее энтропия. Определение энтропии, избыточности информационных сообщений.