格雷碼那點(diǎn)事——遞歸非遞歸實(shí)現(xiàn)

2019-11-14 15:40:29

字體：大中小

供稿：網(wǎng)友

簡(jiǎn)介

　　在一組數(shù)的編碼中，若任意兩個(gè)相鄰的代碼只有一位二進(jìn)制數(shù)不同，則稱這種編碼為格雷碼（Gray Code），另外由于最大數(shù)與最小數(shù)之間也僅一位數(shù)不同，即“首尾相連”，因此又稱循環(huán)碼或反射碼。在數(shù)字系統(tǒng)中，常要求代碼按一定順序變化。例如，按自然數(shù)遞增計(jì)數(shù)，若采用8421碼，則數(shù)0111變到1000時(shí)四位均要變化，而在實(shí)際電路中，4位的變化不可能絕對(duì)同時(shí)發(fā)生，則計(jì)數(shù)中可能出現(xiàn)短暫的其它代碼（1100、1111等）。在特定情況下可能導(dǎo)致電路狀態(tài)錯(cuò)誤或輸入錯(cuò)誤。使用格雷碼可以避免這種錯(cuò)誤。格雷碼有多種編碼形式。

　　格雷碼（Gray Code）曾用過(guò)Grey Code、葛萊碼、格萊碼、戈萊碼、循環(huán)碼、反射二進(jìn)制碼、最小差錯(cuò)碼等名字，它們有的不對(duì)，有的易與其它名稱混淆，建議不要再使用這些曾用名。

　格雷碼是一種具有反射特性和循環(huán)特性的單步自補(bǔ)碼，其循環(huán)和單步特性消除了隨機(jī)取數(shù)時(shí)出現(xiàn)重大錯(cuò)誤的可能，其反射和自補(bǔ)特性使得對(duì)其進(jìn)行求反操作也非常方便，所以，格雷碼屬于一種可靠性編碼，是一種錯(cuò)誤最小化的編碼方式，因此格雷碼在通信和測(cè)量技術(shù)中得到廣泛應(yīng)用。

生成格雷碼　

　　格雷碼(Gray Code)是一個(gè)數(shù)列集合，每個(gè)數(shù)使用二進(jìn)位來(lái)表示，假設(shè)使用n位元來(lái)表示每個(gè)數(shù)字，任兩個(gè)數(shù)之間只有一個(gè)位元值不同。

　　例如以下為3位元的格雷碼： 000 001 011 010 110 111 101 100 。

　　如果要產(chǎn)生n位元的格雷碼，那么格雷碼的個(gè)數(shù)為2^n.

　　假設(shè)原始的值從0開(kāi)始，格雷碼產(chǎn)生的規(guī)律是：

第一步，改變最右邊的位元值；

第二步，改變右起第一個(gè)為1的位元的左邊位元；

第三步，第四步重復(fù)第一步和第二步，直到所有的格雷碼產(chǎn)生完畢（換句話說(shuō)，已經(jīng)走了(2^n) - 1 步）。

用一個(gè)例子來(lái)說(shuō)明：

　　假設(shè)產(chǎn)生3位元的格雷碼，原始值位 000

　　第一步：改變最右邊的位元值： 001

　　第二步：改變右起第一個(gè)為1的位元的左邊位元： 011

　　第三步：改變最右邊的位元值： 010

　　第四步：改變右起第一個(gè)為1的位元的左邊位元： 110

　　第五步：改變最右邊的位元值： 111

　　第六步：改變右起第一個(gè)為1的位元的左邊位元： 101

　　第七步：改變最右邊的位元值： 100

　　如果按照這個(gè)規(guī)則來(lái)生成格雷碼，是沒(méi)有問(wèn)題的，但是這樣做太復(fù)雜了。如果仔細(xì)觀察格雷碼的結(jié)構(gòu)，我們會(huì)有以下發(fā)現(xiàn)：

　　1、除了最高位（左邊第一位），格雷碼的位元完全上下對(duì)稱（看下面列表）。比如第一個(gè)格雷碼與最后一個(gè)格雷碼對(duì)稱（除了第一位），第二個(gè)格雷碼與倒數(shù)第二個(gè)對(duì)稱，以此類(lèi)推。

　　2、最小的重復(fù)單元是 0 , 1。

000
001
011
010
110
111
101
100

　　所以，在實(shí)現(xiàn)的時(shí)候，我們完全可以利用遞歸，在每一層前面加上0或者1，然后就可以列出所有的格雷碼。

　　比如：

　　第一步：產(chǎn)生 0, 1 兩個(gè)字符串。

　　第二步：在第一步的基礎(chǔ)上，每一個(gè)字符串都加上0和1，但是每次只能加一個(gè)，所以得做兩次。這樣就變成了 00,01,11,10 （注意對(duì)稱）。

　　第三步：在第二步的基礎(chǔ)上，再給每個(gè)字符串都加上0和1，同樣，每次只能加一個(gè)，這樣就變成了 000,001,011,010,110,111,101,100。

　　好了，這樣就把3位元格雷碼生成好了。

　　如果要生成4位元格雷碼，我們只需要在3位元格雷碼上再加一層0,1就可以了： 0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1110,1010,0111,1001,1000.

　　也就是說(shuō)，n位元格雷碼是基于n-1位元格雷碼產(chǎn)生的。

算法實(shí)現(xiàn)

1、遞歸實(shí)現(xiàn)

/**     * 遞歸生成二進(jìn)制格雷碼     * 思路:1、獲得n-1位生成格雷碼的數(shù)組     *      2、由于n位生成的格雷碼位數(shù)是n-1的兩倍，故只要在n為格雷碼的前半部分加0，后半部分加1即可。     * @param n 格雷碼的位數(shù)     * @return 生成的格雷碼數(shù)組     */    public static String[] GrayCode(int n) {    //數(shù)組的大小是2的n次方，因?yàn)閚位的格雷碼有2的n次方種排列    String[] grayCodeArr = new String[(int)Math.pow(2, n)];        if(n < 1)    {        System.out.);    }        if(1 == n)    {        grayCodeArr[0] = "0";        grayCodeArr[1] = "1";        return grayCodeArr;    }        //n-1 位格雷碼的生成方式    String[] before = GrayCode(n-1);        for(int i = 0 ; i < before.length ; i++){        grayCodeArr[i] = "0" + before[i];        grayCodeArr[grayCodeArr.length -1 - i] = "1" + before[i];    }        return grayCodeArr;        }

2、非遞歸實(shí)現(xiàn)

  /**     * 非遞歸生成二進(jìn)制格雷碼     * 思路:1、獲得n-1位生成格雷碼的數(shù)組     *      2、由于n位生成的格雷碼位數(shù)是n-1的兩倍，故只要在n為格雷碼的前半部分加0，后半部分加1即可。     * @param n 格雷碼的位數(shù)     * @return 生成的格雷碼數(shù)組     */    public static String[] GrayCode2(int n)    {            int num = (int)Math.pow(2, n);//根據(jù)輸入的整數(shù)，計(jì)算出此Gray序列大小    String[] s1 = {"0","1"};//第一個(gè)Gray序列        if(n < 1)    {        System.out.println("你輸入的格雷碼位數(shù)有誤！");    }        for(int i=2;i<=n;i++){//循環(huán)根據(jù)第一個(gè)Gray序列，來(lái)一個(gè)一個(gè)的求    int p = (int)Math.pow(2, i);//到了第幾個(gè)的時(shí)候，來(lái)計(jì)算出此Gray序列大小    String[] si = new String[p];    for(int j=0;j<p;j++){//循環(huán)根據(jù)某個(gè)Gray序列，來(lái)一個(gè)一個(gè)的求此序列    if(j<(p/2)){    si[j] = "0" + s1[j];//原始序列前面加上"0"    }else{    si[j] = "1" + s1[p-j-1];//原始序列反序，前面加上"1"    }    }    s1 = si;//把求得的si，附給s1,以便求下一個(gè)Gray序列    }        return s1;    }

3、測(cè)試

public static void main(String[] args) {        System.out.println("————————————————————遞歸實(shí)現(xiàn)————————————————");    String[] strArr = GrayCode(4);    for(int i = 0 ; i < strArr.length ; i++)    {        System.out.println(strArr[i]);    }        System.out.println("——————————————————非遞歸實(shí)現(xiàn)————————————————");    String[] strArr2 = GrayCode2(4);    for(int i = 0 ; i < strArr2.length ; i++)    {        System.out.println(strArr2[i]);    }    }

4、結(jié)果：

————————————————————遞歸實(shí)現(xiàn)————————————————0000000100110010011001110101010011001101111111101010101110011000——————————————————非遞歸實(shí)現(xiàn)————————————————0000000100110010011001110101010011001101111111101010101110011000

　　致謝：感謝您的耐心閱讀！