涼麻が行く ~白犬ウエスティの のんきな生活~

ウエストハイランドホワイトテリア(ウエス、ウエスティ、白犬)の涼麻(りょうま)のことを中心にいろいろと

グレイコード #4

2014年12月20日 14時30分55秒 | グレイコード

前回の3ビットグレイコードの続きで、いよいよ4ビットの話です。

 

第3章 4ビットグレイコード

3.1 グレイコード生成とハミルトン路問題

 3ビットグレイコードの生成は、下図のような配置の7つの点を7回の移動で辿ることと同じでした。

 これは、「一筆書き」と似ていますが、ちょっと違います。一筆書きは、全ての「辺」をダブることなく辿っていくことであるのに対し、この問題は、全ての「点」をダブることなく辿ることで、これは「巡回セールスマン問題Traveling Salesman Problem)」において、辺の重み付けをなくした「ハミルトン路問題」(Hamilton Path Problem)と呼ばれます。

 前回の説明で、3ビットグレイコードには、「循環型」と「非循環型」があることを示しましたが、「循環型」の場合は、特に「ハミルトン閉路問題」に分類されるようです。

 「巡回セールスマン問題」にせよ、「ハミルトン路問題」にせよ、いろんな数、いろんな配置の「点」を、さまざまな「辺」で結んだものを、統一的に解く方法は見い出されていないようです。

 コンピューターが得意とする「しらみつぶし法」も、「点」や「辺」の数が増えるほど、現実的な時間内に答えを得られない(例えば、4ビットの場合では21兆通りを調べる必要がある)ことが、人々の興味を惹くところです。

 しかし、グレイコードに限っては、「点」と「点」の繋ぎ方に特徴があるため、どうやら解くことができそうです。

 

3.2 アップダウン法による3ビットグレイコードの生成

 3ビットの場合、0~7の8つの数字を表します。8つの数字を表すので、少なくとも7回はビットを変化させなくてはなりません。1回の変化において1ビットしか変更しないなら、それはグレイコードです。

 前述の図解は、1回の変化で1ビットしか変化しないで繋がる数字同士を辺で結んでいるので、この図を辿っていけば、自ずとグレイコードが得られます。

 上図には、補助線として「Step 0」~「Step 3」を描いてあります。「点0」(Step 0上にある)からスタートして、7回進むと(7は奇数なので)「Step 1」か「Step 3」で終わることになります。「Step 1」で終わるということは「点1」「点2」「点4」で終わることなので「循環型」を示していて、「Step 3」は「点7」なので「非循環型」になるというわけです。

 「Step 0」からスタートする場合、「Step 3」上の「点7」は1回しか通らないので、他の点とはちょっと違います。そこで、何回目に「点7」を通るかで整理してみます。「Step 3」は奇数回目にしか到達しません。奇数回目ということは、1回目、3回目、5回目、7回目のいずれかです。しかし、「点0」から「点7」へは少なくとも3回は要するので、3回目、5回目、7回目のいずれか、ということになります。

 これは、前回の黄表で、それぞれ「3回目の移動で点7に到達」する循環型(左列)、「5回目の移動で点7に到達」する鏡像解(中央列)、「7回目の移動で点7に到達」する非循環型(右列)に相当します。

 それぞれの移動例を示すと、下図(a)~(c)の3パターンになります(ちなみに、図(a)と図(b)が左右対称になっていて、お互いに鏡像関係になっていることが視覚化されています)。

図(a) 3回目に点7に到達

 

図(b) 5回目に点7に到達

 

図(c) 7回目に点7に到達

 

 黄表で示した通り、この3パターンが得られれば、あとはビットの入替えですべての変種を得ることができます。3ビットの入替えによって得られる変種の数は、それぞれについて、3P3=3!=6通りなので、計18種類の配列が得られ、これは前回までに得られた結論と同様です。

 あるいは、別の説明として、例えば、図(a)のパターンに対しては、はじめの動きでは点1、点2、点4の3通りの選択肢があり、このとき点1に進めば、次は、点3か点5の2通りの選択肢、ここで点3に進めば、あとは選択の余地なく終点まで進みます。したがって、3×2=6通り、ということで、前述の数字と一致します。

 

3.3 アップダウン法による4ビットグレイコードの生成

 2ビットのときは二次元の正方形、3ビットのときは三次元の立方体を用いると便利だったのですが、4ビットでは四次元になってしまうので、ドラえもんに頼まない限り、私たちには見ることができません。とはいえ、3ビットのときと同じような絵柄で解くことができます。

 具体的には、4ビットグレイコードの場合、前述の3ビットの図を2つ並べたような感じになります。左下の立方体のような塊は3ビットのときと同じ図で、右上の立方体と、それぞれの頂点が繋がっています。3ビットではA極からC極の3ビットでしたが、4ビットではD極が加わります。左下の立方体はD極が0、右上の立方体はD極が1の状態に相当します。

 四次元的に言うならば、左下と右上の立方体は異なる時間に存在するとか、両者はパラレルワールドに存在する、とか、どんな風に考えるも自由です。

 4ビットグレイコードでは、0~Fの16通りの数字を示すので、15回の移動ですべての点を巡る必要があります。15は奇数なので、点0の「Step 0」からスタートすると、15回目には「Step 1」か「Step 3」で終点を迎えます。終点がStep 1上であれば「循環型」、Step 3ならば「非循環型」になります。

 Step 4上の点15は1回しか通らないので、そこに着目して、3ビットのときと同様に移動パターンを整理してみます。Step 4に到達するのは、4回目以降の偶数回目ですから、4回目、6回目、8回目、10回目、12回目、14回目のいずれかです。それぞれのパターン(の一例)を描いてみると、図(a)~図(f)の6通りです。このうち、(a)と(e)、(b)と(d)は鏡像関係にあります。したがって、この後は、(a)、(b)、(c)、(f)について調べていくことにします。

 

 

図(a) 4回目に点15に到達

 

図(b) 6回目に点15に到達

 

図(c) 8回目に点15に到達

図(d) 10回目に点15に到達

図(e) 12回目に点15に到達

図(f) 14回目に点15に到達

 

 まず、(a)のパターンですが、「4回目に点15に到達」するパターンは、この他にもあり、全部で5C2=10通りがあります。実際に、これらのパターンで、下図の道筋(前掲と同じ)で全てのノードを辿ることができるかどうかを検証する必要があります。

 ちょっと、ややこしくなってきました

コメント
  • Twitterでシェアする
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

グレイコード #3

2014年12月05日 01時14分24秒 | グレイコード

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

 

第2章 3ビットグレイコード

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

 2.1 系統樹による方法

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

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

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

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

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

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

 分類 循環型 循環型

非循環型

 説明

オーソドックス配列のビットを入れ替えて得られる配列
(swapped-Gray Code)

左列の配列を逆順にして得られる鏡像解
(mirrored-Gray Code)

 
1
(ortho-Gray Code)
2

3

4

5

6

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

 

2.2 図解による方法

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

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

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

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

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

分類 循環型 循環型

非循環型

特徴

3回目の移動で「7」に到達

5回目の移動で「7」に到達

 7回目の移動で「7」に到達
1
 
 
(ortho-Gray Code)

 
2

 
3

 

4    

 

5

 

6

 

 

  

2.3 アップダウン法

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

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

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

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

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

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

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

コメント
  • Twitterでシェアする
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

グレイコード #2

2014年11月29日 22時43分57秒 | グレイコード

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

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ビットになると、別の様相が現れてきて、ちょっとおもしろいです。

そのうち、アップします

コメント
  • Twitterでシェアする
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

グレイコード

2014年11月28日 01時06分58秒 | グレイコード

スリップリング式のロータリーエンコーダーについてググっていたら、例の配列が「グレイコード」と呼ばれる配列であるということが分かりました

 

まず、これは、涼麻父が「素直な並び」と呼んでいたBCD配列(二進化十進表現、Binary Coded Decimal)です。

 

これに対して、ズームレンズに使われていたスリップリング式のロータリーエンコーダーの配列が、グレイコードと呼ばれるものでした。

 

グレイコードの特長は、次のステップに進むときに、値の変化するビットが1つだけ(1極だけ)、という点です。

例えば、グレイコードの1番上の「0000」から次ステップの「0001」に変化するときに、A極が「0」→「1」に変化するだけです。

その次は、「0001」から「0011」ですから、B極が「0」→「1」に変化するだけです。

 

一方、BCD配列ではどうかというと、「1」から「2」に進むとき、「0001」から「0010」に変わるので、A極が「1」→「0」、B極が「0」→「1」というように2箇所で同時に値が変わります。

「7」から「8」に進むときは激しくて、「0111」から「1000」に変わるので、同時に4箇所の値が変わります。

この「同時」というのがくせ者で、機械的に「同時に」という動作は、まず起こりえないのです。

なぜかというと、スリップリング上の絶縁部(黒帯の場所)の位置は、どれほど加工精度を上げても各極で微妙にずれてしまうし、薄い金属でできたブラシは気温や経年変化で変形してしまうからです。

そのため、BCD配列で、ズームリングを回していくとき、「0001」から「0010」というようにスッキリ変化することは稀といってよく、実際には、「0001」→「0000」→「0010」あるいは「0001」→「0011」→「0010」と過渡的に変化します。これは、ズーム値でいうと、21mm→24mmと一発でスッキリ変化するのではなく、21mm→18mm→24mmあるいは21mm→28mm→24mmとなるわけです。このように、21mmと24mmの間には存在しない、全くぶっ飛んだ数字が登場してしまうことは制御上の問題となり得るわけです。

同時に2極が変化する場合でもこんな感じなのが、同時に4極が変化する場面では、滅茶苦茶な数字が3回も挟まるおそれがあります。

グレイコードの優れたところは、1つ進むときに、1ビットしか変化しないので、上述のような誤認がまったく発生しない、という点です。スリップリングの加工に多少の誤差があったとしても、前述の例でいえば21mmか24mmのどちらかを示すだけで、とんでもない数字を示すことがありません。

このジーニアスな配列は、米ベル研究所のフランク グレイ(Frank Gray)が1947年に特許出願したものです。

涼麻父は、先日のブログで「技術立国日本云々」と書いてしまいましたが、米国の発明であることが判明しました

 

涼麻父は、各極の「1」の連なりができるだけ長くなる配列のことを追い求めていました。

一昨日のブログでは、この配列では、「1→0」や「0→1」などの切り替わりが15箇所であると書いています。

このときは、15箇所でも多いと思っていたのですが、よくよく考えてみれば、15ステップ進むのですから最低でも15箇所で変化がなければならないので、15箇所というのは必要最小限の変化数だったのです。

「1」の連なりをできるだけ長くする配列は、「1→0」や「0→1」などの切り替わりの数を減らすことと同じだったと考えて良さそうで、また、切り替わりの数は15が最小値なので、そのときの配列が「1」の連なりが最も長くなる最適配列だったといえるでしょう。

 

グレイコードの特許明細書をざっと読んでみると、グレイコードの主目的は1ステップ進むときに1ビットしか変化しない、ということだけれど、副次的に、製造しやすくなるという特長もある、と記載されています。

1つめの特長は、BCD配列に比べて、各ビットの絶縁部の長さが2倍になる(例えばA極をみると、BCD配列では「1」は長さ1で途切れ途切れだけれど、グレイコードでは「1」の連なり長さが2倍の2になっている)。

2つめの特長は、最上位の桁(D極)を除いて、上下対称のパターンになっている(16進表示の「4」と「C」の間の罫線を軸として線対称になっている)。

 

涼麻父は、できるだけ絶縁部の長さを長くする(「1」の連なりを増やす)ことが、品質上の安定性に繋がると考えて、その結果、切り替わりの回数が15箇所だというところまではたどり着いていたのに、これが最小値であり、なおかつ、15回という数字が1ステップ進む際に1箇所でしか値の変化がないということを意味することにまでは思い至っていませんでした。

惜しいっ、残念

コメント
  • Twitterでシェアする
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする