情報量と符号化とは？エントロピー・デジタル符号化・データ圧縮を基礎から理解しよう

はじめに

コンピュータは、文字・画像・音声など、さまざまな情報を扱っています。

しかし、コンピュータ内部では、それらの情報を最終的に0と1の組合せとして扱います。

そのためには、

情報にはどれくらいの量があるのか
アナログ情報をどうやってデジタル化するのか
情報をどうやって0と1へ変換するのか
データ量をどうすれば小さくできるのか

といった考え方が重要になります。

この記事では、

ビット
自己情報量
エントロピー
符号化
デジタル符号化
標本化・量子化・符号化
固定長符号・可変長符号
ランレングス符号化
ハフマン符号
可逆圧縮・非可逆圧縮
誤り検出・訂正

について順番に整理していきます。

1. コンピュータは情報を0と1で表す

コンピュータ内部では、基本的に情報を2進数として扱います。

つまり、

0
1

という2つの状態を組み合わせて情報を表現します。

0または1の1桁分を、**bit（ビット）**と呼びます。

bitはbinary digitを由来とする言葉です。

1ビットで表現できる状態は、

0
1

の2通りです。

2ビットなら、

の4通り。

3ビットなら8通りです。

つまり、nビットで表現できる状態数は、

2^n

となります。

🍯 はちみつメモ

nビットでは2^n通りの状態を表現できます。

1ビット → 2通り
2ビット → 4通り
3ビット → 8通り

2. 情報量とは

情報量とは、

ある出来事が起きたことで、どのくらいの情報を得られたのか

を数値として考えたものです。

ポイントは、

起こりにくい出来事ほど情報量が大きい

ということです。

例えば、

明日も太陽が昇る

と聞いても、それほど驚きません。

一方、

真夏の東京で雪が降った

と言われれば、かなり意外に感じます。

つまり、

起こりやすい
↓
予想しやすい
↓
情報量が小さい

一方で、

起こりにくい
↓
予想しにくい
↓
情報量が大きい

という関係があります。

3. 自己情報量

ある事象が発生する確率をpとしたとき、その事象が起こったことで得られる情報量を自己情報量と呼びます。

自己情報量Iは、

I = -log₂p

または、

I = log₂(1 / p)

で求められます。

単位はbitです。

確率が小さいほど、情報量は大きくなります。

4. 自己情報量を計算してみよう

例えば、公平なコインを投げて表が出る確率は、

1 / 2

です。

したがって、

I = -log₂(1/2)
  = 1 bit

となります。

確率が1/4なら、

I = -log₂(1/4)
  = 2 bit

です。

同じように、

出現確率	自己情報量
1	0 bit
1/2	1 bit
1/4	2 bit
1/8	3 bit
1/16	4 bit

となります。

必ず発生する確率1の出来事は、

I = -log₂1
  = 0

です。

必ず起こることを知らされても、新しく得られる情報がないためです。

🍯 はちみつメモ

珍しい出来事ほど情報量が大きい。

確率が半分になると、情報量は1ビット増えます。

5. エントロピーとは

実際には、一つの出来事だけでなく、複数の出来事がそれぞれ異なる確率で発生します。

そこで、

1回の出来事から平均してどれくらいの情報を得られるのか

を考えます。

これを平均情報量または**エントロピー（Entropy）**と呼びます。

複数の事象の発生確率を、

p₁, p₂, p₃, ...

とすると、

H = -Σ pᵢ log₂pᵢ

で求められます。

難しそうに見えますが、

それぞれの自己情報量
×
その出来事が起こる確率

をすべて足していると考えればOKです。

6. コイン投げのエントロピー

公平なコインなら、

表：1/2
裏：1/2

です。

表と裏の自己情報量はどちらも1ビットなので、

H
= 1/2 × 1
+ 1/2 × 1

= 1 bit

となります。

一方、

表：90%
裏：10%

のように大きく偏っている場合、結果は予想しやすくなります。

そのため、エントロピーは1ビットより小さくなります。

つまり、

どの結果になるか予測しにくいほどエントロピーは大きくなる

ということです。

7. 自己情報量とエントロピーの違い

この2つは混同しやすいので整理しておきましょう。

用語	意味
自己情報量	ある1つの出来事から得られる情報量
エントロピー	すべての出来事を考えた平均情報量

例えば、

サイコロで6が出た

という1回の結果を見るのが自己情報量です。

一方、

サイコロを何度も振ったとき、
1回あたり平均してどれくらい情報が得られるか

を考えるのがエントロピーです。

8. 符号化とは

コンピュータで情報を扱うためには、文字・画像・音声などをコンピュータが扱える形式へ変換する必要があります。

このように、

情報を一定のルールに従って別の表現へ変換すること

を**符号化（Encoding）**といいます。

例えば、

A → 00
B → 01
C → 10
D → 11

と決めれば、A〜Dという4種類の情報を2ビットで表現できます。

9. デジタル符号化とは

私たちの身の回りには、音声などの連続的に変化するアナログ情報があります。

一方、コンピュータは0と1で表されるデジタル情報を扱います。

そのため、アナログ情報をコンピュータで扱うためには、

アナログ情報
↓
デジタル情報

へ変換する必要があります。

代表的な方法が**PCM（Pulse Code Modulation：パルス符号変調）**です。

PCMでは、主に次の3段階でアナログ信号をデジタル化します。

標本化
 ↓
量子化
 ↓
符号化

この3つはセットで覚えておきましょう。

10. 標本化

最初に行うのが**標本化（Sampling）**です。

アナログ信号は連続的に変化しています。

そこで、一定の時間間隔で信号の値を取り出します。

イメージとしては、

連続した音の波

～～～～～～～～～～～～

一定間隔で測定

●   ●   ●   ●   ●   ●

のようなものです。

つまり標本化とは、

連続しているアナログ信号を一定間隔で測定すること

です。

この測定を1秒間に何回行うかを**標本化周波数（サンプリング周波数）**と呼びます。

単位はHzです。

例えば、

44,100 Hz

なら、1秒間に44,100回測定します。

11. 標本化定理

アナログ信号を正しくデジタル化するためには、十分な回数の標本化が必要です。

ここで使われるのが標本化定理です。

標本化定理では、

元の信号に含まれる最高周波数の2倍以上の周波数で標本化する

必要があります。

例えば、最高周波数が20kHzなら、

20kHz × 2 = 40kHz

なので、40kHz以上で標本化する必要があります。

これより低い周波数で標本化すると、元の信号を正しく再現できなくなる可能性があります。

🍯 はちみつメモ

標本化周波数は、元の信号の最高周波数の2倍以上。

12. 量子化

標本化によって取り出した信号の値は、そのままでは連続的な値です。

そこで、値をいくつかの段階に分けます。

これが**量子化（Quantization）**です。

例えば、

0 ～ 10

という値を、

のような決められた段階に当てはめるイメージです。

本来の値が、

5.37

だったとしても、

のように最も近い段階へ変換します。

このとき、本来の値との差が発生します。

これを量子化誤差と呼びます。

13. 量子化ビット数

量子化の細かさは、使用するビット数によって変わります。

例えば4ビットなら、

2^4 = 16

なので、16段階に分けられます。

8ビットなら、

2^8 = 256

段階です。

16ビットなら、

2^16 = 65,536

段階です。

ビット数を増やすほど細かい値を表現できるため、元の信号をより正確に表現できます。

ただし、その分データ量も増えます。

14. 最後に符号化する

標本化と量子化が終わったら、量子化された値を0と1へ変換します。

これが符号化です。

例えば量子化された値が、

であれば、2進数では、

のように表現できます。

これで、

アナログ信号
↓
標本化
↓
量子化
↓
符号化
↓
デジタルデータ

という変換が完了します。

15. PCMのデータ量

デジタル化された音声などのデータ量は、

標本化周波数
×
量子化ビット数
×
チャネル数
×
時間

で求められます。

例えば、

標本化周波数：44,100 Hz
量子化ビット数：16 bit
チャネル数：2（ステレオ）
時間：1秒

なら、

44,100 × 16 × 2

= 1,411,200 bit

です。

つまり約1.411Mbpsになります。

データサイズをByteで求めたい場合は、

1 Byte = 8 bit

なので8で割ります。

応用情報では、このような音声データ量の計算にも注意しましょう。

16. 固定長符号

すべての情報に同じ長さの符号を割り当てる方式を固定長符号といいます。

例えば、

文字	符号
A	00
B	01
C	10
D	11

では、すべて2ビットです。

固定長符号では符号の長さが同じなので、どこで区切ればよいのか分かりやすいという特徴があります。

17. 固定長符号に必要なビット数

N種類の情報を表すためには、

2^n ≧ N

を満たす最小のnビットが必要です。

例えば8種類なら、

2^3 = 8

なので3ビットです。

10種類なら、

2^3 = 8

では足りないため、

2^4 = 16

となり、4ビット必要です。

18. 可変長符号

すべてを同じ長さにするのではなく、情報によって符号の長さを変える方式を可変長符号といいます。

例えば、

A → 0
B → 10
C → 110
D → 111

のようなものです。

よく登場するAには短い符号を割り当て、あまり登場しないCやDには長い符号を割り当てています。

このようにすることで、平均的なデータ量を小さくできます。

19. 接頭語符号

可変長符号では、符号の区切りが分からなくならないように注意する必要があります。

そこで、

ある符号が、別の符号の先頭部分にならない

ように作られた符号を**接頭語符号（Prefix Code）**と呼びます。

例えば、

A → 0
B → 10
C → 110
D → 111

なら、どの符号も他の符号の先頭部分にはなっていません。

そのため、先頭から順番に読み取れます。

20. データ圧縮とは

情報をそのまま保存すると、大きなデータ容量が必要になる場合があります。

そこで、

データの内容をできるだけ保ちながら、必要なデータ量を小さくする

のがデータ圧縮です。

圧縮には大きく、

可逆圧縮
非可逆圧縮

があります。

21. 可逆圧縮

**可逆圧縮（Lossless Compression）**は、

圧縮したデータを完全に元へ戻せる圧縮方式

です。

プログラムや文章など、1ビットでも内容が変わると困るデータに向いています。

代表的な考え方として、

ランレングス符号化
ハフマン符号

などがあります。

22. ランレングス符号化

**ランレングス符号化（Run-Length Encoding：RLE）**は、

同じデータが連続している部分を「データと連続回数」の組合せで表す方法

です。

例えば、

AAAAABBBBCCCCCC

というデータがあったとします。

そのまま記録すると、

AAAAABBBBCCCCCC

ですが、ランレングス符号化を使うと、

A5B4C6

のように、

Aが5回
Bが4回
Cが6回

として表現できます。

同じデータが長く続いているほど、効率よく圧縮できます。

23. ランレングス符号化が得意なデータ

例えば、

AAAAAAAAAAAAAAAAAAAA

のようなデータなら、

A20

と表現できるため、大きく圧縮できます。

そのためランレングス符号化は、

同じ値が長く連続するデータ

と相性が良い方式です。

例えば、単純な画像データなどで効果を発揮する場合があります。

24. ランレングス符号化が苦手なデータ

一方、

ABCDEFGH

のように、ほとんど同じデータが連続しない場合を考えてみます。

これをランレングス符号化すると、

A1B1C1D1E1F1G1H1

のようになります。

元のデータより長くなってしまいました。

つまり、

ランレングス符号化は必ずデータを小さくできるわけではない

ということです。

🍯 はちみつメモ

ランレングス符号化は、

「同じものが何回続いているか」を記録する圧縮方式。

同じ値が長く連続するデータほど効果的です。

25. ハフマン符号

出現頻度を利用して効率のよい可変長符号を作る代表的な方法が**ハフマン符号（Huffman Coding）**です。

基本的な考え方は、

よく登場するデータには短い符号、あまり登場しないデータには長い符号を割り当てる

ことです。

例えば、

文字	出現確率
A	0.5
B	0.25
C	0.125
D	0.125

とします。

出現確率の小さいものから順番に組み合わせていきます。

最初に、

C = 0.125
D = 0.125

をまとめ、

C + D = 0.25

とします。

次に、

B = 0.25
C+D = 0.25

をまとめます。

最後にAとまとめると、

            1.0
           /   \
       A 0.5    0.5
               /   \
           B 0.25   0.25
                   /    \
               C .125  D .125

という木構造になります。

枝に0と1を割り当てると、例えば、

A → 0
B → 10
C → 110
D → 111

とできます。

26. ハフマン符号の平均符号長

先ほどの例では、

A → 1ビット
B → 2ビット
C → 3ビット
D → 3ビット

です。

平均符号長は、

0.5 × 1
+ 0.25 × 2
+ 0.125 × 3
+ 0.125 × 3

となり、

1.75 bit

です。

固定長なら4種類を表現するため、

2 bit

必要です。

したがって、

固定長符号     ：2 bit
ハフマン符号   ：平均1.75 bit

となり、ハフマン符号の方が平均的には短くできます。

27. ランレングス符号とハフマン符号の違い

どちらもデータを圧縮する方法ですが、利用している特徴が異なります。

方式	利用する特徴
ランレングス符号化	同じデータが連続すること
ハフマン符号	データごとの出現頻度の違い

ランレングス符号化では、

AAAAAA
↓
A6

のように連続性を利用します。

ハフマン符号では、

よく登場するA
↓
短い符号

あまり登場しないD
↓
長い符号

のように出現確率を利用します。

この違いはしっかり整理しておきましょう。

28. エントロピーとハフマン符号

ここで、情報量の話と符号化がつながります。

エントロピーは、

情報源が持つ平均的な情報量

でした。

一方ハフマン符号では、

平均的な符号長をできるだけ短くする

ことを目指します。

つまり、効率のよい符号化では、

平均符号長をエントロピーにできるだけ近づける

ことが重要になります。

29. 非可逆圧縮

もう一つが**非可逆圧縮（Lossy Compression）**です。

非可逆圧縮では、

一部の情報を削除する代わりに、データ量を大きく減らす

ことができます。

ただし、一度削除した情報を完全に元へ戻すことはできません。

主に、

画像
音声
動画

など、人間が多少の違いを認識しにくいデータで利用されます。

つまり、

可逆圧縮
→ 完全に元へ戻せる

非可逆圧縮
→ 完全には元へ戻せない

という違いがあります。

30. 文字の符号化

文字も、そのままではコンピュータで扱えません。

そこで、

文字
↓
数値
↓
0と1

という形で対応付けます。

このために使われるのが文字コードです。

代表的なものには、

ASCII
Unicode
UTF-8

などがあります。

例えば文字「A」に特定の数値を割り当て、その数値を2進数で表現することで、コンピュータでも文字を扱えるようになります。

31. 誤り検出・訂正のための符号化

符号化はデータ量を小さくするためだけのものではありません。

通信中にデータが壊れていないか確認するため、

あえて余分な情報を追加する

場合もあります。

代表的なものには、

パリティビット
CRC
ハミング符号

などがあります。

こちらではデータを減らすのではなく、むしろ情報を追加することで、

データが壊れていないか確認する

あるいは、

壊れたデータを訂正する

ことを可能にします。

32. 「符号化」という言葉を整理しよう

ここまで見ると、「符号化」という言葉がいろいろな場面に登場します。

整理すると、

アナログ情報をデジタル化する
        ↓
PCMなどのデジタル符号化

文字をコンピュータで表す
        ↓
文字コード

データを小さくする
        ↓
ランレングス符号
ハフマン符号

通信エラーに備える
        ↓
パリティ
CRC
ハミング符号

のように、目的によってさまざまな符号化があります。

共通しているのは、

情報を一定の規則に従って別の形で表現する

という点です。

33. 全体の流れを整理しよう

今回の内容を一本につなげてみます。

情報
 ↓
コンピュータでは0と1で扱う
 ↓
bit
 ↓
情報量
 ↓
自己情報量
 ↓
平均情報量
 ↓
エントロピー

一方、実際の情報をコンピュータへ取り込む場合は、

アナログ情報
 ↓
標本化
 ↓
量子化
 ↓
符号化
 ↓
デジタルデータ

となります。

さらに、作られたデータを効率よく保存するために、

データ圧縮
 ↓
ランレングス符号
ハフマン符号

などを利用します。

34. 試験で押さえたいポイント

最後に、応用情報技術者試験で特に押さえておきたい部分を整理しましょう。

自己情報量

I = -log₂p

確率が小さいほど情報量は大きくなります。

エントロピー

H = -Σ pᵢ log₂pᵢ

平均情報量を表します。

nビットで表現できる状態

2^n

通りです。

PCM

標本化
 ↓
量子化
 ↓
符号化

の順番です。

標本化定理

標本化周波数
≧
最高周波数 × 2

です。

PCMのデータ量

標本化周波数
×
量子化ビット数
×
チャネル数
×
時間

で求めます。

ランレングス符号化

AAAAAA
↓
A6

のように、同じデータの連続回数を利用します。

ハフマン符号

出現確率の小さいものから組み合わせて木を作る

ことが基本です。

そして、

出現頻度が高いものほど短い符号

になります。

まとめ

今回は、情報量と符号化について学びました。

この記事で覚えること

コンピュータは情報を0と1で表現する
nビットでは2^n通りを表現できる
自己情報量は-log₂pで求める
起こりにくい出来事ほど情報量が大きい
エントロピーは平均情報量
符号化とは情報を一定のルールで別の表現へ変換すること
PCMでは標本化→量子化→符号化の順に処理する
標本化周波数は最高周波数の2倍以上必要
量子化ビット数を増やすと細かく値を表現できる
固定長符号はすべて同じ長さ
可変長符号は情報によって符号長を変える
ランレングス符号化は同じデータの連続を利用する
ハフマン符号は出現頻度の差を利用する
可逆圧縮は元データを完全に復元できる
非可逆圧縮は一部の情報を削除する
符号化はデータ圧縮だけでなく誤り検出・訂正にも利用される

🍯 はちみつメモ

情報量と符号化は「情報をどう0と1で効率よく扱うか」を考える分野です。

情報量では、

珍しい出来事ほど情報量が大きい。

デジタル化では、

標本化 → 量子化 → 符号化。

圧縮では、

ランレングス符号 = 連続をまとめる
ハフマン符号 = よく出るものを短くする

と整理しておきましょう。