格雷碼運(yùn)算研究

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

一般的,普通二進(jìn)制碼與格雷碼可以按以下方法互相轉(zhuǎn)換:
二進(jìn)制碼->格雷碼（編碼）：從最右邊一位起，依次將每一位與左邊一位異或(XOR)，作為對(duì)應(yīng)格雷碼該位的值，最左邊一位不變(相當(dāng)于左邊是0)；
格雷碼-〉二進(jìn)制碼（解碼）：從左邊第二位起，將每位與左邊一位解碼后的值異或，作為該位解碼后的值（最左邊一位依然不變）.
數(shù)學(xué)(計(jì)算機(jī))描述：
原碼：p[0~n]；格雷碼：c[0~n](n∈N)；編碼：c=G(p)；解碼：p=F(c)；書寫時(shí)從左向右標(biāo)號(hào)依次減小.
編碼：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是由貝爾實(shí)驗(yàn)室的Frank?Gray在20世紀(jì)40年代提出的（是1880年由法國(guó)工程師Jean-Maurice-Emlle?
Baudot發(fā)明的），用來在使用PCM（Pusle?Code?Modulation）方法傳送訊號(hào)時(shí)避免出錯(cuò)，并于1953年3月17日取得美國(guó)專利。由定義可知，Gray?Code的編碼方式不是唯一的，這里討論的是最常用的一種。

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

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?

我們發(fā)現(xiàn)，右邊一列數(shù)恰好是十進(jìn)制數(shù)0到21的二進(jìn)制數(shù)的格雷碼！?這當(dāng)然需要21步。如果把5位二進(jìn)制數(shù)依次寫完，就是?

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?

這說明，對(duì)于只有5個(gè)環(huán)的五連環(huán)，從初始到狀態(tài)11111用的不是并不是最多，到狀態(tài)00001才是最多，用31步。類似，對(duì)于九連環(huán)，從初始到狀態(tài)111111111用的不是并不是最多，到狀態(tài)000000001才是最多，用511步。由于格雷碼111111111表示二進(jìn)制數(shù)101010101，表示十進(jìn)制數(shù)341，故從初始狀態(tài)到9個(gè)環(huán)全部上去用341步。?這就是九連環(huán)中蘊(yùn)涵的數(shù)學(xué)內(nèi)涵。?

注?由二進(jìn)制數(shù)轉(zhuǎn)換為格雷碼：從右到左檢查，如果某一數(shù)字左邊是0，該數(shù)字不變；如果是1，該數(shù)字改變（0變?yōu)?，1變?yōu)?）。例，二進(jìn)制數(shù)11011的格雷碼是10110。?

由格雷碼表示變?yōu)槎M(jìn)制數(shù)：從右到左檢查，如果某一數(shù)字的左邊數(shù)字和是偶數(shù)，該數(shù)字不變；如果是奇數(shù)，該數(shù)字改變。?

例?格雷碼11011表示為二進(jìn)制數(shù)是10010。?

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

這樣，我們不但可以知道從任何一個(gè)狀態(tài)到另一個(gè)狀態(tài)用完整解法需要多少步，用簡(jiǎn)單解法又需要多少步，而且可以知道下一步的動(dòng)作是什么。（除去兩個(gè)狀態(tài)000000000和111111111，任何狀態(tài)下都可以轉(zhuǎn)變?yōu)閮蓚€(gè)狀態(tài)，即有兩個(gè)動(dòng)作。）

例?設(shè)九連環(huán)的初始狀態(tài)是?110100110?，要求終止?fàn)顟B(tài)是?001001111?，簡(jiǎn)單解法與完整解法各需要多少步？第一步是什么動(dòng)作？?

解?（1）初始狀態(tài)?110100110?，格雷碼是011001011，轉(zhuǎn)換為二進(jìn)制數(shù)是010001101，相應(yīng)十進(jìn)制數(shù)是141。終止?fàn)顟B(tài)是001001111，格雷碼是111100100，轉(zhuǎn)換為二進(jìn)制數(shù)是101000111，相應(yīng)十進(jìn)制數(shù)是327。二者差326－141＝186，完整解法需要186步。?

（2）由于初始狀況141小于終止?fàn)顩r327，第一步應(yīng)成為142，相應(yīng)二進(jìn)制是010001110，轉(zhuǎn)換為格雷碼是011001001，狀態(tài)是100100110，與原狀態(tài)比較，第一步應(yīng)上第2環(huán)。

（3）簡(jiǎn)單解法步數(shù),我們由141，327分別求相應(yīng)的簡(jiǎn)單步數(shù)，?

對(duì)于N=141,得到N0=103；對(duì)于?N=327,N0=242。二者差139，故簡(jiǎn)單步數(shù)139