• 検索結果がありません。

1 2013 年度「論理回路」演習問題

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2021

シェア "1 2013 年度「論理回路」演習問題"

Copied!
7
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 7 ページ )

全文

(1)

2013

年

7

月

2013

年度「論理回路」演習問題

石浦 菜岐佐

•

定期試験にはこの演習問題の類題を出題するので,よく勉強しておくこと.

•

解答例を見てもなぜそうなるかがわからない場合は

,

聞きにくること

.

•

問題や解答例に修正があった場合は講義

WWW

に訂正を出すので,疑問に思った場合は確認すること.

• *

は類題で練習用. この他に,講義

WWW

にある過去の出題も解いておくと良い.

1

論理式の計算等に関する問題

(1) < 1

章>

(a) n

ビットの

2

の補数表現の

2

進数で表現可能な最小数と最大数を示せ.

(b) 6

ビットの

2

の補数表現の

2

進数で表現可能な最小数と最大数を

(10

進数で

)

示せ

.

(c) 16

進数

D5

を

10

進数に変換せよ

. (d) 10

進数

123

を

16

進数に変換せよ.

(2) < 1

章>

(a) 8

ビットの

2

の補数表現の

2

進数

11011100

を

10

進数に変換せよ.

(b) 10

進数

−77

を

8

ビットの

2

の補数表現の

2

進数に変換せよ

. (3) < 2

章

>

(a) ( x + a + b )( x + a + b )( x + a + c )( x + a + c )

を簡単化せよ.

(b) * ( x + yz + a )( x + y + z + a )( x + yz + b )( x + y + z + b )( x + yz + c )( x + y + z + c )

を簡単化せよ

. (c) xab + x + b + c · yab + y + b + c

を積和形論理式に変換し,簡単化せよ

(結果に至る過程も示せ).

を積和形論理式に変換し

,

簡単化せよ

(

結果に至る過程も示せ

).

(4) < 3

章

>

(a) ( x ⊕ a )( x ⊕ b )( a ⊕ b )

を簡単化せよ.

(b) * ( a ⊕ b ⊕ c )( a ⊕ b c )

を簡単化せよ

. (c) * ( x ⊕ a )( x ⊕ b ) ⊕ ab ⊕ abx

を簡単化せよ.

(d) a ⊕ b

を

and, or, not

で表せ

.

次に

,

これを用いて

x ( y ⊕ z ) = xy ⊕ xz

が成り立つことを示せ

. (5) < 11

章

>

(a) n

変数論理関数

f ( x

1

, x

2

, · · · , x

n

)

に対し,

f

d

( x

1

, x

2

, · · · , x

n

) = f ( x

1

, x

2

, · · · , x

n

)

と定義される関数

f

dを

f

の双対関数と呼び

, f = f

dであるとき

f

は自己双対関数であると言う

. f ( x, a, b, c ) = xa + xb + xc + abc

が自己双対関数であることを示せ.

(b) n

変数論理関数

f

において

, n

リテラルの論理和で各変数のリテラルを

1

つづつ含むものを最大項とい い,

f

を最大項の論理積で表したものを

f

の和積標準形という.

f ( a, b, c, d ) = a + bc + b d

の和積標準 形を求めよ.

(c) F = acd + abd + abcd , G = ab + bcd + da

のとき,

F = G · Q

が成立する最小積和形論理式

Q

を求めよ.

(6) < 11

章

>

(a) g ( a, b, c ) = ab + c

を

and

と

not

だけで表せ

(

簡単化する必要はない

)

．

(b) g ( a, b, c ) = ab + bc + ca

を

and

と

exclusive-or (および 1)

だけを用いて表せ

(簡単化する必要はない).

(c)

論理関数

f ( x, y, z )

に対し

, f

の

x

による微分を

∂f

∂x = f (0 , y, z ) ⊕ f (1 , y, z )

と定義する

. f ( x, y, z ) = xy + yz

に対し

∂f

∂x

を計算せよ

(簡単化せよ).

(2)

(7) < 4

章

>

(a)

下記の組合せ回路を

, nand

ゲートと

not

ゲートのみからなるものに変換せよ

. (

簡単化する必要はない

.) a

b

c f

d

(b)

論理関数

h ( a, b, c, d, e ) = ( a + bc )( a + cd ) + b ( d + e )

を計算する組合せ回路を, not ゲートと

2

入力

nand

ゲートだけを用いて構成せよ

(

簡単化する必要はない

).

2

順序回路の設計に関する問題

< 7

章, 8章, 9章

>

(1)

下記の 表

1

の状態遷移表で動作が定義される順序回路の設計について, 次の問いに答えよ. ただし, 入力を

x ,

出力を

z

とする

.

また

, A

が初期状態であるとする

.

表

1

状態遷移表 現状態 次状態/

z

出力

x = 0 x = 1 z

A A B 0

B A C 0

C B D 1

D B E 0

E D C 1

表

2

状態割当 状態

a b c

A 0 0 0

B 0 0 1

C 0 1 1

D 0 1 0

E 1 1 0

(a)

表

1

の状態遷移表を状態遷移グラフに変換せよ.

(b) x

に信号値系列

1 1 0 1 1 1 1 · · ·

を入力したときに

, z

に出力される信号値系列

(

最初の

8

時刻分

)

を 示せ.

(c)

上記の 表

2

のように

3

ビットの状態変数

a, b, c

を用いて状態割当てを行い

,

それぞれの状態変数に対 応する

3

個の

D

フリップフロップ

D

a

, D

b

, D

c を用いてこの回路を設計するものとする. フリップフ ロップ

D

a

, D

b

, D

c の

D

入力をそれぞれ

d

a

, d

b

, d

c とするとき

, d

a

, d

b

, d

c

, z

の論理関数を

a, b, c, x

の 最小積和形で表せ

.

必ず

don’t care

も考慮すること

.

解答を得る過程として

,

符号化された状態遷移表

,

およびそれぞれの関数のカルノー図も併せて示せ

(解答用紙に書き込め).

(2)

下記の状態遷移グラフで動作が定義される順序機械の設計について

,

次の問いに答えよ

.

ただし

,

入力を

x, y ,

出力を

z

とする. また,

A

が初期状態であるとする.

状態遷移グラフ

(入力: x y /

出力:

z )

A B C

00/1, 11/0 01/0

00/1

11/1

01/0

00/0, 01/1

11/1

状態割当 状態

a b

A 0 0

B 1 0

C 1 1

(a)

入力

x y

に信号値系列

11 01 01 01 00 11 11

を入力したときに

, z

に出力される信号値系列を示せ

. (

最 初の

7

時刻分を示せ.)

(3)

(b)

上記右表のように

2

ビットの状態変数

a, b

を用いて状態割当てを行うとする. 符号化された状態遷移 表を示せ

.

(c)

状態変数

a , b

をそれぞれ

JK

フリップフロップ

J

a

, J

b で記憶する回路を設計するものとする.

J

a の

J

入力と

K

入力をそれぞれ

j

a

, k

a とし,

J

b の

J

入力と

K

入力をそれぞれ

j

b

, k

b とする. フリップフ ロップの入力関数と出力関数の表を示せ

.

(d) j

a

, k

a

, j

b

, k

b

,

および

z

の論理関数を

a, b, x, y

の最小積和形で表せ. 必ず

don’t care

も考慮すること.

解答を得る過程として

,

それぞれの関数のカルノー図も併せて示せ

.

(3) *

下記の 表

1

の状態遷移表で動作が定義される順序回路の設計について

,

次の問いに答えよ

.

ただし

,

入力

を

x ,

出力を

y , z

とする. また,

A

が初期状態であるとする.

表

1

状態遷移表 現状態 次状態 出力

x = 0 x = 1 y z

A B C 0 0

B C D 0 1

C D E 1 0

D E A 1 1

E A B 1 1

表

2

状態割当 状態

a b c

A 0 0 0

B 0 0 1

C 0 1 1

D 1 1 0

E 1 0 0

(a)

信号値系列

1 0 1 0 0 1 0 · · ·

を入力したときに

,

出力される信号値系列

(

最初の

8

時刻分

)

を示せ

. (b)

上記の 表

2

のように

3

ビットの状態変数

a, b, c

を用いて状態割当てを行うものとする

.

符号化された

状態遷移表を示せ.

(c)

状態変数

a , b , c

をそれぞれ

D

フリップフロップ

D

a

, D

b

, D

c で記憶する回路を設計するものとする

.

フリップフロップ

D

a

, D

b

, D

c の

D

入力をそれぞれ

d

a

, d

b

, d

c とするとき,

d

a

, d

b

, c

c

, y, z

の論理関数を

a, b, c, x

の最小積和形で表せ

.

必ず

don’t care

も考慮すること

.

(d)

状態変数

a , b , c

をそれぞれ

JK

フリップフロップ

J

a

, J

b

, J

c で記憶する回路を設計するものとする.

フリップフロップ

J

a

, J

b

, J

c の

J

入力をそれぞれ

j

a

, j

b

, j

c

, K

入力をそれぞれ

k

a

, k

b

, k

c とするとき

, j

a

, k

a

, j

b

, k

b

, j

c

, k

c の論理関数を

a, b, c, x

の最小積和形で表せ

.

必ず

don’t care

も考慮すること

.

3

次の順序回路の状態数を最小化せよ.

< 8

章

>

(1)

現状態 次状態/出力

0 1

S

1

S

2

/ 0 S

3

/ 1 S

2

S

9

/ 0 S

6

/ 1 S

3

S

7

/ 0 S

4

/ 0 S

4

S

2

/ 0 S

7

/ 1 S

5

S

5

/ 1 S

6

/ 1 S

6

S

6

/ 1 S

5

/ 1 S

7

S

3

/ 0 S

4

/ 0 S

8

S

2

/ 0 S

8

/ 0 S

9

S

9

/ 0 S

8

/ 1

(2) *

現状態 次状態

/

出力 入力=0 入力=1

S

1

S

6

/ 0 S

7

/ 1 S

2

S

7

/ 0 S

5

/ 0 S

3

S

8

/ 1 S

6

/ 0 S

4

S

9

/ 0 S

2

/ 1 S

5

S

4

/ 1 S

9

/ 1 S

6

S

1

/ 0 S

3

/ 1 S

7

S

2

/ 1 S

1

/ 0 S

8

S

3

/ 0 S

5

/ 0 S

9

S

4

/ 1 S

8

/ 1

4

算術回路に関する問題

< 10

章

, 4

章>

(4)

(1) 4

ビットの加減算回路に関する次の問いに答えよ.

この回路は

, 2

組の

4

ビット入力

A = ( a

3

, a

2

, a

1

, a

0

)

と

B = ( b

3

, b

2

, b

1

, b

0

),

および制御入力

( x, y )

と

, 4

ビッ ト出力

S = ( s

3

, s

2

, s

1

, s

0

)

を持つ.

A , B , C

の表現には

2

の補数表現が用いられており,それぞれ

a

0

, b

0

, s

0 が最下位ビットである.

s

には下の表の演算結果が出力されるものとする.

制御入力 演算結果

x y S

0 0 A − B − 1

0 1 A − B

1 0 A + B

1 1 A + B + 1

(a)

全加算器

( a , b , c

を入力とし, 1ビット和

s

と上位への桁上り

c

を計算する)の出力

s

と

c

をそれぞ れ

a , b , c

の論理式で表現せよ

(

どんな論理式でもよい

).

(b)

この加減算回路を

4

つの全加算器と適当な論理ゲートを用いて設計せよ.

(2) 2

ビットの

2

進数の大小比較を行う回路に関する次の問いに答えよ.

2

つの

1

ビット入力

a , b

の大小比較を行う次のような関数

g ( a, b ) , l ( a, b )

を考える

. g ( a, b ) l ( a, b )

a > b

のとき

1 0

a < b

のとき

0 1

a = b

のとき

0 0

2

つの

2

ビット入力

( a

1

, a

0

), ( b

1

, b

0

)

の大小比較を行う次のような関数

G ( a

1

, a

0

, b

1

, b

0

), L ( a

1

, a

0

, b

1

, b

0

)

を考える.

G ( a

1

, a

0

, b

1

, b

0

) L ( a

1

, a

0

, b

1

, b

0

) 2 a

1

+ a

0

> 2 b

1

+ b

0 のとき

1 0 2 a

1

+ a

0

< 2 b

1

+ b

0 のとき

0 1

2 a

1

+ a

0

= 2 b

1

+ b

0 のとき

0 0

今

, g

0

= g ( a

0

, b

0

), l

0

= l ( a

0

, b

0

), g

1

= g ( a

1

, b

1

), l

1

= l ( a

1

, b

1

),

とする

.

このとき

, G

および

L

を

g

1

, l

1

, g

0

, l

0 の最小積和形で表せ.

G

と

L

のカルノー図と最小積和形を示せ.

【ヒント】下のような真理値表を作成してみよ

.

例えば，

(g

1

, l

1

) = (0, 0)

は

2

数の上位ビットが等しいことを

, (g

0

, l

0

) = (0, 0)

は

2

数の下位ビットが等しいことを表すので

, (g

1

, l

1

, g

0

, l

0

) = (0, 0, 0, 0)

の時には

2

数が等しく なり

,

従って

(G, L) = (0, 0)

となる

.

ドントケアに注意せよ．

g

1

l

1

g

0

l

0

G L

0 0 0 0

0 0 0 1

(3)

加算器の設計に関する以下の問いに答えよ

.

下記は

4

ビット加算器の一設計例である. 入力

A = ( a

3

, a

2

, a

1

, a

0

), B = ( b

3

, b

2

, b

1

, b

0

)

および出力

S = ( c

4

, s

3

, s

2

, s

1

, s

0

)

は

,

符号無し

2

進数を表す

(

それぞれ

a

0

, b

0

, s

0 が最下位ビットである

). c

0は最下位桁へ の桁上げ入力であり,

A

と

B

と

c

0 の算術和が

S

に出力される.

FA

は全加算器

(full adder)

であり

, a

と

b

と

ci

の

1

ビット和

s

と上位への桁上げ

co

を計算する

.

(5)

FA s co

a b ci co FA s

a b ci co FA s

a b ci co FA s a b ci a

3

b

3

a

2

b

2

a

1

b

1

a

0

b

0

s

3

s

2

s

1

s

0

c

4

c

3

c

2

c

1

c

0

(a)

全加算器の真理値表を示せ.

(b)

上記の回路と同じ桁上げ信号

c

i を

,

より少ない段数の組合せ回路で生成する「桁上げ生成回路」の設 計について考える

.

· i

桁目から桁上げが生成される条件を表す

g

i を

a

i と

b

i の論理式で表せ.

· i

桁目への桁上げ信号が

i + 1

桁目に伝播する条件を表す

p

i を

a

i と

b

i の論理式で表せ

.

· c

i+1

(0 ≤ i ≤ 3)

を

g

i

, p

i

, c

i の論理式で表せ.

· c

4を

g

0

, g

1

, g

2

, g

3

, p

0

, p

1

, p

2

, p

3

, c

0の論理式で表せ.

(4)

次の回路に関して下記の問いに答えよ

.

FA s co

a b ci co FA s

a b ci co FA s

a b ci co FA s a b ci

a

3

b

3

a

2

b

2

a

1

b

1

a

0

b

0

s

3

s

2

s

1

s

0

c

3

c

2

c

1

x FA s

co a b ci

c

4

c

5

s

4

a

4

b

4

図中の

FA

は全加算器

(full adder)

である. この回路は, 5ビットの

2

の補数表現の

2

進数の加減算を行う 回路であり

,

• x = 0

のときには

a

4

a

3

a

2

a

1

a

0 に

b

4

b

3

b

2

b

1

b

0 を加算した結果

,

• x = 1

のときには

a

4

a

3

a

2

a

1

a

0 から

b

4

b

3

b

2

b

1

b

0 を減算した結果

をそれぞれ

s

4

s

3

s

2

s

1

s

0 に出力する

.

ただし

,

オーバフロー

(overflow)

が起こると正しい計算結果は得られ ない.

(a) x = 0, a

4

a

3

a

2

a

1

a

0

= 00111

のとき

,

オーバフローを起こさない

b

4

b

3

b

2

b

1

b

0 のうち表現する値が最大の ものを求めよ.

(b) x = 0, a

4

a

3

a

2

a

1

a

0

= 10111

のとき,オーバフローを起こさない

b

4

b

3

b

2

b

1

b

0 のうち表現する値が最小の ものを求めよ

.

(c) x = 1, a

4

a

3

a

2

a

1

a

0

= 11110

のとき,オーバフローを起こさない

b

4

b

3

b

2

b

1

b

0 のうち表現する値が最大の ものを求めよ

.

(d) x = 1, a

4

a

3

a

2

a

1

a

0

= 00100

のとき,オーバフローを起こさない

b

4

b

3

b

2

b

1

b

0 のうち表現する値が最小の ものを求めよ.

(e) f

v

( x, a

4

, b

4

, s

4

)

は

,

オーバフローが起こるとき

1,

起こらないとき

0

となる関数とする

. f

v

( x, a

4

, b

4

, s

4

)

の真理値表,およびオンセット表現を示せ.

5

順序回路の状態遷移グラフの設計

< 7

章

, 9

章>

(1)

次のような

Mealy

順序回路の状態遷移グラフを示せ

.

(6)

•

この回路は

1

ビットの入力

x

と

1

ビットの出力

z

を持つ.

•

時刻

t − 3, t − 2, t − 1, t

に

x

にそれぞれ

1, 0, 1, 1

が入力されると

,

時刻

t

に

z

に

1

を出力する

.

そ れ以外の場合の

z

の出力は

0

である. 例えば,

x

に

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

が与えられた場合の

z

の 出力は次のようになる.

時刻

0 1 2 3 4 5 6 7 8 9 10 11 12 · · ·

入力

x 0 1 0 1 1 0 1 1 0 1 0 1 1 · · ·

出力

z 0 0 0 0 1 0 0 1 0 0 0 0 1 · · ·

【ヒント】初期状態を

S,

過去

1

時刻に

1

が入力された状態を

S

1

,

過去

2

時刻に

10

が入力された状態を

S

10

,

過 去

3

時刻に

101

が入力された状態を

S

101として記憶するのが一案

.

例えば，

S

10で

1

が入力されれば

S

101 に

, 0

が入力されれば初期状態に遷移することになる．

(2)

次のような

Moore

型順序回路の状態遷移グラフを示せ

.

この回路は

1

ビットの入力

x

と

2

ビットの出力

( z

1

, z

0

)

を持つ

. x

に

0

または

1

の系列を入力すると

, ( z

1

, z

0

)

に過去

3

時刻

(現時刻は含まない)

に入力された

1

の数を

2

進数

( z

0 が下位ビット)で出力する. 例 えば

, x

に

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

を入力した場合の出力は次のようになる

.

時刻

0 1 2 3 4 5 6 7 8 9 10 11 12 13 · · ·

入力

x 0 0 1 0 1 1 0 1 1 1 1 0 1 1 · · ·

出力

z

1

0 0 0 0 0 1 1 1 1 1 1 1 1 1 · · ·

z

0

0 0 0 1 1 0 0 0 0 0 1 1 0 0 · · ·

【ヒント】 過去

3

時刻に入力された系列を状態として記憶するのが一案

.

例えば

,

過去

3

時刻に

110

が入力され た状態を

S

110とし

,

この状態で

0

が入力されれば

S

100 に

, 1

が入力されれば

S

101 に遷移するようにすればよい

.

(3)

次のような

Moore

型順序回路の状態遷移グラフを示せ.

この回路は

1

ビットの入力

x

と

1

ビットの出力

z

を持つ.

•

初期状態では

0

を出力する

. 1

を連続

3

回入力しない限り

, 0

を出力し続ける

.

• 1

を連続

3

回入力すると,次の時刻以降, 0を連続

3

回入力しない限り

1

を出力し続ける.

• 0

を連続

3

回入力すると

,

次の時刻以降

, 1

を連続

3

回入力しない限り

0

を出力し続ける

.

例えば

, x

に

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

を入力した場合の出力は次のようになる

.

時刻

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 · · ·

出力

z 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 · · ·

入力

x 0 0 1 1 1 0 0 1 0 0 0 0 1 1 0 · · ·

(4)

下記の表の可変長符号の復号を行う

Mealy

型順序回路の状態遷移グラフを作成せよ

.

記号 固定長符号 可変長符号

a 001 1

b 010 01

c 011 0000

d 100 0001

e 101 0010

f 110 0011

この回路は

, 1

ビットの入力

x

と

3

ビットの出力

( y

1

, y

2

, y

3

)

を持つ

.

可変長符号は

x

に

1

ビットづつシリ アルに入力され,符号が認識される毎に

( y

1

, y

2

, y

3

)

に対応する固定長符号の

3

ビットが出力される. 固定長 符号の出力が無い間は

( y

1

, y

2

, y

3

) = (0 , 0 , 0)

が出力されるものとする

.

(7)

Nagisa ISHIURA

参照

今ダウンロードする ( PDF - 7 ページ - 561.09 KB )

関連したドキュメント

1 応募理論問題【解答】 第1問 回路の電気抵抗は一定であり

応募理論問題【解答】 第１問 回路の電気抵抗は一定であり，金属棒とレールの間に摩擦はないものとする。時間とと もに電気抵抗が増加することを考慮する場合と，摩擦がある場合については，付録で定性 的に考察する。 １ 1 レンツの法則を用いる説明aとローレンツ力を用いる説明bがある。 a金属棒を右向きに動かすと，スイッチと平行導体レールおよび金属棒で囲まれた閉

2018 年度 ディジタル回路演習問題（1）

[r]

第 1 回レポート（演習問題 3 ）

数学的内容の理解の為に他者と相談をするのは構わないが，レポートの作成にあたっては他

演習問題 1 （ 2015 年 10 月 7 日）

答案作成に際しては以下の点に注意すること：.

解析学 II （ 2021 年度前期）演習問題 1

解析学 II （ 2021 年度前期）演習問題 1 （解答例）. 注意

解析学 II （ 2021 年度前期）演習問題 3

解析学 II （ 2021 年度前期）演習問題 3 （解答例）. 注意

「論理回路」復習課題

双対原理により, ある等 式が成立すれば, その双対も成立する..

1 2013 年度「論理回路」演習問題解答例

[r]