2019 年度ディジタル代数期末試験解答例 再評価試験は期末試験と同程度の難しさである. しっかり準備して受けるように. 1. アドレスが 4 バイトで表わされた画像処理専用プロセッサが幾つかのデータを吐き出して停まってしまった. そのデータの 1 つはレジスタ R0 の中身で,16 進表示すると (BD80) 16 であった. このデータに関して, 以下の問に対する回答を対応する箱内に書け. (1) この専用プロセッサの 1 語は何バイトか. 右の箱内に書け.(5 点 ) レジスタの中身が 16 進 4 桁であるから,16 進 1 桁は 4 ビットなので, レジスタは 16 ビットである. 従って, (1) 2 バイト (2) このプロセッサがチップ内に持っているキャッシュメモリの総ビット数は 2 30 ビットであるとき, その大き さは全論理アドレス空間中の何パーセントに当たるか. 有効数字 3 桁で答えよ.(5 点 ) アドレスは 4 バイト, すなわち 32 ビットで表わされているから, 全論理アドレス空間のアドレスの個数は 2 個あり,1 アドレスに 2 バイト, すなわち 16 = 2 ビットあるから, 全論理アドレス空間のビット数 2 2 = 2 である. 従って, 総ビット数 2 30 のキャッシュメモリの割合は,2 100 2 = 100 2 = 100 64 = 1.562 である から, (2) 1.56 % (3) このデータ (BD80) 16 の 2 の補数を 16 進表示せよ.(5 点 ) (BD80) 16 を 2 進表示すると,(1011 1101 1000 0000) 2 であるから, この数の 2 の補数は,(0100 0010 1000 0000) 2 である. 従って, これを 16 進表示すると, (3) ( 4 2 8 0 )16 (4) レジスタ R0 の中身は 2 の補数表現された 2 進整数の和のはずであるが, オーバーフロウが生じていた. そこで, 正 しい和を求めるために, 以下の推理を行った. 下記の a ~ d および f に適切な数を,e には 負 あるいは 非負 を入れ, 文章を完成させよ.( 全 10 点.f は 5 点 ) レジスタ R0 が数 x と y の和 x+y を示すものとし, 数値ビットからの桁上げを Cv, 符号ビットからの桁上げを Cs と 書く. 今,Cv が 0 だと仮定すると, オーバーフロウが生じていることから,Cs は (a) となる. しかし,R0 の MSB が (b) であるから,Cv が 0 のとき R0 の MSB と Cs がこのような値を取ることはない. 従って,Cv は 1 であり, オ ーバーフロウが生じていることから,Cs は (c) である. そうすると,x および y の MSB は共に (d) でなければな らず,x と y は共に (e) で,x+y の正しい和は 8 進表示すると (f) であることが分かる. 以下であれば, 筋が通る. (4) (a) ( 1 ), (b) ( 1 ), (c) ( 0 ), (d) ( 0 ), (e) ( 非負 ), そうすると, 和 x+y は 2 進 17 ビットで正しく表示でき, それは,(0 1011 1101 1000 0000) 2 である. 従って, これを 8 進表示すると,(01 011 110 110 000 000) 2 と表すことにより, 下記となる. (f) ( 1 3 6 6 0 0 )8
(5) このデータ (BD80) 16 が 2 進浮動小数点数で, 最上位ビットは符号を表し, その下に続く 7 ビットは指数部を, 下 8 ビットは仮数部の小数部を表すとき, これはどのような 10 進数か. なお, 指数部はバイアスが 2 1 のゲタバキ方式 の数であり, 仮数部は 1/2 以上 1 未満に正規化されている.(5 点 ) (BD80) 16 を 2 進表示すると,(1011 1101 1000 0000) 2 であるから, 符号は 1 で負の数で, 指数部は (011 1101) 2 であるから, 指数は, 011 1101 2 1 = 011 1101 011 1111 = 000 0010 = 2 である. 一方, 仮数部が (1000 0000) 2 であるから, 仮数は 0.1 = 0.5 である. 従って,2 進浮動小数点数は 0.1 2 である. これより, 0.1 2 = 0.001 = 0.125 と分かる. 0.5 2 = 0.125 と計算しても良い. (5) ( 0.125 )10 2. 下図に示す回路の出力 z を入力 x, y の最簡な積和形論理式で表し, 右下に書け. その際, 論理変数 z, a, b などの真理値表を 下に書いておくこと.(10 点 ) x y z a b 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 1 1 1 1 0 積和形論理式 Z = x y x y 入力 x, y の各値の組に対して,a および b の値を上の真理値表に書く.z が出力の NOR ゲートの入力は b と a z であるが,1 は NOR の制御値であるから,b が 1 の場合,z は必ず 0 となる.b が 0 の場合,z の値はもう一方の入力 a z の値で決まるが,b が 0 の場合,a は 1 であるので,a z の値は 0 である. 従 って,b が 0 の場合,z が出力の NOR ゲートの入力は共に 0 なので,z は 1 となる. 従って, 上に示した z の真理値表が得られる. これより, 上の積和形論理式を得る. 3. 4 ビットの情報記号 (a 1, a 2, a 3, a 4) に 3 ビットの検査記号 (c 1, c 2, c 3) を付加し,7 ビットのハミング符号を生成 するための回路が, 下図のように途中までできている. これに最小個数の論理ゲートと配線を追加し,3 ビッ トの検査記号 (c 1, c 2, c 3) を生成せよ. ただし,c 3 は a 1, a 2, a 3, a 4 だけを用いて定めるものとし, 使用可能な論理ゲートは NAND ゲートと XOR ゲートだけである.(10 点 ) 上の回路図より,c = a a a a a および c = a a a a a であることが分かる. そこで,x = a a a a を計算してみると,x = a a a a = a a a a = a a を得る. 従って,c = a a a および c = a a a は, それぞれ a, a, a および a, a, a に対する偶数パ リティビットであることが分かる. また,c は c = a という式で生成しているから, 問題はこの を導く最簡な式を見出せば解ける.
そこで, 各検査記号が調べている情報記号をリストすると, 右上の表の黒丸のようになる. 各情報記号お よび検査記号に対してできる丸のパターンを異なるようにすれば,1 ビットの誤り訂正符号 ( ハミング符号 ) ができる. 従って,c は a, a, a に対する偶数パリティビットとすれば良いことが分かる. すなわち,c を,c = a a a で生成すれば良い. 従って, = a a とすれば良いから,XOR ゲート 1 個を付加す ることにより, 回路を完成させることができる.( 図は省略する ) 4. 出力が x, y, z, w = x z x w と表せる組合せ回路において,G x, y, z, w = x y z z y w = 0 となるような値の組が don t care であるとき, 下に示したマス目を用いて x, y, z, w のカルノー図を描き, x, y, z, w を最簡な積和形論理式で表すと共に, x, y, z, w を出力する組合せ回路を NAND ゲートのみで実現し, 右下に図示せよ. ( カルノー図 4 点, 論理式, 回路図各 3 点 ) G x, y, z, w = x y z z y w = x y x z z w y w = 0 となる値の組は,G x, y, z, w = 1 となる値の組以外の組である. そこで,G x, y, z, w = x y x z z w y w のカルノー図を描くと, 左下のようになるから,0 となる値の組が don t care である. それを右下のカルノー図に * で書いておく. このカルノー図に, x, y, z, w = x z x w の値を書く. その際,don t care のところには書かない. このカルノー図より, 最簡な積和形論理式は, = x z z w と書ける. 5. 入力 x に対して, 下の状態遷移表で表されるような状態遷移をし,z を出力する順序回路を設計したい. 今, 状態 A, B, C を, 状態変数 p, q を用いて右下の状態割り当て表のように表したとき, 以下の問に答えよ. 回 答を導く際,1 枚目の問題用紙の裏に描かれているマス目を利用して, カルノー図を描いておくこと.( カルノー図各 3 点 ) < 注意 > この問題は, カルノー図で間違うと, 後の全てが間違ってしまう. カルノー図の正しさを検証してから解 答を進めなければならない! 現状態次状態出力 z 状態変数状態入力 x 0 1 0 1 p, q A B A 1 1 A 0, 1 B C A 1 1 B 1, 0 C A A 0 1 C 1, 1 (1) 状態変数 p, q の次状態の値 p, q を表す状態遷移関数を最簡な和積形論理式で表わし, 下に書け.( 論理式各 4 点 ) (2) 出力関数を最簡な和積形論理式で表わし, 下に書け.( 論理式 4 点 ) 上の状態遷移表および出力表より, 論理変数を用いた状態遷移表および出力表を書くと, 下表となる.
現状態 p, q 次状態 p, q 出力 z 入力 x 0 1 0 1 0, 1 1, 0 0, 1 1 1 1, 0 1, 1 0, 1 1 1 1, 1 0, 1 0, 1 0 1 これより,p,q, および z のカルノー図を描くと下記になる. 従って, これらより最簡な和積形論理式が以下のように導かれる. p = x p q = x p q = x p q q = x p = x p = x p q = x p q (3) D フリップフロップ, インバータ,2 入力 NOR ゲートだけを用いてこの順序回路を実現し, その回路図を 1 枚目の問題用紙の裏に示した D フリップフロップの図を用いて図示せよ. ただし,D フリップフロップは初期化回路を持たな いので,reset = 1 のとき状態を初期状態 A にする初期化回路も, インバータと 2 入力 NOR ゲートだけで構成し, 付 加すること.(9 点 ) 初期状態が A = (0,1) であるので,p を保持する DFF の入力 d p および q を保持する DFF の入力 d q は, それぞれ reset = 1 のときには,d p = 0 および d q = 1 でなければならず,reset = 0 のときには,d = D = x p q および d = D = x p でなければならない. 従って,d および d を次式で決定すればよい. d = reset D, d = reset D 従って, これらを NOR 演算を用いて書くと, d = reset D = reset D, ここで,D および D はそれぞれ下記である. d = reset D = reset D D = x p q = x p q, D = x p = x p DFF の入力 ( 状態遷移回路 ) は全て 2 入力 NOR とインバータで実現できるが, 出力を 2 入力 NOR で実現するには, 式を変形しておく方がよい.x,p,q を下記のように分けるのは 1 つの方法である. 他にもある. = x p q = x p q = x y = p q = p q 回路図は省略する. (4) この順序回路はどのような動作をする回路か, 状態遷移図を右下に図示し, その動作を以下で説明せよ.( 状態遷移図 3 点, 説明 7 点 ) 上の状態遷移表および出力表から状態遷移図を描くと右のようになる.
そこで, 初期状態が A で, 出力が 0 になるのが 1 カ所であることに気が付けば, 出力が 0 になるのは,0 が 3 回連続して入力された場合だけであることが分かる. 従って, この回路は, 0 が 3 回連続して入力されない限り 1 を出力し続け,0 が 3 回連続して入力されたときにのみ 0 を出力する回路で,0 が 4 回連続して入力されても,4 回目の 0 は新たな 1 回目の 0 とする ものであると言える.