格雷码证明

格雷码证明

x为原来的数，y为格雷码，两者都用二进制表示

y=x xor (x shr 1)

可认为y(k)=x(k) xor x(k+1)，其中y(k)为y的从低到高第k位，x(k)为x的从低到高第k位。设二进制位数为n，注意x(n+1)=0。

1.所有二进制对应的格雷码都不相同

x->y    y(k)=x(k) xor x(k+1)

p->q    q(k)=p(k) xor p(k+1)

若y=q,则：y(n)=q(n)，求得x(n)=y(n)；y(n-1)=q(n-1)，求得x(n-1)=y(n-1)；依次类推，x(1)=y(1)，所以x=p。得证。

2.二进制下相邻的两个数对应的格雷码有且只有一位不相同，其它位都相同

二进制下相邻的两个数为x和s，其中x=s+1。而y=x xor (x shr 1), t=s xor (s shr 1)，

要证明y和t有且只有一位不相同，其它位都相同

I．x的最后一位为1

x	a[n]	a[n-1]	……	a[1]	1
x shr 1		a[n]		a[2]	a[1]
y					Diff

s	a[n]	a[n-1]	……	a[1]	0
s shr 1		a[n]	……	a[2]	a[1]
t					Diff

II．x的最后一位为0

x	a[n]	a[n-1]	……	a[k+1]	1	0	0	……	0	0
x shr 1		a[n]	……	a[k+2]	a[k+1]	1	0	……	0	0
y					Diff

s	a[n]	a[n-1]	……	a[k+1]	0	1	1	……	1	1
s shr 1		a[n]	……	a[k+2]	a[k+1]	0	1	……	1	1
t					Diff

所以得证。

3.

二进制->格雷码：y(i)=x(i) xor x(i+1)   [x(n+1)=0]  (规定)

格雷码->二进制：x(i)=x(i+1) xor y(i)

证明 格雷码->二进制：x(i)=x(i+1) xor y(i) 的正确性：

x(i)=x(i+1) xor y(i)=x(i+1) xor x(i) xor x(i+1)=x(i)

得证。