計算システム論第一
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
] [
リンク元
]
開始行:
[[講義日程-2007年度冬学期]]
** 計算システム論第一 [#a68fcc7d]
- 担当：南谷 崇 教授
- 1.5単位
-- 数理：限定選択C
-- システム：限定選択A
- 14:45-16:15 工学部六号館 62講義室
- 出席あり(救済措置的)
- 参考書
-- 新世紀デジタル講座
-- 論理設計--スイッチング回路理論
-- コンピュータの構成と設計
-- [[Huntingtonの公理>http://www.tzik.mydns.jp:80/yambi/f...
-次の授業は 2008/1/15から。二回休講
**内容 [#ba4102ab]
- VLSI計算システム概論
-- ハードウェアの経年劣化と同様に、ソフトウェアも経年劣化...
信頼性を保つためには常にメンテナンスが必要。~
これを怠るとインターフェイスに齟齬が生じ、あちこちに不具...
-- 以下、いろいろ要約すると「電力消費・情報転送量多すぎ。...
- 論理回路
-- 計算機の素子は基本的にはAND,OR,NOTでできている。(実際...
- ブール代数と論理回路
-- 順序集合~
反射律、対称律、推移律を満たす二項関係を伴う集合。~
最大元があればそれを1、最小元があればそれを0とする。その...
-- 束の公理~
冪等で可換、結合的な二項演算で、吸収律を満たすものを伴う...
さらに分配律を満たす束を分配束と呼ぶ。
-- ブール代数の公理~
最大元と最小元を持った分配束に、二重否定除去、相補性とド...
--- 双対性原理~
ブール代数の式について、項を全て否定し、＋を・に、・を＋...
ブール代数では、任意の等式とその双対等式について、片方が...
- 論理関数
-- &mimetex(2 = \{0,1\});~
&mimetex(n);変数論理関数、&mimetex(f:2^n\to2); ブール関数...
表現形式としては、論理式・真理値表・キューブ表現・BDDがあ...
定義域の&mimetex(2^n);全てについて値が定義されているもの...
値が未定義の組み合わせがあり、「渡してはいけない値」があ...
-- 論理式の表現には真理値表が最も簡単。~
ROMの入力値に対応する論理値を書き込んで~
真理値表を作れば、簡単に論理回路を作れる。~
ただし、入力変数が増えると表の行数が急激に増える。
-- 論理式による表現。~
論理関数は必ず論理式で書けるか？Yes.~
--- ブール展開~
&mimetex(F(x,y,z) = x F(1,y,z)+\bar{x} F(0,y,z)); と展開...
同様に展開を進めると、引数の積と否定からなる項の和からな...
ある項を真にする論理変数の組み合わせが唯一であるとき、そ...
全ての論理変数の積を取ったものと、そのうちいくつかの論理...
極小項の和で書かれた論理式は、真理値表と一対一対応。積和...
積和表現の双対として、極小項の双対である極大項の積で表現...
積和表現は、もとの論理関数を否定したものを積和表現で表し...
--- リード・マラー展開~
排他的論理和&mimetex(\oplus);(XOR,exclusive or,対称差)を~
&mimetex(x \oplus y = x\bar{y} + \bar{x}y);で定義する。~
&mimetex(x \oplus y = y \oplus x);~
&mimetex(x \oplus (y \oplus z) = (x \oplus y) \oplus z);~~
&mimetex(x (y \oplus z) = xy \oplus xz);~
&mimetex(x \oplus 0 = x);~
&mimetex(x \oplus 1 = \bar{x});~
&mimetex(x \oplus x = 0);~
&mimetex(x + y = x \oplus y \oplus xy); が成立。~
２変数論理関数&mimetex(F(x,y));について、~
と展開できる。繰り返して展開すると、論理変数からいくつか...
積を作った2^n個の項の排他的論理和として表現できる。~
この展開をリード・マラー展開やガロア標準形と呼ぶ。
--- キューブ表現~
トランジスタの配置パターンそのままで表現。~
各項に論理変数とその否定に対応するビットを用意して、~
項にその変数が現れるならビットを立てる。
- BDD(Binary Decision Diagram)
-- 論理式の真偽値表をツリー表現。標準化して冗長性を除く。~
標準化されたグラフは、評価する順番を固定すると一意に定ま...
ほとんどの論理式はグラフ表現にして簡約すれば簡単な形にな...
- 論理関数の否定
-- 多くの論理変数を含む論理式をドモルガン律を使って否定し...
-- 論理関数&mimetex(F(x,y,z));の否定は、~
&mimetex(F = xF(1,y,z) + \bar{x}F(0,y,z));~
&mimetex(\bar{F} = x\bar{F(1,y,z)} + \bar{x}\bar{F(0,y,z)...
- ユネイト関数~
各変数が、肯定形か否定形かのどちらかしか現れない積和形式...
-- &mimetex(F(x,y,z));が&mimetex(x);について正であるとは、~
&mimetex(F(0,y,z) \leq F(1,y,z));、「左辺が真で右辺が偽」...
&mimetex(x);に関して正な関数については、&mimetex(F(1,y,z)...
&mimetex(F(x,y,z) = xF(1,y,z) + F(0,y,z));と分解できる。
-- xについて負な関数についても同様。
-- すべての変数に関して(正/負)な関数は単調(増大/減少)関数...
- 自己双対関数
-- &mimetex(F(x,y,z));について、&mimetex(F^*(x,y,z) = \ba...
-- &mimetex(F^* = F);となる関数は自己双対関数。
-- &mimetex(\{G(F_1,F_2,F_3)\}^* = G^*(F_1^*,F_2^*,F_3^*));
-- 任意の関数&mimetex(F);について、変数&mimetex(w);を一つ...
- 対称関数~
任意の変数同士を置換しても変化しない関数。
-- 任意の対称関数は基本対称関数の線形結合で表される。~
n変数での対称関数は&mimetex(2^{n+1});種類、~
３変数では
--- &mimetex(\bar{x}\bar{y}\bar{z});~
&mimetex(x\bar{y}\bar{z}+\bar{x}y\bar{z} + \bar{x}\bar{y}...
&mimetex(\bar{x}yz+x\bar{y}z + xy\bar{z});~
&mimetex(xyz);~
の四種類。
- ブール代数方程式
-- &mimetex(F(x,a,b,c,\cdots)=1);の解&mimetex(x);は？~
ブール展開して、&mimetex(xF(1,a,b,c,\cdots) + \bar{x}F(0,...
&mimetex(F_1 = F_0 = 0);のとき、解なし。~
&mimetex(F_1 = 0 \wedge F_0 = 1);のとき、&mimetex(x=0);~
&mimetex(F_1 = 1 \wedge F_0 = 0);のとき、&mimetex(x=1);~
&mimetex(F_1 = 1 \wedge F_0 = 1);のとき、&mimetex(x);は任...
解の存在条件は、&mimetex(F_1 + F_0 = 1);と書ける。
-- 『任意』を&mimetex(J);で表すと、解&mimetex(x = X(F_1,F...
&mimetex(X(0,0) = \bot);~
&mimetex(X(1,0) = 1);~
&mimetex(X(0,1) = 0);~
&mimetex(X(1,1) = J);~
&mimetex(x = \bar{F_1}\bar{F_0}X(0,0) + F_1 \bar{F_0}X(1,...
&mimetex(x = \bar{F_1}\bar{F_0}\bot + F_1 \bar{F_0} + F_1...
解が存在するなら、&mimetex(x = F_1 \bar{F_0} + F_1 F_0 J ...
- 論理合成
-- 真理値表がベース。まず標準形で書いてから最適化する。
-- [[Karnaugh図>http://ja.wikipedia.org/wiki/%E3%82%AB%E3...
真理値表を並び替え、Hamming距離が１になる値が隣り合うよう...
積和標準形での各項が図の上で近くに固まり、項を視覚的に表...
&mimetex(f = xy + \bar{x}z + yz = xy + \bar{x}z);~
--- Hamming距離：異なるビットの数を距離と見たもの。
- Quine-Mcluskeyの方法
-- 積和形論理式の主項を生成する。~
主項とは、項に積として含まれる部分のうち、~
どれを落としても全体の論理式を満たせないもの。~
カルノー図上では、それ以上広げられない塊。~
最も単純な表現の論理式は、主項だけからなる。~
最も大きな主項が含まれるとは限らない。
-- 最小項を全て列挙し、各ハミング距離1の組について、~
その項がまとめられるかどうかをチェックし、まとめられる組...
まとめることができた項を除き、再び各ハミング距離1の組につ...
これをまとめるべき項がなくなるまで繰り返せば、主項を全て...
-- 主項からいくつかを選んで、最小項全てを覆うようにすれば...
それが最も項の少ない積和形論理式の表現になっている。
- ３段NAND形式
-- 否定の入った積和形式はNAND素子三段で実装できる。~
否定回路には、本来２入力のNAND素子に定入力を与えてしまっ...
最初からNANDのみを使って回路を作れば、段数を稼ぐことがで...
//-- &mimetex(a\bar{t_1}\bar{t_2} + a(\bar{at_3}\bar{t_4}...
//&mimetex(a\bar{b} = a\bar{ab});
- ２線論理
-- １線式の通常の論理回路では、論理変化を追うことはできな...
出力が計算結果なのか遅延の影響なのかがわからない。~
値とその否定をペアにして、２線を同時に扱うと、~
クロックを使わずに回路をつくれ、回路は単調増加回路になる。~
配線の量は倍になるが、否定は線の入れ替えだけで作れるので、~
素子の数は倍にはならない。
- 順序回路~
内部状態を持った回路。順序回路。有限状態機会。~
入力X，出力Zの他に内部状態Qをもっていて、遷移関数で特徴づ...
Mealyモデル：&mimetex(\delta:X \times Q \to Q, \omega: X ...
Mooreモデル：&mimetex(\delta:X \times Q \to Q, \omega: Q ...
二つの状態が、任意の入力に対して同じ出力を返し同じ状態に...
-- 順序回路は状態遷移図・状態遷移表で表現される。
-- 順序回路の実装には、出力用の組み合わせ回路，状態遷移用...
- 記憶素子
-- 記憶素子は[[フリップフロップ>http://ja.wikipedia.org/w...
内部状態を持つ回路には初期化の機能が必須。
-- T型フリップフロップ~
JKフリップフロップのJとKをつないで同じ値にしたものと等価。~
入力の立ち上がりと立ち下がりを検出し、立ち下がりの時に出...
&mimetex(Q' = T \oplus Q);
-- D型フリップフロップ~
入力を１クロック文遅延させて出力する。~
&mimetex(Q'=D);
-- SR型~
S(Set)とR(Reset)の２入力フリップフロップ。~
&mimetex(S=1);なら&mimetex(Q'=1);に、&mimetex(R=1);なら&m...
&mimetex(Q' = S\bar{R} + \bar{S}\bar{R}Q);
&mimetex(S=1);かつ&mimetex(R=1);は禁止入力。
-- JKFF~
最も多用される順序回路。~
JとKの２入力フリップフロップ。SR型とT型を合わせた特性。~
&mimetex(J=1);なら&mimetex(Q'=1);に、&mimetex(K=1);なら&m...
ただし&mimetex(J=1);かつ&mimetex(K=1);ならばトグル。~
&mimetex(Q' = \bar{J}\bar{K}Q + J\bar{K} + JK\bar{Q});
-- マスタ・スレーブ型ラッチ~
クロックの変化を待たずに出力が入力に戻ってしまうのを防ぐ...
-- 順序回路の難しさ。~
ゲート遅延や配線遅延のため、過渡的に内部状態が乱れ、~
それを記憶素子が記憶してしまい、回路が誤動作を起こすこと...
信号の遅延には素子の配置や配線が影響してくるので回路図だ...
-- ３進カウンタ~
累積で３回１が入力されたら1回だけ１を出力して初期状態にも...
--- 状態遷移~
状態は３種類。~
&mimetex(\delta\ q\ 0= q);~
&mimetex(\delta\ q_0\ 1\ =\ q_1);~
&mimetex(\delta\ q_1\ 1\ =\ q_2);~
&mimetex(\delta\ q_2\ 1\ =\ q_0);~
&mimetex(\omega\ q_2\ 1\ =\ 1);~
&mimetex(\omega\ _\ _\ =\ 0);~
内部状態は2bit変数&mimetex(y_0,y_1);、状態割り当ては、~
&mimetex(q_0 = 00);
&mimetex(q_1 = 01);
&mimetex(q_2 = 10);
とすると、~
&mimetex(y'_0 = x\bar{y_1}\bar{y_0}+\bar{x}y_0);~
&mimetex(y'_1 = \bar{x}y_1+xy_0);
-- 順序回路の等価性~
完全定義な順序回路について、~
長さsの入力で区別できない二つの状態はs次等価であるという。~
任意の長さの入力で区別できない二つの状態は等価であるとい...
s次等価な状態で、全状態を分割したときに、~
同じ分割に属する&mimetex(i,j);にもう一つ入力を与えてやっ...
別々な分割に遷移しないなら、&mimetex(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 任意の&mimetex(n);変数論理関数&mimetex(F(x_1, x_2, \do...
#mimetex(G(x_0, x_1, x_2, \dots, x_n)=x_0\cdot F(x_1, x_2...
は自己双対であることを証明せよ．
--- 解~
#mimetex(G(0, x_1, x_2, \dots, x_n)=F_d(x_1,x_2,\dots,x_n...
#mimetex(G(1, x_1, x_2, \dots, x_n)=F(x_1,x_2,\dots,x_n));
なので明らかに自明であることは明白より明らか．
-2 次のように定義される関数&mimetex(F(w,x,y,z));のもっと...
|yz&mimetex(\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|
--- 解~
カルノー図を眺め，感より
#mimetex(F(w,x,y,z)=\bar{w}\cdot\bar{y}+z\cdot\bar{x}+w\c...
#mimetex(F(w,x,y,z)=\bar{w}\cdot\bar{y}+z\cdot\bar{x}+w\c...
の2つだろうと思いたい．
-3 1を3回続けて入力したときのみ1を出力する1入力1出力同期...
その結果をAND, OR, NOT及びDFFを基本素子とする最も簡単な論...
ただし，入力信号を&mimetex(X);，出力信号を&mimetex(Z);と...
---解~
3回続けて入力したかどうかを判定することは2つの状態ではで...
状態遷移表はstateを&mimetex(S_0, S_1, S_2);とし隣接行列で...
|現段階&mimetex(\backslash);次段階|&mimetex(S_1);|&mimete...
|&mimetex(S_1);|0/0|0/1|-|
|&mimetex(S_2);|0/0|-|0/1|
|&mimetex(S_3);|0/0|-|1/1|
と書ける．
状態数が2ビットで表現できることより，DFFを2つ(A,Bとする)...
よって，内部状態を&mimetex(Q_A, Q_B);とし，
状態&mimetex(S_1);を&mimetex((0,0));
&mimetex(S_2);を&mimetex((0,1));
&mimetex(S_3);を&mimetex((1,1));
とし，状態遷移表を書き直すと（イベント/次の状態）
|>|&mimetex(Q(t));|>|&mimetex(Q(t+1));|
|&mimetex(Q_A);|&mimetex(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の入力を&mimetex(Q_B);，
DFF Bの入力を&mimetex(X);，
出力&mimetex(Z);を&mimetex(Q_A\cdot Q_B\cdot X);
としたものである．
-4 8ビットレジスタを用いた符合付き「2の補数」表示の2進加...
--(1) 一つのレジスタに収容できる整数の範囲を10進数で示せ.
---解 &mimetex(-128\sim 127);．~
一般に&mimetex(n);ビットレジスタを用いれば&mimetex(-2^{n-...
--(2) 演算「89-76」はどのように実行されるかを説明せよ．
---解~
89は2進数表示で&mimetex(01011001_{(2)});，
76は2進数表示で&mimetex(01001100_{(2)});なので，
&mimetex(01011001_{(2)}+11001100_{(2)});を計算すれば良い．
オーバーフローは無視をする．
--(3) 一般に，結果にオーバーフローが生じるのはどのような...
---解~
|&mimetex(C_7);|&mimetex(C_8);|状況|
|0|0|正と正または正と負（または負と正）の足し算でオーバー...
|0|1|正と正の足し算でオーバーフローが生じたとき．|
|1|0|負と負の足し算でオーバーフローが生じたとき．|
|1|1|負と負または正と負の足し算でオーバーフローが生じない...
なので，オーバーフロー判定は
#mimetex(\bar{C_8}\cdot C_7+C_8\cdot\bar{C_7}=C_7\oplus C...
と書ける．
-5 以下の各演算について，その方法と特徴を簡潔に説明せよ．
--(1) キャリールックアヘッド加算
---解~
通常の加算器（リップルアダー）では&mimetex(n);ビットの足...
段数は定数オーダまで減らすことができるが必要な素子数が指...
#mimetex(c(k+1)=G(j+1,k)+P(i,k)c(i));
として，
#mimetex(G(i,k)=G(j+1,k)+P(j+1,k)G(i,j));
#mimetex(P(i,k)=P(i,j)G(j+1,k));
#mimetex(G(i,i)=g_i=a_i\cdot b_i,\ \ P(i,i)=p_i=a_i+b_i);
とすれば&mimetex(\log n);，素子数は&mimetex(n\log n);で構...
--(2) %%不動%%浮動小数点演算
---解~
[[ググれ>http://www.google.co.jp/search?hl=ja&q=%E6%B5%AE...
~
冗談です．~
小数を仮数部（&mimetex(m);），指数部（&mimetex(e);）を用...
この小数は&mimetex(r);を基数とし&mimetex(m\times r^e);を...
[[wikipediaはこちら>http://en.wikipedia.org/wiki/Floating...
--(3) Boothの乗算アルゴリズム
---解~
2の補数表現の符号付整数乗算の手法の一つ．~
連続する２ビットに着目しその4通りのパターンに従って操作を...
これを拡張し，同時に&mimetex(k);ビットを同時にみることに...
-自己双対論理関数の定義
--&mimetex(F=F^*);となるような関数．すなわち(0と1)，(&mim...
-3変数自己双対関数の例．
#mimetex(f(x_1,x_2,x_3)=x_1);
#mimetex(f(x_1,x_2,x_3)=x_1x_2+x_2x_3+x_3x_1);
とか．
終了行:
[[講義日程-2007年度冬学期]]
** 計算システム論第一 [#a68fcc7d]
- 担当：南谷 崇 教授
- 1.5単位
-- 数理：限定選択C
-- システム：限定選択A
- 14:45-16:15 工学部六号館 62講義室
- 出席あり(救済措置的)
- 参考書
-- 新世紀デジタル講座
-- 論理設計--スイッチング回路理論
-- コンピュータの構成と設計
-- [[Huntingtonの公理>http://www.tzik.mydns.jp:80/yambi/f...
-次の授業は 2008/1/15から。二回休講
**内容 [#ba4102ab]
- VLSI計算システム概論
-- ハードウェアの経年劣化と同様に、ソフトウェアも経年劣化...
信頼性を保つためには常にメンテナンスが必要。~
これを怠るとインターフェイスに齟齬が生じ、あちこちに不具...
-- 以下、いろいろ要約すると「電力消費・情報転送量多すぎ。...
- 論理回路
-- 計算機の素子は基本的にはAND,OR,NOTでできている。(実際...
- ブール代数と論理回路
-- 順序集合~
反射律、対称律、推移律を満たす二項関係を伴う集合。~
最大元があればそれを1、最小元があればそれを0とする。その...
-- 束の公理~
冪等で可換、結合的な二項演算で、吸収律を満たすものを伴う...
さらに分配律を満たす束を分配束と呼ぶ。
-- ブール代数の公理~
最大元と最小元を持った分配束に、二重否定除去、相補性とド...
--- 双対性原理~
ブール代数の式について、項を全て否定し、＋を・に、・を＋...
ブール代数では、任意の等式とその双対等式について、片方が...
- 論理関数
-- &mimetex(2 = \{0,1\});~
&mimetex(n);変数論理関数、&mimetex(f:2^n\to2); ブール関数...
表現形式としては、論理式・真理値表・キューブ表現・BDDがあ...
定義域の&mimetex(2^n);全てについて値が定義されているもの...
値が未定義の組み合わせがあり、「渡してはいけない値」があ...
-- 論理式の表現には真理値表が最も簡単。~
ROMの入力値に対応する論理値を書き込んで~
真理値表を作れば、簡単に論理回路を作れる。~
ただし、入力変数が増えると表の行数が急激に増える。
-- 論理式による表現。~
論理関数は必ず論理式で書けるか？Yes.~
--- ブール展開~
&mimetex(F(x,y,z) = x F(1,y,z)+\bar{x} F(0,y,z)); と展開...
同様に展開を進めると、引数の積と否定からなる項の和からな...
ある項を真にする論理変数の組み合わせが唯一であるとき、そ...
全ての論理変数の積を取ったものと、そのうちいくつかの論理...
極小項の和で書かれた論理式は、真理値表と一対一対応。積和...
積和表現の双対として、極小項の双対である極大項の積で表現...
積和表現は、もとの論理関数を否定したものを積和表現で表し...
--- リード・マラー展開~
排他的論理和&mimetex(\oplus);(XOR,exclusive or,対称差)を~
&mimetex(x \oplus y = x\bar{y} + \bar{x}y);で定義する。~
&mimetex(x \oplus y = y \oplus x);~
&mimetex(x \oplus (y \oplus z) = (x \oplus y) \oplus z);~~
&mimetex(x (y \oplus z) = xy \oplus xz);~
&mimetex(x \oplus 0 = x);~
&mimetex(x \oplus 1 = \bar{x});~
&mimetex(x \oplus x = 0);~
&mimetex(x + y = x \oplus y \oplus xy); が成立。~
２変数論理関数&mimetex(F(x,y));について、~
と展開できる。繰り返して展開すると、論理変数からいくつか...
積を作った2^n個の項の排他的論理和として表現できる。~
この展開をリード・マラー展開やガロア標準形と呼ぶ。
--- キューブ表現~
トランジスタの配置パターンそのままで表現。~
各項に論理変数とその否定に対応するビットを用意して、~
項にその変数が現れるならビットを立てる。
- BDD(Binary Decision Diagram)
-- 論理式の真偽値表をツリー表現。標準化して冗長性を除く。~
標準化されたグラフは、評価する順番を固定すると一意に定ま...
ほとんどの論理式はグラフ表現にして簡約すれば簡単な形にな...
- 論理関数の否定
-- 多くの論理変数を含む論理式をドモルガン律を使って否定し...
-- 論理関数&mimetex(F(x,y,z));の否定は、~
&mimetex(F = xF(1,y,z) + \bar{x}F(0,y,z));~
&mimetex(\bar{F} = x\bar{F(1,y,z)} + \bar{x}\bar{F(0,y,z)...
- ユネイト関数~
各変数が、肯定形か否定形かのどちらかしか現れない積和形式...
-- &mimetex(F(x,y,z));が&mimetex(x);について正であるとは、~
&mimetex(F(0,y,z) \leq F(1,y,z));、「左辺が真で右辺が偽」...
&mimetex(x);に関して正な関数については、&mimetex(F(1,y,z)...
&mimetex(F(x,y,z) = xF(1,y,z) + F(0,y,z));と分解できる。
-- xについて負な関数についても同様。
-- すべての変数に関して(正/負)な関数は単調(増大/減少)関数...
- 自己双対関数
-- &mimetex(F(x,y,z));について、&mimetex(F^*(x,y,z) = \ba...
-- &mimetex(F^* = F);となる関数は自己双対関数。
-- &mimetex(\{G(F_1,F_2,F_3)\}^* = G^*(F_1^*,F_2^*,F_3^*));
-- 任意の関数&mimetex(F);について、変数&mimetex(w);を一つ...
- 対称関数~
任意の変数同士を置換しても変化しない関数。
-- 任意の対称関数は基本対称関数の線形結合で表される。~
n変数での対称関数は&mimetex(2^{n+1});種類、~
３変数では
--- &mimetex(\bar{x}\bar{y}\bar{z});~
&mimetex(x\bar{y}\bar{z}+\bar{x}y\bar{z} + \bar{x}\bar{y}...
&mimetex(\bar{x}yz+x\bar{y}z + xy\bar{z});~
&mimetex(xyz);~
の四種類。
- ブール代数方程式
-- &mimetex(F(x,a,b,c,\cdots)=1);の解&mimetex(x);は？~
ブール展開して、&mimetex(xF(1,a,b,c,\cdots) + \bar{x}F(0,...
&mimetex(F_1 = F_0 = 0);のとき、解なし。~
&mimetex(F_1 = 0 \wedge F_0 = 1);のとき、&mimetex(x=0);~
&mimetex(F_1 = 1 \wedge F_0 = 0);のとき、&mimetex(x=1);~
&mimetex(F_1 = 1 \wedge F_0 = 1);のとき、&mimetex(x);は任...
解の存在条件は、&mimetex(F_1 + F_0 = 1);と書ける。
-- 『任意』を&mimetex(J);で表すと、解&mimetex(x = X(F_1,F...
&mimetex(X(0,0) = \bot);~
&mimetex(X(1,0) = 1);~
&mimetex(X(0,1) = 0);~
&mimetex(X(1,1) = J);~
&mimetex(x = \bar{F_1}\bar{F_0}X(0,0) + F_1 \bar{F_0}X(1,...
&mimetex(x = \bar{F_1}\bar{F_0}\bot + F_1 \bar{F_0} + F_1...
解が存在するなら、&mimetex(x = F_1 \bar{F_0} + F_1 F_0 J ...
- 論理合成
-- 真理値表がベース。まず標準形で書いてから最適化する。
-- [[Karnaugh図>http://ja.wikipedia.org/wiki/%E3%82%AB%E3...
真理値表を並び替え、Hamming距離が１になる値が隣り合うよう...
積和標準形での各項が図の上で近くに固まり、項を視覚的に表...
&mimetex(f = xy + \bar{x}z + yz = xy + \bar{x}z);~
--- Hamming距離：異なるビットの数を距離と見たもの。
- Quine-Mcluskeyの方法
-- 積和形論理式の主項を生成する。~
主項とは、項に積として含まれる部分のうち、~
どれを落としても全体の論理式を満たせないもの。~
カルノー図上では、それ以上広げられない塊。~
最も単純な表現の論理式は、主項だけからなる。~
最も大きな主項が含まれるとは限らない。
-- 最小項を全て列挙し、各ハミング距離1の組について、~
その項がまとめられるかどうかをチェックし、まとめられる組...
まとめることができた項を除き、再び各ハミング距離1の組につ...
これをまとめるべき項がなくなるまで繰り返せば、主項を全て...
-- 主項からいくつかを選んで、最小項全てを覆うようにすれば...
それが最も項の少ない積和形論理式の表現になっている。
- ３段NAND形式
-- 否定の入った積和形式はNAND素子三段で実装できる。~
否定回路には、本来２入力のNAND素子に定入力を与えてしまっ...
最初からNANDのみを使って回路を作れば、段数を稼ぐことがで...
//-- &mimetex(a\bar{t_1}\bar{t_2} + a(\bar{at_3}\bar{t_4}...
//&mimetex(a\bar{b} = a\bar{ab});
- ２線論理
-- １線式の通常の論理回路では、論理変化を追うことはできな...
出力が計算結果なのか遅延の影響なのかがわからない。~
値とその否定をペアにして、２線を同時に扱うと、~
クロックを使わずに回路をつくれ、回路は単調増加回路になる。~
配線の量は倍になるが、否定は線の入れ替えだけで作れるので、~
素子の数は倍にはならない。
- 順序回路~
内部状態を持った回路。順序回路。有限状態機会。~
入力X，出力Zの他に内部状態Qをもっていて、遷移関数で特徴づ...
Mealyモデル：&mimetex(\delta:X \times Q \to Q, \omega: X ...
Mooreモデル：&mimetex(\delta:X \times Q \to Q, \omega: Q ...
二つの状態が、任意の入力に対して同じ出力を返し同じ状態に...
-- 順序回路は状態遷移図・状態遷移表で表現される。
-- 順序回路の実装には、出力用の組み合わせ回路，状態遷移用...
- 記憶素子
-- 記憶素子は[[フリップフロップ>http://ja.wikipedia.org/w...
内部状態を持つ回路には初期化の機能が必須。
-- T型フリップフロップ~
JKフリップフロップのJとKをつないで同じ値にしたものと等価。~
入力の立ち上がりと立ち下がりを検出し、立ち下がりの時に出...
&mimetex(Q' = T \oplus Q);
-- D型フリップフロップ~
入力を１クロック文遅延させて出力する。~
&mimetex(Q'=D);
-- SR型~
S(Set)とR(Reset)の２入力フリップフロップ。~
&mimetex(S=1);なら&mimetex(Q'=1);に、&mimetex(R=1);なら&m...
&mimetex(Q' = S\bar{R} + \bar{S}\bar{R}Q);
&mimetex(S=1);かつ&mimetex(R=1);は禁止入力。
-- JKFF~
最も多用される順序回路。~
JとKの２入力フリップフロップ。SR型とT型を合わせた特性。~
&mimetex(J=1);なら&mimetex(Q'=1);に、&mimetex(K=1);なら&m...
ただし&mimetex(J=1);かつ&mimetex(K=1);ならばトグル。~
&mimetex(Q' = \bar{J}\bar{K}Q + J\bar{K} + JK\bar{Q});
-- マスタ・スレーブ型ラッチ~
クロックの変化を待たずに出力が入力に戻ってしまうのを防ぐ...
-- 順序回路の難しさ。~
ゲート遅延や配線遅延のため、過渡的に内部状態が乱れ、~
それを記憶素子が記憶してしまい、回路が誤動作を起こすこと...
信号の遅延には素子の配置や配線が影響してくるので回路図だ...
-- ３進カウンタ~
累積で３回１が入力されたら1回だけ１を出力して初期状態にも...
--- 状態遷移~
状態は３種類。~
&mimetex(\delta\ q\ 0= q);~
&mimetex(\delta\ q_0\ 1\ =\ q_1);~
&mimetex(\delta\ q_1\ 1\ =\ q_2);~
&mimetex(\delta\ q_2\ 1\ =\ q_0);~
&mimetex(\omega\ q_2\ 1\ =\ 1);~
&mimetex(\omega\ _\ _\ =\ 0);~
内部状態は2bit変数&mimetex(y_0,y_1);、状態割り当ては、~
&mimetex(q_0 = 00);
&mimetex(q_1 = 01);
&mimetex(q_2 = 10);
とすると、~
&mimetex(y'_0 = x\bar{y_1}\bar{y_0}+\bar{x}y_0);~
&mimetex(y'_1 = \bar{x}y_1+xy_0);
-- 順序回路の等価性~
完全定義な順序回路について、~
長さsの入力で区別できない二つの状態はs次等価であるという。~
任意の長さの入力で区別できない二つの状態は等価であるとい...
s次等価な状態で、全状態を分割したときに、~
同じ分割に属する&mimetex(i,j);にもう一つ入力を与えてやっ...
別々な分割に遷移しないなら、&mimetex(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 任意の&mimetex(n);変数論理関数&mimetex(F(x_1, x_2, \do...
#mimetex(G(x_0, x_1, x_2, \dots, x_n)=x_0\cdot F(x_1, x_2...
は自己双対であることを証明せよ．
--- 解~
#mimetex(G(0, x_1, x_2, \dots, x_n)=F_d(x_1,x_2,\dots,x_n...
#mimetex(G(1, x_1, x_2, \dots, x_n)=F(x_1,x_2,\dots,x_n));
なので明らかに自明であることは明白より明らか．
-2 次のように定義される関数&mimetex(F(w,x,y,z));のもっと...
|yz&mimetex(\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|
--- 解~
カルノー図を眺め，感より
#mimetex(F(w,x,y,z)=\bar{w}\cdot\bar{y}+z\cdot\bar{x}+w\c...
#mimetex(F(w,x,y,z)=\bar{w}\cdot\bar{y}+z\cdot\bar{x}+w\c...
の2つだろうと思いたい．
-3 1を3回続けて入力したときのみ1を出力する1入力1出力同期...
その結果をAND, OR, NOT及びDFFを基本素子とする最も簡単な論...
ただし，入力信号を&mimetex(X);，出力信号を&mimetex(Z);と...
---解~
3回続けて入力したかどうかを判定することは2つの状態ではで...
状態遷移表はstateを&mimetex(S_0, S_1, S_2);とし隣接行列で...
|現段階&mimetex(\backslash);次段階|&mimetex(S_1);|&mimete...
|&mimetex(S_1);|0/0|0/1|-|
|&mimetex(S_2);|0/0|-|0/1|
|&mimetex(S_3);|0/0|-|1/1|
と書ける．
状態数が2ビットで表現できることより，DFFを2つ(A,Bとする)...
よって，内部状態を&mimetex(Q_A, Q_B);とし，
状態&mimetex(S_1);を&mimetex((0,0));
&mimetex(S_2);を&mimetex((0,1));
&mimetex(S_3);を&mimetex((1,1));
とし，状態遷移表を書き直すと（イベント/次の状態）
|>|&mimetex(Q(t));|>|&mimetex(Q(t+1));|
|&mimetex(Q_A);|&mimetex(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の入力を&mimetex(Q_B);，
DFF Bの入力を&mimetex(X);，
出力&mimetex(Z);を&mimetex(Q_A\cdot Q_B\cdot X);
としたものである．
-4 8ビットレジスタを用いた符合付き「2の補数」表示の2進加...
--(1) 一つのレジスタに収容できる整数の範囲を10進数で示せ.
---解 &mimetex(-128\sim 127);．~
一般に&mimetex(n);ビットレジスタを用いれば&mimetex(-2^{n-...
--(2) 演算「89-76」はどのように実行されるかを説明せよ．
---解~
89は2進数表示で&mimetex(01011001_{(2)});，
76は2進数表示で&mimetex(01001100_{(2)});なので，
&mimetex(01011001_{(2)}+11001100_{(2)});を計算すれば良い．
オーバーフローは無視をする．
--(3) 一般に，結果にオーバーフローが生じるのはどのような...
---解~
|&mimetex(C_7);|&mimetex(C_8);|状況|
|0|0|正と正または正と負（または負と正）の足し算でオーバー...
|0|1|正と正の足し算でオーバーフローが生じたとき．|
|1|0|負と負の足し算でオーバーフローが生じたとき．|
|1|1|負と負または正と負の足し算でオーバーフローが生じない...
なので，オーバーフロー判定は
#mimetex(\bar{C_8}\cdot C_7+C_8\cdot\bar{C_7}=C_7\oplus C...
と書ける．
-5 以下の各演算について，その方法と特徴を簡潔に説明せよ．
--(1) キャリールックアヘッド加算
---解~
通常の加算器（リップルアダー）では&mimetex(n);ビットの足...
段数は定数オーダまで減らすことができるが必要な素子数が指...
#mimetex(c(k+1)=G(j+1,k)+P(i,k)c(i));
として，
#mimetex(G(i,k)=G(j+1,k)+P(j+1,k)G(i,j));
#mimetex(P(i,k)=P(i,j)G(j+1,k));
#mimetex(G(i,i)=g_i=a_i\cdot b_i,\ \ P(i,i)=p_i=a_i+b_i);
とすれば&mimetex(\log n);，素子数は&mimetex(n\log n);で構...
--(2) %%不動%%浮動小数点演算
---解~
[[ググれ>http://www.google.co.jp/search?hl=ja&q=%E6%B5%AE...
~
冗談です．~
小数を仮数部（&mimetex(m);），指数部（&mimetex(e);）を用...
この小数は&mimetex(r);を基数とし&mimetex(m\times r^e);を...
[[wikipediaはこちら>http://en.wikipedia.org/wiki/Floating...
--(3) Boothの乗算アルゴリズム
---解~
2の補数表現の符号付整数乗算の手法の一つ．~
連続する２ビットに着目しその4通りのパターンに従って操作を...
これを拡張し，同時に&mimetex(k);ビットを同時にみることに...
-自己双対論理関数の定義
--&mimetex(F=F^*);となるような関数．すなわち(0と1)，(&mim...
-3変数自己双対関数の例．
#mimetex(f(x_1,x_2,x_3)=x_1);
#mimetex(f(x_1,x_2,x_3)=x_1x_2+x_2x_3+x_3x_1);
とか．
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
