格雷碼

December 7, 2021
格雷碼(Gray Code)的每個數使用二進位表示,假設使用 n 位元來表示每個數,任兩數間只有一個位元不同。例如以下為 3 位元的格雷碼:

000 001 011 010 110 111 101 100

由定義可以知道,格雷碼的順序並非唯一。例如將以上數列反過來寫,也是一組格雷碼:

100 101 111 110 010 011 001 000

格雷碼是貝爾實驗室的 Frank Gray 在 1940 年代提出,在使用 PCM(Pusle Code Modulation)方法傳送訊號時避免出錯,並於 1953 年 3月 17 日取得美國專利。

解法思路

由於格雷碼相鄰兩數間只改變一個位元,可觀察格雷碼從 1 變 0 或從 0 變1 時的位置。假設有 4 位元的格雷碼如下:

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

觀察奇數項的下個數變化,發現無論是第幾個奇數項格雷碼,下個數永遠只改變最右邊的位元。如果是 1 就改為 0,如果是 0 就改為 1。例如第一項 0000 變為 0001,第三項 0011 變為 0010,第五項 0110 變為 0111,依此類推。

觀察偶數項的下個數變化,發現改變的位元,是由右邊算來首個 1 的左邊位元。例如第二項 0001 下個數變為 0011,第四項 0010 下個變為 0110,第六項 0111 變為 0101,依此類推。

以上兩個變化規則是固定的,無論位元數為何,因此只要判斷是奇數項還是偶數項,就可以決定要改變哪個位元值。

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

同樣地,將 3 位元格雷碼當作立體座標來看的話,可以構成一個正立方體。可以從任一頂點出發,將所有邊走過,並不重複經過頂點的話,經過的頂點座標順序組合也是一組格雷碼。

程式實作

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

void doGray(int, void (*)(int*, int));
void init(int*, int);
int firstOneOf(int*, int);
void next(int*, int, int);
int isLast(int*, int);
void print(int*, int);

int main(void) { 
    int length;
    printf("輸入位元數:"); 
    scanf("%d", &length); 

    doGray(length, print);
    
    return 0; 
} 

void doGray(int length, void (*take)(int*, int)) {
    int* gray = malloc(length * sizeof(int));
    init(gray, length);
    take(gray, length);
    int isOdd = 1; 
    while(!isLast(gray, length)) { 
        next(gray, length, isOdd);
        isOdd = 1 - isOdd;
        take(gray, length);
    }
    free(gray);
}

void init(int* gray, int length) {
    int i;
    for(i = 0; i < length; i++) { gray[i] = 0; } 
}

int firstOneOf(int* gray, int length) {
    int j;
    for(j = 0; gray[j] == 0; j++);
    return j;
}

void next(int* gray, int length, int isOdd) {
    int i = isOdd ? 0 : firstOneOf(gray, length) + 1;
    gray[i] = !gray[i];
}

int isLast(int* gray, int length) {
    int i;
    for(i = 0; i < length - 1; i++) if(gray[i]) { return 0; }
    return gray[i];
}

void print(int* gray, int length) {
    int j;
    for(j = length - 1; j >= 0; j--) { printf("%d", gray[j]); }
    printf("\n"); 
}
import java.util.*;

public class Gray {
    private int[] code;
    private boolean isOdd;
    public Gray(int[] code, boolean isOdd) {
        this.code = code; 
        this.isOdd = isOdd;
    }
    
    public int lastIndexOf(int elem) {
        int i;
        for(i = code.length - 1; code[i] != elem; i--);
        return i;
    }
    
    public Gray next() {
        int[] next = new int[0];
        int i = (isOdd ? code.length : lastIndexOf(1)) - 1;
        if(i != -1) {
            next = Arrays.copyOf(code, code.length);
            next[i] = 1 - next[i];
        }
        return new Gray(next, !isOdd);
    }
    
    public boolean isEmpty() { return code.length == 0; }

    public String toString() {
        return Arrays.toString(code) + (isOdd ? " odd" : " even");
    }
    
    public static List<Gray> gray(int length) {
        List<Gray> grays = new ArrayList<>();
        Gray gray = new Gray(new int[4], true);
        do { grays.add(gray); } while(!(gray = gray.next()).isEmpty());
        return grays;
    }

    public static void main(String[] args) {
        for(Gray gray : gray(4)) { System.out.println(gray); }
    }
}
class Gray:
    def __init__(self, code, isOdd):
        self.code = code
        self.isOdd = isOdd
        
    def lastIndexOf(self, elem):
        return len(self.code) - 1 - self.code[::-1].index(elem)
    
    def next(self):
        i = (len(self.code) if self.isOdd 
                            else self.lastIndexOf(1)) - 1
        return Gray(
            [] if i == -1 \
               else self.code[0:i] + [1 - self.code[i]] + self.code[i + 1:],
               not self.isOdd)
    
    def isEmpty(self):
        return len(self.code) == 0
               
    def __str__(self):
        return str(self.code) + (' odd' if self.isOdd else ' even')
        
def gray(length):
    def successors(gray):
        nx = gray.next()
        return [] if nx.isEmpty() else [nx] + successors(nx)
            
    init = Gray([0] * length, True)
    return [init] + successors(init)
    
for code in gray(4):
    print(code)
class Gray(code: List[Int], isOdd: Boolean) {
    def next = {
        val i = (if(isOdd) code.size else code.lastIndexOf(1)) - 1
        new Gray(
            if(i == -1) Nil
            else code.take(i) ++ 
             ((1 - code(i)) :: code.drop(i + 1)), !isOdd)
    }
    def isEmpty = code.isEmpty
    override def toString = 
        code.toString.replace("List", if(isOdd) "Odd  " else "Even ")
}

def gray(length: Int) = {
    def successors(gray: Gray): List[Gray] = {
        val nx = gray.next
        if(nx.isEmpty) Nil else nx :: successors(nx)
    }
    
    val init = new Gray((for(i <- 0 until length) yield 0).toList, true)
    init :: successors(init)
}

gray(4).foreach(println)
class Gray
    def initialize(code, isOdd)
        @code = code
        @isOdd = isOdd
    end
    
    def next
        i = @isOdd ? @code.size - 1 : @code.rindex(1) - 1
        Gray.new(i == -1 ? [] : 
            @code.take(i) + [1 - @code[i]] + @code.drop(i + 1), !@isOdd)
    end
    
    def empty?
        @code.empty?
    end
    
    def to_s
        "#{@code.to_s + (@isOdd ? ' odd' : ' even')}"
    end
end
        
def gray(length)
    successors = ->(gray) {
        nx = gray.next
        nx.empty? ? [] : [nx] + successors.call(nx)
    }
            
    init = Gray.new([0] * length, true)
    [init] + successors.call(init)
end
    
gray(4).each do |code|
    print("#{code}\n")
end
function Gray(code, isOdd) {
    this.code = code;
    this.isOdd = isOdd;
}

Gray.prototype.toString = function() {
    return this.code + (this.isOdd ? ' odd' : ' even');
};

Gray.prototype.next = function() {
    var i = (this.isOdd ? this.code.length : this.code.lastIndexOf(1)) - 1;
    return new Gray(i === -1 ? [] : 
               this.code.slice(0, i)
                        .concat([1 - this.code[i]])
                        .concat(this.code.slice(
                            i + 1, this.code.length)), 
           !this.isOdd);
};

function gray(length) {
    function successors(gray) {
        var nx = gray.next();
        return nx.code.length === 0 ? [] : [nx].concat(successors(nx));
    }
    var init = new Gray(new Array(length + 1)
                                .join(0)
                                .split('')
                                .map(function() {return 0;}), 
               true);
    return [init].concat(successors(init));
}

gray(4).forEach(function(code) {
    alert(code);
});
data Code = Gray [Int] Bool

instance Show Code where
    show (Gray code isOdd) = 
        show code ++ if isOdd then " odd" else " even"

lastIndexOfOne code =
    if last code == 1 then length code - 1
    else lastIndexOfOne \$ init code
    
succ' (Gray digits isOdd) =
    let i = if isOdd then length digits - 1
            else lastIndexOfOne digits - 1
    in Gray (next digits i) (not isOdd)
    where 
        next digits i =
            if i == -1 then []
            else take i digits ++ 
                 ((1 - digits !! i) : drop (i + 1) digits)

gray length =
    let hd = Gray (replicate length 0) (True)
    in hd : successors hd
    where
        successors gray@(Gray digits isOdd) =
            let nx@(Gray code _) = succ' gray
            in if code == [] then []
               else nx : (successors nx)
               
main = sequence [print code | code <- gray 4]