第１〜３章（要点）pdf 最近の更新履歴 Hideo Fujiwara

第１章 論理回路の基礎

1.1 _{ブール代数}

�コンピュ タ 基礎と 論理体系 ９世紀中頃 英国 数学者

ブ ル George Boole が考案したブ ル代数

つ 要素 と を含む集合Ｂ上

項演算 ＋と および単項演算 ￣ が定義さ ていて

つぎ 公理を満たす代数系 ＜Ｂ, ＋, , ￣ , , ＞

演算 ＋ ブ ル和 ブ ル積 ￣ 反転

ブール代数の公理

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 ド・モル ン ）eMorgan 律

a = a

a + a = 1

(a + b) = a⋅ b

論理代数

ブール代数  ＜Ｂ, ＋, ・, ￣ , ０, １＞ は 一般に、B = {0, 1, a, b, c, …. }

特に、B = {0,1} の場合，論理代数と呼ぶ

＋  論理和

・  論理積

￣  論理否定 _と呼ぶ

論理和、論理積、論理否定

0 ＋ 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 1

0・0 = 0 0・1 = 0 1・0 = 0 1・1 = 1

0 = 1 1 = 0

＋  論理和

・  論理積

￣  論理否定

普通の代数との違い

論理式、論理関数

論理代数  ＜{0,1}, ＋, ・, ￣ , ０, １＞ において 0,1の値をとる変数を 論理変数

論理変数と0と1に演算 ＋, ・ , ￣ を施して得られる式を論理式 論理式で表現する関数を論理関数

論理関数は論理式で表現される

例えば、多数決関数と呼ばれる論理関数はつぎの論理式

f(x

, x

, x

) = x

x

+ x

x

+ x

x

論理式による表現

積項

和項  

論理和形  

論理積形 x₁x₂x₃

x₁ + x₂ + x₃ x_１x_２x₃ x_１x_２x₃ +

(x_１+x_２+x₃) (x_１+x_２+x₃)

主加法標準形  主乗法標準形

最小項  最大項       あとで説明

論理式による表現

x₁ x_２ x_{３ f} 0 0 0

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

0 0 0 1 0 1 1 1

表１.1 多数決論理関数の真理値表

論理式による表現 （最小項）

x₁ x_２ x_{３ f} 0 0 0

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

0 0 0 1 0 1 1 1

表１.1 多数決論理関数の真理値表

x_１・x_２・x₃

最小項

論理式による表現 （最小項）

x₁ x_２ x_{３ f} 0 0 0

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

0 0 0 1 0 1 1 1

表１.1 多数決論理関数の真理値表

x_１・x_２・x₃

最小項

論理式による表現 （最小項）

x₁ x_２ x_{３ f} 0 0 0

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

0 0 0 1 0 1 1 1

表１.1 多数決論理関数の真理値表

x_１・x_２・x₃

最小項

論理式による表現 （最小項）

x₁ x_２ x_{３ f} 0 0 0

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

0 0 0 1 0 1 1 1

表１.1 多数決論理関数の真理値表

x_１・x_２・x₃

最小項

論理式による表現（主加法標準形）

x₁ x_２ x_{３ f} 0 0 0

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

0 0 0 1 0 1 1 1

主加法標準形 ＝ 最小項の論理和形  最小項

x_１x_２x₃ x_１x_２x₃

x_１x_２x₃ x_１x_２x₃ +

f = + +

デモ： trueLogic

論理ゲート

AND OR _NOT

Q = A•B Q = A＋B Q = A

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

A•B A B

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

A+B A B

0 1 1 0 A A

論理積 論理和 ^論理否定

論理ゲート

NAND NOR XOR

Q = A•B Q = A＋B

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

A•B A B

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

A+B A B

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

A + B A B

Q = A + B 排他的論理和

論理回路

入力値、出力値、内部状態の値が０または１の組合せとして 表現できる回路を論理回路（ディジタル回路）

入力 _内部状態 ^出力

（記憶）

組合せ回路 内部状態（記憶）がない

順序回路 内部状態（記憶）がある

f _{1 とf 2 は等価な論理式？}

f = x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

f = x

+ x

x

二つの論理式を調べてみよう

f _{1 とf 2 は等価な論理式？}

f = x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

f = x

+ x

x

１

x

x

x

f _{1 とf 2 は等価な論理式？}

f = x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

f = x

+ x

x

１

x

x

x

１

f _{1 とf 2 は等価な論理式？}

f = x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

f = x

+ x

x

１

x

x

x

１

１

f _{1 とf 2 は等価な論理式？}

f = x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

f = x

+ x

x

１

x

x

x

１

１

１

f _{1 とf 2 は等価な論理式？}

f = x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

f = x

+ x

x

１

x

x

x

f₁のカルノー図

１

１

１

１

f _{1 とf 2 は等価な論理式？}

f = x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

f = x

+ x

x

１

x

x

x

f₁のカルノー図

１

１

１

１

x

x

x

１

１

１

１

f _{1 とf 2 は等価な論理式？}

f = x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

f = x

+ x

x

１

x

x

x

f₁のカルノー図

１

１

１

１ １

x

x

x

１

１

１

１

f _{1 とf 2 は等価な論理式？}

f = x

+ x

x

１

x

x

x

f₁のカルノー図

１

１

１

１ １

x

x

x

１

１

１

１

f_２のカルノー図

f = x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

f

とf

は等価である！

より小さな論理回路で実現

f

= x

+ x

x

f

= x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

より小さな論理回路で実現

f

= x

+ x

x

f

= x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

回路の大きさは

ANDゲートの個数（積項数） 入力線の総数（リテラル数）

で評価できる

論理式の簡単化

積項数が最小の論理和形を、項数最小論理和形

項数最小論理和形のうちで

リテラルの総数が最小の論理和形を、最小論理和形

f = x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

f = x

+ x

x

積項数=5, リテラル数=15

積項数=2, リテラル数=3

カルノー図による簡単化

１

x

x

x

１

１

１

１

最小項

f = x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

カルノー図による簡単化

ブール代数の公理、分配律、相補律 x•a + x•a = x•(a + a) = x

１

x

x

x

１

１

１

１

x₁x₂x₃ x₁x₂x₃ x₂x₃

x₁•x₂•x₃ + x₁•x₂•x₃ = (x₁ + x₁)•x₂•x₃ = x₂•x₃

隣接するループを併合

カルノー図による簡単化

ブール代数の公理、分配律、相補律 x•a + x•a = x•(a + a) = x

１

x

x

x

１

１

１

１

x₁x₂

x₁x₂ x_１ x₁•x₂ + x₁•x₂ = x₁• (x₂ + x₂) = x₁

隣接するループを併合

カルノー図による簡単化

隣接するループを併合し続ける

これ以上併合できないループ（極大なループ）を 主項と呼ぶ

１

x

x

x

１

１

１

１

x_１ x₂x₃

f = x

+ x

x

f = x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

+ x

x

x

第２章 組合せ回路の設計

組合せ回路の設計手順

 組合せ回路の設計手順

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

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

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

半加算器の設計

半加算器は１ビットの加算を行う回路

　  0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 10

0 0 0 1

1

表2.1 半加算器の真理値表

Sum 和 Carry

桁上げ

0 0 0 1

1

半加算器の設計

表2.1 半加算器の真理値表

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

C = X Y

0 0 0 1

1

半加算器の設計

表2.1 半加算器の真理値表

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

C = X Y

0 0 0 1

1

半加算器の設計

表2.1 半加算器の真理値表

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

C = X Y

0 0 0 1

1

半加算器の設計

表2.1 半加算器の真理値表

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

C = X Y

0 0 0 1

1

半加算器の設計

表2.1 半加算器の真理値表

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

C = X Y

図2.4 半加算器の論理図

全加算器の設計

表2.2 全加算器の真理値表

図2.6 全加算器の論理図

下位ビットからの 桁上げ

上位ビットへの 桁上げ

和

全加算器の設計

表2.2 全加算器の真理値表

図2.5 全加算器のカルノー図

全加算器の設計

表2.2 全加算器の真理値表

図2.5 全加算器のカルノー図

全加算器の設計

表2.2 全加算器の真理値表

図2.5 全加算器のカルノー図

全加算器の設計

表2.2 全加算器の真理値表

図2.5 全加算器のカルノー図

全加算器の設計

表2.2 全加算器の真理値表

図2.5 全加算器のカルノー図

全加算器の設計

表2.2 全加算器の真理値表

図2.5 全加算器のカルノー図

全加算器の設計

表2.2 全加算器の真理値表

図2.5 全加算器のカルノー図

全加算器の設計

表2.2 全加算器の真理値表

図2.5 全加算器のカルノー図

図2.5 全加算器のカルノー図

全加算器の設計

YZ

XZ

XY

C

XYZ

Z

Y

X

Z

Y

X

Z

Y

X

S

+

+

=

+

+

+

=

論理式

Y)

Z(X

XY

C

Z

Y

X

S

⊕

+

=

⊕

⊕

=

論理式の簡単化

S = X _{⊕ Y ⊕ Z}

C = X Y + Z (X ⊕ Y)

全加算器の設計

図2.6 全加算器の論理図

図2.7 ４ビット並列加算器

４ビット並列加算器

デコーダの設計

nビットの信号 A_n-1A_n-2…A₁A₀ が入力されると、そのnビット ２進数に対応する番号の出力線に信号を出す回路

A₀ A₁ A₂

D₀ D₁ D₂ D₃ D₄ D₅ D₆ D₇

デコーダ ^DEC

デコーダの設計

nビットの信号 A_n-1A_n-2…A₁A₀ が入力されると、そのnビット ２進数に対応する番号の出力線に信号を出す回路

D₀ D₁ D₂ D₃ D₄ D₅ D₆ D₇ A₀

A₁ A₂ 1 0

0

0 1 0 0 0 0 0 0 (001)₂ = 1

デコーダの設計

nビットの信号 A_n-1A_n-2…A₁A₀ が入力されると、そのnビット ２進数に対応する番号の出力線に信号を出す回路

D₀ D₁ D₂ D₃ D₄ D₅ D₆ D₇ A₀

A₁ A₂ 1 1

0

0 0 0 1 0 0 0 0 (011)₂ = 3

デコーダの設計

表2.3 ３入力８出力デコーダの真理値表

デコーダの設計

表2.3 ３入力８出力デコーダの真理値表

デコーダの設計

表2.3 ３入力８出力デコーダの真理値表

表2.3 ３入力８出力デコーダの真理値表

デコーダの設計

D₀ = A₂ A₁ A₀

表2.3 ３入力８出力デコーダの真理値表

デコーダの設計

D₁ = A₂ A₁ A₀

表2.3 ３入力８出力デコーダの真理値表

デコーダの設計

D₂ = A₂ A₁ A₀

表2.3 ３入力８出力デコーダの真理値表

デコーダの設計

D₃ = A₂ A₁ A₀

表2.3 ３入力８出力デコーダの真理値表

デコーダの設計

D₄ = A₂ A₁ A₀

表2.3 ３入力８出力デコーダの真理値表

デコーダの設計

D₅ = A₂ A₁ A₀

表2.3 ３入力８出力デコーダの真理値表

デコーダの設計

D₆ = A₂ A₁ A₀

表2.3 ３入力８出力デコーダの真理値表

デコーダの設計

D₇ = A₂ A₁ A₀

図2.8 ３入力８出力デコーダの論理図 68

デコーダの設計

D₀ = A₂ A₁ A₀ D₁ = A₂ A₁ A₀ D₂ = A₂ A₁ A₀ D₃ = A₂ A₁ A₀ D₄ = A₂ A₁ A₀ D₅ = A₂ A₁ A₀ D₆ = A₂ A₁ A₀ D₇ = A₂ A₁ A₀

マルチプレクサの設計

多数の入力線の中から１つの入力線を選択し、その入力線の信号を 出力線に伝える回路をマルチプレクサと呼ぶ、セレクタとも呼ぶ

Y D₀

D₁ D₂ D₃

マルチ プレクサ S₁ S₀

MUX

マルチプレクサの設計

Y D₀

D₁ D₂ D₃

MUX

S₁ S_{0 S}

1 ^S0 ^Y

0 0 0 1 1 0 1 1

D₀ D₁ D₂ D₃

マルチプレクサの設計

Y D₀

D₁ D₂ D₃

MUX

S₁ S_{0 S}

1 ^S0 ^Y

0 0 0 1 1 0 1 1

D₀ D₁ D₂ D₃

Y = S₁ S₀ D₀ + S₁ S₀ D₁ + S₁ S₀ D₂ + S₁ S₀ D₃

マルチプレクサの設計

Y D₀

D₁ D₂ D₃

MUX

S₁ S_{0 S}

1 ^S0 ^Y

0 0 0 1 1 0 1 1

D₀ D₁ D₂ D₃

Y = S₁ S₀ D₀ + S₁ S₀ D₁ + S₁ S₀ D₂ + S₁ S₀ D₃

マルチプレクサの設計

Y D₀

D₁ D₂ D₃

MUX

S₁ S_{0 S}

1 ^S0 ^Y

0 0 0 1 1 0 1 1

D₀ D₁ D₂ D₃

Y = S₁ S₀ D₀ + S₁ S₀ D₁ + S₁ S₀ D₂ + S₁ S₀ D₃

マルチプレクサの設計

Y D₀

D₁ D₂ D₃

MUX

S₁ S_{0 S}

1 ^S0 ^Y

0 0 0 1 1 0 1 1

D₀ D₁ D₂ D₃

Y = S₁ S₀ D₀ + S₁ S₀ D₁ + S₁ S₀ D₂ + S₁ S₀ D₃

75

マルチプレクサの設計

図2.11 ４入力マルチプレクサ

Y = S₁ S₀ D₀

+ S₁ S₀ D₁ + S₁ S₀ D₂ + S₁ S₀ D₃

第３章 順序回路の設計

順序回路の構成

図_3.1 順序回路の構成

順序回路の構成

図_3.2 ッ パ 図_3.3 同期式順序回路の構成

クロックパルスで 時間を刻む 時刻を知らせる

順序回路の構成

図_3.2 ッ パ 図_3.3 同期式順序回路の構成

クロックで同期する記憶素子 フリップフロップ

D _{フリップフロップ}

図_3.8 　制御入力を含 _D ッチ

0

1 0

1

1

0

1 0

1

1 1

1

0

0

1

0

D _{フリップフロップ}

0

1 0

1

1

0

1 0

1

1 1

1

0

0

1

0

D _{フリップフロップ}

0

1 0

1

1

D _{フリップフロップ}

Q Q D

C ッ

3.3 _{順序回路の設計例}

Z_０ ３ビットカウンタ X

Z₂ Z₁

X から入力される１の個数を３ビット２進数で表示する 000→001→010→011→100→101→110→111

3.3 _{順序回路の設計例}

図_3.12 　 ビッ カウンタ

Z_０ ３ビットカウンタ X

Z₂ Z₁

000

001

010

011 100

101 110

111

3.3 _{順序回路の設計例}

表_3.5 　 ビッ カウンタの状態遷移表

表_3.4 　状態割当

87

3.3 _{順序回路の設計例}

3.13 D

88

3.3 _{順序回路の設計例}

D

0

^{= Y}

^{X + Y}

^{X = Y}

^{⊕ X}

3.13 D

89

D_Y

1 ^{= Y1 Y0 + X + Y1Y0X = Y1 ⊕ Y0X}

3.3 _{順序回路の設計例}

3.13 D

90

D_Y

2 ^{= Y2 Y1 + Y0 + X + Y2Y1Y0X = Y2 ⊕ Y1Y0X}

3.3 _{順序回路の設計例}

3.13 D

91

D_Y

0 ^{= Y0X + Y0X = Y0 ⊕ X}

D_Y

2 ^{= Y2 Y1 + Y0 + X + Y2Y1Y0X = Y2 ⊕ Y1Y0X}

D_Y

1 ^{= Y1 Y0 + X + Y1Y0X = Y1 ⊕ Y0X}

3.3 _{順序回路の設計例}

3.14

3.3 _{順序回路の設計例}

図_3.15 　タイミン 信号の生成

3.3 _{順序回路の設計例}

図_3.15 　タイミン 信号の生成

0

0 ^{1 0}

0 0

0 0

T₀ = 1

3.3 _{順序回路の設計例}

図_3.15 　タイミン 信号の生成

1

0 ^{0 1}

0 0

1 0

T₁ = 1

3.3 _{順序回路の設計例}

図_3.15 　タイミン 信号の生成

0

1 ^{0 0}

1 0

0 1

T₂ = 1

3.3 _{順序回路の設計例}

図_3.15 　タイミン 信号の生成

1

1 ^{0 0}

0 1

1 1

T₃ = 1

97

3.3 _{順序回路の設計例}

3.16

図_3.17 　 タ

3.3 _{順序回路の設計例}

図_{3.18 　RAM}の ッ 図 RAM

Random Access Memory

99

3.3 _{順序回路の設計例}

図_3.19 　 ビッ _{× 語 RAM}

図_3.20 　記憶セ

100

3.3 _{順序回路の設計例}

図_3.19 　 ビッ _{× 語 RAM}

図_3.20 　記憶セ 0

1 0

1

0

1 _{1 1}

1

書 込

１

書 込

０

101

3.3 _{順序回路の設計例}

図_3.19 　 ビッ _{× 語 RAM}

図_3.20 　記憶セ １

1 0

1

0 1

1 ０

０

読 出し

１

１ １

読 出し

１

3.3 _{順序回路の設計例}

ア を

設定

ータを 設定

書 込

3.3 _{順序回路の設計例}

ア を

設定

読 出し

ータ

読 出された