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

Реферат

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

Тема:

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

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

 

ЗОЛОТЫЕ ПРОПОРЦИИ

 

В математике существует большое количество иррациональных (несоизмеримых) чисел, т. е. обозначающих длину отрезка несоизмеримого с единицей масштаба. Ряд из них широко используется как в математике, так и в др. областях.

Например: Число p = 2pR/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.

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

Таблица 1

n
j0(n)

 

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

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

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

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

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

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

 

(4)

 

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

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

(5)

 

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

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

Для 1-кода Фибоначчи кодовые комбинации имеют вид:

 

Таблица 2

 

N	KK	Вес порядка
	A0
	A1
	A2
	A3
	A4
	A5
	A6
	A7
	A8
	A9
	A10
	A11
	A12
	A13
	А14
	А15

 

N	KK	Вес порядка
	A16
	A17
	А18
	A19
	A20
	A21
	A22
	A23
	A24
	A25
	A26
	A27
	A28
	A29
	A30
	А31

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

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

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

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

 

Код Грея отличается от двоичного кода тем, что при переходе к следующей кодовой комбинации изменяется только один элемент кодовой комбинации (табл. 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

 

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

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

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

 

a_n-1 = b_n-1;

a_i = a_i+1 b_i.

 

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

 

 

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