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