2011
年7
月「論理回路」 2011 年度定期試験 問題
担当: 石浦 菜岐佐
【注意事項】
•
試験時間は80
分で,持ち込みは一切不可である.•
試験開始までこの面を上にして待つこと.•
問題は全部で5
問あり100
点満点である.•
解答用紙の所定の欄に解答せよ.
採点結果閲覧システムと予想得点の記入について
本試験は,採点が終り次第,各自の得点
(各問毎)
をWWW
で閲覧できるようにします.閲覧を希望しない人は
予想得点
/
暗証番号を記入しないで下さい.
見たい人は(1)
解答用紙の「予想得点」欄に各問の予想得点を,
「暗証番号」欄に8
桁の数字を書いて下さい.
こ の情報は閲覧の際に必要になるので,
必ず下に控えをとっておいて下さい.
問題
1 2 3 4 5
暗証番号予想得点
•
暗証番号はWWW
の認証に,予想点数はサーバー上の点数データを暗号化する鍵として用い ます. 他人の点数を見ることはできません.•
予想点数の記入により,
採点上不利/
有利になることはありません.
• “5 5 5 5 5 · · ·”
など意味のないと判断される予想点数を書いた場合は,
記入がなかったものと見なします
(点数は閲覧できません).
(2)
閲覧ページはhttp://ist.ksc.kwansei.ac.jp/∼ishiura/lc/
からリンクします.•
閲覧は8/12(
金)
までです.
•
認証のユーザID
は学籍番号の下4
桁,パスワードは上記の8
桁の暗証番号です.•
認証を通って現れるフォームに予想点数を入力して下さい.•
採点が完了するまでは採点の進捗状況を表示します.
•
セキュリティの問題上,
電子メールでの点数や予想点数等の照会には一切応じません.
1
1
次の問いに答えよ. [35
点] (5 × 7)
【各問完全解答;
部分点なし】(1) 16
進数6D
を10
進数に変換せよ.
(2) 10
進数の−77
を8
ビットの2
の補数表現の2
進数に変換せよ.(3) x + a + b + y + b · x + a + b + y + b
を積和形論理式に変換し,
簡単化せよ(
結果に至る過程も示せ).
(4) ( x ⊕ ab )( x ⊕ bc )( x ⊕ ca ) a
を簡単化せよ(
結果に至る過程も示せ).
(5) F = acd + bcd , G = abc + abd + abcd
のとき,F = G · Q
を満たすQ
の最小積和形論理式を求めよ.(6) g ( a, b, c ) = ab + ca
をand
とexclusive-or (
および1)
だけを用いて表せ(
簡単化する必要はない).
(7)
下記の組み合わせ回路を, nand
ゲートとnot
ゲートのみからなるものに変換せよ(
簡単化する必要はない.) a
b c d e f
x
y g
2
下記の 表1
の状態遷移表で動作が定義されるMoore
型順序機械について,
次の問いに答えよ.
ただし,
入 力をx ,
出力をy , z
とする. また,A
が初期状態であるとする.[25
点] (5 + 4 + 16)表
1
状態遷移表 現状態 次状態 出力x = 0 x = 1 y z
A A B 0 0
B B C 0 1
C C D 1 0
D D E 1 1
E E A 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
(1)
表1
の状態遷移表を状態遷移グラフに変換せよ.
(2) x
に信号値系列1 0 1 1 0 1 · · ·
を入力したときに,z
に出力される 信号値系列を示せ(最初の 7
時刻分 を示 せ).(3)
上記の 表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 , y, z
の論理関数をa, b, c, x
の最小積和形で表せ. 必ず
don’t care
も考慮すること. 解答を得る過程として,符号化された状態遷移表,およびそれぞれの関数のカルノー図も併せて示せ
(
解答用紙に書き込め).
3
次の順序機械の状態数を最小化せよ(
結果のみ示せ). [14
点]
現状態 次状態/出力入力=0 入力=1
S 1 S 2 / 0 S 7 / 0 S 2 S 5 / 1 S 1 / 0 S 3 S 2 / 0 S 6 / 0 S 4 S 5 / 1 S 6 / 1 S 5 S 2 / 0 S 4 / 0 S 6 S 3 / 1 S 4 / 1 S 7 S 1 / 1 S 1 / 1
2
4
次の回路に関して下記の問いに答えよ. [16
点] (4 × 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)
が起こると正しい計算結果は得られない.(1)
全加算器の出力co , s
を入力a , b , ci
の論理式で表せ.
(2) x = 0, a 4 a 3 a 2 a 1 a 0 = 01011
のとき,
オーバフローを起こさないb 4 b 3 b 2 b 1 b 0
のうち表現する値が最大のもの を求めよ.(3) x = 1, a 4 a 3 a 2 a 1 a 0 = 00111
のとき,
オーバフローを起こさないb 4 b 3 b 2 b 1 b 0
のうち表現する値が最小のもの を求めよ.
(4) f v ( x, a 4 , b 4 , s 4 )
は,オーバフローが起こるとき1,
起こらないとき0
となる関数とする.f v ( x, a 4 , b 4 , s 4 )
のオ ンセット表現を示せ.5
下記の表の可変長符号の復号を行うMealy
型順序回路の状態遷移グラフを作成せよ. [10
点]
記号 固定長符号 可変長符号a 001 0
i 010 10
u 011 110
e 100 1110
o 101 1111
この回路は
