格雷码的独特性质

wsc810 · 发表于 2010-5-22 11:58:25

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

如果我们对格雷码再求格雷码，如此反复，经过有限次以后（该值为2的n次幂）会得到什么结果呢？想必你还不知道吧，它就是这个数本身。你说奇怪吧！可谁会证明呢？具体的例子我就不举了，大家随便拿一个数试试就知道了。

mathe · 发表于 2010-5-22 14:50:14

数学归纳法即可

wsc810 · 发表于 2010-5-23 15:13:34

如何运用归纳法，mahe能否给我们写出过程，教教我们这些新手。

mathe · 发表于 2010-5-23 15:33:40

假设一个n比特数各位分别为$a_0,a_1,...,a_{n-1}$,用+表示异或，那么其格莱码各位分别为$a_0,a_0+a_1,...,a_0+a_1+...+a_{n-1}$ 容易用归纳法得出，对于任意一个数，它的任意h次格莱码变换后的第k位是原数据的第k位和前k-1位的一个函数值的的异或，也就是可以写成$g_{h,k}(a_0,a_1,...,a_{n-1})=a_k+f_{h,k}(a_0,a_1,...,a_{k-1})$ 此后就可以对原命题使用归纳法。假设n比特的经过$2^{n-1}$次变换恢复成原始数据。那么n+1比特的数，经过$2^{n-1}$次变换后，前n比特恢复，而最后一比特变成$a_n+f_{2^{n-1},n}(a_0,a_1,...,a_{n-1})$所以如果我们再做$2^{n-1}$次变换，前n比特又会不变，而最后一比特变成 $a_n+f_{2^{n-1},n}(a_0,a_1,...,a_{n-1})+f_{2^{n-1},n}(a_0,a_1,...,a_{n-1})=a_n$

wsc810 · 发表于 2010-5-24 22:09:48

据说九连环与格雷码之间有某种巧妙的联系，想弄一个玩玩不知哪里有卖的？下面这个链接给出了许多由九连环引伸出的数学知识。http://qzc.zgz.cn/index.asp

wsc810 · 发表于 2010-5-26 11:08:57

设G(A)表示对数A求其格雷码的值,则有下式成立。(用＋表示异或) G(A+B)=G(A)+G(B)

账号		自动登录	找回密码
密码			欢迎注册

[原创] 格雷码的独特性质

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。