Код Грея
Материал из Википедии — свободной энциклопедии
|
Код Грея, рефлексный двоичный код — двоичная система нумерования, в которой два соседних значения различаются только в одном двоичном разряде.
Изначально предназначался для защиты от ложного срабатывания электромеханических переключателей. Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи а также в формировании сигналов обратной связи в системах управления.
Содержание |
[править] Название
Название рефлексный (отражённый) двоичный код происходит от факта, что вторая половина значений в коде Грея эквивалентна первой половине, только в обратном порядке, за исключением старшего бита, который просто инвертируется. Если же разделить каждую половину ещё раз пополам, свойство будет сохраняться для каждой из половин половины и т. д.
Код получил имя исследователя лабораторий Bell Labs Фрэнка Грея. Он использовал этот код в своей импульсной системе связи, для чего был написан патент за номером 2632058.
[править] Применения
Использование кодов Грея основано прежде всего на том, что он минимизирует эффект ошибок при преобразовании аналоговых сигналов в цифровые (например, во многих видах датчиков).
Коды Грея часто используются в датчиках-энкодерах [1]. Их использование удобно тем, что два соседних значения шкалы сигнала отличаются только в одном разряде. Также они используются для кодирования номера дорожек в жёстких дисках.
Код Грея можно использовать также и для решения задачи о Ханойских башнях [2].
Широко применяются коды Грея и в теории генетических алгоритмов [3] для кодирования генетических признаков, представленных целыми числами.
[править] Алгоритмы преобразования
Ниже представлен один из алгоритмов создания последовательности кода Грея заданной глубины, записанный на языке Perl:
my $depth = 16; # generate 16 Gray codes, 4 bits wide each
my @gray_codes = ( '0', '1' );
while(scalar(@gray_codes)<$depth)
{
my @forward_half=map{'0'.$_} @gray_codes;
my @reverse_half=map{'1'.$_} reverse(@gray_codes);
@gray_codes=(@forward_half,@reverse_half);
}
Алгоритм преобразования из двоичной системы счисления в код Грея, записанный на языке C:
unsigned int grayencode(unsigned int g) {
return g ^ (g >> 1);
}
обратный алгоритм (преобразование из кода Грея в двоичную систему счисления):
unsigned int graydecode(unsigned int gray) {
unsigned int bin;
for (bin = 0; gray; gray >>= 1) {
bin ^= gray;
}
return bin;
}
[править] См. также
- Код Хэмминга
[править] Примечания
- ↑ http://www.radioradar.net/staty/encoder.php
- ↑ http://occawlonline.pearsoned.com/bookbind/pubbooks/miller2_awl/chapter4/essay1/deluxe-content.html
- ↑ http://www.basegroup.ru/genetic/math_print.htm
[править] Библиография
- Black, Paul E. Gray code. 25 февраля 2004. NIST. [1] (англ.).
