ITの基礎知識|ITパスポート・基本情報

基本情報技術者 平成21年春 午後 問1

2026.05.18

午後問題に共通する注意事項(表記ルールなど)については、下記のリンク先を参照してください。

基本情報技術者 平成21年春 午後問題の注意事項


問題

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

図1は,8×8画素の白と黒だけで色分けされた2値画像の例である。画素を1番上の行の左から右へ,次に2番目の行の左から右へと順に1画素を1ビットで,白を0,黒を1で表すと,図2のように64ビットのビット列で表現することができる。

(1)図2のビット列を,同じ値が連続している部分(以下,ランという)ごとに区切り,各ランをその連続する個数(以下,ランレングスという)で表すことによって,少ないビット数でのビット列表現に書き換えることができる。図2では,左上から数えて0が27個,1が27個,0が10個の順に連続しているので,27,27,10という情報を使った表現に書き換える。これを,ランレングス符号化という。

(2)1番上の行の左端の画素は白で始まるものとする。ただし,その画素が黒の場合は,先頭に0個の白があるものとして符号化を行う。

(3)ランレングス符号化の方法は,次のとおりである。

  1. ランレングスをnとし,nを2進数で表したときのけた数をmとする。
    ただし,常にm≧2となるように,n=0の2進数表現を00,n=1の2進数表現を01とする。
  2. nビットのランを図3のビット列に書き換える。

(4)図2の例では,最初は0が27個連続しているので,n=27である。27を2進数で表現すると11011(5けた)となり,m=5である。m-2=3なので,けた数情報は111である。したがって,この部分の符号化後のビット列表現は111011011となり,9ビットで表現できる。

(5)表に n,m及び符号化後のビット列を示す。


設問1

表中の空欄に入れる正しい答えを,解答群の中から選べ。
*(5)の表内

aに関する解答群

  • ア: 100
  • イ: 0100
  • ウ: 10100
  • エ: 110100

bに関する解答群

  • ア: 14
  • イ: 15
  • ウ: 16
  • エ: 17

設問2

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

解答群

  • ア: 22
  • イ: 23
  • ウ: 24
  • エ: 25

設問3

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

000111011111111101111110 10

Show answer

解答

  • 設問1
    • 空欄 a:ウ(10100)
    • 空欄 b:イ(15)
  • 設問2:エ(25ビット)
  • 設問3:エ

設問1(a)解説

図3で示されたルールでビット列を生成する。手順としては、(c) のランレングス情報を求めてから、そこで分かった桁数を元に、(a)の桁数情報を求める。

  1. (a) のけた数情報:m=3 と分かっているので、$(3-2)=1$ より、1のビットを1桁とする。
  2. (b) の区切りビット:ここは 0 を1桁で固定。
  3. (c) のランレングス情報:n=4 を2進数で表現した '100' となる。

上記で求めたビット列を結合すると、'1'+'0'+'100' = 10100 となる。

設問1(b)解説

(a) の部分は必ず '1' が連続する形になり、(b) の部分は '0' で固定となるので、それをヒントに与えられたビット列を分解する。元のビット列が、 '1101111' なので以下の様に分解できる。

  • (a) の部分:先頭の '11' が該当。ここは、2進数化したときの桁数m から2を引いた分だけ、1が連続する。今回は1が2桁連続しているので、$2+2=4$ で m=4 となる。
  • (b) の部分:3桁目の '0' が該当。
  • (c) の部分:残り4ビット '1111' が該当。これを 10進数に戻すと、$ 2^3 + 2^2 + 2^1 + 2^0 = 8+4+2+1=15$

よって、 b = 15 となる。

設問2解説

図2のビット列のランの内訳:0が27個・1が27個・0が10個*ここは頑張って目視で数えるしかありませんので、見間違え注意。これを元に、それぞれ符号化していく。

上記のように求めたビット数を合計し、9+9+7 = 25ビット が正解。

なお、2進数化したときのビット数を求める際、実際の数値を正直に2進数化していると時間が掛かってしまうので、以下の表のイメージで求めるのが良い。

今回登場する10進数の値は27と10だが、これを上の表に当てはめると、10進数の 27 は 16 以上 31 未満に当てはまるので5桁、10 は 8 以上 15 未満に当てはまるので4桁というのがそれぞれわかる。

ちなみに、この表のルールはN進数全般に当てはまり、以下のようになる。

要は、元の10進数の値が、Nの何乗と何乗の間に当てはまるかさえわかれば、N進数で何桁になるかが特定できる、ということである。

設問3解説

ビット列 '00011101111111110111111010' を前から順に復号する。元のビット列が '0' で始まっているのがポイント。

図3で示されているルールを読み解くと、以下のことが分かる。

  • 常にm≧2となるように,n=0の2進数表現を00,n=1の2進数表現を01とする。
  • m=2 の場合、(a)の桁数情報はビット化されない。

このことから、先頭の `0` は (b) の区切りビットに該当し、m=2 なので、その次の '00' が(c) のランレングス情報に該当する。

つまり、'000' というビット列が最初の色情報ということになり、これは「先頭に0個の白がある」という状態を表した色情報ということになる。

(2)で「1番上の行の左端の画素は白で始まるものとする。ただし,その画素が黒の場合は,先頭に0個の白があるものとして符号化を行う。」というルールが示されているので、'000' というビット列で始まる場合、先頭の画素が黒であることを示しており、先頭画素が「白」になっている ア と ウ は除外される。

この時点で、残ったビット列は '11101111111110111111010' となる。

次は、区切りとなる '0' のビットを探し、'1110' の部分を取り出す。この部分は、(a) のけた数情報・(b) の区切りビット となるので、ここから(c) のランレングス情報に当たるのが、次の何ビット分なのかが求められる。(a) のけた数情報は、1が3桁続いているので、m-2=3 → m=5 と分かる。

そして、残ったビット列 '1111111110111111010' から5桁分取り出した、'11111' が (c) のランレングス情報 となる。'11111' を10進数に直すと、$ 2^4 + 2^3 + 2^2 + 2^1 + 2^0 = 16+8+4+2+1=31$ となり、このことから、次は黒のビットが31個続く、というのがわかる。この時点で、エ のパターンに確定する。