[程式] Gray Code Generation

來寫點昨天讀到 TAOCP (The Art of Computer Programming) 介紹 Gray Code (中譯好像是格雷碼) 的一點心得筆記 (花了一小時讀不到 5 頁...)。

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 來定義：

$ \Gamma(1) = 0, 1 $
$ \Gamma(n+1) = 0\Gamma(n) , 1\Gamma^R(n) $

其中 $ \Gamma(n) $ 代表 n-bit Gray code 的所有序列，$ \Gamma^R(n) $ 代表把 $ \Gamma(n) $ 的順序反向列出，比方說 $ \Gamma(3) $ = 000 -> 001 -> 011 -> 010 -> 110 -> 111 -> 101 -> 100，那麼 $\Gamma^R(3)$ = 100 -> 101 -> 111 -> 110 -> 010 -> 011 -> 001 -> 000。$0\Gamma(n)$ 表示把 $\Gamma(n)$ 所有序列前面都補上一個 0，因此 $0\Gamma(3)$ = 0000 -> 0001 -> 0011 -> 0010 -> 0110 -> 0111 -> 0101 -> 0100，以這個定義就可以簡單的列出所有 n-bit Gray code。

當然，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 = 2^n + r 且 0 \leq r < 2^n$ 可以被表示為

$$g(k) = 2^n + g(2^n - 1 - r)$$

第一個 $2^n$ 來自於 $1\Gamma^R(n)$ 的 1，$g(2^n - 1 - r)$ 來自於由後往前搜尋第 r 個 Gray number。基於這項公式，假設以二進位來表示 $k$ 與 $g(k)$，$k = (... a_n ... a_2 a_1)_2$，$g(k) = (... b_n ... b_2 b_1)_2$，則

$$b_j = a_j ⊕ a_j+1, j > 0 ... (1)$$

其中 ⊕ 表示 bitwise xor 運算，而上面這個式子可以進一步的改寫為

$$g(k) = k ⊕ \left \lfloor \frac{k}{2} \right \rfloor$$

如此一來就可以簡單的計算出第 k 個 Gray number 為何。舉例來說，
$$g(5) = 5 ⊕ \left \lfloor \frac{5}{2} \right \rfloor = 5 ⊕ 2 = (101)_2 ⊕ (010)_2 = (111)_2$$
而利用 (1) 式，給定第 k 個 Gray number 要反向計算出 k 為何也是可以的

$$k = g(k) ⊕ \left \lfloor \frac{g(k)}{2} \right \rfloor ⊕ \left \lfloor \frac{g(k)}{4} \right \rfloor ... $$

所以若 $ g(k) = (111)_2 $ ， 則
$$k = (111)_2 ⊕ \left \lfloor \frac{(111)_2}{2} \right \rfloor ⊕ \left \lfloor \frac{(111)_2}{4} \right \rfloor ⊕ \left \lfloor \frac{(111)_2}{8} \right \rfloor = (111)_2 ⊕ (11)_2 ⊕ (1)_2 ⊕ 0 = (101)_2 = 5$$

以下來簡單說明 (1) 式的證明：
如果 $g( (0 a_{n-1} ... a_2 a_1)_2 ) = ( 0(a_{n-1}) ... (a_3 ⊕ a_2), (a_2 ⊕ a_1) )_2$，那麼
$$g( (1 a_{n-1} ... a_2 a_1)_2 ) = 2^n + g( ( 0 \bar{a_{n-1}} ... \bar{a_2} \bar{a_1})_2 ) = ( 1\bar{a_{n-1}} ... (\bar{a_3} ⊕ \bar{a_2}) (\bar{a_2} ⊕ \bar{a_1}) )_2$$
其中 $\bar{a_i} = a_i ⊕ 1$