同期

(1)

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

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

7 _順序回路

♣ 順序回路とは

♣ 状態遷移

グラフ

^,^状態遷移

表

♣ 記憶素子

フリップフロップ

^と

同期

^{式順序回路}

7.1 順序回路とは

順序(論理)回路(

sequential

(logic) circuit)

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

同じ

⁾

– その他の

特別

^な入力

∗

クロック

^{… 入出力の}

タイミング

^を決める

∗

リセット

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

input output

clock reset

– 出力の値は,

入力

および回路内部に記憶された

状態

^{によって決まる.}

∗ 状態の数は

有限

^.

∗ 次の状態は,現在の

状態

^および

入力

^{によって決まる.}

∗ 同じ入力であってもそのときの

状態

が異なれば出力は異なる.

∗ しかし,一番最初の状態(

初期状態

⁾^と入力の

系列

^{が同じであれば,}^{出力の系列は同}

じになる.

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

状態

S⁰ … 過去に連続

0 回

¹^{が入力された} ⁽

初期

^状態)

S¹ … 過去に連続

1 回

¹^{が入力された}

S2 … 過去に連続

2 回以上

¹^{が入力された}

(2)

動作例

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

状態出力z

S0

1

→ 0

S1

1

→ 0

S2

0

→ 0

S0

1

→

0 S

¹

1

→

0 S

²

1

→

1 S

²

1

→

1

S2 · · ·

z には系列

0 0 0 0 0 1 1 …

^{が出力される}

【例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³ でそれぞれ数

0, 1, 2, 3

^を記憶

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

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

状態出力y¹y⁰

S⁰ 1

→ 00

S¹ 1

→ 01

S² 0

→

10 S

²

1

→

10 S

³

1

→

11 S

⁰

1

→

00

S¹ · · ·

y1y0には系列

00 01 10 10 11 00 …

^{が出力される}

7.2 順序回路の動作の表現

7.2.1 状態遷移グラフ

状態遷移グラフ(

state transition graph

⁾

順序回路の状態を

円

^等で表現(グラフの用語では「節点」(

node

⁾⁾

状態の遷移関係を

矢印

(グラフの用語では「枝」(

edge

^あるいは

arc

⁾⁾

入出力を枝や節点に書き添える(グラフの用語では「ラベル」

label

⁾

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

入力

^で右側が

出力

☆ 状態遷移図(state transition

diagram/chart

⁾^{とも呼ばれる}

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

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

0/0 1/1

0/0

(3)

【例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

table

⁾

状態遷移や入出力関係を

表

^{の形で表したもの}

(情報量としては状態遷移グラフと全く同じ)

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

一番上

^{の状態が初期状態と}

する.

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

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

S

⁰

/0 S

²

/1

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

現状態次状態出力

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

S

³

S

⁰

1 1

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

☆ 言葉だけ

(4)

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

出力が,

現状態

^と

入力

に依存して決まる順序回路

Moore (ムーア)型順序回路

出力が,

現状態

のみに依存して決まる順序回路

【例1】の順序回路は

Mealy

^型

【例2】の順序回路は

Moore

^型

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

7.3.1 順序回路の基本構造

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

状態

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

出力

^関数)

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

状態遷移

^関数)

input

output

output function

state (memory) state transition

function

入出力と状態を

0 と 1

^{で符号化すれば,}^λ^と^δ^は

論理

^{関数になり}

組合せ論理

^回

路で実現できる

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

input

output function

state transition function

state (memory)

output

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

• 同期(式順序)回路(

synchronous

(sequential) circuit)

記憶素子に

同期信号

⁽

クロック

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

フリップフロップ

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

asynchronous

(sequential) circuit)

(5)

記憶素子に

遅延素子

^を用いる

☆ 本講義では

同期式

^{のみを扱う}

☆

非同期

^{回路では,}^わずかな

タイミング

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

時間歪み

無く分配することが困難になりつつある現在,新しい設計方式が模索されている.

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

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

• D フリップフロップ(

D flip-flop

⁾

1ビットの論理値を記憶する素子

• 入出力

入力: D (

データ

^),^CLK ⁽

クロック

⁾

出力: Q D CLK

Q

• 動作

CLK 信号の

立上り

⁽

0

^→

1

^変化)^{に同期して,}^D ^{の信号値を記憶する}

∗ CLK 信号の立上り時点でのDの値を

読み

^,^{これを記憶する}

∗ 記憶している信号値はそのまま

Q

^{に出力される}

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

変化しない

D 1 0 1 1 0

CLK ↑ ↑ ↑ ↑ ↑

Q 1

0 1 1 0

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

遅延

^が生じる

D

HHH LLLLLLLLHHHHHHHHHHHHHHLLLLLL

CLK

LLHHLLHHLLHHLLHHLLHHH

Q

VVVÆHHHHHHLLLLLLHHHHHHHHHHHHHHLL

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

trigger

⁾^と呼ぶ

(6)

∗ CLKの立上りに応答するものを,

ポジティブエッジ

⁽

positive edge

⁾^型

という

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

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

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

Q= 0のときQ=

1

^となり,^Q^{= 1} ^{のときには}^Q⁼

0

^となる

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

reset

⁾

記憶している値を強制的に0にする(クロック信号より

優先

⁾

リセット入力の値を

0

^{にすることにより値を}⁰ ^{にするものが多い}

D

HHHHHHLLLLLHHHHHHLL

CLK

LLHHLLHHLLHHLLL

RST

HHHHHLLLLLLLLHHHHHHHHHH

Q

VVVÆHLLLLLLLLLLLHHHHHH

3. プリセット(

preset

⁾… リセットの反対で,記憶値を強制的に

1

^にする

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

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

Q

Q CLK

D RST

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

(7)

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

⁰ ¹ ⁰ ¹ ¹ ^{· · ·}

(8)

練習問題の解答例

練習7.1

D

HHLHHLLLLLHHHHLLL

CLK

LLHLHLHLHLHLL

RST

LLLLHHHHHHHHHHHHHHHHHHHHHHHHH

Q

VLLLLLLHHHHLLLLLLLLLLHHHH

Q

VÆHHHHHHLLLLHHHHHHHHHHLLLL

Nagisa ISHIURA