"コンピュータシステムの理論と実装 1章ブール論理" を読んだ

「コンピュータシステムの理論と実装」を読んだメモを書いていきます。

コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方

メモ

ブール代数

• ブール値
  • 0/1, false/trueなどのラベルで扱われる値
  • バイナリ値, 2値などとも呼ばれる
• ブール関数
  • ブール値を入力として受け取り出力としてブール値を返す関数
  • ブール関数は正準表現で表すことができる
  • 正準表現は、真理値表の出力が1になっている各行で入力されたリテラルを全てANDで結合して作られた項をORで結合したもの
  • 全てのブール関数はAND, OR, NOTで書くことができる
  • NAND（NOR）を使うことでAND, OR, NOTを作ることができる
  • つまりNANDを使うことですべてのブール関数を作ることができる

論理ゲート

• 論理ゲート
  • ブール関数を実装した物理デバイス
  • n個の入力からm個の出力を行う
  • トランジスタから構成された単純なゲートを組み合わせてより複雑なゲート（複合ゲート）を作る
  • ゲートは回路やチップとしてパッケージングされている
  • 論理ゲートは抽象化されているため具体的な実装技術について気にせずに設計できる
• 論理設計
  • 論理ゲートの構成を組み立てること
  • なるべく少ないゲートを使ってゲートの仕様を満たすよう設計する

ハードウェアの構築

• HDL(Hardware Description Language)を用いてハードウェアシミュレーター上に回路を構築する
• 構築した回路に対して、正確性やコスト、処理速度などを定量化して、回路を評価する
• NANDゲートから以下を作成する
  • 基本論理ゲート
    • NOT(in: in, out: out)
    • AND(in:a,b, out:out)
    • OR(in:a,b, out:out)
    • XOR(in:a,b, out:out)
    • MUX(in:a,b,sel, out:out)
      • データビットと呼ばれる2つの入力のうちどちらかを、選択ビット(sel)と呼ばれる入力に応じて出力する
    • DMUX(in:in,sel, out:a,b)
      • ひとつの入力を選択ビット(sel)の値に応じて二つの出力のうちどちらかに出力する
  • 多ビット基本論理ゲート
    • NOT16
    • AND16
    • OR16
    • MUX16
  • 多入力ゲート
    • OR8way
  • 多入力多ビットゲート
    • MUX4way16
    • MUX8way16
    • DMUX4way
    • DMUX16way

実装

ハードウェアシミュレータはSoftware | nand2tetrisからダウンロードしてくる。

Not, And, Or, Xor, Mux, DMux, Not16, And16, Or16, Mux16, Or8Way, Mux4Way16, Mux8Way16, DMux4Way, DMux8Wayを実装する。

実際は以下 github.com

感想

• 論理ゲートを設計したのが大学の講義ぶりだったのでかなり懐かしい気持ちになった
• 大学の頃はなぜ論理ゲートを設計する知識が必要なのかよくわからなかったが、今あらためて設計してみるとレジスタやメモリやALUといったコンピュータの構成要素の仕組みを理解するのに大事だと思う
• 多ビット、多入力/多出力のMUX/DMUXをより少ない回路で設計するのは頭の体操になった

次章はこちら

iikanji.hatenablog.jp