1. 数学与信息论基础

# 数学基础

傅里叶变换 ( $F$ ) 是一种将信号从时域转换到频域的数学工具，其逆变换 ( $F^{-1}$ ) 则将信号从频域转换回时域。

傅里叶变换公式

$X(f) = F\{x(t)\} = \int_{-\infty}^{\infty} x(t)e^{-j2\pi ft}dt$
傅里叶逆变换公式

$x(t) = F^{-1}\{X(f)\} = \int_{-\infty}^{\infty} X(f)e^{j2\pi tf}df$

下面列举了一些常用函数的傅里叶变换。

狄拉克函数 $\delta(t)$

$F\{\delta(t)\} = 1$

$F\{\delta(t-\tau)\} = e^{-j2\pi \tau f}$

$F\{\delta_T(t)\} = F\{\sum_{n=-\infty}^{\infty}\delta(t-nT)\} = \frac{1}{T}\sum_{n=-\infty}^{\infty}\delta(f-\frac{n}{T})$
常数函数 $1$

$F\{1\} = \delta(f)$
余弦函数 $\cos(2\pi f_0t)$

$F\{\cos(2\pi f_0t)\} = \frac{1}{2}[\delta(f-f_0)+\delta(f+f_0)]$
辛克函数 $\text{sinc}(t)$
定义： $\text{sinc}(t)=\frac{\sin(\pi t)}{\pi t}$

$F\{\text{sinc}(t)\} = \text{rect}(f) = I_{|f|\le 0.5}$

$F^{-1}\{I_{|f|\le W}\} = 2W\frac{\sin(2\pi Wt)}{2\pi Wt} = 2W\text{sinc}(2Wt)$

这里 $I_{|f|\le W}$ 表示一个门函数或矩形函数，当 $|f| \le W$ 时值为 $1$ ，否则为 $0$ 。

事件的信息量
某个事件 $X=x_k$ 发生时所包含的信息量，定义为：

$H(X=x_k)=-\log p_k$

其中 $p_k$ 是该事件发生的概率。
独立事件的信息量
对于一组相互独立的事件 $x_1, x_2, \dots, x_n$

$H(x_1,x_2,\dots,x_n) = \sum_{k=1}^n H(X=x_k)$
熵（平均信息量）
随机变量 $X$ 的熵，表示其所有可能事件发生时的平均信息量，定义为：

$H(X)=-\sum_k p_k\log p_k$

其中 $p_k$ 是随机变量 $X$ 取值为 $x_k$ 的概率。
熵的界限
对于一个有 $K$ 个可能取值的随机变量 $X$ ，其熵的取值范围为：

$0 \le H(X) \le \log K$

当且仅当随机变量的每个取值概率相等，即 $p_k = 1/K$ 时，熵取最大值 $\log K$ 。
霍夫曼编码
霍夫曼编码的平均码长 $\bar{L}$ 满足：

$H(S) \le \bar{L} = \sum p_kl_k < H(S)+1$

其中 $H(S)$ 是信息源的熵， $l_k$ 是第 $k$ 个符号的码字长度。
霍夫曼编码的效率 $\eta$ 定义为：

$\eta=\frac{H(S)}{\bar{L}} \le 1$

联合熵
联合熵 $H(XY)$ 衡量一对随机变量 $(X, Y)$ 的不确定性，定义为：

$H(XY)=-\sum_i\sum_j p_{ij}\log p_{ij}$

联合熵与条件熵和边际熵的关系为：

$H(XY)=H(X) + H(Y|X)$

或

$H(XY)=H(Y) + H(X|Y)$
条件熵
条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的情况下，随机变量 $Y$ 的不确定性，定义为：

$H(Y|X)=-\sum_i\sum_j p_{ij}\log p_{j|i}$
独立随机变量的熵
当随机变量 $X$ 和 $Y$ 相互独立（ $X \perp Y$ ）时，它们之间的关系满足以下等价条件：

$H(XY) = H(X)+H(Y) \iff H(Y|X)=H(Y) \iff I(X;Y)=0$
函数关系随机变量的熵
当随机变量 $Y$ 是 $X$ 的函数（ $Y=f(X)$ ）时，它们之间的关系满足以下等价条件：

$H(XY) = H(X) \iff H(Y|X)=0$
熵的平移不变性
对于任意两个随机变量 $X$ 和 $Y$ ：

$H(X+Y|X) = H(Y|X)$

互信息
互信息 $I(X;Y)$ 衡量随机变量 $X$ 和 $Y$ 之间的相互依赖程度或共享的信息量，其定义和性质如下：

$I(X;Y) = \sum_i\sum_j p_{ij}\log\frac{p_{ij}}{p_ip_j}$

互信息和熵之间的关系：

$I(X;Y) = H(X)-H(X|Y) = H(Y)-H(Y|X) = H(X)+H(Y)-H(XY) \ge 0$
相对熵（KL 散度）
相对熵 $D(p||q)$ 衡量两个概率分布 $p$ 和 $q$ 之间的差异，也称为 KL 散度（Kullback-Leibler divergence）。

$D(p||q) = \sum_k p_k\log\frac{p_k}{q_k} \ge 0$

当且仅当两个分布完全相同时 ( $p=q$ )，相对熵取等号，值为 $0$ 。

信道容量 $C$ 表示信道可靠传输信息的最大速率，通常以比特/单位信息为单位。

可辨别信息数目 $N$
对于传输 $K$ 个独立同分布的信息，每个信息有 $n$ 种可能的取值，观察到输出 $Y$ 时，能够辨别的输入 $X$ 的最大种类数 $N$ 为：

$N = 2^{K\max_{p(X)}I(X;Y)}$
信道容量 $C$
信道容量是单位信息所能获得的可辨别信息数目。
以 $n$ 为底：

$C = \lim_{K\to\infty}\frac{\log_n N}{K} = \frac{\max_{p(x)}I(X;Y)}{\log_2 n}$

以 $2$ 为底（比特/单位信息）：

$C_{bit} = \lim_{K\to\infty}\frac{\log_2 N}{K} = \max_{p(x)}I(X;Y)$

例如，对于一个完全确定的信道，即输出 $Y$ 是输入 $X$ 的函数 ( $Y=f(X)$ )，则 $H(Y|X)=0$ ，因此 $I(X;Y)=H(Y) \le \log_2 n$ 。此时可辨别的信息种类数 $N=2^{K\max I(X;Y)} = n^K$ 。信道容量 $C_{bit} = \max I(X;Y) = \log_2 n$ ，而 $C=\max I(X;Y) / \log_2 n = 1$ 。
一个常见的例子是 二元对称信道（BSC, Binary Symmetric Channel）。

当随机变量为连续型时，相应的概念称为微分熵、联合微分熵等。

微分熵
连续随机变量 $X$ 的微分熵，定义为：

$h(X) = -\int_{-\infty}^{\infty} p(x)\log p(x)dx$
联合微分熵、条件微分熵与互信息

$h(XY) = -\int p(x,y)\log p(x,y)dxdy$

$h(Y|X) = -\int p(x,y)\log p(y|x)dxdy$

$I(X;Y) = \int p(x,y)\log\frac{p(x,y)}{p(x)p(y)}dxdy$

对于一个范围有限的随机变量，其微分熵存在上界。若 $|X| \le A/2$ ，则：

$h(X) \le \log A$
对于方差有限的随机变量，其微分熵存在上界。若 $E[X^2] \le \sigma^2$ ，则：

$h(X) \le \frac{1}{2}\log(2\pi e\sigma^2)$
微分熵具有伸缩性质。

$h(aX) = h(X)+\log|a|$

一维正态分布
若随机变量 $X$ 服从均值为 $\mu$ 、方差为 $\sigma^2$ 的正态分布 $N(\mu, \sigma^2)$ ，其概率密度函数为 $p(x) = \frac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{(x-\mu)^2}{2\sigma^2}}$ ，则其微分熵为：

$h(X) = \frac{1}{2}\log(2\pi e\sigma^2)$
多维正态分布
若 $n$ 维随机向量 $X$ 服从均值为 $\mu$ 、协方差矩阵为 $\Sigma$ 的多维正态分布 $N(\mu, \Sigma)$ ，其概率密度函数为 $p(x)=\frac{1}{\sqrt{(2\pi)^n|\Sigma|}}e^{-\frac{(x-\mu)^T\Sigma^{-1}(x-\mu)}{2}}$ ，则其微分熵为：

$h(X) = \frac{1}{2}\log[(2\pi e)^n|\Sigma|]$