グレイコード

グレイコード（英: Gray code、交番二進符号（こうばんにしんふごう、英：Reflected Binary Codeなどとも）とは、数値の符号化法のひとつで、前後に隣接する符号間のハミング距離が必ず1であるという特性を持つ。ディジタル回路や、具体例としてはアブソリュート・ロータリー・エンコーダーのセンサー出力等に使われる。

2ビット グレイコード 00 01 11 10

3ビット グレイコード 000 001 011 010 110 111 101 100

4ビット グレイコード 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

Reflected Binary Codeという表現はベル研究所のフランク・グレイ（Frank Gray）による1947年の特許出願書にある^[1]。1953年に他の人物が提出した特許出願書ではグレイコードと呼ばれている^[2][3]ほか、他の呼称も使われている^[3]。人名に由来するのであって「灰色コード」ではないため、grey code（灰色を意味するグレイはgreyともgrayとも綴る）と書くのは誤りである。

通常の二進表現との相互の変換

通常の二進表現をグレイコードに変換するには、「対象の二進表現」と、「それを１ビット右シフトし、先頭に０をつけたもの」との排他的論理和をとる。例えば、変換したい対象が10（十進法で）であれば、二進法で表現すれば「1010」であるから、それと「0101」との排他的論理和をとった、「1111」がグレイコードによる表現である。プログラミング言語では、例えばC言語では、v ^ (v >> 1) となる。

逆にグレイコードを通常の二進表現に変換するには、「グレイコードによる表現」の最上位桁から順に最下位桁へ向かって隣の桁との排他的論理和をとる。(ただし最上位桁のみその値を適用する。)例えば、グレイコードによる表現が「1111」であれば、最上位桁から「1」、その値(1)と次の桁(1)との排他的論理和をとり「0」、その値(0)と次の桁(1)との排他的論理和をとり「1」、その値(1)と次の桁(1)との排他的論理和をとり「0」、と順次各桁を確定し、「1010」が二進法による表現である。

利点

グレイコードは、ある値から隣接した値に変化する際に、常に1ビットしか変化しないという点が利用される。

一般的な二進法では、隣接する値に移行する際は、最下位桁だけが 0←→1 の入れ替えになる場合を除き、一般に1個以上のビットが変化する。たとえば3から4に変化する場合、011から100に、3個のビットが変化する。

絶対的な角度をディジタル値で出力するアブソリュート・ロータリー・エンコーダーのような機器において、機械的な接点などで電気信号のオンオフを行う場合を考えてみよう。この場合、機械の動作やデータ読み出しのタイミングによっては、誤ったデータが得られる可能性がある。たとえば011から100に変化する際に、短時間の間に次のように出力が遷移するかもしれない。

011 → 010 → 000 → 100

各ビットとも、変化に誤りはないのであるが、機械構造の精度上の問題で、完璧に同時に全ビットが変化することは保証できないのである。そのため遷移の途中の段階でデータを読み出すと、010（2）や000（0）といった偽データを取得してしまう可能性がある。

一般的な二進法ではなく、グレイコードを使えば、隣接値への変化の際に、常に1ビットしか変わらないので（3から4の変化であれば010から110）、いかなるタイミングで読み出そうとデータの値は以前の値か次の値であり、偽データが生成されることはない。

実践的利用

ハノイの塔

ハノイの塔においてグレイコードによって表記された数字の一番下の桁に一番小さい円盤、次の数字に二番目の円盤というようにすべての桁と円盤を対応付けたとき、数字が変化することによって変わるビットに対応する円盤を動かすことで解答が求められる。

遺伝的アルゴリズム

遺伝的アルゴリズムや分布推定アルゴリズムなどにおいて、数値を表現するのに、グレイコードが使われることがある。多くの場合、結果が改善される。

ロータリエンコーダ

電気接点式のロータリエンコーダについて考える。

金属などの導体をむき出しにしたパターンを円盤に付け、それを複数のブラシで読み取り角度を得るものとする。この時、角度が変化して丁度境目の部分にブラシがあると、接触が不安定で、読み取りデータが1になるかもしれないし0になるかもしれない。しかし、左の図のようにグレイコードを基にしたパターンを使用すれば、不安定になるビットは必ず1ビットだけであり、角度の検出としては安定した結果を得られる。

実数の表現

数学的には、実数の 10 の表現には 10.000000... と 9.999999... の 2 通りがある（一般に、任意の有限小数は、このような 2 通りの無限小数として表現できる）。二進法では、1010.000000... と 1001.111111... の 2 種類があることになるが、この時、ある桁から下が、0 と 1 が反転したパターンになってしまう。これを、グレイコードを使って、最初の一桁だけが不定となった後、残りの桁は一致するように表現できる^[4]。

位相偏移変調 (PSK)

位相偏移変調において、差動(差分)位相偏移変調(DPSK)や四位相偏移変調(QPSK)のアルゴリズムに応用されている。

n進グレイコード

通常の三進法 → 三進グレイコード 000 → 000 001 → 001 002 → 002 010 → 012 011 → 010 012 → 011 020 → 021 021 → 022 022 → 020 100 → 120 101 → 121 102 → 122 110 → 102 111 → 100 112 → 101 120 → 111 121 → 112 122 → 110 200 → 210 201 → 211 202 → 212 210 → 222 211 → 220 212 → 221 220 → 201 221 → 202 222 → 200

n進グレイコード（英: n-ary Gray code n進グレイ符号）とは交番n進符号（こうばんえぬしんふごう）、ノンブーリアングレイコード(英: non-Boolean Gray code ノンブーリアングレイ符号）ともいい、グレイコードの二進法からn進法（位取り記数法)への拡張である。

(n, k)グレイコードはn進グレイコードのｋビットでの表記を意味する。

三進法での拡張グレイコード、三進グレイコードでは０、１、２を用いる。2ビットでは{00, 01, 02, 12, 10, 11, 21, 22, 20}である。

十進に特化した符号化

前後に隣接する符号間のハミング距離が必ず1であるという特性を持つ符号化は、グレイコードだけではない。ここでは、十進法との相性を考慮した符号化である、Glixon code、O'Brien codes、Petherick code、Tompkins codeを紹介する。

十進表記	二進表記	Gray code	Glixon code	O'Brien code I	O'Brien code II	Petherick code	Tompkins code
0	0000	0000	0000	0000	0001	0101	0010
1	0001	0001	0001	0001	0011	0001	0011
2	0010	0011	0011	0011	0010	0011	0111
3	0011	0010	0010	0010	0110	0010	0101
4	0100	0110	0110	0110	0100	0110	0100
5	0101	0111	0111	1110	1100	1110	1100
6	0110	0101	0101	1010	1110	1010	1101
7	0111	0100	0100	1011	1010	1011	1001
8	1000	1100	1100	1001	1011	1001	1011
9	1001	1101	1000	1000	1001	1101	1010

Glixon code

グレイコードとほぼ同じであるが、9に対応する符号はグレイコードが「1101」である一方、 Glixon code では「1000」となっている。これにより、9と0の変化においてもハミング距離が1となる。

O'Brien codes

Glixon code と同様、9と0の変化においてもハミング距離が1となる。0に対して「0000」を対応させない符号化の1つ。 最上位ビットを反転させることで、9の補数（nに対して9-n）となるような符号化の１つ。

Petherick code

Glixon code と同様、9と0の変化においてもハミング距離が1となる。0に対して「0000」を対応させない符号化の1つ。 最上位ビットを反転させることで、9の補数（nに対して9-n）となるような符号化の１つ。

Tompkins code

Glixon code と同様、9と0の変化においてもハミング距離が1となる。0に対して「0000」を対応させない符号化の1つ。 さらに、最下位ビット以外の全てのビットにおいて、1である割合が1/2となっている（最下位ビットは6/10の割合で1である）。

脚注

1. アメリカ合衆国特許第 2,632,058号、F. Gray. Pulse code communication, March 17, 1953 (filed Nov. 1947).
2. アメリカ合衆国特許第 2,733,432号、J. Breckman. Encoding Circuit, Jan 31, 1956 (filed Dec. 1953).
3. アメリカ合衆国特許第 2,823,345号、E. A. Ragland et al. Direction-Sensitive Binary Code Position Control System, Feb. 11, 1958 (filed Oct. 1953).
4. グレイコードと実数 立木秀樹