格雷碼
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]