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

講義日程-2007年度冬学期

計算システム論

論理関数
- $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.2)

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