格雷碼簡(jiǎn)介及格雷碼與二進(jìn)制的轉(zhuǎn)換程序
格雷碼簡(jiǎn)介
格雷碼（英文：Gray Code, Grey Code,又稱作葛萊碼，二進(jìn)制循環(huán)碼）是1880年由法國(guó)工程師Jean-Maurice-Emlle
Baudot發(fā)明的一種編碼[1] ，因Frank Gray于1953年申請(qǐng)專利“Pulse Code
Communication”得名。當(dāng)初是為了機(jī)械應(yīng)用，后來(lái)在電報(bào)上取得了巨大發(fā)展[2]，現(xiàn)在則常用于模擬－數(shù)字轉(zhuǎn)換[3]和轉(zhuǎn)角－數(shù)字轉(zhuǎn)換中[4] 。
典型格雷碼是一種具有反射特性和循環(huán)特性的單步自補(bǔ)碼，它的循環(huán)、單步特性消除了隨機(jī)取數(shù)時(shí)出現(xiàn)重大誤差的可能，它的反射、自補(bǔ)特性使得求反非常方便[5] 。
格雷碼屬于可靠性編碼，是一種錯(cuò)誤最小化的編碼，因?yàn)樗蟠蟮販p少了由一個(gè)狀態(tài)到下一個(gè)狀態(tài)時(shí)電路中的混淆。由于這種編碼相鄰的兩個(gè)碼組之間只有一位不同，因而在用于模－數(shù)轉(zhuǎn)換中，當(dāng)模擬量發(fā)生微小變化而可能引起數(shù)字量發(fā)生變化時(shí)，格雷碼僅改變一位，這樣與其它碼同時(shí)改變兩位或多位的情況相比更為可靠，即可減少出錯(cuò)的可能性．這就允許代碼電路能以較少的錯(cuò)誤在較高的速度下工作。
格雷碼在現(xiàn)代科學(xué)上獲得了廣泛的應(yīng)用，人們還發(fā)現(xiàn)智力玩具九連環(huán)的狀態(tài)變化符合格雷碼的編碼規(guī)律，漢諾塔的解法也與格雷碼有關(guān)。
除了已知的特點(diǎn)，格雷碼還有一些鮮為人知的性質(zhì)。多數(shù)數(shù)字電子技術(shù)和計(jì)算機(jī)技術(shù)的文獻(xiàn)認(rèn)為格雷碼是無(wú)權(quán)碼，只有J.F.A.
Thompson認(rèn)為可以從格雷碼直接轉(zhuǎn)換成十進(jìn)制數(shù)[6]。如果將格雷碼的“權(quán)”及格雷碼的奇偶性等性質(zhì)在數(shù)學(xué)上給予證明，將有助于格雷碼研究與應(yīng)用的發(fā)展，有助于自動(dòng)化技術(shù)的發(fā)展，還可有助于計(jì)算機(jī)科學(xué)的發(fā)展。
/* 格雷碼與二進(jìn)制的轉(zhuǎn)換程序
* 本程序采用遞推的方法進(jìn)行推導(dǎo),可以轉(zhuǎn)換0~2147483647之間的數(shù)(1~31位)
* 推導(dǎo)方式如下(以三位格雷碼為例):
* 序號(hào) 格雷碼 格雷碼實(shí)值 二進(jìn)制碼 二進(jìn)制實(shí)值
* 0 000 0 000 0
* 1 001 1 001 1
* 2 011 3 010 2
* 3 010 2 011 3
* 4 110 6 100 4
* 5 111 7 101 5
* 6 101 5 110 6
* 7 100 4 111 7
* 由上面的數(shù)據(jù)可看出.如果,按照序號(hào)01327645的方式遍歷格雷碼.其編
* 碼實(shí)值是按自然數(shù)順序排列.反之,如果按此順序遍歷其二進(jìn)制實(shí)值.則會(huì)發(fā)
* 現(xiàn)遍歷過(guò)的數(shù)據(jù)的個(gè)數(shù)減一即為二進(jìn)制碼所對(duì)應(yīng)格雷碼的實(shí)值.再觀察序號(hào)
* 順序,我們會(huì)發(fā)現(xiàn): 如果把二進(jìn)制碼分半,前半部分從前向后遍歷,后半部分
* 從后向前遍歷.如果分半部分可再分,則再將其分半.并按照前半部分從前向
* 后遍歷(分解),后半部分從后向前遍歷的方式遍歷(分解).直到不可分.即可
* 實(shí)現(xiàn)按序號(hào)所描述順序遍歷二進(jìn)制碼.如果,按此順序遍歷二進(jìn)制碼,我們可
* 以很方便地在序列中找到所要的二進(jìn)制碼與其對(duì)應(yīng)的格雷碼.本思想可以很
* 方便地用遞歸實(shí)現(xiàn).這樣就實(shí)現(xiàn)了二進(jìn)制到格雷碼的轉(zhuǎn)換.同樣,格雷碼到二
* 進(jìn)制的轉(zhuǎn)換,也可以用相同的方法推出.為了加快運(yùn)算,我們跳過(guò)不必要的遍
* 歷將遞歸改為遞推.這樣就實(shí)現(xiàn)了格雷碼與二進(jìn)制之間的快速轉(zhuǎn)換.
* 此算法的時(shí)間復(fù)雜度約為O(n),n為要轉(zhuǎn)換數(shù)據(jù)的BIT數(shù).
* *****************************************************************
* 補(bǔ)充說(shuō)明：
* 其它的轉(zhuǎn)換方法還有
* 1、查表法（建立一個(gè)二進(jìn)制與格雷碼的對(duì)應(yīng)表）
* 2、公式法（根據(jù)卡諾圖建立一個(gè)二進(jìn)制到格雷碼的每一位的公式）
*/
//#define test
＃i nclude <stdio.h>
#ifdef test
＃i nclude <time.h>
#endif
/**
* 二進(jìn)制轉(zhuǎn)換成格雷碼
* @param lStart lValue所在區(qū)間下界
* @param lEnd lValue所在區(qū)間上界
* @param lValue 要轉(zhuǎn)換的二進(jìn)制數(shù)的實(shí)值
* @return 返回格雷碼對(duì)應(yīng)的二進(jìn)制數(shù)的實(shí)值
* @see g2b() g2b 格雷碼轉(zhuǎn)換二進(jìn)制
* @see BtoG() BtoG 二進(jìn)制轉(zhuǎn)換格雷碼
* @see GtoB() BtoG 格雷碼轉(zhuǎn)換二進(jìn)制
* @author 黃毅
* @useage a=b2g(0,15,4); //取得4所對(duì)應(yīng)格雷碼的二進(jìn)制值 結(jié)果a等于6
* @memo lValue的值必須在區(qū)間[lStart,lEnd]里,否則無(wú)法求得所求結(jié)果.相應(yīng)地,如果區(qū)間越小,求得結(jié)
* 果所用的時(shí)間就越少.而且lStart,lEnd的值必須為2的N次方減1. 通常lStart為0.為了方便求得
* 其值,建議使用BtoG()函數(shù)來(lái)進(jìn)行操作.不過(guò)這樣會(huì)使計(jì)算時(shí)間加長(zhǎng)到原來(lái)的120%~180%.
*/
unsigned long b2g(unsigned long lStart,unsigned long lEnd,unsigned
long lValue)
{
unsigned long Start=lStart,End=lEnd,Temp=0,Counter=0;
bool Type=true;
while(Start<End)
{
Temp=(End+Start-1)>>1;
if (lValue<=Temp)
{
if(!Type)
Counter+=((End-Start+1)>>1);
End=Temp;
Type=true;
}
else
{
if(Type)
Counter+=((End-Start+1)>>1);
Start=++Temp;
Type=false;
}
}
return Counter;
}
/**
* 格雷碼轉(zhuǎn)換成二進(jìn)制
* @param lStart lValue對(duì)應(yīng)二進(jìn)制數(shù)所在區(qū)間下界
* @param lEnd lValue對(duì)應(yīng)二進(jìn)制數(shù)所在區(qū)間上界
* @param lValue 要轉(zhuǎn)換的格雷碼的實(shí)值
* @return 返回二進(jìn)制數(shù)對(duì)應(yīng)的格雷碼的實(shí)值
* @see b2g() b2g 二進(jìn)制轉(zhuǎn)換格雷碼
* @see BtoG() BtoG 二進(jìn)制轉(zhuǎn)換格雷碼
* @see GtoB() BtoG 格雷碼轉(zhuǎn)換二進(jìn)制
* @author 黃毅
* @useage a=b2g(0,15,6); //取得6所對(duì)應(yīng)二進(jìn)制值的格雷碼 結(jié)果a等于4
* @memo lValue對(duì)應(yīng)二進(jìn)制數(shù)的值必須在區(qū)間[lStart,lEnd]里,否則無(wú)法求得所求結(jié)果.相應(yīng)地,如果區(qū)
* 間越小,求得結(jié)果所用的時(shí)間就越少.而且lStart,lEnd的值必須為2的N次方減1. 通常lStart為0.
* 為了方便求得其值,建議使用GtoB()函數(shù)來(lái)進(jìn)行操作.但會(huì)使計(jì)算時(shí)間加長(zhǎng)到原來(lái)的105%~140%.
*/
unsigned long g2b(unsigned long lStart,unsigned long lEnd,unsigned
long lValue)
{
unsigned long Start=lStart,End=lEnd,Counter=0,Temp=0;
bool Type=true;
while(Start<End)
{
Temp=Counter+((End-Start+1)>>1);
if(Type^(lValue<Temp))
{
if(Type) Counter=Temp;
Start=(Start+End+1)>>1;
Type=false;
}
else
{
if(!Type) Counter=Temp;
End=(Start+End-1)>>1;
Type=true;
}
}
return Start;
}
//b2g外殼程序,用來(lái)算lStart,lEnd;
long BtoG(unsigned long lValue)
{
register unsigned long lV=lValue,lMax=1;
while (lV>0)
{
lV>>=1;
lMax<<=1;
}
if (lMax==0) return -1;
return b2g(0,--lMax,lValue);
}
//g2b外殼程序
long GtoB(unsigned long lValue)
{
register unsigned long lV=lValue,lMax=1;
while (lV>0)
{
lV>>=1;
lMax<<=1;
}
if (lMax==0) return -1;
return g2b(0,--lMax,lValue);
}
main()
{
long input=0;
#ifdef test
//程序測(cè)試部分
clock_t cStart,cEnd;
unsigned long dTime;
cStart=clock();
for (input=0;input<9999999;input++)
BtoG(32768);
cEnd=clock();
dTime=(cEnd-cStart);
printf("BtoG: %ld / %ld\n",dTime,CLOCKS_PER_SEC);
//------------------------------------------------------
cStart=clock();
for (input=0;input<9999999;input++)
b2g(0,65535,32768);
cEnd=clock();
dTime=(cEnd-cStart);
printf("b2g: %ld / %ld\n",dTime,CLOCKS_PER_SEC);
//------------------------------------------------------
cStart=clock();
for (input=0;input<9999999;input++)
GtoB(32768);
cEnd=clock();
dTime=(cEnd-cStart);
printf("GtoB: %ld / %ld\n",dTime,CLOCKS_PER_SEC);
//------------------------------------------------------
cStart=clock();
for (input=0;input<9999999;input++)
g2b(0,65535,32768);
cEnd=clock();
dTime=(cEnd-cStart);
printf("g2b: %ld / %ld\n",dTime,CLOCKS_PER_SEC);
#else
//程序演試部分
printf("Input(HEX):");
scanf("%x",&input);
while (input!=-1)
{
printf("------BtoG------\nBinary:%08Xh\nGray
:%08Xh\n------GtoB------\nGray
:%08Xh\nBinary:%08Xh\n----------------\n",input,BtoG(input),input,GtoB(input));
printf("Input(HEX):");
scanf("%x",&input);
}
#endif