NandGame が面白過ぎて年末年始ハマった その２

NandGame、最高では？

前回、NandGame は面白くてハマるから是非やってみて欲しいという話と、ハマった結果として Arithmetics カテゴリまでの成果を披露した。
と言うわけで、さっそく続きの成果を披露していこうと思う。
なお、相変らずバリバリネタバレ全開なので、まさかいないとは思うが万一まだゲームをやっていない方は是非コンプリートしてから読んで欲しい。

2021/01/18 追記

白山風露さん に Data Flip-Flop の最適解を教えて頂いたおかげで、Nand 数を大幅に減らすことができた！

Plumbing

Plumbing って何だ？と思ったら配管とかそういう意味だそうだ。なるほど。

Selector

セレクタである。どちらかの入力を選ぶ、と言うことだ。
入力 s が 0 の場合は d0 を出力、1 の場合は d1 を出力する。
と言うことでまずは愚直に作る。

当然 Nand 使い過ぎで怒られる。
と言うことで、Or と And を分解すればこうなる。

オーケー、4 Nand で正解だ。

Switch

スイッチである。セレクタとは逆にどちらかに出力する、と言うことだ。
これも愚直に作る。

5 Nand、このままで良いようだ。実際、これ以上減らせる気はしない。

2022/09/23 追記

FromNandさんから頂いたコメントの通り、まだ Nand を減らす余地があった。簡単な回路だからと言って油断していた。痛恨の極みである。
そしてサイト側でもこれに気付いていたようで、今までの解では Optimal じゃないという表示になっていた。
と言う訳で、これが真の正解である。

ところで久々にサイトを開いたらいろいろ変わっていた。再度精査せねばなるまい。

Memory

メモリである。記憶が出来ないとコンピュータにならない。私のような鳥頭では困るのだ。

Latch

ラッチである。そういえばラッチってどういう意味だ？と思って調べたところ、掛け金らしい。
入力 st が 0 の時の入力 d を保持して出力する。いわゆる D ラッチだ。
$\overline{\rm RS}$ ラッチの入力を st と d からひねり出せば良いので、まずは愚直に構成する。

これでも Nand 使い過ぎらしい。
で、よくよく見てみると、右の Inv は左の Nand で代用できる事に気付いた。
というわけで、こうなった。

オーケー、ミッションコンプリートだ。

2021/01/18 追記

コメントにも書いたように、Data Flip-Flop の最適解を白山風露さん に教えて頂いたが、この内容から、Nand 数は変わらないものの以下の構成の方がシンプルであることにようやく気付いた。

この構成あっての最適な Data Flip-Flop であると考えられるので、こちらでミッションコンプリートとしたい。

Data Flip-Flop

D フリップフロップである。ここでは Data となっているが Delay の略と言われたりもする。
通常は、クロック（今回の場合は cl。普通は ck な気がするがまぁ気にしない）の切り替えタイミングでその時の入力（今回の場合は d）を覚えて出力し続ける。覚える切り替えタイミングは 0→1 の場合（ポジティブエッジトリガ）と 1→0 の場合（ネガティブエッジトリガ）があるが、この問題ではポジティブエッジトリガだ。
しかし、この問題では st 入力もあるのでちょっと動作が異なる。入力を覚えるのは st が 1 でかつ cl が 0 の時だけ、出力がその覚えた値に切り替わるのが cl が 0→1 の時、となっている。
とりあえず愚直にラッチ 2 つで構成する。いわゆるマスタスレーブフリップフロップと言うヤツである。

なるほど正しく動く。しかし 11 Nand では Nand を使い過ぎらしい。
と言うわけで、ラッチ等を分解してうんうん唸ってみたが、どうしてもこれ以上減らせない。
いや、より正確に言うと、10 Nand でチェックを通る構成は組み上げた。

しかし、見ての通りこれでも Nand は浪費していないと言ってくれていない上に、何より実は仕様を満たしていない。
例えば、今の図の状態から st を 1→0 とした後、cl を 0→1 とした場合、本来は出力が 0 にならなければならないが、この構成ではならない。
というわけで、思い出し悩みしたりはしているものの、現状ギブアップに近い状態である。
もしこれを完全に解けたら是非教えて欲しい（懇願）。
ところで全く関係ないが、マスタスレーブフリップフロップと言う名称も例の言葉狩りの影響で無くなってしまうのだろうか？

2021/01/18 追記

白山風露さん に教えて頂いた！
Latch のところにも書いたが、そもそも Latch の構成がイケてなかったのだ！
と言うわけで、修正した Latch の構成を使って Latch 2 つの構成を分解する。

こうして見ると、確かに Nand を節約する余地があることが分かる。cl に繋がっている Inv が重複しているところと、And の先に Inv が繋がっているところの 2 箇所だ。

ブラボー！これで 9 Nand だ！ありがとう！白山風露さん！

Register

レジスタである。店にあるレジではなく CPU にあるアレである。
今回は 2 ビットと言う事で、Data Flip-Flop 2 個で構成可能である。

オーケー、正解だ。
だが先程の Data Flip-Flop を思い出して欲しい。一段目のラッチ（マスタスレーブのマスタ）の st には And と Inv が使われていたが、これは保持するビットとは全く無関係である。
つまり、こいつらがレジスタのビット数分あるのは明らかにムダであろう。実データ保持部分と制御部分を分けることで、Nand を節約することができる。Nand を大切に！
と言うわけで、まずはデータ保持部分だけの自作部品を作成する。名前を考えるのがめんどくさいので DFF だ。

そして、コイツを使ってレジスタを組み上げる。

オーケー、正しく動いている。19 Nand だ。
ちなみに、部品数が多過ぎると言われているが、ここでは気にしないことにする。
どうせ全部を自作部品に詰め込んでしまえば 1 部品にすることはたやすいのだ。Nand 命！

2021/01/18 追記

上記の通り、Data Flip-Flop は大幅に構成が変更となった。これを元に Register も再構成しよう。
And に当たる部分と Inv を外部に出すのは変わらないが、構成上どうしても入力端子を増やさねばならない。

st と cl に対する Inv も入力に追加した。本当はアッパーバーを端子名に使いたいのだがよく分からなかったので、sti と cli と言う入力にした。
そしてこれを使って Register を再構成する。

絵面が微妙なのはどうか許してほしい。私の美的センスではこれが限界だ。
だが結果は十分満足できるものだ。15 Nand にまで減らすことができた。
白山風露さんには感謝しても感謝しきれない。

Counter

16 ビットのカウンタである。この問題では任意のタイミングで値設定も可能なものである。
そしてツールボックスには 16 ビットレジスタや 16 ビットセレクタ等が生えてきている。
と言うわけで、これらを使って簡単に構成できる。

オーケー、292 Nand で正解だ。
しかし、先程のレジスタでは通常の正解よりも 2 ビットで 3 Nand 節約することができた。つまり通常に構成されたレジスタでは Nand を浪費しているのではないだろうか？
と言うか、そもそもこの 292 Nand の内訳はどうなっているのだろうか？調べてみよう。なに、調べ方は簡単だ。正解した図面で調べたい部品をムダに追加すれば Nand 数が出るので差分を見れば良い。

部品	Nand 数
register	152 Nand
inc 16	75 Nand
select 16	64 Nand
Inv	1 Nand

ん？何だこの 152 Nand と言うのは。ビット数の 16 で割ると 9.5 だ、テンゴって何だよテンゴって。と思ったが、なるほど、先程の 2 ビットレジスタが 19 Nand だったので × 8 で 152 Nand か。惜しい、実に惜しい。残念だが、ここは黙々と 16 ビットレジスタを構成する事としよう。
が、ちょっと待った。今回の 16 ビットレジスタは st 入力がプルアップされている。つまり st 入力なんて要らなかったのだ。st 入力が無い Data Flip-Flop ならもっと少ない Nand で構成出来るハズだ。
ではまず st 入力のない Data Flip-Flop を構成しよう。名前はまたしても DFF だ。先程の物よりも入力が少ないので判別可能だろう。

6 Nand で出来た！配置もなかなか綺麗に出来た！（どうでもいい）
そして、コイツを使って 16 ビットレジスタを構成する。名前は register 16 だ。

完全に読む気は起きないが、まぁ正しく動いていそうだ。
最後に、これを元の回路に組み込む。

よし、235 Nand まで減らすことが出来た！
が、ここで諦めてはいけない。諦めたらそこで試合終了ですよ…？安西先生…… Nand が減らしたいです……
実は、まだ手付かずの部品がある。今回生えてきた 16 ビットセレクタだ。
先程の調査で 16 ビットセレクタは 64 Nand だと言う事が分かっている。分かりやすい、4 Nand × 16 ビットだ。
が、上のセレクタの図を見返してみれば分かる通り、コイツにも制御に関する Nand が一つだけある。そう、s に接続されている Inv だ。
つまり、この Inv も外に出す事で、16 ビット分を集約することができるはずだ。やっていこう。
まず、Inv を外したセレクタを構成する。

最早セレクタとは？と言う感じだが気にしない。
これを使って 16 ビットセレクタをいつも通り気合で構成する。

見ろ！配線がゴミのようだ！！
最後に、これを元の回路に組み込む。

よし、正常に動いている、220 Nand だ。最初の状態からは 72 減らすことができた！

RAM

2 ワード分のラムだっちゃ。まぁレジスタを 2 つ使えばよい。

358 Nand で正解だ。だが勝負はここからだ。
残念ながら、先程構成した register 16 は使えない。st 入力が無いからだ。しかし、制御を除いた Data Flip-Flop は構成済みだ。黙々と st 入力のある register 16 も構築しよう。

いつも通り全く読めない。いや、心眼で見れば何とかなる。心頭滅却すれば火もまた涼しだ。
これを使っていこう。

レジスタの制御を外部に出してしまったので若干見づらいが、315 Nand で正常に動作した。
いや、まだだ！まだ終わらんよ！
スイッチの中身とレジスタの st 入力用制御回路は再構成できる。

正常動作、313 Nand である。
そしてここで致命的な誤りをしてしまっていた事に気付いた。
お分かりだろうか。そう、セレクタである。
あろうことか select 16 に s に対する Inv を組み込んでしまっているのだ。これは本来外部に出しておくべきだった。
たかだか 1 Nand だと侮ることなかれ。たかが 1 Nand、されど 1 Nand。1 Nand を笑うものは 1 Nand に泣く。
と言うわけで、select 16 を修正する事にする。

相変わらず曼荼羅のようだが正しく動くようだ。一応戻ってカウンタも直しておく。

最後にこれを再度組み込む。

正解、これで 312 Nand、ゲームセットだ。

2021/01/18

制御を除いた Data Flip-Flop の入力端子が変わってしまったため、register 16 も再構成しなければならない。

オーケーオーケー、言いたい事はわかる。だが、そんなあなたにブルース・リーのこの言葉を贈ろう。"Don't think! Feel."
最後にこれを組み込んで行こう。

今度こそ正解に違いない。これで 248 Nand、正解だと思っていた上記から 64 Nand も減らすことができた！
白山風露さん恐るべし！

まだまだ道半ば…

ようやく Memory まで終わったが、まだまだ半分程度である。
が、今回も既にだいぶ長くなってしまったし、皆さんに是非聞きたかった Data Flip-Flop を書く事が出来たので、ここまでにしようと思う。
もし精神力が続けば、さらに続きを書きたいと思う。
なお、もしこれらよりも少ない Nand で解けたら是非教えて欲しい。
最後に、万一ここまでゲーム自体をせずに読んでしまった方は、今からでも遅くないので是非やってみて欲しい（前回含めて 6 回目）。