第5章 順序論理回路

第5章 順序論理回路

順序論理回路とは
– 値段と速度の兼ね合い
– 遅延と記憶
– 状態変数
– 同期順序回路と非同期順序回路

同期順序回路の解析と設計
– 状態遷移図と状態遷移表
– 状態遷移図の作り方
– 状態の簡約化(圧縮)
– 記憶回路
順序論理回路とは

組合せ回路
– 入力変数が決まると出力が一意に決まる.

順序回路
– 現在の出力が現在の入力だけでなく,過去の
履歴による影響を受ける.
値段と速度の兼ね合い

奇遇パリティチェック回路
– 排他的論理和 A  B
AB
00
01
10
11
A B
0
1
1
0
桁上げのない加算
A  B  AB  A B
組合せ回路
順序回路
時間とコスト


Ex-or gate … 3つのnand gate
組合せ回路… 7x3個のnand gate
– コストがかかる.

8つのデータが同時に与えられる場合には
– 順序回路のほうが時間がかかる.

同じ機能を二つの方法で実現できる.
– 装置の複雑さ,コスト
– 要求される速度,他の部分との関係
並列と直列
並列
値
段
直列
速度
遅延と記憶

ゲートでは必ず遅延が生じる.
f (t )  A(t  ) B(t  )
A

B
A(t )
B(t )
f (t )

f
順序回路の表現

入力X, 出力Z, 状態 S

過去の入力が状態で保存されるとする.
X
S
H
G

Z
同期順序回路と非同期順序回路
 A  C 1
f ( A, B, C )  AC  BC  
 B  C 0
– Cがセレクタで,AかBを選ぶ.
– A  B  1 であれば B の値に無関係にい
つも1を出力する.
w
1
C
z
1
y
x
C
w
x
y
z
ハザード

ゲートにおける微妙な遅延時間
– 製造工程でのばらつき
– 温度,環境の影響


避けることが難しい.
ハザードがあっても誤動作のない設計
– 同期回路 クロック時点における信号の変化
– 非同期回路 あらゆる時刻における信号
同期・非同期

同期回路
– ハザードの影響がないので設計が容易である.
– クロックの速度で動作速度が決まる.

非同期回路
– 設計が難しい.
– 素子の動作できる最高速度での利用が可能


この講義ではほとんどが同期順序回路
以後は時間軸を離散的に考える.
同期順序回路

i はすべて等しいとする.
とし,
X
S
H
G

Z
時計信号


入力変数の変化はクロックのパルスとパ
ルスの間でのみ許される.
クロックパルスの間隔 T
– 状態メモリの分解能時間(サイクルタイム)
– クロックパルスが入ってから組合せ回路Gの
出力まで状態の変化が伝搬するのに必要な
時間 TL
のいずれよりも長くなければならない.

メモリのトリガに必要な幅,かつ TL よりも
狭いこと.
同期順序回路の例
M1



M2
入力はビット系列
‘111’のパターンを検出する回路
M1, M2 は1ビット時間の記憶回路
状態遷移表

4通りの状態
01101001011101011110
M1 M2
X→ 00
01
10
11
X=0
00
00
01
01
X=1
10
10
11
11
M1
M2
状態遷移表

4通りの状態を割り当てる.
=1
=1
状態の簡約化
状態遷移図
例題

ちょうど2個の‘0’のあとに‘10’が入力さ
れる事象の検出
…110010110100100100…
…000001000000010010…
t
入力信号
0
1
0
0
1

入力系列 ...10010…→ 時間
x
過去のパターン
– 過去の入力4桁を状態にとってみる.
0000 0001 0010 0011 0100 0101 0110 0111
1000 1001 1010 1011 1100 1101 1110 1111
– 次の状態は
…1011x… → …1011x… → …10110…
→ …10111…
すなわち、状態の変化は
0110 x  0 のとき
1011 
 0111 x  1 のとき
状態遷移表
現在の状態
0000
0001
0010
0011
0100
0101
0110
0111
次の状態/出力
x0
x 1
現在の状態
0000/0
0010/0
0100/0
0110/0
1000/0
1010/0
1100/0
1110/0
0001/0
0011/0
0101/0
0111/0
1001/0
1011/0
1101/0
1111/0
1000
1001
1010
1011
1100
1101
1110
1111
次の状態/出力
x0
x 1
0000/0
0010/1
0100/0
0110/0
1000/0
1010/0
1100/0
1110/0
0001/0
0011/0
0101/0
0111/0
1001/0
1011/0
1101/0
1111/0
10進数で表現
現在の状態
0
1
2
3
4
5
6
7
次の状態/出力
x0
x 1
現在の状態
0/0
2/0
4/0
6/0
8/0
10/0
12/0
14/0
1/0
3/0
5/0
7/0
9/0
11/0
13/0
15/0
8
9
10
11
12
13
14
15
次の状態/出力
x0
x 1
0/0
2/1
4/0
6/0
8/0
10/0
12/0
14/0
1/0
3/0
5/0
7/0
9/0
11/0
13/0
15/0
等価な状態で書き換える
現在の状態
0
1
2
3
4
5
6
7
次の状態/出力
x0
x 1
0/0
1/0
2/0
3/0
4/0
5/0
6/0
7/0
8/0
9/0
0=
10/0 3==
11/0
2==
4==
12/0 5==
13/0
14/0 7==
15/0
6==
現在の状態
8
9
10
11
12
13
14
15
次の状態/出力
x0
x 1
0/0
2/1
4/0
6/0
8/0
10/0
12/0
14/0
1/0
3/0
5/0
7/0
9/0
11/0
13/0
15/0
0
2
3
4
5
6
7
等価な状態で書き換える
現在の状態
1
2
3
0
1
2
3
4
5
6
7
次の状態/出力
x0
0/0
2/0
4/0
2=6/0
0/0
2/0
4/0
6/0
x 1
1/0
3/0
1=5/0
3=7/0
9/0
3/0
5/0
7/0
現在の状態
9
次の状態/出力
x0
x 1
2/1
3/0
等価な状態で書き換える
現在の状態
1
0
1
2
3
4
次の状態/出力
x0
0/0
2/0
4/0
2/0
0/0
x 1
1/0
1=3/0
1/0
3/0
9/0
現在の状態
9
次の状態/出力
x0
2/1
x 1
1=3/0
等価な状態で書き換える
現在の状態
0
1
2
4
9

次の状態/出力
x0
x 1
0/0
2/0
4/0
0/0
2/1
1/0
1/0
1/0
9/0
1/0
もう書き換えられない.
等価族を求める.
C
a
c
b
C
a
d
c
b
現在の状態
0
1
2
4
9
次の状態, C
x0
x 1
0, a
2, a
4, =c
a
0, a
2, a
1,
1,
1,
9,
1,
a
a
a
b
a
次の状態, C
現在の状態
x0
x 1
0
1
2
4
9
0, a
2, =d
a
4, c
0, a
2, =d
a
1,
1,
1,
9,
1,
a
a
a
b
a
等価族を求める.
次の状態, C
C
現在の状態
x0
x 1
a
0
1
2
4
9
0, a
2, d
4, c
0, a
2, d
1, =e
a
1, =e
a
1, =e
a
9, b
1, =e
a
e
d
c
b
C
現在の状態
a
e
d
c
b
0
1
2
4
9
次の状態, C
x0
x 1
0, a/0
2, d/0
4, c /0
0, a/0
2, d/1
1, e/0
1, e/0
1, e/0
9, b/0
1, e/0
状態遷移表と状態遷移図
現在の 次の状態/出力
状態
x  0 x 1
a
e
d
c
b
a/0
d/0
c/0
a/0
d/1
e/0
e/0
e/0
b/0
e/0
1/0
0/1
1/0
1/0
0/0
1/0
0/0
0/0
1/0
0/0
状態圧縮のまとめ


出力によって状態をクラス分けする.
クラスごとに
– 次の状態が同じになる行がある限り
• 状態を圧縮し、番号を付け直す.

同一クラス中に異なる行き先クラスがある限り
– 次のクラスの等しいものを集めて新しいクラス
を作る.
– クラスの書き直しをする.