平成21年春期試験午後問題 問1

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】

問1 ハードウェア

画像データの符号化に関する次の記述を読んで,設問1~3に答えよ。

 図1は,8×8画素の白と黒だけで色分けされた2値画像の例である。画素を1番上の行の左から右へ,次に2番目の行の左から右へと順に1画素を1ビットで,白を0,黒を1で表すと,図2のように64ビットのビット列で表現することができる。
pm01_1.gif
  • 図2のビット列を,同じ値が連続している部分(以下,ランという)ごとに区切り,各ランをその連続する個数(以下,ランレングスという)で表すことによって,少ないビット数でのビット列表現に書き換えることができる。図2では,左上から数えて0が27個,1が27個,0が10個の順に連続しているので,27,27,10という情報を使った表現に書き換える。これを,ランレングス符号化という。
  • 1番上の行の左端の画素は白で始まるものとする。ただし,その画素が黒の場合は,先頭に0個の白があるものとして符号化を行う。
  • ランレングス符号化の方法は,次のとおりである。
    1. ランレングスをnとし,nを2進数で表現したときのけた数をmとする。ただし,常にm≧2となるように,n=0の2進数表現を00,n=1の2進数表現を01とする。
    2. nビットのランを図3のビット列に書き換える。
      pm01_2.gif
  • 図2の例では,最初は0が27個連続しているので,n=27である。27を2進数で表現すると11011(5けた)となり,m=5である。m-2=3なので,けた数情報は111である。 したがって,この部分の符号化後のビット列表現は111011011となり,9ビットで表現できる。
  • 表にn,m及び符号化後のビット列を示す。
pm01_3.gif

設問1

表中の に入れる正しい答えを,解答群の中から選べ。
a に関する解答群
  • 100
  • 0100
  • 10100
  • 110100
b に関する解答群
  • 14
  • 15
  • 16
  • 17
解答選択欄
  • a:
  • b:
  • a=
  • b=

解説

aについて〕
設問の手順に従って符号化を行います。
  1. mは10進数のnを2進数に変換したときのけた数です。n=4は、

     4(10)→100(2)

    と変換されるので、m=3になります。
  2. m,nをランレングスのビット列に当てはめると、
    1. けた数情報は(m-2)個の連続する1です。3-2=1なので(a)の部分は1になります。
    2. 区切りは常に1個の0です。(b)は0になります。
    3. nの2進数表現が入ります。4(10)→100(2)なので(c)は100になります。
したがってaには(a),(b),(c)を連結した10100が入ります。

a=ウ:10100

bについて〕
符号化後のビット列の中で最初に現れる「0」は(b)区切りを表しています。つまりnを2進数にしたビット列が1111ということです。2進数1111を10進数に変換すると、

 1111(2)=23+22+21+20
=8+4+2+1=15(10)

n=15とわかります。

b=イ:15
pm01_5.gif

設問2

図2の64ビットのビット列をランレングス符号化すると,何ビットで表現できるか。正しい答えを,解答群の中から選べ。
解答群
  • 22
  • 23
  • 24
  • 25
解答選択欄
  •  
  •  

解説

設問のビット列は 0:27個→1:27個→0:10個 で構成されているため、これらにランレングス符号化を施します。

[0:27個]
n=27(10)→11011(2)
m=5
(a)の長さ=m-2=3

以上より(a)=111,(b)=0,(c)=11011

この部分のビット列は(a),(b),(c)を連結した「111011011」になるため、ビット数は9です。

[1:27個]
上記と同様に9ビットになります。

[0:10個]
n=10(10)→1010(2)
m=4
(a)の長さ=m-2=2

以上より(a)=11,(b)=0,(c)=1010

この部分のビット列は「1101010」になるため、ビット数は7です。

したがって3つの符号化ビット列の長さ(9,9,7)を足した25になります。

∴エ:25

設問3

ランレングス符号化後のビット列が,次のとおりであったとする。このビット列を復号した2値画像として正しい答えを,解答群の中から選べ。

 000111011111111011111010
解答群
  • pm01_4a.gif
  • pm01_4i.gif
  • pm01_4u.gif
  • pm01_4e.gif
解答選択欄
  •  
  •  

解説

まずは与えられたビット列をランごとに分割しなければなりません。

始めが「0」、すなわち区切りから開始するということは(a)の部分が存在しないm=2以下のランと判断できます。mが2以下の場合は常に符号化後のビット列長が2ビットになるため、0に続く2ビット「00」が(c)になります。
pm01_6.gif
次に1が3つ続いた後に「0」が挿入されているため(a)=111,(b)=0と判断できます。(a)の長さから m=3+2=5 と分かるため、0の後に続く5ビット「11111」が(c)になります。
pm01_7.gif
先程と同様に1が3つ続いた後に「0」が挿入されているため(a)=111,(b)=0と判断できます。同じように0の後に続く5ビット「11111」が(c)です。
pm01_8.gif
最後のビット列は「0」で始まっているため(a)の部分がないm=2以下のランと判断できます。したがって0に続く2ビット「10」が(c)です。
pm01_9.gif
以上より設問のビット列は、
  • 000
  • 111011111
  • 111011111
  • 010
の4つのランに分解されることになります。後はそれぞれのラン情報を白黒の画素情報に逆変換するだけです。
pm01_10.gif
[000]
(c)=00
00(2)→0(10)

設問中に「1番上の左端の画素は白で始まるものとする。ただし,その画素が黒の場合は、先頭に0個の白がある者として符号化を行う」という記述があるため、このランは0個の白に該当すると判断できます。

[111011111]
(c)=11111
11111(2)→31(10)
●31個のランに変換されます。

[111011111]
(c)=11111
11111(2)→31(10)
○31個のランに変換されます。

[010]
(c)=10
10(2)→2(10)
●2個のランに変換されます。

以上より、画像の左上より●31個→○31個→●2個と並んでいる「エ」が正解と分かります。

Pagetop