chapter 2 最近の更新履歴 Hideo Fujiwara

(1)

1 第２章ゲート論理

2

2.1 _{ブール代数}

�ディジタルシステムの基礎となる論理体系は、１９世紀中頃に英国の数学者

ブール（George Boole）が考案したブール代数

��

�

�すくなくとも２つの要素０と１をもつ集合Ｂ上に、

２つの２項演算＋と・および１つの単項演算￣が定義されていて、Ｂの任意の要素_{a, b, c}について、つぎの等式（公理）を満たすとき、

この代数系＜Ｂ_,＋_,・_,￣_,０_,１＞をブール代数という。

演算＋_,・_,￣を各々、ブール和、ブール積、反転と呼ぶ

(2)

3

2.1 _{ブール代数}

（1）ベキ等律 a + a = a a ・a = a

（2）交換律 a + b = b + a a ・b = b ・a

（3）結合律 (a + b) + c = a + (b + c) (a ・b) ・c = a ・(b ・c)

（4）吸収律 a + (a ・b) = a a ・ (a + b) = a

（5）分配律 (a + b) ・c = (a ・c) + (b ・c)

(a ・b ) + c = (a + c) ・(b + c)

（6）対合律

（7）相補律

（8）単位元 1・a = a 0 + a = a

（9）零元 1 + a = 1 0・a = 0

（10）ド・モルガン（DeMorgan）律

a = a

a + a = 1 _a _{! a = 0}

(a + b) = a! b (a! b) = a + b

2.1 _{ブール代数}

（1）ベキ等律 a + a = a a ・a = a

（2）交換律 a + b = b + a a ・b = b ・a

（3）結合律 (a + b) + c = a + (b + c) (a ・b) ・c = a ・(b ・c)

（4）吸収律 a + (a ・b) = a a ・ (a + b) = a

（5）分配律 (a + b) ・c = (a ・c) + (b ・c)

(a ・b ) + c = (a + c) ・(b + c)

（6）対合律

（7）相補律

（8）単位元 1・a = a 0 + a = a

（9）零元 1 + a = 1 0・a = 0

（10）ド・モルガン（DeMorgan）律

a = a

a + a = 1 _a _{! a = 0}

(a + b) = a! b (a! b) = a + b

双対の原理

(3)

3

5

2.1 _{ブール代数}

�^{ブール代数}^＜Ｂ^,^＋^,^・^,^￣^,^０^,^{１＞において、}

集合Ｂ上の任意の値をとる変数をブール変数と呼び、ブール変数と定数０と１に演算＋_,・_,￣を施して得られる式をブール

式という

ブール式で表現する関数をブール関数という

特に、０または１のみをとるブール変数を論理変数といい、その場合のブール式、ブール関数、ブール和、ブール積、反転を、

各々、論理式、論理関数、

論理和（ＯＲ）、論理積（ＡＮＤ）、論理否定（ＮＯＴ）と呼ぶ

6

真理値表

(4)

7

演習問題

�^{ブール代数}の公理より、つぎの等式を示せ。

(1) x + x・y = x + y

(2) x・y + x・z + y・z = x・y + x・z

(3) x ^・ z + y ^・ z = x ^・ z + y ^・ _z

演習問題（解答）

(1) x + x

^・

y _{= x + y}

_左辺 _{= x}

・

_{(1+y) + x}

・

_y

= x + x

^・

^{y + x} ^・ y

= x + (x + x)

^・

_y

_{= x + 1}

・

_y

= x + y

= 右辺

(5)

5

9

演習問題（解答）

(2) x・y + x・z + y・z = x・y + x・z

左辺 = x・y + x・z + (x + x)・y・z

= x ^・ y + x ^・ z + x ^・ y ^・ z + x ^・ y ^・ _z

= x ^・ y ^・ (1+z) + x ^・ z ^・ _(1+y)

= x ^・ y + x ^・ _z

10

演習問題（解答）

(3) x ^・ z + y ^・ z = x ^・ z + y ^・ _z

左辺 _{= x} ・ _z ・ _y ・ _z

= (x + z) ^・ _{(y + z)}

= x ^・ y + x ^・ z + y ^・ z + z ^・ _z

= x ^・ y ^・ (z + z) + x ^・ z + y ^・ _z

= x ^・ y ^・ z + x ^・ y ^・ z + x ^・ z + y ^・ _z

= x ^・ z ^・ (y+1) + y ^・ z ^・ (x+ ₁₎

= x ^・ z + y ^・ z = ^右辺

(6)

11

2.2 _{ディジタル回路}

�入力値、出力値および内部状態の値が

０または１の値の組み合わせとして表現することのできる回路をディジタル回路または論理回路という

論理回路はさらに、組合せ回路と順序回路に分類できる

回路の出力値がそのときの入力値だけにより決まるとき、組合せ回路と呼び、

入力値だけで決まらず回路の内部状態にも依存するとき順序回路と呼ぶ

組合せ回路

�^{各入力に論理変数 x}¹^{, x}²^{, ..., x}ⁿ^, 各出力に論理変数 z

1

, z

2

, ..., z

m

を対応

出力 zi は入力変数 x

1

, x

2

, ..., x

n

, の論理関数

z

(7)

7

13

ゲート

14

等価回路

A + B = A・B

(8)

15

XOR _ゲート

xy

x・xy + y・xy = x・y + x・y

順序回路

内部状態は、そのときの入力と内部状態によってつぎの時刻の内部状態へと変化するこの時刻のタイミングをとるかとらないかにより、

順序回路は同期式順序回路と非同期式順序回路に分類

(9)

9

17

同期式順序回路

18

D _ラッチ

(10)

19

D _{ラッチの動作}

0

1 0

1

0

1 0

1

1 1

1

0

1

0

D _{ラッチの動作}

0

1 0

1

0

1 0

1

1 1

1

0

1

0

(11)

11

21

D _{ラッチの動作}

制御入力Ｃの値が１を持続している間は、

データ入力Ｄの変化が次々とＤラッチに取り込まれてしまう

クロックが１の値をとる時間幅が、

組合せ回路を信号変化が伝播する時間より長くなってしまうと、

フリップフロップの状態がそのクロックの間に２度以上変化することが起こり、正しい状態変化を保証することができなくなってしまう

0

1 1

1

0

1

0

0 1

1 0 ⁰ ¹

22

マスタースレーブDフリップフロップ

クロックＣが１をとる時間が長くても、その間にデータ入力Ｄから取り込んだ値がフリップフロップの出力Ｑに一度に伝播せず、

クロックＣが０になったときにスレーブラッチの出力_Q₂すなわち_Qに伝播するこの動作により、先に述べた誤動作を防ぐことができる

(12)

23

エッジトリガDフリプフロップ

Ｄラッチのようにクロックのレベルで同期せず、

クロックの変化、０から１への立ち上がりや１から０への立ち下がりに同期して、データ入力をフリップフロップに取り込む方法

０から１への立ち上がり（正エッジ）

１から０への立ち下がり（負エッジ）

フリップフロップ

(13)

13

25

2.3 _{組合せ回路の設計}

組合せ回路の設計手順

（１）実現しようとする組合せ回路の機能の仕様を記述する具体的には、入力と出力の対応を記述する

（２）仕様を満たす真理値表を作成する

（３）真理値表の各出力に対応する論理関数の簡単化を行なう

（４）論理図を描く

26

半加算器

半加算器の設計

0 0 0 1

1

S = X Y + X Y = X _{! Y}

C = X Y

(14)

27

全加算器

全加算器の設計

全加算器

C = X Y + X Z + Y Z

S = X Y Z + XY Z + X Y Z + X Y Z ^{S = X}! Y ! Z C = X Y + Z (X ! Y)

(15)

15

29

全加算器

S = X _{! Y ! Z}

C = X Y + Z (X ! Y)

30

並列加算器

(16)

31

デコーダ

(17)

17

33

イネーブル入力付きデコーダ

34

デコーダの合成

(18)

35

エンコーダ

A

0

= D

1

+ D

3

+ D

5

+ D

7 A

1

= D

2

+ D

3

+ D

6

+ D

7 A

2

= D

4

+ D

5

+ D

6

+ D

7

マルチプレクサ

(19)

19

37

マルチプレクサ

38

ROM (Read Only Memory)

(20)

39

PLA (Programmable Logic Array)

2.4 _{順序回路の設計}

順序回路の設計手順

（１）実現しようとする順序回路の機能の仕様を記述する具体的には、状態図（state diagram）で記述する

（２）状態図から状態遷移表（state transition table）を作成し、フリップフロップを用いて状態割当（state assignment）を行なう

（３）順序回路の出力関数およびフリップフロップの入力関数を求め、簡単化を行なう

（４）論理図を描く

(21)

21

41

カウンタ（状態図）

42

カウンタ（状態割当、状態遷移表）

(22)

43

カウンタ（簡単化）

カウンタ D

_Y

0

^{= Y}

0

^{X + Y}

0

^{X = Y}

0

! X

(23)

23

45

カウンタ

D_Y

1^{= Y}¹^Y⁰^{+ X + Y}¹^Y⁰^{X = Y}¹! Y0^X

46

カウンタ

D_Y

2^{= Y}2^Y1^{+ Y}0^{+ X + Y}2^Y1^Y0^{X = Y}2! Y1^Y0^X

(24)

47

カウンタ（論理図）

D_Y₀ = Y₀X + Y₀X = Y₀_{! X}

D_Y

2^{= Y}²^Y¹^{+ Y}⁰^{+ X + Y}²^Y¹^Y⁰^{X = Y}²^{! Y}¹^Y⁰^X

D_Y

1^{= Y}¹^Y⁰^{+ X + Y}¹^Y⁰^{X = Y}¹^{! Y}⁰^X

演習問題

Ｄラッチを用いてマスタスレーブＪＫフリップフロップを設計せよ。

Ｄラッチ D

C

Q Q

D Q(t+1) 0

1

0 1

マスタスレーブ_JKフリップフロップ J

C

Q

JK Q(t+1) 0 0

0 1 1 0 1 1

Q(t) 0 1 Q(t) K

(25)

25

49

演習問題（解答）

D ^Q

Q マスタスレーブ_JKフリップフロップ

J ^Q

Q K

J

K

Q Q

50

演習問題（解答）

D ^Q

Q J

K

Q Q JK Q(t+1)

0 0 0 1 1 0 1 1

Q(t) 0 1 Q(t)

１０００１１１０ K

Q J

D = J K + K Q + J Q

(26)

51

タイミング信号生成

レジスタ

(27)

27

53

RAM (Random Access Memory)

54

RAM (Random Access Memory)

(28)

55

chapter 2 最近の更新履歴 Hideo Fujiwara

1

第２章 ゲート論理

2.1 ブール代数

2.1 ブール代数

a = a

a + a = 1 a ! a = 0

(a + b) = a! b (a! b) = a + b

2.1 ブール代数

a = a

a + a = 1 a ! a = 0

(a + b) = a! b (a! b) = a + b

双対の原理

3

2.1 ブール代数

真理値表

演習問題

(1) x + x・y = x + y

(2) x・y + x・z + y・z = x・y + x・z

(3) x ・ z + y ・ z = x ・ z + y ・ z

演習問題（解答）

(1) x + x

y = x + y

左辺 = x

(1+y) + x

y

= x + x

y + x ・ y

= x + (x + x)

y

= x + 1

y

= x + y

= 右辺

5

演習問題（解答）

(2) x・y + x・z + y・z = x・y + x・z

左辺 = x・y + x・z + (x + x)・y・z

= x ・ y + x ・ z + x ・ y ・ z + x ・ y ・ z

= x ・ y ・ (1+z) + x ・ z ・ (1+y)

= x ・ y + x ・ z

演習問題（解答）

(3) x ・ z + y ・ z = x ・ z + y ・ z

左辺 = x ・ z ・ y ・ z

= (x + z) ・ (y + z)

= x ・ y + x ・ z + y ・ z + z ・ z

= x ・ y ・ (z + z) + x ・ z + y ・ z

= x ・ y ・ z + x ・ y ・ z + x ・ z + y ・ z

= x ・ z ・ (y+1) + y ・ z ・ (x+ 1)

= x ・ z + y ・ z = 右辺

2.2 ディジタル回路

組合せ回路

7

ゲート

等価回路

A + B = A・B

XOR ゲート

xy

x・xy + y・xy = x・y + x・y

順序回路

9

同期式順序回路

D ラッチ

D ラッチの動作

D ラッチの動作

11

D ラッチの動作

マスタースレーブDフリップフロップ

エッジトリガDフリプフロップ

フリップフロップ

13

2.3 組合せ回路の設計

半加算器

全加算器

全加算器

15

全加算器

並列加算器

デコーダ

デコーダ

第２章ゲート論理

2.1 _{ブール代数}

2.1 _{ブール代数}

a + a = 1 _a _{! a = 0}

2.1 _{ブール代数}

a + a = 1 _a _{! a = 0}

2.1 _{ブール代数}

(3) x ^・ z + y ^・ z = x ^・ z + y ^・ _z

y _{= x + y}

_左辺 _{= x}

_{(1+y) + x}

_y

^{y + x} ^・ y

_y

_{= x + 1}

_y

= x ^・ y + x ^・ z + x ^・ y ^・ z + x ^・ y ^・ _z

= x ^・ y ^・ (1+z) + x ^・ z ^・ _(1+y)

= x ^・ y + x ^・ _z

(3) x ^・ z + y ^・ z = x ^・ z + y ^・ _z

左辺 _{= x} ・ _z ・ _y ・ _z

= (x + z) ^・ _{(y + z)}

= x ^・ y + x ^・ z + y ^・ z + z ^・ _z

= x ^・ y ^・ (z + z) + x ^・ z + y ^・ _z

= x ^・ y ^・ z + x ^・ y ^・ z + x ^・ z + y ^・ _z

= x ^・ z ^・ (y+1) + y ^・ z ^・ (x+ ₁₎

= x ^・ z + y ^・ z = ^右辺

2.2 _{ディジタル回路}

XOR _ゲート

D _ラッチ

D _{ラッチの動作}

D _{ラッチの動作}

D _{ラッチの動作}

2.3 _{組合せ回路の設計}

2.4 _{順序回路の設計}

^{= Y}

^{X + Y}

^{X = Y}