信息
消除不确定性的数据
消除的不确定性越多，信息量越大
量化
信息量
I
(
x
i
)
=
log
2
(
1
p
i
)
I(x_i)=\log_2(\frac{1}{p_i})
I(xi)=log2(pi1)
例如52张扑克牌，收到的信息是“卡片花色为红心”，
I
(
h
e
a
r
t
)
=
log
2
(
1
13
/
52
)
=
2
b
i
t
I({\rm heart})=\log_2(\frac{1}{13/52})=2\rm bit
I(heart)=log2(13/521)=2bit
即需要两位编码才可以消除足够的不确定性。
两位编码恰好可以表示四种情况
非整数
两个魔方投出第一个红第二个绿面朝上需要的信息量为
I
(
x
i
)
=
log
2
(
1
1
/
36
)
=
5.17
I(x_i)=\log_2({\frac{1}{1/36}})=5.17
I(xi)=log2(1/361)=5.17
这意味着需要六位编码。然而对于十个连续情况的编码，我们不需要
⌈
5.17
⌉
×
10
=
60
\lceil 5.17\rceil\times 10=60
⌈5.17⌉×10=60位，仅需要
⌈
5.17
×
10
⌉
=
52
\lceil 5.17\times 10\rceil=52
⌈5.17×10⌉=52位。
熵
定义
随机变量的熵是是了解这个随机变量的值时，所收到每份数据中包含的信息量的期望。
H
(
X
)
=
E
(
I
(
X
)
)
=
∑
i
=
1
N
p
i
⋅
log
2
(
1
p
i
)
H(X)=E(I(X))=\sum_{i=1}^N p_i\cdot \log_2(\frac{1}{p_i})
H(X)=E(I(X))=i=1∑Npi⋅log2(pi1)
例如
这告诉我们相较于简单地用两位编码，存在一个更优的编码方式
意义
- 熵是我们需要传输位数的下限
- 为数据传输的优化提供方向
编码
准确的映射
固定长度编码
当每个选择出现的可能性相等
- 支持随机访问：只需要跳过固定长度的编码
H ( x ) = ∑ i = 1 N 1 N log 2 ( 1 1 / N ) = log 2 N H(x)=\sum_{i=1}^N\frac{1}{N}\log_2(\frac{1}{1/N})=\log_2N H(x)=i=1∑NN1log2(1/N1)=log2N
例如对0-9十进制整数编码，需要四位，而熵为 log 2 10 = 3.322 \log_2 10=3.322 log210=3.322，对1000位十进制整数进行固定长度编码需要4000位，大于可能的最小值。
有符号整数
二进制补码定义
取反计算
取反+1
-1的补码为全1，-1-A相当于对A的每一位取反（1-1=0，1-0=1）
可变长度编码
当每个选择的可能性不相等
最优长度编码：哈夫曼编码
检错
存在单位或多位错误时，仅经过简单编码的信息可能发生错误传输
H a m m i n g D i s t a n c e \rm Hamming \ Distance Hamming Distance
在两个相同长度的编码中，相应数字不同的位置数
当汉明距离为0时，两个编码相同
奇偶校验码
解决单位错误（ S i n g l e − b i t e r r o r \rm Single-bit \ error Single−bit error）
做法：使得单位错误无法产生一个新的有效编码，所以需要至少相差两位的编码，也就是我们希望任意编码间的汉明距离至少为2
偶数校验码：在原编码末尾加上一位校验码，使得编码中的1的位数为偶数
有效编码的1的位数均为偶数，当出现01或10的情况时，1的位数为奇数，所以发生了奇偶错误。
同时，当偶数个位上发生了损坏，偶数校验码将无法探测到错误。
推广
为了探测E位错误，最小汉明距离位E+1
从000/111出发，任何长度为2的路径都无法达到一个有效编码。
纠错
E位错误产生的编码集不重叠，即最小汉明距离为2E+1.