Изменения

[[Файл:PCM_Tube.png|500px|thumb|center|Часть первой страницы патента Грея, показывающая PCM трубку с отраженным двоичным кодом в тарелке.]]* В технике коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов в цифровые (например, в [http://ru.wikipedia.org/wiki/%D0%AD%D0%BD%D0%BA%D0%BE%D0%B4%D0%B5%D1%80 датчиках-энкодерах]).  В частности, коды Грея и были открыты в связи с этим применением. (Код Грея — это код преобразования бинарных символов в <tex>M</tex>-арные, такие, что двоичные последовательности, соответствующие соседним символам (сдвигам фаз), отличаются только одним битом. Обычная бинарная кодировка сравнивается с кодировкой Грея. При появлении ошибки в <tex>M</tex>-арном символе наиболее вероятными являются ближайшие соседние символы, отличающиеся от переданного лишь одним битом, если используется кодировка Грея.  Таким образом, высока вероятность того, что при кодировании с помощью кода Грея в случае возникновения ошибки ошибочным будет только один из <tex>k = \log_2 M</tex> переданных битов.)  

 * Коды Грея широко применяются в теории [http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC генетических алгоритмов] для кодирования генетических признаков, представленных целыми числами. * Коды Грея используются в [http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%80%D1%82%D1%8B_%D0%9A%D0%B0%D1%80%D0%BD%D0%BE Картах Карно] (при передаче в карту переменные сортируются в код Грея). * Алгоритм модуляции 2B1Q (англ. ''2 Binary 1 Quandary'') <ref>[http://en.wikipedia.org/wiki/2B1Q Описание 2B1Q кода в английской Википедии]</ref> * Код Грея можно использовать также и для решения задачи о [http://ru.wikipedia.org/wiki/%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%B8%D0%B5_%D0%B1%D0%B0%D1%88%D0%BD%D0%B8 следующей задачи]: === Задача о Ханойских башнях]: === 

Пусть <tex>n</tex> — количество дисков. Начнём с кода Грея длины <tex>n</tex>Даны три стержня, состоящего на один из одних нулей (т.е. <tex>G(0)</tex>)которых нанизаны восемь колец, причем кольца отличаются размером и будем двигаться по кодам Грея (от <tex>G(i)</tex> переходить к <tex>G(i+1)</tex>)лежат меньшее на большем. Поставим Задача состоит в соответствие каждому <tex>i</tex>-ому биту текущего кода Грея <tex>i</tex>-ый диск (причём самому младшему биту соответствует наименьший по размеру дисктом, а самому старшему биту — наибольший)чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. Поскольку на каждом шаге изменяется ровно За один бит, то мы можем понимать изменение бита <tex>i</tex> как перемещение <tex>i</tex>-го диска. Заметим, что для всех дисков, кроме наименьшегораз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если <tex>n</tex> нечётно, то последовательность перемещений наименьшего диска имеет вид <tex>f \rightarrow t \rightarrow r \rightarrow f \rightarrow t \rightarrow r \rightarrow \ldots .</tex>(где <tex>f</tex> — стартовый стержень, <tex>t</tex> — финальный стержень, <tex>r</tex> — оставшийся стержень), а если <tex>n</tex> чётно, то <tex>f \rightarrow r \rightarrow t \rightarrow f \rightarrow r \rightarrow t \rightarrow \ldotsменьшее.</tex>

* Коды Грея широко применяются в теории [http'''Решение:''' Пусть <tex>n</tex> — количество дисков. Начнём с кода Грея длины <tex>n</rutex>, состоящего из одних нулей (т.wikipediaе.org<tex>G(0)</tex>), и будем двигаться по кодам Грея (от <tex>G(i)</wikitex> переходить к <tex>G(i+1)</%D0%93%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC генетических алгоритмов] для кодирования генетических признаков, представленных целыми числамиtex>).* Коды Грея используются Поставим в [http:соответствие каждому <tex>i</tex>-ому биту текущего кода Грея <tex>i</rutex>-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший).wikipedia.orgПоскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита <tex>i</wikitex> как перемещение <tex>i</%D0%9A%D0%B0%D1%80%D1%82%D1%8B_%D0%9A%D0%B0%D1%80%D0%BD%D0%BE Картах Карно] tex>-го диска.  Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (при передаче в карту переменные сортируются в код Греяза исключением стартовой и финальной позиций).* Алгоритм модуляции 2B1Q Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если <tex>n</tex> нечётно, то последовательность перемещений наименьшего диска имеет вид <tex>f \rightarrow t \rightarrow r \rightarrow f \rightarrow t \rightarrow r \rightarrow \ldots .</tex>(англ. ''2 Binary 1 Quandary'') где <reftex>[http:f</tex> — стартовый стержень, <tex>t</en.wikipedia.orgtex> — финальный стержень, <tex>r</wikitex> — оставшийся стержень), а если <tex>n</2B1Q Описание 2B1Q кода в английской Википедии]tex> чётно, то <tex>f \rightarrow r \rightarrow t \rightarrow f \rightarrow r \rightarrow t \rightarrow \ldots.</reftex>