グレイコード #2

涼麻父、すっかり、グレイコードそのものに興味が湧いてきてしまいました

4ビットのグレイコードは、先日のブログで示した通りです。

実用面では、これで充分です。

涼麻父が夢中になっているのは、4ビットのグレイコードには、はたして、全部で何通りのパターンがあるか、なのです

 

第１章　２ビットグレイコード

　まずは、簡単な2ビットのグレイコードについて整理してみます。

　2ビットのBCD配列は、こんな感じでした。

 

　グレイコードの作り方は、2進表示して、右シフトしたものと元の2進表示との排他的論理和（XOR）をとればよいことが知られています。

　例えば、「2」のグレイコードは、2進表示した「10」と右シフトした「01」との排他的論理和である「11」になります。

　こうして生成した2ビットのグレイコードが、これです。

　しかし、2ビットのグレイコードは、これだけではありません。

　1ステップ進む際に、値の変化が1ビットだけである、という意味では、これもグレイコードです。

　それでは、はたして、2ビットグレイコードには何種類あるのでしょうか。

　しらみつぶしに調べようとすると、4!=4×3×2×1=24通りについて検証する必要があります。

　まぁ、これくらいであれば、現実的な範囲ですが、ここでは、２つの方法、すなわち「場合分け系統樹」と「図解法」により、合理的に調べてみます。

　あり得ないパターンは、途中で棄却してケース数を減らしながら調べていく方法です。

 

1.1　系統樹による方法

　２ビットの場合は、比較的、簡単で、「0」からスタートする場合、2ステップ目でA極を変化させるか、B極を変化させるか2ケースが生じるだけで、その後は、一本道になります。

 

　このように、前述した２つのパターンが得られました。

　次に、もう一つの方法でも調べてみます。

 

1.2　図解による方法

　グレイコードでは、一度に一箇所しか値を変化させません。

　２ビットの場合、A極を変化させるか、B極を変化させるか、選択肢は２つです。

　具体的には、「0」の次は「1」か「2」だけで、「3」にはできません（「3」にしようとすると、一度に2つのビットを変化させなくてはならないからです）。

　同様に、「1」の次は「0」か「3」、「2」の次は「0」か「3」、「3」の次は「1」か「2」です。

　この繋がりを図で示すと、このようになります。

　各ステップを丸印（ノード）で表し、次のステップに進むには、辺（黒線）を通っていきます。

　「0」から始まるグレイコードを生成することは、この図の「0」からスタートして、各ノードを１回ずつ回ることと同じです。

　具体的には、次の図の赤矢印のように辿ることになります。

　この数字の順番は、まさしく冒頭に示した２つのグレイコードと一致しています。

 

1.3　まとめ

　以上より、「0」からスタートする２ビットグレイコードには、冒頭に示した２種類が存在することがわかります。

　こちらが、ビット操作や排他的論理和などから機械的に得られるグレイコードですが、ここでは、この配列をオーソドックスなグレイコード（ortho-Gray Code）と呼ぶことにします。

 

　もうひとつが、この配列ですが、これは、実は、オーソドックス配列において、A極とB極を入れ替えた変種です（ここでは、以降、swapped-Gray Codeと呼ぶことにします）。

　また、同時にこの配列はオーソドックス配列を逆順にした鏡像解でもあります（ここでは、以降、mirrored-Gray Codeと呼びます）。

　したがって、２ビットグレイコードには、実質的には１つのパターンしかないことが分かります。

　「0」からスタートする場合、オーソドックス配列と変種（あるいは鏡像解）の２種類があり、スタートする数字は「1」でも「2」や「3」でも同様なので、2×4=8種類の配列が存在します（下図の配列例ようにスリップリング上の黒帯部分が長さ１の細切れ状になる配列も含まれるので、これらは工学的には採用できないかも知れません）。

 

２ビットグレイコードは、こんな感じですが、これが３ビットになると、別の様相が現れてきて、ちょっとおもしろいです。

そのうち、アップします