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

Реферат

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

Тема:

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

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.

При этом x²–x–1 = 0. Корни этого уравнения равны: x_1,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 число ₀(n) совпадает с двоичными разрядами 2ⁿ (табл. 1) .

Таблица 1

При р = 1 число ₀(n) совпадает с обычным рядом Фибоначчи:

1, 1, 2, 3, 5, 8, ...

При р = число ₀(n) = 1 для любого n  0 равно:

1, 1, 1, 1, 1, 1, 1, 1, ...

1.3 КОДЫ ФИБОНАЧЧИ

Любое натуральное число N можно представить с помощью p-чисел Фибоначчи

(4)

где: a_{i }{0, 1} - двоичная цифра i-го разряда; _p(i) - вес i-го разряда;

Любое натуральное число N можно представить также следующим способом:

(5)

Такое представление чисел N называется p-кодом Фибоначчи. Каждому p _{0, 1, 2, …, } соответствует свой код, т. е. их число бесконечно.

При p = 0 p -код Фибоначчи совпадает с двоичным кодом.

Для 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)+ ₁(n)= ₁(n)+ ₁(n-1)+ ₁(n-2) т. е. равно 1 и перенос 1 в два младших разряда.

2. ₁(n)+ ₁(n)= ₁(n+1)+ ₁(n-2) т. е. равно 0 и перенос 1 в два разряда - предыдущий и последующий.

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

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

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

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

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

Таблица 3

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

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

b_i =a_i a_i+1

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

Пример:

1) a_i = 1 1 1 0 1

1 1 1 0 1

b_i = 1 0 0 1 1

2) a_i = 1 1 1 1

1 1 1 1

b_i = 1 0 0 0

Схема кодера Грея приведена на рис. 2. Как видно из кодер Грея реализуется с помощью регистра RG, сдвигового регистра SRG и сумматора по модулю 2 SM2.

Правила перехода из кода Грея в двоичный код. Существует несколько способов перехода.

1. Используется следующий алгоритм:

a_n-1 = b_n-1;

a_i = a_i+1 b_i .

где a_n-1 - значение старшего разряда двоичного числа.

a_i b_i

n n n n

n

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

RG

SRG

SM2

Пример 1. Дана запись числа кодом Грея b_i = 10101  b₄ b₃ b₂ b₁ b₀ получить двоичную запись. Используя приведенные выше формулы, получим

a₄ = b₄ = 1 ;

a₃ = a₄ b₃ =1 0 = 1;

a₂ = a₃ b₂ =1 1 = 0;

a₁ = a₂ b₁ =0 0 = 0;

a₀ = a₁ b₀ =0 1 = 1;

a_i = a₄ a₃ a₂ a₁ a₀ = 11001

2. Переход осуществляется по алгоритму a_i = - т. е. как сумма по модулю 2 всех предыдущих значений

Пример 2. Дана запись числа кодом Грея b_i = 11001. При этом двоичная запись равна a_i = 10101;

Правила перехода из двоичного кода и кода Грея к десятичной записи

Для двоичного кода:

Для кода Грея:

для нечетных “1” знак “+”, для четных “1” знак “-”.

Пример 3. Дана запись числа двоичным кодом a_i = .

При этом десятичная запись равна

a₁₀ = 12⁵ + 12⁴ + 12² +12¹ = 32+16+4+2 = 54.

Пример 4. Дана запись числа двоичным кодом a_i =110110. Получить код Грея и преобразовать его в десятичную запись.

Получим код Грея

a_i = 1 0 1 1 0

1 1 0 1 1 0

b_i = 1 0 1 1 0 1.

Получим десятичную запись

b₁₀ = 1(2⁶-1)- 1(2⁴-1)+ 1(2³-1)- 1(2¹ -1) = 63-15+7-1=54.

Достоинство кода Грея: Простота перевода в двоичный код и обратно, а также к десятичной записи.

Применение кода Грея: Код Грея, чаще всего, используется для надежного перехода от аналогового представления информации к цифровой и обратно, т. е. в аналого-цифровых преобразователях (АЦП).

Список Литературы

1. Вернер М. Основы кодирования. — М.: Техносфера, 2004.

2. Зюко А.Г. , Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. –368 с.

3. Кнут Дональд, Грэхем Роналд, Паташник Орен Конкретная математика. Основание информатики — М.: Мир; Бином. Лаборатория знаний, 2006. — С. 703.

4. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002. – 120с.

5. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И. Халкин, Е.В. Федоров и др. – М.: Высшая школа, 2001 г. – 383с.

6. Рудаков А. Н. Числа Фибоначчи и простота числа 2¹²⁷-1 // Математическое Просвещение, третья серия. — 2000. — Т. 4.

7. Стахов А.П. Коды золотой пропорции. –М.: Радио и Связь, 1984.

8. Цапенко М.П. Измерительные информационные системы. - . – М.: Энергоатом издат, 2005. - 440с.