基础信息论知识汇总

这是一篇笔者的《信息论与编码》课内学习笔记，最近刚考完信息论，分享下自己的笔记吧😀希望能出个好成绩

个人感觉这门课最有用的就是香农三大定理了，尤其是香农公式给出了信噪比和带宽的需求关系

离散单符号信源

基础概率表示

• 无条件概率（先验概率）
  $$
  p(a_i)
  $$
• 条件概率(后验概率)
  $$
  p(a_i/b_j)
  $$
• 联合概率
  $$
  p(a_ib_j)=p(b_j)p(a_i/b_j)=p(a_i)p(b_j/a_i)
  $$

  信息量

• 概率的降函数
• 度量
  $$
  自信息量I(x_i)=\log \frac 1{p(x_i)} = -\log p(x_i) \\
  联合自信息量 I(a_ib_j)=-\log_2p(a_ib_j) \\
  条件自信息量 I(a_i/b_j)=-\log_2p(a_i/b_j) \\
  互信息量I(x_i;y_i) = \log_2 \frac {p(x_i|y_i)} {p(x_i)}= I(x_i)-I(x_i/y_i) \\
  条件互信息量 I(a_i;b_j/c_k)=\log _2\frac {p(a_i/b_jc_k)}{p(a_i/c_k)}
  $$
  • bit：2底
  • nat：e底
  • hart：10底
• 互信息量性质
  • 互易性
    $$
    I(a_i;b_j) = I(b_j;a_i)
    $$
  • 统计独立时，互信息量为0
  • 只有互信息量可为负,此时表示信道受到干扰或者错误
• 联合互信息量
  $$
  I(a_i;b_jc_k)=I(a_i;c_k)+I(a_i;b_j|c_k)
  $$

信息熵

$$
信源熵H(X)=E[I(x_i)]=E[-\log p(x_i)] \\
条件熵H(X|Y)= E[I(a_i|b_j)]=\sum^m_{j=1}\sum^n_{i=1} p(a_ib_j)I(a_i|b_j) \\
联合熵H(X,Y)=\sum^n_{i=1}\sum^m_{j=1} p(a_ib_j)I(a_ib_j)
$$
注意
$$
H_r(x)=\frac {H(x)}{\log_2r}
$$

• 可加性
  $$
  H(XY)=H(X)+H(Y/X)=H(Y)+H(X/Y)
  $$
  • 各熵之间关系
    $$
    H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y) \\
    H(X)-H(X|Y)=H(Y)-H(Y|X) \\
    H(X_1,X_2,\cdots,X_N)=H(X_1)+H(X_2|X_1)+\cdots+H(X_N|X_1X_2\cdots X_N)
    $$
• 联合熵也叫共熵
• 意义
  • 信源输出后，每个消息的平均信息量
  • 信源输出前，平均不确定度
• 条件熵
  • 损失熵=信道疑义度：在获得输出的情况下对信源的不确定度
    $$
    H(X|Y)
    $$
  • 噪声熵：在已知输入的情况下，由于噪声造成对输出不确定
    $$
    H(Y|X)
    $$
• 最大熵定理
  $$
  H(p_1,p_2,\cdots,p_n)\le H(\frac 1n,\frac 1n,\cdots,\frac 1n)=\log n
  $$
• 极值定理
  $$
  \because X和Y消息个数相同 \\ \therefore
  H_n[p(a_1),p(a_2),\cdots,p(a_n)]\le -\sum^n_{i=1}p(a_i)\log_2p(b_i) \\
  H(X/Y) \le H(X)
  $$
  注意：条件熵小于信源熵
• 扩展性
  $$
  \lim_{\epsilon\to0}H_{n+1} [p(a_1),p(a_2),\cdots,p(a_n)-\epsilon,p(a_{n+1})=\epsilon] \\ = H_{n} [p(a_1),p(a_2),\cdots,p(a_n)]
  $$
• 熵函数是严格上凸函数
  • 凸函数定义：
    $$
    f[\alpha X_1+(1-\alpha)X_2]\ge \alpha f(X_1)+(1-\alpha)f(X_2)
    $$
• 确定性：只要一个概率为1，熵为0
• 加权熵
  • 各信息量带权求熵
  • 同有非负性
  • 连续性
  • 对称性
  • 均匀性
    $$
    H_\omega(\omega_1,\cdots,\omega_n;\frac1n,\frac1n,\cdots,\frac1n)=\frac {\omega_1+\omega_2+\cdots+\omega_n}n \log_2n
    $$
  • 确定性
  • 扩展性
  • 线性叠加性
  • 加权熵最大值
    $$
    p(a_i)=e^{\frac \lambda {\omega_i}-1} \\
    H_{max}=\sum^n_{i=1}\omega_i p(a_i)-\lambda
    $$

    平均互信息量

$$
I(X;Y)=\sum^n_{i=1}\sum^m_{j=1} p(a_ib_j)I(a_i;b_j)
$$

• 意义1
  $$
  I(X;Y)=H(X)-H(X/Y)
  $$
  收到Y前、后关于X的不确定度的减少量
• 意义2
  $$
  I(Y;X)=H(Y)-H(Y/X)
  $$
  发送X前后关于Y的不确定度的减少量
• 意义3
  $$
  I(X;Y)=H(X)+H(Y)-H(XY)
  $$
  平均互信息量等于通信前后整个系统不确定度的减少量
• 互易性：即从任意一个方向获得的信息量是一样多的
• 非负性
• 极值性
  $$
  I(X;Y)\le H(X)
  $$
• 凸函数
  • 平均互信息是信源概率分布的上凸函数
  • 平均互信息是信道传递概率的下凸函数
• 平均互信息量与各熵关系

多符号（离散平稳）

• N次扩展无记忆信源的熵就是原离散信源的熵的N倍
  $$
  H(X^N)=NH(X)
  $$
• 一维平稳信源
  $$
  P(X_i=x_1)=P(X_j=x_1)=P(x_1) \\
  P(X_i=x_2)=P(X_j=x_2)=P(x_2) \\
  \cdots
  $$
• 二维离散平稳信源
  $$
  P(X_iX_{i+1})=P(X_jX_{j+1}),i=\not j
  $$
  性质
  $$
  X=X_1X_2 \Rightarrow
  H(X)=H(X_1)+H(X_2|X_1) \\
  \because H(X_2|X_1)\le H(X_2) \\
  \therefore H(X_1X_2)\le H(X_1)+H(X_2)
  $$
• 若各维联合概率均与时间无关，则为完全平稳信源，即离散平稳信源
  • 一般是有记忆信源
• N维推广
  $$
  H(X)=H(X_1)+H(X_2|X_1)+H(X_3|X_2X_1)+\cdots+H(X_N|X_1\cdots X_{N-1})
  $$
• 平均符号熵
  $$
  H_N=\frac 1N H(X_1X_2\cdots X_N)\\
  $$
  • 极限（信息）熵
    $$
    H_\infty=\lim_{N\to\infty}\frac 1N H(X_1X_2\cdots X_N)\\
    $$
  • 对于平稳信源，极限熵存在
    $$
    H_\infty=\lim_{N\to\infty} H(X_N|X_1X_2\cdots X_{N-1})
    $$

马尔可夫信源

• m阶马尔可夫信源极限熵
  $$
  H_\infty=H(X_{m+1}|X_1X_2\cdots X_m) \\
  =H_{m+1}=-\sum_{i=1}^{n^m}\sum_{j=1}^{n^m}p(s_i)p(s_j|s_i)\log_2p(s_j|s_i)
  $$
  注意：马尔可夫链状态极限
  $$
  p(s_j)=\sum_{i=1}^{n^m}p(s_i)p(s_j|s_i)
  $$
  • 极限概率
    $$
    p(s_j)=\sum_{i=1}^{n^m}p(e_i)p(e_j|e_i)
    $$
• 信源熵相对率
  $$
  \eta = \frac {H_\infty} {H_0}=\frac {I_{0\infty}}{H_0}
  $$
  • 信源剩余度
    $$
    R = 1-\eta
    $$
    • 意义：信源可压缩的程度
    • 但是为了提高抗干扰能力，希望增加冗余度
  • 信息变差
    $$
    I_{0\infty}=H_0-H_\infty
    $$

    连续信源

• 相对熵
  $$
  H_c(X)=-\int_R p(x)\log_2p(x)dx \\
  联合熵H_c(XY)=-\iint_{R^2} p(xy)\log_2p(xy)dxdy \\
  条件熵H_c(Y|X)= -\iint_{R^2}p(xy)\log_2p(y|x)dxdy
  $$
  • 不具有非负性
  • 可加性
    $$
    H_c(XY)=H_c(X)+H_c(Y|X)
    $$
    可推广到n维
  • 平均互信息
    $$
    I_c(X;Y) = \lim \log \frac{p(x|y)\Delta x}{p(x)\Delta x} = \log \frac{p(xy)}{p(x)p(y)}
    \\=H_c(X)-H_c(X|Y)\ge0 \\
    I_c(X;Y)=I_c(Y;X)
    $$
  • 注意：连续信源考虑的是相对熵，和离散信源的熵不同；实际上连续信源的不确定性应该为无穷大
• 最大连续熵定理：若无限制条件，连续情况是没有最大熵的
  • 在信号幅度受限的情况下：服从均匀分布的随机变量，具有最大输出熵
  • 平均功率受限的条件下：高斯分布具有最大输出熵
• 熵功率
  $$
  \overline P= \frac 1{2\pi e} e^{2H(X)}
  $$
• 互信息量（连续）
  $$
  I(x;y)=\log \frac {p(xy)}{p(x)p(y)}
  $$

高斯分布信源

$$
H_c(X)=\frac 12\ln(2\pi e\sigma^2)=\frac 12\ln (2\pi eP)
$$
注意：只与方差有关

指数分布

$$
H_c(X)=\log_2 (me)
$$

信道容量

• 平均互信息：原始信源熵与信道疑义度之差
  $$
  I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)
  $$
• 信道矩阵：随机过程的随机矩阵
• 信道容量：平均互信息的最大值
  $$
  C\stackrel {def} =\max_{p(x)}{I(X;Y)}
  $$
• 信息传输速率
  $$
  R_t= \frac 1t I(X;Y) \\
  C_t=\frac 1t \max_{p(x)}{I(X;Y)}
  $$
• 无损信道
  $$
  H(X|Y)=0 \\
  I(X;Y)=H(X)<H(Y) \\
  C=\max_{p(x)}{I(X;Y)}=\max_{p(x)}H(X)=\log n
  $$
• 无噪信道
  $$
  H(Y|X)=0 \\
  I(X;Y)=H(Y)<H(X) \\
  C=\max_{p(x)}{I(X;Y)}=\max_{p(x)}H(Y)=\log m
  $$
• 无损无噪信道
  $$
  H(X|Y)=0=H(Y|X) \\
  I(X;Y)=H(X)=H(Y) \\
  C=\max_{p(x)}{I(X;Y)}=\max_{p(x)}H(X)=\log n=\log m
  $$
• m个输出符号对称信道的信道容量(当输出为等概分布)
  $$
  C=\log m-H(q_1q_2\cdots q_m)
  $$
  引理：对于对称信道，只有当信道输入分布为等概分布时，输出分布才能为等概分布
• 均匀信道（强对称信道）
  $$
  C=\log n-p\log(n-1)-H(p)
  $$
• 二元对称信道
  $$
  I(X;Y)=H(w\overline p+\overline wp)-H(p) \\
  $$

离散信道容量计算方法

• 拉格朗日乘子法
  $$
  F=I(X;Y)-\lambda[\sum^n_{i=1}p(x_i)-1]\\ \Rightarrow
  \frac {\partial F}{\partial p(x_i)}=0 \\ \Rightarrow
  I(X;Y)=\log e+\lambda=C
  $$
• 条件互信息定理
  $$
  I(x_i;Y)=\sum^m_{j=1}p(y_j|x_i)\log\frac {p(y_j|x_i)} {p(y_j)} =\log e+\lambda=C
  $$
  对于一般离散信道
  $$
  I(x_i;Y)=C,p(x_i)=\not0 \\
  I(x_i;Y)\le C,p(x_i)=0 \\ \Rightarrow
  I(X;Y)达到极大值C
  $$
• 离散信道容量计算
  $$
  \sum^m_{j=1} p(y_j|x_i) \beta_j = \sum^m_{j=1} p(y_j|x_i)\log p(y_j|x_i) \Rightarrow \beta_j \\
  C=\log(\sum^m_{j=1} 2^{\beta_j}) \Rightarrow C \\
  p(y_j)=2^{\beta_j-C} \Rightarrow p(y_j) \\
  p(y_j)= \sum^n_{i=1} p(x_i)p(y_j|x_i) \Rightarrow p(x_i)
  $$

多符号离散信道

• 无记忆信道
  $$
  P(\mathbf Y|\mathbf X)=\prod^N_{i=1} P(Y_i|X_i) \\
  p(b_j|a_i)=\prod^N_{i=1} p(y_{jk}|x_{ik}) \\ \Rightarrow
  I(\mathbf X;\mathbf Y)\le \sum^N_{i=1} I(X_i;Y_i)
  $$
• 无记忆信源
  $$
  I(\mathbf X;\mathbf Y) \ge \sum^N_{i=1} I(X_i;Y_i)
  $$
• 无记忆信源信道
  $$
  I(\mathbf X;\mathbf Y) = \sum^N_{i=1} I(X_i;Y_i)
  $$

连续信道

• 无记忆连续信道
  $$
  p(\mathbf y|\mathbf x)=p(y_1|x_1)p(y_2|x_2)\cdots p(y_n|x_n)
  \\ \Rightarrow
  I(\mathbf X;\mathbf Y)\le \sum^N_{i=1} I(X_i;Y_i) \le nC
  $$

• 加性噪声信道
  $$
  p(y|x)=p_N(y-x)=p_N(z) \\ \Rightarrow
  H(Y|X)=H(N) \\ \therefore
  I(X;Y)=H(Y)-H(Y|X)=H(Y)-H(N)
  $$

  • 若信源和噪声源都是服从高斯分布的
    $$
    I(X;Y)=H(Y)-H(N) \\ =\frac 12\log[2\pi e(\sigma^2_X+\sigma^2_N)] -\frac12 \log[2\pi e\sigma^2_N] \\ =\frac12 \log(1+\frac {\sigma^2_X}{\sigma^2_N})
    $$
  • 非高斯型加性噪声信道
    $$
    \because P_X < \sigma^2_X,P_N=\sigma^2_N \\ \therefore
    \frac12\log(1+\frac {\sigma^2_X}{\sigma^2}) \le C\le \frac12\log(\frac {\sigma^2_X+\sigma^2_N}{\sigma^2})
    $$

    同样的噪声功率下，高斯干扰是最坏的干扰

• 连续信道容量
  $$
  C=\max_{p(x_i)} \sum^N_{i=1} I(X_i;Y_i)
  $$

  • 若信道为高斯信道(均值0，且变量相互独立)
    $$
    C=\frac n2 \log(1+\frac {\sigma^2_X}{\sigma^2_N})
    $$

窄带高斯信道

零均值，信道带宽为B，时间范围为[0,T]

注意：乃归斯特采样定理

• 信道容量
  $$
  n=2BT \\
  C=BT\log(1+\frac {\sigma^2_X}{\sigma^2_N})
  $$
• 单位时间信道容量
  $$
  C_t=B\log(1+\frac {\sigma^2_X}{\sigma^2_N})= B\log(1+\frac {P_X}{P_N})
  $$
• 香农公式
  $$
  N_0/2为功率谱密度\\
  C_t= B\log(1+\frac {\sigma^2_X}{N_0 B})
  $$
  注意：
  • 适用于加性高斯白噪声信道
  • 可用于确定非高斯信道的容量下限
  • 意义：给出了理想通信系统的极限传输率
• 无限带宽香农式
  $$
  C_t=1.44\frac {\sigma_X^2}{N_0}
  $$

有失真传输

单符号失真

• 失真函数：用来定量描述失真度
  $$
  d(x_i,y_j)
  $$
  将这些失真函数放到矩阵里，就变成了失真矩阵
  • 汉明失真
    $$
    d(x_i,y_j)=\begin{cases}
    0 &i=j \\
    1 & i=\not j
    \end{cases}
    $$
  • 平方误差失真
    $$
    d(x_i,y_j)=(y_j-x_i)^2
    $$
• 平均失真
  $$
  \overline D=E[d(x_i,y_j)]=\sum^n_{i=1}\sum^m_{j=1} p(x_iy_j)d(x_i,y_j)
  $$

N次扩展的失真函数

$$
d_N(X,Y)=\sum^n_{i=1} d(X_i,Y_i) \\
\overline {D_N}=\sum^N_{i=1} E[d(X_i,X_j)] =\sum^n_{i=1} \overline {D_i} = N \overline {D_i}
$$

保真度允许信道

失真度D许可信道

$$
P_D={p(y|x):\overline D\le D}
$$

信息率失真函数

$$
R(D)=\min_{p(y|x)\in P_D} I(X;Y)
$$

给定的信源，在允许的保真度下，信息率允许压缩的最小值

• 离散无记忆信道
  $$
  R(D)=\min_{p(y_j|x_i)\in P_D} \sum^n_{i=1} \sum^m_{j=1} p(x_i)p(y_j|x_i)\log \frac {p(y_j|x_i)}{p(y_j)}
  $$

• 性质

  • R(D)是关于D的下凸函数,且严格递减

  • 定义域

    最小值
    $$
    D_{min}=0 \Rightarrow R(0)=H(X) \\
    D_{min}= \sum^n_{i=1} p(x_i) \min_j d (x_i,y_j)
    $$
    最大值
    $$
    D_{max}=\min { D:R(D)=0} \\ \Rightarrow
    D_{max}=\min_{p(y|x)\in P_D} E[d(x,y)],P_D是使I(X,Y)=0的集合 \\
    \because I(X;Y)=0 \Rightarrow p(y_j|x_i)=p(y_j) \\
    \therefore D_{max}=\min_{p(y_j)} \sum_j p(y_j) \sum_i p(x_i)d(x_i,y_j) =\min_{p(y_j)} \sum_j p(y_j)D_j
    \\ \Rightarrow D_{\max} = \min D_j, D_j = \sum_i p(x_i)d(x_i,y_j)
    $$
    若在最大值外
    $$
    D>D_{max}\Rightarrow R(D)=0
    $$

  • 值域
    $$
    0@D=0 到 H(X)@D=D_{max}
    $$

• n元等概率信源信息率失真函数（汉明失真矩阵）

  $$
  R(D) = \ln n + \frac D \alpha \ln \frac { \frac D \alpha}{n-1} + (1-\frac D \alpha)\ln (1-\frac D \alpha)
  \\ \alpha 为汉明失真矩阵系数
  $$

参量表示法

1. 首先建立输出m个数联立的如下形式方程
   $$
   1=\sum^n_{i=1} \lambda_iP(x_i)e^{Sd(x_i,y_j)}
   $$
2. 将求出的m个参数代入下式，计算输出分布概率
   $$
   1=\lambda_i\sum^m_{j=1} P(y_j)e^{Sd(x_i,y_j)}
   $$
3. 由下式得传输概率
   $$
   P(y_j|x_i)=\lambda_iP(y_j)e^{Sd(x_i,y_j)}
   $$
4. 则可得到以S为参量的平均失真函数和失真函数
   $$
   D(s)=\sum^n_{i=1} \sum^m_{j=1} P(x_i)\lambda_iP(y_j) e^{Sd(x_i,y_i)}d(x_i,y_i) \\
   R(s) = \sum^n_{i=1} \sum^m_{j=1} P(x_i)\lambda_iP(y_j) e^{Sd(x_i,y_i)} \ln \frac {\lambda_iP(y_j) e^{Sd(x_i,y_i)}}{P(Y_j)} = sD(s)\sum^n_{i=1} P(x_i) \ln \lambda_i
   $$

连续情况失真函数

$$
D=E{ d(X,Y) }= \int^\infty_{-\infty}\int^\infty_{-\infty} p(xy)d(x,y)dxdy \\
R(D)=\inf_{p(y|x)\in B_D} I(X,Y)
$$

• 高斯信源
  $$
  \because 均值m_X，方差\sigma_X^2，d(x,y)=(x-y)^2 \\
  \therefore \begin{cases}
  D=\iint p(xy)(x-y)^2dxdy \\
  \int^\infty_{-\infty} p(y|x)dy =1
  \end{cases} \Rightarrow R(D) \\
  \Rightarrow R(D)=\begin{cases}
  \frac12\log \frac {\sigma^2_X}D & D\le \sigma_X^2 \\
  0 & D> \sigma_X^2
  \end{cases}
  $$

无失真离散信源编码

• 编码信息率：编码后平均每个符号带的最大信息量
  $$
  R’=\frac {K\times \log m}L = \overline K \times \log m
  $$
• 信息传输率：平均每个码元带的信息量
  $$
  R = \frac {H(X)} {\overline K}
  $$

定长编码定理

$$
\because X_1\cdots X_L有H(X) \\
用K个符号Y_1\cdots Y_K编码，Y_k有m种可能取值
\\ \forall \epsilon>0,\delta>0 \\ \therefore
\frac KL\log_2m \ge H(X)+\epsilon，当L足够大时译码差错小于\delta \\
\frac KL\log_2m \le H(X)-2\epsilon，L足够大时译码失真一定大于\delta
$$

• 无失真译码
  $$
  译码差错率小于\delta \\
  \Rightarrow
  L\ge \frac{\sigma^2(x)}{\epsilon^2\delta} \\
  \sigma^2(x) = D[I(a_i)]= \sum^n_{i=1} p(x_i)[\log p(x_i)]^2-[H(X)]^2
  $$
• 编码效率
  $$
  \eta = \frac {H(X)}{R’} = \frac {H(X)} {H(X)+\epsilon}
  $$

变长编码

• 变长无失真编码

  $$
  对L次扩展信源H(X)使用m元码元进行变长编码 \\
  \exist 码平均长度\overline K的无失真编码方法 \\
  \Rightarrow 1 +\frac {LH(x)}{\log_2m} > \overline K\ge \frac {LH(X)}{\log_2m} \\
  $$
  也就是变长编码之后的信息量只要大于原本信息量，就存在唯一可译编码。若推广到一般或马尔可夫信源
  $$
  \lim_{L\to\infty}\frac {\overline {K_L}}L = \frac {H_\infty}{\log m}
  $$

• 香农第一定理

  $$
  H(X)\le R < H(X)+ \epsilon
  $$
  存在唯一可译变长编码

• 信息率
  $$
  \Rightarrow
  \eta=\frac{H(X)}{\overline K} > \frac{H(X)}{H(X)+\frac {\log_2m}L}
  $$

• 平均码长
  $$
  \overline K = \sum^n_{i=1}p(x_i)k_i
  $$

码字唯一可译条件

• 克拉夫特不等式：即时码存在充要条件
  $$
  \sum^n_{i=1}m^{-k_i} \le 1
  $$

香农第三定理

$$
\forall D \ge 0,\epsilon > 0 \\
R’ > R(D) \\
L够长
\Rightarrow \exist \overline D(C) \le D + \epsilon
$$

香农编码

1. 将信源排序
   $$
   p(a_1)\ge p(a_2)\ge \cdots \ge p(a_n)
   $$
2. 累加概率
   $$
   \because p(a_0)=0 \\ \therefore
   p_a(a_j)=\sum^{j-1}_{i=0}p(a_i),j=i+1
   $$
3. 确定码长
   $$
   -\log_2p(a_i) \le k_i < 1-\log_2p(a_i)
   $$
4. 取累加概率小数点后相应码长编码

Fano编码

1. 将信源排序
2. 按编码进制数（m）将概率分组，使每组概率总和尽可能接近or相等
3. 给每组分配一位码元
4. 对分配后的每分组，按同样原理编码（回到步骤2）

Huffman编码

编码过程略

• 码长方差
  $$
  \sigma^2=E[(k_i-\overline K)^2]
  $$
  选取方差小的

• m进制全树，码字数为
  m+k(m-1)

信道编码

• 正确译码概率

  $$
  p(F(y_j)|y_j) = p(x_i|y_j)
  $$

• 错误译码概率

  $$
  p(e|y_j) = 1-p(F(y_j)|y_j) = 1 - p(x_i|y_j)
  $$

• 译码平均错误概率

  $$
  P_e = E[p(e|y_j)] = \sum^m_{i=1} p(y_j) p(e|y_j) \\
  = 1-\sum_Yp[F(y_j),y_j] = \sum_{Y,X-x^*} p(xy)
  $$

  平均正确概率

  $$
  \overline P_e = \sum_Y p[F(y_j),y_j]=\sum _Y p(x^*y_j)
  $$

• 菲诺不等式
  $$
  H(X|Y) \le H(p_E)+p_E\log(n-1)
  $$

• 信息传输率：平均每个码符号携带的信息量

  $$
  R= \frac {H(X)}{\overline L}
  $$

最大后验概率译码准则

选取所有后验概率中最大的一个作为译码输出
$$
F(y_j)=x^* \\
\Rightarrow \forall i, p(x^*|y_j) \ge p(x_i|y_j)
$$
则译码平均错误概率最小

极大似然译码规则

$$
\Rightarrow \frac {p(y_j|x^*)p(x^*)}{p(y_j)} \ge \frac {p(y_j|x_i)p(x_i)}{p(y_j)}
$$

当输入为等概分布时，则有：

$$
p(y_j|x^*) \ge p(y_j|x_i)
$$

汉明距离

对于二元n长码
$$
X=(x_1,x_2,\cdots,x_n),Y=(y_1,y_2,\cdots,y_n)
\\ \Rightarrow
D(X,Y)=\sum^n_{k=1}x_k \bigoplus y_k
$$

• 最小码距
  $$
  D_{\min} = \min [D(C_i,C_j)],i=\not j
  $$
  最小码矩越大，平均错误概率越低
• 最小距离译码准则
  $$
  F(y_j) = x^* \\
  D(x^*,y_j) = D_{\min}(x_i,y_j)
  $$

检纠错能力

• 纠正u个错误
  $$
  d_{min} = 2u+1
  $$
• 检查l个错误
  $$
  d_{min} = l+1
  $$
• 同时纠正u个错误和检测出l个错误
  $$
  d_{min} = u+l+1, l>t
  $$

线性码编码方式

$$
\alpha_{i1} = \alpha_{i1} \\
\alpha_{i2} = \alpha_{i2} \\
\alpha_{i3} = \alpha_{i1} \bigoplus \alpha_{i2} \\
\alpha_{i4} = \alpha_{i1} \\
\alpha_{i5} = \alpha_{i1} \bigoplus \alpha_{i2}
$$