カテゴリ: 3.コンピュータの基礎理論

 

1.CRC

CRCは、「送信側では、生成多項式を用いて検査対象のデータから検査用のデータを作り、これを検査対象のデータに付けて送信する(H16NW午前問31)」ものです。

2.CRCの過去問 

CRCに関して、ここ最近の応用情報技術者試験では、あまり問われていません。
(1)H21春AP午前問4

問4 誤り検出方式であるCRCに関する記述として,適切なものはどれか。
ア 検査用のデータは,検査対象のデータを生成多項式で処理して得られる1ピットの値である。
イ 受信側では,付加されてきた検査用のデータで検査対象のデータを割り,余りがなければ送信が正しかったと判断する。
ウ 送信側では,生成多項式を用いて検査対象のデータから検査用のデータを作り,これを検査対象のデータに付けて送信する。
エ 送信側と受信側では,異なる生成多項式が用いられる。




正解:ウ

(2)H22秋FE午後問3

問3 CRC(巡回冗長検査)に関する次の記述を読んで,設問1~3に答えよ。
 CRCは,誤り検出方式の一つである。送信側でデータに誤り検出符号(以下,符号という)を付加して送信し,受信側で検査することによって,転送の際の誤りの有無を判断する。

設問1 次の記述中の[    ]に入れる正しい答えを,解答群の中から選べ。
 CRCを採用したパケット転送システムでは,送信側でパケットに符号が付加され,受信側で誤りの有無を検査する。受信側で誤りが検出されると,送信側に対して該当パケットの再送を要求する。100個のパケットに格納されたデータの転送において,受信側が実際に受信したパヶツトが,再送されたパケットも含めて[    ]個であったとすると,受信したパケットの20%から誤りが検出されたことになる。ここで,送信したパケットは必ず相手に届くものとする。また,パケットの再送要求は誤りなく届き,再送要求には必ず応じるものとする。

解答群
ア 100    イ 102    ウ 120    エ 125

正解は、エです。

設問2 次の記述中の[    ]に入れる正しい答えを,解答群の中から選べ。

 任意の長さのビット列の符号を求める計算手順を次に示す。ここで,符号の長さはnビットとする。

〔nビットの符号を求める計算手順〕
 (1)左端及び右端のビットが1である(n +1)ビットのビットパターン(以下,マスクという)を定める。
 (2)符号計算対象のビット列の右端にnビットの0を付加したビット列を作る。
 (3)(2)で作ったビット列に対して次の操作を行う。
  ① ビット列の左端から調べ,最初に値が1であるビットの位置pを見つける。
  ②pを左端としp+nを右端とする部分ビット列に対し,マスクで排他的論理和(XOR)を取る。
  ③ ビット列の右端nビット以外がすべて0になるまで,①及び②を繰り返す。
 (4)(3)の操作で得られたビット列の右端nビットが符号となる。

  図に,マスクが101のときの符号(2ビット)を計算する例を示す。

22-FE問3-1

  図 マスクが101のときの符号(2ビット)を計算する例

 マスク101で計算した,符号計算対象のビット列0010 0110の2ビットの符号は[    ]である。

解答群
ア 00    イ 01    ウ 10    エ 11

正解は、イです。

設問3 次の記述中の[    ]に入れる正しい答えを,解答群の中から選べ。

  誤りの有無の検査は,次の手順で行う。

 〔誤りの有無の検査手順〕
(1)受信したビット列に対して,送信側で符号の計算に利用したものと同じマスクを使い,〔nビットの符号を求める計算手順〕の(3)と同じ処理を行う。
(2)右端nビットの値によって,誤りの有無を判断する。

 受信したビット列(符号が付加されたビット列)を,誤りの有無の検査手順に従って検査すると,誤りがなければ最後に残った右端nビットの値は[    ]になる。このことは次の手順で説明できる。

〔手順〕
(1)符号計算対象のビット列を一つの数値Dと見ると,符号Cは次の式で表せる。
22-FE問3-2
(2)〔誤りの有無の検査手順〕で得られた結果の右端nビットの値Tは,次の式で表せる。
22-FE問3-3

(3)式②を変形すると次の式となる。
22-FE問3-4

(4)式①と式③によって,
    [  b  ]=T
となる。

 マスク101で計算した符号を右端に付加したビット列1001001101を受信した。このピット列には[  c  ]。

aに関する解答群
ア すべてのビットが0  
イ すべてのビットが1
ウ 符号と同じ
エ 符号の各ビットを反転させたものと同じ

bに関する解答群
22-FE問3-5

cに関する解答群
ア 誤りが含まれる
イ 誤りは含まれない
ウ 誤りが含まれるか否かは判断できない




正解は、

a ア
b エ
c ア です。

小学校ではこんな問題があったと思います。
30人の生徒がいます。野球を好きな人が15人、サッカーが好きな人が10人、両方好きな人が4人いました。では、両方嫌いな人は何人でしょう。  
これをベン図で表すと、以下のようになります。
1
応用情報技術者試験を勉強する成子 

なぜベン図というのですか?
イギリスのベン(Venn)さんが考案したからです。レントゲンを発明したのがレントゲンさんであるのと同様です。
さて、論理和(OR)、論理積(AND)、排他的論理和(XOR)を覚えましょう。

これ以外には、否定も覚えておきましょう。ベン図では、補集合と言います。

論理和(OR)、
上でいう、野球とサッカーのどちらかが好きな人です。
合計20人です
情報処理技術者試験では、A∪B、A∨B、A+B、などの表現が使われます。「AまたはB」と読みましょう。
ベン図と真理値表は、以下です。
ベン図 真理値表
OR2 OR

論理積
上でいう、野球とサッカーの両方が好きな人です。
4人います。
です。
ベン図真理値表
AND2AND  

情報処理技術者試験では、A∩B、A∧B、A・B、などの表現が使われます。「AかつB」と読みましょう。
応用情報技術者試験を勉強する成子 

子供の頃に、AかつBだから、「つ」と「∩」を関連して覚えるといいと言われました。
試験では、問題文に表記の解説がなされますが、覚えておくのはいいと思います。

否定
です。
ベン図真理値表
後日記載NOT  


排他的論理和
は、上でいう、どちらか一方だけが好きな人です。
16人います。
です。
ベン図真理値表
haita2ahaita  

では、ベン図に関して、過去問(H25年秋FE午前問1)を見てみましょう。
ベン図

正解はウです。
面倒ですが、一つ一つ丁寧に書いていくのが近道です。

論理演算において、いくつかの公式があります。それは、結合法則や分配法則、ド・モルガンの法則です。
応用情報技術者試験を勉強する成子 

結合法則と分配法則は、中学校の数学か何かで習った記憶があります。

はい、それとほぼ同じです。
実際に見てみましょう。

 

1.結合法則

これは、過去問(H29年春AP午前問1)でズバリ問われています。
(A∪B)∪C=A∪(B∪C)
(A∩B)∩C=A∩(B∩C)

これは、数学における足し算や掛け算の以下の公式が成り立つのと同じです。
(A+B)+C=A+(B+C)
(A×B)×C=A×(B×C)

2.分配法則

A∩(B∪C)=(A∩B)∪(A∩C)
A∪(B∩C)=(A∪B)∩(A∪C)

こちらも1つめは数学と同様です。
A×(B+C)=(A×B)+(A×C)

2つ目は、数学の公式とは違いますね。以下の式は成り立ちません。
A+(B×C)=(A×B)+(A∪C)

3.ド・モルガンの法則

aaa









分かりにくいですね。
ベン図を描いてみると、たしかに一致します。
aaaa
言葉で考えてみましょう。小学生にて、Aが野球が好き、Bがサッカーが好きと仮定します。
上の公式で考えます。
左辺:野球とサッカーの両方が好きではない人
右辺:野球が嫌い、または、サッカーが嫌いのどちらかの人
言葉で表現するとわかりにくいのですが、左辺も右辺も同じ人が対象になります。(以下の○の人が対象)
ben2

 

4.論理演算の公式の過去問を解いてみよう

(1)平成29年春期 午前問1

ben






順番にベン図を描くのが近道かも知れませんね。
すべて成立します。
【正解】エ

(2)H25春AP午前問2

問2
1-3H25h-2





【正解】ア

(3)H28春AP午前問1

問1 nビットの値L1,L2がある。次の操作によって得られる値L3は,L1とL2に対するどの論理演算の結果と同じか。
〔操作〕
(1)L1とL2のビットごとの論理和をとって,変数Xに記憶する。
(2)L1とL2のビットごとの論理積をとって更に否定をとり,変数Yに記憶する。
(3)XとYのビットごとの論理積をとって,結果をL3とする。
ア 排他的論理和   イ 排他的論理和の否定
ウ 論理積の否定   エ 論理和の否定






【正解】ア

(4)H27秋AP午前問1

問1 0以上255以下の整数nに対して,
1-3H27a-1
と定義する。 next (n)と等しい式はどれか。ここで,x AND y 及び x OR yは,それぞれxとyを2進数表現にして,桁ごとの論理積及び論理和をとったものとする。
ア (n +1)AND 255   イ (n +1)OR 256
ウ (n +1)OR 255    エ (n +1)AND 256






【正解】ア

(5)H27秋AP午前問2

問2 集合A,B,Cに対してA∪B∪Cでが空集合であるとき,包含関係として適切なものはどれか。ここで,∪は和集合を,∩は積集合を,XはXの補集合を,また, X⊆YはXがYの部分集合であることを表す。
ア (A∩B)⊆C   イ A∩B)⊆C   
ウ ((span style="text-decoration: overline;">A∩B)⊆C   エ ((span style="text-decoration: overline;">A∩B)⊆C






【正解】エ

(6)H26秋AP午前問2

問2 4nビットを用いて整数を表現するとき,符号なし固定小数点表示法で表現できる最大値をaとし, BCD (2進化10進符号)で表現できる最大値をbとする。nが大きくなるとa/bはどれに近づくか。
ア (15/9)×n
イ (15/9)n
ウ (16/10)×n
エ (16/10)n






【正解】エ

(7)H25秋AP午前問4

問4 論理式P,Qがいずれも真であるとき,論理式Rの真偽にかかわらず真になる式はどれか。ここで,“ ̄”は否定,“V”は論理和,“∧”は論理積,“→”は含意(“真→偽”となるときに限り偽となる演算)を表す。
1-3H25a-4






【正解】エ

(8)H28秋AP午前問1

問1 8ビットのデータX及びyの値をそれぞれ16進表現で0F,F0とするとき,  8ビットのデータAの下位4ビットを反転させ,上位4ビットを0にする論理式はどれか。
1






【正解】ウ
まず、XとYが2進数でどんな値なのでしょうか。慣れている人は、0FとF0を見て、00001111、11110000とすぐに分かったことでしょう。

念のため、一つずつ変換してみます。
X:0F(16進数)⇒15(10進数)⇒00001111(2進数(8ビット))
Y:F0(16進数)⇒240(10進数)⇒11110000(2進数)
たとえばAを11010111とすると、「8ビットのデータAの下位4ビットを反転させ,上位4ビットをOにする」と、
00001000 になります。
選択肢のなかでどれが正しいのかは、実際にやってみましょう。
たとえば、アです。わかりやすいように表にしましたが、このような図を書かなくても、A・Xを求めて、その否定を求めることはそう難しくないと思います。
2 
ウは以下のようになります。よって、正解選択肢です。
3

 

1.符号化とは

広義の「符号化」とは、アナログデータをデジタルデータにすることです。狭義の「符号化」に関しては、音声の符号化(A/D変換) における、「標本化,量子化,符号化の3段階で処理」で考えます。詳しくは以下に記載しています。

nw.seeeko.com

2.符号化に関する過去問

■H28春
問4 a,b,c,dの4文字から成るメッセージを符号化してビット列にする方法として表のア~エの4通りを考えた。この表はa,b,c,dの各1文字を符号化するときのビット列を表している。メッセージ中でのa,b,c,dの出現頻度は,それぞれ50%,30%,10%,10%であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって,ビット列の長さが最も短くなるものはどれか。
H28h-4



【正解】ウ

 

3.参考(ラングレス法)

可逆圧縮アルゴリズムの一つであるランレングス法について過去問(H21春FE午後問1)を紹介します。

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

 図1は,8×8画素の白と黒だけで色分けされた2値画像の例である。画素を1番上の行の左から右へ,次に2番目の行の左から右へと順に1画素を1ピットで,白を0,黒を1で表すと,図2のように64ビットのピット列で表現することができる。
H21春FE午後問1図1・図2
(1) 図2のビット列を,同じ値が連続している部分(以下,ランという)ごとに区切り,各ランをその連続する個数(以下,ランレングスという)で表すことによって,少ないビット数でのピット列表現に書き換えることができる。図2では,左上から数えて0が27個,1が27個,0が10個の順に連続しているので,27,27,10という情報を使った表現に書き換える。これを,ランレングス符号化という。

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

(3) ランレングス符号化の方法は,次のとおりである。
 ① ランレングスをnとし,nを2進数で表現したときのけた数をmとする。ただし,常にm≧2となるように,n =0の2進数表現を00,n =1の2進数表現を01とする。
 ② nビットのランを図3のビット列に書き換える。
H21春FE午後問1図3
(4) 図2の例では,最初は0が27個連続しているので,n =27である。27を2進数で表現すると11011 (5けた)となり,m =5である。m-2=3なので,けた数情報は111である。したがって,この部分の符号化後のピット列表現は111011011となり,9ピットで表現できる。

(5) 表にn,m及び符号化後のピット列を示す。
H21春FE午後問1 表 ビット列
設問1 表中の[    ]に入れる正しい答えを,解答群の中から選べ。

 aに関する解答群
 ア 100
 イ 0100
 ウ 10100
 エ 110100

 bに関する解答群
 ア 14
 イ 15
 ウ 16
 エ 17

正解は、
a ウ
b イ
です。

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

解答群
ア 22
イ 23
ウ 24
エ 25

正解は、エです。

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

 000111011111111011111010

解答群
H21春FE午後問1 設問3 解答群

正解は、エです。

 

 

1.信号処理に関して

 信号処理に関して、応用情報技術者試験シラバスでは、以下の記載があります。

(1)信号処理
アナログ波形を分析して,雑音を除去し,特徴を抽出する信号処理の考え方,仕組みを理解する。
用語例 DFT(Discrete Fourier Transform:離散フーリエ変換),FFT(Fast Fourier Transform:高速フーリエ変換),インパルス応答,フィルタ(ローパスフィルタ,ハイパスフィルタ,バンドパスフィルタ,ディジタルフィルタ),サンプリング定理,D/A 変換,A/D 変換

2.A/D変換

 会話や通話はアナログの波です。これを、TCP/IP上で通信をするには、0と1で表されるデジタル化をする必要があります。つまりアナログ(Analog)からデジタル(Digital)に変換する処理が必要です。
 A/D変換(アナログ/デジタル変換)に関しては、以下に記載しています。
http://nw.seeeko.com/archives/50493771.html

3.A/D変換に関する過去問

(1)平成28年秋期 午前

問22 音声を標本化周波数10 kHz,量子化ビット数16ビットで4秒間サンプリングして音声データを取得した。この音声データを,圧縮率1/4のADPCMを用いて圧縮した場合のデータ量は何kバイトか。ここで,1kバイトは1,000バイトとする。

ア 10  イ 20  ウ 80  エ 160 



標本化周波数10 kHzなので、1秒間に10k回のデータが存在します。量子化ビット数16ビットなので、1回のデータ量は16ビットです。
それを4秒間サンプリングし、1/4の圧縮をしたので、全部をかけ合わせます。
10k×16×4÷4=160kbit

これをバイトに直すために8で割ると、20kバイトです。

正解:イ

(2)H23秋FE午後問1

問1 A/D変換に関する次の記述を読んで,設問1~3に答えよ。

 A/D変換とは,アナログ信号をディジタル信号に変換することであり,標本化,量子化,符号化の3段階で処理する。直流の電圧を例にnビットのA/D変換を説明する。
(1)標本化
 標本化では,時間的に連続したアナログ信号である電圧を一定の時間間隔で測定する。図1では,時間軸をt0,t1,…と等間隔dで区切り,各時刻での電圧をv(t1),v(t1),…と表す。
2011h23a_fe_pm_qs_1

2011h23a_fe_pm_qs_2
2011h23a_fe_pm_qs_3
(3)符号化
 符号化では,(2)の量子化で用いた電圧v0,v1,…, vmaxに2進符号を対応付ける。この符号によって,各測定値を表す。

 

設問1 図2左の電圧v(t0),v(t1),…,v(t10)だけの符号化を考える。図2右の電圧v0,v1,…,v7を2進符号000,001,…,111に順に対応付けた場合を表1に示す。
2011h23a_fe_pm_qs_4

 図2左のv(t0),v(t1),…,v(t10))の各測定値を,表1に基づいて符号化すると表2のようになる。表2中の[    ]に入れる正しい答えを,解答群の中から選べ。
2011h23a_fe_pm_qs_5
  注記 網掛けの部分は表示していない。

解答群
ア 011  イ 100  ウ 101  エ 110  オ 111



正解は、
a エ
b ウです。

設問2 次の記述中の[    ]に入れる正しい答えを,解答群の中から選べ。

 アナログ信号の電圧の範囲が0~9Vであるとき,FSRを9Vとし, 4ビットで量子化した場合,qは[  c  ]である。アナログ信号の電圧7.49…Vの測定値は[  d  ]Vとなり,表1の場合と同様に2進符号0000,0001,…,1111に順に対応付けて符号化すると[  e  ]となる。

c, dに関する解答群
ア 0.5625    イ 0.6  ウ 1.2  エ 2.25  オ 5.5
カ 7.0   キ 7.2  ク 7.5  ケ 7.8   コ 8.0

eに関する解答群
ア 1010  イ 1011  ウ 1100  エ 1101  オ 1110



正解は、
c イ
d キ
e ウです。

設問3 次の記述中の[    ]に入れる正しい答えを,解答群の中から選べ。
 FSRが1,022ミリVであるアナログ信号の電圧を,50ミリ秒間隔で5秒間標本化した。このとき, A/D変換後の総データ量を1,000ビット以内に納めることができる刻み幅qの最小値は[  f  ]ミリVである。

解答群
ア 0.1  イ 0.5   ウ 1.0   エ 1.5  オ 2.0  カ 2.5  キ 3.0



正解は、オです。

過去問(H25春AP午前問4)ではハミング符号に関して、「ハミング符号とは,データに冗長ビットを付加して,1ビットの誤りを訂正できるようにしたものである」とあります。ポイントは、どのビットが間違っているかまで検出できるので、データ誤りを訂正できることです。

(1)過去問(H25春AP午前問4)

問4 ハミング符号とは,データに冗長ビットを付加して,1ビットの誤りを訂正できる
haming
ハミング符号1110011には1ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。

ア 0110011  イ 1010011  ウ 1100011  エ 1110111

今回は1ビット誤りなので、X1~X4のどれかに誤りがあります。
問題文と照らし合わせ、X1X2X3P3X4P2P1=1110011 として、3つの式に入れてみましょう。

1※1※0※1=1
1※1※0※1=1
1※1※1※0=1  ※は排他的論理和(表記の関係で)

ということで、本来は0になるべき値が、全て1に変わっています。
全ての式にX1が入っているので、X1が誤りということが分かります。
よって、X1を0に置き換えた0110011(選択肢ア)が正解です。
ネットワークスペシャリストを目指す女性SEあれ?

それ以外のビットは変更無しですか?




はい。1ビットの誤りですし、実際、X1を0にすることで、付加ビットの3つの式も全て満たします。


(2)H19秋SW午前問7

問7 コンピュータの主記憶の誤り制御などに採用されている方式のうち、1 ビット誤りを訂正し,2ビットの誤りを検出することができる方式はどれか。
ア 奇数パリティ方式 
イ 水平パリティ方式 
ウ チェックディジット方式
エ ハミング符号方式

奇数パリティ方式や水平パリティ方式では、誤り訂正はできません。1ビットの誤り検知までです。↓


正解は、エのハミング符号です。


(3)H17NW午前問32

haming2

 

1.誤り制御とは

データを通信相手の送信する際に、通信中のノイズなどにより、データが誤って送られる場合があります。受信側では、その誤りを検知したり、場合によっては訂正するなどの誤り制御をすることで、データの正確性を保ちます。
誤り制御方式には、①パリティビット、②CRC、③ハミング符号、などがあります。

 

2.パリティビット

パリティとは、データの誤りを検知するために付与する冗長ビットのことです。
具体例は、次で説明します。

(1)奇数パリティと偶数パリティ
偶数パリティは、1の数が偶数、奇数パリティは奇数になるようにします。
たとえば、
1000という4ビットデータがあった場合、
➀偶数パリティ
1000 ⇒ 10001 最後に1のパリティを付与
②奇数パリティ
1000 ⇒ 10000 最後に0のパリティを付与します。

もし、途中で1ビットのデータ誤りが発生した場合、上記の偶数パリティが10101になっていれば、1の数が奇数個ですから、データ誤りが発生したことが分かります。しかし、10111というように、2ビットのデータ誤りの場合、1の数が偶数個(つまり正しい)なので、データ誤りを検知できません。
1

(2)垂直パリティと水平パリティ
この下の過去問にありますように、垂直方向か水平方向にチェックするかによって、垂直パリティと水平パリティがあります。
垂直パリティだけですと、1ビットの誤りは検知できますが、どのビットで誤りが発生したかは分かりません。水平パリティと組み合わせることで、どこに誤りが発生したかが分かります。そのビットを反転(0⇒1、1⇒0)させることでデータ誤りの検知だけでなく、訂正まで行うことができます。

3.パリティビットに関する過去問

(1)H27秋AP午前問4

問4 図のように16ビットのデータを4×4の正方形状に並べ,行と列にパリティビットを付加することによって何ビットまでの誤りを訂正できるか。ここで,図の網掛け部分はパリティビットを表す。
パリティ
ア 1  イ 2  ウ 3  エ 4



正解:ア

(2)H25春FE午前問4

問4 通信回線の伝送誤りに対処するパリティチェック方式(垂直パリティ)の記述として,適切なものはどれか。
ア 1ビットの誤りを検出できる。
イ 1ビットの誤りを訂正でき,2ビットの誤りを検出できる。
ウ 奇数パリティならば1ビットの誤りを検出できるが,偶数パリティでは1ビットの誤りも検出できない。
エ 奇数パリティならば奇数個のビット誤りを,偶数パリティならば偶数個のビット誤りを検出できる。

1ビットの誤りまでは検知できますが、それ以上の検知や、誤りの訂正はできません。



正解:ア

 

 

↑このページのトップヘ