IPA 数値表現・論理演算・符号理論 — 頻出論点と過去問

頻出論点

1. この分野は何か

コンピュータの内部で数値や文字、音声などの情報を0と1のビット列としてどう表現し、どのように演算・処理するかの理論的な土台を学ぶ分野です。ビット数で表せる値の範囲や計算の順序で生まれる誤差、送ったデータの誤りを符号で見つけて直す手順など、手を動かして確かめる計算と、用語や式の定義の正確な区別が問われます。

2. 実際の出題のされ方

アナログとディジタルの表現の違いや国際単位系（SI）接頭語の倍率、演繹推論・帰納推論・仮説形成の区別が、ITパスポートの本試験で問われています。具体的な入力と出力の例から演繹推論を選ばせる問題や、帰納推論で得た規則の性質を穴埋めで問う問題が出ています。

応用情報技術者の午前や高度試験の午前Iでは、数値表現の性質、論理・集合演算、誤り検出・訂正符号に関する具体的な計算や式変形が中心になります。数値表現では、2進数の桁数と2乗した値の最大ビット数の関係、2の補数表現で加算結果がオーバフローしない条件、浮動小数点数の計算における桁落ちや情報落ちの判定が出題されています。論理・集合演算では、4変数のカルノー図と等価な論理式の導出や、含意（$\to$）および排他的論理和の相補演算が問われます。あわせて、差集合と補集合の等価な式の選択、ビット演算を用いた循環カウンタの式、数式の逆ポーランド表記法への変換も出ています。符号と文字コードでは、ハミング符号の受信語から誤りビットを特定して訂正する計算、水平垂直パリティチェックで訂正可能なビット数、CRC（巡回冗長検査）の仕組み、XML宣言で符号化宣言を省略できる文字コードが問われています。さらに桁数やデータ量の計算として、英大文字のコードで将来の顧客数をカバーするために必要な最小桁数、音声のA/D変換におけるデータ量計算、ビット誤り率から誤りを含むパケットの期待個数を求める計算も出題されています。

回線のビット誤り率から誤りを含む電文の期待個数を求める計算は、ネットワークスペシャリストの午前IIでも問われています。

データベースや組込みシステムの文脈に沿った計算や状態追跡も、高度試験の午前IIで出題されています。データベーススペシャリストでは関係の属性数から異なる射影の個数を求める部分集合の計算やECCメモリで誤りの検出と訂正に用いる符号の選択、エンベデッドシステムスペシャリストでは組込みシステムの状態遷移図や状態遷移表をイベント発生順にたどって最終状態や表の空欄を特定する問題が出ています。

3. 学習のポイント

2進数と数値演算では、桁数と表現範囲、および誤差の発生条件を整理します。$m$ ビットと $n$ ビットの正の整数を掛けた積は、最大で $m+n$ ビットになります。また、0から $2^k-1$ までを1ずつ増やして0に戻る循環処理では、$k$ 個の1が並んだ値との論理積（AND）をとることで上位ビットの桁上がりを消せます（例: 0〜15なら15とのAND）。負数を2の補数で表す符号付き整数の加算では、同符号同士の加算でのみオーバフローする可能性があり、異符号同士の加算では結果が必ず元の2数の間に収まるためオーバフローしません。浮動小数点数の誤差は、次の4つを発生原因で区別します。

• 桁落ち: 近い値どうしを引くと、そろっていた上位の桁が消え、意味のある桁が少しだけ残ります。
• 情報落ち: 大きさが極端に違う数を足し引きすると、小さい方の値が仮数部に収まらず、結果に反映されません。防ぐには絶対値の小さい数同士を先に計算します。
• 丸め誤差: 仮数部などの決められた桁数に収める際、それより下の桁を切捨て・切上げ・四捨五入して生まれるずれです。
• 打切り誤差: 本来は無限に続く計算を、途中の項で止めて近似値としたために残るずれです。

論理演算・集合・記法では、記号の定義と図表の読み方を押さえます。

• 論理演算とベン図: 含意 $A \to B$ は「$A$ が真かつ $B$ が偽」のときのみ偽となり、前提 $A$ が偽ならば $B$ の真偽にかかわらず真になります。排他的論理和（XOR）の否定（相補演算）は、2入力が一致するときに真となる等価演算（XNOR）であり、ベン図では2つの円の共通部分と両方の円の外側を合わせた領域になります。また、差集合 $X - Y$ は $X \cap \bar{Y}$ と等価です。
• カルノー図: 表の中で値が1のマスを $2^n$ 個（1, 2, 4, 8…）の長方形にまとめ、同じグループ内で0と1の両方をとる変数を共通因数でくくって消去し、残った変数の論理積を論理和でつなぎます。図の左端の列と右端の列、上端の行と下端の行は、変数が1つだけ違う組なので、隣どうしとして同じグループに入れられます。
• 逆ポーランド表記法と部分集合: 逆ポーランド表記法（後置記法）では、演算の優先順位が高い部分から順に、演算子を2つのオペランドの後ろに置く並びへ変換します。また、要素が $n$ 個ある集合の部分集合の総数は、各要素を入れるか入れないかの2通りを掛け合わせた $2^n$ 個になります。

誤り検出・訂正符号では、方式ごとの検出・訂正能力と計算手順を区別します。

• パリティチェックとチェックサム: 1ビットの偶数・奇数パリティやチェックサムは誤りの検出のみを行えます。データを縦横の表の形に並べて行と列にパリティを付加する水平垂直パリティチェックでは、エラーが出た行と列の交点から1ビットの誤りを特定して訂正できます。
• ハミング符号: ハミング符号は、情報ビットに複数の検査ビットを付けて、1ビットの誤りの位置を特定して訂正できる符号です。ECCメモリでは、検査ビットをさらに足して2ビットの誤りの検出もできるようにした形が使われます。問題文で与えられる検査式（$\bmod 2$ の加算や排他的論理和 $\oplus$）に受信語を代入し、成り立たない式の組合せや位置計算式から反転すべきビット位置を特定します。
• CRC（巡回冗長検査）: CRCでは、送信側と受信側が同じ生成多項式を使います。送信側は、データの後ろに生成多項式の次数と同じ個数の0を並べた値を生成多項式で割り、その余りを検査用のデータとして0の部分に入れて送ります。受信側は受け取った全体を同じ生成多項式で割り、余りが0なら誤りなしとみなします。

状態遷移と推論では、条件の追跡方法を確かめます。状態遷移図や状態遷移表では、初期状態からイベントを1つずつ適用して遷移先をたどります。このとき、自分自身の状態にとどまる自己遷移を見落とさないようにします。推論の型は、一般的な前提と個別の事実から論理的必然性をもって結論を導く演繹推論、複数の個別事例から共通する規則を導く（ただし例外があり常に成立するとは限らない）帰納推論、観察された結果と規則から原因となる前提を推測する仮説形成、類似性から性質を当てはめる類推に分けて整理します。

4. 間違えやすいところ

バイトとビットの単位換算を忘れる計算ミスがあります。ビット誤り率から誤りを含むパケット数や電文数の期待値を求める問題では、パケット長や電文長がバイト単位で与えられます。これを8倍してビット数に変換せずにビット誤り率を掛けてしまう誤答肢や、音声のA/D変換のデータ量計算で「サンプリング周波数 × 量子化ビット数 × チャンネル数 × 時間」で求めたビット数を8で割らずにそのままバイト数として答えてしまう誤答肢が作られています。計算の前後で単位がビットかバイトかを必ず確かめます。

また、符号や誤差の性質を取り違えた選択肢にも注意が必要です。

• CRCの割り算の対象: 受信側が「付加されてきた検査用のデータで検査対象のデータを割り」とする誤答肢や、「検査用のデータは，検査対象のデータを生成多項式で処理して得られる1ビットの値である」とする誤答肢があります。
• 水平垂直パリティの訂正限界: 行と列にパリティを付加したとき、2ビットの誤りでは交点の候補が複数生じて位置を特定できず、長方形の頂点にあたる4ビットが同時に反転した場合は行・列ともにパリティが合ってしまい検出さえできません。
• オーバフロー条件の境界値: 8ビットの2の補数表現（$-128 \sim 127$）で $100 + 50$ を計算すると、どちらも $127$ 以下なのに和が $127$ を超えてオーバフローします。個々の値が表現範囲内でも、同符号どうしの和は範囲を超えることがあります。
• 浮動小数点数の加算順序: 情報落ちを問う問題では、指数の大きい数と小さい数を先に加減算してしまうと、その時点で小さい数の有効桁が仮数部のビット数からあふれて失われます。括弧の位置によってどの2数を先に計算するかを順に追い、正規化後の仮数部が指定ビット数に収まるかを確認します。