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

講義日程-2007年度冬学期

計算システム論第一 †

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

次の授業は 2008/1/15から。二回休講

↑

内容 †

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)$ について、

と展開できる。繰り返して展開すると、論理変数からいくつか取り出して
積を作った2^n個の項の排他的論理和として表現できる。
この展開をリード・マラー展開やガロア標準形と呼ぶ。

キューブ表現
トランジスタの配置パターンそのままで表現。
各項に論理変数とその否定に対応するビットを用意して、
項にその変数が現れるならビットを立てる。

BDD(Binary Decision Diagram)
- 論理式の真偽値表をツリー表現。標準化して冗長性を除く。
  標準化されたグラフは、評価する順番を固定すると一意に定まる。
  ほとんどの論理式はグラフ表現にして簡約すれば簡単な形になる。

論理関数の否定
- 多くの論理変数を含む論理式をドモルガン律を使って否定しようとすると、項数がとても多くなる。
- 論理関数 $F(x,y,z)$ の否定は、
  $F = xF(1,y,z) + \bar{x}F(0,y,z)$
  $\bar{F} = x\bar{F(1,y,z)} + \bar{x}\bar{F(0,y,z)}$

ユネイト関数
各変数が、肯定形か否定形かのどちらかしか現れない積和形式で表される論理関数。
- $F(x,y,z)$ が $x$ について正であるとは、
  $F(0,y,z) \leq F(1,y,z)$ 、「左辺が真で右辺が偽」とはならない論理関数。
  $x$ に関して正な関数については、 $F(1,y,z) = F(1,y,z) + F(0,y,z)$ が成立。
  $F(x,y,z) = xF(1,y,z) + F(0,y,z)$ と分解できる。
- xについて負な関数についても同様。
- すべての変数に関して(正/負)な関数は単調(増大/減少)関数。エラー検出について有用。

自己双対関数
- $F(x,y,z)$ について、 $F^*(x,y,z) = \bar{F(\bar{x},\bar{y},\bar{z})}$ を $F$ の双対関数と呼ぶ。
- $F^* = F$ となる関数は自己双対関数。
- $\{G(F_1,F_2,F_3)\}^* = G^*(F_1^*,F_2^*,F_3^*)$
- 任意の関数 $F$ について、変数 $w$ を一つ追加した $G = wF + \bar{w}F^*$ は自己双対。

対称関数
任意の変数同士を置換しても変化しない関数。
- 任意の対称関数は基本対称関数の線形結合で表される。
  n変数での対称関数は $2^{n+1}$ 種類、
  ３変数では
  - $\bar{x}\bar{y}\bar{z}$
    $x\bar{y}\bar{z}+\bar{x}y\bar{z} + \bar{x}\bar{y}z$
    $\bar{x}yz+x\bar{y}z + xy\bar{z}$
    $xyz$
    の四種類。

ブール代数方程式
- $F(x,a,b,c,\cdots)=1$ の解 $x$ は？
  ブール展開して、 $xF(1,a,b,c,\cdots) + \bar{x}F(0,a,b,c,\cdots) = xF_1 + \bar{x}F_0 = 1$
  $F_1 = F_0 = 0$ のとき、解なし。
  $F_1 = 0 \wedge F_0 = 1$ のとき、 $x=0$
  $F_1 = 1 \wedge F_0 = 0$ のとき、 $x=1$
  $F_1 = 1 \wedge F_0 = 1$ のとき、 $x$ は任意。
  解の存在条件は、 $F_1 + F_0 = 1$ と書ける。
- 『任意』を $J$ で表すと、解 $x = X(F_1,F_0)$ は、
  $X(0,0) = \bot$
  $X(1,0) = 1$
  $X(0,1) = 0$
  $X(1,1) = J$
  $x = \bar{F_1}\bar{F_0}X(0,0) + F_1 \bar{F_0}X(1,0) + \bar{F_1}F_0 X(0,1) + F_1 F_0 X(1,1)$
  $x = \bar{F_1}\bar{F_0}\bot + F_1 \bar{F_0} + F_1 F_0 J$ であり、
  解が存在するなら、 $x = F_1 \bar{F_0} + F_1 F_0 J = \bar{F_0} + F_1 F_0 J$ と書ける。

論理合成
- 真理値表がベース。まず標準形で書いてから最適化する。
- Karnaugh図を用いる。
  真理値表を並び替え、Hamming距離が１になる値が隣り合うようにすると、
  積和標準形での各項が図の上で近くに固まり、項を視覚的に表現できる。 $f = xy + \bar{x}z + yz = xy + \bar{x}z$
  - Hamming距離：異なるビットの数を距離と見たもの。

Quine-Mcluskeyの方法
- 積和形論理式の主項を生成する。
  主項とは、項に積として含まれる部分のうち、
  どれを落としても全体の論理式を満たせないもの。
  カルノー図上では、それ以上広げられない塊。
  最も単純な表現の論理式は、主項だけからなる。
  最も大きな主項が含まれるとは限らない。
- 最小項を全て列挙し、各ハミング距離1の組について、
  その項がまとめられるかどうかをチェックし、まとめられる組は全て生成する。
  まとめることができた項を除き、再び各ハミング距離1の組について同じようにまとめる。
  これをまとめるべき項がなくなるまで繰り返せば、主項を全て得られる。
- 主項からいくつかを選んで、最小項全てを覆うようにすれば、
  それが最も項の少ない積和形論理式の表現になっている。

３段NAND形式
- 否定の入った積和形式はNAND素子三段で実装できる。
  否定回路には、本来２入力のNAND素子に定入力を与えてしまっている。
  最初からNANDのみを使って回路を作れば、段数を稼ぐことができる。

２線論理
- １線式の通常の論理回路では、論理変化を追うことはできない。
  出力が計算結果なのか遅延の影響なのかがわからない。
  値とその否定をペアにして、２線を同時に扱うと、
  クロックを使わずに回路をつくれ、回路は単調増加回路になる。
  配線の量は倍になるが、否定は線の入れ替えだけで作れるので、
  素子の数は倍にはならない。

順序回路
内部状態を持った回路。順序回路。有限状態機会。
入力X，出力Zの他に内部状態Qをもっていて、遷移関数で特徴づけられる。
Mealyモデル： $\delta:X \times Q \to Q, \omega: X \times Q \to Z$
Mooreモデル： $\delta:X \times Q \to Q, \omega: Q \to Z$ 出力が状態のみに依存。出力は遷移後。
二つの状態が、任意の入力に対して同じ出力を返し同じ状態に移動するなら、同じ状態。
- 順序回路は状態遷移図・状態遷移表で表現される。
- 順序回路の実装には、出力用の組み合わせ回路，状態遷移用の組み合わせ回路，記憶素子を使う。

記憶素子
- 記憶素子はフリップフロップの構造を持つ回路の集まり。
  内部状態を持つ回路には初期化の機能が必須。
- T型フリップフロップ
  JKフリップフロップのJとKをつないで同じ値にしたものと等価。
  入力の立ち上がりと立ち下がりを検出し、立ち下がりの時に出力を反転させる。
  $Q' = T \oplus Q$
- D型フリップフロップ
  入力を１クロック文遅延させて出力する。
  $Q'=D$
- SR型
  S(Set)とR(Reset)の２入力フリップフロップ。
  $S=1$ なら $Q'=1$ に、 $R=1$ なら $Q'=0$ にする。
  $Q' = S\bar{R} + \bar{S}\bar{R}Q$ $S=1$ かつ $R=1$ は禁止入力。
- JKFF
  最も多用される順序回路。
  JとKの２入力フリップフロップ。SR型とT型を合わせた特性。
  $J=1$ なら $Q'=1$ に、 $K=1$ なら $Q'=0$ にする。
  ただし $J=1$ かつ $K=1$ ならばトグル。
  $Q' = \bar{J}\bar{K}Q + J\bar{K} + JK\bar{Q}$
- マスタ・スレーブ型ラッチ
  クロックの変化を待たずに出力が入力に戻ってしまうのを防ぐために、記憶素子を２重にする。
- 順序回路の難しさ。
  ゲート遅延や配線遅延のため、過渡的に内部状態が乱れ、
  それを記憶素子が記憶してしまい、回路が誤動作を起こすことがある。
  信号の遅延には素子の配置や配線が影響してくるので回路図だけからは予測が難しい。

３進カウンタ
累積で３回１が入力されたら1回だけ１を出力して初期状態にもどる回路。
- 状態遷移
  状態は３種類。
  $\delta\ q\ 0= q$
  $\delta\ q_0\ 1\ =\ q_1$
  $\delta\ q_1\ 1\ =\ q_2$
  $\delta\ q_2\ 1\ =\ q_0$
  $\omega\ q_2\ 1\ =\ 1$
  $\omega\ _\ _\ =\ 0$
  内部状態は2bit変数 $y_0,y_1$ 、状態割り当ては、
  $q_0 = 00$ $q_1 = 01$ $q_2 = 10$ とすると、
  $y'_0 = x\bar{y_1}\bar{y_0}+\bar{x}y_0$
  $y'_1 = \bar{x}y_1+xy_0$

順序回路の等価性
完全定義な順序回路について、
長さsの入力で区別できない二つの状態はs次等価であるという。
任意の長さの入力で区別できない二つの状態は等価であるという。
s次等価な状態で、全状態を分割したときに、
同じ分割に属する $i,j$ にもう一つ入力を与えてやったときに
別々な分割に遷移しないなら、 $i,j$ はs+1次等価。
- まずは出力で区別できるかを調べて１次分割。

Boothの乗算アルゴリズム
- 乗数中に1が続くときに、引き算を使って1の数を減らし、
  乗算時に使う加算の回数を減らす。
  - 乗数を下位ビットから順に見て行き、現在見ているビットが
    一つ前のビットと同じならば何もしない。
    1になったら結果から被乗数を引く、0になったら結果に被乗数を足す。
    結果を1ビット左にシフト。
```
multiply(A,B){
  P = 0;
  b = 0;
  repeat(N){
    case(A[0],b){
      (01)-> P += B;
      (10)-> P -= B;
    }
    (P,A,b) >>= 1;
  }
  return (P,A);
}
```

Presented by yambi. tzik all blame reserved.
誤植は見つけた人が直してね

1 任意の $n$ 変数論理関数 $F(x_1, x_2, \dots, x_n)$ とその双対関数 $F_d(x_1, x_2, \dots, x_n)$ を用いて得られる $n+1$ 変数論理回路
$G(x_0, x_1, x_2, \dots, x_n)=x_0\cdot F(x_1, x_2, \dots, x_n)+\bar{x_0}\cdot F_d(x_1, x_2, \dots, x_n)$
は自己双対であることを証明せよ．

解

$G(0, x_1, x_2, \dots, x_n)=F_d(x_1,x_2,\dots,x_n)$

$G(1, x_1, x_2, \dots, x_n)=F(x_1,x_2,\dots,x_n)$
なので明らかに自明であることは明白より明らか．

2 次のように定義される関数 $F(w,x,y,z)$ のもっとも簡単な積和論理式を全て示せ．

yz $\backslash$ wx	00	01	11	10
00	1	1	0	0
01	1	1	0	1
11	1	1	1	1
10	0	0	1	1

解
カルノー図を眺め，感より
$F(w,x,y,z)=\bar{w}\cdot\bar{y}+z\cdot\bar{x}+w\cdot y+y\cdot z$

$F(w,x,y,z)=\bar{w}\cdot\bar{y}+z\cdot\bar{x}+w\cdot y+\bar{w}\cdot z$
の2つだろうと思いたい．

3 1を3回続けて入力したときのみ1を出力する1入力1出力同期式順回路をDFFを用いて設計する過程を示せ．その結果をAND, OR, NOT及びDFFを基本素子とする最も簡単な論理回路図で示せ．ただし，入力信号を $X$ ，出力信号を $Z$ とする．

解
3回続けて入力したかどうかを判定することは2つの状態ではできないことは明らか．

状態遷移表はstateを $S_0, S_1, S_2$ とし隣接行列で書くと（動作/イベント）

現段階 $\backslash$ 次段階	$S_1$	$S_2$	$S_3$
$S_1$	0/0	0/1	-
$S_2$	0/0	-	0/1
$S_3$	0/0	-	1/1

と書ける．

状態数が2ビットで表現できることより，DFFを2つ(A,Bとする)用いて表現できる．

よって，内部状態を $Q_A, Q_B$ とし，状態 $S_1$ を $(0,0)$ $S_2$ を $(0,1)$ $S_3$ を $(1,1)$ とし，状態遷移表を書き直すと（イベント/次の状態）

$Q(t)$		$Q(t+1)$
$Q_A$	$Q_B$	X=0	X=1
0	0	0/00	0/01
0	1	0/00	0/11
1	1	0/00	1/11
1	0	-	-

以上より同期式順序回路は DFF Aの入力を $Q_B$ ， DFF Bの入力を $X$ ，出力 $Z$ を $Q_A\cdot Q_B\cdot X$ としたものである．

4 8ビットレジスタを用いた符合付き「2の補数」表示の2進加算に関して以下の問いに答えよ．

(1) 一つのレジスタに収容できる整数の範囲を10進数で示せ.
- 解 $-128\sim 127$ ．
  一般に $n$ ビットレジスタを用いれば $2^{n-1}\sim (2^{n-1}-1)$ までの整数を収容できる．
(2) 演算「89-76」はどのように実行されるかを説明せよ．
- 解
  89は2進数表示で $01011001_{(2)}$ ， 76は2進数表示で $01001100_{(2)}$ なので， $01011001_{(2)}+11001100_{(2)}$ を計算すれば良い．オーバーフローは無視をする．

(3) 一般に，結果にオーバーフローが生じるのはどのような場合かを符号ビットへのキャリー（C7）と符号ビットからのキャリー（C8）に関連して説明せよ．

解

$C_7$	$C_8$	状況
0	0	正と正または正と負（または負と正）の足し算でオーバーフローが生じないとき．
0	1	正と正の足し算でオーバーフローが生じたとき．
1	0	負と負の足し算でオーバーフローが生じたとき．
1	1	負と負または正と負の足し算でオーバーフローが生じないとき

なので，オーバーフロー判定は

$\bar{C_8}\cdot C_7+C_8\cdot\bar{C_7}=C_7\oplus C_8$

と書ける．

5 以下の各演算について，その方法と特徴を簡潔に説明せよ．
- (1) キャリールックアヘッド加算
  - 解
    通常の加算器（リップルアダー）では $n$ ビットの足し算を行うために $O(n)$ 段の計算が必要であるが，キャリーを先読みするようにすれば段数を減らすことができる．
    段数は定数オーダまで減らすことができるが必要な素子数が指数的に増えてしまう．
    
    $c(k+1)=G(j+1,k)+P(i,k)c(i)$
    として，
    $G(i,k)=G(j+1,k)+P(j+1,k)G(i,j)$
    
    $P(i,k)=P(i,j)G(j+1,k)$
    
    $G(i,i)=g_i=a_i\cdot b_i,\ \ P(i,i)=p_i=a_i+b_i$
    とすれば $\log n$ ，素子数は $n\log n$ で構成できバランスが良い．

(2) 不動浮動小数点演算
- 解
  ググれ
  
  冗談です．
  小数を仮数部（ $m$ ），指数部（ $e$ ）を用いて表現して演算を行う．この小数は $r$ を基数とし $m\times r^e$ を表す．
  wikipediaはこちら

(3) Boothの乗算アルゴリズム
- 解
  2の補数表現の符号付整数乗算の手法の一つ．
  連続する２ビットに着目しその4通りのパターンに従って操作を行うもの．
  これを拡張し，同時に $k$ ビットを同時にみることにすれば $n$ ビットの掛け算に $O(n-k)$ の計算しか必要なくなると思うが，この文章は疑わしい．

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