Коды Грея — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 42: Строка 42:
  
 
Существует несколько видов Кода Грея, самый простой из них {{---}} так называемый зеркальный двоичный Код Грея, строится он так:  
 
Существует несколько видов Кода Грея, самый простой из них {{---}} так называемый зеркальный двоичный Код Грея, строится он так:  
Для получения кода длины n производится n шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй - "1". С каждым шагом длина векторов увеличивается на 1, и их количество вдвое.  
+
Для получения кода длины <tex>n</tex> производится <tex>n</tex> шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй - "1". С каждым шагом длина векторов увеличивается на 1, и их количество вдвое.  
 
Таким образом, количество векторов длины <tex>n</tex> равно <tex>2^n.</tex>
 
Таким образом, количество векторов длины <tex>n</tex> равно <tex>2^n.</tex>
  
Строка 50: Строка 50:
  
 
* на первом шаге код отвечает условиям  
 
* на первом шаге код отвечает условиям  
* предположим, что получившийся код на шаге i есть Код Грея
+
* предположим, что получившийся код на шаге <tex>i</tex> есть Код Грея
* тогда на шаге i+1: первая половина кода будет корректна, так как она совпадает с кодом с шага i за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит 1. На стыке: первые i бит совпадают в силу зеркальности, последние различны по построению.  
+
* тогда на шаге <tex>i + 1</tex>: первая половина кода будет корректна, так как она совпадает с кодом с шага <tex>i</tex> за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит 1. На стыке: первые <tex>i</tex> бит совпадают в силу зеркальности, последние различны по построению.  
 
Таким образом, этот код {{---}} Код Грея. Индукционное предположение доказано, алгоритм работает верно.  
 
Таким образом, этот код {{---}} Код Грея. Индукционное предположение доказано, алгоритм работает верно.  
  
  
Этот алгоритм можно обобщить и для k-ичных векторов. Также известен алгоритм преобразования двоичного кода в Код Грея.  
+
Этот алгоритм можно обобщить и для <tex>k</tex>-ичных векторов. Также известен алгоритм преобразования двоичного кода в Код Грея.  
  
 
Существует ещё несколько видов Кода Грея {{---}} сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея.
 
Существует ещё несколько видов Кода Грея {{---}} сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея.

Версия 05:42, 27 октября 2011

2-битный код Грея
00
01
11
10
3-битный код Грея
000
001
011
010
110
111
101
100
4-битный код Грея
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

Код Грея - такое упорядочение [math]k[/math]-ичных (обычно двоичных) векторов, что соседние вектора отличаются только в одном разряде. Код назван в честь Фрэнка Грея, который в 1947 году получил патент на "отраженный двоичный код". Изначально он предназначался для избавления от паразитных состояний в электромеханических переключателях, однако сейчас область его применения гораздо шире.


Алгоритм построения

Существует несколько видов Кода Грея, самый простой из них — так называемый зеркальный двоичный Код Грея, строится он так: Для получения кода длины [math]n[/math] производится [math]n[/math] шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй - "1". С каждым шагом длина векторов увеличивается на 1, и их количество вдвое. Таким образом, количество векторов длины [math]n[/math] равно [math]2^n.[/math]

Доказательство правильности работы алгоритма

По индукции:

  • на первом шаге код отвечает условиям
  • предположим, что получившийся код на шаге [math]i[/math] есть Код Грея
  • тогда на шаге [math]i + 1[/math]: первая половина кода будет корректна, так как она совпадает с кодом с шага [math]i[/math] за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит 1. На стыке: первые [math]i[/math] бит совпадают в силу зеркальности, последние различны по построению.

Таким образом, этот код — Код Грея. Индукционное предположение доказано, алгоритм работает верно.


Этот алгоритм можно обобщить и для [math]k[/math]-ичных векторов. Также известен алгоритм преобразования двоичного кода в Код Грея.

Существует ещё несколько видов Кода Грея — сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея.


Применение

Код Грея применяется в:

  • датчиках-энкодерах ( устройства, преобразующие угол поворота вала в электрический сигнал );
  • как способ решения задачи о Ханойских башнях ( дано три стержня, на первом из них нанизано 8 колец разного размера в виде пирамиды; цель — перенести

пирамиду на другой стержень, сохранив упорядоченность );

  • в генетических алгоритмах;
  • в Картах Карно ( при передаче в карту переменные сортируются в Код Грея );
  • в кодах, исправляющих ошибки;
  • для связи систем с различной частотой работы.


Источники