8 順序回路の設計 (1)

「論理回路」ノート

年度

関西学院大学 石浦 菜岐佐

http://ist.ksc.kwansei.ac.jp/∼ishiura/lc/

8 _{順序回路の設計} (1)

♣

D フリップフロップを用いた同期式順序回路の設計

♣

状態 最小化

8.1

設計の流れ

(1)

状態遷移表の作成

(2)

状態 最小 ^化

(3)

入出力, 状態の 符号 ^化

状態 ^割当て)

(4)

状態遷移 ^関数, 出力 ^{関数を求める}

(5)

フリップフロップの入力関数を求める

組合せ回路の設計

8.2

具体的な設計法

「50 円玉と

円玉を受け付け, 150 円のジュースを売る自動販売機の制御部」を設計 入力

− 何も入らない 50 50円の投入 100 100円の投入

状態

S⁰ 0円が入っている(初期状態) S⁵⁰ 50円が入っている

S100 100円が入っている

出力

(−,−) ジュースもお釣も出さない (J,−) ジュースだけ出す

(J,50) ジュースと50円のお釣を出す

(1)

状態遷移表の作成

状態遷移グラフ

S0 S50 S100

−/(−,−) −/(−,−) −/(−,−) 50/(−,−)

100/(J,−) 50/(−,−) 100/(−,−) 50/(J,−),100/(J,50)

⇓ 2

状態遷移表

現状態 次状態 出力

入力

入力

入力

入力

入力

入力

(2)

状態最小化

状態遷移表で表された順序回路を, 同じ動作をする最も 状態数 の少ないものに変換する.

この例の場合は, 既に状態数最小なのでこのステップは不要. 状態最小化の方法の詳細は次節で述べる.

(3)

入出力

状態の符号化

入力, 状態, 出力を 0 と 1 ^{で符号化する}

例えば, 次のように符号化できる 入力

−

0 0

50

0 1

100

1 0

状態

S⁰

0 0

S50

0 1

S100

1 0

出力

(−,−)

0 0

(J,−)

1 0

(J,50)

1 1

☆ 実は, この状態と入出力の符号化によって, 最終的な回路の規模・複雑さは大きく変わってくる. 回路が簡単 になるような符号化を求めるための理論は多数あるが, それはいずれも大変難しい

(4)

状態遷移関数

出力関数を求める

(3)

で決めた符号化に従って, 状態遷移表を全て 0 と 1 ^{だけで表す}

2

状態遷移表

現状態 次状態 出力

入力

入力

入力

入力

入力

入力

S⁰ S⁰ S⁵⁰ S¹⁰⁰ (−,−) (−,−) (−,−)

S⁵⁰ S⁵⁰ S¹⁰⁰ S⁰ (−,−) (−,−) (J,−)

S¹⁰⁰ S¹⁰⁰ S⁰ S⁰ (−,−) (J,−) (J,50)

⇓

符号化

入力 x1 x2

− 0 0 50 0 1 100 1 0

状態 q1 q2

S0 0 0 S50 0 1 S100 1 0

出力 z1 z2

(−,−) 0 0 (J,−) 1 0 (J,50) 1 1

3

符号化された状態遷移表

q¹q² q^′1q2^′ (次状態) z¹z²(出力)

x¹x²= 0 0 x¹x²= 0 1 x¹x²= 1 0 x¹x²= 0 0 x¹x²= 0 1 x¹x²= 1 0

0 0 0 0 0 1 1 0 0 0 0 0 0 0

0 1 0 1

1 0 0 0 0 0 0 0 1 0

1 0 1 0

0 0 0 0 0 0 1 0 1 1

(5)

フリップフロップ入力関数を求める

の場合には超簡単)

(4)

で求めた状態遷移

から

への変化) 起こすためには, フリッ

プフロップの入力にどのような値を入れれば良いかを求める

q d x1

x2

z1

z2

1

q2

1

d₂

clock Q D Q D combinational

circuit

D

フリップフロップの場合には,

の値が次の時刻にそのまま

に出るので,

となる.

3

符号化された状態遷移表

q1q2 q^′1q2^′ (次状態) z1z2(出力)

x1x2= 0 0 x1x2= 0 1 x1x2= 1 0 x1x2= 0 0 x1x2= 0 1 x1x2= 1 0

0 0 0 0 0 1 1 0 0 0 0 0 0 0

0 1 0 1 1 0 0 0 0 0 0 0 1 0

1 0 1 0 0 0 0 0 0 0 1 0 1 1

⇓ D-FF

の場合は

をそのまま

にするだけ

フリップフロップの入力関数, 出力関数

q1q2

d

d

への入力)

x1x2= 0 0 x1x2= 0 1 x1x2= 1 0 x1x2= 0 0 x1x2= 0 1 x1x2= 1 0

0 0 0 0 0 1 1 0 0 0 0 0 0 0

0 1 0 1 1 0 0 0 0 0 0 0 1 0

1 0 1 0 0 0 0 0 0 0 1 0 1 1

(6)

組合せ回路の設計

フリップフロップの入力関数と出力関数の カルノー図 ^{を作り, 組合せ回路を設計}

例)

の入力関数

4

の表の

の列より

(q1, q2, x1, x2) = (0,0,0,0)

のとき

0

(q¹, q², x¹, x²) = (0,0,0,1)

のとき

0

(q1, q2, x1, x2) = (0,0,1,0)

のとき

1

· · ·

【重要】このとき, 使われていない符号 に対する関数の値は ドントケア とする

1 , 1

^と

1 , 1

^{は使われていない}

(q1, q2, x1, x2) = (0,0,1,1)

のとき

X

(q1, q2, x1, x2) = (0,1,1,1)

のとき

X

(q , q , x , x ) = (1,0,1,1)

のとき

X

(q¹, q², x¹, x²) = (1,1,1,0)

のとき

X

(q1, q2, x1, x2) = (1,1,1,1)

のとき

X

カルノー図を作成し, 論理関数を最小化

q¹q² 00 01 11 10

x1x2

00 01 11 10 X 1 1 X X X X X

1 X

q¹

q2

x1

x² X 1 1 X X X X X

1 X

d¹=

q

q

x

+ q

x

x

+ q

x

同様にして,

および出力

の最小積和形を求める

☆ この回路は Mealy ^{型なので,} 出力が状態と入力の両方に依存しているが, Moore ^型

の場合は, 出力は状態だけに依存する.

最小化した論理式から回路を設計する

Q D Q

d₁ d₂ x₂

x₁

z₁

z₂

Q D Q

clock q₁

q₂

練習

上記の

と同様にして

のカルノー図を作成し, 最小積和形を求めよ.

4

フリップフロップの入力関数, 出力関数

q1q2 d1d2(FF

への入力)

x1x2= 0 0 x1x2= 0 1 x1x2= 1 0 x1x2= 0 0 x1x2= 0 1 x1x2= 1 0

0 0 0 0 0 1 1 0 0 0 0 0 0 0

0 1 0 1 1 0 0 0 0 0 0 0 1 0

1 0 1 0 0 0 0 0 0 0 1 0 1 1

d

q

q

00 01 11 10

x

x

00 01 11 10

z

q

q

00 01 11 10

x

x

00 01 11 10

z

q

q

00 01 11 10

x

x

00 01 11 10

8.3

状態最小化

状態最小化

state minimization

^とは

与えられた状態遷移表を, 同じ動作で 状態数 のできるだけ少ないものに変換する 現状態 次状態, 出力

x= 0 x= 1 S⁰ S¹,1 S²,0 S¹ S⁰,1 S²,0 S² S²,0 S¹,1

⇒

現状態 次状態, 出力

S² S²,0 S⁰¹,1

等価 ^な状態

^{外部からは} 区別 ^{できない状態) を} 併合 ^{して一つの状}

態にする.

最小化のアルゴリズム

☆ 最初は「 全て の状態が等価」と仮定して, 全 ^状態を

つのグループにまとめた所からスター トし, これを識別可能なグループに次々に 分割 ^していく

1)

出力 を観測することにより識別可能な状態を, 出力値に従ってグループ分けする.

(全ての入力に対して

同じ出力 を出す状態を同一グループにまとめる)

2)

下記のグループの 分割 をそれ以上できなくなるまで行なう

2.1)

各グループ

内の状態について, 同じ入力を与えた時の 次状態 が同じグループに属して いるかどうか調べる.

2.2)

全ての入力について次状態が同じグループに属していれば, そのグループの分割は終了

2.3)

もしいずれかの入力について次状態が異なるグループに属していれば,

を

に分割し,

の状態同一入力に対する次状態が全て同じグループに属するようにする.

併合

現状態 次状態, 出力

x= 0 x= 1 ^0x1 Sa Sa,0 Sb,0 0 0 Sb Sd,1 Sa,1 1 1 Sc Sc,0 Se,0 0 0 Sd Sf,1 Se,1 1 1 Se Sd,1 Sc,1 1 1 Sf Se,1 Sa,0 1 0

⇒

現状態 次状態, 出力

x= 0 x= 1 ^0x1 0

S

S

S

S

S

S

⇒

現状態 次状態, 出力

x= 0 x= 1 ^0x1 0 Sa Sa,0 Sb,0 0 1 Sc Sc,0 Se,0 0 1 1

S

S

S

⇒

現状態 次状態, 出力

x= 0 x= 1

0

S

S

S

1

S

S

3 Sd Sf,1

S

2 Sf

S

S

コメント

•

ここで紹介した状態最小化は, 完全定義

すべての次状態, 出力が定義されている) の 状態遷移表に対する方法である. 不完全定義

次状態や出力にドントケアが存在す る) の状態最小化には異なるアルゴリズムが必要となるが, それは大変難しい.

•

状態最小化を行なって得られる回路が, 行なわない回路よりも小さい とは限らない

^{状態数の減}

少によりフリップフロップの個数が減ることはあるが, 逆に論理回路が複雑になることもある.

練習問題の解答例

練習

d2

q1q2

00 01 11 10

x1x2

00 01 11 10 1 X

1 X

X X X X X d2=q1q2x2+q2x1x2

z1

q1q2

00 01 11 10

x1x2

00 01 11 10 X X 1 X X X X

1 X 1

z1=q2x1+q1x2+q1x1

z2

q1q2

00 01 11 10

x1x2

00 01 11 10 X X X X X X

X 1 z2=q1x1

Nagisa ISHIURA