Gray code 的特點在於相鄰兩個數只有一個 bit 有變化，這點在電路設計上特別值得注意，因為可以減少位元變化的頻率，有助於增加硬體壽命、減少功率消耗等等，這個特殊的性質也可以用來開發特殊功能的電路，可以參閱維基百科。不過如果是初次見到 Gray code 應該會不知道設計的規律為何，以 3-bit 的 Gray code 來說，從 0 ~ 7 分別被表示為 000 -> 001 -> 011 -> 010 -> 110 -> 111 -> 101 -> 100，不過其實 n-bit 的 Gray code 可以用個簡單的 recursive relation 來定義：
Γ(1)=0,1
Γ(n+1)=0Γ(n),1ΓR(n)
其中 Γ(n) 代表 n-bit Gray code 的所有序列，ΓR(n) 代表把 Γ(n) 的順序反向列出，比方說 Γ(3) = 000 -> 001 -> 011 -> 010 -> 110 -> 111 -> 101 -> 100，那麼 ΓR(3) = 100 -> 101 -> 111 -> 110 -> 010 -> 011 -> 001 -> 000。0Γ(n) 表示把 Γ(n) 所有序列前面都補上一個 0，因此 0Γ(3) = 0000 -> 0001 -> 0011 -> 0010 -> 0110 -> 0111 -> 0101 -> 0100，以這個定義就可以簡單的列出所有 n-bit Gray code。Γ(n+1)=0Γ(n),1ΓR(n)
當然，Gray code 還有其它的定義方式，比方說如果我們把 Gray code 加以編號 (從 0 開始)，g(k) 代表第 k 個 Gray number (為方便表示，leading zero 通通省略)，則 g(0) = 0, g(1) = 1, g(2) = 11, g(3) = 10, g(4) = 110, g(5) = 111, g(6) = 101, g(7) = 100, ...。則根據前面的講到的 recursive relation 我們可以發現 g(k),k=2n+r且0≤r<2n 可以被表示為
g(k)=2n+g(2n−1−r)
第一個 2n 來自於 1ΓR(n) 的 1，g(2n−1−r) 來自於由後往前搜尋第 r 個 Gray number。基於這項公式，假設以二進位來表示 k 與 g(k)，k=(...an...a2a1)2，g(k)=(...bn...b2b1)2，則bj=aj⊕aj+1,j>0...(1)
其中 ⊕ 表示 bitwise xor 運算，而上面這個式子可以進一步的改寫為g(k)=k⊕⌊k2⌋
如此一來就可以簡單的計算出第 k 個 Gray number 為何。舉例來說，g(5)=5⊕⌊52⌋=5⊕2=(101)2⊕(010)2=(111)2
而利用 (1) 式，給定第 k 個 Gray number 要反向計算出 k 為何也是可以的
k=g(k)⊕⌊g(k)2⌋⊕⌊g(k)4⌋...
所以若 g(k)=(111)2 ， 則k=(111)2⊕⌊(111)22⌋⊕⌊(111)24⌋⊕⌊(111)28⌋=(111)2⊕(11)2⊕(1)2⊕0=(101)2=5
以下來簡單說明 (1) 式的證明：
如果 g((0an−1...a2a1)2)=(0(an−1)...(a3⊕a2),(a2⊕a1))2，那麼
g((1an−1...a2a1)2)=2n+g((0¯an−1...¯a2¯a1)2)=(1¯an−1...(¯a3⊕¯a2)(¯a2⊕¯a1))2
其中 ¯ai=ai⊕1
沒有留言:
張貼留言