こんばんは。きなこ屋です。
シャカシャカで足し算を実装した覚書を残します。
完成図
自分は電子回路について全くの初心者ですので、加算器についての正確な情報はWikipediaをご参照いただくとして、まずは完成形を紹介します。簡単に言えば、シャカシャカの問題を解くだけで2進数の計算ができるという機構です。なお実用性は皆無です。
問題を最後まで解くと、紫部分が1100(01100)になる。
この図は「3+9=12」を表しています。2進法で言うところの「0011+1001=1100」です。上部にある8個の2×2正方形(赤・青)が入力、下部にある5個の2×2正方形(紫)が出力になっています。三角形が入る場合(◇)は1、入らない場合(□)は0を表すというわけです。
より正確には、入力マスのすぐ上にある0や1が直接の入力を司っています。pzprRTでリアルタイムソルバーを有効にして、これらの数字を変更してみると、それに従って出力も変化するのが観察できるでしょう。
繰り返し構造をさらに増やせば、解答能力の許す限り、何桁でも足し算ができることになります。また、意図した構造ではありませんが、上部の入力を片方だけにして、下部に0や1を入れて逆の入力とすることで、引き算も一応できます(答が0~15でない場合はパズルとして解なしになります)。
動機
きっかけはこの問題です。[リンク]
小さいながら先読みだか仮置きだかが必要な問題です。この形自体はかなり前からヒント数字の効率を上げるアイデアとして持っていました。
さてこの問題、数字がない状態でちょうど4個の解を持ちます。
図を見れば、左上2マス目に1を入れることで唯一解になることが分かります。そして、他に数字1つでこの問題を唯一解にする方法は、同じマスに0を入れるか、右下に0を入れるしかないと分かります。
では、盤面を少し広げて、外部からヒントを与える場合はどうでしょうか。
図5を見てみると、上と左下の2箇所(図6の0の位置)を決めてやれば、どの場合でも唯一解になることが見て取れます。言い換えれば、上と左下の2箇所のヒントが4つの解にそれぞれ対応しているわけです。これは真理値表ではありませんか！
例えば、図7のように正方形と1を配置してみると、2箇所のヒントが両方とも0である場合のみ、下の正方形に三角形が入ることになります。あたかもスイッチを操作するかのようです。
2×2の正方形は、三角形が入るか入らないかの2択になりますから、これをON/OFFに対応させることができます。ということで、ヒント側も2×2の正方形に置き換えてみましょう。
図9では、上と左が両方ともONの場合のみ、下もONになることが分かります。これはAND回路に他なりません。
かくして、シャカシャカ電子回路プロジェクト(？)は誕生したのでした。
設計
図5のような形(以下ゲートと呼称)を回路に組み込むには条件があります。ゲートがn個の入力を受ける場合、ゲートは外部からの情報がない状態でちょうど2ⁿ個の解を持つ必要があります(一部例外を除く)。
解が2ⁿより少ない場合、ある入力に対しては解が存在しないことになり、回路が壊れます(そのような入力を受けないと分かっている場合を除く)。解が2ⁿより多い場合、ある入力に対して複数の解が存在することになり、唯一解になりません。
従って、解が2個や4個であるような形を探して、それが上手く目的の入出力を行ってくれるように調整する必要があります。現状1~2入力のゲートは考えうる全種類が再現できました。まだ試行錯誤は済んでいませんが、発見できたゲートを下に挙げます。
ケーブル
単純に2×2正方形どうしを1で繋いだ場合、ON/OFFが反転します。これが素朴なNOTゲートになります。NOTを2回繋げば自明なゲートができます。
※以下の図では、赤が入力A、青が入力B、紫が出力としています。
ON/OFFをそのまま伝達する方法は他にもあります。マス数に応じて使い分けます。
3番目：同時に橙部分に¬Aを作れて分岐しやすい。
4番目：4マス先に送る場合。形がシンプル。
ANDとOR(1)
先程の図4は、実はANDと同時にORゲートも兼ねることができます。2つを同時に取り出したいときもコンパクトに纏まりますね。
反転させればNANDとNORも作ることができます。
ANDとOR(2)
この形は、一度に最大3つの異なる出力を生みます。ただ位置を考えると効率よく使える状況は限られそうです。
S₂=B→Aなので、反転を組み合わせれば、2入力のほとんどのゲートを作ることができます。残るXORはこの次で。
S₁=A∧¬B
S₂=A∨¬B=B→A
ケーブルの交差
ゲートに繋ぐために信号を交差させたい？そんな時はこれ！
整流器とXOR
ON/OFFで信号を表す性質上、値域が0,1,2である信号を処理することは困難です。ですが、図の右下の整流器を付けることにより、信号をON/OFFに還元することができます。最後のXORゲートもここで再現できました。ぶっちゃけこれが万能です。
S₁=A nand B (0を取り出す)
S₂=A nor B (2を取り出す)
加算器の実現
というわけで、これらを組み合わせることで足し算機構である加算器を再現することができます。
半加算器を2つ繋げた形。
まとめ
論理回路に知識のある人なら、足し算より面白いことが出来そうです。
これよりサイズの小さい加算器を再現していただける方、面白いアイデアを形にしていただける方を心待ちにしています。
