ДВОИЧНЫЙ ОТРАЖЕННЫЙ КОД. КОД ГРЕЯ
Реферат по курсу “Теория информации и кодирования ” Тема: " СПЕЦИАЛЬНЫЕ КОДЫ " КОДЫ ФИБОНАЧЧИ
ЗОЛОТЫЕ ПРОПОРЦИИ
В математике существует большое количество иррациональных (несоизмеримых) чисел, т. е. обозначающих длину отрезка несоизмеримого с единицей масштаба. Ряд из них широко используется как в математике, так и в др. областях. Например: Число 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... использовалась в архитектуре, художественных произведениях, музыке с античных времен. С этим числом связан ореол мистики, таинственности, божества и т.д. В последнее десятилетие эта пропорция нашла свое применение в ЭВМ, АЦП-ЦАП, измерениях и т. д.
ЧИСЛА ФИБОНАЧЧИ
С золотым сечением тесно связаны числа Фибоначчи открытые итальянским математиком Леонардо из Пизы (Фибоначчи) в 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
При р = 1 число j 0 (n) совпадает с обычным рядом Фибоначчи: 1, 1, 2, 3, 5, 8, ... При р = число j 0 (n) = 1 для любого n ³ 0 равно: 1, 1, 1, 1, 1, 1, 1, 1, ... КОДЫ ФИБОНАЧЧИ Любое натуральное число N можно представить с помощью p-чисел Фибоначчи
(4)
где: ai Î{0, 1} - двоичная цифра i-го разряда; j 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. 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 в два разряда - предыдущий и последующий. Коды Фибоначчи обладают рядом полезных свойств (например, избыточность и т. д.), позволяющих строить быстродействующие и помехоустойчивые АЦП (“фибоначчевые” АЦП), реализующих специальные алгоритмы преобразования. Коды Фибоначчи используются для диагностики ЭВМ, в цифровых фильтрах для улучшения спектрального состава сигнала за счет перекодировки и др. областях. ДВОИЧНЫЙ ОТРАЖЕННЫЙ КОД. КОД ГРЕЯ
Код Грея отличается от двоичного кода тем, что при переходе к следующей кодовой комбинации изменяется только один элемент кодовой комбинации (табл. 3). Если при передаче сообщений с помощью кода Грея одновременно изменяется несколько разрядов кода, то это свидетельствует об ошибке, в этом состоит обнаруживающая способность кода Грея. Код Грея, не взвешенный и непригоден для вычислительных операций без предварительного перевода в двоичный код.
Схема кодера Грея приведена на рис. 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;
Популярное: Почему стероиды повышают давление?: Основных причин три... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (190)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |