計算システム論第一のバックアップ(No.3)

講義日程-2007年度冬学期

計算システム論第一
- 担当：南谷崇教授
- 1.5単位
  - 数理：限定選択C
  - システム：限定選択A
- 14:45-16:15 工学部六号館 62講義室
- 出席あり(救済措置的)
- 参考書
  - 新世紀デジタル講座
  - 論理設計--スイッチング回路理論
  - コンピュータの構成と設計

VLSI計算システム概論
- ハードウェアの経年劣化と同様に、ソフトウェアも経年劣化する。~~信頼性を保つためには常にメンテナンスが必要。~~これを怠るとインターフェイスに齟齬が生じ、あちこちに不具合が現れる。

以下、いろいろ要約すると「電力消費・情報転送量多すぎ。無駄な情報流さず、もっと節約せい。」

論理回路
- 計算機の素子は基本的にはAND,OR,NOTでできている。(実際にはNANDだけで他を構成している)

ブール代数と論理回路
- 順序集合~~反射律、対称律、推移律を満たす二項関係を伴う集合。~~最大元があればそれを1、最小元があればそれを0とする。その集合を
- 束の公理~~冪等で可換、結合的な二項演算で、吸収律を満たすものを伴う集合。~~さらに分配律を満たす束を分配束と呼ぶ。
- ブール代数の公理~~最大元と最小元を持った分配束に、二十否定除去、相補性とドモルガン律を満たす単項演算を入れたもの。
  - 双対性原理~~ブール代数の式について、項を全て否定し、＋を・に、・を＋に置き換えた式を双対な論理式と呼ぶ。~~ブール代数では、任意の等式とその双対等式について、片方が成り立てばもう片方も成り立つ。

論理関数
- $2 = {0,1}$
  $n$ 変数論理関数、 $f:2^n\to2$ ブール関数・スイッチング関数とも呼ばれる。
  表現形式としては、論理式・真理値表・キューブ表現・BDDがある。
  定義域の $2^n$ 全てについて値が定義されているものを、完全定義関数。
  値が未定義の組み合わせがあり、「渡してはいけない値」があるものを、不完全定義関数と呼ぶ。
- 論理式の表現には真理値表が最も簡単。
  ROMの入力値に対応する論理値を書き込んで
  真理値表を作れば、簡単に論理回路を作れる。
  ただし、入力変数が増えると表の行数が急激に増える。
- 論理式による表現。
  論理関数は必ず論理式で書けるか？Yes.
  - ブール展開
    $F(x,y,z) = x F(1,y,z)+\bar{x} F(0,y,z)$ と展開すれば、２変数論理関数２つに分解できる。
    同様に展開を進めると、引数の積と否定からなる項の和からなる形の論理式として、この論理関数を表現できる。
    ある項を真にする論理変数の組み合わせが唯一であるとき、その項は極小項と呼ばれる。
    全ての論理変数の積を取ったものと、そのうちいくつかの論理変数を否定したものが極小項。
    極小項の和で書かれた論理式は、真理値表と一対一対応。積和表現。
    積和表現の双対として、極小項の双対である極大項の積で表現した和積表現も真理値表と一対一。
    積和表現は、もとの論理関数を否定したものを積和表現で表して、ド・モルガン則で元に戻せば得られる。
  - リード・マラー展開
    排他的論理和 $\oplus$ (XOR,exclusive or,対称差)を
    $x \oplus y = x\bar{y} + \bar{x}y$ で定義する。
    $x \oplus y = y \oplus x$
    $x \oplus (y \oplus z) = (x \oplus y) \oplus z$ ~
    $x (y \oplus z) = xy \oplus xz$
    $x \oplus 0 = x$
    $x \oplus 1 = \bar{x}$
    $x \oplus x = 0$
    $x + y = x \oplus y \oplus xy$ が成立。
    ２変数論理関数 $F(x,y)$ について、
    $F(x,y) = x \{F(1,y)\oplus F(0,y)\}F(0,y)$
    と展開できる。繰り返して展開すると、論理変数からいくつか取り出して
    積を作った2^n個の項の排他的論理和として表現できる。
    この展開をリード・マラー展開やガロア標準形と呼ぶ。
  - キューブ表現
    トランジスタの配置パターンそのままで表現。
    各項に論理変数とその否定に対応するビットを用意して、
    項にその変数が現れるならビットを立てる。

計算システム論第一 のバックアップ(No.3)

計算システム論第一のバックアップ(No.3)