格雷码 Gray Code

文章来源：http://hi.baidu.com/zyzbm/blog/item/fac9f96e8f1f0bd881cb4a9e.html

格雷码(Gray code),又叫循环二进制码或反射二进制码 

　　在数字系统中只能识别0和1，各种数据要转换为二进制代码才能进行处理，格雷码是一种无权码，采用绝对编码方式，典型格雷码是一种具有反射特性和循环特性的单步自补码，它的循环、单步特性消除了随机取数时出现重大误差的可能，它的反射、自补特性使得求反非常方便。格雷码属于可靠性编码，是一种错误最小化的编码方式，因为，自然二进制码可以直接由数/模转换器转换成模拟信号，但某些情况，例如从十进制的3转换成4时二进制码的每一位都要变，使数字电路产生很大的尖峰电流脉冲。而格雷码则没有这一缺点，它是一种数字排序系统，其中的所有相邻整数在它们的数字表示中只有一个数字不同。它在任意两个相邻的数之间转换时，只有一个数位发生变化。它大大地减少了由一个状态到下一个状态时逻辑的混淆。另外由于最大数与最小数之间也仅一个数不同，故通常又叫格雷反射码或循环码。下表为几种自然二进制码与格雷码的对照表：

┌────┬──────┬───┬────┬──────┬────┐
│十进制数│自然二进制数│格雷码│十进制数│自然二进制数│ 格雷码 │
├────┼──────┼───┼────┼──────┼────┤
│0        │0000       │0000   │8        │1000         │1100     │
├────┼──────┼───┼────┼──────┼────┤
│1        │0001         │0001   │9        │1001         │1101     │
├────┼──────┼───┼────┼──────┼────┤
│2        │0010         │0011   │10       │1010         │1111     │
├────┼──────┼───┼────┼──────┼────┤
│3        │0011         │0010   │11       │1011         │1110     │
├────┼──────┼───┼────┼──────┼────┤
│4        │0100         │0110   │12       │1100         │1010     │
├────┼──────┼───┼────┼──────┼────┤
│5        │0101         │0111   │13       │1101         │1011     │
├────┼──────┼───┼────┼──────┼────┤
│6        │0110         │0101   │14       │1110         │1001     │
├────┼──────┼───┼────┼──────┼────┤
│7        │0111         │0100   │15       │1111         │1000     │
└────┴──────┴───┴────┴──────┴────┘

一般的,普通二进制码与格雷码可以按以下方法互相转换:
二进制码->格雷码（编码）：从最右边一位起，依次将每一位与左边一位异或(XOR），作为对应格雷码该位的值，最左边一位不变(相当于左边是0)； int a; a = ;
格雷码-〉二进制码（解码）：从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）.
数学(计算机)描述：
原码：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的编码方式不是唯一的，这里讨论的是最常用的一种。

----------------------------------------------------------------------------------------------------------------------------------------------------------

From Gossip@caterpillar

Algorithm Gossip: 格雷碼（Gray Code）的生成方法

說明
Gray Code是一個數列集合，每個數使用二進位來表示，假設使用n位元來表示每個數好了，任兩個數之間只有一個位元值不同，例如以下為3位元的Gray Code：

000 001 011 010 110 111 101 100

由定義可以知道，Gray Code的順序並不是唯一的，例如將上面的數列反過來寫，也是一組Gray Code：

100 101 111 110 010 011 001 000

Gray Code是由貝爾實驗室的Frank Gray在1940年代提出的，用來在使用PCM（Pusle Code Modulation）方法傳送訊號時避免出錯，並於1953年三月十七日取得美國專利。

解法
由於Gray Code相鄰兩數之間只改變一個位元，所以可觀 察Gray Code從1變0或從0變1時的位置，假設有4位元的Gray Code如下：

0000 0001 0011 0010 0110 0111 0101 0100
1100 1101 1111 1110 1010 1011 1001 1000

觀察奇數項的變化時，我們發現無論它是第幾個Gray Code，永遠只改變最右邊的位元，如果是1就改為0，如果是0就改為1。

觀察偶數項的變化時，我們發現所改變的位元，是由右邊算來第一個1的左邊位元。

以上兩個變化規則是固定的，無論位元數為何；所以只要判斷位元的位置是奇數還是偶數，就可以決定要改變哪一個位元的值，為了程式撰寫方便，將陣列索引 0當作最右邊的值，而在列印結果時，是由索引數字大的開始反向列印。

將2位元的Gray Code當作平面座標來看，可以構成一個四邊形，您可以發現從任一頂點出發，繞四邊形周長繞一圈，所經過的頂點座標就是一組Gray Code，所以您可以得到四組Gray Code。

同樣的將3位元的Gray Code當作平面座標來看的話，可以構成一個正立方體，如果您可以從任一頂點出發，將所有的邊長走過，並不重複經過頂點的話，所經過的頂點座標順序之組合也就是一組Gray Code。 

實作：C    Java    Python    Scala

•  C

#include <stdio.h>
#include <stdlib.h>

#define MAXBIT 20
#define TRUE 1
#define CHANGE_BIT(x) x = ((x) == '0' ? '1' : '0')
#define NEXT(x) x = (1 - (x))

int main(void) {
    char digit[MAXBIT];
    int bits;
    printf("輸入位元數：");
    scanf("%d", &bits);

    int i;
    for(i = 0; i < bits; i++) {
        digit[i] = '0';
        printf("0");
    }

    printf("\n");

    int odd = TRUE;

    while(1) {
        if(odd)
            CHANGE_BIT(digit[0]);
        else {
            // 計算第一個1的位置
            int j;
            for(j = 0; j < bits && digit[j] == '0'; j++) ;
            if(j == bits - 1) // 最後一個Gray Code
                 break;
            CHANGE_BIT(digit[j + 1]);
        }
        int j;
        for(j = bits - 1; j >= 0; j--)
            printf("%c", digit[j]);

        printf("\n");
        NEXT(odd);
    }
    return 0;
}

•  Java

import java.util.*;
public class GrayCode implements Iterable<char[]>, Iterator<char[]> {
    private char[] digit;
    private boolean first = true;
    private boolean odd = true;

    public GrayCode(int length) {
        digit = new char[length];
        for(int i = 0; i < length; i++) {
            digit[i] = '0';
        }
    }

    public Iterator<char[]> iterator() {
        return this;
    }

    public boolean hasNext() {
        return count() != digit.length - 1;
    }

    public char[] next() {
        if(first)
            first = false;
        else {
            if(odd) charge(0);
            else if(hasNext()) charge(count() + 1);  // 最後一個 Gray Code
            odd = ! odd;
        }
        return reverse();
    }

    public void remove() {
        throw new RuntimeException("Unsupported operation");
    }

    private int count() {
        int count;
        // 計算第一個1的位置
        for(count = 0;
            (count < digit.length) && (digit[count] == '0');
             count++) ;
        return count;
    }

    private void charge(int i) {
        digit[i] = ((digit[i] == '0') ? '1' : '0');
    }

    private char[] reverse() {
        char[] tmp = new char[digit.length];
        int i = digit.length - 1;
        for(char c : digit) {
            tmp[i] = c;
            i--;
        }
        return tmp;
    }

    public static void main(String[] args) {
        for(char[] digit : new GrayCode(4)) {
            for(char c: digit)
                System.out.print(c);
            System.out.println();
        }
    }
}

• Python

TypeError: instance has no next() method

class GrayCode:
    def __init__(self, length):
        self.__digit = ['0'] * length
        self.__first = True
        self.__odd = True

    def __iter__(self):
        return self

    def __next__(self):
        if not self.__hasNext():
            raise StopIteration

        if self.__first:
            self.__first = False
        else:
            if self.__odd:
                self.__charge(0)
            else:
                if self.__hasNext():
                    self.__charge(self.__count() + 1)
            self.__odd = not self.__odd
        return self.__reverse()

    def __hasNext(self):
        return self.__count() != len(self.__digit) - 1

    def __charge(self, i):
        if self.__digit[i] == '0':
            self.__digit[i] = '1'
        else:
            self.__digit[i] = '0'

    def __count(self):
        count = 0
        while(count < len(self.__digit) and self.__digit[count] == '0'):
            count += 1
        return count

    def __reverse(self):
        tmp = []
        for i in range(len(self.__digit) - 1, -1, -1):
            tmp.append(self.__digit[i])
        return tmp

for digit in GrayCode(4):
    for i in range(0, len(digit)):
        print(digit[i],)
    print()

• Scala

class GrayCode(length: Int) extends Iterator[Array[Char]] {
    private var first = true
    private var odd = true
    private val digit = (for(i <- 0 until length) yield '0').toArray

    private def count() = {
        var c = 0
        while(c < digit.length && digit(c) == '0') {
            c += 1
        }
        c
    }

    private def charge(i: Int) {
        digit(i) = if(digit(i) == '0') '1' else '0'
    }

    def hasNext() = {
        count != digit.length - 1
    }

    def next() = {
        if(first) {
            first = false
        }
        else {
            if(odd) charge(0)
            else if(hasNext()) charge(count + 1)
            odd = !odd
        }
        digit.reverse
    }
}

for(digit <- new GrayCode(4)) {
    digit.foreach(print)
    println()
}