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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Дополнение)
(Правка 3)
Строка 1: Строка 1:
'''Код Грея''' - такое упорядочение k-ичных (обычно двоичных) векторов, что соседние вектора отличалются только в одном разряде.
+
'''Код Грея''' - такое упорядочение k-ичных (обычно двоичных) векторов, что соседние вектора отличаются только в одном разряде.  
Код назван в честь Френка Грея, который в 1947 году получил патент на "отраженный двоичный код". Изначально он предназначался для избавления от паразитных состояний в электромеханических переключателях, однако сейчас область его применения гораздо шире.
+
Код назван в честь Фрэнка Грея, который в 1947 году получил патент на "отраженный двоичный код". Изначально он предназначался для избавления от паразитных состояний в электромеханических переключателях, однако сейчас область его применения гораздо шире.  
  
== Алгоритм построения ==
 
  
Существует несколько видов Кода Грея, самый простой из них - так называемый зеркальный двоичный Код Грея, строится он так:
+
== Алгоритм построения ==
Для получения кода длины n производится n шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй - "1". Таким образом с каждым шагом длина векторов увеличивается на 1, и их количество вдвое.
 
Таким образом количество векторов длины n равно <math>2^n</math>.
 
  
'''Доказательсво правильности работы алгоритма'''
+
Существует несколько видов Кода Грея, самый простой из них - так называемый зеркальный двоичный Код Грея, строится он так:
 +
Для получения кода длины n производится n шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй - "1". С каждым шагом длина векторов увеличивается на 1, и их количество вдвое.
 +
Таким образом количество векторов длины n равно <math>2^n.</math>
  
По индукции:
+
'''Доказательство правильности работы алгоритма'''
  
-на первом шаге код отвечеат условиям
+
По индукции:
  
-предположим, что получившийся код на шаге i есть Код Грея
+
-на первом шаге код отвечает условиям
  
-тогда на шаге i+1: первая половина кода будет корректна, так как она совпадает с кодом с шага i за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она явлеятся зеракальным отражением первой половины, только добавлена везде 1. На стыке: i бит совпадают в силу зеркальности, отличается последний.
+
-предположим, что получившийся код на шаге i есть Код Грея  
Таким образом этот код - Код Грея. Индукционное предположение доказанно, алгоритм работает верно.
 
  
Этот алгоритм можно обобщить и для k-ичных векторов.
+
-тогда на шаге i+1: первая половина кода будет корректна, так как она совпадает с кодом с шага i за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит 1. На стыке: первые i бит совпадают в силу зеркальности, последние различны по построению.
Сущестует ещё несколько видов Кода Грея - сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея.
+
Таким образом этот код - Код Грея. Индукционное предположение доказано, алгоритм работает верно.
 +
 
 +
 
 +
Этот алгоритм можно обобщить и для k-ичных векторов. Также известен алгоритм преобразования двоичного кода в Код Грея.
 +
 
 +
Существует ещё несколько видов Кода Грея - сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея.
 +
 
 +
 
 +
== Применение ==
 +
 
 +
Код Грея применяется в:
 +
 
 +
-датчиках-энкодерах ( устройства, преобразующие угол поворота вала в электрический сигнал );
 +
 
 +
-как способ решения задачи о Ханойских башнях ( дано три стержня, на первом из них нанизано 8 колец разного размера в виде пирамиды; цель - перенести
 +
 
 +
пирамиду на другой стержень, сохранив упорядоченность );
 +
 
 +
-в генетических алгоритмах;
 +
 
 +
-в Картах Карно ( при передаче в карту переменные сортируются в Код Грея );
 +
 
 +
-в кодах, исправляющих ошибки;
 +
 
 +
-для связи систем с различной частотой работы.
 +
 
 +
 
 +
 
 +
== Источники ==
 +
 
 +
[http://en.wikipedia.org/wiki/Gray_code] Gray code, From Wikipedia, the free encyclopedia
 +
 
 +
[http://ru.wikipedia.org/wiki/Код_Грея] Код Грея, Материал из Википедии — свободной энциклопедии

Версия 05:57, 12 ноября 2010

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


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

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

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

По индукции:

-на первом шаге код отвечает условиям

-предположим, что получившийся код на шаге i есть Код Грея

-тогда на шаге i+1: первая половина кода будет корректна, так как она совпадает с кодом с шага i за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит 1. На стыке: первые i бит совпадают в силу зеркальности, последние различны по построению. Таким образом этот код - Код Грея. Индукционное предположение доказано, алгоритм работает верно.


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

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


Применение

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

-датчиках-энкодерах ( устройства, преобразующие угол поворота вала в электрический сигнал );

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

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

-в генетических алгоритмах;

-в Картах Карно ( при передаче в карту переменные сортируются в Код Грея );

-в кодах, исправляющих ошибки;

-для связи систем с различной частотой работы.


Источники

[1] Gray code, From Wikipedia, the free encyclopedia

[2] Код Грея, Материал из Википедии — свободной энциклопедии