涼麻父、すっかり、グレイコードそのものに興味が湧いてきてしまいました
4ビットのグレイコードは、先日のブログで示した通りです。
実用面では、これで充分です。
涼麻父が夢中になっているのは、4ビットのグレイコードには、はたして、全部で何通りのパターンがあるか、なのです
第1章 2ビットグレイコード
まずは、簡単な2ビットのグレイコードについて整理してみます。
2ビットのBCD配列は、こんな感じでした。
グレイコードの作り方は、2進表示して、右シフトしたものと元の2進表示との排他的論理和(XOR)をとればよいことが知られています。
例えば、「2」のグレイコードは、2進表示した「10」と右シフトした「01」との排他的論理和である「11」になります。
こうして生成した2ビットのグレイコードが、これです。
しかし、2ビットのグレイコードは、これだけではありません。
1ステップ進む際に、値の変化が1ビットだけである、という意味では、これもグレイコードです。
それでは、はたして、2ビットグレイコードには何種類あるのでしょうか。
しらみつぶしに調べようとすると、4!=4×3×2×1=24通りについて検証する必要があります。
まぁ、これくらいであれば、現実的な範囲ですが、ここでは、2つの方法、すなわち「場合分け系統樹」と「図解法」により、合理的に調べてみます。
あり得ないパターンは、途中で棄却してケース数を減らしながら調べていく方法です。
1.1 系統樹による方法
2ビットの場合は、比較的、簡単で、「0」からスタートする場合、2ステップ目でA極を変化させるか、B極を変化させるか2ケースが生じるだけで、その後は、一本道になります。
このように、前述した2つのパターンが得られました。
次に、もう一つの方法でも調べてみます。
1.2 図解による方法
グレイコードでは、一度に一箇所しか値を変化させません。
2ビットの場合、A極を変化させるか、B極を変化させるか、選択肢は2つです。
具体的には、「0」の次は「1」か「2」だけで、「3」にはできません(「3」にしようとすると、一度に2つのビットを変化させなくてはならないからです)。
同様に、「1」の次は「0」か「3」、「2」の次は「0」か「3」、「3」の次は「1」か「2」です。
この繋がりを図で示すと、このようになります。
各ステップを丸印(ノード)で表し、次のステップに進むには、辺(黒線)を通っていきます。
「0」から始まるグレイコードを生成することは、この図の「0」からスタートして、各ノードを1回ずつ回ることと同じです。
具体的には、次の図の赤矢印のように辿ることになります。
この数字の順番は、まさしく冒頭に示した2つのグレイコードと一致しています。
1.3 まとめ
以上より、「0」からスタートする2ビットグレイコードには、冒頭に示した2種類が存在することがわかります。
こちらが、ビット操作や排他的論理和などから機械的に得られるグレイコードですが、ここでは、この配列をオーソドックスなグレイコード(ortho-Gray Code)と呼ぶことにします。
もうひとつが、この配列ですが、これは、実は、オーソドックス配列において、A極とB極を入れ替えた変種です(ここでは、以降、swapped-Gray Codeと呼ぶことにします)。
また、同時にこの配列はオーソドックス配列を逆順にした鏡像解でもあります(ここでは、以降、mirrored-Gray Codeと呼びます)。
したがって、2ビットグレイコードには、実質的には1つのパターンしかないことが分かります。
「0」からスタートする場合、オーソドックス配列と変種(あるいは鏡像解)の2種類があり、スタートする数字は「1」でも「2」や「3」でも同様なので、2×4=8種類の配列が存在します(下図の配列例ようにスリップリング上の黒帯部分が長さ1の細切れ状になる配列も含まれるので、これらは工学的には採用できないかも知れません)。
2ビットグレイコードは、こんな感じですが、これが3ビットになると、別の様相が現れてきて、ちょっとおもしろいです。
そのうち、アップします