47377 (Коды Фибоначи. Коды Грея), страница 2

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

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

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

Т

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

аблица 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. Используется следующий алгоритм:

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