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