自学笔记(4)

大二上学期的自学笔记，由四门离散数学课程组成。

一、信息论

1. 错误检测码

1. 奇偶校验码：在数据后加一位，使得 1 的个数为奇数或偶数（例：$\mathrm{ASCII}$）
2. 改进：按 $N$ 位划分数据块，添加 $N$ 位校验码
3. 加权校验码：$wxyz\to 4w+3x+2y+z$，再加一位使得和能被某数整除（例：身份证号）
4. $x_4=x_1+x_2,x_5=x_1+x_3,x_6=x_2+x_3$

2. 错误纠正码

1. 线性码：将 $k$ 位映射到 $n$ 位，$x=sG$，$G$ 为 $k\times n$ 矩阵
2. 校验：$Hy^T\neq 0$ 则有错，$H$ 为 $(n-k)\times n$ 矩阵，$HG^T=0$
3. 对偶码：将 $H$ 作为生成矩阵，$G$ 作为校验矩阵
4. 例：三重重复码、$(7,4)\ \mathrm{Hamming}$ 码 $(p_1=x_1+x_2+x_4,p_2=x_1+x_3+x_4,p_3=x_2+x_3+x_4)$

3. 数据压缩

1. 熵：$H(X)=-\sum p(x)\log p(x)$
2. 香农第一定理：编码平均长度 $\geq H(X)$，取等时必为平均分布
3. 数据压缩码：$\mathrm{Huffman}$ 码（最优前缀码、最优唯一可译码）

4. 信道编码

1. 定义 $P_{X,Y}(x_i,y_j)$：发出 $x_i$ 且接收 $y_j$ 的概率，$P_{Y|X}(y_j|x_i)$：发出 $x_i$ 时接收 $y_j$ 的条件概率
2. 熵：$H(X,Y)=-\sum P_{X,Y}(x_i,y_j)\log P_{X,Y}(x_i,y_j)$，$H(Y|X)=-\sum P_{X,Y}(x_i,y_j)\log P_{Y|X}(y_j|x_i)$
3. 链式法则：$H(X,Y)=H(X)+H(Y|X)$（信道的总熵等于输入的熵加上信道引入的熵）
4. 互信息：$I(x_i;y_j)=\log(\frac{1}{P_{X}(x_i)})-\log(\frac{1}{P_{X|Y}(x_i|y_j)})$（接收到 $y_j$ 后对 $x_i$ 的不确定性减少了多少）
5. 平均互信息：$I(X;Y)=\sum P_{X,Y}(x_i,y_j)I(x_i;y_j)=H(X)-H(X|Y)$
6. 性质：$I(X;Y)=H(X)$ 当且仅当无损；$I(X;Y)=0$ 当且仅当 $X,Y$ 独立（无信息量）
7. 信道容量：$\displaystyle C=\max_{P_X(\cdot)}I(X;Y)$（对所有可能的输入分布求最大平均互信息）
8. 香农第二定理：若 $R<C$，则存在编码使得误码率 $\to 0$，只要码长足够长；若 $R>C$，则任何编码误码率均有下限，其中 $R$ 为信道传输速率（用几个比特传输一个符号）

二、初等数论

三、组合数学

四、博弈论