グレイコード

出典: フリー百科事典『ウィキペディア(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であるという特性を持つ。デジタル回路や、具体例としてはアブソリュート・ロータリー・エンコーダーのセンサー出力等に使われる。

交番二進符号の名はベル研究所フランク・グレイが1947年の特許出願書で使用したのが最初である[1]。1953年に他の人物が提出した特許出願書ではフランク・グレイにちなんでグレイコードと呼ばれている[2][3]ほか、他の呼称も使われている[3]。人名に由来するのであって「灰色コード」ではないため、grey code(灰色を意味するグレイはgreyともgrayとも綴る)と書くのは誤りである。

2進数からグレイコードへ変換する方法[編集]

「変換したい2進数」と、「変換したい2進数を1ビット右にシフトし、先頭に0をつけたもの」との排他的論理和をとる。例えば、変換したい2進数が「1010」であれば、「0101」との排他的論理和をとる。その結果、グレイコードは「1111」になる。

プログラミングでは、ビットシフトと排他論理和のループで変換できる。C言語では、v ^ (v >> 1) で変換できる。

利点[編集]

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

一般的な2進数では、隣接する値に移行する際に変化するビットの数は1以上である。たとえば3から4に変化する場合、2進数だと011から100に、3ビットの変化が起こる。

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

011 → 010 → 000 → 100

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

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

実践的利用 [編集]

ハノイの塔 [編集]

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

遺伝的アルゴリズム[編集]

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

ロータリエンコーダ[編集]

Encoder Disc (3-Bit).svg

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

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

実数の表現[編集]

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

n進グレイコード [編集]

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}である。

三進数 ->

三進グレイコード

  0 -> 000
  1 -> 001
  2 -> 002
 10 -> 012
 11 -> 010
 12 -> 011
 20 -> 021
 21 -> 022
 22 -> 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

脚注[編集]

  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. ^ グレイコードと実数 立木秀樹