/var/log/messages

Apr 5, 2015 - 4 minute read - Comments - programming

加算器の実装など (nand to tetris(6))

とりあえず 02 なディレクトリに 01/*.hdl をコピィして git init したり Github に push したりしておいて実装着手。

要件見てみるに sum は Xor の出力、carry は And の出力で良いのかな。

以下なカンジの実装をでっち上げて、

CHIP HalfAdder {
    IN a, b;    // 1-bit inputs
    OUT sum,    // Right bit of a + b 
        carry;  // Left bit of a + b

    PARTS:
    Xor(a=a, b=b, out=sum);
    And(a=a, b=b, out=carry);
}

テストにはパスしています。次は全加算器ですが半加算器二つで良いのかな。carry は or に食わせちゃって良いのかな。

そして次はオーバーフロー無視な Add16 というソレを、とのこと。そうか全加算器って carry 加えないといけないので入力が三つなんスね。

その次は Inc16 というソレ。Add16 の片方の引数が 1 で良いのかな。これってどう書けば良いのかと。1 の指定の方法がかなりズルかったのですが気付かなんだッスorz

ALU

なんだかここでいきなりハードルが上がる感じがします。とりあえず戻すナニはレジスタ (?) に格納しておくとして入力なフラグをどう取り扱って条件分岐すれば良いのか、がカギなのかな。

よくよく見てみるに、zx、nx、zy、ny なフラグは入力な x あるいは y の状態を変えるかどうかを指示するフラグになっていますね。あるいは f は x および y でどのような演算をするのかを指示するフラグになっていて out は出力にどんなフィルタかけるかを指示しているのか。

演算子としては

  • And16
  • Add16
  • Not16

が使えますね。あるいは場合分けとして

  • z が 0、n が 0 なら入力値はそのまま使う
  • z が 1、n が 0 なら入力値は 0 に
  • z が 0、n が 1 なら入力値は Not 演算なフィルタかける
  • z が 1、n が 1 なら入力値は -1 になるのか

これって 4way なマルチプレクサが使えるの?

あるいは

  • 0 にするには Not したソレと And すれば良い?
  • -1 は 0 の Not
  • 0 は false って理解で良いのかな
  • true は -1 でした
  • ちなみに 0 番目の要素に true 代入で 1 になる模様

これを順に適用すれば良い?

あとは出力なフラグを何とかしないと、なのか。ここはスルーで上のソレを実装してみます。実装なポイントとしてはゲートに渡す引数、あるいは逆に出力される引数を

sel[0]=nx, sel[1]=zx,

みたく分けたり

out[0..7]=low

みたく分割取得できたりできるあたりがアレです。ちょっと考えることができる手順を以下に控えておきます。

  • x および y の Not 取得
  • sel[0] を n、sel[1] を z で指定して Mux4Way16 を呼び出して x および y の初期値の準備
  • x+y および x&y の演算結果取得
  • それぞれの Not 取得
  • sel[0] を f、sel[1] を no で指定して Mux4Way16 呼び出して戻り値取得

これで戻さなければならない値は取得できているはず。あとはフラグをどうするか、なのか。これって分割取得できる仕組みを使って

  • Or8Way 使うと上、下のビットが全部 0 かを確認できる?
  • 全部ゼロだったらフラグを、ってどうやるんだろ
  • 最上位ビットを検査すれば符号が分かる

あ、Or8Way 使って最後に Not すれば良いのかorz

実装してみます

微妙な試行錯誤のうちに試験にパス。微妙ながらも commit 作ってみます (リセットして差分を消したナニがあるのでバックアップ作成用途orz)。

マルチビットバージョン (nand to tetris(5)) nand2tetris5 [programming]

16 ビット並列なゲートも作れとのこと。繰り返しって使えるのかな、と思い for とか使ってみましたが、どうも実装されていないようで .hdl が読みこめませんでした。仕方が無いのでコピペでアレしましたが、これはなかなかに辛みのあるナニですな (何

とりあえずここまでの時点で作ってる部品は使って良いとのことなのでそのまんま使ってしまい multi-bit なソレは実装できました。

また、この HDL では変数の使いまわしはできないみたいなので Or8Way もちょっと工夫が必要らしい。

Mux4Way

これ、どうすりゃ良いのかな。以下なコメントがあるのですが

* out = a if sel == 00
        b if sel == 01
        c if sel == 10
        d if sel == 11

末端ビットからグループ絞って云々、なのか。これはムズい。これを応用すれば Mux8Way も手間ではありますができますね。

Multi-Way/Multi-Bit Demultiplexor

今度は出力先を、なのか。DMux 二度呼び出せば 4 つのうち 2 つは選択できますね。あとは sel[1] の値が 0 なら a か b で 1 なら c か d なのか。。。DMux みたいに一つづつ And 取れば良いのかな。