グレイコード

反射バイナリ コード( RBC ) は、フランク グレイにちなんで反射バイナリ( RB ) またはグレイ コードとも呼ばれ、連続する 2 つの値が 1ビット(2 進数)のみ異なるような2 進数値システムの順序付けです。

たとえば、10 進数値「1」を 2 進数で表すと、通常は「001」となり、「2」は「010 」となります。グレイ コードでは、これらの値は「 001」および「011 」として表されます。このように、値を 1 から 2 に増やす場合、2 ビットではなく 1 ビットのみを変更すれば済みます。

グレイコードは、電気機械式 スイッチからのスプリアス出力を防止し、地上デジタルテレビや一部のケーブルテレビシステムなどのデジタル通信におけるエラー訂正を容易にするために広く使用されています。これらのデバイスでグレイコードを使用すると、論理演算が簡素化され、実際のエラーが削減されます。^[3]

多くのデバイスは、スイッチの開閉によって位置を示します。デバイスが自然バイナリ コードを使用する場合、位置 3 と 4 は隣り合っていますが、バイナリ表現の 3 つのビットはすべて異なります。

自然なバイナリ コードの問題は、物理スイッチが理想的ではないことです。物理スイッチの状態が正確に同期して変化することはほとんどあり得ません。上に示した 2 つの状態間の遷移では、3 つのスイッチすべてが状態を変えます。すべてが変化している短い期間に、スイッチは誤った位置を読み取ります。キーバウンスがなくても、遷移は011 — 001 — 101 — 100のように見えるかもしれません。スイッチが位置001にあるように見える場合、観察者はそれが「実際の」位置 1 なのか、他の 2 つの位置間の遷移状態なのかを判断できません。出力が、おそらく組み合わせロジックを介して順次システムに入力されると、順次システムは誤った値を格納する可能性があります。

この問題は、一度に 1 つのスイッチだけを変更することで解決できるため、位置の曖昧さがなくなり、連続する整数セットのそれぞれ、または循環リストの各メンバーに、2 つのコードワードが同一ではなく、隣接する 2 つのコードワードが正確に 1 つのシンボルだけ異なるようなシンボルのワードを割り当てるコードが生まれます。これらのコードは、隣接するコード間のハミング距離が 1 であることから、単位距離^{[4] [5 ] [6] [7] [8]、} 単一距離、シングルステップ、モノストロフィック^{[9] [ 10] [7] [8]}またはシンコピック コード^[9]としても知られています。

原則として、与えられたワード長に対して複数のそのようなコードが存在する可能性があるが、グレイコードという用語は、負でない整数の特定のバイナリコード、バイナリ反射グレイコード、またはBRGCに最初に適用された。ベル研究所の研究者である ジョージ・R・スティビッツは、1943年に付与された1941年の特許出願でそのようなコードについて説明した。 ^{[11] [12] [13]} フランク・グレイは、1947年の特許出願で反射バイナリコードという用語を導入し、そのコードには「まだ認識された名前がない」と述べた。^[14]彼は、それが「一種の反射プロセスによって従来のバイナリコードから構築される可能性がある」という事実からその名前を導き出した。

グレイ コードの標準的なエンコードでは、最下位ビットは 2 オン、2 オフ(… 11001100 …) の繰り返しパターンに従います。次の桁は 4 オン、4 オフのパターン、最下位のi番目のビットは 2 ⁱオン、2 ⁱオフのパターンです。最上位桁は例外です。nビットのグレイ コードの場合、最上位桁は 2 ^{n -1}オン、2 ^{n -1}オフのパターンに従います。これは、2 番目に重要な桁と同じ (循環的な) 値のシーケンスですが、2 ^{n -2}桁前方にシフトされています。これを 4 ビット バージョンにしたものが以下です。

10進数の15の場合、コードはスイッチを1回変更するだけで10進数の0にロールオーバーします。これはコードの循環性または隣接性と呼ばれます。 ^[15]

現代のデジタル通信では、グレイ コードはエラー訂正において重要な役割を果たします。たとえば、データが通常4 ビット以上のシンボルで送信されるQAMなどのデジタル変調方式では、信号の星座図は、隣接する星座点によって運ばれるビット パターンが 1 ビットだけ異なるように配置されます。これを、単一ビット エラーを訂正できる前方誤り訂正と組み合わせると、受信機は、星座点が隣接する点の領域に逸脱する原因となる伝送エラーを訂正できます。これにより、伝送システムはノイズの影響を受けにくくなります。

スティビッツがこのコードをグレイより前に記述していたにもかかわらず^{[11] [12] [13]}、反射バイナリコードは後にそれを使用した他の人によってグレイにちなんで名付けられました。 1953年の2つの異なる特許出願では、「反射バイナリコード」の別名として「グレイコード」が使用されています。 ^{[16] [17]}そのうちの1つには、「最小エラーコード」と「巡回置換コード」も名前に含まれています。 ^[17] 1954年の特許出願では「ベル電話グレイコード」に言及しています。^[18]他の名前には「巡回バイナリコード」、^「巡回進行コード」、「巡回置換バイナリ」 ^{[19] [12]}「巡回置換バイナリ」^[20]または「巡回置換バイナリ」（CPB）などがあります。^{[21] [22]}

グレイコードは、19世紀の電気機器発明家エリシャ・グレイに誤って帰属されることがある。^{[13] [23] [24] [25]}

反射バイナリコードは、エンジニアに知られるようになる前から数学パズルに適用されていました。

バイナリ反射グレイコードは、1872年にフランスのルイ・グロによって記述された連続的な機械的なパズルのメカニズムである古典的な中国のリングパズルの基本的なスキームを表しています。 ^{[26] [13]}

これは、 1883年にフランスのエドゥアール・ルーカスが考案したゲームに基づいたハノイの塔問題の解決ガイドとして役立ちます。^{[27] [28] [29] [30]}同様に、いわゆるブカレストの塔とクラーゲンフルトの塔のゲーム構成では、3進法と5進法のグレイコードが生成されます。^[31]

マーティン・ガードナーは1972年8月にサイエンティフィック・アメリカン誌の「数学ゲーム」コラムでグレイコードについての一般向け解説を書いた。^[32]

このコードは、各ビットが 1 次元として見られるハイパーキューブ上のハミルトン サイクルも形成します。

フランスの技術者エミール・ボードが1875年^[33]または1876年に印刷電信システムで6単位（6ビット）コードから5単位コードに変更したとき[ ^{34] [35]、}彼は反転バイナリコードを使用して印刷ホイール上のアルファベット文字を順序付けし、3ビットのみを使用してコードを母音に割り当てました。母音と子音がアルファベット順に並べられ、^{[36] [37] [38]}、他の記号が適切に配置され、5ビット文字コードは反転バイナリコードとして認識されました。^[13]このコードはボードコードとして知られるようになり^{[39] 、小さな変更を加えて、最終的に1932年に}国際電信アルファベットNo.1（ITA1、CCITT-1）として採用されました。 ^{[40] [41] [38]}

ほぼ同じ頃、ドイツ系オーストリア人のオットー・シェフラー [de] ^[42]は、1874年にウィーンで同じ目的で5ビットの反射バイナリコードを使用した別の印刷電信機を実演しました。^{[43] [13]}

互換カラーテレビに使用されるようになった信号方式を発明したことで有名になったフランク・グレイは、真空管ベースの装置を使用してアナログ信号を反射バイナリコードグループに変換する方法を発明しました。1947年に出願されたこの方法と装置は1953年に特許を取得しました。^[14]コードにはグレイの名前が付けられました。グレイが特許を取得した「PCMチューブ」装置は、ベル研究所のレイモンド・W・シアーズがグレイとウィリアム・M・グドールと協力して作ったもので、反射バイナリコードのアイデアはグレイの功績であるとされています。^[44]

グレイは、アナログ信号をデジタルに変換する際のエラーを最小限に抑えるためにコードを使用することに最も興味を持っていました。彼のコードは今日でもこの目的で使用されています。

グレイ コードは、加重バイナリ エンコーディングよりも優先して、リニアおよびロータリー位置エンコーダ (アブソリュート エンコーダおよびクアドラチャ エンコーダ) で使用されます。これにより、位置のバイナリ表現で複数のビットが変化する場合に、一部のビットが他のビットよりも先に変化して誤読が発生する可能性が回避されます。

たとえば、一部のロータリー エンコーダーは、同心円 (トラック) 上に導電性のグレー コード パターンを持つディスクを備えています。各トラックには、導電性コード パターンに電気的に接触する固定金属スプリング コンタクトがあります。これらのコンタクトが一緒になって、グレー コードの形式で出力信号を生成します。その他のエンコーダーは、光学センサーまたは磁気センサーに基づく非接触メカニズムを使用して、グレー コード出力信号を生成します。

可動エンコーダのメカニズムや精度に関係なく、コードが読み取られる (サンプリングされる) 瞬間にコードが変化する可能性があるため、特定の位置 (コード境界) で位置測定エラーが発生する可能性があります。バイナリ出力コードでは、すべてのビットを正確に同時に変化させることが不可能なため、重大な位置測定エラーが発生する可能性があります。位置がサンプリングされる瞬間に、一部のビットが変化し、他のビットが変化していない場合、サンプリングされた位置は不正確になります。絶対エンコーダの場合、示された位置は実際の位置から大きく離れている可能性があり、増分エンコーダの場合、位置の追跡が損なわれる可能性があります。

対照的に、位置エンコーダで使用されるグレイ コードでは、連続する 2 つの位置のコードが 1 ビットだけ異なることが保証され、その結果、一度に変更できるのは 1 ビットだけです。この場合、最大位置誤差は小さくなり、実際の位置に隣接する位置を示します。

グレイコードはハミング距離の特性を持つため、遺伝的アルゴリズムで使用されることがあります。^[15]コードの突然変異によって大部分は漸進的な変化が可能ですが、時折1ビットの変更で大きな飛躍が起こり、新しい特性につながることがあるため、この分野では非常に有用です。

グレイコードは、1953年以来カルノー図の軸のラベル付けにも使用されており^{[45] [46] [47]}、1958年以来ヘンドラー円グラフにも使用されている^{[48] [49] [50] [51]。どちらも}論理回路の最小化のためのグラフィカルな手法である。

現代のデジタル通信では、1D および 2D グレイ コードは、エラー訂正を適用する前のエラー防止において重要な役割を果たします。たとえば、データが通常4 ビット以上のシンボルで送信されるQAMなどのデジタル変調方式では、信号の星座図は、隣接する星座点によって運ばれるビット パターンが1ビットだけ異なるように配置されます。これを、単一ビット エラーを訂正できる前方誤り訂正と組み合わせることで、受信機は、星座点が隣接する点の領域に逸脱する原因となる伝送エラーを訂正できます。これにより、伝送システムはノイズの影響を受けにくくなります。

• 
  コード 4-PSK
• 
  コード 8-PSK
• 
  コード 16-QAM

デジタル ロジック設計者は、異なるクロック周波数で動作する同期ロジック間でマルチビット カウント情報を渡すために、グレイ コードを広く使用します。このロジックは、異なる「クロック ドメイン」で動作するものと見なされます。これは、さまざまなクロック周波数で動作する大型チップの設計の基本です。

システムが、一連の制御のオン/オフ状態のすべての可能な組み合わせを順番に循環させる必要があり、制御の変更にかなりの費用 (時間、磨耗、人的作業など) がかかる場合、グレイ コードを使用すると、設定変更の回数が状態の組み合わせごとに 1 回だけに変更されます。例としては、配管システムの手動操作バルブの設定のすべての組み合わせをテストすることが挙げられます。

バランスのとれたグレイコード[ ^52]は、すべてのビットを同じ頻度で反転するコードです。ビット反転は均等に分散されるため、次のように最適になります。バランスのとれたグレイコードは、各桁のビット反転の最大回数を最小限に抑えます。

ジョージ・R・スティビッツは1941年にすでに2進パルスカウント装置に反射バイナリコードを使用していました。^{[11] [12] [13]}

グレイ コード カウンターの一般的な用途は、異なるクロック ドメインに存在する読み取りポートと書き込みポートを持つFIFO (先入先出) データ バッファーを構築することです。このようなデュアル ポート FIFO 内の入力カウンターと出力カウンターは、カウントがクロック ドメインをまたぐときに無効な過渡状態がキャプチャされるのを防ぐために、グレイ コードを使用して格納されることがよくあります。^[53] 更新された読み取りポインタと書き込みポインタは、各ドメインの FIFO の空と満杯のステータスを追跡できるように、変更時にクロック ドメイン間で渡す必要があります。このクロック ドメイン転送では、ポインタの各ビットが非決定論的にサンプリングされます。したがって、各ビットについて、古い値または新しい値のいずれかが伝播されます。したがって、サンプリング ポイントでマルチビット ポインタの複数のビットが変化すると、「間違った」バイナリ値 (新しい値でも古い値でもない) が伝播される可能性があります。グレイ コードは、1 つのビットだけが変化することを保証することで、サンプリングされる可能性のある値が新しいマルチビット値または古いマルチビット値のみであることを保証します。通常、2 の累乗の長さのグレイ コードが使用されます。

電子システムのデジタル バスは、一度に 1 つずつしか増加または減少できない量を伝達するために使用されることがあります。たとえば、クロック ドメイン間またはデジタル - アナログ コンバーターに渡されるイベント カウンターの出力などです。これらのアプリケーションでのグレイ コードの利点は、コードのビットを表す多数の配線の伝播遅延の違いによって、受信値がグレイ コード シーケンスから外れた状態になることがないことです。これは、機械式エンコーダーの構築におけるグレイ コードの利点に似ていますが、この場合のグレイ コードのソースは電子カウンターです。カウンター自体はグレイ コードでカウントする必要があります。または、カウンターがバイナリで動作する場合は、カウンターからの出力値をグレイ コードに変換した後に再クロックする必要があります。これは、値がバイナリからグレイ コードに変換されるときに、^{[注 1]}バイナリ データ ビットがバイナリ - グレイ変換回路に到着する時間の違いによって、コードが一時的に大幅にシーケンスから外れた状態になる可能性があるためです。カウント値をグレイコードに変換する回路の後にクロックレジスタを追加すると、クロックサイクルの遅延が発生する可能性があるため、グレイコードで直接カウントする方が有利な場合があります。^[54]

グレイコードカウンタで次のカウント値を生成するには、保存されている現在のカウント値を増分する組み合わせロジックが必要です。グレイコード番号を増分する方法の1つは、それを通常のバイナリコードに変換し、^[55]標準のバイナリ加算器でそれに1を加算し、結果を再びグレイコードに変換することです。^{[56]グレイコードでカウントする他の方法は、}ロバートW.ドランによるレポートで説明されており、バイナリリップルカウンタのマスタースレーブフリップフロップの最初のラッチから出力を取得する方法も含まれています。^[57]

プログラムコードの実行により、通常、ローカルに連続したアドレスの命令メモリアクセスパターンが発生するため、バイナリアドレス指定の代わりにグレイコードアドレス指定を使用するバスエンコーディングにより、アドレスビットの状態変化の回数を大幅に減らすことができ、低電力設計ではCPUの消費電力を削減できます。 ^{[58] [59]}

nビットのバイナリ反射グレイコードリストは、n − 1ビットのリストからリストを 反射（つまり、逆順にエントリをリストする）し、元のリストのエントリの前にバイナリ0を付け、反射リストのエントリの前にバイナリ 1を付け、元のリストと反転リストを連結することによって再帰的に生成できます。 ^[13] たとえば、n  = 2のリスト からn  = 3のリストを生成するには、次のようにします。

1 ビットのグレイ コードはG ₁  = ( 0,1 ) です。これは、 長さ 0 の単一エントリで構成される0 ビットのグレイ コードG ₀  = (  Λ ) から上記のように再帰的に構築されるものと考えることができます。G _nからG _{n +1 を生成するこの反復プロセスにより、標準反射コードの次の特性}が明らかになります。

• G _{n は}、0、...、2 ⁿ − 1 の順列です 。(各数字はリスト内に 1 回だけ出現します。)
• G _{n は}G _{n +1}の前半として埋め込まれます。
• したがって、バイナリ数がG _nに一度現れると、より長いリストすべてで同じ位置に現れるという意味で、コーディングは安定しています。したがって、数値の反射グレイ コード値について話すことは理にかなっています。G ( m ) = 0から数えてm番目の反射グレイ コード。
• G _nの各エントリは、前のエントリと 1 ビットだけ異なります。(ハミング距離は 1 です。)
• G _nの最後のエントリは、最初のエントリと 1 ビットだけ異なります。(コードは循環的です。)

これらの特性は、バイナリ値を対応するグレイコードに変換する簡単で高速な方法を示唆しています。入力値の次の上位ビットが 1 に設定されている場合、各ビットは反転されます。これは、ビットシフトと排他的論理和演算が利用可能な場合は、それらを並列に実行できます。n番目のグレイコードは、を計算することで取得されます。先頭に0ビットを追加してもコードワードの順序は変更されませんが、先頭に1ビットを追加するとコードワードの順序が逆になります。コードワードの位置のビットが反転すると、隣接するコードワードブロックの順序が逆になります。たとえば、3 ビットのコードワードシーケンスでビット 0 が反転すると、隣接する 2 つのコードワードの順序が逆になります。 ${\displaystyle n\oplus \left\lfloor {\tfrac {n}{2}}\right\rfloor }$${\displaystyle i}$${\displaystyle 2^{i}}$

000,001,010,011,100,101,110,111 → 001,000,011,010,101,100,111,110  (ビット 0 を反転)

ビット 1 が反転すると、2 つのコードワードのブロックの順序が変わります。

000,001,010,011,100,101,110,111 → 010,011,000,001,110,111,100,101  (ビット 1 を反転)

ビット 2 が反転されている場合、4 つのコードワードのブロックの順序は逆になります。

000,001,010,011,100,101,110,111 → 100,101,110,111,000,001,010,011  (ビット 2 を反転)

したがって、位置 のビットと位置 のビットに対して排他的論理和を実行すると、の場合はコードワードの順序がそのまま残り、の場合はコードワードのブロックの順序が逆になります。これは、グレイ コードを生成するためのリフレクト アンド プレフィックス法とまったく同じ操作です。 ${\displaystyle b_{i}}$${\displaystyle i}$${\displaystyle b_{i+1}}$${\displaystyle i+1}$${\displaystyle b_{i+1}={\mathtt {0}}}$${\displaystyle 2^{i+1}}$${\displaystyle b_{i+1}={\mathtt {1}}}$

逆変換を実行するのに同様の方法を使用できますが、各ビットの計算は次の上位ビットの計算値に依存するため、並列に実行することはできません。 が 番目のグレイコード化ビット（は最上位ビット）であり、 が番目のバイナリコード化ビット（は最上位ビット）であると仮定すると、逆変換は、 、 と再帰的に表すことができます。 あるいは、グレイ コードをバイナリ数にデコードすることは、グレイ コードのビットのプレフィックス合計として記述でき、プレフィックス合計内の個々の合計演算はそれぞれ 2 を法として実行されます。 ${\displaystyle g_{i}}$${\displaystyle i}$${\displaystyle g_{0}}$${\displaystyle b_{i}}$${\displaystyle i}$${\displaystyle b_{0}}$${\displaystyle b_{0}=g_{0}}$${\displaystyle b_{i}=g_{i}\oplus b_{i-1}}$

バイナリ反射グレイコードを繰り返し構築するには、ステップ 0 で から開始し、ステップ で のバイナリ表現における最下位1のビット位置を見つけ、前のコードにおけるその位置のビットを反転して次のコードを取得します。ビット位置は 0、1、0、2、0、1、0、3、... で始まります。 ^{[注 2]}これらの値を計算するための効率的なアルゴリズムについては、 「最初のセットの検索」を参照してください。${\displaystyle \mathrm {コード} _{0}={\mathtt {0}}}$${\displaystyle i>0}$${\displaystyle i}$${\displaystyle \mathrm {コード} _{i-1}}$${\displaystyle \mathrm {コード} _{i}}$

以下のC関数は、2進数とそれに関連するグレイコード間の変換を行います。グレイコードから2進数への変換では、各ビットを1つずつ処理する必要があるように思われますが、より高速なアルゴリズムが存在します。^{[60] [55] [注 1]}

typedef unsigned int uint ;   

// この関数は、符号なし 2 進数を反転 2 進グレイ コードに変換します。uint 
BinaryToGray ( uint num ) { return num ^ ( num >> 1 ); // 演算子 >> は右シフトです。演算子^は排他的論理和です。}  

          


// この関数は、反射された 2 進グレイコード数を 2 進数に変換します。
uint GrayToBinary ( uint num ) { uint mask = num ; while ( mask ) { // 各グレイコードビットは、すべての上位ビットと排他的論理和されます。mask >>= 1 ; num ^= mask ; } return num ; }  

       
                 
          
            
    
     


// SWAR (レジスタ内の SIMD) 技術を使用した、32 ビット以下のグレイ コード用のより効率的なバージョンです。
// 並列プレフィックス XOR 関数を実装します。割り当てステートメントは任意の順序にすることができます。
// 
// この関数は、ステップを追加することで、より長いグレイ コードに適応できます。

uint GrayToBinary32 ( uint num ) { num ^= num >> 16 ; num ^= num >> 8 ; num ^= num >> 4 ; num ^= num >> 2 ; num ^= num >> 1 ; return num ; } // 4 ビット一括変換バリアントでは、2 進数 (abcd)2 を (abcd)2 ^ (00ab)2 に変更し、次に (abcd)2 ^ (00ab)2 ^ (0abc)2 ^ (000a)2 に変更します。  

        
         
         
         
         
     

新しいプロセッサでは、 CLMUL 命令セットを利用することで、デコード手順における ALU 命令の数を減らすことができます。MASK が 1 つのゼロで終わる定数バイナリ文字列である場合、MASK と x のグレー エンコーディングとのキャリーレス乗算により、常に x またはそのビット否定が得られます。

実際には、「グレイ コード」はほとんどの場合、バイナリ反射グレイ コード (BRGC) を指します。ただし、数学者は他の種類のグレイ コードを発見しました。BRGC と同様に、各グレイ コードは単語のリストで構成され、各単語は次の単語と 1 桁だけ異なります (各単語と次の単語の ハミング距離は 1 です)。

長さが偶数であれば、nビットで長さが2n未満である2進グレイコードを構成することは可能である。1^つの可能性は、バランスの取れたグレイコードから始めて、先頭と末尾、または中間の値のペアを^{削除することである。 [61]} OEISシーケンスA290772 ^[62]は、ゼロを含み、最小のビット数を使用する 長さ2nのグレイシーケンスの可能な数を示している。

バイナリ反射グレイ コード以外にも、多くの特殊なタイプのグレイ コードがあります。そのようなタイプのグレイ コードの 1 つに、非ブール グレイ コードとも呼ばれるn進グレイ コードがあります。名前が示すように、このタイプのグレイ コードは、エンコードに 非ブール値を使用します。

例えば、3進（三進）グレイコードでは、0、1、2 という値が使用されます。^[31] ( n、  k )-グレイコードは、 k桁のn進グレイコードです。^[63] (3、2)-グレイコードの要素のシーケンスは、00、01、02、12、11、10、20、21、22 です。( n、  k )-グレイコードは、BRGC のように再帰的に構築することも、反復的に構築することもできます。 ( N、  k )-グレイコードを反復的に生成するアルゴリズムが示されています（ Cで）。

// 入力: 基数、桁数、値
// 出力: Gray 
// 指定された基数と桁数を使用して、値をグレイ コードに変換します。//
値のシーケンスを反復処理すると、
一度に 1 桁のみが変更されるグレイ コードのシーケンスが生成されます。void 
toGray ( unsigned base 、unsigned digits 、unsigned value 、unsigned gray [桁数]) { unsigned baseN [桁数]; // 通常の基数 N の数値 (エントリごとに 1 桁) を格納しますunsigned i ; // ループ変数// 通常の基数 N の数値を baseN 配列に格納します。基数 10 の場合、109 // は [9,0,1] として格納されますfor ( i = 0 ; i < digits ; i ++ ) { baseN [ i ] = value % base ; value = value / base ; } // 通常の基数 N の数値をグレイ コードの同等の値に変換します。ループは最上位桁から開始して下っていくことに注意してください。 unsigned shift = 0 ; while ( i -- ) { // Gray の数字は上位の数字の合計だけシフトダウンされます。 gray [ i ] = ( baseN [ i ] + shift ) % base ; shift = shift + base - gray [ i ]; // base から減算して shift が正になるようにします} } // 例// 入力: value = 1899、base = 10、digits = 4 // 出力: baseN[] = [9,9,8,1]、gray[] = [0,1,7,1] // 入力: value = 1900、base = 10、digits = 4 // 出力: baseN[] = [0,0,9,1]、gray[] = [0,1,8,1]        
 
	 	
	 		
 
	
	
	        
		    
		       
	
 
	
	
	   
	  
		
		
		      
		      	
	

( n , k )-グレイコードには他のグレイコードアルゴリズムもあります。上記のアルゴリズムで生成される( n , k )-グレイコードは常に循環的です。Guan ^[63]などのアルゴリズムでは、kが奇数の場合にこの特性がありません。一方、この方法では一度に1桁しか変化しませんが、ラップ（n  -1から0へのループ）によって変化することができます。Guanのアルゴリズムでは、カウントが交互に増減するため、2つのグレイコード桁の数値差は常に1になります。

グレイ コードは一意に定義されません。このようなコードの列の順列もグレイ コードだからです。上記の手順により、桁の重要度が低いほど頻繁に変化するコードが生成され、通常のカウント方法に似たものになります。

スキュー2進数システムも参照してください。これは、各増分が最大1桁の桁上げ操作 で実行できるため、各増分で最大2桁が変更される変形3進数システムです。

2進反射グレイコードは多くのシナリオで有用であるが、「均一性」が欠如しているため、特定のケースでは最適ではない。^[52]バランスのとれたグレイコードでは、異なる座標位置の変化の数は可能な限り近くなる。これをより正確にするために、Gを遷移シーケンスを持つR進完全グレイサイクルとすると、Gの遷移カウント（スペクトル）は、次のように定義される整数の集合である 。${\displaystyle (\delta _{k})}$

${\displaystyle \lambda _{k}=|\{j\in \mathbb {Z} _{R^{n}}:\delta _{j}=k\}|\,,{\text{ }}k\in \mathbb {Z} _{n}} の場合$

グレイコードは、その遷移カウントがすべて等しい場合、均一または均一にバランスが取れていると言えます。この場合、 すべてのkに対して が成り立ちます。明らかに のとき、そのようなコードはnが 2 の累乗の場合にのみ存在します。 ^[64] nが 2 の累乗でない場合は、 2 つの遷移カウントの差が最大でも 2 である、バランスの取れたバイナリコードを構築できます。つまり、（両方のケースを組み合わせると）すべての遷移カウントがまたは になります。^{[52]グレイコードは、その遷移カウントがすべて隣接する 2 の累乗である場合、}指数的にバランスが取れていることもあり、そのようなコードはすべての 2 の累乗に対して存在します。^[65]${\displaystyle \lambda _{k}={\tfrac {R^{n}}{n}}}$${\displaystyle R=2}$${\displaystyle 2\left\lfloor {\tfrac {2^{n}}{2n}}\right\rfloor }$${\displaystyle 2\left\lceil {\tfrac {2^{n}}{2n}}\right\rceil }$

例えば、バランスのとれた4ビットのグレイコードには16の遷移があり、4つの位置すべてに均等に分散されるため（位置ごとに4つの遷移）、均一にバランスが取れています。^[52]

0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0

0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0

0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0

0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1

一方、バランスのとれた5ビットのグレイコードでは、合計32の遷移があり、位置間で均等に分散することはできません。この例では、4つの位置にそれぞれ6つの遷移があり、1つの位置には8つの遷移があります。^[52]

1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0

0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0

1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1

1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1

1 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1

ここでは、 nに対してn桁のバランスの取れたグレイコードを生成することができる、バランスの取れた2進グレイコードの構成^[66]と実装^[67]を示します。主な原理は、n桁のグレイコードGが与えられたときに、バランスの取れた性質が維持されるように ( n  + 2) 桁のグレイコードを帰納的に構築することです。これを行うには、 を次の形式の偶数L個の空でないブロック に分割することを検討します。${\displaystyle G'}$${\displaystyle G=g_{0},\ldots ,g_{2^{n}-1}}$

${\displaystyle \left\{g_{0}\right\},\left\{g_{1},\ldots ,g_{k_{2}}\right\},\left\{g_{k_{2}+1},\ldots ,g_{k_{3}}\right\},\ldots ,\left\{g_{k_{L-2}+1},\ldots ,g_{-2}\right\},\left\{g_{-1}\right\}}$

ここで、、、である。この分割により、次式で表される -桁のグレイコード が導かれる。${\displaystyle k_{1}=0}$${\displaystyle k_{L-1}=-2}$${\displaystyle k_{L}\equiv -1{\pmod {2^{n}}}}$${\displaystyle (n+2)}$

${\displaystyle {\mathtt {00}}g_{0},}$

${\displaystyle {\mathtt {00}}g_{1},\ldots ,{\mathtt {00}}g_{k_{2}},{\mathtt {01}}g_{k_{2}},\ldots ,{\mathtt {01}}g_{1},{\mathtt {11}}g_{1},\ldots ,{\mathtt {11}}g_{k_{2}},}$

${\displaystyle {\mathtt {11}}g_{k_{2}+1},\ldots ,{\mathtt {11}}g_{k_{3}},{\mathtt {01}}g_{k_{3}},\ldots ,{\mathtt {01}}g_{k_{2}+1},{\mathtt {00}}g_{k_{2}+1},\ldots ,{\mathtt {00}}g_{k_{3}},\ldots ,}$

${\displaystyle {\mathtt {00}}g_{-2}、{\mathtt {00}}g_{-1}、{\mathtt {10}}g_{-1}、{\mathtt {10}}g_ {-2},\ldots ,{\mathtt {10}}g_{0},{\mathtt {11}}g_{0}、{\mathtt {11}}g_{-1}、{\mathtt {01}}g_{-1}、{\mathtt {01}}g_{0}}$

遷移多重度を定義すると

${\displaystyle m_{i}=\left|\left\{j:\delta _{k_{j}}=i,1\leq j\leq L\right\}\right|}$

を、分割内の連続するブロック間で位置iの桁が変化する回数とすると、この分割によって生じる( n  +2)桁のグレイコードの遷移スペクトルは、 ${\displaystyle \lambda '_{i}}$

${\displaystyle \lambda '_{i}={\begin{cases}4\lambda _{i}-2m_{i},&{\text{if }}0\leq i<n\\L,&{\text{otherwise }}\end{cases}}}$

この構成の難しいところは、バランスのとれたn桁のグレイコードを適切に分割して、それによって生成されるコードがバランスのとれたままになるようにすることですが、これには遷移の多重度だけが問題になります。2 つの連続するブロックを桁遷移で結合し、別のブロックを別の桁遷移で分割すると、まったく同じ遷移スペクトル を持つ異なるグレイコードが生成されます。そのため、たとえば^[65]桁での最初の遷移を 2 つのブロックの間にある遷移として指定することができます。ユニフォームコードはおよび のときに見つけることができ、この構成はR進数の場合にも拡張できます。^[66]${\displaystyle i}$${\displaystyle i}$${\displaystyle \lambda '_{i}}$${\displaystyle m_{i}}$${\displaystyle i}$${\displaystyle R\equiv 0{\pmod {4}}}$${\displaystyle R^{n}\equiv 0{\pmod {n}}}$

ロングラン（または最大ギャップ）グレイコードは、同じ位置の数字の連続的な変化間の距離を最大化します。つまり、任意のビットの最小ランレングスは可能な限り長く変化しません。^[68]

単調コードは相互接続ネットワークの理論で有用であり、特にプロセッサの線形配列の膨張を最小限に抑えるのに役立ちます。^{[69]バイナリ文字列の}重みを文字列内の1の数として 定義すると、厳密に重みが増加するグレイコードを持つことは明らかにできませんが、次の重みに到達する前に2つの隣接する重みをコードが通過するようにすることで、これを近似することができます。

モノトーングレイコードの概念は次のように定式化できる。ハイパーキューブを等しい重みを持つ頂点のレベルに分割することを考えてみよう。 ${\displaystyle Q_{n}=(V_{n},E_{n})}$

${\displaystyle V_{n}(i)=\{v\in V_{n}:v{\text{ は重み }}i を持つ\}}$

に対して。これらのレベルは を満たします。が によって誘導されるのサブグラフであるとし、が の辺であるとします。単調なグレイ コードは のハミルトン パスであり、 がパスの前に来るときはいつでもとなります。 ${\displaystyle 0\leq i\leq n}$${\displaystyle |V_{n}(i)|=\textstyle {\binom {n}{i}}}$${\displaystyle Q_{n}(i)}$${\displaystyle Q_{n}}$${\displaystyle V_{n}(i)\cup V_{n}(i+1)}$${\displaystyle E_{n}(i)}$${\displaystyle Q_{n}(i)}$${\displaystyle Q_{n}}$${\displaystyle \delta _{1}\in E_{n}(i)}$${\displaystyle \delta _{2}\in E_{n}(j)}$${\displaystyle i\leq j}$

任意のnに対する単調なn桁グレイコードのエレガントな構成は、長さのサブパスを再帰的に構築し、そのサブパスに辺が にあるというアイデアに基づいています。^[69]またはの ときはいつでもを定義し、${\displaystyle P_{n,j}}$${\displaystyle 2\textstyle {\binom {n}{j}}}$${\displaystyle E_{n}(j)}$${\displaystyle P_{1,0}=({\mathtt {0}},{\mathtt {1}})}$${\displaystyle P_{n,j}=\emptyset }$${\displaystyle j<0}$${\displaystyle j\geq n}$

${\displaystyle P_{n+1,j}={\mathtt {1}}P_{n,j-1}^{\pi _{n}},{\mathtt {0}}P_{n,j} }$

そうでなければ、は適切に定義された順列であり、によって座標が順列化されたパスPを指します。これらのパスは、2つの単調なn桁のグレイコードを生み出し、によって与えられます。 ${\displaystyle \pi_{n}}$${\displaystyle P^{\pi}}$${\displaystyle \pi}$${\displaystyle G_{n}^{(1)}}$${\displaystyle G_{n}^{(2)}}$

${\displaystyle G_{n}^{(1)}=P_{n,0}P_{n,1}^{R}P_{n,2}P_{n,3}^{R}\cdots {\text{ および }}G_{n}^{(2)}=P_{n,0}^{R}P_{n,1}P_{n,2}^{R}P_{n,3}\cdots }$

の選択により、これらのコードが確かにグレイ コードであることが保証され、 は になります。 の最初のいくつかの値を下の表に示します。 ${\displaystyle \pi_{n}}$${\displaystyle \pi _{n}=E^{-1}\left(\pi _{n-1}^{2}\right)}$${\displaystyle P_{n,j}}$

これらの単調なグレイコードは、後続の各要素をO ( n ) 時間で生成できるように効率的に実装できます。このアルゴリズムは、コルーチンを使用すると最も簡単に記述できます。

単調符号は、連結されたすべての頂点推移グラフにはハミルトン経路が含まれるというロヴァース予想と興味深い関係がある。「中間レベル」サブグラフは頂点推移的（つまり、その自己同型群は推移的であるため、各頂点は同じ「ローカル環境」を持ち、他の頂点と区別することはできない。自己同型を得るために座標とバイナリ桁を再ラベル付けできるからである）であり、このサブグラフでハミルトン経路を見つける問題は「中間レベル問題」と呼ばれ、より一般的な予想への洞察を与えることができる。この問題は に対して肯定的に答えられており、単調符号の前述の構成により、長さが少なくとも 0.839 ‍ Nのハミルトン経路が保証される。ここで、N は中間レベルサブグラフの頂点数である。^[70]${\displaystyle Q_{2n+1}(n)}$${\displaystyle n\leq 15}$

グレイコードの別のタイプであるベケット・グレイコードは、対称性に興味を持っていたアイルランドの劇作家サミュエル・ベケットにちなんで名付けられました。彼の劇「クワッド」には4人の俳優が登場し、16の期間に分かれています。各期間は、4人の俳優のうちの1人が舞台に登場するか、舞台から退場することで終わります。劇は空の舞台で始まり、終わり、ベケットは俳優の各サブセットが正確に1回舞台に登場することを望みました。^[71]明らかに、現在舞台にいる俳優の集合は、4ビットのバイナリグレイコードで表すことができます。しかし、ベケットは脚本に追加の制約を設けました。彼は、最も長く舞台にいた俳優が常に退場するように俳優が登場および退場することを望みました。そうすれば、俳優は先入れ先出しのキューで表すことができ、（舞台上の俳優の中で）キューから外される俳優は常に最初にキューに入れられた俳優になります。^[71]ベケットは彼の劇のベケット・グレイコードを見つけることができなかったし、実際、すべての可能なシーケンスを網羅的にリストすると、n = 4の場合にはそのようなコードは存在しないことが明らかになった。今日では、そのようなコードはn = 2、5、6、7、8には存在し、n = 3または4には存在しないことが知られている。8ビットのベケット・グレイコードの例は、ドナルド・クヌースのArt of Computer Programmingに記載されている。^[13]サワダとウォンによると、n = 6の探索空間は15時間で探索​​でき、n = 10の探索空間は100時間以上で探索できる。 n = 7の場合、9500の解が見つかった。^[72]

スネーク・イン・ザ・ボックス符号（スネーク）は、 n次元ハイパーキューブグラフ内の誘導パスのノードのシーケンスであり、コイル・イン・ザ・ボックス符号^[73]（コイル）は、ハイパーキューブ内の誘導サイクルのノードのシーケンスです。グレイコードとして見ると、これらのシーケンスは、1ビットのコーディングエラーを検出できるという特性があります。このタイプのコードは、1950年代後半にウィリアム・H・カウツによって初めて説明されました。 ^[5]それ以来、特定のハイパーキューブ次元に対して可能な限り最大のコードワード数を持つコードを見つけるための研究が盛んに行われてきました。

さらに別の種類のグレイコードとして、ノーマン・B・スペディング^{[74] [75]}によって開発され、ヒルトゲン、パターソン、ブランデスティニによって「シングルトラックグレイコード」（1996 年）で改良されたシングルトラックグレイコード（STGC）があります。^{[76] [77]} STGC は、長さ n のP個の一意のバイナリエンコードの循環リストであり、連続する 2 つの単語は 1 つの位置で異なり、リストをP  ×  n 行列として調べた場合、各列は最初の列の循環シフトになります。^[78]

この名前は、ロータリー エンコーダで使用されることに由来しています。ロータリー エンコーダでは、多数のトラックが接点によって感知され、それぞれ0または1が出力されます。異なる接点がまったく同時に切り替わらないことによって生じるノイズを減らすには、接点によるデータ出力がグレイ コードになるようにトラックを設定するのが望ましいです。高い角度精度を得るには、多数の接点が必要です。少なくとも 1° の精度を達成するには、1 回転あたり少なくとも 360 の異なる位置が必要であり、これには最低でも 9 ビットのデータが必要であり、したがって接点の数も同じになります。

すべての接点が同じ角度位置に配置されている場合、少なくとも 1° の精度を持つ標準 BRGC を得るには 9 つのトラックが必要です。ただし、製造元が接点を別の角度位置 (ただし、中心シャフトからの距離は同じ) に移動した場合、対応する「リング パターン」を同じ角度だけ回転させて同じ出力を得る必要があります。最上位ビット (図 1 の内側のリング) を十分に回転させると、次のリングと完全に一致します。両方のリングは同一であるため、内側のリングを切り取り、そのリングのセンサーを残りの同一リング (ただし、そのリング上の他のセンサーからその角度だけオフセット) に移動できます。1 つのリング上のこれらの 2 つのセンサーは、直交エンコーダーになります。これにより、「1° 解像度」角度エンコーダーのトラック数が 8 トラックに減ります。BRGC では、トラック数をさらに減らすことはできません。

長年、トルステン・シルケ^[79]と他の数学者は、2センサー1トラックの直交エンコーダを除いて、連続する位置が1つのセンサーのみで異なるように、1つのトラック上の位置をエンコードすることは不可能であると信じていました。そのため、8トラックでは大きすぎるアプリケーションでは、シングルトラックのインクリメンタルエンコーダ（直交エンコーダ）または2トラックの「直交エンコーダ+リファレンスノッチ」エンコーダが使用されました。

しかし、ノーマン・B・スペッディングは、それが可能であることを示すいくつかの例とともに、1994年に特許を登録しました。^[74]単一トラック上のn個のセンサーで2nの位置を^区別することはできませんが、それに近い数なら区別できます。エツィオンとパターソンは、n自体が2の累乗である場合、n個のセンサーは最大で²ⁿ  −2nの位置を区別でき、素数のnの場合はその限界は²ⁿ  −2の位置であると推測しています。^{[80]著者らは、長さ9の504位置単一トラックコードを生成しましたが、これが最適だと考えています。この数は28} =256より大きいため、どのコードでも8個以上のセンサーが必要ですが、BRGCは9個のセンサーで512の位置を区別できます。

P  = 30 およびn = 5の STGC を 次に示します。

各列は最初の列の巡回シフトであり、どの行から次の行へ行っても1ビットだけ変化します。^[81] 単一トラックの性質（コードチェーンのような）は、これらのホイールの製造に便利です（BRGCと比較して）。必要なトラックは1つだけなので、コストとサイズが削減されます。グレイコードの性質は便利です（チェーンコード（デ・ブリュインシーケンスとも呼ばれる）と比較して）。一度に1つのセンサーだけが変化するため、2つの離散状態間の遷移中の不確実性は、デバイスが分解できる角度測定のプラスまたはマイナス1単位だけです。^[82]

この30度の例が追加されて以来、より高い角度分解能の例に多くの関心が寄せられています。2008年、ゲイリー・ウィリアムズ^[83]は、以前の研究 ^{[80]に基づいて、1度の分解能を提供する9ビットのシングルトラックグレイコードを発見しました。このグレイコードは、} Thingiverseのサイトで公開された実際のデバイスの設計に使用されました。このデバイス^[84]は、2022年9月にetzenseep（Florian Bauer）によって設計されました。

P  = 360 およびn = 9の STGC を 次に示します。

2次元グレイコードは、通信において、直交振幅変調（QAM）の星座の隣接点におけるビットエラーの数を最小限に抑えるために使用されます。典型的な符号化では、水平および垂直の隣接星座点は1ビット異なり、対角の隣接点は2ビット異なります。^[85]

2次元グレイコードは位置識別方式にも使用され、地球表面のメルカトル図法などのエリアマップにコードを適用し、マンハイム距離などの適切な循環2次元距離関数を使用して2つのエンコードされた位置間の距離を計算し、ハミング距離の特性とメルカトル図法の循環継続を組み合わせることができます。^[86]

特定のコード値のサブセクションがその値から抽出される場合、たとえば 4 ビットのグレイ コードの最後の 3 ビットなど、結果のコードは「超過グレイ コード」になります。このコードは、元の値がさらに増加すると、抽出されたビットで逆方向にカウントする特性を示します。その理由は、グレイ エンコードされた値は、「最高」値を超えて増加したときに、従来のバイナリ エンコードで知られているオーバーフローの動作を示さないためです。

例: 最高 3 ビットのグレー コード 7 は、(0)100 としてエンコードされます。1 を追加すると、数値 8 になり、グレーでは 1100 としてエンコードされます。最後の 3 ビットはオーバーフローせず、元の 4 ビット コードをさらに増やしても逆方向にカウントされます。

複数のグレーエンコード値をシリアル形式で出力するセンサーを使用する場合は、センサーがそれらの複数の値を 1 つのグレーコードでエンコードして生成するか、または別々の値としてエンコードして生成するかに注意する必要があります。そうしないと、「オーバーフロー」が予想されるときに値が逆方向にカウントされているように見える場合があります。

全単射写像 { 0 ↔ 00 , 1 ↔ 01 , 2 ↔ 11 , 3 ↔ 10 }は、ハミング距離によって計量が与えられる有限体上の計量空間と、リー距離 によって計量される有限環(通常のモジュラー算術) 上の計量空間との間の等長写像を確立します。この写像は、ハミング空間と の等長写像に適切に拡張されます。その重要性は、 からの環線形符号のにおけるグレイマップ画像などの、さまざまな「良い」が必ずしも線形ではない符号間の対応を確立することにあります。^{[87] [88]} ${\displaystyle \mathbb {Z} _{2}^{2}}$ ${\displaystyle \mathbb {Z} _{4}}$ ${\displaystyle \mathbb {Z} _{2}^{2m}}$${\displaystyle \mathbb {Z} _{4}^{m}}$${\displaystyle \mathbb {Z} _{2}^{2}}$${\displaystyle \mathbb {Z} _{4}}$

グレイ コードに似たバイナリ コードは多数あります。以下に例を示します。

• Datexコード、別名Gianniniコード（1954）は、Carl P. Spauldingによって説明されているように、^{[9] [89] [90] [91] [92] [8]} O'BrienコードIIの変種を使用しています。
• Varec（1954年頃）が使用したコード^{[93] [94] [95] [96]}は、 O'BrienコードIの変種と、12進数および16進数のグレイコードの変種を使用しています。
• ルーカルコード（1959）^{[1] [2] [57]}別名修正反射バイナリコード（MRB）^{[1] [2] [注 3]}
• ギルハムコード（1961/1962）^{[90] [97] [8] [98] [99]}は、デイテックスコードとオブライエンコードIIの変種を使用しています。
• レスリーとラッセルのコード（1964）^{[100] [10] [101] [97]}
• ロイヤルレーダー施設コード^[97]
• ホクラスコード（1988年）^{[102] [103] [104]}

次の2 進化 10 進数(BCD) コードもグレイ コードのバリエーションです。

• ペザリックコード（1953年）^{[19] [105] [106] [107] [55] [103] [注4]}ロイヤル・エアクラフト・エスタブリッシュメント（RAE）コードとしても知られる。^[108]
• オブライエン符号 I および II (1955) ^{[109] [110] [111] [91] [92] [103]} (オブライエン I 型符号^{[注 5]は、} IBMの Frederic A. Foss ^{[112] [113]}によって既に記述されており、1954 年に Varec によって使用されていました。後に、ワッツ符号またはワッツ反射 10 進数 (WRD) 符号としても知られるようになり、時には曖昧に反射 2 進修正グレイ符号と呼ばれることもあります。^{[114] [20] [21] [115 ] [116] [ 117] [118] [119] [120] [注 1] [注 3]}オブライエン II 型符号は、1954 年に Datex によって既に使用されていました。^{[注 4]} )
• 過剰3グレイコード（1956年）^[121]（別名グレイ過剰3コード、^{[91] [92] [8]}グレイ3過剰コード、反射過剰3コード、過剰グレイコード、^[103]グレイ過剰コード、10過剰3グレイコードまたはグレイ・スティビッツコード）、ITTのフランク・P・ターベイ・ジュニアによって説明されました。^[121]
• トンプキンスコードIとII（1956）^{[4] [110] [111] [91] [92] [103]}
• グリクソンコード（1957）、曖昧に修正グレイコードとも呼ばれる^{[122] [55] [123] [124] [110] [111] [91] [92] [103] [nb 3] [nb 5]}

• 線形フィードバックシフトレジスタ
• デ・ブリュインシーケンス
• シュタインハウス・ジョンソン・トロッターアルゴリズム–階乗数システムのグレイコードを生成するアルゴリズム
• 最小距離コード
• プルーエ・テュー・モールス系列– 逆グレイコードに関連
• ライザー式
• ヒルベルト曲線