コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

グレイコード

出典: フリー百科事典『ウィキペディア(Wikipedia)』
グレイ・コードから転送)
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

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

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

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

[編集]

通常の二進表現をグレイコードに変換するには、「対象の二進表現」と、「それを1ビット右シフトし、先頭に0をつけたもの」との排他的論理和をとる。例えば、変換したい対象が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進グレイコードのkビットでの表記を意味する。

三進法での拡張グレイコード、三進グレイコードでは0、1、2を用いる。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)となるような符号化の1つ。

Petherick code

[編集]

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

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. ^ a b アメリカ合衆国特許第 2,823,345号、E. A. Ragland et al. Direction-Sensitive Binary Code Position Control System, Feb. 11, 1958 (filed Oct. 1953).
  4. ^ グレイコードと実数 立木秀樹