グレイコード

グレイコードとは

グレイコード（Gray code）は、数値の符号化方式の一種で、隣接する符号間でハミング距離が必ず1になるという特徴を持ちます。これは、符号が変化する際に常に1ビットだけが変化することを意味します。別名として、交番二進符号（Reflected Binary Code）とも呼ばれます。

この特性から、グレイコードはデジタル回路やアブソリュート・ロータリー・エンコーダーのセンサー出力など、様々な分野で利用されています。特に、機械的な接点を持つデバイスで、信号のオンオフを検出する場合に、誤ったデータ読み取りを防ぐために役立ちます。

グレイコードの起源

グレイコードという名称は、ベル研究所のフランク・グレイ（Frank Gray）が1947年に特許を出願したことに由来します。しかし、1953年には別の人物による特許出願で「グレイコード」という名称が使用されており、様々な呼称が用いられました。人名に由来するため、「灰色コード」と記述するのは誤りです。

通常の二進表現との変換

グレイコードと通常の二進表現は、相互に変換することができます。

二進法からグレイコードへの変換

二進表現をグレイコードに変換するには、元の二進数と、それを1ビット右にシフト（最上位ビットに0を追加）した数の排他的論理和（XOR）を計算します。

例えば、10（二進法で1010）をグレイコードに変換する場合、以下のように計算します。

1010 XOR 0101 = 1111

したがって、10のグレイコード表現は1111となります。C言語などのプログラミング言語では、`v ^ (v >> 1)` のように記述することができます。

グレイコードから二進法への変換

グレイコードを二進表現に戻すには、最上位ビットから順に、隣り合うビットとの排他的論理和を計算します。最上位ビットはそのまま使用し、その値と次のビットのXORを計算し、その結果を次のビットの値として確定させます。

例えば、グレイコード表現が1111の場合、以下の手順で変換します。

• - 最上位ビットは1
• - 1 XOR 1 = 0
• - 0 XOR 1 = 1
• - 1 XOR 1 = 0

結果として、二進表現は1010となります。

グレイコードの利点

グレイコードの最大の利点は、隣接する値に変化する際に必ず1ビットしか変化しないことです。通常の二進法では、複数のビットが同時に変化するため、デジタル回路で信号の切り替わりを検出する際に、誤った値を読み取ってしまう可能性があります。

例えば、二進数で3（011）から4（100）に変化する場合、3つのビットが同時に変化します。しかし、グレイコードを使用すると、変化するビットは常に1つであるため、誤ったデータの発生を防ぐことができます。

実践的な利用例

1. アブソリュート・ロータリー・エンコーダー:
回転角をデジタル値として出力する機器で、角度の変化を正確に検出するためにグレイコードが使用されます。機械的な接点で電気信号を検出する際、ビットの変化のタイミングずれによる誤読を防ぎます。

2. ハノイの塔:
パズルゲームであるハノイの塔では、グレイコードで表現された数字と円盤を対応させ、数字が変化する際に変わるビットに対応する円盤を動かすことで、問題を解くことができます。

3. 遺伝的アルゴリズム:
最適化問題の解を探索する遺伝的アルゴリズムや分布推定アルゴリズムでは、数値を表現する際にグレイコードを使用することで、結果が改善される場合があります。

4. ロータリーエンコーダー:
電気接点式のロータリーエンコーダーでは、円盤上の導体パターンをブラシで読み取る際、接触が不安定な部分でも1ビットしか変化しないグレイコードを使用することで、安定した角度検出が可能になります。

5. 実数の表現:
実数を無限小数で表現する場合、二進法では0と1が反転したパターンが続くことがあります。グレイコードを使用することで、最初の一桁だけが不定となった後、残りの桁は一致するように表現できます。

6. 位相偏移変調 (PSK):
デジタル変調方式であるPSKでは、差動位相偏移変調(DPSK)や四位相偏移変調(QPSK)のアルゴリズムに、グレイコードが応用されています。

n進グレイコード

グレイコードは二進法だけでなく、n進法（位取り記数法）にも拡張することができます。これをn進グレイコードと呼びます。例えば、三進グレイコードでは、0、1、2の3つの数字を使用します。2ビットの三進グレイコードは、{00, 01, 02, 12, 10, 11, 21, 22, 20}となります。

十進に特化した符号化

ハミング距離が1となる符号化は、グレイコードだけではありません。十進法との相性を考慮した符号化として、Glixon code、O'Brien codes、Petherick code、Tompkins codeなどがあります。

• - Glixon code: グレイコードとほぼ同じですが、9に対応する符号が異なります。9と0の変化でハミング距離が1となるように設計されています。
• - O'Brien codes: 9と0の変化でハミング距離が1となる符号化です。0に「0000」を対応させず、最上位ビットを反転させることで、9の補数となるように設計されています。
• - Petherick code: O'Brien codesと同様に、0に「0000」を対応させず、最上位ビットを反転させることで、9の補数となるように設計されています。
• - Tompkins code: 0に「0000」を対応させず、最下位ビット以外のすべてのビットにおいて1である割合が1/2となるように設計されています。

これらの符号化は、十進数を扱う場合に、グレイコードよりも効率的な表現が可能になる場合があります。

もう一度検索