JavaScriptでセル・オートマトンのワイヤーワールドを作りました。

logisimやマインクラフトで回路を作ったりしていてデジタル回路を学んでいるときに、セル・オートマトンのワイヤーワールドを見つけました。セル・オートマトンでは、コンウェイのライフゲームが有名ですが、このワイヤーワールドは回路図と同じような仕組みなので非常に興味深いです。またライフゲームに比べると規則が非常にシンプルです。

規則

状態

セルは以下の4つの状態のどれかです。色は特に必要なくて、グレースケールなどでも問題ないです。見やすいように、導体(電子が流れるところ)を黄色にして、電子を青赤で表現するのが多いようです。

  • 空(Empty)は黒
  • 導体(Conductor)は、黄色
  • 電子の頭(Electron Head)は、青
  • 電子の尾(Electron Tail)は、赤

世代ルール

世代は単純に、ゲーム中の1ループのことです。

  • 電子の頭は、電子の尾になる
  • 電子の尾は、導体になる
  • 導体は、近傍セル(その導体の周りのセルの事)のうち、1つまたは2つのセルが、電子の頭であった場合、その導体セルは、電子の頭になる

最後がちょっとわかりづらいので画像で説明します。

中央の導体セルから、周り8個を見る

上記図は、中央の導体セルから、周り(近傍きんぼう)の8個のセルを見ると、画像の左側は、青が1つ、画像の右側は青が2つあります。この時に次の世代に進むと、以下画像になります。

注目してほしいのは、中央の導体セルが黄色から、世代ルールにより、青に変わったところです。

たったこれだけのルールですが、これコンピュータが作れます。

まさに電子(Electron)のよう!

ゲームループを動かすと、世代ルールが適用されて電子の頭(青)と電子の尾(赤)が移動しているのが分かります。

 

ダイオード

 

NOT回路・インバーター

確かに、世代ルールが適用されて、電子が流れなくなるので、NOT回路と同じになります。ですがこれだけ単純だと不思議な感じがします。

 

ソースコードをもう少し綺麗にしたらデモもアップロードしようと思います。現在のソースコードはgithubにアップロードしました。

ソースコード

https://github.com/dev001hajipro/wireworld

参考資料

ゲートICやレジスターを作るには以下が参考になりそうです。

https://www.quinapalus.com/wi-index.html

ワイヤーワールドでデジタル回路のNOT回路やOR回路など基本的なものを作るときの参考になりそうです。

http://karlscherer.com/Wireworld.html

 

便利なレッドストーン回路シミュレータの一覧とソースコード

マインクラフトでレッドストーン回路をやってみると、単純な回路でもかなりの大きさになるのがわかります。移動してブロックを設置するのも結構面倒です。ちょっと回路を試す場合はレッドストーン回路シミュレータが便利です。

レッドストーン回路シミュレータを調べると英語版でいくつか種類が見つかったので有名なものををまとめてみます。

Baezons redstone simulator

http://www.minecraftforum.net/forums/mapping-and-modding/minecraft-tools/1260528-baezons-redstone-simulator-v2-2

Baezonsさんが作成したレッドストーンシミュレータです。Baezonさんのシミュレーターを基本として、いろんな人が拡張したようです。ソースコードはgithubにあります。

https://github.com/digama0/MCRedstoneSim

 

Simnik Circuit Simulator

http://www.minecraftforum.net/forums/minecraft-discussion/redstone-discussion-and/344005-circuit-simulator-v0-82-1-0-0-compatibel

リピーターを使えるようにした物です。現在はソースコードはダウンロードできないようです。

Circuit Simulator v0.81-rek

http://www.minecraftforum.net/forums/minecraft-discussion/redstone-discussion-and/342852-circuit-simulator-v0-81-rek

Simnik Circuit Simulatorをフォークしてピストンを追加したものです。ソースコードはzipファイル内にあります。

Mordritch’s JavaScript Redstone Simulator

オンラインですぐ試せるレッドストーン回路シミュレータです。コンパレータはありませんが、リピーターやピストンもあるので一通り遊べそうです。

http://mordritch.com/mc_rss/

Minifyしたソースコードは公開していますが、元のコードは公開していないようです。ですが、以下githubに似たようなコードがあるようです。

https://github.com/JonathanLydall/JavaScript-Redstone-Simulator

 

マインクラフトのDラッチの回路図を書く

マインクラフトは、リピーターをロックさせる仕組みで簡単にDフリップフロップ回路が作成できますが、今回はより理解を深めるため、マインクラフトの回路図から、実世界のDラッチの回路図を書いて確認します。

マインクラフトの回路の信号方向 でも書きましたが、以下のようなマインクラフトの回路図は、レッドストーントーチにより信号の方向性が生まれるので注意する必要があります。

上部がDラッチ

https://www26.atwiki.jp/minecraft/pages/26.html 引用

 

 

真理値表

C D Q ~Q
 0  0  0
 0  1  1
 1  0  保持
 1  1  保持

www.falstad.comで書いたDラッチの回路図

http://tinyurl.com/j46pcvm

Logisimで書いたDラッチの回路図

まとめ

真理値表通りに動くのでたぶんこの回路図であっていると思います。マインクラフトの回路図から、実世界で使われる回路図にしてみました。ポイントとしては、レッドストーントーチが指向性を持つので、その先のワイヤーが交差する箇所で、単純に分配しているのか、OR回路になって1つのワイヤーになるのかをしっかり確認することです。

 

 


マインクラフトの回路の信号方向

マインクラフトではレッドストーントーチとブロックを組み合わせてNOT回路が作成できます。またこのような回路の場合、信号の流れが特定方向に固定されます。

https://www26.atwiki.jp/minecraft/pages/1037.html

Aから~Q側へ信号が流れそうですが、黄色いブロックについているレッドストーントーチがあるため、Aから~Q側には流れません。回路図で書くと以下になります。

真理値表

A B Q ~Q
 0  0  1  0
 0  1  0  1
 1  0  1  0
 1  1  1  1

 

Dフリップフロップ回路を作成するときに、このような構造が出てきます。

 


マインクラフトでDラッチ

Dフリップフロップ回路はデータを保存できるので、複数並べるとレジスターになります。最新のマインクラフトではレッドストーン回路のリピーターで信号を止めることができるため、これで先ずはDラッチ回路を作ってみます。

 

2bitのレジスター

参考資料

https://www26.atwiki.jp/minecraft/pages/26.html#id_c8183ecb

 

Dラッチ回路

画像のようにリピーターを交差するような感じで配置します。

リピーターをこのように並べると、以下Gif画像のように信号が伝わらないように遮断棒がでてきます。

右上のリピーターに、棒が表示される

左側のリピーターのように棒が横たわると、リピーター上を信号が伝わらなくなります。

遮断棒が下りているので、スイッチを押しても信号が伝わらない。

もう一度、リピーターを見てみましょう。リピーターは、レッドストーントーチで出来ています。遮断機が下りて、左のスイッチからの信号が伝わらなくなります。ですが、リピーターのレッドストーントーチは、以前の状態を保持しているので、出力も以前の状態になります。現在のスイッチの変更は関係なくなります。これは遮断機が下りた時の状態を保持している事になります。

つまり、これを並べるとメモリーやレジスターになります。

リピーター上のレッドストーントーチが遮断機が下りても、前の状態を保持

黄色いブロックにレッドストーントーチを横につけてNOT回路を作っていますが、これは、クロックを表す側のリピーターがONになったときに、(=Highになったとき)に、状態を保持するためです。これをハイレベルエッジと言います。

マインクラフトではまだわかりませんが、現実世界のハードウェアでは、このレベルエッジを適宜切り替えて使っているそうです。

 

まとめ

マインクラフトでDラッチ回路を作成しました。次回はDフリップフロップ回路を作って、クロック入力の立ち上がり時のみ入力状態が反映され、それ以外では保持されるようにしてみます。

 

Falstad’s Curcit Simulatorでデジタル回路の書き方(注意点)

この記事では、Falstad’s Curcuit Simulator Appletでデジタル回路を書く方法と注意点を簡単に説明します。アナログ回路が豊富にありますが、デジタル回路の順序回路の勉強のために使うため、そこだけに特化して説明します。またワイヤーの配線時に注意が必要なのでそこも詳しく説明します。

私の現状

Logisimでデジタル回路を学び、最近はマインクラフトで回路を実装してみようといろいろ調べています。Logismは教育用の無料のシミュレータで、レジスターやRAM、ROM、FlipFlop回路などはあらかじめICのような部品として用意されています。これをAND、ORなどの論理回路を使って書きたいですが、Logisimでは、順序回路のようなフィードバックがある回路は信号をシミュレートしていないので正常に動作しません。

マインクラフトでCPUを作ろうとすると、保存する仕組みをマインクラフトで実装する必要があります。ですが、マインクラフトのレッドストーン回路はいろいろ癖があるので、まずはFalstad’s Curcuit Simulator Appletで回路図を書くことにしました。

Falstad’s Curcuit Simulator Appletの基本操作

falstad’s Curcuit Simulatorは、信号のシミュレートもしているので、コンデンサーや抵抗を使うような回路は、電気の流れも確認できます。

視覚的に分かりやすい!

操作は、初心者向きではありません。何らかのシミュレーターなどを使った人向けで、右クリックのコンテキストメニューから各部品を選択するか、キーボードのショートカットで部品を選択します。

削除

Ctrl+Aで全選択して、DELETEキー

または、メニュー[Circuits]->[Blank Circuit]

選択モード

スペースキーで選択モードになります。またはShiftキーで範囲選択でも選択モードになります。スペースキーを押して現在選択モードであるかは、右クリックのコンテキストメニューから確認できます。またアイコンが十字マーク出ない場合は、選択モードです。

ワイヤーが斜めになっていたり、移動したり、引き延ばしたりするときは、選択モードで行うので、スペースキーを使う事をお勧めします。

シフトキーを押しながら範囲選択しているところ

デジタル回路の選択方法

メニューの[Draw]または右クリックで、コンテキストメニューが表示されるので、ここからワイヤーやデジタル回路を選択します。

右クリックして、[Logic Gates, Input and Output]を開いたところ
デジタル回路(論理回路)を書く場合は、コンテキストメニューの[Add Wire]、[Logic Gates, Input And Output]、[Digital Chips]になります。上から5場面目に[Outputs and Labels]があるので、ここからLEDやラベルなども選択できます。

Logisimと同様に順序回路などもICとして用意されている

部品の配置方法

部品の配置方法が独特でコンテキストメニューで選択して、クリックしながら、つまりドラッグで配置します。一般的なソフトウェアは、アイテムを選択してマウスを移動すると、そのアイコンが透過で表示されたりして分かりやすくクリックで配置するものも多いので、これが分かっていないと部品を配置できずに戸惑います。

配線の調整

ワイヤーを選択して、点から点を繋げると接続できます。また選択モードにしてワイヤーを選択すれば移動や長さの調整ができます。

配線の注意!!!

配線は点と点を繋げると接続します。点と線では接続されません。

この回路シミュレータは、点から線に接続すると、赤い点が表示されて接続しません。点から線にワイヤーを引くと、交差する部分が点になるので接続しているように見えますが接続していません。

非常に直感的ではなく、かつエラーが分かりづらいです。ワイヤーを移動したり長さを調節して、必ず点と点で接続してください。

以下画像は、接続していない例です。新しいワイヤーの点を、線に向かって繋げているので、赤点がひょうじされて接続されていません。

交差して赤い点が表示されるが接続されていない!!!

次の画像は、新しいワイヤーの点を、別のワイヤーの点にむかって繋げているので、白点が表示されて接続されています。

ワイヤーは点と点で接続!!!

SRラッチの例

以下画面の上部のSRラッチは、ワイヤーの点と線で繋げようとしているため、赤点が表示されて接続されていません。一方、下のSRラッチは、ワイヤーの長さを調節して、点と点で繋げているため、白点で表示されて接続されています。

ワイヤーを選択して、回路図のワイヤーなどの上でマウスボタンを押し続けると以下のように部品とワイヤーの接続点が確認できます。また赤点が出た場合は、右下のメッセージで、[2 bad connections]のように表示されていますが、これも非常に分かりづらいです。

 

まとめ

Falstad’s Curcit Simulatorで論理回路を作るときの操作方法を説明しました。非常に独特な操作方法ですが、わかってしまえば手軽に試せます。Logisimは使いやすいですが、順序回路をうまく扱えないので、このFalstad’s Curcit Simulatorを併用するとよさそうです。

 

スタックマシンのlogisimのサンプルを探す。

[Implementing a One Address CPU in Logisim]で1つのレジスターを使うハーバード・アーキテクチャのシンプルなCPUを作成しました。スタックマシンは演算にRAMなどのスタック領域を用意してレジスターはないはずです。

今の知識では回路図を書くのは無理なので、Logisimでstack machineの実装を探したら、UMBC(ユニバーシティ・オブ・メリーランド, ボルティモア・カウンティー)の

https://www.csee.umbc.edu/~chang/cs313.s13/

シラバス の後半の「Thu 04/11」から、アセンブリ言語とLogisimの講義でこの時のスライドとホームワークのlogisimの回路図があるので参考になりそうです。

 


Logisimで比較回路(Comparator)を学ぶ

Logisimで組み合わせ回路(Combinational Logic)の比較回路(Comparator:コンパレータ)を学んでいきます。比較回路は、単純に2つの入力を比較して、その状態を出力します。

ひと桁の二進数の入力Aを考えると0か1です。

入力A
0
1

比較するので、入力Bも考えると、これも0か1なので、入力Aと入力Bは、以下4通りの組み合わせがあります。

入力A 入力B
0 0
1 0
0 1
1 1

この表から、二進数で入力A、Bを比較すると、出力は値が同じ時、Aが小さい時、Aが大きい時の3パターンあることが分かります。AとBが両方とも0または1の時は、A-B=0と考えることもできます。

  • A=Bの時は、0=0,1=1
  • A<Bの時は、A0<B1
  • A>Bの時は、A1>B0

これで出力のパターンが3つにまとまったので真理値表にします。

入力A 入力B A<B A=B A>B
0 0 0 1 0
1 0 0 0 1
0 1 1 0 0
1 1 0 1 0

各出力の式を求める

A<Bの出力は、~AB

A=Bの出力は、~(~AB + A~B)

A>Bの出力は、A~B

つまり、A=Bは、A<BとA>Bの出力ピンをXNOR回路の入力とすればよいです。XNOR回路の求め方ですが、難しく考えるよりかは真理値表で、1001となってたらXNOR回路だ!と覚えてしまうのがよさそうです。

A=B
1
0
0
1

XNORを使わない解説が以下にあり分かりやすいです。

http://www.s-graphics.co.jp/nanoelectronics/kaitai/logicgate/4.htm

論理式、カルノー図、ベン図を学習すると、真理値表などを踏まえて回路図に落とせるようです。

いろいろな回路シミュレータ

Logisimは教育用回路シミュレータとして操作性が良く便利です。ですが順序回路の挙動が不自然なのでちょっと残念です。似たようなシミュレータをいくつか探してみました。

Atanua

昔はライセンス販売していましたが、今はライセンスも無料で、ソースコードもgithubで公開しています。7400シリーズのICなどが用意されていています。

http://sol.gfxile.net/atanua/index.html

atanuaを使ったチュートリアルなどはないようなので、入門情報やこれでCPUをを作るよりかは何か学んできてからそれをAtanuaで試すのがよさそうです。

 

Circuit Wizard

商用ですが、登録すると制限付き版が使えるのでダウンロードしてみました。以下のように回路が光るので入門によさそうですが、この制限付き版では、自分で回路を作るのは可能でしたが、シミュレートはできませんでした。また、購入金額や日本語の案内がないのも残念です。

 

ReTro

つい先ほど見つけたのですが、これもLogisimに近い感じのシミュレータのようです。公式サイトにCPUのサンプルも4つ載っているので後でやってみます。

http://robotics.ee.uwa.edu.au/retro/

 

 

flastad circuitjs

チュートリアルや入門情報がないので、他で電子回路やロジックICについて学んでから使う必要がありますが、これは電流がアニメーションして、電流や電圧も表示できるので非常に分かりやすいです。

使い始めは右クリックでコンテキストメニューを開いて、各部品を追加するので使い方に戸惑うかもしれませんがショートカットを覚え始めると途端に効率の良さが分かるようになります。

まだ触り始めなのでわかりませんが、Logisimのような回路の階層構造は作れるのかわかりません。

http://www.falstad.com/circuit/circuitjs.html

また、オープンソースです。https://github.com/sharpie7/circuitjs1

Digital

Logisimに触発されて作られた回路シミュレータDigialです。名前が一般名詞なので検索しづらいのが残念です。FlipFlop回路なども問題なく動作します。Flasted circuitjsのように、メニューから部品を選択する形式なのでlogisimで回路シミュレータをはじめたひとはとっつきづらいかもしれません。

サンプルも非常に豊富で素晴らしいのですが、チュートリアル等のドキュメントが不足していて使い方が分かりません。ユーザーがいないため簡単なチュートリアル記事などがなく、せっかくよいツールなので残念です。

https://github.com/hneemann/Digital

 


Implementing a One Address CPU in LogisimのCPU実装を調べる5 複製してみる

これまでの作業で「Implementing a One Address CPU in Logisim」のアセンブリ言語と回路図がすべてわかりました。最後に同じ回路を作ってみます。

各ソフトウェア

このドキュメントで使っている各ソフトウェアは、Charles Kannさんのサイトhttp://chuckkann.com/joomlaMain/index.php/2016-05-09-22-19-35/one-address-cpu からダウンロードできます。

自分でCPUを作ってみる

ただ教科書を読むだけでなく、実際に全部作ってみると、どこを理解していないか確認できるので、実装してみます。

CPU全体

マシン語を実行して0005+0002=0007の実行後のループ(=halt)状態

ALU

ALUは、加算、減算のみです。Overflowフラグを用意するため15bitの桁上がり(Carry Out)と16bitの桁上がりのどちらかがある場合をOverflowにします。Logisimに付属している加算器ICは、ビット数は変更できますが、Overflowフラグの出力ピンはありません。そのため15bit加算器と、1bit加算器をそれぞれ計算して、あとで繋げることで16bitの加算にしています。

なぜ15bitと1bitに分けるかですが、最上位ビットは正負のビットなので、正の数の場合は15bitで表し16bitになる場合は桁上がりです。また負の数は最上位ビットを1にして、17bitになったら桁上がりです。そのため、Overflowフラグは、15bitと16bitの桁上がりを確認する必要があります。

16bitの演算となると、ワイヤーがとても面倒なのが分かりました。

Control Unit

制御装置は、入力のInstructionで、各装置(=各IC)をOn/Offする信号を送るだけなので単純な回路です。

Sign Extend

8bitを16bitに拡張する回路図です。

 

ダウンロード

http://hajimete-program.com/logisim/one.circ

まとめ

今回、回路シミュレーターLogisimと「Implementing a One Address CPU in Logisim」でCPUを作ってみました。気付いただけでも回路図は抵抗やコンデンサーなどもないし、順序回路FlipFlop回路も動作しないし、出来たCPUは加算器と減算器しかないし、実物で動作できないし…と課題は沢山あります。

ですが、今回CPUを作成するまで多くの発見がありました。

  • 回路シミュレータは、トライアンドエラーがやりやすい
  • 初心者でも失敗を恐れずに試せる
  • 論理回路を小さく作ってみて、そこから大きくしていくプログラミングと同等な感覚が分かった
  • アセンブリ言語(仕様)を作るという事はCPUを作る事
  • よく図解されているCPUの基本構成の制御装置、ALU、レジスター、PC、メモリーなどが理解できた。
  • アセンブリ言語の分岐は、if文でありfor文である。

また、50ページ教材で、CPUの論理回路とアセンブリ言語の実装を学べたのは非常に有意義であるとともに、複雑なものを複雑なまま学習していることが多いと感じさせられました。