2009年7月
「論理回路」 2009 年度定期試験 問題
担当: 石浦 菜岐佐
【注意事項】
• 試験時間は 80分で,持ち込みは一切不可である.
• 試験開始までこの面を上にして待つこと.
• 問題は全部で5 問あり100 点満点である.
• 解答用紙の所定の欄に解答せよ.
bababababababababababababababababababababab
採点結果閲覧システムと予想得点の記入について
本試験は,採点が終り次第,各自の得点(各問毎)を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) 5ビットの2の補数表現の2進数で表現可能な最小数と最大数を10進数で示せ.
(2) 10進数−52を8ビットの2の補数表現の2進数に変換せよ.
(3) (x+y+a)(y+z+b)(z+x+c)(x+a z)(y+b x)(z+c y)を簡単化せよ. (結果に至る過程も示せ).
(4) (a⊕b⊕c)(a⊕bc)を簡単化せよ(結果に至る過程も示せ).
(5) f(x, a, b) =xa+xb+a bが自己双対関数であることを示せ.
(6) g(a, b, c) =a⊕bcをand, or, not演算だけで表せ(簡単化する必要はない).
(7) 下記の組み合わせ回路を, nandゲートとnotゲートのみからなるものに変換せよ. (簡単化する必要はない.) a
b
c f
d
2 下記の 表1 の状態遷移表で動作が定義される Moore型順序機械について, 次の問いに答えよ. ただし,入 力をx,出力をy, zとする. また,Aが初期状態であるとする. [23点] (5 + 18)
表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
(1) 表1 の状態遷移表を状態遷移グラフに変換せよ.
(2) 上記の 表2 のように3ビットの状態変数 a, b, cを用いて状態割当てを行い, それぞれの状態変数に対応す る3個のDフリップフロップDa,Db,Dcを用いてこの回路を設計するものとする. フリップフロップDa, Db,Dc の D入力をそれぞれda, db, dc とするとき,da, db, dc, y, z の論理関数をa, b, c, x の最小積和形で表
せ. 必ずdon’t careも考慮すること. 解答を得る過程として,符号化された状態遷移表,およびそれぞれの関
数のカルノー図も併せて示せ(解答用紙に書き込め).
3 次の順序機械の状態数を最小化せよ(結果のみ示せ). [14点]
現状態 次状態/出力
0 1
S1 S3/0 S5/1 S2 S6/0 S5/1 S3 S8/1 S6/1 S4 S1/0 S6/0 S5 S7/1 S3/1 S6 S8/1 S3/1 S7 S2/0 S3/0 S8 S9/0 S6/0 S9 S1/0 S4/1
2
4 4ビットの加減算回路に関する次の問いに答えよ. [14点] (4 + 10)
この回路は, 2 組の 4 ビット入力 A = (a3, a2, a1, a0) とB = (b3, b2, b1, b0), 制御入力 x と, 4 ビット出力 S= (s3, s2, s1, s0)を持つ. A,B,S は2 の補数表現による符号付き2進数であり,a0,b0, s0が最下位ビットであ る. オーバーフローが起きなければ，この回路は次の計算をする.
制御入力 演算結果
x S
0 A−B
1 A+B
(1) 全加算器(入力a,b,cの 1ビット和sと上位への桁上り c′ を計算する)の出力sとc′ をそれぞれa, b,c の論理式で表現せよ(積和形でなくてもよい;簡単化する必要はない).
(2) この回路を4 つの全加算器と適当な論理ゲートを用いて設計せよ.
5 次のようなMoore型順序回路の状態遷移グラフを示せ. [14点]
この回路は1 ビットの入力xと1 ビットの出力z を持つ. xに過去3時刻(現時刻は含まない)に入力された 値のうち,数の多い方が z に出力されるものとする. ただし,初期状態は, 過去3時刻に0 0 0が入力されていた 状態とする. 例えば,xに 0 1 1 0 0 1 1 1 0 0 1 0 1 1を入力した場合の出力は次のようになる.
時刻 0 1 2 3 4 5 6 7 8 9 10 11 12 13 · · · 入力 x 0 1 1 0 0 1 1 1 0 0 1 0 1 1 · · · 出力 z 0 0 0 1 1 0 0 1 1 1 0 0 0 1 · · ·
※ 過去3時刻に入力された系列を状態として記憶するのが一案. 例えば,過去3時刻に0 0 0が入力された状態 を S000 とし,この状態で0 が入力されればS000 に, 1が入力されればS001に遷移するようにすればよい.
Nagisa ISHIURA
3
