問題1

ハミング符号とは,データに冗長ビットを付加して, 1ビットの誤りを訂正できるようにしたものである。ここでは,X1,X2,X3,X4の4ビットから成るデータに,3ビットの冗長ビットP3,P2,P1を付加したハミング符号 X1X2X3P3X4P2P1 を考える。付加ビットP1,P2,P3は,それぞれ
X1⊕X3⊕X4⊕P1=0
X1⊕X2⊕X4⊕P2=0
X1⊕X2⊕X3⊕P3=0
となるように決める。ここで⊕は排他的論理和を表す。ハミング符号 1110011 には1ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。

ア0110011 イ1010011 ウ1100011 エ1110111

まずハミング符号 1110011とのことで、冗長ビットにすると

X1=1,X2=1,X3=1,X4=0,
P1=1,P2=1,P3=0

各ビットを問題中の3つの式に当てはめて、誤りを検証します。

1⊕1⊕0⊕1=1
1⊕1⊕0⊕1=1
1⊕1⊕1⊕0=1

存在する誤りが1ビットであり、すべての式の結果が0ではないということは、唯一すべての式に含まれているX1が誤りビットであると判断できます。

したがって、訂正前のハミング符号「1110011」のX1(1ビット目)を0に反転させ「0110011」が正解となります。

 

問題2

非負の整数m,nに対して次のとおりに定義された関数 Ack(m,n) がある。Ack(1,3) の値はどれか。

am1/05.gif/image-size:450×59

ア3 イ4 ウ5 エ6

設問の再帰関数 Ack(1,3) を実行すると次のようになります。

Ack(1,3)              //Ack(1,3)は、m>0かつn>0
=Ack(0,Ack(1,2))         //Ack(1,2)は、m>0かつn>0
=Ack(0,Ack(0,Ack(1,1)))     //Ack(1,1)は、m>0かつn>0
=Ack(0,Ack(0,Ack(0,Ack(1,0)))) //Ack(1,0)は、m>0かつn=0
=Ack(0,Ack(0,Ack(0,Ack(0,1)))) //Ack(0,1)は、m=0
=Ack(0,Ack(0,Ack(0,2)))     //Ack(0,2)は、m=0
=Ack(0,Ack(0,3))         //Ack(0,3)は、m=0
=Ack(0,4)             //Ack(0,4)は、m=0
=5

問題3

再帰的な処理を実現するためには,再帰的に呼び出したときのレジスタ及びメモリの内容を保存しておく必要がある。そのための記憶管理方式はどれか。

アFIFO イLFU ウLIFO エLRU

再帰とは、実行中に自分自身を呼び出すことをいい、再帰呼出しを行っても正しい結果を返すことができる性質をもつプログラムを「再帰的プログラム」といいます。再帰関数の動作を理解するために例を挙げて説明します。例えば、nの階乗を再帰的に計算する関数F(n)が次のように定義されていたとします。(nは非負の整数です)

n>0のとき、F(n)=n×F(n-1)
n=0のとき、F(n)=1

階乗とは、1からある自然数nまでの相乗のことをいい、n の階乗は記号 ! を使って「n!」と表記されます。例えば 3! であれば、

3×2×1=6

というように計算します。

関数F(n)を用いて 3! を計算すると、以下のように実行途中で自分自身の呼び出しを伴います。

F(3)=3×F(3-1)
F(2)=2×F(2-1)  //自分自身 F(2)を呼び出す
F(1)=1×F(1-1)  //F(1)を呼び出す
F(0)=1      //F(0)を呼び出す
F(1)=1×1=1   //F(1)の処理に戻る
F(2)=2×1=2   //F(2)の処理に戻る
F(3)=3×2=6   //F(3)の処理に戻る
上記のように再帰的な処理では、ある関数の処理中に同じ関数(自分自身)を呼び出し、呼び出した関数の処理が終わると呼出し元の処理に戻ります。このような手順で処理されるため、最終的に正しい結果を得るためには、自分自身を呼び出した時点での呼出し元側の途中経過を記憶しておかなければなりません。再帰的な処理では、実行中に自分自身が呼び出された場合にそこまでの実行途中の状態を、スタックと呼ばれるデータ構造に格納しておきます。

am1/08_1.gif/image-size:404×136

そして、n=0のときにF(0)が1を返し、呼出し元の処理に戻っていく過程では、最後に積み上げたものから順にF(1)、F(2)、F(3)と値が返ってきて計算されます。

am1/08_2.gif/image-size:404×135

上記のように、再帰的な処理では A1→A2→A3 の順でプログラムを呼び出した場合、A3→A2→A1 というように後から入れたものから順にその値を使用します。つまり再帰的な処理は、LIFO(Last-In First-Out,後入れ先出し)の記憶管理方式を用いて実現されています。

 

問題4

メモリインタリーブの説明として,適切なものはどれか。

ア 主記憶と外部記憶を一元的にアドレス付けし,主記憶の物理容量を超えるメモリ空間を提供する。

イ 主記憶と磁気ディスク装置との間にバッファメモリを置いて,双方のアクセス速度の差を補う。

ウ 主記憶と入出力装置との間でCPUとは独立にデータ転送を行う。

エ 主記憶を複数のバンクに分けて,CPUからのアクセス要求を並列に処理できるようにする。

メモリインタリーブは、メモリアクセス高速化のための技法で、物理的にひとつの主記憶を同時アクセス可能な複数の論理的な領域(バンク)に分け、これに並列アクセスすることで見かけ上のアクセス時間を短縮することができます。

am1/11.gif/image-size:265×226

問題5

4種類の装置で構成される次のシステムの稼働率は,およそ幾らか。ここで,アプリケーションサーバとデータベースサーバの稼働率は0.8であり,それぞれのサーバのどちらかが稼働していればシステムとして稼働する。また,負荷分散装置と磁気ディスク装置は,故障しないものとする。

am1/16.gif/image-size:337×189

ア 0.64 イ 0.77 ウ 0.92 エ 0.96

4種類の装置のうち、負荷分散装置と磁気ディスク装置は故障しない、システム全体の稼働率はアプリケーションサーバ(以下、APサーバ)とデータベースサーバ(以下、DBサーバ)の部分だけによって決まる。そしてAPサーバとDBサーバは、2台のうちどちらかが稼働していればよい、下図のように2台が並列に接続されているものと見なせる。

 

am1/16_1.gif/image-size:292×98

装置単体の稼働率がRのとき、2台が並列に接続されている場合の全体としての稼働率は「1-(1-R)2」、直列の場合は「R2」で求められる。この公式を使って、まずは並列で接続されている部分の稼働率を計算。

1-(1-0.8)2
=1-0.04=0.96

APサーバ群、DBサーバ群の稼働率はともに0.96とわかります。そして稼働率0.96のサーバ群同士が直列で接続されているので、システム全体としての稼働率は、

0.96×0.96=0.9216≒0.92

am1/16_2.gif/image-size:290×161

 

問題6

ページング方式の仮想記憶における主記憶の割当てに関する記述のうち,適切なものはどれか。
ア プログラム実行時のページフォールトを契機に,ページをロードするのに必要な主記憶が割り当てられる。

イ プログラムで必要なページをロードするための主記憶の空きが存在しない場合には,実行中のプログラムのどれかが終了するまで待たされる。

ウ プログラムに割り当てられる主記憶容量は一定であり,プログラムの進行によって変動することはない。

エ プログラムの実行開始時には,プログラムのデータ領域とコード領域のうち,少なくとも全てのコード領域に主記憶が割り当てられる。

ページング方式は、仮想アドレス空間を「ページ」と呼ばれる固定長の区画に分割、同時に主記憶上も同じように固定長に分割して、このページ単位で主記憶と補助記憶装置のアドレス変換を行う仮想記憶管理方式です。ページング方式の仮想記憶において、プログラムの実行に必要なページが主記憶(実メモリ)上に存在しない場合、システムは「ページフォールト」という割込みを発生させます。ページフォールトが発生すると、主記憶と仮想記憶間でページの入替えが行われます。この入替え動作において、主記憶から仮想記憶にページを退避することを「ページアウト」、仮想記憶から主記憶にページをロードすることを「ページイン」といいます。

 

問題7

ワンチップマイコンにおける内部クロック発生器のブロック図を示す。15MHzの発振機と,内部のPLL1,PLL2及び分周器の組合せでCPUに240MHz,シリアル通信(SIO)に115kHzのクロック信号を供給する場合の分周器の値は幾らか。ここで,シリアル通信のクロック精度は±5%以内に収まればよいものとする。
am1/23.gif/image-size:497×182

ア 1/24 イ 1/26 ウ 1/28 エ 1/210

発信器から出力された15MHzは、PLL1で8倍にされて120MHzになります。その後CPUへはPLL2でさらに2倍されて240MHzのクロック信号が届けられます。

am1/23a.gif/image-size:453×167
問題の分周器の値ですが、分周器への入力が120MHz、SIO(シリアル通信)に供給されるクロック信号は115kHzなので、およそ 1/1000の値になっていることに気が付きます。

120×106÷(115×103)≒103

つまり分周器の値は約 1/1000に設定すればよく、これを2進数で表した「1/210」(=1/1024)が答えとなります。

広告