格雷碼運算研究

在數字系統中只能識別0和1，各種數據要轉換為二進制代碼才能進行處理，格雷碼是一種無權碼，采用絕對編碼方式，典型格雷碼是一種具有反射特性和循環特性的單步自補碼，它的循環、單步特性消除了隨機取數時出現重大誤差的可能，它的反射、自補特性使得求反非常方便。格雷碼屬于可靠性編碼，是一種錯誤最小化的編碼方式，因為，自然二進制碼可以直接由數/模轉換器轉換成模擬信號，但某些情況，例如從十進制的3轉換成4時二進制碼的每一位都要變，使數字電路產生很大的尖峰電流脈沖。而格雷碼則沒有這一缺點，它是一種數字排序系統，其中的所有相鄰整數在它們的數字表示中只有一個數字不同。它在任意兩個相鄰的數之間轉換時，只有一個數位發生變化。它大大地減少了由一個狀態到下一個狀態時邏輯的混淆。另外由于最大數與最小數之間也僅一個數不同，故通常又叫格雷反射碼或循環碼。下表為幾種自然二進制碼與格雷碼的對照表：

一般的,普通二進制碼與格雷碼可以按以下方法互相轉換:
二進制碼->格雷碼（編碼）：從最右邊一位起，依次將每一位與左邊一位異或(XOR)，作為對應格雷碼該位的值，最左邊一位不變(相當于左邊是0)；
格雷碼-〉二進制碼（解碼）：從左邊第二位起，將每位與左邊一位解碼后的值異或，作為該位解碼后的值（最左邊一位依然不變）.
數學(計算機)描述：
原碼：p[0~n]；格雷碼：c[0~n](n∈N)；編碼：c=G(p)；解碼：p=F(c)；書寫時從左向右標號依次減小.
編碼：c=p?XOR?p[i+1](i∈N,0≤i≤n-1)，c[n]=p[n]；
解碼：p[n]=c[n]，p=c?XOR?p[i+1](i∈N,0≤i≤n-1).

Gray?Code是由貝爾實驗室的Frank?Gray在20世紀40年代提出的（是1880年由法國工程師Jean-Maurice-Emlle?
Baudot發明的），用來在使用PCM（Pusle?Code?Modulation）方法傳送訊號時避免出錯，并于1953年3月17日取得美國專利。由定義可知，Gray?Code的編碼方式不是唯一的，這里討論的是最常用的一種。

[color=#FF0000]格雷碼是中國人的老祖先發現的[/color]
九連環與格雷碼?
分析解九連環的完全記法，由于每次只動一個環，故兩步的表示也只有一個數字不同。下面以五個環為例分析。左邊起第一列的五位數是5個環的狀態，依次由第一環到第五環。第二列是把這個表示反轉次序的五位數，似乎是二進制數,但是與第四列比較就可以看出這不是步數的二進制數表示。第三列是從初始狀態到這個狀態所用的步數。最右邊一列才是步數的二進制表示。?

00000－00000－0－00000?
10000－00001－1－00001?
11000－00011－2－00010?
01000－00010－3－00011?
01100－00110－4－00100?
11100－00111－5－00101?
10100－00101－6－00110?
00100－00100－7－00111?
00110－01100－8－01000?
10110－01101－9－01001?
11110－01111－10－01010?
01110－01110－11－01011?
01010－01010－12－01100?
11010－01011－13－01101?
10010－01001－14－01110?
00010－01000－15－01111?
00011－11000－16－10000?
10011－11001－17－10001?
11011－11011－18－10010?
01011－11010－19－10011?
01111－11110－20－10100?
11111－11111－21－10101?

我們發現，右邊一列數恰好是十進制數0到21的二進制數的格雷碼！?這當然需要21步。如果把5位二進制數依次寫完，就是?

10111－11101－22－10110?
00111－11100－23－10111?
00101－10100－24－11000?
10101－10101－25－11001?
11101－10111－26－11010?
01101－10110－27－11011?
01001－10010－28－11100?
11001－10011－29－11101?
10001－10001－30－11110?
00001－10000－31－11111?

這說明，對于只有5個環的五連環，從初始到狀態11111用的不是并不是最多，到狀態00001才是最多，用31步。類似，對于九連環，從初始到狀態111111111用的不是并不是最多，到狀態000000001才是最多，用511步。由于格雷碼111111111表示二進制數101010101，表示十進制數341，故從初始狀態到9個環全部上去用341步。?這就是九連環中蘊涵的數學內涵。?

注?由二進制數轉換為格雷碼：從右到左檢查，如果某一數字左邊是0，該數字不變；如果是1，該數字改變（0變為1，1變為0）。例，二進制數11011的格雷碼是10110。?

由格雷碼表示變為二進制數：從右到左檢查，如果某一數字的左邊數字和是偶數，該數字不變；如果是奇數，該數字改變。?

例?格雷碼11011表示為二進制數是10010。?

以上可以用口訣幫助記憶：?2G一改零不改，G2奇變偶不變。?

這樣，我們不但可以知道從任何一個狀態到另一個狀態用完整解法需要多少步，用簡單解法又需要多少步，而且可以知道下一步的動作是什么。（除去兩個狀態000000000和111111111，任何狀態下都可以轉變為兩個狀態，即有兩個動作。）

例?設九連環的初始狀態是?110100110?，要求終止狀態是?001001111?，簡單解法與完整解法各需要多少步？第一步是什么動作？?

解?（1）初始狀態?110100110?，格雷碼是011001011，轉換為二進制數是010001101，相應十進制數是141。終止狀態是001001111，格雷碼是111100100，轉換為二進制數是101000111，相應十進制數是327。二者差326－141＝186，完整解法需要186步。?

（2）由于初始狀況141小于終止狀況327，第一步應成為142，相應二進制是010001110，轉換為格雷碼是011001001，狀態是100100110，與原狀態比較，第一步應上第2環。

（3）簡單解法步數,我們由141，327分別求相應的簡單步數，?

對于N=141,得到N0=103；對于?N=327,N0=242。二者差139，故簡單步數139