グレイコード

グレイコード（英: Gray code、交番二進符号（こうばんにしんふごう、英：Reflected Binary Codeなどとも）とは、数値の符号化法のひとつで、前後に隣接する符号間のハミング距離が必ず1であるという特性を持つ。ディジタル回路や、具体例としてはアブソリュート・ロータリー・エンコーダーのセンサー出力等に使われる。 Reflected Binary Codeという表現はベル研究所のフランク・グレイ（Frank Gray）による1947年の特許出願書にある。1953年に他の人物が提出した特許出願書ではグレイコードと呼ばれているほか、他の呼称も使われている。人名に由来するのであって「灰色コード」ではないため、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 通りがある（一般に、任意の有限小数は、このような二通りの無限小数として表現できる）。二進法では、1010.000000... と 1001.111111... の 2 種類があることになるが、この時、ある桁から下が、0 と 1 が反転したパターンになってしまう。これを、グレイコードを使って、最初の一桁だけが不定となった後、残りの桁は一致するように表現できる。 位相偏移変調において、差動(差分)位相偏移変調(DPSK)や四位相偏移変調(QPSK)のアルゴリズムに応用されている。 ｎ進グレイコード（英: n-ary Gray code ｎ進グレイ符号）とは交番ｎ進符号（こうばんえぬしんふごう）、ノンブーリアングレイコード(英: non-Boolean Gray code ノンブーリアングレイ符号）ともいい、グレイコードの二進法からｎ進法（位取り記数法)への拡張である。 (n, k)グレイコードはｎ進グレイコードのｋビットでの表記を意味する。 三進法での拡張グレイコード、三進グレイコードでは０、１、２を用いる。2ビットでは{00, 01, 02, 12, 10, 11, 21, 22, 20}である。 前後に隣接する符号間のハミング距離が必ず1であるという特性を持つ符号化は、グレイコードだけではない。ここでは、十進法との相性を考慮した符号化である、Glixon code、O'Brien codes、Petherick code、Tompkins codeを紹介する。 グレイコードとほぼ同じであるが、9に対応する符号はグレイコードが「1101」である一方、 Glixon code では「1000」となっている。これにより、9と0の変化においてもハミング距離が1となる。 Glixon code と同様、9と0の変化においてもハミング距離が1となる。0に対して「0000」を対応させない符号化の1つ。 最上位ビットを反転させることで、9の補数（nに対して10-n）となるような符号化の１つ。 Glixon code と同様、9と0の変化においてもハミング距離が1となる。0に対して「0000」を対応させない符号化の1つ。 最上位ビットを反転させることで、9の補数（nに対して10-n）となるような符号化の１つ。 Glixon code と同様、9と0の変化においてもハミング距離が1となる。0に対して「0000」を対応させない符号化の1つ。 最上位ビットを反転させることで、9の補数（nに対して10-n）となるような符号化の１つ。 さらに、最下位ビット以外の全てのビットにおいて、1である割合が1/2となっている（最下位ビットは6/10の割合で1である）。 ^ アメリカ合衆国特許第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). ^ グレイコードと実数 立木秀樹