Вики-разметка

[gromak94]

Есть кто-нибудь, кто шарит в сабже?

Писал конспект, всё было ок, а потом посмотрел на узком мониторе, там провал.

Суть проблемы: если определение не влезает по ширине, то оно уползает куда-то очень далеко. Есть какие-то примитивные способы побороть такую проблему?

UPD: Уже и не нужно.

[t456ak]

наркотики

[gromak94]

Пфф, опять этот баг с мультитемами.

Кстати, там ещё в доказательстве какой-то рак. Если знаете, как исправить, прошу помочь.

[Vespirka]

 

 

{| width="150" align="right" cellpadding="5" border="1" style="border-collapse: collapse;"

|-

| <span style="font-size:smaller;">2-битный код Грея</span>

00

01

11

10

|-

| <span style="font-size:smaller;">3-битный код Грея</span>

000

001

011

010

110

111

101

100

|-

| <span style="font-size:smaller;">4-битный код Грея</span>

0000

0001

0011

0010

0110

0111

0101

0100

1100

1101

1111

1110

1010

1011

1001

1000

|}

'''Код Грея''' — [[система счисления]], в которой два соседних значения различаются только в одном разряде. Наиболее часто на практике применяется '''рефлексный [[двоичный код]] Грея''', хотя в общем случае существует бесконечное множество кодов Грея для систем счисления с любым основанием. В большинстве случаев, под термином «код Грея» понимают именно рефлексивный бинарный код Грея.

 

 

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

 

 

== Название ==

Название ''рефлексный (отражённый) двоичный код'' происходит от факта, что вторая половина значений в коде Грея эквивалентна первой половине, только в обратном порядке, за исключением старшего бита, который просто инвертируется. Если же разделить каждую половину ещё раз пополам, свойство будет [[Самоподобие|сохраняться]] для каждой из половин половины и т. д.

 

 

Код получил имя исследователя лабораторий [[bell Labs]] [[Грей, Фрэнк|Фрэнка Грея]]. Он использовал этот код в своей импульсной системе связи, для чего был написан патент за номером 2632058.

 

 

== Применения ==

Использование кодов Грея основано прежде всего на том, что он минимизирует эффект ошибок при преобразовании аналоговых сигналов в цифровые (например, во многих видах датчиков).

 

 

[[Файл:US02632058 Gray.png|center|thumb|500px|Фрагмент главной страницы патента Грея]]

[[Файл:Encoder Disc (3-Bit).svg|thumb| Круговой энкодер с трёхбитным кодом грея]]

 

 

Коды Грея часто используются в датчиках-[[энкодер]]ах. Их использование удобно тем, что два соседних значения шкалы сигнала отличаются только в одном разряде. Также они используются для кодирования номера дорожек в [[жёсткий диск|жёстких дисках]].

 

 

Код Грея можно использовать также и для решения задачи о [[Ханойские башни|Ханойских башнях]] <!-- <ref>http://occawlonline.pearsoned.com/bookbind/pubbooks/miller2_awl/chapter4/essay1/deluxe-content.html</ref> Error 404 -->.

 

 

Широко применяются коды Грея и в [[генетический алгоритм|теории генетических алгоритмов]] <ref>[http://www.basegroup.ru/genetic/math_print.htm BaseGroup.ru :: Генетические алгоритмы — математический аппарат<!-- Заголовок добавлен ботом -->]</ref> для кодирования генетических признаков, представленных целыми числами.

 

 

Код Грея используется для генерации [[Сочетание|сочетаний]] [[метод вращающейся двери|методом вращающейся двери]]<ref>Кнут, Дональд, Э. Искусство программирования, том 4, выпуск 3: генерация всех сочетаний и разбиений (раздел 7.2.1.3): Пер. с англ. - М.: ООО "И.Д. Вильяме", 2007. - 208 с. : ил.]</ref>

 

 

== Алгоритмы преобразования ==

 

 

 

 

=== Преобразование двоичного кода в код Грея ===

 

 

Коды Грея легко получаются из двоичных чисел путём побитовой операции «Исключающее ИЛИ» с тем же числом, сдвинутым вправо на один бит. Следовательно, ''i''-й бит кода Грея ''G_i'' выражается через биты двоичного кода ''B_i'' следующим образом:

 

 

<center><math>~

G_i = B_i \oplus B_{i+1},

</math></center>

 

 

где <math> \oplus </math> – операция «исключающее ИЛИ»; биты нумеруются справа налево, начиная с младшего.

 

 

Ниже приведён алгоритм преобразования из [[двоичная система счисления|двоичной системы счисления]] в код Грея, записанный на языке [[Си (язык программирования)|C]]:

<source lang="C">

unsigned int grayencode(unsigned int g)

{

    return g ^ (g >> 1);

}

</source>

 

 

Тот же самый алгоритм, записанный на языке Паскаль:

 

 

<source lang="pascal">

function BinToGray(b:integer):integer;

begin

  BinToGray:=b xor (b shr 1)

end;

</source>

 

 

Пример: преобразовать двоичное число 10110 в код Грея.

 

 

10110

01011

-----

11101

 

 

=== Преобразование кода Грея в двоичный код ===

 

 

Обратный алгоритм – преобразование кода Грея в двоичный код – можно выразить рекуррентной формулой

 

 

<center><math>~

B_i = B_{i+1} \oplus G_i,

</math></center>

 

 

причём преобразование осуществляется побитно, начиная со старших разрядов, и значение <math>B_{i+1}</math>, используемое в формуле, вычисляется на предыдущем шаге алгоритма. Действительно, если подставить в эту формулу вышеприведённое выражение для

''i''-го бита кода Грея, получим

 

 

<center><math>~

B_i = B_{i+1} \oplus G_i = B_{i+1} \oplus (B_i \oplus B_{i+1}) = B_i \oplus (B_{i+1} \oplus B_{i+1}) = B_i \oplus 0 = B_i.

</math></center>

 

 

Однако приведённый алгоритм, связанный с манипуляцией отдельными битами, неудобен для программной реализации, поэтому на практике используют видоизменённый алгоритм:

 

 

<center><math>~

B_k = \bigoplus \limits^N_{i=k} G_i,

</math></center>

 

 

где ''N'' – число битов в коде Грея (для увеличения быстродействия алгоритма в качестве ''N'' можно взять номер старшего ненулевого бита кода Грея); знак <math> \oplus </math> означает суммирование при помощи операции «исключающее ИЛИ», то есть

 

 

<center><math>~

\bigoplus \limits^N_{i=k} G_i = G_k \oplus G_{k+1} \oplus ... \oplus G_{N-1} \oplus G_N.

</math></center>

 

 

Действительно, подставив в формулу выражение для ''i''-го бита кода Грея, получим

 

 

<center><math>~

B_k = \bigoplus \limits^N_{i=k} G_i =

\bigoplus \limits^N_{i=k} (B_i \oplus B_{i+1})=

 

 

(B_k \oplus B_{k+1}) \oplus (B_{k+1} \oplus B_{k+2}) \oplus ... \oplus (B_{N-1} \oplus B_N) \oplus (B_{N} \oplus B_{N+1})

=

</math>

<math>

= B_k \oplus (B_{k+1} \oplus B_{k+1}) \oplus ... \oplus ( B_N \oplus B_N) \oplus B_{N+1}

= B_k \oplus B_{N+1} = B_k

</math></center>

 

 

Здесь предполагается, что бит, выходящий за рамки разрядной сетки (<math>B_{N+1}</math>), равен нулю.

 

 

Ниже приведена функция на языке С, реализующая данный алгоритм. Она осуществляет последовательный сдвиг вправо и суммирование исходного двоичного числа, до тех пор, пока очередной сдвиг не обнулит слагаемое.

<source lang="Cpp">

unsigned int graydecode(unsigned int gray)

{

    unsigned int bin;

    for (bin = 0; gray; gray >>= 1) {

      bin ^= gray;

    }

    return bin;

}

</source>

 

 

Тот же самый алгоритм, записанный на языке Паскаль:

<source lang="pascal">

function GrayToBin(b:integer):integer;

var g:integer;

begin

  g:=0;

  while b>0 do begin

    g:=g xor b;

    b:=b shr 1;

  end;

  GrayToBin:=g;

end;

</source>

 

 

Пример: преобразовать код Грея 11101 в двоичный код.

 

 

11101

01110

00111

00011

00001

-----

10110

 

 

Быстрое преобразование 8/16/24/32-разрядного значения кода Грея в двоичный код на языке BlitzBasic:

<source lang="blitzbasic">

Function GRAY_2_BIN%(X%)

Return X Xor ((X And $88888888) Shr 4) Xor ((X And $CCCCCCCC) Shr 2) Xor ((X And $EEEEEEEE) Shr 1)

End Function

</source>

 

 

=== Генерация кодов Грея ===

 

 

Код Грея для n бит может быть рекурсивно построен на основе кода для n–1 бит путём переворачивания списка бит (то есть записыванием кодов в обратном порядке), конкатенации исходного и перевёрнутого списков, дописывания нулей в начало каждого кода в исходном списке и единиц — в начало кодов в перевёрнутом списке. Так, для генерации списка для n = 3 бит на основании кодов для двух бит необходимо выполнить следующие шаги:

 

 

{|

|-

| Коды для n = 2 бит: || 00, 01, 11, 10 ||

|-

| Перевёрнутый список кодов: ||  || 10, 11, 01, 00

|-

| Объединённый список: || 00, 01, 11, 10 || 10, 11, 01, 00

|-

| К начальному списку дописаны нули: || 000, 001, 011, 010 || 10, 11, 01, 00

|-

| К перевёрнутому списку дописаны единицы: || 000, 001, 011, 010 || 110, 111, 101, 100

|}

 

 

Ниже представлен один из алгоритмов создания последовательности кода Грея заданной глубины, записанный на языке [[Perl]]:

<source lang="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);

    }

</source>

 

 

Рекурсивная функция построение кода Грея на языке [[Си (язык программирования)|C]]:

<source lang="C">

 

 

//n -- требуемая длина кода,

//m -- указатель на массив, способный хранить

// все коды Грея, длиной до n

// (должен быть выделен до вызова функции)

//depth -- параметр рекурсии

 

int gray (int n, int* m, int depth)

 

 

{

int i, t = (1 << (depth - 1));

 

if (depth == 0)

m[0] = 0;

 

else {

        //массив хранит десятичные записи двоичных слов

for (i = 0; i < t; i++)

m[t + i] = m[t - i - 1] + (1 << (depth - 1));

}

if (depth != n)

gray(n, m, depth + 1);

 

 

return 0;

}

</source>

 

 

Быстрое преобразование 8/16/24/32-разрядного бинарного кода в код Грея на языке BlitzBasic:

<source lang="blitzbasic">

Function BIN_2_GRAY%(X%)

Return X Xor ((X And $EEEEEEEE) Shr 1)

End Function

</source>

 

 

== См. также ==

* [[Код Хемминга]]

* [[Код Джонсона]]

 

 

== Примечания ==

<references/>

 

 

== Библиография ==

* Black, Paul E. ''Gray code''. 25 февраля 2004. NIST. [http://www.nist.gov/dads/HTML/graycode.html] {{ref-en}}.

 

 

== Ссылки ==

* [http://www.nist.gov/dads/HTML/graycode.html NIST Dictionary of Algorithms and Data Structures: Gray code]{{ref-en}}

* [http://alglib.sources.ru/articles/graycode.php Коды Грея]

 

 

[[Категория:Электроника]]

[[Категория:Комбинаторика]]

[[Категория:Теория кодирования]]

 

 

[[ar:شفرة منعكسة]]

[[bg:Огледален двоичен код]]

[[ca:Codi Gray]]

[[cs:Grayův kód]]

[[de:Gray-Code]]

[[en:Gray code]]

[[es:Código Gray]]

[[et:Gray kood]]

[[fa:کد گری]]

[[fi:Gray-koodi]]

[[fr:Code de Gray]]

[[he:קוד גריי]]

[[hi:ग्रे कोड]]

[[hu:Gray-kód]]

[[it:Codice Gray]]

[[ja:グレイコード]]

[[ko:그레이 부호]]

[[nl:Gray-code]]

[[pl:Kod Graya]]

[[pt:Código de Gray]]

[[ro:Cod Gray]]

[[sk:Grayov kód]]

[[sv:Graykod]]

[[th:รหัสเกรย์]]

[[uk:Код Грея]]

[[vi:Mã Gray]]

[[zh:格雷码]]

 

 

 

 

Не благодари