順序回路の設計 (2)

c 関西学院大学石浦菜岐佐)
「論理回路」ノート (2014 年度, http://ist.ksc.kwansei.ac.jp/∼ishiura/lc/
9
順序回路の設計 (2)
♣ SR, T,
JK
フリップフロップを用いた同期式順序回路の設計
♣ 色々な順序回路 (状態遷移グラフ) の設計
9.1
9.1.1
種々のフリップフロップ
トリガ信号の種類
フリップフロップのトリガ (
(1) 立上り (クロックの
(2) 立下り (クロックの
クロック
0→1
1→0
変化) (
変化) (
信号) には 4 タイプある
positive
negative
edge)
edge)
1
立上りで D の値が読み込まれ, 立下り
( master-slave 型と呼ばれる)
(3) 信号値
Æ D
CLK
Q
(4) 信号値
9.1.2
でその値が Q に出される.
0
… 信号値 1 の逆
フリップフロップの種類
D フリップフロップを含めて 4 タイプのフリップフロップがある
それぞれにトリガが 4 種類があるので, 理論上は計 4 × 4 = 16 通りのフリップフロップがある
動作表
☆ Q は現在の出力, Q はクロック信号が入った後の出力
(a) D フリップフロップ
D
0
1
Q
0
1
(b) SR フリップフロップ
入力として S, R を持つ
☆ S は
set
,Rは
reset
と覚える
9–1
S
R
0
0
0
1
1
0
1
1
Q
Q
0
1
−
· · · 現在の信号値を維持 (信号値変化なし)
· · · 入力
禁止
(出力は
不定
;
発振
したり
破損
する)
(c) T フリップフロップ
入力として T を持つ
toggle
☆ T は
の略と言われる
Q
T
Q
Q
0
1
· · · 信号値変化なし
· · · 信号値反転
※通常, クロックとは別に Q を 1 や 0 に設定するセット入力やリセット入力を持つ
(d) JK フリップフロップ
入力として J, K を持つ
☆ JK の名前の由来は諸説ある
練習 9.1
J
K
0
0
0
1
1
0
1
1
Q
Q
0
1
Q
· · · SR と同じ
· · · SR と同じ
· · · SR と同じ
· · · 信号値
反転
下図は JK フリップフロップの入出力の時系列を表したものである. Q 出力の空欄を埋めよ.
J
K
CLK
Q
1
0
↑
0
0
↑
1
1
↑
1
1
↑
0
1
↑
1
☆ ポジティブエッジ型の JK フリップフロップの動作波形
J
K
CLK
Q
Æ 9–2
9.2
SR, T, JK フリップフロップによる設計
☆ 異なるのは, フリップフロップの入力関数だけ
(1) 状態遷移表の作成
(2) 状態最小化
(3) 状態割当て (入出力, 状態の符号化)
(4) 状態遷移関数, 出力関数を求める
(5) フリップフロップの入力関数を求める
(6) 組合せ回路の設計
9.2.1
準備: フリップフロップの入力要求表の作成
入力要求表
フリップフロップ現在の出力値 Q を, 次時刻で Q にしたい時に, どのような
入力の組合せ
を入れれば良いかを表にしたもの
1) D-フリップフロップ
機能表
D
Q
0
0
1
1
入力要求表
Q
Q
0
0
0
1
1
1
0
1
D
0 · · · (※ 1)
1
0
1
(※ 1) の解説
∗ フリップフロップの現在の出力 (Q) が 0 のとき, 次の時刻の出力 (Q ) を 0 にしたければ, D に 0
を入力すればよい.
2) SR-フリップフロップ
機能表
S
R
Q
Q
0
0
0
1
Q
0
0
0
入力要求表
Q
S R
0
0 X 1 0
1
1
1
0
1
1
−
1
0
0 1
1
1
X 0
· · · (禁止)
· · · (※ 2)
(※ 2) の解説
∗ SR フリップフロップの現在の出力 (Q) が 0 のとき, 次の時刻の出力 (Q ) を 0 にするには,
(S, R) = (0, 1) としてもよいが, (S, R) =
(0, 0)
としてもよい. この 2 パタンをまとめると
(S, R) = (0, X) と書ける. (X はドントケアで, 0 でも 1 でもよいから.)
3) T-フリップフロップ
機能表
入力要求表
T
Q
Q
Q
T
0
Q
0
0
0
1
Q
0
1
1
0
1
1
1
1
0
9–3
4) JK-フリップフロップ
機能表
9.2.2
入力要求表
Q
Q
Q
0
0
1
0
0
1
0
1
1
Q
1
0
1
1
J
K
Q
0
0
0
1
1
J
K
0
1
X
X
X
X
1
0
···
···
···
···
0
1
0
1
1
0
1
0
0
1
1
0
(オフ) と
(オン) と
(オフ) と
(オン) と
0
1
1
0
(維持)
(反転)
(反転)
(維持)
フリップフロップの入力関数の求め方 (JK フリップフロップの例)
前章の自動販売機の制御回路を JK フリップフロップで設計
2 状態遷移表
現状態
次状態
出力
入力 = −
入力 = 50
入力 = 100
入力 = −
入力 = 50
入力 = 100
S0
S0
S50
S100
(−, −)
(−, −)
(−, −)
S50
S100
S50
S100
S100
S0
S0
S0
(−, −)
(−, −)
(−, −)
(J, −)
(J, −)
(J, 50)
符号化
入力
−
50
100
⇓
x1
0
0
1
状態
S0
S50
S100
x2
0
1
0
q1
0
0
1
出力
(−, −)
(J, −)
(J, 50)
q2
0
1
0
z1
0
1
1
z2
0
0
1
3 符号化された状態遷移表
q1 q2 (次状態)
q1 q2
x1 x2 = 0 0
z1 z2 (出力)
x1 x2 = 0 0
x1 x2 = 0 1
x1 x2 = 1 0
00
01
x1 x2 = 0 1
0 1 3
10
x1 x2 = 1 0
00
01
10
00
00
00
00
00
00
10
10
10
00
00
00
10
11
⇓
JK フリップフロップ
J
0
0
1
1
機能表
K Q
0
Q
0
1
1
0
1
Q
Q
0
0
1
1
入力要求表
Q
J
0
0
1
1
X
0
X
1
K
X
X
1
0
4 フリップフロップの入力関数, 出力関数
j1 k1 j2 k2
(JK-FF の入力)
q1 q2
x1 x2 = 00
00
0 X 0 X
x1 x2 = 01
0 X 1 X 3
01
0 X X 0
1 X X
1
10 X 0 0 X
3 の部分の解説
X 1 0
X
z1 z2 (出力)
x1 x2 = 10
1X0X
0XX1
X10X
q1 q2
q1 q2
現状態 0 0 を次状態で 0 1 に変えたい.
9–4
x1 x2 = 00
x1 x2 = 01
x1 x2 = 10
00
00
00
00
00
10
00
10
11
q1
q1
0 → 0 とするためには, フリップフロップの「入力要求表」より,
j1 k1
0 X とすればよい.
j2 k2
q2
q2
同様に 0 → 1 とするためには, 1 X とすればよい.
この後は D フリップフロップの場合と同様, カルノー図により j1 , k1 , j2 , k2 および z1 , z2 の関数を最
小化し, 回路を設計する.
x1 + x2
x1 x2
q1 q2 00 01 11 10
00 X X X X
k1 =
j1 = x1 q2 + x2 q2
x1 x2
00
01
11 10
q1 q2
00
X 1
1
01
01 X X X X
X
11 X X X X
11 X X X X
10 X X X X
1 X 1
10
練習 9.2
同様にして, j2 と k2 の関数を求め, 最小化せよ.
j2 =
x2q1
x1 + x2
x1 x2
q1 q2 00 01 11 10
00 X X X X
k2 =
x1 x2
q1 q2 00 01 11 10
1 X
00
01
11 X X X X
11 X X X X
10
10 X X X X
X
出力関数 z1 , z2 は D フリップフロップの場合と全く同じである.
z1 = q2 x1 + q1 x2 + q1 x1
x1 x2
00
01
11 10
q1 q2
00
X
01
X
1
11 X X X X
10
1 X 1
01 X X X X
1
X
1
z2 = q1 x1
x1 x2
00
01
11 10
q1 q2
00
X
01
X
11 X X X X
10
X
9–5
1
JK-FF を用いて設計した回路
(参考) D-FF を用いて設計した回路
x1
x1
z1
x2
z1
x2
z2
z2
j2
d2
k1
j1
d1
q1
Q
J
Q K
q2
Q
q1
J
Q D
Q
Q K
q2
clock
Q D
Q
clock
9.3
9.3.1
順序回路の例 (状態遷移グラフの設計)
ビットパターンを検出する回路
例題 9.1 次のような Moore 型順序回路の状態遷移グラフを示せ.
この回路は 1 ビットの入力 x と 1 ビットの出力 z を持ち, x に過去 3 時刻 (現時刻は含まない) に 1 0 1 が入力
されていれば z に 1 を, そうでなければ z に 0 を出力する. 例えば, x に 1 1 0 1 0 0 1 0 1 0 1 1 · · · を入力した
場合の出力は次のようになる.
0 1 2 3 4 5 6 7 8 9 10 11 · · ·
時刻
入力
x
1 1 0 1 0 0 1 0 1 0 1
1 ···
出力
z
0 0 0 0 1 0 0 0 0 1 0
1 ···
状態遷移グラフは例えば次のようになる.
0
S/0
1
1
S1 /0
1
0
0
S10/0
1
0
9–6
S101/1
例題 9.2 次のような Mealy 型順序回路の状態遷移グラフを示せ.
この回路は 1 ビットの入力 x と 1 ビットの出力 z を持ち, x に現時刻と過去 2 時刻に 1 0 1 が入力されていれば
z に 1 を, そうでなければ z に 0 を出力する. 例えば, x に 1 1 0 1 0 0 1 0 1 0 1 1 · · · を入力した場合の出力は
次のようになる.
0 1 2 3 4 5 6 7 8 9 10 11 · · ·
時刻
入力
x
1 1 0 1 0 0 1 0 1 0 1
1 ···
出力
z
0 0 0 1 0 0 0 0 1 0 1
0 ···
状態遷移グラフは例えば次のようになる.
0/0
1/0
1/0
S
0/0
S1
S10
1/1
0/0
9.3.2
可変長符号復号回路
下記の表の可変長符号の復号を行う順序回路を考える.
記号
固定長符号
可変長符号
a
001
0
b
c
010
011
100
101
d
e
100
101
1100
1101
f
g
110
111
1110
1111
【解説】
可変長符号とは
記号の集合 (上の例では {a, b, c, d, e, f, g}) の 2 進符号化を行う際, 符号長が全て等しい符号を
「
固定長
符号」, 記号毎に符号長が異る符号を「可変長符号」と呼ぶ. 例えば上の例で,
「acaga」という記号列を表の固定長符号で符号化すると, 「001 011 001 111 001」となるのに対
し, 可変長符号で符号化すると, 「0 101 0 1111 0」が得られる. 可変長符号は, 出現
高い記号に
短い
頻度
の
符号語を割り当てることによって総データ量を削減するもので, データの通
信や保存の際に良く用いられる.
可変長符号の復号とは
可変長符号「0 101 0 1111 0」が与えられたときに, ここから同じ記号列「acaga」を表す固定長符
号「001 011 001 111 001」を求める処理.
可変長符号復号回路
入力: 1 ビット x
出力: 3 ビット (y1 , y2 , y3 )
動作
9–7
可変長符号は x に 1 ビットづつシリアルに入力され, 符号が認識される毎に (y1 , y2 , y3 ) に対
応する固定長符号の各ビットが 3 ビットパラレルに出力される. 固定長符号の出力が無い間は
(y1 , y2 , y3 ) = (0, 0, 0) が出力されるものとする.
動作例
0
1
2
3
4
5
6
7
8
9
···
0
1
0
1
0
1
1
1
1
0
···
a
?
?
c
a
?
?
?
g
a
···
y1
y2
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
0
0
···
···
y3
1
0
0
1
1
0
0
0
1
1
···
時刻
入力
x
(記号)
出力
状態遷移グラフ
記号
a
b
c
d
e
f
g
固定長符号
001
010
011
100
101
110
111
可変長符号
0
100
101
1100
1101
1110
1111
1/000
0/001
1/000
0/000
0/000
1/000
0/010, 1/011
0/100, 1/101
0/110, 1/111
練習問題の解答例
練習 9.1
J
1
0
1
1
0
K
CLK
0
↑
0
↑
1
↑
1
↑
1
↑
Q
1
1
0
1
0
練習 9.2
q1 q2
00
j2 = x2 q1
x1 x2
00 01 11 10
1
X
k2 = x1 + x2
x1 x2
q1 q2 00 01 11 10
00 X X X X
01 X X X X
01
11 X X X X
11 X X X X
10
10 X X X X
X
1
X
1
Nagisa ISHIURA
9–8

Download Report