論理回路基礎

論理回路基礎
8. 順序回路の簡単化，機能的な順序回路
五島正裕
論理回路基礎
前回の復習
論理回路基礎
順序回路の例
 Q
 自動販売機

使える硬貨は100円のみ

200円の商品1種のみ
– 100円が 2個投入されると，商品を送り出す
 その順序機械：

入力 x：100円が投入されると，1サイクルの間だけ 1

出力 z：1 のとき，商品が送り出される
論理回路基礎
順序回路の例
x
0
1
0
1
0
0
0
1
1
0
z
0
0
0
1
0
0
0
0
1
0
time
clock
x
z
論理回路基礎
順序回路の例
time
x 0 1 0 1 0 0 0 1 1 0
z 0 0 0 1 0 0 0 0 1 0
0/0
1/0
S(t +1), z(t)
S(t)
A
x=0
x=1
A
A, 0
B, 0
B
B, 0
A, 1
B
1/1
0/0
x/z
状態遷移図
(state diagram)
状態遷移表
(state transition table)
論理回路基礎
順序回路の例
D Q
clock
 状態
 AとB

（たとえば）D-FF 1個で
 状態割り当て
 A:Q=0
 B:Q=1
論理回路基礎
順序回路の例
S(t+1), z
S(t)
x=0
x=1
A
A, 0
B, 0
B
B, 0
A, 1
状態遷移表
A:Q=0
B:Q=1
D
z
Q
Q
x=0
x=1
0
0
1
1
1
0
x=0
x=1
0
0
0
1
0
1
次状態関数
(next state function)
の真理値表
出力関数
(output function)
の真理値表
D = Q’x + Qx’
z = Qx
論理回路基礎
順序回路の例
x
D Q
z
clock
x
Q
z
time
論理回路基礎
順序回路の例その2
 Q
 自動販売機

使える硬貨は100円のみ

200円の商品1種のみ
– 100円が 2個投入されると，次のサイクルに商品を送り出す
 その順序機械：

入力 x：100円が投入されると，1サイクルの間だけ 1

出力 z：1 のとき，商品が送り出される
論理回路基礎
順序回路の例その2
x
D Q
D Q
clock
x
Q
z
z
time
論理回路基礎
Mealy 機械と Moore 機械
D Q
x
x
z
clk
D Q
D Q
clk
Mealy 機械
Moore 機械
z
論理回路基礎
Mealy 機械と Moore 機械
出力関数
入力
現状態
出力
入力
次状態関数
Q D
出力関数
次状態
現状態
次状態関数
Q D
clk
Mealy 機械
出力
次状態
clk
Moore 機械
論理回路基礎
順序回路の簡単化
論理回路基礎
順序回路の簡単化
 状態の削除
 不要な状態の削除
 重複した状態の削除
 状態割り当ての「最適」化
論理回路基礎
不要な状態の削除
a
x
ad
bd
D Q
D Q
aq
bq
z
初期状態
clk
b
0/0
A
00
0/1
B
01
1/0
1/0
0/0
C
10
1/1
0/1
1/1
D
11
論理回路基礎
不要な状態の削除
S(t)
S(t+1), z(t)
x=0
x=1
A:00
A:00, 0
C:10, 0
B:01
A:00, 1
C:10, 1
C:10
C:10, 0
B:01, 0
x : don’t care
aqbq
ad
x=0
x=1
aqbq
bd
x=0
x=1
aqbq
z
x=0
x=1
00
1
00
00
01
1
01
01
1
1
x
11
x
11
x
x
1
10
11
x
10
1
ad = aq’x + aqx’
x
10
bd = aqx
z = bq
論理回路基礎
不要な状態の削除
a
x
ad
bd
D Q
D Q
aq
bq
z
clock
b
ad = aq’x + aqx’
bd = aq x
z = bq
論理回路基礎
重複した状態の削除
D Q
x
D Q
z
clock
a
x
D Q
b
D Q
z
clock
論理回路基礎
次状態と出力
重複した状態の削除
が同じ状態は，
同じ状態
S(t+1), z(t)
S(t+1), z(t)
S(t) : a b
x=0
x=1
S(t) : a b
x=0
x=1
A : 00
A : 00, 0
C : 10, 0
A : 00
A : 00, 0
B : 10, 0
B : 01
B : 01, 0
D : 11, 0
B : 01
B : 01, 0
D : 11, 0
C : 10
B : 01, 0
D : 11, 0
D : 11
A : 00, 1
B : 10, 1
D : 11
A : 00, 1
C : 10, 1
a
x
D Q
b
D Q
z
clock
論理回路基礎
次状態と出力
重複した状態の削除
が同じ状態は，
同じ状態
S(t+1), z(t)
0/0
S(t+1), z(t)
S(t) : a b
x=0
x=1
S(t) : a b
x=0
x=1
A : 00
A : 00, 0
C : 10, 0
A : 00
A : 00, 0
B : 10, 0
B : 01
B : 01, 0
D : 11, 0
B : 01
B : 01, 0
D : 11, 0
C : 10
B : 01, 0
D : 11, 0
D : 11
A : 00, 1
B : 10, 1
D : 11
A : 00, 1
C : 10, 1
A
00
1/0
C
10
B
01
0/0
0/1
1/0
1/1
1/0
D
11
0/0
0/0
A
00
1/0
B
01
1/1
0/0
1/0
0/1
D
11
論理回路基礎
状態割り当ての「最適」化
 状態割り当て
 A:00, B:01, C:10, D:11
 A:00, B:01, C:11, D:10
 ...
 n 個の状態を k 個のFFで表すとき，異なる割り当て
 (2k − 1)! / (2k − n)! k! 通り

n = 3, k = 2
⇒ 3 通り

n = 5, k = 3
⇒ 140 通り

n = 10, k = 4
⇒ 27億+ 通り
 効率のよいアルゴリズムは知られていない！
 仕様どおり，素直に設計したほうがよい（？）
論理回路基礎
機能的な順序回路
論理回路基礎
機能的な組み合わせ回路
 これまでの内容
 すべての組み合わせ回路：論理関数（完全集合）
 論理回路の簡単化 ⇒ 最小の積和形（和積型）回路
 しかし，実際は…
 大規模で複雑な回路に対しては困難：

その論理関数を求める

それを簡単化する
論理回路基礎
機能的な組み合わせ回路
 階層化設計 (hierarchical design)
 ex) ソフトウェアのサブルーチン
 機能的な組み合わせ回路
 比較的単純
 頻繁に使われる
論理回路基礎
機能的な組み合わせ回路の例
 非演算回路
 セレクタ
 デコーダ
 エンコーダ
 演算回路
 ALU
 シフタ
 浮動小数点演算器
論理回路基礎
機能的な順序回路
 これまでの内容
 すべての順序回路：状態遷移
 順序回路の簡単化 ⇒ 状態遷移の簡単化
 しかし，実際は…
 大規模で複雑な回路に対しては困難：

その状態，遷移を求める

それを簡単化する
論理回路基礎
機能的な組み合わせ回路
 階層化設計 (hierarchical design)
 ex) ソフトウェアのサブルーチン
 機能的な順序回路
 比較的単純
 頻繁に使われる
論理回路基礎
機能的な順序回路の例
 機能的な順序回路の例：
 レジスタ
 カウンタ
 シフト・レジスタ
論理回路基礎
レジスタ
D[0]
D Q
Q[0]
D[1]
D Q
Q[1]
D[n−1]
D Q
Q[n−1]
 n-bit レジスタ ≒
 n 個の D-FF
clk
論理回路基礎
レジスタ（ライト・イネーブル付き）
D[0]
D Q
Q[0]
D Q
Q[1]
D Q
Q[n−1]
 n-bit レジスタ ≒
 n 個の D-FF
D[1]
 Write-Enable：we
 0: 保持
 1: 書き込み
D[n−1]
we
clk
論理回路基礎
レジスタ（ライト・イネーブル付き）
D[0]
D Q
Q[0]
D[1]
D Q
Q[1]
D[n−1]
D Q
Q[n−1]
 n-bit レジスタ ≒
 n 個の D-FF
 Write-Enable：we
 0: 保持
 1: 書き込み
 クロック・ゲーティング
we
clk
論理回路基礎
クロック・ゲーティング
D Q
we
clk
c
time
clk
下げるのが
遅いと...
we
c
失敗！
論理回路基礎
リセット
 フリップ・フロップ
 初期状態（電源投入直後の状態）：不定 (unknown)
1
0
0
1
論理回路基礎
非同期リセット付き D-FF
 非同期リセット (asynchronous reset)
 クロックと関係なく（非同期に），出力を 0 に
data
sync_reset’
clock
D Q
R
R
async_reset’
D
Q
R
論理回路基礎
（バイナリ）カウンタ
Cin
 二進数を保存
D Q
Q[0]
D Q
Q[1]
D Q
Q[2]
 入出力：
 キャリー入力：Cin

1:
C0
インクリメント
桁上げ
(carry)
C1
0111
+) 1 0 1 1
1100
C2
clk
論理回路基礎
（バイナリ）カウンタ
 カウンタ：
 アップ・カウンタ
 ダウン・カウンタ
 アップ／ダウン・カウンタ
論理回路基礎
シフト・レジスタ
SI
D Q
PO[0]
D Q
PO[1]
D Q
PO[n−1]
 n-bit レジスタ
 入出力：
 Serial-In : SI
 Parallel-Out : PO[n−1...0]
clk
論理回路基礎
シフト・レジスタ（並列ロード付き）
SI
 n-bit レジスタ
PI[0]
D Q
PO[0]
D Q
PO[1]
D Q
PO[n−1]
 入出力：
 Serial-In : SI
 Parallel-Out : PO[n−1...0]
PI[1]
 Parallel-In : PI[n−1...0]
 Load：l

0: シフト

1: ロード
PI[n−1]
l
clk
論理回路基礎
シフト・レジスタ
 並列―直列，直列―並列変換 (parallel-serial, serial-parallel conversion)
SI
PI
SI
PO
PI
SO
clk
PO
SO
clk
clock recovery
論理回路基礎
リング・カウンタ
 リング・カウンタ
 シフト・レジスタの FF のうち，
プリセット

1つ：

残り：リセット
P
D Q
clk
reset’
D Q
D Q
D Q
R
R
R
論理回路基礎
今日のまとめ
論理回路基礎
今日のまとめ
 順序回路の簡単化
 機能的な順序回路
 レジスタ
 カウンタ
 シフト・レジスタ
論理回路基礎
今後の予定
 12/22
 演算回路
 1/12
 3/ 2
 試験（9:00～10:30）

Download Report