情報理論 において、シャノンの情報源符号化定理 （シャノンのじょうほうげんふごうかていり、英語 : Shannon's source coding theorem, noiseless coding theorem ）は、データ圧縮 の可能な限界と情報量 （シャノンエントロピー）の操作上の意味を確立する定理である。1948年のクロード・シャノン の論文『通信の数学的理論 』で発表された。シャノンの第二基本定理（通信路符号化定理 ）に対してシャノンの第一基本定理 とも言う。
情報源符号化定理によれば、（独立同分布 (iid)の確率変数 のデータの列の長さが無限大 に近づくにつれて）、符号化率 （記号1つ当たりの平均符号長）が情報源のシャノンエントロピーよりも小さいデータを、情報が失われることが事実上確実ではないように圧縮することは不可能である。しかし、損失の可能性が無視できる場合、符号化率を任意にシャノンエントロピーに近づけることは可能である。
シンボルコードの情報源符号化定理は、入力語（確率変数と見なされる）のエントロピーとターゲットアルファベットの大きさの関数として、符号語の可能な期待される長さに上限と下限を設定する。
編集
情報源符号化 とは、情報源の記号（の列）からアルファベット記号（通常はビット）の列への写像 である。情報源の記号は二進数ビットから正確に復元できる（可逆圧縮）か、何らかの歪みを伴って復元される（非可逆圧縮）。これが、データ圧縮 の背後にあるコンセプトである。
編集
情報源符号化定理 (Shannon 1948)[ 1] [ 2] [ 3]
情報量 H (X )N 個の独立同分布 の確率変数は、N → ∞N H (X )ビット 以上に圧縮できる。しかし、N H (X )
編集
Σ1 , Σ2 を2つの有限のアルファベットとし、Σ∗ と Σ∗ をそれぞれのアルファベットからの全ての有限語の集合 とする。
X を Σ1 の値をとる確率変数とし、 f を Σ∗ から Σ∗ への一意復号可能な符号 とする（ここで、|Σ2 | = a ）。S を単語長 f (X ) で与えられる確率変数とする。
f が X の最小単語長さという意味で最適であるとき、
H
(
X
)
log
2
a
≤
E
S
<
H
(
X
)
log
2
a
+
1
{\displaystyle {\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} S<{\frac {H(X)}{\log _{2}a}}+1}
である。(Shannon 1948)
編集
編集
X が独立同分布 (iid)な情報源であるとき、その時系列 X 1 , ..., Xn エントロピー H (X )差分エントロピー で独立同分布となる。情報源符号化定理によれば、情報源のエントロピーより大きい任意のレート の任意の ε > 0n と、情報源 X 1:n n 個の複写をとり、これを n (H (X ) + ε )1 − ε の確率で、情報源記号 X 1:n
達成可能性の証明 。 いくつかの ε > 0
p
(
x
1
,
…
,
x
n
)
=
Pr
[
X
1
=
x
1
,
⋯
,
X
n
=
x
n
]
.
{\displaystyle p(x_{1},\ldots ,x_{n})=\Pr \left[X_{1}=x_{1},\cdots ,X_{n}=x_{n}\right].}
とする。典型集合 （英語版 ） A ε n
A
n
ε
=
{
(
x
1
,
⋯
,
x
n
)
:
|
−
1
n
log
p
(
x
1
,
⋯
,
x
n
)
−
H
n
(
X
)
|
<
ε
}
{\displaystyle A_{n}^{\varepsilon }=\left\{(x_{1},\cdots ,x_{n})\ :\ \left|-{\frac {1}{n}}\log p(x_{1},\cdots ,x_{n})-H_{n}(X)\right|<\varepsilon \right\}}
漸近的等分配性 （英語版 ） n に対して、情報源によって生成された列が典型集合 A ε n n に対しては、
P
(
(
X
1
,
X
2
,
⋯
,
X
n
)
∈
A
n
ε
)
{\displaystyle P((X_{1},X_{2},\cdots ,X_{n})\in A_{n}^{\varepsilon })}
1
−
ε
{\displaystyle 1-\varepsilon }
典型集合の定義は、典型集合にある列が以下を満足することを意味する。
2
−
n
(
H
(
X
)
+
ε
)
≤
p
(
x
1
,
⋯
,
x
n
)
≤
2
−
n
(
H
(
X
)
−
ε
)
{\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p\left(x_{1},\cdots ,x_{n}\right)\leq 2^{-n(H(X)-\varepsilon )}}
注意:
A ε n
(
X
1
,
X
2
,
⋯
X
n
)
{\displaystyle (X_{1},X_{2},\cdots X_{n})}
1 − ε より大きい。
p
(
x
1
,
x
2
,
⋯
x
n
)
{\displaystyle p(x_{1},x_{2},\cdots x_{n})}
|
A
n
ε
|
≤
2
n
(
H
(
X
)
+
ε
)
{\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )}}
p
(
x
1
,
x
2
,
⋯
x
n
)
{\displaystyle p(x_{1},x_{2},\cdots x_{n})}
A ε n
|
A
n
ε
|
≥
(
1
−
ε
)
2
n
(
H
(
X
)
−
ε
)
{\displaystyle \left|A_{n}^{\varepsilon }\right|\geq (1-\varepsilon )2^{n(H(X)-\varepsilon )}}
よって、
|
A
n
ε
|
≤
2
n
(
H
(
X
)
+
ε
)
,
n
.
(
H
(
X
)
+
ε
)
{\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )},n.(H(X)+\varepsilon )}
エンコードアルゴリズム : エンコーダは、入力列が典型集合内にあるかどうかをチェックする。そうであれば、典型集合内の入力列のインデックスを出力する。そうでなければ、エンコーダは任意の n (H (X ) + ε )1 − ε の確率で）、エンコーダは何の誤りも生じない。従って、エンコーダの誤りの確率の上限は ε である。
逆の証明。 その逆 は、A ε n
編集
1 ≤ i ≤ n について、si xi
q
i
=
a
−
s
i
/
C
{\displaystyle q_{i}=a^{-s_{i}}/C}
C は q 1 + ... + qn = 1
H
(
X
)
=
−
∑
i
=
1
n
p
i
log
2
p
i
≤
−
∑
i
=
1
n
p
i
log
2
q
i
=
−
∑
i
=
1
n
p
i
log
2
a
−
s
i
+
∑
i
=
1
n
p
i
log
2
C
=
−
∑
i
=
1
n
p
i
log
2
a
−
s
i
+
log
2
C
≤
−
∑
i
=
1
n
−
s
i
p
i
log
2
a
≤
E
S
log
2
a
{\displaystyle {\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&\leq -\sum _{i=1}^{n}p_{i}\log _{2}q_{i}\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\sum _{i=1}^{n}p_{i}\log _{2}C\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\log _{2}C\\&\leq -\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\\&\leq \mathbb {E} S\log _{2}a\\\end{aligned}}}
ここで、2行目はギブスの不等式 に、5行目はクラフトの不等式 による。
C
=
∑
i
=
1
n
a
−
s
i
≤
1
{\displaystyle C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1}
よって log C ≤ 0 である。
2行目の不等式について、
s
i
=
⌈
−
log
a
p
i
⌉
{\displaystyle s_{i}=\lceil -\log _{a}p_{i}\rceil }
とすると、
−
log
a
p
i
≤
s
i
<
−
log
a
p
i
+
1
{\displaystyle -\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1}
であり
a
−
s
i
≤
p
i
{\displaystyle a^{-s_{i}}\leq p_{i}}
であり
∑
a
−
s
i
≤
∑
p
i
=
1
{\displaystyle \sum a^{-s_{i}}\leq \sum p_{i}=1}
よって、クラフトの不等式には、これらの語長を持つ接頭辞のない符号が存在する。従って、最小の S は以下を満たす。
E
S
=
∑
p
i
s
i
<
∑
p
i
(
−
log
a
p
i
+
1
)
=
∑
−
p
i
log
2
p
i
log
2
a
+
1
=
H
(
X
)
log
2
a
+
1
{\displaystyle {\begin{aligned}\mathbb {E} S&=\sum p_{i}s_{i}\\&<\sum p_{i}\left(-\log _{a}p_{i}+1\right)\\&=\sum -p_{i}{\frac {\log _{2}p_{i}}{\log _{2}a}}+1\\&={\frac {H(X)}{\log _{2}a}}+1\\\end{aligned}}}
編集
編集
典型集合 A ε n
A
n
ε
=
{
x
1
n
:
|
−
1
n
log
p
(
X
1
,
⋯
,
X
n
)
−
H
n
¯
(
X
)
|
<
ε
}
{\displaystyle A_{n}^{\varepsilon }=\left\{x_{1}^{n}\ :\ \left|-{\frac {1}{n}}\log p\left(X_{1},\cdots ,X_{n}\right)-{\overline {H_{n}}}(X)\right|<\varepsilon \right\}}
と定義する。
次に、与えられた δ > 0n が十分に大きい場合、 Pr(A ε n δ である。あとは、典型集合の列をエンコードするだけであり。情報源符号化の通常の方法は、この集合の濃度 が
2
n
(
H
n
¯
(
X
)
+
ε
)
{\displaystyle 2^{n({\overline {H_{n}}}(X)+\varepsilon )}}
1 − δ より大きい確率で符号化するには、平均して Hn X ) + ε n を大きくすることによって、ε と δ を任意に小さくすることができる。
編集
編集
^ C.E. Shannon , "A Mathematical Theory of Communication ", Bell System Technical Journal ^ David J. C. MacKay. Information Theory, Inference, and Learning Algorithms ISBN 0-521-64298-1
^ Cover, Thomas M. (2006). “Chapter 5: Data Compression”. Elements of Information Theory . John Wiley & Sons. ISBN 0-471-24195-4
![{\displaystyle p(x_{1},\ldots ,x_{n})=\Pr \left[X_{1}=x_{1},\cdots ,X_{n}=x_{n}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1baf624e1a98b895c1c370d0da4c8f5a2bafca8)
