格雷碼簡介及格雷碼與二進制的轉換程序

格雷碼簡介

　　格雷碼（英文：Gray Code, Grey Code,又稱作葛萊碼，二進制循環碼）是1880年由法國工程師Jean-Maurice-Emlle
Baudot發明的一種編碼[1] ，因Frank Gray于1953年申請專利“Pulse Code
Communication”得名。當初是為了機械應用，后來在電報上取得了巨大發展[2]，現在則常用于模擬－數字轉換[3]和轉角－數字轉換中[4] 。
　　典型格雷碼是一種具有反射特性和循環特性的單步自補碼，它的循環、單步特性消除了隨機取數時出現重大誤差的可能，它的反射、自補特性使得求反非常方便[5] 。
　　格雷碼屬于可靠性編碼，是一種錯誤最小化的編碼，因為它大大地減少了由一個狀態到下一個狀態時電路中的混淆。由于這種編碼相鄰的兩個碼組之間只有一位不同，因而在用于模－數轉換中，當模擬量發生微小變化而可能引起數字量發生變化時，格雷碼僅改變一位，這樣與其它碼同時改變兩位或多位的情況相比更為可靠，即可減少出錯的可能性．這就允許代碼電路能以較少的錯誤在較高的速度下工作。
　　格雷碼在現代科學上獲得了廣泛的應用，人們還發現智力玩具九連環的狀態變化符合格雷碼的編碼規律，漢諾塔的解法也與格雷碼有關。
　　除了已知的特點，格雷碼還有一些鮮為人知的性質。多數數字電子技術和計算機技術的文獻認為格雷碼是無權碼，只有J.F.A.
Thompson認為可以從格雷碼直接轉換成十進制數[6]。如果將格雷碼的“權”及格雷碼的奇偶性等性質在數學上給予證明，將有助于格雷碼研究與應用的發展，有助于自動化技術的發展，還可有助于計算機科學的發展。

/*   格雷碼與二進制的轉換程序
 * 本程序采用遞推的方法進行推導,可以轉換0~2147483647之間的數(1~31位)
 * 推導方式如下(以三位格雷碼為例):
 * 序號 格雷碼 格雷碼實值 二進制碼 二進制實值
 *  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
 *     由上面的數據可看出.如果,按照序號01327645的方式遍歷格雷碼.其編
 * 碼實值是按自然數順序排列.反之,如果按此順序遍歷其二進制實值.則會發
 * 現遍歷過的數據的個數減一即為二進制碼所對應格雷碼的實值.再觀察序號
 * 順序,我們會發現: 如果把二進制碼分半,前半部分從前向后遍歷,后半部分
 * 從后向前遍歷.如果分半部分可再分,則再將其分半.并按照前半部分從前向
 * 后遍歷(分解),后半部分從后向前遍歷的方式遍歷(分解).直到不可分.即可
 * 實現按序號所描述順序遍歷二進制碼.如果,按此順序遍歷二進制碼,我們可
 * 以很方便地在序列中找到所要的二進制碼與其對應的格雷碼.本思想可以很
 * 方便地用遞歸實現.這樣就實現了二進制到格雷碼的轉換.同樣,格雷碼到二
 * 進制的轉換,也可以用相同的方法推出.為了加快運算,我們跳過不必要的遍
 * 歷將遞歸改為遞推.這樣就實現了格雷碼與二進制之間的快速轉換.
 * 此算法的時間復雜度約為O(n),n為要轉換數據的BIT數.
 * *****************************************************************
 *  補充說明：
 *  其它的轉換方法還有
 *    1、查表法（建立一個二進制與格雷碼的對應表）
 *    2、公式法（根據卡諾圖建立一個二進制到格雷碼的每一位的公式）
 */
 
//#define test
＃i nclude <stdio.h>
#ifdef test
 ＃i nclude <time.h>
#endif
/**
 * 二進制轉換成格雷碼
 * @param lStart lValue所在區間下界
 * @param lEnd lValue所在區間上界
 * @param lValue 要轉換的二進制數的實值
 * @return 返回格雷碼對應的二進制數的實值
 * @see g2b() g2b 格雷碼轉換二進制
 * @see BtoG() BtoG 二進制轉換格雷碼
 * @see GtoB() BtoG 格雷碼轉換二進制
 * @author 黃毅
 * @useage a=b2g(0,15,4); //取得4所對應格雷碼的二進制值 結果a等于6
 * @memo lValue的值必須在區間[lStart,lEnd]里,否則無法求得所求結果.相應地,如果區間越小,求得結
 *       果所用的時間就越少.而且lStart,lEnd的值必須為2的N次方減1. 通常lStart為0.為了方便求得
 *       其值,建議使用BtoG()函數來進行操作.不過這樣會使計算時間加長到原來的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;
}
/**
 * 格雷碼轉換成二進制
 * @param lStart lValue對應二進制數所在區間下界
 * @param lEnd lValue對應二進制數所在區間上界
 * @param lValue 要轉換的格雷碼的實值
 * @return 返回二進制數對應的格雷碼的實值
 * @see b2g() b2g 二進制轉換格雷碼
 * @see BtoG() BtoG 二進制轉換格雷碼
 * @see GtoB() BtoG 格雷碼轉換二進制
 * @author 黃毅
 * @useage a=b2g(0,15,6); //取得6所對應二進制值的格雷碼 結果a等于4
 * @memo lValue對應二進制數的值必須在區間[lStart,lEnd]里,否則無法求得所求結果.相應地,如果區
 *       間越小,求得結果所用的時間就越少.而且lStart,lEnd的值必須為2的N次方減1. 通常lStart為0.
 *       為了方便求得其值,建議使用GtoB()函數來進行操作.但會使計算時間加長到原來的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外殼程序,用來算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
//程序測試部分
 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