6.004 L01

2021年09月15日 阅读数:3
这篇文章主要向大家介绍6.004 L01,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
Basics of Information

本章目的: 学习使用bit编码信息的不一样方法而且学习帮助肯定编码是否正确的数学工具.算法


6.004 L01_子树

什么是信息? 已传达或接收的数据, 用来解决特定事实或状况的不肯定性(接收数据后, 会知道更多特定事实或状况)ide

例子: 从52张扑克中选一张, 若是不知道任何数据, 有52种可能, 但若是有如下数据:工具

  • 已知是红心: 13种可能.
  • 已知不是黑桃A: 51种可能.
  • 已知是J, Q或K: 12种可能.
  • 已知是红心K: 就是红心K一种.

以上4个哪一个数据包含的信息最多(哪一个数据解决的最多的不肯定性)?学习


6.004 L01_子树_02

经过随机变量来给特定状况的不肯定性建模. 例若有N个不一样选择, 使用一个离散随机变量X. 有N个可能的值\(\left\{x_{1}, x_{2}, \ldots, x_{N}\right\}\). 每一个都对应一个几率: \(x_1\)的几率为\(p_1\). 几率越小, X越大.编码

 

\[I\left(x_{i}\right)=\log _{2} \frac{1}{p_{i}} \mathrm{bits} \]

 

选择的不肯定性与其几率成反比. 使用\(log_2\)是由于一个bit为0或1. \(I(x_i)\)为接收数据\(x_i\)所得信息.3d


6.004 L01_子树_03

假设接收的数据并无解决全部的不肯定性(已知是红心的牌, 但还不知道确切的哪张牌, 因此不肯定性还在.)orm

经过式子:对象

 

\[I(\text { data })=\log _{2} \frac{1}{p_{\text {data }}} \text { bits } \]

 

红心有13张牌, 总共52张, 那么几率为13/52 = 0.25. 代入式子:blog

 

\[I(\text { heart })=\log _{2} \frac{1}{p_{\text {heart }}}=\log _{2} \frac{1}{0.25}=2 \text { bits } \]

 

当有M个相同几率(1/N)同时发生, 总几率为M(1/N), 因此为:字符串

 

\[I(\mathrm{~N} \text { choices } \rightarrow \mathrm{M} \text { choices })=\log _{2} \frac{1}{M(1 / N)}=\log _{2} \frac{N}{M} \text { bits. } \]

 


6.004 L01_子树_04

几个例子:

  • 投一个硬币(正反面), 两种可能, 每种可能为1/2. 须要\(\log _{2}(2 / 1)=1 \mathrm{bit}\)(1正, 0反).
  • 已知下一张牌是红心, 须要\(\log _{2}(52 / 13)=2\)bit的信息.
  • 投一次两个骰子, 每一个6个面, 总共36种可能, \(\log _{2}(36 / 1)=5.17\)bit. 向上取整须要6bit. 但若是投10次, 须要52bit来编码.

6.004 L01_子树_05

表中显示接收不一样数据的多种可能. 能够看出, 数据解决的不肯定性越多, 收到信息越多.


6.004 L01_变长编码_06

H(X): 离散随机变量的熵, 是X值接受信息的平均值.

 

\[H(X)=E(I(X))=\sum_{i} p_{i} \log _{2} \frac{1}{p_{i}} \]

 


6.004 L01_信息内容_07


6.004 L01_补码_08

使用0或1序列编码数据时, 在bit字符串和数据集合之间的映射要明确.


6.004 L01_信息内容_09

能够编码为一个二叉树, 将编码的对象放在树的叶. 如上图, B离根的长度为1, A为2, C,D为3.


6.004 L01_信息内容_10

固定长度编码: 全部叶到根的距离都相同.

固定长度编码能够支持随机访问.

N个同可能的元素的熵为\(\log _{2}(N)\). 例如, 有10个不一样的数字, 使用一个4-bit 代码来表明这10种可能, 那么其熵为\(\log _{2}(10)=3.322bits\). 形成效率低下.


6.004 L01_子树_11

使用0, 1表明十进制数. 对N-bit的二进制表示, 把每一个位乘权重. N-bit所能表明的最小数位0(每一个位为0), 最大数是\(2^N-1\)(全部位为1).


6.004 L01_补码_12

每4位当作一组, 每组都表明一个十六进制数字.


6.004 L01_子树_13

经过给二进制串最前面分配一个符号位, 若是为0, 表示正数, 若是为1, 表示负数. 0能够被表示为+0或-0. 电路须要执行加法和减法两种方法, 这会有一点麻烦.


6.004 L01_信息内容_14

经过二进制补码来简化电路.

二进制补码: 假设一个N-bit的二进制补码, 最高位为负(\(-2^{N-1}\)), 其余位为正.

  • 最高位为1, 该数为负数.
  • 最小负数: 10…0000(\(-2^{N-1}\)).
  • 最大正数: 01…1111(\(+2^{N-1}-1\)).
  • 全部位为1: 11…1111(-1).
  • 全部位为0: 00…0000(0).

6.004 L01_数据_15

当N-bit值加上1, 例如: 11…1111 加上 00…0001, 结果为00…0000.

为了计算B-A, 以及改变式子: B+(-A). 给定A的二进制补码, 求出-A的二进制补码.

  • 首先, A+(-A) = 0.
  • 由之间推导, 0 = -1 + 1. 因此-A = 1+(-1) - A.
  • -1的二进制补码上的每一个位为1, 因此(-1-A)能够当作A的每一个位上取反.
  • 因此-A = ~A + 1.

6.004 L01_变长编码_16

当全部可能的选择有相同的信息内容时(全部选项都有固定长度编码时), 效果良好. 可是若是这些选择信息内容不一样, 为频率更高的使用更短的编码, 这样效率更高.


6.004 L01_信息内容_17

假设4个可能选择(A, B, C, D), 每个选择有指定的几率. 几率越高, 编码越短(B), 几率越低, 编码越长(C, D). 编码长度的指望值为(2 * (1/3) + 1 * (1/2) + 3 * (1/12) * 2 = 1.667bit).

若是使用固定长度编码, 每一个选择都须要2bit, 若是编码1000个, 须要2000bit. 可是用变长编码, 须要大约1667(1.667 * 1000), 但下界为H(X)=1626, 因此有更好的选择.


6.004 L01_变长编码_18

Huffman算法: 构建最佳变长编码.

  • 从底开始构建二叉树. 选择两个最小几率的元素, 假设\(p_i\)和\(p_j\).
  • 将这两个元素组合为二元子树, 一个标为0, 一个为1. 从列表中删除这两个元素, 并将几率相加(\(p_i\)+\(p_j\)), 将该子树加入列表.
  • 重复直到最后只有两个元素, 将这两个元素组合成树.

6.004 L01_信息内容_19

经过将元素组合而不是只使用单个元素来构建Huffman树. 例如使用两个元素做为一组时, 指望长度为1.646. 使用3个会更小.


6.004 L01_子树_20

若是原本为0的数据因为传输时发生错误变为1, 没法检测是否发生错误.


6.004 L01_数据_21

Hamming Distance: 两个相同长度编码中, 不一样的位的数量.


6.004 L01_变长编码_22

当有一个单位错误时, 00被修改成01或10, 这两个都不是有效数字. 这样1要么出现0次, 要么出现2次. 若是1出现奇次, 那么就能够知道发生了错误.


6.004 L01_补码_23


6.004 L01_信息内容_24


6.004 L01_信息内容_25