第9回 - 九州大学

Title
論理回路
九州大学工学部
電気情報工学科
01/29
講義内容
第１回：アナログとディジタル
第２回：論理代数と論理関数
第３回：論理関数の表現
第４回：MOSトランジスタの機能とCMOS論理と基本論理ゲート
第５回：論理式の最小化
第６回：組み合わせ論理回路の設計
第７回：組み合わせ回路と順序回路
第８回：フリップフロップとメモリ
第９回：有限状態機械
第10回：有限状態機械の状態数の最小化
第11回：一般化した次状態関数・出力関数
第12回：同期式順序回路による有限状態機械の実現
第13回：同期式順序回路の設計
02/29
講義日程
•「論理回路」と「コンピュータアーキテクチャI」はペア
科目として，学期の前後半にそれぞれ週2コマずつ実施
「論理回路」再試験
「論理回路」本試験＠教場
Title
論理回路
第９回
—有限状態機械—
九州大学工学部
電気情報工学科
04/29
順序回路の構成
論理回路
入力
x
記憶 s
出力
f (x,s)
-順序回路の出力は，その入力と内部の記憶情報に依存
-記憶情報も入力にとって変化する場合あり
05/29
記憶回路の構成
• 受動素子
-「情報」を電荷として保持
-ダイナミックラッチ
-DRAM（Dynamic Random Access Memory）
• 能動素子
-フィードバックループを利用して「情報」を保持
-スタティックラッチ
-SRAM（Static Random Access Memory）
06/29
DRAM（受動素子）の特徴
-トランジスタ1個から実装できるため，高集積化・高
速動作が可能
-電荷は時間と共に減少していくため，各メモリセル
は定期的にリフレッシュ処理（内部状態を読み出して
増幅した後に再取り込み）を行う必要がある
放電
放電
放電
-消費電力が（比較的）大きい
放電
07/29
SRAM（能動素子）の特徴
-トランジスタ6個から実装されるため，高集積化には
やや難がある
-フィードバックループを利用しているためリフレッ
シュ処理は不要
-消費電力が（比較的）小さい
-電力供給がなくなると記憶内容が失われる（揮発性
メモリ）ため，一般にキャッシュメモリとしてプロセッ
サに搭載される
08/29
マスタースレーブ型フリップフロップ
• ラッチ1とラッチ2が交互に記憶モードになり，その際
に入力-出力間が必ず遮断される
• Clockの立ち下がり時のdataがoutputとして記憶される
Clock
data
D
Q 記憶
L1 取り込み
記憶
取り込み
L2 取り込み
data 記憶
x
Clock
1 0
D
Q
取り込み
記憶
記憶記憶
取り込み
output
取り込み
0 1
output
09/29
データのセットとリセット
• Clockに依存せずに「2つの安定状態」を切り替える
• set !" F = 1 ／ reset !" F = 0
input A
input A
1
0
(set)
1
0
input B
output F
set
reset
input B
1F
0
output
(reset)
安定状態
reset
set 0
1
t0
t1
t2
t3
t4
10/29
RSフリップフロップ
• 前スライドの論理回路にド・モルガンの定理を適用
• S (set) 入力，R (reset) 入力に対して，Q と Q’ を出力
S
R
Q
Q’
11/29
【確認】RSフリップフロップの特性表
動作
S
R Qt+1 Q’t+1
0
0
Qt
Q’t
保持
0
1
0
1
リセット
1
0
1
0
セット
1
1
/
/
禁止
12/29
【確認】RSフリップフロップの動作
S
R
Qt+1
Q’t+1
13/29
順序機械
• 順序機械
-順序回路をモデル化したもので，コンピュータ（計
算機）の基本的な数学モデル
-内部状態の数が有限
-量子化された時間で動作
-ほとんどのディジタル回路は順序機械に分類される
14/29
順序機械の描像
入力
x(t)
出力関数f
状態遷移関数g
記憶
s(t)
出力
z(t)
=f(x(t), s(t))
-順序機械の内部状態はそれまでの入力系列に依存（状
態遷移関数）し，現在および将来の出力に影響を及ぼす
15/29
【例】「200円の自動販売機」の動作①
入力
なし
0円
出力
なし
-入力があるまでは内部状態も出力も変化しない
16/29
【例】「200円の自動販売機」の動作②
100円玉
0円
!
100円
出力
なし
-100円玉1個だけでは商品は出ない
-内部状態は「100円を受け取った状態」へと遷移する
17/29
【例】「200円の自動販売機」の動作③
入力
なし
100円
出力
なし
-さらに入力があるまでは内部状態も出力も変化しない
18/29
【例】「200円の自動販売機」の動作④
100円玉
100円
!
0円
商品
-さらに100円玉が投入されたときに商品を出す
-内部状態は初期状態に戻る（「200円」状態はない）
19/29
順序機械の記述
• M = (I, O, S, !, ")
-I: 入力アルファベット，入力集合
-O: 出力アルファベット，出力集合
-S: 状態集合
-!: 状態遷移関数（S!I"S）
-": ミーリ型（Mealy型）出力関数（S!I"O）
-": ムーア型（Moore型）出力関数（S"O）
20/29
「200円の自動販売機」M1とM2
• M1 = (I, O, S1, !1, "1) • M2 = (I, O, S2, !2, "2)
-I: {なし, 100円玉}
-I: {なし, 100円玉}
-O: {なし, 商品}
-O: {なし, 商品}
-S: {0円, 100円}
-S: {0円, 100円, 200円}
-!1: S1!I"S1
-!: S2!I"S2
-"1: S1!I"O
-": S2!I"O
21/29
状態遷移表
入力1
入力2
次状態, 次状態,
現状態1
出力
出力
次状態, 次状態,
現状態2
出力
出力
…
…
…
次状態, 次状態,
現状態s
出力
出力
…
…
…
入力n
次状態,
出力
次状態,
出力
…
…
…
次状態,
出力
22/29
「200円の自動販売機」の状態遷移表
0円
100円
なし
100円玉
0円,
なし
100円,
なし
100円,
なし
0円,
商品
23/29
状態遷移図
入力, 出力
s2
s1
入力, 出力
s3
sn
-状態を節点とし，各入力に対応する出力を枝とする
24/29
「200円の自動販売機」の状態遷移図
なし, なし
100円玉, なし
0円
なし, なし
100円
100円玉, 商品
なし, なし
なし, なし
100円玉, なし
0円
100円
なし, 商品
100円玉, なし
200円
25/29
【確認】「200円の自動販売機２」
論理回路
入力
x
記憶 s
出力
f (x,s)
-100円玉だけでなく50円玉も入力できる場合の「200
円の自動販売機」の動作？
26/29
「200円の自動販売機２」の状態遷移表
なし
0円
50円
100円
150円
0円,
なし
50円,
なし
100円,
なし
150円,
なし
50円玉
100円玉
50円,
100円,
なし
なし
100円,
150円,
なし
なし
150円,
0円,
なし
商品
0円,
0円,
商品商品+50円
27/29
「200円の自動販売機２」の状態遷移図
なし, なし
100円玉, 商品+50円玉 150円
50円玉, 商品
なし,
なし
50円玉, なし
0円
100円
50円玉, なし
100円玉, なし
100円玉, なし
なし,
なし
50円玉, なし
50円
100円玉, 商品
なし, なし
28/29
次回予定
論理回路
第９回
—有限状態機械の状態数の最小化—
九州大学工学部
電気情報工学科
29/29

Download Report