入出力の を決める

「論理回路」ノート (2013年度, c 関西学院大学 石浦 菜岐佐)

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

7 _順序回路

♣ 順序回路とは

♣ 状態遷移 ,状態遷移

♣ 記憶素子 と 式順序回路

7.1 順序回路とは

順序(論理)回路( (logic) circuit)

– 0 か1の値をとるn本の入力とm本の出力を持つ(組合せ回路と )

– その他の な入力

∗ … 入出力の を決める

∗ … 回路中の記憶を初期化する

input output

clock reset

– 出力の値は, および回路内部に記憶された によって決まる.

∗ 状態の数は .

∗ 次の状態は,現在の および によって決まる.

∗ 同じ入力であってもそのときの が異なれば出力は異なる.

∗ しかし,一番最初の状態( )と入力の が同じであれば,出力の系列は同 じになる.

【例1】 入力xに1 が連続3回入力されると,出力zに 1を出力する(それ以外は0を出力する)回路

状態

S⁰ … 過去に連続 1が入力された ( 状態) S¹ … 過去に連続 1が入力された

S2 … 過去に連続 1が入力された

動作例

xに系列1 1 0 1 1 1 1… が入力された場合 入力x

状態 出力z

S0

1

→ 0

S1

1

→ 0

S2

0

→ 0

S0

1

→

1

→

1

→

1

→ S2 · · ·

z には系列 が出力される

【例2】 4進カウンタ 入力c, 出力y1y0

動作

∗ c= 1 のとき: y1, y0= 00,01,10,11,00,01,· · · と2進数で 0〜3までをカウントアップする(3の 次は0に戻る).

∗ c= 0のとき: 同じ数を維持する.

状態

∗ S⁰, S¹, S², S³ でそれぞれ数 を記憶

∗ 初期状態はS0 とする 動作例

c に系列1 1 0 1 1 1… が入力された場合 入力c

状態 出力y¹y⁰

S⁰ 1

→ 00

S¹ 1

→ 01

S² 0

→

1

→

1

→

1

→ S¹ · · ·

y1y0には系列 が出力される

7.2 順序回路の動作の表現

7.2.1 状態遷移グラフ

状態遷移グラフ( )

順序回路の状態を 等で表現(グラフの用語では「節点」( ))

状態の遷移関係を (グラフの用語では「枝」( あるいは )) 入出力を枝や節点に書き添える(グラフの用語では「ラベル」 )

スラッシュ(/)の左側が で右側が

☆ 状態遷移図(state transition )とも呼ばれる

【例1】 1が3連続すると1を出力する回路

S⁰ S¹ S² 1/0 1/01/0

0/0 1/1

0/0

【例2】 4進カウンタ

S⁰/00 1 S¹/01 1 S²/10 1 S³/11

0 0 0 0

1

☆ 良く見ると【例1】と【例2】で が示してある場所が異なっている

【例1】では出力は入力にも依存するので,出力は入力と一緒に書いてある.

【例2】では,状態が決まると出力が一意に決まるので,出力は状態と一緒に書いてある.

「Mealy型」と「Moore型」に分類される (後述)

7.2.2 状態遷移表

状態遷移表(state transition )

状態遷移や入出力関係を の形で表したもの (情報量としては状態遷移グラフと全く同じ)

☆ 初期状態は別途指定されるが,特に指定がない場合,本講義では表の の状態が初期状態と する.

【例1】 1が連続3 回入力されると1 を出力する回路 現状態 次状態/出力z

x= 0 x= 1 S⁰ S⁰/0 S¹/0 S1 S0/0 S2/0 S2

あるいは次のように書いても等価

現状態 次状態 出力

x= 0 x= 1 x= 0 x= 1

S0 S0 S1 0 0

S¹ S⁰ S² 0 0

S² S⁰ S² 0 1

【例2】4進カウンタ

現状態 次状態 出力 c= 0 c= 1 y1y0

S0 S0 S1 0 0 S¹ S¹ S² 0 1 S² S² S³ 1 0 S3

7.2.3 Mealy 型順序回路と Moore型順序回路

☆ 言葉だけ

Mealy (ミーリー)型順序回路

出力が, と に依存して決まる順序回路

Moore (ムーア)型順序回路

出力が, のみに依存して決まる順序回路

【例1】の順序回路は 型

【例2】の順序回路は 型

7.3 順序回路の基本構造と非同期式/同期式

7.3.1 順序回路の基本構造

一般的な順序回路(Mealy型)の構成

を記憶する記憶素子と, 2つの関数を計算する回路により構成できる 出力=λ(入力,状態) ( 関数)

次状態=δ(入力,状態) ( 関数)

input

output

output function

state (memory) state transition

function

入出力と状態を で符号化すれば,λとδは 関数になり 回 路で実現できる

Moore型の場合は少し簡単になる

input

output function

state transition function

state (memory)

output

7.3.2 同期式順序回路と非同期式順序回路

• 同期(式順序)回路( (sequential) circuit)

記憶素子に ( )に同期して値を変える素子を用いる 代表的な記憶素子は

• 非同期(式順序)回路( (sequential) circuit)

記憶素子に を用いる

☆ 本講義では のみを扱う

☆ 回路では,わずかな の違いが思わぬ誤動作 につながることがあり,一般 には設計が難しい. このため,現在では同期式順序回路が主流となっている. しかし, VLSIの高速化によっ て配線の遅延が無視できなくなり,クロックをチップ全体に 無く分配することが困難にな りつつある現在,新しい設計方式が模索されている.

7.4 D フリップフロップ—記憶素子

☆ フリップフロップには色々な種類があるが,ここではまず代表的な「ポジティブエッジトリガのD フリップ フロップ」を紹介する. (その他のフリップフロップについては, 9章参照)

• D フリップフロップ( ) 1ビットの論理値を記憶する素子

• 入出力

入力: D ( ),CLK ( ) 出力: Q

D CLK

Q

• 動作

CLK 信号の ( → 変化)に同期して,D の信号値を記憶する

∗ CLK 信号の立上り時点でのDの値を ,これを記憶する

∗ 記憶している信号値はそのまま に出力される

∗ CLK 信号が変化しない限り,記憶している値(およびQの信号値)は

D 1 0 1 1 0

CLK ↑ ↑ ↑ ↑ ↑

Q 1

☆ CLK の立上りからQの変化までに若干の が生じる

D

HHH LLLLLLLLHHHHHHHHHHHHHHLLLLLL

CLK

LLHHLLHHLLHHLLHHLLHHH

Q

VVVÆHHHHHHLLLLLLHHHHHHHHHHHHHHLL

「CLKの立上り」のようなイベントを「トリガ」( )と呼ぶ

∗ CLKの立上りに応答するものを, ( )型 という

∗ その他(全部で4 型)は9章の「順序回路の設計(2)」で紹介する

• 入出力のバリエーション 1. Q出力

QとQの2 つの出力を持つフリップフロップが多い

Q= 0のときQ= となり,Q= 1 のときにはQ= となる

※ 回路の構成上,たまたまQと Qが同時に得られるので,それを利用しているだけ

2. リセット( )

記憶している値を強制的に0にする(クロック信号より ) リセット入力の値を にすることにより値を0 にするものが多い

D

HHHHHHLLLLLHHHHHHLL

CLK

LLHHLLHHLLHHLLL

RST

HHHHHLLLLLLLLHHHHHHHHHH

Q

VVVÆHLLLLLLLLLLLHHHHHH

3. プリセット( )… リセットの反対で,記憶値を強制的に にする

• Dフリップフロップの内部構成 【参考】

論理ゲートで構成され,フィードバックにより記憶が実現されている (動作原理は極めて難解)

Q

Q CLK

D RST

練習 7.1 リセット入力RST (信号値0でリセット動作するものとする),およびQ出力を持つポジティブエッ ジ型Dフリップフロップに対し,下図のような入力波形が与えられた時の出力QとQの波形を示せ.

D

HHLHHLLLLLHHHHLLL

CLK

LLHLHLHLHLHLL

RST

LLLLHHHHHHHHHHHHHHHHHHHHHHHHH

Q

...

Q

...

7.5 順序回路の実現例

【例2】 4進カウンタ

• 状態遷移グラフ •回路例

S⁰/00 S¹/01 S²/10 S³/11

1 1 1

0 0 0 0

1

d₀ d₁ c

clock

q₁

q₀ Q D

Q

Q D

Q

y₁

y₀

• 動作例

c

LHHHHHHHLLLLHHHHHHHHHHHHHHHHLLLLHHHHH

CLK

LLHLHLHLHLHLHLH LH

y1

LLLLLLLLLHHHHHHHHHHHHHHHHLLLLLLLLLLLLLLLL

y0

LLLHHHHLLLLLLLLLLHHHHLLLLHHHHHHHHHH

各信号線の各時刻での信号値は, クロックの で決まる

入力c 1 1 0 1 1 1 0 1 · · ·

出力y¹ 0 0 1 1 1 0 0 0 · · ·

出力y0 0 1 0 1 1 · · ·

練習問題の解答例

練習7.1

D

HHLHHLLLLLHHHHLLL

CLK

LLHLHLHLHLHLL

RST

LLLLHHHHHHHHHHHHHHHHHHHHHHHHH

Q

VLLLLLLHHHHLLLLLLLLLLHHHH

Q

VÆHHHHHHLLLLHHHHHHHHHHLLLL

Nagisa ISHIURA