2016年度期末試験問題と解答例

2016 年度ディジタル代数期末試験解答例
１． 16 進表現で (C3A8)16 と表される 2 バイトの数は，下記の表現では，10 進でどのような数か，下の枠内に書け．
(i) 符号絶対値表現の 2 進数で，下位 8 ビットは小数部．
<解答例>
16 進表現で (C3A8)16 と表される数は，2 進表現では (1100 0011 1010 1000)2 と表される．
最上位ビット（MSB）が 1 なので，負の数であり，絶対値は，下位 8 ビットが小数部なので，次の数となる．
(1100 0011 1010 1000)2 = 26 + 21 + 20 + 21 + 23 + 25 = 64 + 2 + 1 + 0.5 + 0.125 + 0.03125 = 67.65625
従って，67.65625 である．
(ii)
最上位ビットが符号，それに続く 7 ビットが指数部の 2 進浮動小数点数．指数部はバイアスが 261 のバイア
ス指数で，下位 1 バイトの仮数部は，IEEE の標準方式のように，非零の数の場合，1 以上 2 未満に正規化され，整
数部の 1 を省いた小数部を表す．
<解答例>
2 バイト (1100 0011 1010 1000) の最上位ビット（MSB）が 1 なので，この数は負の数である．
指数部の 7 ビット (100 0011) は，バイアスが 261 = (100 0000)2 1 であるから，(100 0011)2  (100 0000)2 1
(0100)2 = (4)10 を表している．さらに，仮数は，整数部の 1 が省かれているので，(1. 1010 1000)2 である．従って，
この 2 進浮動小数点数は次の数を表している．
(1. 1010 1000)2 24 = (1 1010. 1000)2 = (24 + 23 + 21 + 21) = 16 + 8 + 2 + 0.5 = 26.5
２．複数の家電製品を制御するリモコンの開発を命じられた A さんは，旧型の家電製品のリモコンに使われていた 1 語 2 バイ
トのマイクロプロセッサと，5cm10cm のタッチパネルを用いて実現する方法を検討している．何故なら，旧型のリモコン用
プログラムの入った総ビット数が 216 ビットの ROM を利用し，開発コストを少なくしたいからである．このマイクロプロセッサ
のメモリアドレス（番地）は 2 バイトで表されており，ROM の仕様書には，ROM の番地は 0 番地からとし，(ROM 内の最終
番地)＋1 番地から始まる番地を持つ RAM の最初の 1,024 語分のメモリは，この ROM のプログラムが使用すると書かれて
いる．従って，新たに作成するプログラムは，この部分のメモリを使用できない．このとき，以下の問に答えよ．回答は回答
欄に書け．
(i) このマイクロプロセッサの相対 jump 命令は，program counter に入っているアドレス（その jump 命令の次の命令が入
っているアドレス）APC に，その命令の下位 1 バイトに入っている数（2 の補数表現された数）BJ を加算したアドレス
APC+BJ を program counter に入れる．すなわち，その番地 APC+BJ に jump する．今，相対 jump 命令の下位１バイト
が (D7)16 で，その命令実行時の program counter に (8E4B)16 が入っているとき，相対 jump 命令が jump する先の
番地を 16 進数で書け．
<解答例>
2 の補数表現された下位１バイトが (D7)16 であるから，これは (1101 0111)22C = (0010 1001)2 でなる数である．
従って，これを program counter に入っている数 (8E4B)16 = (1000 1110 0100 1011)2 に加算すると，下記の数とな
る．
(1000 1110 0100 1011)2 (0010 1001)2 = (1000 1110 0010 0010)2 = (8E22)16
この加算（引き算）は，2 の補数を加算することによって実行することができるが，その際，ビット数を揃えておか
ねばならない．すなわち，2 の補数表現された１バイトの数 (D7)16 は，番地と同じ 2 バイトにすると，(FFD7)16 で
あるから，これをプログラムカウンタの数 APC に加算することにより，APC+BJ を計算することもできる．
(8E4B)16 + (FFD7)162C = (1000 1110 0100 1011)22C(1111 1111 1101 0111)22C
この加算を実行し，最上位ビットからの桁上げを無視すると，(1000 1110 0010 0010)2 = (8E22)16 を得る．
(ii)
開発したリモコンに総ビット数が共に 216 ビットの ROM と RAM を 1 個ずつ実装したとき，実際に実装されて
いるメモリは，全論理アドレス空間中の何パーセントになるか．
<解答例>
2 バイトのアドレスで表される全アドレスの個数は，216 であり，各アドレスには 2 バイト = 16 ビット = 24 ビット入っ
ているので，全論理アドレスに含まれる総ビット数は，21624 = 220 ビットである．従って，216 ビットのメモリは，1 個
当たり，216/220 = 1/24 = 1/16 の割合であるから，ROM と RAM が各１個入っているので，メモリの割合は，
1/8 = 12.5% である．
(iii) ROM 内の最終番地を 16 進数で書け．また，RAM 内で，新たに作成するプログラムが使用できるメモリの
先頭番地を，16 進数で書け．
<解答例>
各アドレスには 24 ビット入っているので，216 ビットの ROM で構成できるアドレスの総数は，216/24 = 212 アドレス
である．従って，0 番地から始まると，最終番地は 212 1 番地であるから，これを 2 進数で表してから，16 進に変
換すると，(1 0000 0000 0000)2 1 = (0 1111 1111 1111)2 = (0FFF)16 = (FFF)16 である．
また，RAM の先頭番地は，(ROM 内の最終番地)＋1 番地から始まるので，その番地は (1000)16 であり，そこ
から 1,024 = (100 0000 0000)2 = (400)16 語分のメモリが使えないので，使用可能なメモリの先頭番地は，(1000)16 +
(400)16 = (1400)16 である．
(iv) このマイクロプロセッサで，2 の補数表現された 1 語の整数の加算を実行したとき，その結果が 10 進数で 2048 の
ように読めたが，オーバーフロウが生じていた．正しい和は幾つか 10 進数で書け．
<解答例>
2 の補数表現された数が 2048 と読めたということは，2048 = (1000 0000 0000)2 であるから，2 つの数 x と y の
和 x+y のビット系列は，2048 = (1111 1000 0000 0000)22C であり，MSB は負の数を表す 1 になっている．また，オ
ーバーフロウが生じていることの必要十分条件は，数値ビットからの桁上げ C15 と，符号ビットからの桁上げ C16 が
異なることであるから，C15 が 0 だと仮定すると，オーバーフロウが生じていることから，C16 は 1 になっているはず
である．
しかし，C15 が 0 のときに和 x+y の MSB が 1 になるには，x の MSB あるいは y の MSB のいずれか一方のみが
1 でなければならない．そうすると，C16 は 0 になり，1 であることに矛盾する．従って，C15 は 0 でなく，1 であり，C16
は 0 である．
そうすると，C15 = 1, C16 = 0 となるのは，x および y が共に負の数で，和が 2 バイトで表現できる範囲を超えた場
合であることが分かる．なお，オーバーフロウが生じていて，和が負の数のように読めた場合には，正の数の加算
において，表現可能な数を超えた場合であることを知っていれば，上のような議論を省くこともできる．
C15 = 1, C16 = 0 の場合，和 x+y は 17 ビット用いれば， (0 1111 1000 0000 0000)22C と書ける．従って，x+y の正
しい和は，下記である．
(0 1111 1000 0000 0000)22C = (1 0000 0000 0000 0000)2 (1000 0000 0000)2 = 216  211 = 65536 2048 = 
３． 4 ビットの情報記号 (a1, a2, a3, a4) に 3 ビットの検査記号 (c1, c2, c3) を付加した 7 ビットのハミング符号を構成す
るため，検査記号 c1，c2，および c3 を生成する組合せ回路を下図のように構成中である．なお，図に描かれてい
る論理ゲートはこの回路以外でも利用するため，全て必要なものである．この回路を完成させるため，c3 を生成
する論理式を，c1 および c2 は用いず，XOR 演算を用いて書け．また，下図に適切な論理ゲートを付加し，回路を
完成させよ．ただし，XOR ゲートは用いず，付加する論理ゲートの個数を最小にせよ．
<解答例>
与えられた回路より，c1 および c3 はそれぞれ次式で与えられる．
c1 = (a1 a2 )a3 = a1 a2 a3 ，
c2 = (a1 a2 )a4 = a1 a2 a4
従って，共に偶数パリティの検査記号であり，それぞれ右図の行 P123 および P124 の黒丸が書かれたビットの 1 の個数
を偶数にしていることが分かる．そこで，c3 が検査すべきビットを考えると，c2 あるいは c3 は用いないならば，下図の
行 P に書かれているように， a3，a4，c3，および a1 あるいは a2 のいずれかを検査するようにすればよい．すなわち，こ
れにより，a1, a2, a3, a4 および c1, c2, c3 のいずれかにおいて誤りが生じたとき，P123，P124 および P が異なるパターンで誤
りを検出し，誤りの箇所を特定できる．従って，c3 を
次式のどちらかで決定すれば 7 ビットの単一誤り
訂正符号が生成できる．
c3 = a1 a3 a4
あるいは
c3 = a2 a3 a4
a1
a2
a3
P123
●
●
●
P124
●
●
P
X
X
a4
c1
c2
c3
●
●
●
●
●
●
今，a1 ∙ ̅̅̅
a3 + a̅1 ∙ a3 および ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
a1 ∙ ̅̅̅
a3 + a̅1 ∙ a3 を
生成する回路はできており，
a1 ∙ ̅̅̅
a3 + a̅1 ∙ a3 = a1 a3 ，
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
a1 ∙ ̅̅̅
a3 + a̅1 ∙ a3 = ̅̅̅̅̅̅̅̅
a1 a3
であるから，c3 = a1 a3 a4 を用い，
c3 = a1 a3 a4 = (a1 a3 )a4 = (a1 a3 ) ∙ ̅̅̅
a4 + ̅̅̅̅̅̅̅̅
a1 a3 ∙ a4
と変形すれば，c3 を AND-OR 2 段回路で構成できるので，AND ゲートを 2 つ，OR ゲートを 1 つ付加すれば，回路を
完成できる．回路図は省略する．
４．右図の回路の出力 z を入力 x, y の最簡な積和形論理式で表し，下に書け．そ
の際，図の右に真理値表を書いておくこと．
<解答例>
今，右図のように，下の NOR ゲートの出力を A とすると，A の値は，右の表
のようになる．A = 0 の場合，0 は NAND の制御値であるから，もう一方の入力
の値に関わらず z = 1 となる．
また，A = 1，すなわち x = y = 0 の場合には，上の NAND ゲートの出力は，
x = 0 であるから，z の値に関わらず 1 となる．従って，下の NAND ゲートの入
力は共に 1 となるので，z = 0 となる．それ故，z の真理値表は右のようになるか
ら，z は次式で書ける．
𝑓 =x+y
x
z
y
A
ｘ，ｙ
0, 0
0, 1
1, 0
1, 1
z
0
1
1
1
A
1
0
0
0
５．下に示す回路が右の真理値表に示すような値 f を出力するには，d を出力する部分回路をどのように構成すれば良いか．
出力 d のカルノー図を問題用紙 1 枚目の裏のマス目を利用して示し，d を最簡な積和形論理式で表すと共に，NAND ゲ
ートだけを用いた回路を下の破線で囲まれた長方形内に描け．
ｘ，ｙ，ｚ，ｗ
0, 0, 0, 0
0, 0, 0, 1
0, 0, 1, 0
0, 0, 1, 1
0, 1, 0, 0
0, 1, 0, 1
0, 1, 1, 0
0, 1, 1, 1
<解答例>
回路図より，a = 1 であるならば，b の値に関わらず f = 1 となるから，
a = (̅̅̅̅̅
x ∙ y) ∙ z = x̅ ∙ z + y̅ ∙ z = 1 となるような値の組は，d を出力する回路
では don’t care であることが分かる．また，c = ̅̅̅̅̅
x ∙ y = 0 となるような値の
組も，d の値に関わらず b = 1 となり，d を出力する回路では don’t care で
ある．ちなみに，真理値表では，a = 1 あるいは c = 0 となるような値の
組において， f = 1 となっているので，図示されている回路は f の真理値
表と矛盾しない．
そこで，c = 1 かつ a = 0 のときを考えると，𝑓 = b = d̅ であるから，
f
0
1
1
1
1
0
1
1
ｘ，ｙ，ｚ，ｗ
1, 0, 0, 0
1, 0, 0, 1
1, 0, 1, 0
1, 0, 1, 1
1, 1, 0, 0
1, 1, 0, 1
1, 1, 1, 0
1, 1, 1, 1
f
0
1
1
1
1
1
1
1
d の値は，d = 𝑓 ̅ を満たさなければならない．これらより，d のカルノー図は右上図のようになる．従って，d の最簡な積
和形論理式は次式となる．
d = y̅ ∙ w
̅ +y∙w
これを NAND ゲートだけで実現するには，次のように変形すればよい．
(̅̅̅̅̅̅
d = ̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿
y̅ ∙ w
̅ + y ∙ w = ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
y̅ ∙ w
̅ ) ∙ (̅̅̅̅̅̅
y ∙ w)
回路図は省略する．
６．入力 x に対して，下の状態遷移表で表されるような状態遷移をし，出力 z を出す順序回路を設計したい．今，状態 Q0,
Q1, Q2 を，状態変数 v, w を用いて右下の状態割り当て表のように表したとき，以下の問に答えよ．回答は 1 枚目の問題
用紙の裏に書け．その際，カルノー図に利用可能なマス目と，D フリップフロップの図を描いておいたので，利用せよ．
現状態
入力
x
Q0
Q1
Q2
(1)
出力 z
次状態
0
Q1
Q2
Q0
1
Q2
Q0
Q1
0
0
0
1
Q0
Q1
Q2
各状態変数 v, w の次状態の値 v', w' を表す状態遷移関数をできるだけ簡単な和積形（乗法標準形，OR-AND 形）論
理式で表せ．
次状態 v’, w’
現状態入力
<解答例>
v, w
x
0
1
問題で指定された状態割り当てを行った場合，状態変数を
0, 0
1, 0
0, 1
用いた状態遷移表は右のようになるから，v' および w' のカルノ
1, 0
0, 1
0, 0
̅ および ̅̅̅
ー図は，右下図のようになる．従って，v′
w′ の積和形
0, 1
0, 0
1, 0
論理式はそれぞれ次式となる．
̅ = v + x̅w + xw
v′
̅
v'
̅̅̅ = x̅w + y̅v
w′
これらより，v’ および w’ の最簡な和積形論理式
はそれぞれ次式となる．
v ′ = v̿′ = ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
v + x̅w + xw
̅ = (v̅)(̅̅̅̅̅
x̅w)(̅̅̅̅̅
xw
̅)
(
)
(
)
(
)
= v̅  x + w
̅  x̅ + w
0
1
00
1
0
01
0
1
vw
11 ＊＊
10
w'
x
x
v
̿̿̿′ = ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
w ′ = ̿w
w + x̅v̅ + xv = (w
̅ )(̅̅̅̅
x̅v̅)(̅̅̅̅
xv)
= (w
̅ )(x + v)(x̅ + v̅)
(2)
状態変数
v, w
0, 0
1, 0
0, 1
状態
1
0
1
0
0
x
x
0
1
00
0
1
01
0
0
vw
w
w
11 ＊＊
v
10
0
1
0
出力関数をできるだけ簡単な和積形（乗法標準形，OR-AND 形）論理式で表せ．
<解答例>
状態変数を用いた状態遷移表は下のようになるから，z のカルノー図は，
右図のようになる．
現状態
v, w
0,
1,
0,
0
0
1
入力
x
z
1
0
1
0
0
1
00
0
0
01
1
0
vw
出力 z
0
0
0
1
v
11 ＊＊
10
従って，z̅ の最簡な積和形論理式は次式となる．
z̅ = x̅w
̅ + xv̅
これより，z の和積形論理式は次式となる．
z = z̿ = ̅̅̅̅̅̅̅̅̅̅̅̅
x̅w
̅ + xv̅ = (̅̅̅̅̅
x̅w
̅ )(̅̅̅̅
xv̅) = (x + w)(x̅ + v)
x
x
0
1
w
(3)
D フリップフロップ，インバータ，NOR ゲートだけを用いてこの順序回路を実現し，その回路図を図示せよ．ただし，D
フリップフロップは初期化回路を持たないので，reset = 1 のとき状態を初期状態 Q1 にする初期化回路も，インバータと
NOR ゲートだけで構成し，付加すること．
<解答例>
(1) および (2) で得られた和積形論理式より，下記のように NOR 演算を用いた式を得ることができる．これらより，
reset = 0 のとき，状態変数 v，w の値を蓄える DFF への入力 dv，dw を生成する回路および出力 z を生成する回路が
得られる．
̅̅̅̅
̿̿̿ = ̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿
(v̅)(x + w
(v̅) + ̅̅̅̅̅̅̅̅̅̅
(x + w
(x̅ + w) = ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
(x + w
(x̅ + w)
dv = dv
̅ )(x̅ + w) = ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
̅ ) + ̅̅̅̅̅̅̅̅̅̅
v + ̅̅̅̅̅̅̅̅̅̅
̅ ) + ̅̅̅̅̅̅̅̅̅̅
̅̅̅̅̅
(w
(w
(x + v) + ̅̅̅̅̅̅̅̅̅
(x̅ + v̅) = ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
(x + v) + ̅̅̅̅̅̅̅̅̅
(x̅ + v̅)
dw = ̿̿̿̿
dw = ̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿
̅ )(x + v)(x̅ + v̅) = ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
̅ ) + ̅̅̅̅̅̅̅̅̅
w + ̅̅̅̅̅̅̅̅̅
̅̅̅̅̅̅̅̅̅̅
(x + w)(x̅ + v) = ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
(x + w) + ̅̅̅̅̅̅̅̅̅
(x̅ + v)
z = z̿ = ̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿
reset = 1 のとき，状態を初期状態 Q1 にするには，v’ = 1，w’ = 0 にし，reset = 0 のとき，v’ = dv，w’ = dw となるよう
にすればよいから，状態変数 v，w の値を蓄える DFF への入力 Dv，Dw を次式で生成すればよい．
̅̅̅̅̅̅̅̅̅̅̅̅̅
(dv
Dv = dv + reset = ̿̿̿̿̿̿̿̿̿̿̿̿̿
dv + reset = ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
+ reset)
̅̅̅̅
̅̅̅̅̅̅̅̅dw = ̅̅̅̅̅̅̅̅̅̅̅̅̅̅
Dw = ̅̅̅̅̅̅̅
resetdw = ̿̿̿̿̿̿̿̿̿̿̿̿̿
reset
reset + dw
回路図は省略する．
以上

Download Report