信息论

信息论 王立威

• 首先谈谈我对这门课的看法，王老师授课不会循规蹈矩地按照参考教材（黑皮书信息论），他是按照自己对信息论的理解和看法来的，所以前后知识的串联性会比较强一些，另外这门课是纯英文板书、中英夹杂授课。
• 整体上是按照信源编码和信道编码两方面展开，然后重点介绍了香农的一些工作，实际上信道方面在实际中会更重要、复杂一些，但是在各个领域包括计算中信源会涉及更多一些

L1

熵：随机信号的最低不可降低复杂度

• 量化信息的大小
• 如何用算法克服物理噪声

传输信息——需要事先约定 eg：传输一场比赛的结果 字符集{0，1}

W	L	T(平局)
0	1	10
0	11	10

第一种是否可行？
第二种是否可行？ 可行->只传输一次
可行&效率max->平均编码长度？Minimize average code length

两个基本假设：

1. infinite communication
2. a prob distribution over the message

引入 pre-fix free 编码

1. 无前缀->无歧义
2. 无前缀<-×无歧义

Set $A$: pre-fix free
Set $B$: Uniquely decode codes 唯一可译码集合

注意前缀无码一定是唯一可译码，但反之则否

$A\subsetneqq B$,显然$\min_{c\in B}E[l(c)]\le min_{c\in A}E[l(c)]$,但是实际上$\star \min_{c\in B}E[l(c)]= min_{c\in A}E[l(c)]$. $\implies \forall c^* \in B$,使得平均码长$E[l(c^* )]$达到最短,则$\exists \check{c}^* \in A$,$E[l(c^* )]=E[l(\check{c}^*)]$.

如何设计$c^*$调整为$\check{c}^*$?

Kraft Inequality
Assure $C=(c_1,c_2,...,c_n)$ is pre-fix free: Let $l_1,l_2,...,l_n$ be the length(numbers of bit) of $c_1,...,c_n$,则$l_1,...l_n$ 不能都很短(为了prefix-free)
$$\sum_{i=1}^n 2^{-l_i}\le 1$$
若二叉树为满，则$\le$变为严格=
平均码长最短->二叉树为满树，则有
$$\sum_{i=1}^n 2^{-l_i}=1$$
如何求解？
Minimal Average Code Length
令message $M={m_1,...,m_n}$. Prob distribution $P={P_1,...,P_n}$. 目标是Find $C=(c_1,...,c_n)$ prefix-free with length $l_1,...,l_n$,同时有平均码长=$\sum_{i=1}^np_il_i$(期望长度) 约束有：$\sum_{i=1}^n 2^{-l_i}\le 1$
求解：运用拉格朗日乘子法,$\min L$
$$L=\sum_{i=1}^n p_i l_i + \lambda(\sum 2^{-l_i} - 1)$$
$$\frac{\partial L}{\partial l_i}=p_i-\lambda2^{-l_i}\ln2=0 \implies 2^{-l_i}=\frac{p_i}{\lambda \ln2}$$
$$\sum 2^{-l_i}=1,\ \sum p_i=1 \implies \lambda=\frac{1}{\ln2}$$
$$\therefore\ l_i=-\log_2 p_i \star$$
$$L^*=\sum_{i=1}^n p_i l_i=-\sum_{i=1}^n p_i \log_2 p_i$$
($l_i$是否为整数的差距不会超过1)

$\implies -log_2p_i\le l_i < -log_2p_i+1$

两边同乘$p_i$再求和可得,$H \le L < h+1$

---

定义：熵（entropy）
$$H(x)=\sum_{i=1}^np_ilog_2\frac{1}{p_i}=-\sum_{i=1}^np_ilog_2p_i$$

$\star$此为不可压缩的最短码长，为信息的量化

信息$m_i$的信息量为$-log_2p_i$
均匀分布的熵最大,单点分布的熵为0 e.g 对于伯努利分布$X~(P,1-P)$,有$H(x)=-plog_2p-(1-p)log_2(1-p)$

L2

Entropy被提出以qunantity information(量化信息)来描述uncertainty.
由琴生不等式可得. $\sum_{i=1}^np_ilog_2\frac{1}{p_i} < log_2n$
信息量的刻画

• 随机变量$X$:$H(X)(bits)$
• message $m_i$:$log_2\frac{1}{p_i}$(可以看出概率小的事情信息量大)

---

Q:对于随机变量$X:P_1,P_2,...P_{n-1},P_n$,其中$P_n$可细化为$q_1+q_2$

$Y$:为对局部信息的详细描述$\frac{q_1}{q_1+q_2} \frac{q_2}{q_1+q_2}$ $Z$:$P_1,P_2,...,P_{n_1},q_1,q_2$ $H(Z)=H(X)+P_nH(Y)$

什么样的码平均码长最短？ Properties of optimal code

1. 若$p_1\le p_2...\le p_n$则,$|C_1|\le |C_2|\le ...\le |C_n|$
2. 满足Kraft Ineq:$\sum_{i=1}^n2^{-|c_i|}=1$ for opt code
3. $|c_{n-1}|=|c_n| \implies$可以使$c_{n-1} c_n$成为兄弟结点

Huffman哈夫曼编码：一种简单的给出的最优五前缀编码的算法。
eg: 二源码 1:0.25 2:0.25 3:0.2 4:0.15 5:0.15

---

联合熵、条件熵、互信息（自信息）、KL散度（相对熵）

1. 联合熵 Joint Entropy
   两个$r.v. X,Y$有联合密度分布$P_{XY}=(p_{ij})_{m\times n}$,如何定义一个联合熵？
   $$H(X,Y)=-\sum_{x\in X}\sum_{y\in Y}P(x,y)log_2P(x,y)=-E[log_2P(x,y)]$$
   显然$H(X,Y)\le H(X)+H(Y)$ $\bigtriangleup X,Y$彼此独立时,$H(X,Y)=H(X)+H(Y)$;$X=Y$时,$H(X,Y)=H(X)+H(Y)$
2. 条件熵 $H(Y|X)$

   定义：
   $$H(Y|X=x_i)=\sum_{j=1}^nP(Y=y_i|X=x_i)log_2\frac{1}{P(Y=y_i|X=x_i)}$$
   $$H(Y|X)=\sum_{i=1}^n\sum_{j=1}^nP(Y=y_i|X=x_i)log_2\frac{1}{P(Y=y_i|X=x_i)}$$
   $$H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y)$$
   $$\Uparrow 推导：log_2P(X,Y)=log_2P(X)+log_2P(Y|X)两边取期望$$
   $$H(X,Y)=-\sum_{x\in X}\sum_{y\in Y}p(x,y)log_2(p(x,y))$$
   $$也即H(X,Y)=-\sum_{x\in X}\sum_{y\in Y}p(x)p(y|x)(log_2(p(x))+log_2(p(y|x)) )$$

L3

接续上一节的内容
$$H(X,Y)=H(X)+H(Y|X) （1）$$
$$H(X,Y)=H(Y)+H(X|Y) （2）$$
$$H(X,Y)\le H(X)+H(Y)（3）$$
Combine (1)&(3) and (2)&(3) 可得conditions reduce entropy
$$H(Y)\ge H(Y|X)$$
$$H(X)\ge H(X|Y)$$
则有：
$$H(X)+H(Y|X)+H(Y)+H(X|Y)=2H(X,Y)$$
$$H(X)+H(Y)-H(X,Y)=H(X,Y)-H(Y|X)-H(X|Y)$$
$$=H(X)-H(X|Y)=H(Y)-H(Y|X)$$
那么我们可以取量化这样一个量$H(X)-H(X|Y)$或$H(Y)-H(Y|X)$: X与Y重叠那部分的信息量。

---

互信息（自信息）：
$$I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)$$
$$=H(X)+H(Y)-H(X,Y)$$
$$=\sum_{x,y}p(x,y)log_2\frac{p(x,y)}{p(x\ne y)}$$
$$=I(Y;X)$$
接下来可以进一步探讨多元形式
$$H(X_1,X_2,…,X_n)=\sum p_{1,2,…,n}log_2\frac{1}{p_{1,2,…,n} }(Joint\quad Entropy)$$
同理$H(X_1,X_2,...,X_n|Y_1,Y_2,...,Y_n)$的定义
我们有：
$$H(X_1,X_2,…,X_n)=H(X_1)+H(X_2|X_1)+…+H(X_n|X_1,…,X_{n-1})$$
这样在知道一串码和其概率分布时可求其熵,但这样我们的pmf时理想化的
True PMF is $P=(p_1...p_n)(unknown)$
我们的近似：$Q=(q_1...q_n)$
两种码长差多少？
$P:\sum p_ilog_2\frac{1}{p_i}$ $Q:\sum q_ilog_2\frac{1}{q_i}$
$Q-P=\sum p_ilog_2\frac{p_i}{q_i}$

---

相对熵/KL散度 $D(P||Q)$
$$D(P||Q)=\sum_{x\in X}p(x)log_2\frac{p(x)}{q(x)}=E_qlog_2\frac{p(x)}{q(x)}$$
Question:P、Q的KL距离和1维欧式距离之间关系？$||P-Q||_1 = \sum_i|p_i - q_i|$
$$D(P||Q) = \sum_{i} p_i \log \frac{p_i}{q_i}$$
$$\sum_{i=1}^n p_i \log \frac{p_i}{q_i} \ge \frac{1}{2} \left( \sum |p_i - q_i| \right)^2 \quad \text{(Pinsker)}$$
ps:大部分时候对数的底取决于编码空间，公式中可转换，大部分时候是以2为底，有些情况下是10或者e方便推导
简单推导:$P=(p_1,...,p_n)\quad Q=(q_1,...,q_n)$

$\|P-Q\|_{1}=\sum |p_i-q_i|=\sum_{p_i\ge q_i}(p_i-q_i)+\sum_{p_i\le q_i}-(p_i-q_i)$

则模型可化为$\tilde{P}=(\sum_{p_i\ge q_i}p_i,\sum_{p_i\le q_i}q_i )$
特例：伯努利分布$\bigtriangleup P=(p,1-p) \bigtriangleup Q=(q.1-q)$
$$KL(P||Q)=plog\frac{p}{q}+(1-p)log\frac{1-p}{1-q}$$
$$||P-Q||_1=|p-q|+|(1-p)-(1-q)|=2|p-q|$$

L4

1. Entropy Rate 熵率
   eg. $X$为$r.v.$ $X=(0.01,0.99)$
   (1).$H(X)\approx 0.07 bit$
   (2).最短平均码长=1 bit $H(X)$为最优码长的下届，何时为下确界？ 无限次传输时，最短码长还是0.07 bit吗？$X:X_1,X_2,...,X_T idd~P$ $Min Average Code Length\le TH(X)+1$(受限于码长必须是整数) $H(X_1,X_2,...,X_T)=TH(X)$ 平均每次的码长即为：
   $$\frac{TH(X)+1}{T}=H(X)+\frac{1}{T}$$
   当$T\to \infty$,$\frac{1}{T}\to 0$.
   真实信源信源是一个随机过程,$H(X)=lim_{T\to \infty}\frac{1}{T}H(X_1,X_2,...,X_T)$
   假设极限存在，定义平均每一时刻的信息量增长：
   $$H(X)=lim_{T\to \infty}H(X_T|X_1,X_2,…,X_T)$$
   即为熵率：序列长度的增长速率

---

2. Differential Entropy （微分熵）
   仿照离散型对连续型随机变量的讨论.
   考虑$r.v. X\sim V[0,1]$,连续型随机变量的熵为 $\infty$
   但是可以离散化$X_{\Delta}\sim [0,\Delta,2\Delta,...,1-\Delta,\Delta] \quad \Delta \to 0 \quad H(X_{\Delta})\to \infty$
   可以从形式上定义一个Entropy $continuous \quad r.v. X \quad pdf \quad f(x)$ $$h(x)=-\int f(x)\log_2f(x)dx=-E\log f(x)$$
   当$X$退化为 $X_{\Delta}$时
   $$H(X_{\Delta})\approx h(x)+\log_2\frac{1}{\Delta}$$
   如何证明？
   $$H(X_{\Delta})=-\sum p(x)\Delta\log_2p(x)\Delta dx$$
   $$(p(x)\Delta\approx \int p(x)dx)$$
   $$\approx -\int p(x)\log_2p(x)\Delta dx$$
   $$=h(x)+\log_2\frac{1}{\Delta}$$

反直觉的一件事：differential entropy不过是形式化定义而已
由以上的推导，我们由以下几个结论：

• 考虑离散$r.v.\quad X \quad Y=X+c\quad Z=ax$
  $$H(X)=H(Y)=H(Z)$$
• 考虑连续$r.v.\quad X \quad Y=aX$
  $$h(Y)=h(X)+\log_2a$$
  如何证明连续的情况？ $Y=aX\quad \to X=\frac{Y}{a}$ $$\star\int P_Y(y)dy=\int \frac{1}{|a|}P_X(\frac{y}{a})dy$$
  $$h(Y)=-\int P_Y(y)\log_2P_Y(y)dy$$
  $$=-\int \frac{1}{|a|}P_X(\frac{y}{a})\log_2(\frac{1}{|a|}P_X(\frac{y}{a}))dy$$
  $$=-\int P_x(X)\log_2(\frac{1}{|a|}P_X(x))dx$$
  $$=h(x)+\log_2|a|$$

  PS：概统知识 已知$X$的概率密度函数$P_X(x)$与$Y=aX(a\ne 0)$的概率密度$P_Y(y)$,如何得到$\star$式？
  $$F_Y(y)=P(Y\le y)=P(aX\le y)$$
  $$(1).a>0 \quad P(aX\le y)=P(X\le \frac{y}{a})=F_X(\frac{y}{a})$$
  $$(2).a>0 \quad P(aX\le y)=P(X\ge \frac{y}{a})=1-F_X()\frac{y}{a}$$
  $$1.a>0 \quad P_Y(y)=\frac{\mathrm{d} }{\mathrm{d}y }F_X(\frac{y}{a})=P_X(\frac{y}{a})\frac{1}{a}$$
  $$2.a<0 \quad P_Y(y)=\frac{\mathrm{d} }{\mathrm{d}y }(1-F_X(\frac{y}{a}))=-P_X(\frac{y}{a})\frac{1}{a}=P_X(\frac{y}{a})\frac{1}{|a|}$$
  $$\therefore P_Y(y)=\frac{1}{|a|}P_X(\frac{y}{a})$$

---

$e.g. \quad r.v. \quad X\sim N(\mu ,\sigma^2)\quad \delta=\sigma^2 \quad$求 $h(x)$

$$h(x)=-E\log_2p(x)=-\frac{1}{\ln2}E\ln p(x)$$
$$\ln p(x)=-\frac{1}{2}\ln (2\pi \sigma)-\frac{(x-\mu)^2}{2\sigma}$$
$$E[\ln p(x)]=-\frac{1}{2}\ln (2\pi \sigma)-\frac{1}{2\sigma}E[(x-\mu)^2]$$
$$=-\frac{1}{2}\ln (2\pi \sigma)-\frac{1}{2}$$
$$\therefore h(x)=\frac{1}{2}\log_2(2\pi e\sigma^2)$$
$$\Longrightarrow E[g(x)]=\int_{-\infty}^{+\infty}g(x)p(x)dx $$

L5

Differential Continuous entropy在上一节中已经进行了清晰的定义，沿用这些概念,定义一些新概念。

1. Joint differential entropy 联合熵
   $$h(X,Y)=-\int f(x,y)logf(x,y)dxdy$$
   where $f(x,y)$ is he joint pdf of X,Y
2. conditional differential entropy 条件熵
   $$h(X|Y)=-\int f(x,y)logf(x|y)dxdy$$
   $$=h(X,Y)-h(Y)$$
3. Mutual Infoimation 互信息
   离散情况: $I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)+H(Y)-H(X,Y)$
   若$X,Y$为连续随机变量$f_{X,Y}\quad f_{X|Y}\quad f_{Y|X}$则有定义：
   $$\int f_{XY}(X,Y)log_2\frac{f_{XY}(x,y)}{f_X(x)f_Y(y)}dxdy$$
4. KL dicergence 相对熵
   定义$f,g$为两个$pdf$(连续随机变量)定义：
   $$KL(f||g):=\int_{-\infty}^{+\infty}f(x)\log\frac{f(x)}{g(x)}$$
   $$KL(P_{\Delta}||Q_{\Delta})=^{\Delta\to 0}=KL(f||g)$$

L6

Kolmagorov Complexity 柯尔莫哥洛夫复杂度
对于 determinist object有最优描述，例如圆(o,r) 矩形(o,a,b)，why optimal is (o,r)? 对于random object如何？
另一个e.g.描述一段序列 ${0,1}^*$

• 对与0,0,…,0全为0 显然容易 $\{0,repeat\quad n\quad times\}$
• 011011… 显然也容易 $\{011,repeat\quad n\quad times\}$
• 110101001… 本身无规律 方法只有copy序列本身

---

引入一个问题：对于一个给定问题，讨论可用一段代码计算求解问题

• computer：能用代码实现
• 不computer：不能用代码实现 e.g. 表示所有实数 e.g. 多元方程整数解的存在

1. Problems Decision Problems (eg 给定$L\subseteq {0,1}^* \text{decide if }x\in L\text{? for every }x\in {0,1}^*$)
2. Algorithms 一段代码$alg-a\in {0,1}^*$（图灵机有限步内有解）

存在大量Problems(不可数多)没有Algorithms(可数多),事实上Problems是A lgorithms数量的幂级 $|S|<|\mathcal{P} (S)|$

[实变函数]一个集合和它的幂集无一一对应的关系
Halting Problem:给定代码$input(a,i)$能否在有限步停下来的问题
哥德尔不完备定理：若一个公理体系是内无矛盾的，则存在大量的statements无法被证明/证伪

---

Kolmogorov complexity
柯复杂度定义为：若字符串$x\in {0,1}^* \text{ is defined as:}$
$$K(x):=min|P|\quad P\to \text{代码}$$
$$u(P)=x:\text{执行代码输出为}x$$
对于某一个universal Turing Machine:
Q1. 对于不同的图灵机$u_1,u_2$他们的$K(x)$有本质区别吗？
结论：$u \quad u^*$为两个universal T.M,则存在$c\in N$使得对$\forall x\in \{0,1\}^* K_u(x)\le K_u^* (x)+c \text{ c与x无关,取决于} u\text{与}u^*$
Q2.固定$u,K_u(x)$?(怎么找到最短代码)
枚举？不可行,不存在一个算法可以决定program P 能否把输入x在有限步生成。
猜想&证明：Kolmogorov complexity不可计算？

---

Them $K_u(X)$ is not computable
proof:若存在算法$P_0$ 计算$K_u(x)$ for $\forall x \in \{0,1\}^*$
这是$P_0$的长度是固定的，$|P_0| = const$
取$S_1,S_2,...\in \{0,1\}^*$,其中$|S_1|\le |S_2|\le ...$

$P_0^*: For\quad i=1 ...$ compute $K_u(S_i)$ using $P_0$: if $K_u(S_i)=10^8$ output $S_i$

若$\exists P_0\quad \forall x\in \{0,1\}^* \quad K(x)$
设$|P_0|=m$ $S_0,S_1,S_2,...$

$P^* \quad for\quad i=1,2.....$ compute $K(S_i)$ using $P_0$: if $K(S_i)\ge m+1$ output $S_i$ $P^*$ 只调用$P_0$枚举，$\therefore$长度不大于$m+c$

$$K(S)\to \ge m+1$$

$P^*$生成了一个复杂度大于其长度的代码，这与定义的“最小”矛盾

Kolmogorov complexity $\to K(s)\le |P^* |\le m+c$,即$K(s)$不应超过$P^*$的长度

---

最大熵分布估计 从部分信息估计概率密度函数
常见：矩约束

$$\int f(x)dx=1$$
$$\int xf(x)dx=r_1$$
$$…$$
$$\int g_i(x)f(x)dx=r_i\text{（泛化形式）}$$
最大熵分布估计：从所有信息里面选Entropy最大的
$$max\quad -\int f(x)\ln f(x)dx \quad s.t.\quad \int f(x)dx=1,\quad \int xf(x)dx=r_1 …$$
例题：矩约束为$\int f(x)dx=1\quad \int xf(x)dx=0 \text{(一阶原点矩约束)}E(x) \quad \int x^2f(x)dx=\sigma^2\text{(二阶矩约束)}D(x)$
$$PS:D(x)=E[(x-E(x))^2]=E[x^2]-(E[x])^2=\int x^2f(x)dx$$
解：首先构造拉格朗日函数
$$ \mathcal{L} (x,f(x))=-f(x)\log f(x)+\lambda_1f(x)+\lambda_2xf(x)+\lambda_3x^2f(x)$$
$$ \mathcal{J} (f)=\int_{+\infty}^{-\infty}\mathcal{L}(x,f(x))dx-\lambda_1-\lambda_2*0-\lambda_3\sigma^2 \quad \text{（泛函）}$$
$$\frac{\mathrm{d} \mathcal{L} }{\mathrm{d} f(x)}=-\log f(x)+(-f(x))\frac{1}{f(x)}+\lambda_1+\lambda_2x+\lambda_3x^2 $$
$$\therefore f(x)=e^{\lambda-1+\lambda_2x+\lambda_3x^2}\quad \text{即为正态分布}$$

L7

Channel Coding 信道编码

1. 信道噪声
2. 算法减少（纠正）错误
   重复编码 0—>000 1->n1 解码：最近邻

• $M_1\to C_1$
• $M_2\to C_2$
• …
• $M_m\to C_m$

Lower bound - $\{0,1\}^m\to \{0,1\}^n$

$\text{Goal:}\forall i\ne j \quad d_H(C_i,C_j)\ge 2t+1\text{(correct t bits error)}\quad$ 给定t,m估计n的下界

Sphere packing bound
$$M\le \frac{2^n}{\sum_{i=0}^t\binom{n}{i} }$$
总空间$2^n$至少容纳$m$ 个球给出$n$的下界($n$至少多大才能支持$m$个码字纠正$t$位错误)
Upper bound 上界(存在性分析) $d_H(C_i,C_j)\ge \delta n (\delta \in (0,\frac{1}{2}))$
给定$m,\delta$求最小的$n$,使得必然存在： $2^m\text{个}n\text{位字}\ge \delta n$

1. 单对坏概率上界 Chernoff界
   $$i\ne j \quad P(d_H(C_i,C_j)<\delta n)<e^{-\theta(n)}$$
2. 全局坏概率
   $$P(\exists i\ne j,d_H(C_i,C_j)<\delta n)<C_{\alpha}^{2^m}e^{-\theta(n)}$$
3. 概率小于1
   $$C_{\alpha}^{2^m}e^{-\theta(n)}<1$$

GV 线性关系 $n>cm\quad \text{c为常数项,则存在}C_1,...,C_{2^m}$使得$d_H(C_i,C_j)\ge \delta n$
汉明码（至多纠正一个错误） 二元域$GF(2)$的矩阵 零空间$Null(H)=\{x\in\{0,1\},HX=0\}$

L9

Message ->Error correcting Code. $\{0,1\}^m\to \{0,1\}^n$

1. $\forall C_i,C_j\in \{0,1\}^n,d_H(C_i,C_j)\ge 2t+1\quad bits$
2. Sphere packing bound $\frac{2^n}{\sum_{i=0}{t}\binom{n}{i} \ge 2^m }$
3. G. V. bound(Gilbert–Varshamov bound)
4. Eifficient Encoding/Decoding Algorithm

Hamming Coding

$H=\begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{bmatrix}$ $x_i,x_j\in Null(H)=\{x\in \{0,1\}^7, Hx=0 \}$

列线性无关，任意两列之和不为第三列

$x\in Null(H)\to \text{满足}Hx=0$

解码 correct 1-bit error $d_H(x,C_i)\le 1 \quad bit \quad \delta \to \text{错误向量}$

$Hx= \begin{cases} 0 \quad x\to C_i\\ 2 \quad x-\delta \to C_i \end{cases}$

编码目的

1. 信息量： $m_i\in \{0,1\}^4\quad$ 码字 $c_i\in [m_i,...]$
2. 生成矩阵：生成矩阵 $G$由 $H$零空间的4个基向量 $g_1,g_2,g_3,g_4$构成， $g_1 \in Null(H)$,因此 $HG=0$
3. 码字是基向量的线性组合 $c=\sum_{i=1}^4a_ig_i=Ga$
4. 生成矩阵的标准形式
   $$G=[I_4|G_3]$$
   $$c=[a|G_3a]\to \text{[信息位|监督位]}$$
5. 监督矩阵的置换
   $$H=[P|I_3]\to G=(\frac{I_4}{P^T})$$
6. 生成矩阵 $n\times k\to G\quad m\to Gm\quad G=[I_k|G_{n-k}]$
   [n,k,d]:

• n:码字长度 $n=k+r$
• k:信息位长度
• d:最小汉明 $d\ge 2t+1$

L10

[n,k,d]->[m+1,k+1,d+1] 其中d为odd，d+1为even
方法： 通过添加全局奇偶校验位(Overall Parity Check)实现，使最小汉明距离增加1.
循环编号 由上往下每一行向右偏移一位

$\begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{bmatrix}$

1. 噪声信道如何模拟？ $X--P(Y|X)-->Y$
2. 给定噪声信道 $P(Y|X)$,X会接受多少信息？
   $$I(X;Y)=D(P_{XY}||P_XP_Y)$$

---

信道容量： $C:=max_{P_X}I(X;Y)$
对所有的输入$P_X$,互信息最大值代表最大可靠传输速率
信道编码定理:

$R:\text{码率，每s传输bit}$ $\text{if}\quad R< C,\exists \text{error correcting code}\quad \text{error}\to 0\quad$ $\text{if}\quad R>C,\nexists \text{error correcting code}\quad \text{error}\ge \varepsilon_0$

L11

渐进充分性（AEP）i.i.d

大数定理及其扩展 $P$为概率分布
$$P(|\frac{1}{n}\sum X_i-E(x)|\ge\varepsilon)\to0(n\to\infty)$$
函数的定义下：
$$P(|\frac{1}{n}\sum g(X_i)-E(g(x))|\ge\varepsilon)\to0$$
熵的定义下：
$$P(|\frac{1}{n}\sum \log\frac{1}{p(x_i)}-E(\log\frac{1}{p(x)})|\ge\varepsilon)\to0$$

$E(\log\frac{1}{p(x)})为信源熵,熵的定义下表明经验熵收敛于真实熵$

典型集 $A=\{(x_1,...,x_n):P(x_1,..,x_n)\in 2_{-nH(x)\pm \varepsilon }\}\Rightarrow 1. P(A)\approx 1（典型集必出现） 2. P(A_c)\approx 0 （非典型集合可忽略）$
则有$|A|\to A\text{中元素个数}$
$$\log P(·)=-nH(X)$$
$$\sum_{x\in A}p(x)\approx 1$$
$$|A|2^{-nH(x)}\approx1$$
$$|A|\approx2^{-nH(x)}$$

---

联合典型序列 定义联合AEP
$$i.i.d\quad (X_1,Y_1)(X_2,Y_2)…(X_n,Y_n)\sim P(X,Y)$$
联合分布概率
$$P_{XY}(·)\in 2^{-n(H(X,Y)\pm \varepsilon)}$$
边缘分布
$$P_X(·)\in 2^{-n(H(X)\pm \varepsilon)}$$
$$P_Y(·)\in 2^{-n(H(Y)\pm \varepsilon)}$$
[采样相关] 如何生成$X_1,Y_1,...,X_n,Y_n$？

1. $(X_i,Y_i)\sim P(X,Y)$
2. $X_1,...,X_n\sim P(X) \quad Y_1,...,Y_n\sim P(Y|X)$

固定序列$x_1,x_2,...,x_n$相应的采样典型序列 $y_1,y_2,...,y_n$ is $2^{nH(Y|X)}$
考虑独立的典型序列$X,Y$,则能构成典型序列的概率为：
$$\frac{2^{nH(X,Y)} }{2^{n(H(X)+H(Y))} }=2^{-nI(X;Y)}$$

L12

香农信道编码原理 Shannon Channel Coding Theorem

$R:\text{码率，每s传输bit}$ $\text{if}\quad R< C,\exists \text{error correcting code}\quad \text{error}\to 0$ $\text{if}\quad R>C,\nexists \text{error correcting code}\quad \text{error}\ge \varepsilon_0> 0$

Proof Shannon Part1(Assume R<C)

1. raw message $\{m_1,m_2,...m_{2^{nR} }\}$服从均匀分布 $P(m_i)=\frac{1}{2^{nR} }$
2. Design codeBook $CB=(C_1,C_2,...C_{2^{nR} })$
   $$m_1\to C_1=(C_11,C_12,…,C_1n)$$
   $$m_2\to C_2=(C_21,C_22,…,C_2n)$$
   $$…$$
   $$m_{2^{nR} }\to C_{2^{nR} }=(C_{2^{nR_1} },C_{2^{nR_2} },…,C_{2^{nR_n} })$$
   idea random coding
   $$P(X)=argmax_{\rho (x)}I(X;Y)$$
3. Decoding algorithm/mode
   Upon receiving $(y_1,...,y_n)--?->C_i$
   寻找唯一码字$C_i=(x_1,...,x_n)\quad s.t.\quad (x_1,...,x_n,y_1,..,y_n)\quad \text{is a joint typical sequence}$
   即满足$P(X)P(Y|X)$联合典型序列（AEP）,需要考虑以下情况：
   (a) 无码字与y联合 解码失败（如y本身非典型） 不考虑这种情况
   (b) 多码字与y联合 解码失败 $\star \star \star$
   (c) 唯一码字与y联合 无需证明
   对于情况(b):

   y为联合典型概率为$2^{-nI(X;Y)}$
   其本身有$2^{nR}-1\approx 2^{nR}个其它码字$
   $$P((b))\le 2^{nR}·2^{-nI(X;Y)}=2^{n(R-I(X;Y))}=2^{n(R-C)}$$

   $R< C$时，$n\to \infty$,$2^{n(R-C)}\to 0$

L13

范式不等式(Fan’s Inequality)
Theorem. $X,Y \quad discrete X\in\mathcal{H} \quad |\mathcal{H}|<\infty$
用Y估计X $\hat{X}=g(Y)$作为X的估计
最小化错误率 $P_e:=P(\hat{X}\ne X)\{P与P(X|Y)和H(X|Y)相关\}$
$$P_e\ge \frac{H(X|Y)-1}{\log|\mathcal{H}|}$$

Proof Shannon Part2(Assume R>C)
消息$M\in \{1,2,...,2^{nR}\}$均匀分布$H(M)=nR$
信道输出$Y^n=(Y_1,...,Y_n)$,则互信息$I(M;Y^n)\le nC(C=maxI(X;Y))$
证明$R>C\text{时}\quad P_e\le \varepsilon > 0$
$$I(M;Y^n)=H(M)-H(M;Y^n)$$
$$H(M;Y^n)=H(M)-I(M;Y^n)$$
$$H(M)=nR\quad I(M;Y^n)\le nC$$
$$H(M;Y^m)\ge n(R-C)$$
设$\hat{M}=g(Y_n)\quad P_e=P(\hat{M}\ne M)\quad |\mathcal{H}|=2^{nR}\quad \log |\mathcal{H}|=nR$
$$P_e\ge \frac{n(R-C)-1}{nR}\approx \frac{R-C}{R}=\varepsilon_0 > 0 \quad (R>C) $$

---

费希尔信息(Fisher Information)与克拉美劳不等式(Cramer-Rao Inequality)

1. 无偏估计 $X=(x_1,...,x_n)\quad i.i.d\quad \text{密度函数}\quad f(X;\theta)=\prod_{i=1}^nf(x_i;\theta)$ 目的：用$x_1,...,x_{\theta}$估计$\theta$
   $$\hat{\theta}=\phi(x_1,…x_n)\quad \phi:X\to R$$
   无偏估计$E(\phi(X)=\theta)\quad Var(\phi(X))$有下届 $\hat{\theta}$即为$\theta$的无偏估计
2. 费舍尔信息(Fisher Information)
   定义分数函数
   $$S(X;\theta):=\frac{\partial }{\partial \theta}\ln f(X;\theta) $$
   $$E(S(X;\theta))=\int S(X;\theta)f(x;\theta)dx$$
   $$=\int \frac{\partial }{\partial \theta}\ln f(x;\theta)·f(x;\theta)dx$$
   $$=\int\frac{\partial }{\partial \theta} f(x;\theta)dx$$
   $$=\frac{\partial }{\partial \theta}\int f(x;\theta )dx$$
   $$=\frac{\partial }{\partial \theta}1=0$$
   $$E(S^2(X;\theta))=Var(S(X;\theta))$$
   定义费舍尔信息：
   $$I(\theta)=Var(S(X;\theta))=E[S(X;\theta)^2]$$
   $$Var=E[(X-E(X)^2)]=E(X^2)$$
   等价于
   $$I(\theta)=-E(\frac{\partial^2 }{\partial \theta^2}\ln f(X;\theta))$$
3. 克拉美劳不等式
   无偏估计$\phi:X\to R\quad Var(\phi(X))\ge \frac{1}{I(\theta)}$
   分数函数：
   $$E(\nabla_\theta \ln f(X;\theta))$$
   Fisher information:
   $$-E(\nabla_\theta^2 \ln f(X;\theta))$$
   Camer-Rao:(两者之差时半正定的)
   $$Cov(\phi(X))\ge I(\theta)^{-1}$$

L14

通信复杂度（Communication Complexity）
定义：$f(x,y)$计算函数$(x,y\in\{0,1\}^*,f\text{为二元函数})$ 所需交换的最大比特数

$Alice\to x \quad Bob\to y$ 有限次通信写作计算$f(x,y)\quad goal:$最小通信量

时序矩阵
分块数：$\mathcal{X}(f)\to$将函数$f$的真值表分解为若干时序矩阵的最小数量
通信复杂度的下界：
$$CC(f)\ge \log_2\mathcal{X}(f)$$
每个时序矩阵对应一种通信协议路径(固定的比特序列) 若$\mathcal{X}(f)$时分块数，则至少需要$\log_2\mathcal{X}(f)$来区分（因$k$比特可表示$2^k$种）

$\log_2 \mathcal{X}(f)\to Alice\&Bob$都知道结果

示例1：传达$EQ(X,Y)=[x=y]$需要多少比特?

$\begin{bmatrix} · & 00 & 01 & 10 & 11 \\ 00 & 1 & 0 & 0 & 0 \\ 01 & 0 & 1 & 0 & 0 \\ 10 & 0 & 0 & 1 & 0 \\ 11 & 0 & 0 & 0 & 1 \end{bmatrix}$

若包含对角线元素则不能包含非对角线元素，否则通信协议会混淆，则每个对角线必须单独构成一个矩阵，共$2^n$个矩阵

$\therefore CC(EQ)\ge \log_2(2^n)=n\to$至少需要n比特通讯

示例2：传达$NAND(X,Y)=[\neg(x\wedge y)]$需要多少比特?

$\begin{bmatrix} · & 00 & 01 & 10 & 11 \\ 00 & 1 & 1 & 1 & 1 \\ 01 & 1 & 0 & 1 & 0 \\ 10 & 1 & 1 & 0 & 0 \\ 11 & 1 & 0 & 0 & 1 \end{bmatrix}$

$$\mathcal{X}(NAND)\ge 2^n \quad CC(F)>n$$

$rank(M(f))\text{与}\mathcal(X)(f)$

$$f(x,y)\quad M(f)_{2^n\times2^n}\to Matrix$$
$$M(f)\quad\text{into some rank 1 matrices}$$
$$rank(M(f))\le \mathcal{X}(f)$$
$$rank(A+B)\le rank(A)+rank(B)$$

L15

PNT素数定理

$$P\in[n^{100},n^{101}]\quad P\le m\sim\frac{m}{lnm}\quad \text{P存在性有保障}$$
Protoacl
$$Alice:x\in{0,1}^n \quad Bob:y\in{0,1}^n$$

1. 随机选择一个素数 $p\in \{n^{100},n^{101}\}$
2. Alice选择一个$t\in \{0,1,...,p-1\}$
3. Alice将$x$映射为多项式$f(t)=\sum x_it_i\quad mod \quad p$
4. Alice send $t\quad \text{and}\quad f(t)\quad$to Bob$(o(\log p)=o(\log n)\quad bits)$
5. 接收$t\quad \text{and}\quad f(t)\quad$compute $g(t)=\sum y_it_i\quad mod\quad p\quad$比较$f(t)\quad \text{and}\quad g(t)\quad$ 若相等，则为1否则为0
   若$f\ne g \quad \text{但}f(t)=g(t)\quad$说明$t$为$f-g$的根
   求$t\in \{0,1,...,p-1\}$是$h(x)=f(x)-g(x)$根的概率
   $$h(x)=\sum_{i=0}^{n-1}(x_i-y_i)t_i\quad mod \quad p$$
   其为非0多项式，且次数$\le n-1$(有限域熵多项式根的定理)，即最多$n-1$ 个根
   $$P(error)\le \frac{n-1}{p} \quad p\ge n^{100}$$
   $$\therefore \frac{n-1}{p}\le \frac{n}{n^{100} }\le o(n^{-99})$$

Max Entropy（多元情况）
最大熵分布是一个多元高斯$N(0,\Sigma)$
$$X\to d维 \quad E(X)=0\quad Cov(X)=XX^T=\Sigma$$
Let $Y\sim N(0,\Sigma)\quad Then \quad h(x)\le h(Y)$
$$D(X||Y)=\int f_X(t)\ln\frac{f_X(t)}{f_Y(t)}dt$$
$$=-h(x)-\int f_X(t)\ln f_Y(t)dt$$
$$=h(Y)-h(X)\ge0$$
由d维向量，可证：
$$f_Y(t)=\frac{1}{(2\pi)^{\frac{d}{2} }det(\Sigma)^{\frac{1}{2} } }exp(-\frac{1}{2}t^T\Sigma^{-1}t)$$
$$\ln f_Y(t)=-\frac{d}{2}\ln(2\pi)-\frac{1}{2}\ln det(\Sigma)-\frac{1}{2}t^T\Sigma t \quad (1)$$
$$-\int f_X(t)\ln f_Y(t)dt=\frac{d}{2}\ln(2\pi)+\frac{1}{2}\ln det(\Sigma)+\frac{1}{2}\int f_X(t)t^T\Sigma^{-1}tdt$$
$$t^T\Sigma^{-1}t\to E_X[t^T\Sigma^{-1}t]=tr(\Sigma^{-1}E[tt^T])$$
$$=tr(\Sigma^{-1}\Sigma)=tr(Id)=d$$
即
$$\frac{1}{2}\int f_X(t)t^T\Sigma^{-1}tdt=\frac{d}{2}\quad (2)$$
$$-\frac{d}{2}\ln(2\pi)+\frac{1}{2}\ln det(\Sigma)=\ln((2\pi)^{\frac{d}{2} }det(\Sigma)^{\frac{1}{2} })=\ln\frac{1}{f_Y^*(0)}$$
$$h(Y)=\frac{d}{2}\ln(2\pi)+\frac{1}{2}\ln det(\Sigma)+\frac{d}{2}$$
$$h(Y)=\frac{1}{2}\ln((2\pi e)^ddet(\Sigma)) \quad (3)$$

将（1）（2）（3）带入原式即可证明

❀完结撒花❀