情報量と符号化｜何ビットで何通り、標本化とオーダー記法【基本情報技術者試験 科目A】

科目A 第1章 基礎理論1-7　情報量と符号化最終更新 2026-09-26

コンピュータは 0 と 1 しか持てません。 そこで必要になるのが、ほしいものを 0 と 1 の並びに置き換えるという考え方です。 この回では、何ビットで何通り表せるかから始めて、音や画像を数字にする流れ、 誤りを見つける仕組み、圧縮、そして処理時間の見積り方（オーダー記法）までを扱います。

n ビットで 2 の n 乗通り

1桁の2進数（1ビット）で表せるのは 0 と 1 の2通りです。桁を1つ増やすと、 それぞれに 0 と 1 が付くので2倍になります。

1 ビット   2 通り     （0, 1）
2 ビット   4 通り     （00, 01, 10, 11）
3 ビット   8 通り     （000 〜 111）
8 ビット  256 通り   （2 を 8 回かけた数）

n ビットで 2 の n 乗通り。逆に「1000種類を表したい」なら、2 の 10 乗＝1024 なので 10 ビット必要です。

文字コードも色の指定も、この数え方でビット数が決まります。 1文字を8ビットで表せば256種類、16ビットなら65,536種類です。

情報量 ── 珍しい知らせほど大きい

「表か裏か」を伝えるには1ビットあれば足ります。では「8通りのうちどれか」なら3ビットです。 何通りを区別できたかが、そのまま知らせの大きさになります。これが情報量で、単位はビットです。

起こる確率が小さいほど、その知らせの情報量は大きくなります。 「2分の1のくじに当たった」より「1024分の1のくじに当たった」のほうが、驚きも情報量も大きい、という扱いです。 確率 p のときの情報量は 2 を何回かけると 1/p になるかで、log を使って log₂(1/p) と書きます。

アナログをデジタルにする ── 標本化・量子化・符号化

音や温度は、なめらかに変化するアナログの量です。 これを 0 と 1 にするには、3つの段階を踏みます。

どちらをどこまで細かくするかが、音質とファイルサイズの釣り合いです。

誤りを見つける ── パリティ

送る途中で 0 と 1 が化けることがあります。そこで、確かめ用の1桁を足して送ります。

送るデータ　 1 0 1 1 0 0 1　　1 の個数は 4 個＝偶数
パリティ　　 0　　　　　　　　偶数のままにしたいので 0 を付ける
送る並び　　 1 0 1 1 0 0 1 0

受け取った　 1 0 1 0 0 0 1 0　1 の個数が 3 個＝奇数 → 誤りがある

1 の個数を偶数に保つのが偶数パリティ。1桁の誤りは見つかりますが、どの桁かは分かりませんし、2桁同時に化けると見逃します。

パリティのように見つけるだけの仕組みを誤り検出、 どの桁が化けたかまで特定して直せる仕組みを誤り訂正といいます。 訂正には、より多くの確かめ用の桁が必要です。

圧縮 ── よく出るものを短くする

すべての文字を同じ長さで表すと、よく出る文字も珍しい文字も同じビット数を使います。 よく出る文字を短くすれば、全体は短くなります。この考え方がハフマン符号です。

同じ100文字が 150 ビットで送れました。すべて2ビットにすると200ビットなので、4分の1短くなっています。 よく出る A を1ビットにできたぶんが、そのまま効いています。

符号は途中で区切りが分かるように選びます。 かりに A を 0、B を 01、C を 1 と割り当てると、 受け取った 01 が B なのか A・C なのか決まりません。

どの符号も、ほかの符号の先頭にならないように選びます。 上の割り当てでは、A に 0 を渡したので、残りはすべて 1 で始まる側（10 と 11）に置けます。 こうすると衝突が起きず、区切り記号なしで読めます。

文字コード

文字も番号で表します。どの文字に何番を割り当てるかの取り決めが文字コードです。

⚠️ 同じ日本語でも方式ごとに番号が違うので、送る側と受け取る側で方式が食い違うと文字化けします。

計算量 ── データが増えたとき、どれだけ遅くなるか

処理の速さは、データが増えたときの伸び方で表します。この表し方がオーダー記法です。

オーダーが見ているのは「何秒かかるか」ではなく「データが増えたときに何倍になるか」です。 どの解き方が速いかは、この伸び方の違いで決まります。 探索や整列それぞれのオーダーは、アルゴリズムを扱う第2章でまとめて見ます。

まとめ

次に読む