グレイコード
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とも綴る）と書くのは誤りである。
目次 |
２進数からグレイコードへ変換する方法 [編集]
「変換したい２進数」と、「変換したい２進数を１ビット右にシフトし、先頭に０をつけたもの」との排他的論理和をとる。例えば、変換したい２進数が「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）、いかなるタイミングで読み出そうとデータの値は以前の値か次の値であり、偽データが生成されることはない。
実践的利用 [編集]
ハノイの塔 [編集]
ハノイの塔においてグレイコードによって表記された数字の一番下の桁に一番小さい円盤、次の数字に二番目の円盤というようにすべての桁と円盤を対応付けたとき、数字が変化することによって変わるビットに対応する円盤を動かすことで解答が求められる。
遺伝的アルゴリズム [編集]
遺伝的アルゴリズムや分布推定アルゴリズムなどにおいて、数値を表現するのに、グレイコードが使われることがある。多くの場合、結果が改善される。
ロータリエンコーダ [編集]
.svg)
電気接点式のロータリエンコーダについて考える。
金属などの導体をむき出しにしたパターンを円盤に付け、それを複数のブラシで読み取り角度を得るものとする。この時、角度が変化して丁度境目の部分にブラシがあると、接触が不安定で、読み取りデータが1になるかもしれないし0になるかもしれない。しかし、左の図のようにグレイコードを基にしたパターンを使用すれば、不安定になるビットは必ず1ビットだけであり、角度の検出としては安定した結果を得られる。
実数の表現 [編集]
数学的には、実数の 10 の表現には 10.000000... と 9.999999... の 2 通りがある（一般に、任意の有限小数は、このような二通りの無限小数として表現できる）。二進法では、1010.000000... と 1001.111111... の 2 種類があることになるが、この時、ある桁から下が、0 と 1 が反転したパターンになってしまう。これを、グレイコードを使って、最初の一桁だけが不定となった後、残りの桁は一致するように表現できる[4]。
ｎ進グレイコード [編集]
ｎ進グレイコード（英: n-ary Gray code ｎ進グレイ符号）とは交番ｎ進符号（こうばんえぬしんふごう）、ノンブーリーングレイコード(英: non-Boolean Gray code ノンブーリーングレイ符号）ともいい、グレイコードの二進法からｎ進法（位取り記数法)への拡張である。
(n, k)グレイコードはｎ進グレイコードのｋビットでの表記を意味する。
三進法での拡張グレイコード、三進グレイコードでは０、１、２を用いる。2ビットでは{00, 01, 02, 12, 10, 11, 21, 22, 20}である。
|
脚注 [編集]
- ^ アメリカ合衆国特許第2,632,058号、F. Gray. Pulse code communication, March 17, 1953 (filed Nov. 1947).
- ^ アメリカ合衆国特許第2,733,432号、J. Breckman. Encoding Circuit, Jan 31, 1956 (filed Dec. 1953).
- ^ a b アメリカ合衆国特許第2,823,345号、E. A. Ragland et al. Direction-Sensitive Binary Code Position Control System, Feb. 11, 1958 (filed Oct. 1953).
- ^ グレイコードと実数 立木秀樹
 |
この項目は、コンピュータに関連した書きかけの項目です。この記事を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |
