308
правок
Изменения
м
Для Подобные рассуждения можно провести для любого <tex>k</tex>-ичного кода антигрея рассуждения будут аналогичными, где <tex>k \ge 3</tex>.
→Доказательство корректности алгоритма
* <tex dpi = "140">G_i^0</tex> и <tex dpi = "140">G_i^1</tex>, равно как <tex dpi = "140">G_i^1</tex> и <tex dpi = "140">G_i^2</tex>, отличаются во всех битах.
* Если говорить о векторах как о троичных числах, то <tex dpi = "140">G_{i+1}^0</tex> получено из <tex dpi = "140">G_i^0</tex> прибавлением единицы, это значит, что у <tex dpi = "140">G_{i+1}^0</tex> несколько разрядов справа на единицу больше (по модулю <tex>3</tex>), чем у <tex dpi = "140">G_i^0</tex> (по правилам сложения в столбик). С другой стороны <tex dpi = "140">G_{i}^2</tex> получено из <tex dpi = "140">G_{i}^0</tex> двумя циклическими сдвигами вперёд, что равносильно одному циклическому сдвигу назад. Таким образом, в числе <tex dpi = "140">G_{i+1}^0</tex> некоторые биты такие же, как в <tex dpi = "140">G_{i}^0</tex>, остальные на единицу больше; в числе <tex dpi = "140">G_{i}^2</tex> все биты на один меньше по сравнению с <tex dpi = "140">G_{i}^0</tex>, значит <tex dpi = "140">G_{i}^2</tex> и <tex dpi = "140">G_{i+1}^0</tex> различны во всех битах.
== См. также ==
