2010年8月29日日曜日

Penroseタイル

GoogleでPenrose tileの記事を眺めていたら, Penrose tileは3 colorableという記述が! ジャジャーン. 平面の地図は4色で塗り分けられるが, 3色で塗り分けられるというわけだ. さっそく前回のブログの最後の図をプリントし, 4色のマーカーを手に, 塗り分けてみると, 確かに3色でうまく行く.

余談だが, 慶應の皆さんは, 慶應の校旗はblue red and blueの3色といい, 私の2010年5月13日のブログのように, オランダ国旗も3色だ. ジャジャーン.言語学者の用語では, 「サイタ サイタ サクラ ガ サイタ」は, 延べ語数5,異なり語数3という. その伝では, 慶應の校旗は述べ3色旗. オランダ国旗は異なり3色旗である. Penrose tileは異なり3色で塗り分け可能である.

数学者なら, 3色塗り分け可能を証明するわけだが, 私の場合はプログラムで,3色塗り分けしたい. さっそくトライ.

前回のブログの最後にプログラムがあるが, そこで分かるように, それぞれの線分はtranslateで原点を移動し, rotateで向きを変えたユーザ座標て描いている. これでは誰が隣りかは判明しない. どうすれば絶対座標(装置座標)で描けるか, PostScriptのマニュアルをみると, transformという関数がある. PostScriptでは,装置座標とユーザ座標の関係は, current matrixが記憶していて, transformはユーザ座標を装置座標にしてくれるらしい.

ところが,例えば kite0のn=0の部分を0 0 transform == phi2 36 xy transform == phi -72 xy transform ==のようにし,
[1 0 0 1 0 0] setmatrix
300 400 translate
/n 0 def init
0 0 0 kite0

で起動すると, kite0の3点は,

A 300.0 400.0
B 469.442719 523.107361
C 340.0 276.892639
と出力された.

今, 単位長さが80なので, すこし計算してみる.
(* 80 phi phi (cos (d2r 36))) => 169.4427190999916
(* 80 phi phi (sin (d2r 36))) => 123.10734148701015
(* 80 phi (cos (d2r -72)) => 40.00000000000001
(* 80 phi (sin (d2r -72))) => -123.10734148701013

理由は分からないが, AとBは正しい; CはAから-72度の方向に移動した距離になっている. それが分かればあとはプログラムでCの位置は計算出来る.

こうしてkite0, kite1, dart0, dart1の3点の座標が得られた. 次はkite0とkite1, dart0とdart1を組合わせる. 始点と終点は合っているから, それらを対にする. 相棒のないのは外す. こうして95の四辺形が揃った. 各四辺形には0から94まで番号をつける.

次は隣りどうしを探す作業で, alistを作り, 辺を登録したり探索したりして,隣組のリストが出来た. 両方から指すこともないので, 自分より番号の少ない隣りの四辺形のリストになっている.

次にそれぞれに色0,1,2を対応させる. 目で見てやるのと違うから,バックトラックすることになる. SICPの8クィーン(ex2.42)のプログラムをちょっと改造して書いてみたが, これは全解探索だし, 深さも8段から95段になるので,たちまち再帰のオーバーフローを起した. うーん. 駄目か.

仕方ないので, 通常のバックトラックのプログラムを書く.解が1つ見つかったところで, call-ccを使って脱出する.

(define next' (() (0) () (0 2) (2 1) (3) (5) () (7) ()
(7 9 0) (10 0) (9 8) (7) (7 13 5 3) (6 13) (15 6) () (17) ()
(17 19) (19 18) (20) (22) () (24 2) (25 2 5) (4) ()
(24 28 17) (29 17) (28 27 25) (24 26) (24 32 22 20)
(23 6 32) (16 34 23) () (36) () (36 38) (38 37) (39) (41) ()
(43 19) (44 19 22) (21) () (43 47 36) (48 36) (47 46 44)
(43 45) (43 51 41 39) (42 23 51) (35 53 42) () (55) ()
(55 57) (57 56) (58) (60) () (62 38) (63 38 41) (40) ()
(62 66 55) (67 55) (66 65 63) (62 64) (62 70 60 58)
(61 42 70) (54 72 61) () (74) (8) (76 8 13) (74 76) (76 75)
(79 12) (78 77) (81 15) () (83 57) (84 57 60) (59) ()
(83 87 74) (88 74) (87 86 84) (83 85) (83 91 81 78)
(82 61 91) (73 93 82 16)))
(define colorlist '())
(define (search)
(call-with-current-continuation
(lambda (throw)
(define (safe? n c)
(let ((es (list-ref next n)) (revc (reverse colorlist)))
(not (member c (map (lambda (x) (list-ref revc x)) es)))))
(define (test n)
(if (= n 95) (throw (reverse colorlist))
(do ((m 0 (+ m 1))) ((= m 3))
(let ((c (modulo (+ m n) 3)))
(if (safe? n c)
(begin (set! colorlist (cons c colorlist))
(test (+ n 1))
(set! colorlist (cdr colorlist))))))))
(test 0))))
(search)

ジャジャーン. これでやっと色のリストが得られた.

(0 1 2 1 0 2 0 1 2 0 2 1 1 2 0 1 2 2 0 1 0 2 1 2 1 0 1 1 1 0
1 2 0 2 1 0 0 1 2 1 0 2 0 1 2 0 1 1 2 1 0 2 0 1 2 1 2 0 2 1
0 1 2 0 1 2 2 0 2 1 0 1 2 0 2 0 1 0 0 2 0 1 2 0 1 2 2 2 1 0
0 1 2 0 1)

結果はご覧の通り.

2010年8月25日水曜日

Penroseタイル

今回はPenrose tilingの絵の描き方のことである. Penrose tileには

のようにkite(凧)とdart(矢)の2種類のタイルを使うものと,

のようにthick(でぶ)とthis(やせ)の2種類のタイルを使うものとがあるらしい.

これらのタイルは, 菱形以外に組合わせると, 平行移動方向の周期的パターンで平面を埋めることが出来ないことで知られている. どちらのタイルにも, 赤と青の円弧が描いてあるのは, 菱形が出来るのを禁止するからで, タイルを置く時は, 同じ色の円弧が接続する必要がある.

従って, 沢山のタイルによるパターンを描くには, タイルを同型のタイルに分割し(これをdeflationという), 再帰的に埋めていく方法を用いる.

分割はタイルの半分について行うので, 分割を示す破線が描いてあり, 緑の線は半分のタイルの起点を示す.

半分のタイルは, 上には0, 下には1をつけて区別する.

今回は, 私がPostScriptで書いたプログラムの話をしたい.

上の2組のタイルの絵は, googleで探したもので, 凧の方はWolfram MathWorldのだ. kiteとdartが長さで与えられ, thickとthinが角度で与えられているのも, 出所が違うからだ.

kiteの辺ABがφ+1, BCがφ-1+1と示されているが, WolframMathWorldにそう書いてあったからだが, kiteの青の円弧の半径がφで, 赤の円弧の半径が1, dartの青の円弧の半径が1で, 赤の円弧の半径がφ-1であることも示す. φはもちろん黄金比 (√5+1)/2である. φの計算に慣れている人には分かるように, φ+1は実はφ2, φ-1+1は実はφである. 従ってAB:BCはφ:1である. kiteとdartは, dartを左右逆にするとkiteに密着出来て菱形になる. 菱形の長い対角線をφ:1に分けた点がCになる. つまりkiteのAC:dartのAC=φ:1. kiteのCABもdartのBCAも2等辺三角形である.

kiteの∠CABを計算しよう. AからBCの中点Eに垂線を引くと, 直角三角形AEBについて, sin ∠EAB=1/2φ=sin 18°, つまり∠CAB=36°である. ゆえに∠ABC = ∠ACB=72°である. dartについては, ∠CAB=∠ABC=36° である.

(注: sin 3α=3 sin α-4 sin3α, cos 2&alpha=1-2 sin2α. &alpha=18°の時, sin 54°=cos 36°からsin 18°は解ける. sin 18°は(√5+1)/4.)

ここでthinの上半分を見ると, ∠CAB=∠ABC=72°だから, thin0はkite0と同じ形である. また大きさは違うが, thick0はdart0と相似形である.

kite0は下のようである. この図の上は, 1個のkite0の描き方で, 左端の原点(緑の線が出発する位置)から, 36°方向へφ2だけ線を引き, 次にそこから-72°方へφだけ引くことを示す.

図の下は, 1個のkite0の分割法で, kite0'が出来るところである. (分割後のタイルにはプライム(')をつけて区別する.)kite0'の左の三角は, dartの片割れだが, 緑の線からdart1であることが分かる. また右の方はkite0とkite1で出来ている. つまり左端に原点を持ち, 36°に向けたdart1を置き, 36°方向へφ2行った所に原点を持ち, 252°に向けたkite0とkite1を置けばよいことを示す. kite0は長い辺がφ, 短い辺が1であった. 分割の結果は, 短い辺がkiteの長い辺で出来ているから, タイルの大きさは1/φになった. 従って, 分割の図のスケールはφ倍で示してある. 上の図のφ2が下の図ではφ3になるのは, そのためである.

そろそろプログラムの出番だ.

描画の出発点は緑の線のついている頂点で, 頂点の座標x, yと緑の基本の線の方向aを貰い, タイルを描く. kite0は(0,0)から出発, 36度の方向にφの長さの線を引く. 次に-72度の方向に1の長さの線を引く. これをPostScriptで

0 0 moveto φ 36 xy lineto one -72 xy rlineto

のように書く. xyは線の長さ l と方向 a を貰い, その先のx, yの位置を返す関数である.

/xy {2 dict begin /a exch def /l exch def l a cos mul l a sin
mul end} def

kite0'の描き方は, まずスケールを1/φにする. (0,0)の位置に36度の方向でdart1を描く. 次は36度の方向にφ行った所を原点とし, -108度の方向でkite0とkite1を描く. 注意点は, φ行ったところといっても, スケールが1/φになっているから, φ2行く必要があることだ. このことさえ忘れなければ, すべての絵は描ける.

0 0 36 dirt1 phi3 36 xy 252 kite0 phi3 36 xy 252 kite1

phi3はφ3に相当する長さのつもりである.

kite1, dart0, dart1の分割は以下の通り.

dart0

dart1

thickとthinも同じだ.
thick0

thick1

thin0

thin1


kiteとdartのプログラムは以下のとおり.

/phi 5 sqrt 1 add 2 div def /one 80 def
/init {/phs n 5 add array def /f one def
n -1 0 {/i exch def /f f phi div def phs i f put} for
phs n 1 add one put /one one phi mul def phs n 2 add one put
/one one phi mul def phs n 3 add one put
/one one phi mul def phs n 4 add one put} def
/ph {phs exch n add get} def
/xy {2 copy cos mul 3 1 roll sin mul} def
/red {1 0 0 setrgbcolor arc stroke} def
/blue {0 0 1 setrgbcolor arc stroke} def
/green {0 1 0 setrgbcolor 0 0 moveto 1 ph 0 lineto stroke}def

/kite0 {3 dict begin /a exch def /y exch def /x exch def
gsave x y translate a rotate
n 0 eq {0 setgray 0 0 moveto 3 ph 36 xy rlineto
2 ph -72 xy rlineto stroke
0 0 2 ph 0 36 blue 3 ph 0 1 ph 108 180 red green}
{/n n 1 sub def 0 0 36 dart1 4 ph 36 xy 252 kite0
4 ph 36 xy 252 kite1 /n n 1 add def} ifelse
grestore end} def

/kite1 {3 dict begin /a exch def /y exch def /x exch def
gsave x y translate a rotate
n 0 eq {0 setgray 0 0 moveto 3 ph -36 xy rlineto
2 ph 72 xy rlineto stroke
0 0 2 ph -36 0 blue 3 ph 0 1 ph 180 252 red green}
{/n n 1 sub def 0 0 -36 dart0 4 ph -36 xy 108 kite0
4 ph -36 xy 108 kite1 /n n 1 add def} ifelse
grestore end} def

/dart0 {3 dict begin /a exch def /y exch def /x exch def
gsave x y translate a rotate
n 0 eq {0 setgray 0 0 moveto 3 ph 36 xy rlineto
2 ph 252 xy rlineto stroke
0 0 1 ph 0 36 blue 2 ph 0 0 ph 72 180 red green}
{/n n 1 sub def 0 0 0 kite0 4 ph 36 xy 216 dart0
/n n 1 add def} ifelse
grestore end} def

/dart1 {3 dict begin /a exch def /y exch def /x exch def
gsave x y translate a rotate
n 0 eq {0 setgray 0 0 moveto 3 ph -36 xy rlineto
2 ph 108 xy rlineto stroke
0 0 1 ph -36 0 blue 2 ph 0 0 ph 180 288 red green}
{/n n 1 sub def 0 0 0 kite1 4 ph -36 xy 144 dart1
/n n 1 add def} ifelse
grestore end} def

300 400 translate
/n 3 def init
0 72 288 {/a exch def 0 0 a kite0 0 0 a kite1} for
showpage

これで描いたn=3の図は次のようだ.

ここで, 最初に作る配列 phs は, φの等比級数を保持する. 再帰が深くなる, つまり, nが小さくなるにつれ, phsの添字の小さい方を使うようになっている.

thickとthinも同様なので, 省略する.

余計なことながら, YouTubeにdeflationの面白い動画があった.

2010年8月20日金曜日

都府県の接続グラフ

TAOCP vol.4にContiguous United States of Americaというグラフがある.



アメリカのハワイとアラスカを除く, 本土の48州とDCの隣接関係をグラフにしたものだ. 州名は郵便コードか何かの略号で書いてあるが, 大体は推測がつく. 殆んどは3つの州を頂点とする三角形の辺のグラフで, 注目すべきは左のUT, CD, NM, AZの四角と,中央上のWI, MI, IN, ILの四角だ. 前者は有名な4 sates cornerであり, 後者はミシガン湖である.

前から日本の都府県についても書いてみたいと思っていたところ, やっと書くことが出来た. もちろん北海道と沖縄は入っていない.


関東地方では古河のあたり, 茨城と埼玉が隣接し, 栃木と千葉を隔てているなど, クリティカルな場所がはっきりする. 隣接県の数(次数)が多い県は長野(8)であり, 最小は長崎(1)である. 長野が多いのは 信濃の国は十州に境連ぬる国にして の歌の通りだ.


ついでだが, 隣接する辺は次の通り. 頂点の番号は, 都道府県コードである.

((2 3)(2 5)(3 4)(3 5)(4 5)(4 6)(4 7)(5 6)(6 7)(6 15)(7 8)
(7 9)(7 10)(7 15)(8 9)(8 11)(8 12)(9 10)(9 11)(10 11)(10 15)
(10 20)(11 12)(11 13)(11 19)(11 20)(12 13)(13 14)(13 19)
(14 19)(14 22)(15 16)(15 20)(16 17)(16 20)(16 21)(17 18)
(17 21)(18 21)(18 25)(18 26)(19 20)(19 22)(20 21)(20 22)
(20 23)(21 23)(21 24)(21 25)(22 23)(23 24)(24 25)(24 26)
(24 29)(24 30)(25 26)(26 27)(26 28)(26 29)(27 28)(27 29)
(27 30)(28 31)(28 33)(29 30)(31 32)(31 33)(31 34)(32 34)
(32 35)(33 34)(34 35)(36 37)(36 38)(36 39)(37 38)(38 39)
(40 41)(40 43)(40 44)(41 42)(43 44)(43 45)(43 46)(44 45)
(45 46))

辺の数は86である.

2010年8月10日火曜日

リレー加算器

以下は夏休み工作の記である.

前回の説明通り, 全加算器は4極双投のリレー2個で実現出来る. 田中君によると, 4極双投のリレーは市販されている, というので, 秋葉原へ出かけ, パナソニック電工の12volt駆動のAHJ3241(1個270円)を8個購入した. (写真はパナソニック電工のカタログから)


スイッチは, A0,...,A3, B0,...,B3の入力用8個の他, C0 inも欲しい(最下段に入れる繰上げは, 減算で必要). 始めの8つはオンオフだが, 最後のCは, 切替えなので, 全部同じ切替えスイッチ9個を購入(1個130円). LEDはS0,...,S3の4個の他, C3 outも含めて5個購入(12volt用 1個30円)した. 従って, 合計3480円也であった.




これが組立て用の図である. 下の方に8個のリレーがあり, 上下のリレーが対の全加算器が4個配置されている. 赤が12voltの線. 青がアースである.

上が操作パネルの裏側で, 上の方にLEDが5個. その下にスイッチが二進数A用に4個, B用に4個. 下から入れる繰上げCin用に1個配置する.

スイッチは下向きを0, 上向きを1にしたい. 裏の端子では, スイッチを上向きにすると, 中と下が接続する. 従って, 左に書いてある繰上げ用スイッチは, 上の端子が¬Cin用である.

AのリレーのA0,A1,A2,A3の端子, BのリレーのB0,B1,B2,B3の端子, それぞれ操作パネルの対応するスイッチに, B0リレーの9と10番の端子は, スイッチCinの¬CとCに接続する.

Aの各リレーの10番の端子Sは, 対応するLEDへ, B3リレーの12番の端子Cは, CoutのLEDに接続する.

この図では操作パネルの方が幅狭く描いてあるが, 実際はパネルは幅が100ミリ. リレーは1個の幅が21.5ミリ, 4個で86ミリであり, リレーの方が幅は狭い.

パネルの下の方, 裏面にリレーを固定してある.

電源は, パソコン用のアダプターを利用した.

完成した加算器の写真を以下に示す. (Coutのラベルのところは, LEDの基盤取りつけネジの穴と重なってしまった. LEDの取りつけ方は最後まで決らなかったので, こういうことに.)


表側


裏側

工作は私の属している研究所の工作室で行った. 電気回路をいじるのは実に久しぶりなので, 研究所の宇夫君に最新技術をいろいろ教えて貰った. 工作後一番の感想は, 視力がずいぶん落ちていることだが, 年のことを考えるとまぁ仕方ないか.

2010年8月8日日曜日

十六進乗算表

1985年頃, NTTの電気通信研究所でLispマシンの研究をしていた. そのマシンをELISという. Eは通研 (Electro Communication Laboratories) LISはLispである.

そのプロジェクトで作られた計算機の何台かが, JAIST(北陸先端科学技術大学)にあり, 8月7日から9日にかけて, JAISTでELIS復活祭というイベントが行われた. 20年くらい前の計算機の電源を入れ, もう一度走らせてみようというのである.

同時に多くの発表もあった.

私もLispプログラマなので, お誘いを受け, 参加し, 楽しい時を過している.

そのプロジェクトの最後の時期に TAO/SILENTというのがあり, その発表の時, 当時開発メンバーが十六進法をどう読んでいたかという話題になった. つまりFAB1を「エフエイビーイチ」ではなく, フタブイのように読むのである. これは面白いと思い, 早速(十進の九々に相当する)十六進の乗算表を作ってみた.

まず読み上げ方. 数の次が標準の読み方で, 読みにくい時はかっこ内が使える.

0 レ(オ)
1 イ
2 ニ
3 サ(ミ)
4 ヨ(シ)
5 ゴ
6 ロ(ム)
7 ナ
8 ハ(バヤ)
9 ク
A タ(カ)
B ブ(ボ)
C チャ
D ド
E テ(ケ)
F フ

とりあえず, 十六進数で乗算表を作ると, 次のようになる. 九々も0と1の段がないが, ここでも2の段から始まる. 最初は十六進でもニニガシである. 横に14個並ばないので, 縦長になり過ぎたが.

2204 2306 2408 250A 260C 270E 2810
2912 2A14 2B16 2C18 2D1A 2E1C 2F1E

3206 3309 340C 350F 3612 3715 3818
391B 3A1E 3B21 3C24 3D27 3E2A 3F2D

4208 430C 4410 4514 4618 471C 4820
4924 4A28 4B2C 4C30 4D34 4E38 4F3C

520A 530F 5414 5519 561E 5723 5828
592D 5A32 5B37 5C3C 5D41 5E46 5F4B

620C 6312 6418 651E 6624 672A 6830
6936 6A3C 6B42 6C48 6D4E 6E54 6F5A

720E 7315 741C 7523 762A 7731 7838
793F 7A46 7B4D 7C54 7D5B 7E62 7F69

8210 8318 8420 8528 8630 8738 8840
8948 8A50 8B58 8C60 8D68 8E70 8F78

9212 931B 9424 952D 9636 973F 9848
9951 9A5A 9B63 9C6C 9D75 9E7E 9F87

A214 A31E A428 A532 A63C A746 A850
A95A AA64 AB6E AC78 AD82 AE8C AF96

B216 B321 B42C B537 B642 B74D B858
B963 BA6E BB79 BC84 BD8F BE9A BFA5

C218 C324 C430 C53C C648 C754 C860
C96C CA78 CB84 CC90 CD9C CEA8 CFB4

D21A D327 D434 D541 D64E D75B D868
D975 DA82 DB8F DC9C DDA9 DEB6 DFC3

E21C E32A E438 E546 E654 E762 E870
E97E EA8C EB9A ECA8 EDB6 EEC4 EFD2

F21E F32D F43C F54B F65A F769 F878
F987 FA96 FBA5 FCB4 FDC3 FED2 FFE1

これはこんなプログラムで生成する.

(for-each (lambda (a)
(newline) (newline)
(for-each (lambda (b)
(display (string-append (number->string a 16)
(number->string b 16)
(number->string (quotient (* a b) 16) 16)
(number->string (modulo (* a b) 16) 16) " ")))
(a2b 2 9))
(newline)
(for-each (lambda (b)
(display (string-append (number->string a 16)
(number->string b 16)
(number->string (quotient (* a b) 16) 16)
(number->string (modulo (* a b) 16) 16) " ")))
(a2b 9 16))) (a2b 2 16))

関数 (a2b m n) は, (m m+1 ... n-1) のリストを作る. このプログラムを多少手直しすると, 九々ではなく, フフが得られる. 長い段は途中で折り返してあるので, 要注意.

気づている人もあろうが, 九々では積が1桁の場合, ニニガシのように, 「ガ」を挿入する. 下の表も「ニニガヨ」から始まる.


こんなもの, 使えるだろうか.

ニニガヨ ニサガロ ニヨガハ ニゴガタ ニロガチャ ニナガテ
ニハイレ
ニクイニ ニタイヨ ニブイロ ニチャイハ ニドイタ ニテイチャ
ニフイテ

サニガロ ササガク サヨガチャ サゴガフ サロイニ サナイゴ
サハイハ
サクイブ サタイテ サブニイ サチャニヨ サドニナ サテニタ
サフニド

ヨニガハ ヨサガチャ ヨヨイレ ヨゴイヨ ヨロイハ ヨナイチャ
ヨハニレ
ヨクニヨ ヨタニハ ヨブニチャ ヨチャサレ ヨドサヨ ヨテサハ
ヨフサチャ

ゴニガタ ゴサガフ ゴヨイヨ ゴゴイク ゴロイテ ゴナニサ
ゴハニハ
ゴクニド ゴタサニ ゴブサナ ゴチャサチャ ゴドシイ ゴテシロ
ゴフシブ

ロニガチャ ロサイニ ロヨイハ ロゴイテ ロロニヨ ロナニタ
ロハサレ
ロクサロ ロタサチャ ロブシニ ロチャシハ ロドシテ ロテゴヨ
ロフゴタ

ナニガテ ナサイゴ ナヨイチャ ナゴニサ ナロニタ ナナサイ
ナハサハ
ナクサフ ナタシロ ナブシド ナチャゴヨ ナドゴブ ナテロニ
ナフロク

ハニイレ ハサイハ ハヨニレ ハゴニハ ハロサレ ハナサハ
ハハシレ
ハクシハ ハタゴレ ハブゴハ ハチャロレ ハドロハ ハテナレ
ハフナハ

クニイニ クサイブ クヨニヨ クゴニド クロサロ クナサフ
クハシハ
ククゴイ クタゴタ クブロサ クチャロチャ クドナゴ クテナテ
クフハナ

タニイヨ タサイテ タヨニハ タゴサニ タロサチャ タナシロ
タハゴレ
タクゴタ タタロヨ タブロテ タチャナハ タドハニ タテハチャ
タフクロ

ブニイロ ブサニイ ブヨニチャ ブゴサナ ブロシニ ブナシド
ブハゴハ
ブクロサ ブタロテ ブブナク ブチャハヨ ブドハフ ブテクタ
ブフタゴ

チャニイハ チャサニヨ チャヨサレ チャゴサチャ チャロシハ
チャナゴヨ チャハロレ
チャクロチャ チャタナハ チャブハヨ チャチャクレ チャドクチャ
チャテタハ チャフブヨ

ドニイタ ドサニナ ドヨサヨ ドゴシイ ドロシテ ドナゴブ
ドハロハ
ドクナゴ ドタハニ ドブハフ ドチャクチャ ドドタク ドテブロ
ドフチャサ

テニイチャ テサニタ テヨサハ テゴシロ テロゴヨ テナロニ
テハナレ
テクナテ テタハチャ テブクタ テチャタハ テドブロ テテチャヨ
テフドニ

フニイテ フサニド フヨサチャ フゴシブ フロゴタ フナロク
フハナハ
フクハナ フタクロ フブタゴ フチャブヨ フドチャサ フテドニ
フフテイ

この方のプログラムは, 以下の通り.

(define kana0 '
("レ" "イ" "ニ" "サ" "ヨ" "ゴ" "ロ" "ナ"
"ハ" "ク" "タ" "ブ" "チャ" "ド" "テ" "フ"))
(define kana1 '
("ガ" "イ" "ニ" "サ" "シ" "ゴ" "ロ" "ナ"
"ハ" "ク" "タ" "ブ" "チャ" "ド" "テ" "フ"))
(define (foo n)
(display (list-ref kana1 (quotient n 16)))
(display (list-ref kana0 (modulo n 16))))
(define (bar n)
(display (list-ref kana0 n)))

(for-each (lambda (a)
(newline) (newline)
(for-each (lambda (b)
(bar a) (bar b) (foo (* a b)) (display " "))
(a2b 2 9))
(newline)
(for-each (lambda (b)
(bar a) (bar b) (foo (* a b)) (display " "))
(a2b 9 16)))
(a2b 2 16))

2010年8月2日月曜日

リレー加算器

リレーの話だ. 運動会とは関係ない. ここでいうリレーは電気部品で, 電気信号を継続するという意味から, 和語では継電器という.

私が学生時代に所属していた研究室では, 私が研究室に入る少し前までは, 論理回路の素子はリレーであり, それを使って, ディジタル抵抗計を試作したりしていた. 従って, 研究室にはリレーが沢山あった. 物理教室の実験室には, 直流電源が来ていたから, リレーの実験は簡単で, 私も電話交換機に使う回転スイッチを回して遊んだりしたものだ.

当時, 工学部にはリレー回路の講義があった. 私は大学院生になると, 応用物理学科の磯部教授の, William Keisterの教科書The Design of Switching Circuitsによる講義に出席した. もちろん当時は, その後で私もその学科のメンバーになるとは, まったく思わなかった.

私自身は, ちょうど後藤さんがパラメトロンを発明した直後だったから, 論理回路といえばパラメトロン一点張りであり, リレーの経験はない. そこで一度リレーで二進4桁くらいの加算器を作ってみたいと思っていた.

昨年の夏だったか, 日本橋学館大学の田中君が, リレーの加算器を見せてくれたのに刺激され, 私も実現に向け, 少しずつ進んだ.

まずリレーのおさらいを少々.

リレーには働きにより3種類あり, 左からmake, break, transferという. 下の箱にワイヤが巻いてあるのが電磁石で, 電流が流れると(1の時), その磁力により, 普段(0の時)はバネで上の位置にあるスイッチが下の位置になる.

makeは0の時, 左右の回線が切れ, 1の時, 繋がる. breakは0の時, 回線が繋がり, 1の時, 切れる. transferは, 0の時, 左の回線は右の上と繋がり, 1の時, 下と繋がる. このtransferは, 切替えの時, 左の回線は一旦, 上下のいずれとも切れるが, transferには, 一旦上下両方に繋がるタイプもある.

注意: リレーの回路は, このように, 電流が流れていない時(0の時)の図を描くことになっている.


こういうリレーを想定し, 2ヶ月程前, 二進加算器のリレー回路なんか簡単さと思って, 下のように設計した.


図が左右に長いので, 途中で分割してあり, 上の図の右が, 下の図の左に続く.

一番下の桁a0, b0の和がs0で, 繰上げがc1である. 次のa1, b1, c1の和がs1で, 繰上げがc1である. のように見る.

そして, 田中君に意見を求めたところ, 繰上げにリレーを使うと遅くなるからよくないというコメントが早速来た. そしてZuseの回路(dual-rail-carry full adder)を教えてくれた.



これがニ進1桁分, いわゆる全加算器である. 1桁のaとbと, 下の桁からの繰上cinを足す. この入力に対し, 出力はこの桁の和outと, 上の桁への繰上げcoutである.

この回路の最大の味噌は, 繰上げに裏回路があることだ. (dual circuitという.) つまりcinと¬cin, coutと¬coutがある. 回路図では, notは上線で表現するが, htmlでは書けないので, この説明では¬を使う.

左のb=0と書いてある上が, リレーbで動く(つまりbの値の0,1で動く)リレーで, 4回路のtransferになっている. 4極双投(four pole double throw)ともいう.

右手のa=0と書いてある上がのリレーaである. aとbは上下が反対になっているが, 図を簡単にするためだ.

この他, V+には, 出力を駆動する電源を繋ぐ. (常時1になっている.)

前述のように, aのリレーもbのリレーも0の時の図なので, この時の注目すべき回線を赤線で示す. つまりこの時は, V+の1が¬coutを1にしている. cin, ¬cinはいずれかが1のはずだが, ¬cinが1なら, その先はどこにも繋がっていないので, 関係なし. cinが1なら, 下から繰上げがあり, outを1にする.

全加算器の真理値表は下のようだ. 計算機屋なら夢の中でも書けるはずだ.


入力 出力
a b c s c ¬c
0 0 0 0 0 1
0 0 1 1 0 1
0 1 0 1 0 1
0 1 1 0 1 0
1 0 0 1 0 1
1 0 1 0 1 0
1 1 0 0 1 0
1 1 1 1 1 0

さてZuseの回路のチェックは次のようにする. まずoutが1になる条件を調べる. aとbの組合せを4通り書き, outが1になる条件を探す. つまりoutから逆にV+かcinか¬cinを見るわけである. 0 0ならc=1だ. 0 1ならbの節点を上に切替えてみると, ¬cinに辿り着くからc=0だ. このようにして書くと

a b c
Out= 0 0 1
0 1 0
1 0 0
1 1 1

が得られ, 二進3変数の和であることが分かる. 同様にして, cout, ¬coutも書いてみる. xはそういうcはないこと, oはcに関係なく1になることを示す.

a b c
cout 0 0 x
0 1 1
1 0 1
1 1 o

a b c
cnot 0 0 o
0 1 0
1 0 0
1 1 x

というわけで, この全加算器回路は正しいことが分かる. 繰上げが伝搬する場合, aがすべて0, bがすべて1, 一番下のcinが1なら, 右から来たcinは左のcoutから出ていき, aとbのリレーの動作が終った途端に一番上のcoutを1にする.

ウェブページを探したら, リレーを使って計算機を作ったという, やはり物好きな報告を見つけた.
http://web.cecs.pdx.edu/~harry/Relay/RelayPaper.htm
Konrad Zuseの全加算器の説明の後, "Except for the full adder, I designed all circuits used in my computer."と書いてあるから, この加算器は誰にも真似の出来ない完成品なのであろう.

Processingで描いたこの回路のシミュレータが, http://playground.iijlab.net/~ew/relayadder/relayadder.htmlにある. (ダウンロードには多少時間がかかります.) 右下のa,b,cの枠内をクリックすると, その値の0,1が反転する.
キーボードのキーを押しても値は変わる.