序言
信源与信息熵
马尔可夫信源
定义
当信源记忆长度为 $m+1$ ，即当前符号与前 $m$ 个符号相关时，称其为 $m$ 阶马尔可夫链。
$$
\begin{array}\
p(x_1,x_2,…,x_{L})&\\
=p(x_L|x_1,x_2,…,x_{L-1})*p(x_1,x_2,…,x_{L-1})&\\
=p(x_L|x_{L-m},…,x_{L-1})*p(x_1,x_2,…,x_{L-1})&\\
\end{array}
$$
如果一个马尔科夫链的上述概率与时间无关，则称其为齐次马尔科夫链。
转移概率
对于 $m$ 阶马尔科夫链，将某一时刻前出现的 $m$ 个符号组成的序列定义为一个状态，即 $s_i=(x_{i_1},…,x_{i_m})$ 。
那么下一时刻，符号 $x_j$ 出现的概论只与 $s_i$ 有关，表示为 $p(x_j|s_i)$ 。 同时接收到新符号后，状态变为了 $s_j$ ，因此也可以用 $p(s_j|s_i)$ 表示。
更一般地，若时刻 $m$ 系统处于状态 $S_m=s_i$ ，经过 $n-m$ 步后的状态 $S_n=s_j$ ,则用可以用转移概率$p_{ij}(m,n)={S_n=s_j|S_m=s_i}$ 表示。对于 $n=m+1$ 的情况，可以简写成 $p_{ij}(m)$，而我们主要讨论的就是这种单步转移。
显然转移概率有以下两个性质
(1)
$p_{ij}(m,n)\ge 0$
(2)
$\Sigma_{j\in S}p_{ij}(m,n)=1$
更进一步，对于齐次马尔科夫链，其状态与时间无关，因此再简化成 $p_{ij}$ 。
需要注意 $p_{ij}=P(s_j|s_i)$。
我们用转移概率矩阵表示齐次马尔科夫链的概率分布。
$$
P=\begin{bmatrix}
p_{11}&p_{12}&…&p_{1n}\\
p_{21}&p_{22}&…&P{2n}\\
\vdots&\vdots&…&\vdots\\
p_{n1}&p_{n2}&…&p_{nn}
\end{bmatrix}
$$
平稳马尔科夫链
平稳马尔科夫链是齐次马尔科夫链的稳态形式，其不但转移概率不随时间改变，各个状态的分布也不随时间变化。
一般来说，平稳包含齐次，齐次不一定包含平稳。
平稳马尔科夫链的稳态概率满足 $\sum_iW_ip_{ij}=W_j$ ，因此可以通过概率分布矩阵构造方程组求解，即$WP=W$ 。
自信息量与信息熵的计算
自信息量
对于有 $m$ 个码元的系统而言，传输一个概率为 $p$ 的符号$x$ 需要 $I(x)$ 个码元，且满足，$m^{I(x)}*p=1$，因此我们定义自信息量$I(x)=-\log_m(p)$ 。
通常使用的底数有2，$e$ ，10，其对应的单位为 $bit$ 、$net$ 、$det$。
根据定义，自信息量满足以下规律，
$p(x)=1,I(x)=0$
$p(x)=0,I(x)=\infty$
非负性
$I(x)\ge0$
单调递减
若 $p(x_1)<p(x_2)$ ，则 $I(x_1)>I(x_2)$
可加性
当符号 $x$、$y$ 独立时， $I(x,y)=I(x)+I(y)$
当两个符号不独立时， $I(x,y)=I(x|y)+I(y)=I(y|x)+I(x)$
信源熵
信源熵是信源中各符号自信息量的期望，即 $H(X)=E(I(X))=\sum_iI(x_i)$，熵即是不确定性，
它有以下特性
- 非负性
- 确定性信源熵为0
二元信源熵
$H(X)=H(p)=-p\log_2p-(1-p)\log_2(1-p)$
条件熵
单变量条件熵
$H(y|X)=\sum_ip(y|x_i)\ log_2\ p(y|x_i)$
$H(Y|x)=-\sum_jp(y_j|x)\ \log_2\ p(y_j|x)$
双变量条件熵
$H(Y|X)=-\sum_{ij}p(y_i,x_j)\ \log_2\ p(y_i|x_j)$
联合熵
联合熵的计算公式
$H(X,Y)=-\sum_{ij}p(x_i,y_j)\ \log_2\ p(x_i,y_j)$
联合熵与条件熵的关系
$H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y)$
互信息
互信息量计算公式
$I(x;y)$是指符号 $y$ 中包含的关于符号 $x$ 的信息量，即$I(x)-I(y|x)=\log_2\frac{p(y|x)}{p(x)}$
$I(X;Y)=\sum_{i,j}p(x_i,y_j)\ \log_2\ \frac{p(x_i|y_j)}{p(y_j)}$
$0\le I(X;Y)\le H(X)$
互信息量和熵的关系
$I(X;Y)=I(Y;X)=H(X)-H(X|Y)=H(Y)-H(Y|X)$
$I(X;Y)=H(X)+H(Y)-H(X,Y)$
条件互信息量
在三变量的情况下，
符号 $x$ 与符号对$(y,z)$ 之间的信息量 $I(x;y,z)=\log_2\frac{p(x|y,z)}{px}$。
给定符号$z$ 时，$x$ 、$y$ 之间的互信息量可以表示成 $I(x;y|z)$。
$I(x;y|z)=I(x|z)-I(x|y;z)=\log_2\frac{p(x|y,z)}{p(x|z)}$
$I(X;Y|Z)=\sum_{x,y,z}\frac{p(x|y,z)}{p(x|z)}$
$I(X;Y|Z)=H(X|Z)-H(X|Y,Z)=H(Y|Z)-H(Y|X,Z)$
信息不增原理
对于输入变量 $X$，一级输出变量 $Y$ ，2级输出变量 $Z$，若满足 $p(x,z|y)=p(x|y)p(z|y)$，即在 $Y$ 出现的情况下 $X$ 、$Z$相互独立，此时有马尔科夫链 $X\rightarrow Y\rightarrow Z$。
则 $I(X;Z)\le I(Y;Z)$
相对熵
$D(p//q)=\sum_ip_i\log_2\frac{p_i}{q_i}$
$I(X;Y)=D(X,Y//X\times Y)$
熵的性质
非负性
$H(X)=0$ 当且仅当存在 $p_i=1$
对称性
信源熵只与概率分布的总体结构有关，不受符号与概率之间对应关系的影响。
香农辅助定理
任意概率分布本身的熵必小于它对其他概率分布的数学期望
$-\sum_ip_ilog_2p_i\le-\sum_ip_ilog_2q_i$
最大熵定理
当各符号等概分布时，熵取最大值。
$H(X)\le \log_2M$ ，$M$ 为符号数量。
$H(X|Y)\le H(X)$
$H(X,Y)\le H(X)+H(Y)$
由互信息的性质得出
扩展性
$\lim\limits_{\varepsilon\to 0}H(p_1,p_2,…,p_n-\varepsilon,\varepsilon)=H(p_1,p_2,…,p_n)$
$H(p_1,p_2,…,p_n-\delta,\delta)\gt H(p_1,p_2,…,p_n)$
序列信源熵
$\mathbf X=(X_1,X_2,…,X_n)$
信源无记忆
$H(\mathbf X)=\sum_{i_1}\sum_{i_2}…\sum_{i_n} p(x_{i_1},x_{i_2}…,x_{i_n})\log2p(x_{i_1},x_{i_2}…,x_{i_n})$
在此基础上信源平稳，
$H(\mathbf X)=LH(X)$
平均符号熵 $H_L(X)=\frac{1}{L}H(\mathbf X)=H(X)$
信源有记忆
$H(\mathbf X)=H(X_1)+H(X_2|X_1)+…+H(X_n|X_1,X_2,…X_{n-1})$
记作 $H(\mathbf X)=H(X^n)$=$\sum_iH(X_i|X^{i-1})$
序列信源熵的性质
$H(X_L|X^{L-1})$ 是 $L$ 的单调非增函数
这是由符号间的关联性导致的，符号数目越多，关联性越强，不确定度就越小。
$H(\mathbf X)\ge H(X_L|X^{L-1})$
从 $H(\mathbf X)$ 的表达式以及熵的非负性推出。
$H_L(\mathbf X)$ 是 $L$ 的单调非增函数
$H_L(\mathbf X)\ge H_{L+1}(\mathbf X)$
由符号之间的关联性引起。
极限信息量
$H_{\infty}=\lim\limits_{L\to\infty} H_L(\mathbf X)$
$H_0(\mathbf X)\ge H_1(\mathbf X)\ge…\ge H_{\infty}(\mathbf X)$
马尔可夫链的极限熵
$H(\mathbf X)=\underset{i=1}{\overset{n}{\Sigma}}W_iH(X|s_i)$
连续信源熵
连续信源熵是无穷！
通常用微分熵代替熵的计算
微分熵
$H_c(X)=-\int_{-\infty}^{+\infty}p_X(x)\log_2p_X(x)dx$
条件熵
$H_c(Y|X)=-\int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty}p_{X}(x)p_Y(y|x)\log_2p_{Y}(y|x)dxdy$
联合熵
$H_c(X,Y)=-\int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty}p_{X,Y}(x,y)\log_2p_{X,Y}(x,y)dxdy$
限平均功率的最大熵定理
对于随机变量 $\mathbf X$，当且仅当它是正态分布时熵最大。
若 $\mathbf X\sim N(\mu,\sigma^2)$，则 $H_c(\mathbf X)=\frac{1}{2}\log_22\pi e\sigma^2$。
由此可知，当信源属于正态分布时，熵仅和 $\sigma^2$ 有关，该变量在物理上往往是指信源的功率。
根据限平均功率最大熵定理，当噪声符号正态分布时，其对信道干扰最大，因此我们研究高斯白噪声其实就是在研究信道在最坏情况下的传输能力。
冗余度
信息效率
$\eta=\frac{H_{\infty}(X)}{H_m(X)}$
冗余度
$\gamma=1-\eta$
信道与信道容量
信道的数学模型
信道分类
对于信道输入 $\mathbf X={X_1,X_2,…,X_n}$ ，输出 $\mathbf Y={Y_1,Y_2,…,Y_n}$，通常使用 $p(\mathbf Y|\mathbf X)$ 来表示信道输入输出之间的依赖关系，即转移概率。
据此我们将信道分为以下三类
有干扰无记忆信道
无干扰无记忆信道
该类信道的转移概率满足以下条件
$$
p(\mathbf Y|\mathbf X)=
\left{
\begin{array}{rcl}
1,\mathbf Y=f(\mathbf X)\\
0,\mathbf Y\ne f(\mathbf X)
\end{array}
\right.
$$有干扰无记忆信道
该类信道的转移概率并不恒为0或1，根据其输入输出数据的类型又分为下面三类
离散无记忆信道
这类信源可以用马尔科夫链的转移概率矩阵描述。
$$
\begin{bmatrix}
p_{11}&p_{12}&…&p_{1n}\\
p_{21}&…&…&p_{2n}\\
\vdots&\cdots&\cdots&\vdots\\
p_{n1}&p_{n2}&…&p_{nn}
\end{bmatrix}
$$离散输入，连续输出信道（不考）
这类信道往往存在噪声，其中以加性高斯白噪声最为重要。对于含有这类噪声的信道，输入输出之间的关系为
$$
Y=X+G
$$
其中 $G\sim N(0,\sigma^2)$，而 $p_Y(y|x_i)=\frac{1}{\sqrt{2\pi\sigma}}e^{-\frac{(y-x_i)^2}{2\sigma^2}}$波形信道（不考）
该类信道中我们着重关注含有加性噪声的情况，其关系式如下
$$
y(t)=x(t)+n(t)
$$
可以证明，在输入信号与噪声互相独立的情况下，
$$
H_c(Y|X)=H_c(n)
$$
信道容量
定义平均每个符号所传输的信息量是信息传输率。根据定义可以得出
$$
R=I(X;Y)=H(X)-H(Y|X)
$$
其单位是 bit/符号 或 bit/s。
显然应当存在某种输入信号的分布使得信息传输率最大，我们称此时的信息传输率为信道容量。
$$
C=\underset{p(a_i)}{max}I(X;Y)
$$
离散单符号信道容量
无干扰信道
假定输入 $X\in{a_1,a_2,…a_n}$ ，输出 $Y\in{b_1,b_2,…,b_m}$。
分以下几种情况
$n=m$
这种情况下输入输出一一对应，即 $H(Y|X)=0$，$I(X;Y)=H(X)=H(Y)$。
根据最大熵定理，当输入等概时，$H(X)$ 取最大值 $\log_2$n。
$$
C=maxI(X;Y)=\log_xn
$$$n>m$
这种情况下，$H(X|Y)=0$ ，因此信道容量取决于 $H(Y)$ 。
因而当输出等概分布时信道容量取最大值。
$$
C=maxH(Y)=\log_2m
$$$n<m$
这种情况与前一种正好相反，在输入等概时取最大值。
$$
C=maxH(Y)=\log_2n
$$
综上所述，离散单符号无干扰信道的容量 $C=\log_2(min{n,m})$。
离散对称无记忆信道
对称
若一个离散无记忆信道的转移概率矩阵的每一行都是第一行的置换，则称其为输入对称信道。
若一个离散无记忆信道的转移概率矩阵的每一列都是第一列的置换，则称其为输出对称信道。
若一个离散无记忆信道既是输入对称的又是输出对称的，则其是一个离散对称无记忆信道（DMC）。
DMC的容量
当输入符号等概分布时，DMC的容量取最大值
$$
C=log_2m-H(Y|a_i)=\log_2m+\underset{j}{\Sigma}p_{ij}log_2(p_{ij})
$$
其中 $m$ 是信道输出符号个数。
离散无记忆模K加性噪声信道
这是一种特殊的DMC信道，$X\in Z_K$ 是输入，$Y\in Z_K$ 是输出 ，$Z$ 的信道干扰，满足
$$
Y=X+Z\ mod\ K
$$
这类信道有恒等式 $H(Y|X)=H(Z)$ ，因此容易得出其信道容量
$$
C=log_2K-H(Z)
$$
BSC信道
二进制离散信道（BSC）也是DMC的一种，其转移概率矩阵如下
$$
\begin{bmatrix}
1-p&p\\
p&1-p
\end{bmatrix}
$$
根据DMC信道容量计算规则得到
$$
C=1-H(p)
$$
信道串接
信道串接在数学上的处理是将多个信道的转移概率矩阵按序相乘。
一般来说，串接信道越多，信息传输率或信道容量越小。
准对称DMC信道
准对称DMC信道是指输入对称而输出不对称的DMC信道。
该信道被称为准对称是因为其转移概率矩阵可以被划分成若干个对称DMC信道的矩阵的组合。
$$
C=\log_2n-H(p_{11},p_{12},…,p_{1m})-\underset{k=1}{\Sigma}N_klog_2M_k
$$
其中 $n$为输入符号个数，$m$ 为输出符号个数，$N_k$ 是第k个子矩阵行元素之和，$M_k$ 是第k个矩阵列元素之和。
离散序列信道容量
对于连续信道的输入矢量 $\mathbf X$ 和输出矢量 $\mathbf Y$ ，则其互信息量 $I(\mathbf X;\mathbf Y)$ 有以下两个不等式
$\mathbf X$ 中各矢独立
$$
I(\mathbf X|\mathbf Y)\ge \underset{l=1}{\overset{L}{\Sigma}}I(X_l;Y_l)
$$信道无记忆
$$
I(\mathbf X|\mathbf Y)\le \underset{l=1}{\overset{L}{\Sigma}}I(X_l;Y_l)
$$
显然当两个条件都满足时，互信息量可以计算。
此时，信道容量有
$$
C_L=\underset{p_X}{max}I(\mathbf X;\mathbf Y)=\underset{p_X}{max}\underset{l=1}{\overset{L}{\Sigma}}I(X_l;Y_l)=\underset{l=1}{\overset{L}{\Sigma}}\underset{p_X}{max}I(X_l;Y_l)=\underset{l=1}{\overset{L}{\Sigma}}C(l)
$$
当信道平稳时，$C_L=LC_1$。
连续信道容量
连续单符号加性信道
我们先来研究噪声是加性高斯白噪声的情况，即噪声的分布 $n\sim N(0,\sigma^2)$。
在此前提下，我们得出该噪声的微分熵 $H(n)=\frac{1}{2}\log_2\pi e\sigma^2$。再进一步得出该信道的信道容量
$$
C=\underset{p_x}{max}H_c(Y)-\frac{1}{2}\log_22\pi e\sigma^2
$$
而前文提到，当且仅当 $Y\sim N(0,P)$ 时 $Y$ 的微分熵达到最大值，故上式可进一步展开为
$$
C=\frac{1}{2}\log_22\pi eP-\frac{1}{2}\log_22\pi e\sigma^2=\frac{1}{2}\log_2\frac{P}{\sigma^2}=\frac{1}{2}\log_2(1+\frac{S}{\sigma^2})
$$
其中 $\frac{S}{\sigma^2}$ 就表示信噪比，记作 $SNR$。
而在一般情况下，噪声并不是正态分布的，因而有下面不等式
$$
\frac{1}{2}\log_2(1+\frac{S}{\sigma^2})\le C\le \frac{1}{2}\log_22\pi eP-H_c(n)
$$
多维无记忆连续信道
注水法
香农公式
$$
C_t=\underset{t_B\to\infty}{lim}\frac{C}{t_B}=Wlog(1+\frac{P_s}{N_0W})=Wlog(1+SNR)
$$
$W$是带宽，$P_s$ 是信号的平均功率，$N_0W$是噪声的平均功率，$log(1+SNR)$称为频带利用率。
极限容量
$$
C_{\infty}=\frac{P_s}{N_0ln2}
$$
信源编码
编码概念
编码分类
$$
编码
\left{
\begin{array}{rcl}
非分组码&\\
分组码&
\left{
\begin{array}{rcl}
奇异码&\\
非奇异码&
\left{
\begin{array}{rcl}
非可唯一译码&\\
可唯一译码&
\left{
\begin{array}{rcl}
延长码&\\
即时码&
\end{array}
\right.
\end{array}
\right.
\end{array}
\right.
\end{array}
\right.
$$
奇异码是指码字和信源符号一一对应的码。
唯一译码是码元只能被唯一分割的码。
即时码指接收端收到完整码字后不必查看下一位即可译码的编码，也称异前缀码。
$Kraft$ 不等式
唯一可译码存在的充要条件
$$
\underset{i=1}{\overset{n}{\Sigma}}m^{-K_i}\le1
$$
上式中， $m$ 是码字的进制，$K_i$ 是各个码字的长度。
需要注意，该式是唯一可译码存在的充要条件，即唯一可译码必然满足表达式；满足表达式的码长一定可用构造出唯一可译码。但是对于一个已经给定的编码方式，即使满足表达式我们也不能认为其是唯一可译码，因为是否是唯一可译码还取决于具体的编码方式。
无失真编码定理
码字的信息量
若码字符号集 $Y\in{Y_1,Y_2,…Y_m}$ ，则长度为 $K_L$ 的码字的最大信息量为 $K_L\log_2m$，传输一个信源符号所需的二进制平均长度 $\overline{K}=\frac{K_L}{L}\log_2m$。
定长编码定理
定长编码定理
由 $L$ 个平均符号熵为 $H_L(X)$ 的无记忆平稳序列可用 $K_L$ 个码元符号组成的序列编码。
$$
\frac{K_L}{L}\log_2m\ge H_L(X)+\varepsilon
$$
即码元的平均符号熵应略大于信源的平均符号熵。
差错率
$$
L\ge\frac{D^2(X)}{\varepsilon^2\delta}
$$
当 $\varepsilon$ 和 $D(X)$ （即信源自信息量的方差）一定时，只要编码的序列长度满足上式，就能达到差错率的要求。
编码效率
$$
\eta=\frac{H_L(X)}{\overline{K}}=\frac{H_L(X)}{H_L(X)+\varepsilon}
$$
显然，$\underset{L\to \infty}{lim} \eta=1$ 。
变长编码
单符号变长编码定理
离散无记忆信源熵为 $H(X)$ ，用 $m$ 元编码表示之，则一定存在一种无失真编码，其满足
$$
\frac{H(X)}{\log_2m}\le \overline{K}\lt \frac{H(X)}{\log_2m}+1
$$
香农编码
符号重排
将信源符号按概率从大到小排列 $p_1\ge p_2\ge…\ge p_n$
选择码长
按照香农第一定理选择码长
$$
I(x_i)\le K_i \lt I(x_i)+1
$$计算累加概率
$$
P_i=\underset{i=0}{\overset{i-1}{\Sigma}} p(x_i)\ ,\ p(x_0)=0
$$编码
对于符号 $x_i$ 的编码，将累加概率 $P_i$ 转成二进制并去前 $K_i$ 位。
哈夫曼编码
略
算术编码
初始化
$$
\left{
\begin{array}{rcl}
&C(\phi)=0\\
&A(\phi)=1r
\end{array}
\right.
$$计算累加概率 $P_r$
同香农编码
递推
$$
\left{
\begin{array}{rcl}
&C(S,r)=C(S)+A(S)P_r\\
&A(S,r)=A(S)p_r
\end{array}
\right.
$$编码
$$
L=\lfloor\log_2\frac{1}{A(S)}\rfloor
$$
之后取 $C(S)$ 二进制小数点后 $L$ 位
信道编码
码空间
n维空间
在二元域 $F_2$ 上的矢量集合 $\mathbf V={v_i}$ ，$||v_i||=n$ ，若其满足以下条件，则称该矢量集合构成一个n维空间
- $\mathbf V$ 中元素在矢量加法下构成加法群
- $\mathbf V$ 中元素与 $F_2$ 中元素乘法关于 $\mathbf V$ 封闭
- 满足分配律和结合律
基底
对于数域 $F$ 上的若干矢量 $\mathbf v_1,\mathbf v_2,…\mathbf v_n$ ，若存在 $a_1,a_2,…,a_n$ 使得
$$
a_1 \mathbf v_1+a_2\mathbf v2+…+a_n\mathbf v_n=\mathbf 0
$$
则称这组矢量是线性相关的。
若存在一组矢量 $\mathbf v_1,…,\mathbf v_n$ 是线性无关的且它们构成一个n维空间，则称这组矢量的该空间的基底。
一个n维线性空间的一组基底应当有n个矢量，同一个线性空间的基底是不唯一的。
对偶空间
若线性空间 $\mathbf V_1$ 中任意矢量与线性空间 $\mathbf V_2$ 中任意矢量的内积为0，则称这两个线性空间正交。
若两个线性空间的基底正交，则这两个线性空间一定正交。
正交的两个线性空间互为对偶空间，其中一个是另一个的零空间（零化空间）。
信道编码定理
$$
P_e\lt e^{-NE(R)}
$$
其中 $P_e$ 是平均差错率， $E(R)$ 是可靠性函数
该定理表明，只要信息传输率 $R$ 小于信道容量 $C$ ，则一定可以找到一种信道码能够以任意小的差错率实现编码。
最优译码
译码器
译码器的工作是从接收到的受损信息中尽可能的正确的恢复出原文信息，即
- 接受到实际码字 $\mathbf r$
- 信道编码解码得到带有一定错误率的信源编码 $\mathbf c_i$
- 通过最优译码得出真实信源发送码字的估值序列 $\widehat{\mathbf c}_i$
- 信源编码解码还原消息 $\mathbf m_i$
最优译码
最佳译码
$$
\widehat{\mathbf c}_i=MaxP(\mathbf c_i|\mathbf r)
$$
即通过经验总结和归纳得出接受码字的后验概率，然后从中选出后验概率最大者作为正确码字。
该方法也被称为最大后验概率译码，因为是从后验概率出发，因而也是最优的解码方法。但实际操作中，后验概率往往是很难得到的。
最大似然译码
$$
\widehat{\mathbf c}_i=MaxP(\mathbf r|\mathbf c_i)
$$
该方法使用先验概率作为判断依据，其中 $P(\mathbf r|\mathbf c_1)$ 被称为似然函数，似然函数在实际工作中比较容易获取。
先验概率和后验概率可以通过贝叶斯公式联系起来
$$
P(\mathbf c_i|\mathbf r)=\frac{P(\mathbf c_i)*P(\mathbf r|\mathbf c_i)}{P(\mathbf r)}
$$
实际通信中，最大似然译码的有效性略差于最优译码，但可以通过改良信道弥补部分差距，而先验概率又比较容易获取，因此最大似然译码是最常用的译码方法。
对于无记忆信道
$$
MaxP(\mathbf r|\mathbf c_i)=Max\prod_{j=1}^nP(r_j|c_{ij})
$$
有时为简化运算，常用其等效函数对数似然函数。
$$
Max\ logP(\mathbf r|\mathbf c_i)=Max\ log\sum_{j=1}^nP(r_j|c_{ij})
$$
底数可以是2，e，10。
最小汉明距离
对于 BSC 信道，最大似然译码简化成最小汉明距离译码，此时先验概率简化为
$$
P(r_i|c_{ij})=
\left{
\begin{array}{rcl}
&p\ ,\ \ c_{ij}\ne r\\
&1-p\ ,\ \ c_{ij}=r
\end{array}
\right.
$$
定义 $\mathbf r$ 与 $\mathbf c$ 的不同位个数 $d$ 是汉明距离，则最大似然函数变为关于 $d$ 的一元函数
$$
P(\mathbf r|\mathbf c_i)=p^d(1-p)^{N-d}=(\frac{p}{1-p})^d*(1-p)^N
$$
这是关于 $d$ 的单调递减函数，因此最优译码问题变成求最小汉明距离问题。
线性分组码
生成矩阵
令 $\mathbf g_0,\mathbf g_2,…,\mathbf g_{n-1}$ 是m维码空间 $C$ 的一组基底，则该空间中的任意矢量（码字）可以表示成
$$
\mathbf c=m_{n-1}\mathbf g_{n-1}+m_{n-2}\mathbf g_{n-2}+…+m_{0}\mathbf g_{0}
$$
若基底以列向量表示，则我们称 $\mathbf G=[\mathbf g_{n-1}\ \mathbf g_{n-1}\ …\ \mathbf g_0]^T$ 为该$(m,n)$线性分组码的生成矩阵，则
$\mathbf c=\mathbf m\mathbf G$
系统化
$$
\mathbf G=[\mathbf I_n|\mathbf P]=
\left[\begin{array}{cccc|cccc}
1&0&…&0&p_{(n-1){(m-n-1)}}&\cdots&p{(n-1){1}}&p{(n-1){0}}\\
0&1&…&0&\vdots&\ddots&\vdots&\vdots\\
\vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&\cdots&1&p{0_{(m-n-1)}}&\cdots&p_{0_1}&p_{0_0}
\end{array}\right]
$$
该矩阵由原生成矩阵经过线性变换得到。
校验矩阵
一个 $(m,n)$ 线性分组码的生成矩阵只使用了该m维空间的n个基底，剩下 $m-n$ 个基底应当也可以组成一个 $(m,m-n)$ 线性分组码，它是这个 $(m,n)$ 线性分组码的对偶码。由于两个码空间的基底同属于一个m维线性空间，因此它们之间是线性无关的，即两个码空间互为对偶空间，即
$$
\mathbf c\mathbf H^T=\mathbf 0\
\mathbf G\mathbf H^T=\mathbf 0
$$
$\mathbf H$ 是 $(m,m-n)$ 线性分组码的生成矩阵，也是 $(m,n)$ 线性分组码的校验矩阵。
即线性分组码的校验矩阵是其对偶空间的生成矩阵。
利用系统码求校验矩阵
对于一个系统化的线性分组码，其校验矩阵可以通过系统矩阵快速得出
$$
\mathbf H=[-\mathbf P^T|I_{m-n}]
$$
在二元域下， $\mathbf P$ 前面的符号可以忽略。
伴随式与标准阵列译码
差错图案
$$
\mathbf E=\mathbf R-\mathbf C
$$
其中 $\mathbf R$ 是收码， $\mathbf C$ 是发码。
伴随式
利用校验矩阵检查收码是否有误
$$
\mathbf S=\mathbf R\mathbf H^T=(\mathbf C+\mathbf E)\mathbf H^T=\mathbf E\mathbf H^T
$$
这里的 $\mathbf S$ 就是伴随式，是一个 $m-n$ 元矢量，其所代表的$m$元方程组只有 $m-n$ 个方程，在二元域下有 $2^n$ 个解，即最终差错图样有 $2^n$ 中可能性。
由于 $||\mathbf E||$ 即汉明距离，根据最大似然译码，汉明距离最小的差错图样出现的可能性最大，因此我们选取这 $2^n$ 个解中汉明距离最小的作为真实的差错图样。
标准阵列译码
由于解伴随式的计算量比较大，因此考虑用查表的方法解码，下面介绍标准阵列译码。
- 代入 $\mathbf S$ 的 $2^{m-n}$ 中情况，解出伴随式，并选取 $||\mathbf E||$ 最小者作为真实的差错图样。
- 构造 $2^{m-n}\times2^n$ 的表格。表格行标是伴随式的取值，列标是发码的码字。
- 第一行填入 $2^n$ 个发码码字$\mathbf C_i$，该行所对应的伴随式为全0，即发码等于收码。
- 第一列根据每列所对应的伴随式的值填入求解的最小差错图样 $\mathbf E_i$，此列对应发码为全0的情况，即收码等于差错图样。
- 对于剩下的格点第 $i$ 行 $j$ 列填入 $\mathbf E_i\bigoplus \mathbf C_j$ 。
译码过程如下
在表格中找出收码所在位置 $(i,j)$ 。
该步骤可以直接对表进行遍历，也可以根据 $\mathbf S=\mathbf R\mathbf H^T$ 算出伴随式，然后在对应行做一维搜索。
找出 $(1,j)$ 位置的码字作为发码。
该步骤也可以计算 $\mathbf R\bigoplus \mathbf E_i$ 来得到发码。
纠错能力
码距与最小距离
码距表示了码集中码字之间的差异。
$d=||\mathbf C_1\bigoplus\mathbf C_2||$
定理一 线性分组码的最小距离 $d_{min}=min{||\mathbf C_i||}$。
定理二 $(n,k)$ 线性分组码的最小距离为 $d_{min}$ 的必要条件是其校验矩阵 $\mathbf H$ 中有 $d_{min}-1$ 列线性无关，即最小距离的上限是 $R(\mathbf H)+1$。
定理三 $(n,k)$ 线性分组码的最小距离一定满足 $d_{min}\le n-k+1$。
若$(n,k)$线性分组码的最小距离满足定理三的等号，则称该线性分组码是极大最小距离码（MDC) 。
纠错能力与检错能力
信道在传输码字的过程中，会使码字产生差错，如果该差错正好使得一个码字变成了另一个码字，解码方只会认为自己收到了另一个码字而没有检错能力；同样地，假使两个码字的码距是 $d$ ，如果传输过程中码字产生了不多于 $d/2$ 位差错，收码方可以根据最优译码纠错，反之若大于这个数，收码方则会将其解释成另一码字。
定理四 任何最小距离为 $d_{min}$ 的线性分组码，其检错能力为 $d_{min}-1$ ，纠错能力为 $[\frac{d_{min}-1}{2}]$。
完备码
对于 $(n,k)$ 线性分组码的码字，其差错图样有 $\sum_{i=0}^kC_n^i$ 中可能。如果该码的纠错能力是 $k$ ，则应当满足
$$
2^{n-k}\ge \sum_{i=1}^tC_n^i
$$
该式称为汉明限。
将其中满足
$$
2^{n-k}=\sum_{i=1}^tC_n^i
$$
的 $(n,k)$ 线性分组码称为完备码。
汉明码
汉明码是纠错能力为1的完备码的统称。
$(n,k)$ 汉明码服从 $(n,k)=(2^m-1,2^m-1-m)$ ，其中 $m=n-k$。
汉明码的构造
汉明码的校验矩阵具有特殊性，$(n,k)$ 线性分组码的校验矩阵是 $(n-k)\times n$ ，而汉明码满足 $n=2^m-1$ 正好是 $m$ 长非零进制数。因此只要将 $n-k$ 长度的非零二进制数作为 $\mathbf H$ 的列排列即可。
循环码
码多项式
若 $\mathbf C=c_{n-1}c_{n-2}…c_0$ ，则 $C(x)=c_{n-1}x^{n-1}+c_{n-2}x^{n-1}+…+c_0$称为该码字的码多项式。
生成多项式
由于循环码满足一个码字的循环位移仍是码字，因而其生成矩阵的基底也是一个基底的循环位移。称这个基底对应的多项式为生成多项式，从而简化编码运算。
循环码构造
构造 $(n,k)$ 循环码方法如下
分解 $x^n+1$ ，找出其中次数为 $n-k$ 次的因子。
以该 $n-k$ 次因式$g(x)$作为循环码的生成多项式，码字计算规则如下
$$
\mathbf C(x)=m(x)g(x)
$$
校验多项式
若 $g(x)$ 为循环码的生成多项式，$h(x)=\frac{x^n+1}{g(x)}$ 就是该码的校验矩阵。
$$
C(x)h(x)=m(x)g(x)h(x)=m(x)(x^n+1)=0\ mod\ x^n+1
$$
类似码空间，$g(x)$ 所构造的 $(n,k)$ 循环码与 $h(x)$ 所构造的 $(n,n-k)$ 循环码互为对偶码。
系统循环码
系统循环码具有如下形式
$$
C(x)=x^{n-k}m(x)+r(x)
$$
由于等式两边模 $g(x)$ 为0，我们可以通过这一性质计算 $r(x)$ 。
$$
\begin{align}
&x^{n-k}m(x)+r(x)\ mod\ g(x)=0\\
&\Leftrightarrow r(x)=2^{n-k}m(x)\ mod\ g(x)
\end{align}
$$
因此系统循环码构造方法如下
- 根据需要确定 $g(x)$
- $m(x)$ 乘以 $x^{n-k}$，即左移 $n-k$ 位。
- 将 $x^{n-k}m(x)$ 除 $g(x)$ 的余数作为 $r(x)$
- 取 $C(x)=x^{n-k}m(x)+r(x)$