Изменения

Перейти к: навигация, поиск

Коды антигрея

204 байта добавлено, 14:50, 13 января 2013
м
Доказательство корректности алгоритма
<tex dpi="120">G_{i+1}^0</tex> <br>
...
* <tex dpi = "140">G_i^0</tex> и <texdpi = "140">G_i^1</tex>, равно как <texdpi = "140">G_i^1</tex> и <texdpi = "140">G_i^2</tex>, отличаются во всех битах.* Если говорить о векторах как о троичных числах, то <texdpi = "140">G_{i+1}^0</tex> получено из <texdpi = "140">G_i^0</tex> прибавлением единицы, это значит, что у <texdpi = "140">G_{i+1}^0</tex> несколько разрядов справа на единицу больше (по модулю <tex>3</tex>), чем у <texdpi = "140">G_i^0</tex> (по правилам сложения в столбик). С другой стороны <texdpi = "140">G_{i}^2</tex> получено из <texdpi = "140">G_{i}^0</tex> двумя циклическими сдвигами вперёд, что равносильно одному циклическому сдвигу назад. Таким образом, в числе <texdpi = "140">G_{i+1}^0</tex> некоторые биты такие же, как в <texdpi = "140">G_{i}^0</tex>, остальные на единицу больше; в числе <texdpi = "140">G_{i}^2</tex> все биты на один меньше по сравнению с <texdpi = "140">G_{i}^0</tex>, значит <texdpi = "140">G_{i}^2</tex> и <texdpi = "140">G_{i+1}^0</tex> различны во всех битах.
Для <tex>k</tex>-ичного кода антигрея рассуждения будут аналогичными.
101
правка

Навигация