比特 Bits

布尔位：与、或、非、抑或等运算

电路位：

有回路的电路位可能更复杂，叫时序逻辑电路 sequential logic

控制位：例如 (if (and (< x 0) (> y 0)) (define z 0))，特点在于有短路效应

物理位：若一个位可以被储存或转移，则其必定有物理形式

量子位：

  • 可逆性 reversibility：量子数学中的函数是可逆的
  • 叠加性 superposition：27% yes 73% no
  • 纠缠 entanglement：量子纠缠

经典位：0V-0.2V 为逻辑假，0.8V-1V 为逻辑真

编码 Codes

符号空间大小：1、2、2 的幂次方、有限、无限可数、无限不可数

  • 二进制编码十进制 BCD
  • 基因编码
  • 电话地址编码
  • IP 地址
  • ASCII

00000000 表示 NUL，被忽略

11111111 表示删除

固定长度和可变长度编码

摩尔斯编码

压缩 Compression

分成两类：有损（可逆）和无损（不可逆）

可变长度编码 运行长度编码：把 abbbbb 编码为 a1b5

静态字典：多余的位用于编码一些常用的信息

半静态字典：在每次传递信息时都预先编码一次字典

动态字典：

  • LZW
  • 二维余弦变换 JPEG

错误 Errors

检测 detection 和纠正 correction 错误

汉明距离 Hamming distance：两个东西不同的位的数量

单个比特：三倍冗余（0 编码为 000）、五倍冗余（0 编码为 00000）

多个比特：

  • 检验位 parity：使和为偶数
  • 矩阵编码：将信息扩充为矩阵，每行每列都有检验位
  • 汉明编码：001、010、100 等为检验位，几者叠加可以得出错误出在哪一个数据上

块编码：(n,k,d)，n 为字符串长度，k 为有效数据位，d 为汉明距离

概率 Probability

概率-集合论-通信中的很多东西都可以一一对应

如：事件，已知结果，未知结果，合并事件，条件概率，平均值

最重要的——信息，其量本质上是得知该信息的惊讶度

I=∑ip(Ai)log⁡2(1p(Ai))I = \sum_i p(A_i) \log_2(\frac{1}{p(A_i)})

这与描述某个物理系统的熵 entropy 相同

当所有事件的概率相等时，源的熵最大

通信 Communications

Kraft 不等式：

∑i12Li≤1\sum_i \frac{1}{2^{L_i}} ≤ 1

Gibbs 不等式：

∑ip(Ai)log⁡2(1p(Ai))≤∑ip(Ai)log⁡2(1p′(Ai))\sum_i p(A_i) \log_2(\frac{1}{p(A_i)}) ≤ \sum_i p(A_i) \log_2(\frac{1}{p^{\prime}(A_i)})

源点编码定理：

H≤LH ≤ L

信道模型

  • 有噪声信道
  • 无噪声信道

交互信息 mutual information：把输出视为输入的结果

噪声信道容量定理：

C=MmaxWC = M_{max}W

WW 是输出状态可以跟上输入变换的最大速度，CC 是信道容量

过程 Processes

过程分类：

  • 离散——连续
  • 噪声——无噪声
  • 无损——有损

过程图类型：

  • 块图
  • 环路图
  • 概率图
  • 信息图

一个简单的信道

信息图

推理 Inference

贝叶斯法则

最大熵原则 Principle of Maximum Entropy

对于贝叶斯法则中的先验概率，需要假设我们对此已知最少，即最大化熵

一些约束：

  • 概率和为 1
  • 平均值为某个数等

方法：拉格朗日乘数

物理系统 Physical Systems

量子力学

∣ψ(r,t)∣2=ψ(r,t)ψ∗(r,t)|ψ (r, t)|^2 = ψ (r, t) ψ^* (r, t)

ih∂ψ(r,t)∂t=−h22m∇2ψ(r,t)+V(r)ψ(r,t)i h \frac{∂ψ(r, t)}{∂t} = -\frac{h^2}{2m} ∇^2 ψ(r, t) + V(r) ψ(r, t)

稳定状态：

ψ(r,t)=ϕ(r)e−iEt/hψ(r, t) = ϕ(r) e^{-iEt/h}