2008年7月
「論理回路」 2008 年度定期試験 問題
担当: 石浦 菜岐佐
【注意事項】
• 試験時間は 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) 10進数の93を16進数に変換せよ(結果のみ示せ).
(2) 8ビットの2 の補数表現の2進数10101010を10進数に変換せよ(結果のみ示せ).
(3) (ab+x)(bc+y)(ca+z)(a+b+x)(b+c+y)(c+a+z)を簡単化せよ(結果に至る過程も示せ).
(4) (x⊕a)(x⊕b)⊕ab⊕abxを簡単化せよ(結果に至る過程も示せ).
(5) f(a, b, c) =ab+bc+caが自己双対関数であることを示せ.
(6) g(a, b, c) =ab+c をandとnotだけで表せ．
(7) 論理関数 h(a, b, c, d, e, f) = (ab+c)(d+e) +f を計算する組み合わせ回路を, not ゲートと 2 入力nand ゲートだけを用いて構成せよ. (それ以外のゲートは用いてはならない.)
2 下記の状態遷移グラフで動作が定義されるMealy型順序機械について,次の問いに答えよ. ただし,入力を x,出力をy, zとする. [22点] (7 + 15)
A B
S
C D
0/00
1/00
0/01
0/00 1/00
1/01
0/11
1/11 1/00
0/00
(1) 次のように, 3 ビットの状態変数 a, b, cを用いて状態符号化を行ったとする. 符号化された状態遷移表を作
成せよ(解答用紙の空欄を埋めよ).
【注意】(1)の間違いで(2)が間違っても部分点は与えない．ケアレスミスがないように 良く見直すこと.
a b c
S 0 0 0
A 0 1 0
B 0 1 1
C 1 1 0
D 1 1 1
(2) 3個のDフリップフロップを用いてこの回路を設計する. 状態変数a, b, cに対応するフリップフロップのD
入力をそれぞれda, db, dc とする. da, db, dc, y, zを a, b, c, xの最小積和形で表せ. 必ずdon’t careも考慮す ること. それぞれのカルノー図も併せて示せ(解答用紙に書き込め).
3 次の順序機械の状態数を最小化せよ(結果のみ示せ). [12点]
現状態 次状態/出力
0 1
S1 S3/0 S2/1 S2 S4/0 S6/1 S3 S1/1 S7/0 S4 S2/1 S5/0 S5 S5/1 S4/1 S6 S7/0 S2/1 S7 S6/1 S3/0
2
4 2ビットの2進数の大小比較を行う回路に関する次の問に答えよ. [16点] (4 + 12)
(1) 2つの1ビット入力a,bの大小比較を行う次のような関数g(a, b), e(a, b)を考える. g(a, b)とe(a, b)をa, b の論理式で表せ.
g(a, b) e(a, b)
a > bのとき 1 0
a < bのとき 0 0
a=bのとき 0 1
(2) 2つの2ビット入力(a1, a0), (b1, b0)の大小比較を行う次のような関数G(a1, a0, b1, b0),E(a1, a0, b1, b0)を 考える.
G(a1, a0, b1, b0) E(a1, a0, b1, b0)
2a1+a0>2b1+b0 のとき 1 0
2a1+a0<2b1+b0 のとき 0 0
2a1+a0= 2b1+b0 のとき 0 1
今, g0 =g(a0, b0), e0 = e(a0, b0), g1 = g(a1, b1), e1 = e(a1, b1), とする. このとき, G および E を g1, e1, g0, e0の最小積和形で表せ. GとE のカルノー図と最小積和形を示せ.
【ヒント】下のような真理値表を作成してみよ. 例えば，(g1, e1) = (0,1)は2数の上位ビットが等しいこと を, (g0, e0) = (0,1) は2数の下位ビットが等しいことを表すので, (g1, e1, g0, e0) = (0,1,0,1)の時には2数 が等しくなり,従って(G, E) = (0,1)となる. ドントケアに注意せよ．
g1 e1 g0 e0 G E
0 0 0 0
0 0 0 1
5 [15点]
次のようなMealy順序機械の状態遷移グラフを示せ.
• この回路は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 が入力された状態を S1, 過去2時刻に10 が入力された状態を S10,過去3時刻に101が入力された状態をS101として記憶するのが一案. 例えば，S10で 1が入力されれ ば S101 に, 0が入力されれば初期状態に遷移することになる．
Nagisa ISHIURA
3
