グレイコード #3

飽きずに懲りずに、またまたグレイコードの話です。

 

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

 　前回の２ビットグレイコードに続いて、今回は３ビットグレイコードについてまとめてみました。

 2.1　系統樹による方法

　まず、これが３ビットBCD配列です。

　３ビットグレイコードについても、２ビットのときと同様に場合分けをしながら、「0」から始まるグレイコードを生成します。３ビットのうち１つのビットのみを変化させるので、はじめの選択肢は３通り、その後は２通り以下になります（一歩前に戻る訳にはいかないので）。場合分けをしながら丹念に調べていくと、下表のように全18種類の配列が得られます。

　左列は、一番上の配列がオーソドックス配列で、その下に続く５つは、A極←→B極、A極←→C極などと、ビットを入れ替えて得られる配列です。また、中央列の配列は、左列の配列を上下逆順に並べて得られる配列です。

　左列も中央列も一番下から一番上に繋げることができる（１ビットのみの値を変えて繋がる）という意味で「循環型」と呼ぶことにします。

　特異的なのが、右列の配列です。これらは、一番下から一番上に繋がらない、いわば「非循環型」になっています。これは、２ビットグレイコードには現れなかったパターンです。

　循環型配列は、スリップリング方式のロータリーエンコーダーを360°グルリと円環状に取り付ける際に役立ちそうです。一方、先日のズームレンズのように円弧状に取り付けるのであれば、非循環型でも事足りそうです（ただし、黒帯部が１箇所だけ、長さ１の細切れになってしまいます）。

分類	循環型	循環型	非循環型
説明	オーソドックス配列のビットを入れ替えて得られる配列 (swapped-Gray Code)	左列の配列を逆順にして得られる鏡像解 (mirrored-Gray Code)	−
1	(ortho-Gray Code)
2
3
4
5
6

　上表には、「0」から始まるグレイコードとして、全18種類を示しましたが、基本的には左上の循環型が１つ、右上の非循環型が１つ、計２パターンに集約されることが分かります。その他の配列は、すべて、ビットの入替えか、逆順に並べ直すことで得られる変種です。

 

2.2　図解による方法

　２ビットのときと同様に３ビットグレイコードについても、図解法を用いて整理してみます。

　２ビットのときは、はじめの選択肢がA極かB極の２通りでしたが、３ビットでは３通りの選択肢があります。それぞれの数字を素直に結びつけて描くと、下図のように複雑になってしまいます。

　同じ関係を保ったまま、別の描き方をすると、次のようになります。

　２ビットの図解法では二次元の正方形が便利でしたが、３ビットでは、このように三次元の立方体が便利です。

 　あれやこれや系統的に矢印を入れていくと、下表のように18種類の配列が得られ、上の青表と一致する結果が得られます。

分類	循環型	循環型	非循環型
特徴	3回目の移動で「7」に到達	5回目の移動で「7」に到達	7回目の移動で「7」に到達
1		(ortho-Gray Code)
2
3
4
5
6

 　

2.3　アップダウン法

　さて、系統樹の方法も図解法も良いのですが、４ビット以上のグレイコードを調べるには、いささか困難そうです。

　ここで、黄表で、赤矢印の移動を眺めていると、「0」←→「1」or「2」or「4」←→「3」or「5」or「6」←→「7」という移動を繰り返していることに気付きます。下図で説明すると、「0」←→赤い面←→青い面←→「7」を渡り歩いていることになります。

　「0」は３ビット２進表示で「000」、「1」「2」「4」は、それぞれ「001」「010」「100」、「3」「5」「6」は「011」「101」「110」、「7」は「111」です。

　すなわち、上述した移動は、値が1であるビットの数が、0←→1←→2←→3と1つずつ変化しているんだ、ということが分かります。実は、これは、ごく当たり前の話で、グレイコードでは、「一度に１つのビットしか変化させない」のだから、値が1であるビットの数は1つずつしか変化しないんです。

　下図は、値が1であるビットの数が同じノード（黒丸印）を一直線上に並べたものです（各直線をStepと呼ぶことにします）。この図を見たときに、上に示した立方体を斜め上から見下ろした透視図だと思っても構いませんが、ここでは、あくまでも二次元の図として扱います。

　グレイコードの生成とは、あるノードからスタートして、各Stepを１段ずつ登ったり降りたりしながら、すべてのノードを最小移動数で巡っていく順番を決めること、です。この方法は図解法の一種と言えますが、ここでは、あえて、「アップダウン法」と名付けることにします。

　実際にどうなるかは、また次回。