170
правок
Изменения
Формулы в доказательстве теперь совсем нормальные
Код назван в честь Фрэнка Грея, который в 1947-ом году получил патент на "отражённый двоичный код". Изначально он предназначался для избавления от паразитных состояний в электромеханических переключателях, однако сейчас область его применения гораздо шире.
{| width="150" align="right" cellpadding="5" border="1" style="border-collapse: collapse;" float = "right"
|-
Обозначим за <tex>L</tex> код длины <tex>n + 1</tex>, полученный из <tex>M</tex> описанным выше алгоритмом. Тогда:
<tex>\forall x < 2^n \enskip L_x = 0M_x = 0(x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n-1}x_{n-2}...x_{1}) = </tex><tex> 0x_{n-1}x_{n-2}...x_{0} \oplus 00x_{n-1}x_{n-2}...x_{1} = x \oplus (x \div 2)</tex>
<tex>\forall x \geq 2^n \enskip L_x = 1M_y</tex>, где <tex>y = 2^{n+1} - 1 - x = \neg x</tex>, то есть
<tex>L_x = 1(\neg x_{n-1} \neg x_{n-2}... \neg x_{0} \oplus 0 \neg x_{n-1} \neg x_{n-2}... \neg x_{1}) = </tex><tex> 1(\neg x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n-1}x_{n-2}...x_{1}) =</tex> <tex>= 1(x_{n-1}x_{n-2}...x_{0} \oplus 1x_{n-1}x_{n-2}...x_{1}) = 1x_{n-1}x_{n-2}...x_{0} </tex><tex> \oplus 01x_{n-1}x_{n-2}...x_{1} = x_{n}x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n}x_{n-1}x_{n-2}...x_{1} = </tex><tex> x \oplus (x \div 2)</tex>
Таким образом, по теореме о математической индукции требуемое доказано.
