第6章 信道编码噪声信道中的编码前言平均互信息（信息传输率）为$I(X;Y)=H(X)-H(X|Y)$信道容量为$C=\max I(X;Y)$通过调整信源的概率分布，使得信息传输率尽量接近信道容量，也就是让信息传输率尽可能大，这一过程称为信源和信道匹配信源编码的目的：增加信源熵$H(X)$，理解为信源发出的所有符号中每个符号带有的平均信息量，实现符号匹配，压缩冗余信道编码的目的：减少损失熵$H(X|Y)$，提高传输信号的抗干扰能力避免少量差错信号对信息内容的影响：使用纠错编码（纠错、检错）信道编码的研究对象：信息序列（即码元间彼此无关且等概率出现）基本思路：在传输的信息码中按照一定规律产生一些附加码元，经过信道传输，在传输中若码字出现错误，接收端则利用编码规律发现码的内在相关性被破坏，从而按照一定的译码规则自动纠正或发现错误，降低误码率基本方法前向纠错(FEC)纠错过程在接收端独立进行，没有反馈，信息一直朝着前面的方向传播，因此叫前向译码设备复杂，适用于实时性高容错能力强的场合反馈重发(ARQ)在接收端判断收到的序列是否符合编码规则，如果不符合就通知重发如循环冗余校验码(CRC)混合纠错(HEC)结合前向纠错和反馈重发的纠错方法，兼有检错和纠错的能力检错后在能力范围内直接纠错，如果超过该范围就通知重发差错描述与控制纠错码的传送形式是有形的，承载信息比特的基本单位为码元或符号，大的符号畸变会引起符号差错，使得其携带的信息比特也发生差错信号差错和信息差错分别用差错符号和差错比特来描述，有区别也有联系差错符号：符号出错的概率（误码概率），即信号差错概率差错比特：误比特率，信息差错概率对于二进制系统来说，因为一个符号承载的信息量就是$\log_22=1$，因此符号差错数值上等于比特差错，但对于多进制系统而言，一个符号差错对应的比特差错根据不同的编码方式而有所区别反射二进制码（格雷码/循环二进制码）编码特点：任意两个相邻代码中只有一位是不同的，且最大编码和最小编码间也仅有一位不同举例（三位格雷码）：$000、001、011、010、110、111、101、100$转换方法：递归法、异或转换、卡诺图等优点：差错比特小，对于一般高斯信道来说，最可能的符号差错是畸变一个量级，此时格雷码明显优于自然二进制码差错图样(Error Pattern)定义：差错图样=发码-收码$$ E=C-R $$举例：8进制码，发$C=(0,2,5,4,7,5,2)$，收$R=(0,1,5,4,7,5,4)$，则$E=C-R=(0,1,0,0,0,0,6)$特别地，对于二进制码来说，若发$C=(0,1,1,0,1,0,1)$，收$R=(0,1,0,0,1,0,1)$，则$E=C-R=(0,0,1,0,0,0,0)$，可以等效为模2相加，此时差错图样中的1既表示符号差错，又表示比特差错差错的个数称为汉明距离(Hamming Distance)从通信角度来看，收码是可测得的一直量，如果要从收码获知发码，那就要设法找到差错图样，就能通过反变换得到发码禁用码组和许用码组将信源发出的信息序列按照一定的编码规则，在n重矢量中编出的一组可用码字称为许用码组，剩下的矢量称为禁用码组在信道编码过程中应当在许用码组中尽量寻找差异化最大的码组，以降低误码率信道编码的分类类别检错码：能否发现错误的码纠错码：能够发现并纠正错误的码纠删码：能够纠正删除错误的码纠错码线性与非线性码区别在于原始信息元是否为线性组合，乘法、非运算等为非线性运算，出现这些运算的组合式即为非线性组合非分组码举例（出现了乘法运算）：输出码字为$(C_3,C_2,C_1,C_0)$时，按规则$C1=C_2+C_2C_3;C_0=1+C_2C_3$编出得码为非分组码分组码举例（都是线性运算）：输出码字为$(C_3,C_2,C_1,C_0)$时，按规则$C_0=m_1;C_1=m_2;C_2=m_1\oplus m_2;C_3=m_1$编出的码为分组码卷积码与分组码区别码字的关联性仅存在于码字内部还是码字和码字之间，只有码字内部有关联而码字间无关联的称卷积码，码字间存在关联性的为分组码码字是否有记忆，在编码时是否要使用寄存器移位循环码定义：将码字内部的码元依次循环摆放组成的编码，如将码字的第一位移到最后一位变成一个新的码字举例：$\{011101,111010,110101,101011,010111,101110\}$系统码定义：码字的前$k$位与信息序列相同，后面$n-k$位校验元则根据前面的信息元得到信道译码和译码规则信道传输模式分析发端具有$2^k$个许用码组，接收端的矢量空间中共有$2^n$个码组，其中包含$2^k$个许用码组和$2^n-2^k$个禁用码组以发端发出第$C_i$个码字为例正确传输：收端也正确接收到$C_i$不可检出错误传输：收端收到的是$n$维矢量空间中许用码组部分的非$C_i$的其他码字可检出错误传输：收端收到的禁用码组中的码字核心问题：收端要怎样对收到的码进行合适的“翻译”，或者说分类，如接收到码A应该分到哪个类，有什么样的规则译码规则将输入的接受矢量转换成一个输出码字的规则，核心是根据译码准则来构建译码规则表译码准则：制定译码规则的原则常见的译码准测最小错误准则(MEPD)最大后验概率准则(MPPD)最大联合概率准则(MJPD)最大似然译码准则(MLD)有噪信道编码定理（香农第二定理）定义设某离散无记忆信道有$r$个输入，$s$个输出，信道容量为$C$，在输入$r^n$个符号中选出$M$个码字组成一组码，设$\epsilon$是任意小的正数若$M\leqslant 2^{(n(C-\epsilon))}$，则存在这样的码和相应的译码规则，在当$n$足够大时，使信道输出的错误概率$P_e$任意小若$M=2^{(n(C+\epsilon))}$，则无论$n$多大，也找不到这样一种编码使得译码错误概率任意小其他表述也可以写作$$ M\leqslant2^{n(C-\epsilon)}\to R=\frac {\log M} n \leqslant C-\epsilon $$解释：若信息传输率$R$不大于信道容量$C$，则存在一种编码，当码长$n$足够大时，它可以使信道输出端的错误概率任意小的同时信息传输率无限接近于$C$，但如果$R$大于$C$，则不可能找到这样一种编码使得错误概率任意小讨论香农第二定理纠正了“可靠性和有效性是一对不可调和的矛盾”的传统观点，为信道编码理论和技术的研究指明了方向但是该定理只给出了编码的存在性，并没有给出编码的具体方法定理指出，$R<C$是可靠传输的必要条件，进一步证明了$R=C$时，任意小的差错概率也是有可能达到的线性分组码的基本概念定义分组码：编码中的约束性仅局限于码字内部，而不同码字之间没有关系线性：编码生成的码元满足线性叠加原理从信息序列到码字，是一个线性映射的过程如果一个$(n,k)$分组码的编码规则可以用线性方程组表示，则称该码为线性分组码判断标准满足该式关系的编码称为线性分组码$$ f(\alpha M+\beta M')=\alpha f(M)+\beta f(M') $$该式表明，任意两个信息组的线性组合映射得到的码字都应是两个信息组对应码字的线性组合共性都有全零码：所有码字中一定含有全零的码满足封闭性：任意两个码相加还是其中一个可能地码字讨论码的重量：一个码字中非零码元的个数称为该码字的（汉明）重量，如$01011$的重量为$3$码集中非零码字的汉明重量的最小值称为该码字的最小汉明重量码的距离：两个长度相同的码字中，对应位置码元不同的码元数目称为两码字之间的汉明距离，简称码距，如$01011$和$01000$之间的汉明距离为$2$码集中码字间汉明距离的最小值称为该码的最小汉明距离一个$(n,k)$分组码中非零码字的最小重量等于码的最小距离生成矩阵设码字可以写作$$ \overrightarrow C=m_{k-1}\overrightarrow g_{k-1}+m_{k-2}\overrightarrow g_{k-2}+\cdots+m_{1}\overrightarrow g_{1}+m_{0}\overrightarrow g_{0} $$用矩阵乘法的形式可以表示为$$ (C_{n-1},\cdots,C_0)=(m_{k-1},m_{k-2},\cdots,m_1,m_0) \begin {bmatrix} \overrightarrow g_{k-1}\\ \overrightarrow g_{k-2}\\ \cdots \\ \overrightarrow g_{1}\\ \overrightarrow g_{0}\\ \end {bmatrix} $$生成矩阵是一个$k$行$n$列的矩阵，表示生成的码字长度为$n$，信源序列长度为$k$，生成矩阵并不是唯一的，可写作如下形式$$ G=\begin {bmatrix} \overrightarrow g_{k-1}\\ \overrightarrow g_{k-2}\\ \cdots \\ \overrightarrow g_{1}\\ \overrightarrow g_{0}\\ \end {bmatrix}= \begin {bmatrix} g_{k-1,0}&\cdots&g_{k-1,n-1}\\ \vdots &\ddots & \vdots\\ g_{0,0}&\cdots&g_{0,n-1} \end {bmatrix} $$举例若一个编码的生成规则为$$ \left \{ \begin {align} &C_4=m_1\\ &C_3=m_0\\ &C_2=m_1\\ &C_1=m_0\\ &C_0=m_1\oplus m_0 \end {align} \right. $$将其对应的生成矩阵为生成方程的系数矩阵再转置即可得到生成矩阵$$ G=\begin {bmatrix} 1 & 0\\ 0 & 1\\ 1 & 0\\ 0 & 1\\ 1 & 1 \end {bmatrix}^T =\begin {bmatrix} 1 & 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 1 \end {bmatrix} $$讨论生成矩阵的行表示基本码字（一组基底）生成矩阵的列表示了某位码元的编码方式一致校验矩阵根据校验规则可列出一致校验方程组（判断是否出错的规则），该方程组的系数矩阵即一致校验矩阵举例若某编码的一致校验方程为$$ \left \{ \begin {align} &C_2+C_4=0\\ &C_1+C_3=0\\ &C_0+C_4+C_3=0 \end {align} \right. $$一致校验矩阵即$$ \begin {bmatrix} 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 &1 \end {bmatrix} $$
第5章 信源编码前言编码方式信源编码信道编码信源编码原因由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度目的通过信源编码减少冗余，提高编码效率，提高通信的有效性方法解除相关性概率均匀化定理无失真编码定理（针对离散信源）限失真编码定理（针对连续信源）编码的概念定义分组码将信源消息分成若干组，用符号序列$\mathbf {x_i}=(x_{i_1},x_{i_2},\cdots,x_{i_l},\cdots,x_{i_L})$表示，序列中每个符号都取自于符号集$A$，$x_{i_L}\in A=\{a_1,a_2,\cdots,a_i,\cdots,a_n\}$，每个$x_i$依照固定的码表映射成一个码字$y_i$按照码表映射编码的码称为分组码，有时也叫做块码，只有分组码才有对应的码表，非分组码不存在码表码字每个码符号序列称为码字，如编码后的${0001,0010,1100}$$D$元码由$D$个符号组成的码字集合，如${0,1}$对应二源码，${0,1,2}$对应三元码理解根据编码方式的不同，同一个信源符号可以有不同的码符号序列将信源符号变换成由码元符号组成的码符号序列的过程就是信源编码的过程分类按码字长度分定长码：码中所有码字的长度都相同变长码：码中的码字长短不一按符号码字对应关系分非奇异码：信源符号和码字一一对应，没有重复，不存在多对一的情况奇异码：多个信源符号对应同一个码字按可译程度分唯一可译码：对于任意长的码元序列，只能被唯一地分割成一个个的码字非唯一可译码：对于任意长的码元序列，无法被唯一地进行分割，会存在歧义，如$1000010$是由$(10,0,01,00)$产生的码流，在译码时会产生多种不同的结果，出现歧义按照可译时效分非即时码：唯一可译码中如果接收端接收到一个完整的码字后不能及时译码，必须等下一个码字开始接收时才能判断是否可以译码，这种情况下某一码字可以是其他码字的前缀即时码（非延长码）：唯一可译码中如果接收端接收到一个完整的码字后可以立刻译码，无需等待后面的码字接收，这种情况下要求任意码字都不能是其他码字的前缀部分，也叫做异前缀码码树形状倒立的树，树根在上，树枝在下概念树枝：码树中的线段，表示编码路径，用码字符号标注节点：结点，树枝的端点树根：最顶端的节点，编码的起始段，码字起点$r$级节点：从树根开始经过第$r$个分支节点所到达的节点$m$进码树：一个节点最多能伸出$m$个树枝的码树，表示$m$进制终端节点：码树的最底层节点，不再伸出树枝，表示编码结束节数：码长满树：每个分支都延伸到最后一级节点的码树，共有$m$的$r$次方个等长码码树与编码的关系$m$进码树表示对应的编码为$m$进制编码码字为树根到每个终端节点树枝的标号序列，是即时码$r$级终端符号对应的一个码字最多有$r$个码字符号组成$n$个终端节点则对应n个不同的码字讨论唯一可译码存在的充要条件：各码字的长度$K_i$符合克劳夫特不等式，式中$m$为进制数，$n$为信源符号数$$ \sum_{i=1}^nm^{-K_i}\leqslant1 $$以上判断方式并没有涉及具体的编码结果，所以只能判断某种编码方式是否存在唯一可译码，并不能给出具体的结果，也不是所有满足上述编码方式的编码结果都是唯一可译码无失真信源编码定理编码的数学模型拟进行编码的信源符号序列长度为$L\geqslant 1$，以传输$11$个符号$information$为例，则可将信源序列描述为$$ \mathbf X=(i,n,f,o,r,m,a,t,i,o,n),X_l\in\{a,b,\cdots,z\},L=11 $$码表为26个字母$a,b,c,\cdots,z$依次编码成$00000, 00001,\cdots,11001$，变换成由$K_L$个符号组成的码序列，编码后的输出序列可写作$$ \mathbf Y=(01000,01101,00101,01110,10001,01100,00000,10011,01000,01110,01101),Y_k\in\{0,1\} $$编码变换的基本要求是能够无差错地从$Y$恢复到$X$，能够正确地进行反变换（译码），同时希望传送$Y$的信息率最小，因此延伸出几个概念编码输出序列含有的最大信息量为（$K_L$长的输出符号序列，含有$K_L$个码元，二进制情况下每个码元所携带的信息量为$\log2$）$$ K_L\log_2m=55\log_22 $$而该输出码字表示了本身长为$L=11$的信源发出序列（即原始信源序列里有$11$个符号），则每发送一个信源符号所需要的信息率平均值为（$m$为进制数，不同进制下要对应将$m$的值做出改变）$$ \begin {align} \overline{K}&=\frac {K_L} L \log m=\frac 1 L\log m^{K_L}=\frac 1 L \log M\\ &=\frac {55} {11}\log_22=5\log_22=5=\frac 1 {11}\log_22^{55} \end {align} $$$M=m^{K_L}=2^{55}$表示输出序列能够编码的码字个数（所有可能的情况数量）为了让信息率最小，也就意味着要找到一种编码方式，使得符号平均信息率K拔值最小，由此引出无失真信源编码定理（包括定长、边长编码）定长编码定理讨论研究对象：离散无记忆信源成立条件$K=K_L$，各码字的序列长度相等编码是唯一可译码对于$m$元码，最多有$m^{K_L}$个码字目的寻找最小的$K$值实现无失真传输，满足条件：信源符号和码字是一一对应的且由码字组成的码符号序列的逆变换也是唯一的定义设由$L$个符号组成的，每个符号熵为$H_L(\mathbf X)$的无记忆平稳信源符号序列$X_1,X_2,...,X_L$可以用$K_L$个符号$Y_1,Y_2,\cdots,Y_k,\cdots,Y_{K_L}$进行定长编码（其中每个符号有$m$种可能的取值）正定理：对于任意$\epsilon>0,\delta>0$,只要$\frac {K_L} L\log m\geqslant H_L(\mathbf X)+\epsilon$那么当$L$足够大时，必可使译码差错小于$\delta$逆定理：反之，当$\frac {K_L} L\log m\leqslant H_L(\mathbf X)-2\epsilon$时，译码差错一定是有限值，且当$L$足够大时，译码几乎必定出错类似极限的定义，有着相同的思路$\overline K=\frac {K_L} L \log m$是编码后发送一个信源符号所需要的平均信息量分析正定理说明当编码和信源满足关系$\overline K=\frac {K_L} L \log m>H_L(\mathbf X)$或$K_L\log m>LH_L(\mathbf X)=H(\mathbf X)$，即编码发送一个消息符号所需平均信息量大于信源平均每符号的信息量时，近乎无失真编码存在当$L$足够大时，译码误差可以控制在小于$\delta$内，而这个$\delta$值是任取的换一种形式来说，假设$L$足够大，当$K_L$长的码字所能够携带的最大信息量大于信源序列输出的信息量时，则可以使得传输几乎无失真逆定理说明当编码和信源满足关系$\overline K=\frac {K_L} L \log m <H_L(\mathbf X)$或$K_L\log m<LH_L(\mathbf X)=H(\mathbf X)$，即编码发送一个消息符号所需平均信息量小于信源平均每符号的信息量时，必定存在编码失真当$L$足够大时，译码几乎必定出错此时不可能做成一种编码器可以使得接收端译码时的差错概率趋于$0$，译码误差必然存在，且为一个有限值$\delta>0$临界情况下即满足关系$\overline K=\frac {K_L} L \log m =H_L(\mathbf X)或K_L\log m=LH_L(\mathbf X)=H(\mathbf X)$时此时可能有失真，也可能无失真，要进一步讨论通过例题发现，当处于临界状态时，若信源等概率分布，则可以实现无失真编码，反之不可能实现无失真，必然存在编码误差差错概率测度与控制假设信源序列长度为$L$，由文献可知$P_e\leqslant\frac {\sigma^2(\mathbf X)} {L\epsilon^2}$其中$\sigma^2(\mathbf X)=E\{[I(\mathbf x_i)-H(\mathbf X)]^2\}$为信源序列的自信息方差当$\sigma^2(\mathbf X)$和$\epsilon$为定值时，只要$L$足够大，差错概率便可小于任意一个数$\delta$，即当$L$序列长度满足$L\geqslant\frac {\sigma^2(\mathbf X)}{\epsilon^2\delta}$时，编码可以满足用户定义的差错概率$\delta$，该值一般很小，如$10^{-9}$等连续信源限失真编码原理由前面所学知识可知，连续信源的信息量趋于无穷，不能用离散符号序列进行无失真编码，只能进行限失真编码$$ H(\mathbf X)=-\int_a^bp_X(x_i)\log p_X(x_i)\mathrm d x=\lim_{\Delta x\to0}\log \Delta x $$定义采用平均码长$K_L$编码所得到的编码效率为$$ \eta=\frac {H_L(\mathbf X)} {\overline K} $$最佳编码效率可定义为（当$L$趋近于无穷大时，可实现编码效率趋近于1，但在实际中无法实现，最佳编码可看作平均码长最接近于熵的无损编码）$$ \eta = \frac {H_L(\mathbf X)} {H_L(\mathbf X)+\epsilon},\epsilon >0,\lim_{\epsilon \to 0}\eta =1 $$变长编码定理讨论变长编码的特点：用不同长度的码序列实现信源符号的编码编码方法：根据信源符号的不同统计特性采用不同长度的码字编码，如用短码表示大概率符号，长码表示小概率符号，提高编码效率单个符号的变长编码定理若离散无记忆信源的符号熵为$H(X)$，每个信源符号用$m$进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足不等式$$ \frac {H(\mathbf X)}{\log m}\leqslant\overline K<\frac {H(\mathbf X)}{\log m}+1 $$注意：上式是一个左闭右开的不等式，且这里的$\overline K$和前面的定长编码中的定义不同，这里指的是码字的平均长度$$ \overline K=\sum_{i}p_iK_{L_i} $$当$m=2$时，即码元符号是二进制时，此时码字平均长度和码字平均符号信息量相等，意味着码字平均符号信息量和信息熵相差$1bit$以内$$ H(\mathbf X)\leqslant \overline {K_1}<H(\mathbf X)+1 $$离散平稳无记忆序列变长编码定理对于平均符号熵为$H_L(X)$的离散平稳无记忆信源，必然存在一种无失真编码方法，使得平均信息率（码字平均符号信息量）满足不等式（其中$\epsilon$为任意小正数）$$ H_L(\mathbf X)\leqslant\overline K<H_L(\mathbf X)+\epsilon $$变长编码的编码效率变长编码一般可以达到较高的编码效率，其下界可以根据上述定理得知$$ \eta = \frac {H_L(\mathbf X)}{\overline K}>\frac {H_L(\mathbf X)}{H_L(\mathbf X)+\frac {\log m}{L}} $$剩余度认为编码效率趋近于1的编码为最佳编码，为了衡量各种编码方法和最佳编码之间的差距，定义编码的剩余度为$\gamma$，实际中剩余度可以无限接近于$\gamma$，但却无法达到$$ \gamma=1-\eta=1-\frac {H_L(\mathbf X)}{\overline K}=1-\frac {H_L(\mathbf X)}{\frac {\overline {K_l}}{L}\log m} $$最佳编码特征能载荷一定的信息量码字的平均长度最短可分离的变长码的码字组合方法概率大的信息符号编以短码字，概率小的编长码字，使得平均码长最短常见方法Shannon Coding 香农编码Fano Coding 费诺编码Huffman Coding 哈夫曼编码香农编码香农第一定理：如果编码后的信源序列信息传输率不小于信源的熵，则可实现无失真编码，反之不存在无失真编码编码过程1.将信源消息符号按照其出现概率大小依次排列得到$$ p(x_1)\geqslant p(x_2)\geqslant \cdots \geqslant p(x_n) $$2.按照以下关系确定整数码长$K_i$$$ -\log p(x_i)\leqslant K_i\leqslant-\log p(x_i)+1 $$3.为了变成唯一可译码，计算消息的累加概率$$ P_i=\sum_{k=1}^{i-1}p(a_k) $$4.将累加概率$P_i$变成二进制数（小数点后不断乘2，出现进位则记为1，反之记为0）5.将$P_i$二进制数小数点后$K_i$位作为该消息符号的二进制码字讨论香农编码方法的多余度较大，编码效率低，实用性不强但其给出了香农第一定理，给出了最佳编码方法（概率小码长，概率大码短），也提出了累加概率的概念费诺编码特点属于概率匹配编码有代表性，但不是最佳编码编码过程1.将信源消息符号按照出现的概率大小依次排列得到$$ p(x_1)\geqslant p(x_2) \geqslant \cdots \geqslant p(x_n) $$2.将依次排列好的信源符号按照概率值分为$m$组（几进制就分几组），使得各组的概率之和趋近于相同，并对各组依次赋$m$进码元3.将每一大足的信源符号进一步分成$m$个组，使得划分后的$m$组的概率之和趋近相同，再依次给各组赋$m$进码元4.重复以上步骤，直到每组只剩下一个信源符号位置5.将信源符号的码字从左到右读出，即费诺码常用信源编码方法讨论变长编码优点：无损编码，相对于定长编码有着较高的编码效率缺点：具有分组码具有的缺点常见编码方法信源统计特性已知/未知编码无失真/限失真编码无记忆/有记忆编码分组/非分组码等长/变长码最常见的是已知统计特性，离散、平稳且无失真的信源编码哈夫曼编码编码过程1.将$n$个信源符号按其概率大小依次排列得到$$ p(x_1)\geqslant p(x_2) \geqslant \cdots \geqslant p(x_n) $$2.取两个概率最小的字母分布依次配以$m$个码元，并将这$m$个概率相加作为一个新字母的概率，与未分配的字母重新排队3.对重排后的$m$个概率最小符号重复第二步4.不断重复以上过程，直到最后$m$个符号分配完成5.从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即对应码字讨论哈夫曼编码并不是唯一的，其和$m$个符号的放置顺序、相同合并概率的放置位置有关一般将合并后的概率放在最靠上的位置（如当合并后的概率和其他剩余概率值相等时，应放在这些相同概率值的最上面），以减小方差哈夫曼编码的效率高于费诺编码和香农编码随着序列长度$L$的不断增加，平均码长迅速降低，接近信源熵值，效率不断增加特点短码对应概率大的信源符号，长码对应概率小的信源符号，提高了编码效率缩减信源的最后两个码字总式最后一位不同，保证了哈夫曼编码为即时码优点哈夫曼编码通过概率匹配的方法提高了编码效率当信源为单个符号或序列长度较小时，哈夫曼编码仍可达到较高的编码效率（相比下高于费诺编码和香农编码）缺点其码字长度有时比定长编码的码字长，使得送出一个信源符号所需的平均信息量增加当传输码字序列中任意符号出错，就会存在译码断点，从而造成后面一系列译码出错，产生差错扩散，但定长编码不会出现这种情况对单个符号进行变长编码永远不能使得编码效率接近于$1$对于多个符号一起编码，虽然能够提高编码效率，但是也要大幅增加码表长度，增加存储器需要大量存储设备来缓冲码字长度，存储容量不够大时，容易出现短码取空，长码溢出的现象算数编码基本思想算术编码属于非分组码，需要将编码的全部数据看成某一长$L$的序列，将所有可能出现的L长序列的概率映射到$[0,1]$区间上，把$[0,1]$区间划分成许多个小段，每段的长度等于某一序列概率，再在段内取一个二进制小数作为码字，长度与序列概率匹配，从而实现高效率编码编码过程1.获取信源各符号的先验概率，转换为二进制数，将各符号的概率累加，获得符号累加概率（累加概率都用大写$P$表示，普通概率用小写$p$表示）$$ P_r=\sum_{i=1}^{r-1}p_i,P_0=0,P_1=p_1,P_2=p_1+p_2,\cdots $$2.计算序列累加概率$$ P(S,a_r)=P(S)+p(S)P_r,p(S,a_r)=p(S)p_r $$3.$P(S)$把区间$[0,1]$根据各序列的概率分布分割成若干个小区间，每个小区间的长度为其对应的序列的概率$p(S)$，各个小区间不重叠，选择小区间内任意一点可用来唯一代表该区间，取$P(S)$的小数点后$L$位，得到编码$$ L=\left \lceil \log \frac 1 {p(S)} \right \rceil $$如果小数位数$=L$，则直接取小数后$L$位，即$P(S)=C$如果小数位数$>L$，则将尾数依次向前进位，即$$ P(S)=C-2^{-L}+\sum_{i=L+1}^ma_k2^{-i},k=2,a_k\in\{0,1\} $$讨论$C$的取值满足关系$$ P(S)\leqslant C<P(S+1) $$这是一个左闭右开的区间，永远不可能取到$P(S+1)$）各个小区间是不重叠的，可以实现唯一译码满足概率匹配，编码效率高$L$较大时，$P(S)$对应较小，使得取整造成的误差较小，平均码长接近于信源熵值编码算法实际应用中，采用累积概率$P(S)$来表示码字$C(S)$，符号概率$p(S)$来表示状态区间$A(S)$，可得递推关系$$ \left \{ \begin {matrix} C(S,r)=C(S)+A(S)P_r\\ A(S,r)=A(S)p_r \end {matrix} \right. $$定义两个存储器，将初始值设置为$$ A(\varphi)=1,C(\varphi)=0 $$每输入一个信源符号，两个存储器$A$和$C$就按照递推关系更新一次，输入结束时，$C$就作为编码输出在计算过程中，状态区间$A(S)$会越来越小，由于$C(S)$是递增的，增量$A(S)P_r$会随着序列的增长而减小举例设有四个符号$a,b,c,d$，其符号概率分别为$0.100,0.010,0.001,0.001$，构成简单序列$\{abda\}$，求其算数编码可得各符号的累积概率依次为$0.000,0.100,0.110,0.111$，设初始状态为空序列$\phi$，定义两个存储器$A(\varphi)=1,C(\varphi)=0$，接着由递推关系依次求解$$ \begin {align} &C(\phi,a)=C(\phi)+A(\phi)P_a=0+1\times0=0;\\ &A(\phi,a)=A(\phi)p_a=1\times0.1=0.1;\\ &C(a,b)=C(a)+A(a)P_b=0+0.1\times0.1=0.01;\\ &A(a,b)=A(a)p_b=0.1\times0.01=0.001;\\ &C(a,b,d)=C(a,b)+A(a,b)P_d=0.01+0.001\times0.111=0.010111;\\ &A(a,b,d)=A(a,b)p_d=0.001\times0.001=0.000001;\\ &C(a,b,d,a)=C(a,b,d)+A(a,b,d)P_a=0.010111+0.000001\times0=0.010111;\\ &A(a,b,d,a)=A(a,b,d)p_a=0.1\times0.000001=0.0000001;\\ \end {align} $$接着计算序列码长$$ L=\left \lceil \log \frac 1 {p(S)} \right \rceil=\left \lceil \log \frac 1 {A(a,b,d,a)} \right \rceil=7 $$于是得到编码为$C$小数点后$7$位，不够的补$0$，得到$0101110$可同时求得编码效率为$$ \eta=\frac {H(\mathbf X)}{\overline K}=\frac {1.75}{\frac 7 4}=100\% $$拓展算术编码是一种现代编码方法，实际中比哈夫曼编码更加有效算术编码在图像数据压缩标准（如JPEG,JBIG）中扮演了重要角色限失真信源编码定理讨论无失真编码：输入符号与输出符号一一对应，信道的损失熵（疑义度）和噪声熵均为0，通过信道的信息传输率等于信源熵，因此无失真信源编码是保熵的过程，只是对冗余度进行了压缩有失真编码的中心任务：在允许失真的范围内把编码后的信息量压缩到最小，有失真信源编码的失真范围受限，也称为限失真信源编码，编码后的信息率受到压缩，属于熵压缩编码信息率失真函数$R(D)$的物理意义：允许失真为$D$时的最小信息率，当信息率大于$R(D)$时可以进行编码，小于时出现信息损失，不可在允许失真范围内编码引入限失真编码定理的原因保熵编码并非都是必须的，有时候信宿不需要或者没有能力接受信源发出的全部消息保熵编码并非总是可能的，如对连续信号进行数字处理时，不可能从根本去除量化误差降低信息率有利于信息传输和处理，从而有必要进行熵压缩编码定理阐述设离散无记忆信源$X$的信息率失真函数为$R(D)$，则当信息率$R>R(D)$，只要信源序列长度$L$足够长，则一定存在一种编码方法，其译码失真小于或等于$D+\epsilon$，$\epsilon$为任意小的正数，反之则无论采用怎样的编码方法，其译码失真必定大于0二元信源的情况下，对于任意小的$\epsilon>0$，每一个信源符号的平均码长应满足不等式$$ R(D)\leqslant\overline K\leqslant R(D)+\epsilon $$理解该定理适用于离散、连续的信源在失真限度内使得信息率接近$R(D)$的编码方法存在要使得信息率小于$R(D)$，平均失真一定会超过失真限度$D$无失真与限失真编码定理比较相同之处：都对信息量有一定的要求，给出了编码平均长度的范围不同之处：限失真编码定理中通过引入允许的一定程度失真，较大幅度地提高了编码效率其他编码方法（略）LZ编码、游程编码、矢量量化编码、预测编码、变换编码
第4章 信息率失真函数前言对于失真的合理与可行性分析实际信息处理过程允许一定程度的失真连续信源编码必定存在失真一定范围内的失真可以大幅提高编码效率本章的研究对象允许一定失真的离散信源编码和连续信源编码失真函数定义设某一信源$X$，输出样值为$x_i$，经过有失真的信源编码器，输出$Y$，样值为$y_j$，满足以下关系$$ x_i\in \{a_1,\cdots,a_n\},y_j\in \{b_1,\cdots,b_m\} $$如果$x_i$=$y_j$，则认为没有失真，反之认为产生失真失真函数表示为$d(x_i,y_i)$，是用来表示失真的大小的量，能衡量用$y_i$代替$x_i$所引起的失真程度，一般的失真函数可定义为$$ d(x_i,y_j)=\left \{ \begin {matrix} 0,&x_i=y_j\\ \alpha,&\alpha>0,x_i\neq y_j \end {matrix} \right. $$如果把所有的失真函数值排列起来，则可以用矩阵表示，构成失真矩阵$$ \mathbf d=\begin {bmatrix} d(a_1,b_1) & d(a_1,b_2) & \cdots & d(a_1,b_m)\\ d(a_2,b_1) & d(a_2,b_2) & \cdots & d(a_2,b_m)\\ \vdots & \vdots & \ddots & \vdots\\ d(a_n,b_1) & d(a_n,b_2) & \cdots & d(a_n,b_m)\\ \end {bmatrix} $$常见失真函数均方失真$$ d(x_i,y_j)=(x_i-y_j)^2 $$绝对失真$$ d(x_i,y_j)=|x_i-y_j| $$相对失真$$ d(x_i,y_j)=\frac {|x_i-y_j|} {|x_i|} $$误码失真$$ d(x_i,y_j)=\delta(x_i,y_j)=\left \{ \begin {matrix} 0,&x_i=y_j\\ 1,&\mathrm others \end {matrix} \right. $$推广将一般情况推广到序列编码情况，离散信源输出$L$长符号序列，经过信源编码后输出$L$长编码序列$$ \begin {matrix} \mathbf X=(X_1,X_2,\cdots,X_L),\mathbf x_i=(x_{i_1},x_{i_2},\cdots,x_{i_l},\cdots,x_{i_L})\\ \mathbf Y=(Y_1,Y_2,\cdots,Y_L),\mathbf y_j=(y_{i_1},y_{i_2},\cdots,y_{i_l},\cdots,y_{i_L}) \end {matrix} $$此时的失真函数可定义为$$ d_L(\mathbf x_i,\mathbf y_i)=\frac 1 L \sum_{l=1}^Ld(x_{i_l},y_{j_l}) $$平均失真定义由于$x_i$,$y_j$都是随机变量，因此失真函数也是一个随机变量，要分析整个信源的失真大小，就需要使用一个整体的值来表示定义失真函数的数学期望称为平均失真离散情况下$$ \begin {align} \overline D &=\sum_{i=1}^n\sum_{j=1}^mp(a_i,b_j)d(a_i,b_j)\\ &=\sum_{i=1}^n\sum_{j=1}^mp(a_i)p(b_j|a_i)d(a_i,b_j) \end {align} $$理解根据定义式可以将平均失真理解为给定信源分布$p(a_i)$在经过某一转移概率分布为$p(b_j|a_i)$的有失真信源编码器后产生的失真的总体量度将信源编码器看成一个假想信道，从而可以利用信道转移概率的思想来进行讨论推广对于连续随机变量有$$ \overline D =\int_{-\infty}^\infty\int_{-\infty}^\infty p_{X,Y}(x,y)d(x,y)\mathrm d x\mathrm d y $$对于$L$长序列编码情况有$$ \overline D_L=\frac 1 L \sum_{l=1}^LE[d(x_{i_l},y_{j_l})]=\frac 1 L\sum_{l=1}^L\overline D_l $$信息率失真函数前置知识回顾：信息率信息率函数是信道中平均每个符号能传送的信息量，单位为$bit/sig$$$ R=I(X;Y)=H(X)-H(X|Y) $$信息率就是所需输出的有关信源$X$的信息量，从信道的角度来考虑就是接收端$Y$需要获得的有关$X$的信息量，也就是互信息当$p(x_i)$一定时，$I$是关于$p(y_j|x_i)$的$\cup$型函数，有极小值信源编码器目的是使编码后所需要的信息传输率$R$尽可能小，然而$R$越小，所引起的平均失真越大信源压缩的必要性当信源输出的信息量大于信道的传输能力时，必须对信源进行压缩即使信源输出的信息量小于信道的传输能力，压缩编码也能够大幅度提高传输效率失真限度信源编码的过程其实是引入失真的过程要根据实际情况定义最大失真限度，保证压缩引入的失真必须在失真限度之内信息压缩原理对于给定的信源，在满足失真限度（平均失真小于某一值）的前提下，应该使编码后的信息量尽可能小，称为保真度准则定义D允许试验信道将失真编码器看作有干扰信道，用分析信道传输的方法探究失真编码将满足失真限度的所有转移概率分布构成一个假想信道，称为D允许试验信道，离散无记忆的情况下可写作$$ P_D=\{p(y_j|x_i);\overline D\leqslant D,i=1,2,\cdots,n,j=1,2,\cdots,m\} $$信息率失真函数R(D)在所有D允许信道中，寻找某一个信道，使得给定的信源经过此信道传输后，互信息达到最小，该最小的互信息即称为信息率失真函数$$ R(D)=\min_{P_D}I(X;Y) $$通常信源分布是给定的，于是互信息就取决于概率转移分布，也对应了不同D允许信道的选择$$ I(X;Y)=\sum_{ij}p(x_i,y_j)\log\frac {p(x_i|y_j)} {p(x_i)} $$数学模型离散无记忆信源的信息率失真函数可写作$$ R(D)=\min_{p_{ij}\in P_D}I(X;Y)=\sum_{p_{ij}\in P_D}p(a_i)p(b_j|a_i)\log\frac {p(b_j|a_i)}{p(b_j)} $$失真编码$$ I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X) $$理解互信息是信源熵和噪声产生的疑义度之差，也可以理解为接收端应收到的信息量与信道噪声产生的噪声熵之差，是信道传输最终有价值的信息量对于信源编码，$Y$是$X$的编码结果，不考虑信道噪声的影响。将信道噪声造成的损失（如疑义度）看作是信息存储或传输时需要去掉的冗余（可以忽略的次要成分），从而完成对信源的原始信息在允许的失真限度内进行了压缩从物理意义上来看，信息率是真函数是对于给定信源，在平均失真不超过失真限度$D$的条件下，信息率所允许压缩到的最小值$R(D)$因为互信息是在信源分布确定下的关于$p_{ij}$的下凸函数，存在极小值，因此存在合适的$p_{ij}$，使得互信息最小，也就意味着可以选择某种编码方式，使得在满足保真度的条件下，信源可以压缩到最小信息量信息率失真函数的性质$R(D)$的定义域和值域定义域和值域定义域为$[D_{min},D_{max}]$值域为$[H(X),0]$理解当平均失真取到最小值时，对应失真最小，信源的信息大部分都被传输，信息传输率（互信息）非常接近$H(X)$，当通过合理构造试验信道使得$D_{min}=0$时，信息能够被无失真传输，信息传输率就是信源熵$H(X)$当平均失真取到最大值时，相当于失真达到最大，信息都被损失掉了，信息传输率会达到0，相当于没有任何信息传输$D_{min}$的讨论构造式子$$ \begin {align} D_{min}&=\min \left [\sum_{i=1}^n \sum_{j=1}^mp(a_i)p(b_j|a_i)d(a_i,b_j) \right ]\\ &=\sum_{i=1}^n\left \{p(a_i)\min[\sum_{j=1}^mp(b_j|a_i)d(a_i,b_j)] \right \} \end {align} $$理解因为信源分别是给定的，我们能调整的只是假想信道的转移概率分布（即调整不同的编码方式）使得平均失真最小，因此可以将$min$移到后面那部分中，问题转换为求后面那部分式子的最小值由失真函数的性质可知，当信源输入$a_i$是固定的情况下，对于不同的$b_j$，失真矩阵中每行总有一个或多个相同的最小值在不同位置，因此可以由此构造试验信道使得平均失真最小化构造方法固定$a_i$，看失真矩阵中第$i$行的所有元素，让$d_{ij}$最小值对应的$p_{ij}$定为1，不为最小值的元素对应$p_{ij}$定为0，从而就能够构造出整体的最小值在实际求解过程中，求失真矩阵中每一行的最小元素乘以对应的$p(a_i)$值（如第一行的最小值就乘$p(a_1)$，第二行的最小值就乘$p(a_2)$，再把所有的值加起来），求和即可得出$D_{min}$值，然后再令每一行中最小元素所在位置的值为1，其他位置值为0，构建转移概率矩阵讨论当失真矩阵每一行至少有一个0时，才有可能通过构造一个合适的编码使得平均失真为0在每行至少一个0的基础上，若每列至多有一个0，有该等式成立$$ R(D_{min})=R(0)=H(X) $$$D_{max}$的讨论构造式子$$ \begin {align} D_{max}&=\min R(D)\\ &=\min \left [\sum_{i=1}^n\sum_{j=1}^mp(a_i)p(b_j|a_i)d(a_i,b_j)\right]\\ &=\min\left[\sum_{i=1,j=1}^{n,m}p(b_j|a_i)\sum_{i=1}^np(a_i)d(a_i,b_j)\right] \end {align} $$理解$D_{max}$虽然是一个最大值，但它其实是相对的，它对应了使得$R(D)=0$的最小失真，即对于任意大于$D_{max}$的失真，信息传输率都满足$R(D)=0$$R(D)=0$意味着没有信息被传输，$I(X;Y)=0$，说明$X$和$Y$是统计独立的，互相没有关系，转移概率和信源概率分布无关，有$$ p_{ij}=p(y_j|x_i)=p(y_j)=p_j $$问题转换为通过构造一个试验信道使得整个式子的值最小化构造方法固定$a_i$，若$\sum_{i=1}^np(a_i)d(a_i,b_j)$取到最小，则令$p(b_j|a_i)=p_j=1$，否则令其为0根据以上方法就有$$ D_{max}=\min\sum_{i=1}^np(a_i)d(a_i,b_j) $$也就是说，在求解过程中，先计算失真矩阵各列元素乘以其对应$p(a_i)$的值的和（例如某列中的第一个元素乘$p(a_1)$，第二个元素乘$p(a_2)$，再把所有值加起来），然后看哪一列的这一和值最小，令转移概率矩阵中的此列为1，其他列为0例题设信道输入为$X=\{a_1,a_2,a_3\}$，且为等概率分布，已知失真矩阵为$$D=\begin{bmatrix}1 & 2 & 3\\2 & 1 & 3\\3 & 2 & 1\end {bmatrix}$$求$D_{min}$和$D_{max}$及相应的试验信道转移概率矩阵首先求$D_{min}$$$ D_{min}=\frac 1 3min[1,2,3]+\frac 1 3min[2,1,3]+\frac 1 3min[3,2,1]=\frac 1 3\times 3=1 $$各行最小值均为1，分别在(1,1)(2,2)(3,3)处，于是此时试验信道的转移概率矩阵中这些位置的值记为1，其他位置均为0，得到转移概率矩阵$$P_{(Y|X)}= \begin {bmatrix}1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 1\end {bmatrix}$$接着求$D_{max}$$$ \begin {align} D_{max}&=\min\left [ \sum_{i=1}^np(a_i)d(a_i,b_j)\right ]\\ &=\min \begin {bmatrix} p(a_1)\times1+p(a_2)\times2+p(a_3)\times3\\ p(a_1)\times2+p(a_2)\times1+p(a_3)\times2\\ p(a_1)\times3+p(a_2)\times3+p(a_3)\times1 \end {bmatrix}\\ &=\min\begin {bmatrix} \frac 6 3\\ \frac 5 3\\ \frac 6 3 \end {bmatrix}=\frac 5 3 \end {align} $$发现使得该式子取到最小值的列为第二列，于是此时试验信道的转移概率矩阵中第二列的元素值记为1，其他位置均为0，得到转移概率矩阵$$P_{(Y|X)}=\begin {bmatrix} 0 & 1 & 0\\0 & 1 & 0\\0 & 1 & 0\end {bmatrix}$$$R(D)$是关于$D$的下凸函数（证明略）$R(D)$在定义域内是严格递减函数（证明略）信息率失真函数与信道容量从定义上来看信道容量为$C=\max_{p(a_i)}I(X;Y)$表示信道的最大传输能力，反映的是信道本身的特性，和信源无关为了排除信源特性对信道容量的影响，通常采用在所有信源中那个能够使平均互信息量达到最大的信源作为参考，从而使得信道容量仅与信道本身的特性有关信道不同，$C$也不同信息率失真函数为$R=\min_{p_D}I(X;Y)$表示保真度条件下信源信息率可以被压缩的最低限度，反映的是信源本身的特性，和信道无关为了排除信道特性对信息率失真函数的影响，通常采用所有的编码其中那个能够使得平均互信息量达到最小的编码器作为参考，从而使得信息率失真函数仅与信源本身的特性有关信源不同，$R$也不同从引入目的来看引入信道容量$C$是为了解决在所用信道中传送的最大信息量到底有多大的问题，其给出了可能传输的最大信息量为信道编码服务，提高通信的可靠性引入信息率失真函数$R$是为了解决在允许失真度$D$的条件下，信源编码能够压缩到什么程度的问题，其给出了保真度条件下信源信息率可以被压缩道的最低信度为信源的压缩编码服务，提高通信的有效性离散和连续信源的R(D)计算（略）
第3章 信道与信道容量信道的基本概念信道分类按用户数量分单用户信道一个输入端和一个输出端，信息朝一个方向传输多用户信道输入端和输出端中至少有一端存在两个以上住户，信息在两个方向上都能传输（双向）按输入输出关系分无反馈信道输出端的信号不反馈到输出端，输入输出无影响反馈信道输出信号通过一定途径反馈到输入端，使得输入端的信号发生变化按信道参数与时间的关系分固定参数信道信道参数（统计特性）不随时间变化而变化，如光纤、光缆信道等时变参数信道信道参数会随事件发生改变，如无线信道的参数会因为天气等环境原因而发生较大的变化按所受噪声种类分随机差错信道噪声独立随机地影响每个传输码元，如以高斯白噪声为主体的信道突发差错信道噪声和干扰的影响是前后相关的，错误成串出现，如实际的衰落信道、码间干扰信道按输入输出信号特点分离散信道输入输出信号在时间上离散连续信道信号的幅度是连续的，时间是离散的半离散半连续信道输入和输出两个信号中有一个是离散的，另一个则是连续的波形信道输入、输出信号在时间和幅度上均连续，可以用随机过程来描述由前面的章节可知，只要随机过程有某种限制（如限时限频），就可以分解成（时间或频率）离散的随机序列，随机序列可以是幅度上连续，也可以离散。因此波形信道可以拆分成前面三种信道来进行研究特殊信道多输入多输出(MIMO)信道在发送端和接收端分别放置多副天线的系统，具有可以充分利用空间资源、大大提高通信系统的性能的优点理解广义上来说，信道可以指一段线路，也可以指包含了设备的复杂系统，即使在同一个通信系统中，也可以有着不同的划分对于不同的划分方法，信道信号呈现出不同特点数学模型设输入为$\mathbf X=(X_1,X_2,\cdots,X_i,\cdots),X_i\in A=\{a_1,a_2,\cdots,a_n\}$，输出为$\mathbf Y=(Y_1,Y_2,\cdots,Y_j,\cdots),Y_j\in B=\{b_1,b_2,\cdots,b_m\}$，并使用条件概率$P(Y|X)$来描述信道输入、输出信号之间统计的依赖关系，也称转移概率无干扰（无噪声）信道信道的输出信号$Y$与输入信号$X$之间有确定的关系$Y=f(X)$，即已知$X$后就确知$Y$，所以转移概率可写作$$ p(Y|X)=\left \{ \begin {matrix} 1,&Y=f(X)\\ 0,&Y\neq f(X) \end {matrix} \right. $$有干扰无记忆信道信道的输出信号Y与输入信号X之间没有确定的关系，但转移概率满足关系$$ p(Y|X)=p(y_1|x_1)p(y_2|x_2)\cdots p(y_L|x_L) $$每个输出信号只和当前输入信号之间有转移概率关系，而与其他非该时刻的输入信号、输出信号都无关，也就是我们所说的无记忆，这使得问题得到简化，我们无需再采用矢量的形式，只要分析单个符号的转移概率即可二进制离散信道（BSC）输入和输出信号的符号数都是2，分别为0和1$$ \left \{ \begin {align} &p(Y=0|X=1)=p(Y=1|X=0)=p\\ &p(Y=1|X=1)=p(Y=0|X=0)=1-p \end {align} \right. $$输出信号仅与对应时刻的一个输入符号有关，而与以前的输入无关，因此是无记忆的离散无记忆信道（DMC）输入和输出的符号数大于2但为有限值输入为$n$元符号，即输入符号集有$n$个元素，信道的输出为$m$元符号，即输出符号集由$m$个元素构成，因此就会有$nm$个转移概率，可以用$n$行$m$列的转移概率矩阵来表示，可以写作$$ \mathbf P= \begin {bmatrix} p_{11} & p_{12} & \cdots & p_{1m} \\ p_{21} & p_{22} & \cdots & p_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ p_{n1} & p_{n2} & \cdots & p_{nm} \\ \end {bmatrix} $$由概率转移矩阵的性质可知，输入$a_i$时各可能输出值$b_j$的概率之和必定等于1，即$$ \sum^m_{j=1}=p(b_j|a_i)=1,i=1,2,\cdots,n $$BSC信道可以看作DMC信道的特例，因此其概率转移矩阵可以表示为2*2的形式$$ \mathbf P= \begin {bmatrix} 1-p&p\\ p&1-p \end {bmatrix} $$离散输入、连续输出信道（离散时间无记忆信道）信道输入符号选自一个有限的、离散的输入符号集，而信道输出未经量化，这时信道的输出可以是实轴上的任意取值，范围由$-\infty$到$\infty$，这样的信道模型称为离散时间无记忆信道，其特性由离散输入$X$、连续输出$Y$以及一组条件概率密度函数来决定最重要的一种是加性高斯白噪声（AWGN）信道，$G$表示一个零均值、方差为$\sigma^2$的高斯随机变量，当$X=a_i$给定后，$Y$将会是一个均值为$a_i$、方差为$\sigma^2$的高斯随机变量$$ \begin {matrix} Y=X+G\\ p_Y(y|a_i)=\frac{1}{\sqrt{2\pi}\sigma} e^{\frac{-(y-a_i)^2}{2\sigma^2}} \end {matrix} $$波形信道输入和输出都是随机过程$\{x(t)\}$和$\{y(t)\}$时，该信道称为波形信道。在实际的模拟系统中，信道都是波形信道，而在通信系统模型中，常把来自各部分的噪声都集中在一起，认为是通过信道加入的实际波形信道的频宽总是受限的，所以在有限的观察时间内，能满足限频、限时的条件，根据所学知识和，可以将这样一个平稳随机过程信号离散化为$L=2ft$个时间离散，取值连续的平稳随机序列，这样一来波形信道就转化为了多维连续信道，信道的转移概率密度函数为$$ p_Y(\mathbf y|\mathbf x)=p_Y(y_1,y_2,\cdots,y_L|x_1,x_2,\cdots,x_L) $$且满足$$ \int_\mathbf R\int_\mathbf R\cdots\int_\mathbf R\int_\mathbf Rp_Y(y_1,y_2,\cdots,y_L|x_1,x_2,\cdots,x_L)\mathrm dy_1 \mathrm d y_2\cdots \mathrm d y_L=1 $$当多维连续信道的转移概率密度函数满足如下关系时，称信道为连续无记忆信道（相互独立），即任意时刻的输出变量只和对应时刻的输入变量有关，与此前的均没有关系，即表示为$$ p_Y(\mathbf y|\mathbf x)=\prod^L_{l=1}p_Y(y_l|x_l) $$而在一般情况下，变量间不都是相互独立的，任意时刻的输出变量与以前时刻的输入、输出都有关，则称这样的信道为连续有记忆信道关于噪声的讨论加性噪声：噪声与信号是相加关系，也是多数情况下会出现的噪声记噪声过程的一个样本函数为$n(t)$，则单符号加性噪声信道可以表示为$y(t)=x(t)+n(t)$（加性多维连续信道的表示方法类似，只是将这里的过程换成序列）通常噪声与信号相互独立，因此信道的转移概率密度函数等于噪声的概率密度函数\[p_Y(y|x)=\frac{p_{X,Y}(x,y)}{p_X(x)}=\frac{p_{X,n}(x,n)}{p_X(x)}=p_n(n)\]考察条件熵$H(Y|X)$可以发现，这个熵就是由噪声所引起的，它等于噪声信源的熵$H(n)$乘性噪声：噪声与信号是相乘关系，较少见有干扰有记忆信道实际情况中遇到的信道都是该类信道，信道特性不理想，存在码间干扰，输出信号不但与当前的输入信号有关，还和以前的输入信号有关处理方法将记忆很强的$L$个符号当成矢量符号，各矢量符号之间可以认为无记忆，但这会引入误差，当$L$越大，误差则会越小将转移概率看成马尔科夫链的形式，记忆有限，信道的统计特性可用在已知现在时刻输入信号和前时刻信道所处的状态的条件下信道容量定义将信道中平均每个符号能够传送的信息量定义为信道的信息传输率$R$，单位为$bit/sig$$$ R=I(X;Y)=H(X)-H(X|Y) $$若平均传输一个符号所需时间为$t(s)$，那么信道在单位时间内平均传输的信息量就可以定义为信息传输速率，单位为$bit/s$$$ R_t=\frac{I(X;Y)}{t} $$对于某特定信道，转移概率是确定的，那么互信息I就是关于输入符号分布概率的上凸型函数，也就是说可以通过找到某种概率分布$p(a_i)$，使得互信息达到最大，定义该最大值就是信道所能传输的最大信息量，即信道容量，单位为$bit/sig$$$ \begin {matrix} C=\max_{p(a_i)}I(X;Y)\\ p(a_i)\geqslant0,\sum_{i=1}^np(a_i)=1 \end {matrix} $$理解根据单位可以知道，$C$表示了信道上每传送一个符号（每使用一次信道）所能携带的比特数性质对于固定参数的信道，信道容量是一个确定的值，但是在传输信息时信道能否提供其最大传输能力，则取决于输入端的概率分布拓展对于时变信道参数的信道，信道容量不再是一个固定的量，而是一个随机变量，要用其他的量来表征其信道性能平均容量也称遍历容量，是对随机信道容量的所有可能值进行平均的结果，一般用其来衡量系统整体意义上的信道容量性能中断容量当信道顺势容量小于用户要求的速率时，信道就会发生中断，发生这个事件的概率称为中断概率，例如看视频时选择高码率会有卡顿对于某个信道而言，中断概率的大小取决于用户的要求，要求速率越大，终中断概率就越大，某个用户要求的速率就定义为相应中断概率的中断容量$C$$$ p(C_{inst}<C_{outage})=P_{outage} $$离散单个符号信道及其容量无干扰离散信道输入输出一一对应，无噪无损信道，条件概率矩阵是一个单位矩阵，当输入符号等概率分布时，信道的传输能力达到信道容量$$ C=\max I(X;Y)=\log n $$多个输入对应一个输出，无噪有损信道，噪声熵为0，但疑义度（信息的损失量）不为0$$ C=\max I(X;Y)=\max H(Y) $$一个输入对应多个输出，有噪无损信道，疑义度为0，但噪声熵不为0$$ C=\max I(X;Y)=\max H(X) $$对称离散无记忆信道定义输入对称信道转移概率矩阵的每一行都包含相同的元素输出对称信道转移概率矩阵的每一列都包含相同的元素输入输出对称信道转移概率矩阵的每一行和每一列都包含相同元素例如$$ \mathbf P=\begin {bmatrix} \frac 1 2 & \frac 1 3 & \frac 1 6 \\ \frac 1 6 & \frac 1 2 & \frac 1 3 \\ \frac 1 3 & \frac 1 6 & \frac 1 2 \end {bmatrix} $$数学模型因为对称信道转移概率矩阵中每行的元素都相同，因此条件熵与信道输入符号的概率分布无关$$ \begin {align} H(Y|X)&=-\sum_ip(a_i)\sum_j p(b_j|a_i)\log p(b_j|a_i)\\ &=-\sum_jp(b_j|a_i)\log p(b_j|a_i)\\ &=H(Y|a_i),i=1,2,\cdots,n \end {align} $$信道容量可以写作$$ C=\max_{p(a_i)}I(X;Y)=\max_{p(a_i)}H(Y)-H(Y|X) $$特别地，当信道输入符号等概率分布，由于概率转移矩阵的列对称，因此可以求出信道的输出符号也是等概率分布的（反之也成立）$$ p(b_j)=\sum_ip(a_i)p(b_j|a_i)=\frac 1 n \sum_i p(b_j|a_i) $$要让H(Y)达到最大，即求C值，只有当信道输出符号等概率分布（此时输入符号也必定是等概率分布）才能取得，故对称DMC信道的容量为$$ C=\log m-H(Y|a_i)=\log m+\sum_{j=1}^mp_{ij}\log p_{ij} $$上式中，$\log m$为利用输入对称可求得，后者为利用输出对称求得应用根据以上的数学关系和推导，可以求任意对称信道的信道容量，通常会遇到参数不定的情况，求能够达到信道容量时的概率分布准对称离散无记忆信道定义如果转移概率矩阵P是输入对称输而输出不对称，称该信道为准对称DMC信道数学模型准对称信道的转移概率矩阵中每行的元素相等，因此仍有结论：条件熵与信道输入符号的概率分布无关$$ H(Y|X)=H(Y|a_i),i=1,2,\cdots,n $$但是转移概率矩阵的每列的元素不完全相同，因此信道的输入和输出分布概率可能不等，$H(Y)$的最大值可能小于$Y$等概时的熵，则有关系$$ C\leqslant\log m+\sum_{j=1}^mp_{ij}\log p_{ij} $$求解方法：根据互信息是关于输入符号概率的上凸型函数，因此可以用拉格朗日乘子法求解极值问题，进而求得最大输入符号概率和互信息一般离散无记忆信道BA算法为使得$I(X;Y)$最大化以求DMC的容量，输入符号概率集必须满足的充分和必要条件是$$ \left \{ \begin {align} I(a_i;Y)=C &,对于所有满足p(a_i)>0的i\\ I(a_i;Y)\leqslant C &,对于所有满足p(a_i)=0的i \end {align} \right. $$当信道平均互信息达到信道容量时，输入符号概率集中的每一个符号对输出端都提供相同的互信息，只有概率为0的符号除外理解在某种给定的输入符号分布下，若其中有一个符号$x=a_i$对于输出$Y$所提供的平均信息比其他输入符号的大，那么就可以更多地使用这一符号，即增大$a_i$出现的概率$p(x=a_i)$，使得平均互信息增大但是这样一来会改变输入符号的分布，使得该符号的平均互信息减小，其他符号的互信息增大因此需要不断地调整输入符号的概率分布，最终将使得每个概率不为零的输入符号对输出Y提供的平均互信息相同注意BA算法只给出了达到信道容量$C$时输入符号概率分布的充要条件，无法根据这个结论来计算具体值，因此没有具体可求的公式，通常最佳分布并不唯一，只要满足上述充要条件，使得互信息最大即可信源与信道的匹配符号匹配信源输出的符号必须是信道能够传送的符号，即要求信源符号集就是信道入口符号集或其子集这是实现信息传输的必要条件，可以在信源与信道间加入编码器予以实现，也可以在信源压缩编码时一步完成信息匹配定义对于某一信道，只有当输入符号的概率分布$p(x)$满足一定条件时才能达到其信道容量C，只有特定信源才能使得某一信道的信息传输速率达到最大当信源与信道连接时，其信息传输率$R=I(X;Y)$并未达到最大，即信道没有得到充分利用，信道有冗余当信源与信道连接时，信息传输速率达到了信道容量，则称此信源与信道达到匹配数学模型信道绝对冗余度定义为$$ C-I(X;Y) $$信道相对冗余度定义为$$ 1-\frac {I(X,Y)}{C} $$讨论冗余度大，说明信源和信道的匹配程度低，此时信道的信息传递能力没有得到充分利用冗余度小，说明信源和信道能够较好地匹配，此时信道的信息传递能力得到了充分利用实际情况中一般不能实现冗余度为0，因此只要让冗余度尽可能小即可多输入多输出信道及其容量（略）定义每个信道输出都与所有M个信道输入信号有关，是由M个信道输入信号经各自路径传输后与噪声的线性叠加MIMO信道模型MIMO信道容量讨论MIMO系统对于提高无线通信系统的容量具有极大潜力连续信道及其容量基础：加性噪声信道幅度连续的单符号加性信道定义信道输入和输出均为取值连续的一维随机变量，加入信道的噪声是均值为0、方差为$\sigma^2$的加性高斯白噪声数学模型噪声的微分熵可以写作$$ H_c(n)=\frac 1 2 \log 2\pi\mathrm e \sigma^2 $$平均互信息，即信息传输率为$$ I(X;Y)=R=H_c(X)+H_c(Y)-H_c(X,Y) $$信道容量为$$ C=\max_{p(x)}I(X;Y)=\max_{p(x)}[H_c(Y)-H_c(Y|X)]=\max_{p(x)}H_c(Y)-\frac 1 2\log 2 \pi \mathrm e \sigma^2 $$为了让上式达到最大，求解得输入必须也是满足高斯分布得随机变量，均值为0，方差为$S$$$ C=\frac 1 2 \log2 \pi\mathrm e P-\frac 1 2 \log2 \pi\mathrm e\sigma^2=\frac 1 2 \log\frac P {\sigma^2}=\frac 1 2\log(1+\frac S {\sigma^2}) $$信噪比（输入信号与噪声的功率比）记作$$ SNR=\frac S {\sigma^2} $$拓展只要是满足加性关系的信道，其信道容量的上下界即可求除，但是乘性噪声就会很难分析$$ \frac 1 2\log(1+\frac S {\sigma^2})\leqslant C\leqslant \frac 1 2 \log 2 \pi \mathrm e P-H_c(n),P=S+\sigma^2 $$理解：噪声熵考虑的是最坏的情况，因此左边才能作为信道容量的下限值，当噪声满足高斯分布时，对于通信系统的影响最大，不知是因为其方便计算，在设计通信系统时往往要考虑最糟的情况以规避不必要的影响多维无记忆加性连续信道定义输入输出均为随机序列，加入噪声为均值为0的高斯噪声数学模型互信息满足关系$$ I(\mathbf X; \mathbf Y)\leqslant\sum_{l=1}^LI(X_L;Y_L)=\sum_{l=1}^L\frac 1 2 \log (1+\frac {P_l} {\sigma^2_l}) $$则$$ C=\max_{p(x)}I(\mathbf X;\mathbf Y)=\sum_{l=1}^L\frac 1 2 \log(1+\frac {P_L} {\sigma^2_l})\mathrm bit/L $$当每个单元时刻上的噪声都是均值为0、方差相同为$\sigma^2$的高斯噪声时，有$$ C=\frac L 2 \log(1+\frac S {\sigma^2})\mathrm bit/L $$当个单元时刻$L$个高斯噪声均值为0，但方差不同时，若输入信号的总平均功率受限，满足以下约束条件时，此时个单元时刻的信号平均功率应合理分配，才能使信道容量最大$$ E[\sum_{l=1}^LX_l^2]=\sum_{l=1}^LE[X^2_l]=\sum_{l=1}^LP_l=P $$注水法各个时刻的信道输出功率为$$ \nu=\frac{P+\sum_l\sigma^2_l}{L} $$各单元时刻输入信号平均功率为$$ P_l=\nu-\sigma^2_l=\frac {P+\sum_{l=1}^L\sigma^2_l}{L}-\sigma^2_l,l=1,2,\cdots,L $$此时信道容量$$ C=\frac 1 2 \sum_{l=1}^L\log\frac{P+\sum_{l=1}^L\sigma_l^2}{L\sigma_l^2} $$若果某些单元时刻的噪声$\sigma_l^2$太大，大于各个时刻的信道输出功率，使得$P_l$出现负值，说明这些时刻的信道质量太差，无法使用，必须把$P_l$置为0，不分配功率，予以关闭，然后再重新根据分配法则调整信号功率分配详见课本例3-10总体思路：计算平均输出功率→关闭输出功率大于平均输出功率的信道（置为0）→重新计算平均输出功率→循环前面的步骤，直到能够保证平均输出功率大于所有子信道的平均功率，再计算此时的总信道容量限时限频限功率加性高斯白噪声信道定义在波形信道中，在限时$t_B$、限频$f$的条件下可转换为多维连续信道，将输入输出的随机过程转换成L维的随机序列数学模型波形信道的平均互信息为$$ I[x(t);y(t)]=\lim_{L\to\infty}[H_c(\mathbf X)+H_c(\mathbf Y)-H_c(\mathbf X,\mathbf Y)] $$信息传输率$$ R_t=\lim_{t_B\to\infty}\frac 1 {t_B}I(\mathbf X;\mathbf Y)\mathrm bit/s $$信道容量$$ C_t=\max_{p(x)}[\lim_{t_B\to\infty}\frac 1 {t_B} I(\mathbf X; \mathbf Y)]\mathrm bit/s $$香农公式定义高斯白噪声加性信道单位时间的信道容量数学模型$$ C_t=\lim_{t_B\to\infty}\frac C {t_B}=W\log(1+\frac {P_S} {N_0W})\mathrm bit/s $$讨论当带宽$W$一定时，SNR与$C_t$成对数关系，SNR增大，$C_t$就增大，但增大到一定程度后趋于缓慢当输入信号功率$P_s$一定时，增加信道带宽，容量可以增加，但到一定阶段后增加变得缓慢（因为当噪声为加性高斯白噪声时，随着W的增加，噪声功率$N_0W$也随之增加）即使带宽是无限的，信道容量仍是有限的，当$C_\infty=1bit/s$，$P_s/N_0=\ln 2=-1.6dB$，即传送$1bit$信息，信噪比最低只需要$-1.6dB$，这也叫做香农限$C_t$一定时，带宽$W$增大，SNR会降低，二者可以相互转换。若有较大的传输带宽，则在保持信号功率不变的情况下，可容许较大的噪声，即此时系统的抗噪声能力较高离散序列信道及其容量定义实际应用中，信道的输入和输出一般都是在空间或时间上离散的随机序列，有记忆和无记忆的离散序列信道，更多情况下是有记忆的，即序列的转移概率之间有关联性数学模型无记忆离散序列信道的转移概率为（仅与当前输入有关）$$ p(\mathbf Y|\mathbf X)=p(Y_1,\cdots,Y_L|X_1,\cdots,X_l)=\prod_{l=1}^Lp(Y_l|X_l) $$互信息的两个性质如果信道无记忆，那么$$ I(\mathbf X;\mathbf Y)\leqslant\sum_{l=1}^LI(X_l;Y_l) $$如果输入矢量$X$的各分量相互独立，那么$$ I(\mathbf X;\mathbf Y)\geqslant\sum_{l=1}^LI(X_l;Y_l) $$当输入矢量$X$独立且信道无记忆时，上述两式子取等，两个性质达到统一当输入适量达到上述最佳分布时，有$$ C_L=\max_{P_X}I(\mathbf X;\mathbf Y)=\max_{P_X}\sum_{l=1}^LI(X_l;Y_l)=\sum_{l=1}^L\max_{P_X}I(X_l;Y_l)=\sum_{l=1}^LC(l) $$信道平稳时，有$$ C_L=LC_l,I(\mathbf X;\mathbf Y)\leqslant LC_l $$拓展若果对离散但符号信道进行$L$次扩展，就形成了$L$次离散无记忆序列信道，信道序列转移概率为$$ p(\mathbf Y|\mathbf X)=\prod_{l=1}^Lp(Y_l|X_l) $$
第2章 信源与信息熵信源的分类与数学模型无记忆信源发出单个符号的无记忆信源每次只发出一个符号代表一个信息的信源$$ A=\{a_1,a_2,\cdots,a_n\}, X\in A $$$$ \begin{bmatrix} \mathbf{X}\\ P \end{bmatrix}= \begin{bmatrix} a_1 & a_2 & \cdots & a_n\\ p(a_1) & p(a_2) & \cdots & p(a_n) \end{bmatrix} $$$$ p(a_i)\geqslant0, \sum_{i=1}^{n}p(a_i)=1 $$发出单个符号的连续无记忆信源发出的消息也是单个符号，但消息数量是无限的，如测量干电池的电压值，取值为\([0,1.5]\)之间的所有实数，测量值随机$$ \begin {bmatrix} X\\P \end {bmatrix}= \begin {bmatrix} (a,b)\\p_X(x) \end {bmatrix}或 \begin {bmatrix} \mathbf{R}\\p_X(x) \end {bmatrix} $$$$ p_X(x)\geqslant0, \int_a^bp_X(x)\mathrm{dx}=1或\int_\mathbf{R}p_X(x)\mathrm{dx}=1 $$发出符号序列的无记忆信源每次发出一组含2个或以上符号的序号序列来代表一个消息，需要用随机矢量来描述\[\mathbf{X}=(X_1,X_2,\cdots,X_L)\]\[p(X_1,X_2,\cdots,X_L)=p(X_1)p(X_2)\cdots p(X_L)\]\(L=2\)时，信源的联合概率分布为$$ \begin{bmatrix} \mathbf{X}\\ P \end{bmatrix}= \begin{bmatrix} a_1,a_1 & a_1,a_2 & \cdots & a_n,a_n\\ p(a_1,a_1) & p(a_1,a_2) & \cdots & p(a_n,a_n) \end{bmatrix} $$$$ p(a_i,a_j)\geqslant0,\sum_{i,j=1}^np(a_i,a_j)=1 $$平稳信源定义信源发出的序列的统计性质和时间的推移无关分类强平稳信源信源输出序列的各维概率分布都不随时间推移而发生变化弱平稳信源输出序列均值与起始时刻无关而仅与时间间隔有关离散平稳无记忆信源（独立同分布）信源输出的每个符号都统计独立，且具有相同的概率空间有记忆信源定义信源在不同时刻发出的符号之间是相互依赖的（既有记忆的，前后相互关联和影响）数学模型需引入条件概率来反映各个符号间的记忆特征$$ p(x_1,x_2,x_3,\cdots,x_L)=p(x_L|X^{L-1})p(X^{L-1})=p(x_{L-1}|X^{L-2})p(X^{L-2})=\cdots $$马尔可夫信源定义当信源的记忆长度为\(m+1\)时，该时刻发出的符号与前\(m\)个符号有关联性，而与更前面的符号无关，这样的有记忆信源称为\(m\)阶马尔可夫信源注意：信源的记忆长度应该是阶数+1，如2阶马尔可夫信源的记忆长度应该是3，某时刻发出的符号与前2个符号有关稳定马尔可夫信源：概率分布特性不随时间推移改变的马尔可夫信源，发出稳定马尔科夫链齐次马尔可夫信源：转移概率（条件概率）不随时间推移而改变，发出序列为齐次马尔科夫链数学模型整体描述：可用马尔科夫链来进行描述$$ \begin {align} p(x_1,x_2,x_3,\cdots,x_L)&=p(x_L|x_1,x_2,x_3,\cdots,x_{L-1})p(x_1,x_2,x_3,\cdots,x_{L-1})\\ &=p(x_L|x_{L-m},\cdots,x_{L-1})p(x_1,x_2,x_3,\cdots,x_{L-1})\\&=\cdots\cdots \end {align} $$某时刻前出现的m个符号组成的序列，称状态；\( s_i\)代表一种状态，可以表示以上描述条件概率中的条件，共有\(Q=n^m\)种取值\[s_i=(x_{i_1},x_{i_2},\cdots,x_{i_m}), x_{i_m}\in{A}=(a_1,a_2,\cdots,a_n)\]符号条件概率：表示信源在某时刻出现符号\(x_j\)的概率与信源此时所处的状态\(s_i\)有关\[p(x_j|s_i),i=1,2,\cdots,Q;j=1,2,\cdots,n\]状态转移概率：表示从\(s_i\)状态变换到\(s_j\)状态的概率$$ p(s_j|s_i),i,j=1,2,\cdots,Q $$更一般地，系统从\(m\)时刻的状态\(s_i\)转移到\(n\)时刻的状态\(s_j\)（经过\(n-m\)步）的概率可以表示为$$ p_{ij}(m,n)=P\{s_j|s_i\},i,j\in S $$通常特别关心\(n-m=1\)的情况，此时的状态转移概率称为基本转移概率，也称为一步转移概率$$ p_{ij}(m,m+1)记为p_{ij}(m)=P\{S_{m+1}=j|S_m=i\}=p_{ij} $$从而有\(k\)步转移概率为\[p_{ij}^{(k)}(m)=P(S_{m+k}=j|S_m=i)=p_{ij}^{(k)}\]转移概率矩阵（一步）$$ \mathbf{{P}}=\{p_{ij},i,j\in S\}= \begin{bmatrix} p_{11} & p_{12} & \cdots & p_{1Q} \\ p_{21} & p_{22} & \cdots & p_{2Q} \\ \vdots & \vdots & \ddots & \vdots \\ p_{Q1} & p_{Q2} & \cdots & p_{QQ} \\ \end{bmatrix} $$行数对应\(i\)，列数对应\(j\)，每个元素\(p_{ij}\)表示从状态\(s_i\)转移到状态\(s_j\)的概率每行之和为1，每列不一定为1符号条件概率矩阵≠状态转移概率矩阵稳态分布概率，满足\[\sum_iW_ip_{ij}=W_j,\sum_iW_i=1\]计算稳态分布概率时需满足的条件：遍历性，不可约性，非周期性计算方法：利用矩阵点乘、解方程即可得出各稳态概率香农线图（马尔可夫状态图）在各圆圈中写上各状态的代号，箭头指从一个状态转移到另一个状态，上面的数字表示转移概率箭头出发的状态表示初始状态（条件），指向的状态表示到达的状态（目标）离散信源熵和互信息自信息量定义具有概率\(p(x_i)\)的符号\(x_i\)的自信息量为$$ I(x_i)=-\mathrm{log}p(x_i) $$联合自信息量：$$ I(x_i,y_j)=-\mathrm{log}p(x_i,y_j) $$条件自信息量：表示在给定\(y_j\)条件符号下\(x_i\)出现时收信者得到的信息量$$ I(x_i|y_j)=-\mathrm{log}p(x_i|y_j) $$单位对数底为2，单位为比特(\(bit\))对数底为e，单位为奈特(\(nat\))对数底为10，单位为笛特(\(det\))理解自信息量表示该符号出现后，提供给收信者的信息量是多少，一个量化的值不确定度：也可理解成信源符号在发出前所存在的不确定度，出现概率越小，自信息量越大，发生的可能性小，不确定度越大；概率越接近1，说明发生的可能性特别大，很容易猜测是否发生，自信息量很小，不确定度也很小性质-\[p(x_i)=1,I(x_i)=0;p(x_i)=0,I(x_i)=\infty\]非负性：概率总是在\([0,1]\)区间内，因此自信息量一定大于0，不会是负数单调递减性：$$ 若p(x_1)<p(x_2),则I(x_1)>I(x_2) $$可加性：若\(x_i,y_j\)相互独立，则$$ p(x_i,y_j)=p(x_i)p(y_j),I(x_i,y_j)=I(x_i)+I(y_j) $$离散信源熵定义总体平均意义上的信源不确定度，称为信源熵，是在平均意义上来表征信源总体特性的量用信源中各符号自信息量的数学期望表示$$ H(X)=E(I(X))=\sum_ip(x_i)I(x_i)=-\sum_ip(x_i)\mathrm{log}(p(x_i)) $$条件熵：条件自信息量的联合概率加权均值$$ H(X|Y)=-\sum_{i,j}p(x_i,y_j)\mathrm{log}p(x_i|y_j) $$联合熵：每个元素对的自信息量的加权均值$$ H(X,Y)=-\sum_{i,j}p(x_i,y_j)\mathrm{log}p(x_i,y_j) $$满足关系$$ \begin {matrix} H(X,Y)=H(X)+H(Y|X)\\ H(X,Y)=H(Y)+H(X|Y) \end {matrix} $$单位：$$ bit/sig $$理解与热熵相似，表征一个系统/信源的混乱程度，即所含有的不确定程度性质当信源给定，概率空间也随之确定，信源熵也相应是一个确定的值，不同概率空间熵值不同因为概率处于\([0,1]\)区间，因此信源熵也是非负的当某一符号的概率为0时，规定此时其在熵计算公式中的贡献也为0当信源只包含一个符号时，则其概率确定，始终为1，此时信源熵为0，是确定性信源（区别于概率为0的情况）互信息定义先验与后验先验概率：从原因的角度看结果，如掷骰子掷到某个点数的概率\(p(x)\)后验概率：从结果的角度看原因，如信源接收到符号\(y\)时信源发出\(x\)的概率（与条件概率区别）接收者通过信道传输收到的信源\(X\)的信息量，即通过信道传输后不确定度的减少量$$ \begin {matrix} \begin {align} I(X;Y)&=H(X)-H(X|Y)\\ &=\sum_{i,j}p(x_i,y_j)\mathrm{log}\frac{p(x_i|y_j)}{p(x_i)}\\ &=\sum_{i,j}p(x_i,y_j)\mathrm{log}\frac{p(y_j|x_i)}{p(y_j)}=I(Y;X) \end {align} \end {matrix} $$互信息在集合\(X\)上的统计平均为$$ I(X|y_j)=\sum_ip(x_i|y_j)I(x_i|y_j)=\sum_ip(x_i|y_j)\mathrm{log}\frac{p(x_i|y_j)}{p(x_i)} $$平均互信息可定义为互信息在\(X\)上的统计平均值再在\(Y\)集合上的概率加权统计平均值$$ I(X;Y)=\sum_jp(y_j)I(X;y_j)=\sum_{i,j}p(x_i,y_j)\mathrm{log}\frac{p(x_i|y_j)}{p(x_i)} $$性质统计平均意义上的互信息一定大于0，满足关系\(0\leqslant I(X;Y)\leqslant H(X)\)当\(p(x_i)\)一定时，\(I\)是关于\(p(y_j|x_i)\)的\(\cup\)型函数，有极小值当\(p(y_j|x_i)\)一定时，\(I\)是关于\(p(x_i)\)的\(\cap\)型函数，有极大值理解\(H(X)\)一定大于\(H(Y|X)\)，加入条件会使得熵（即不确定度）降低，在已知\(Y\)后，\(X\)的不确定度减少单个符号之间的互信息可以定义为符号后验概率与先验概率比值的对数，该值可正可负$$ I(x_i,y_j)=\mathrm{log}\frac {p(y_j|x_i)}{p(x_i)} $$物理意义\(H(X)\)是符号\(X\)的熵或不确定度\(H(X|Y)\)是当\(Y\)已知时\(X\)的不确定度可以看作由于信道上存在干扰和噪声而损失掉的平均信息量也可以看作由于信道上存在干扰和噪声使接收端获得\(Y\)后还剩余的对信源符号\(X\)的平均不确定度，称为疑异度\(H(Y|X)\)是当信源发出符号已知时需要确定接收符号\(Y\)所需的平均信息量可以看作唯一地确定信道噪声所需要的平均信息量，称为噪声熵或散布度\(I(X;Y)=H(X)-H(X|Y)\)是\(Y\)已知后所获得的关于\(X\)的信息量互信息反映出的关系\(I(X;Y)=H(X)\)：已知\(Y\)就能完全解除\(X\)的不确定度，是最理想的情况，信道为理想信道/无扰信道\(I(X;Y)>0\)：正相关，信宿获得信息\(I(X;Y)=0\)：不相关，信源信宿相互独立，信道为全损信道\(I(X;Y)<0\)：负相关，误导信宿拓展三变量情况下单符号与符号对之间的互信息为\[I(x_i;y_j,z_k)=\mathrm{log}\frac{p(x_i|y_j,z_k)}{p(x_i)}=I(x_i;z_k)+I(x_i;y_j|z_k)\]三变量下的条件互信息量$$ I(x_i;y_j|z_k)=\mathrm{log}\frac{p(x_i|y_j,z_k)}{p(x_i|z_k)} $$表明一个联合事件\((y_j,z_k)\)出现后所提供的有关\(x_i\)的信息量\(I(x_i;y_j,z_k)\)等于\(z_k\)事件出现后所提供的有关\(x_i\)的信息量\(I(x_i;z_k)\)加上在给定\(z_k\)条件下再出现\(y_j\)事件后所提供的有关\(x_i\)的信息量\(I(x_i;y_j|z_k)\)三变量互信息量满足关系$$ I(X;Y|Z)=H(X|Z)-H(X|Z,Y)=H(Y|Z)-H(Y|Z,X) $$$$ I(X;Y,Z)=I(X;Y)+I(X;Z|Y) $$数据处理中信息的变化当消息通过多级处理器时，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量趋于变小。信息不增性：数据处理过程中只会失掉信息，绝不会出现新的信息。任何信息处理过程中总会失掉信息，最多保持原来的信息，且信息一旦丢失，用任何手段都不可能再恢复。相对熵（交叉熵，cross entropy）定义\(p\)相对于\(q\)的相对熵为$$ D(p//q)=\sum_ip_i\mathrm{log}\frac{p_i}{q_i} $$理解用来衡量概率分布\(p_i\)与\(q_i\)之间的差异是两个概率测度之间的“距离”\(p_i\)=\(q_i\)时，相对熵为0也可理解为度量真实分布为\(p\)而假定分布为\(q\)时的无效性互信息可理解为联合分布\(p(x,y)\)与乘积分布\(p(x)p(y)\)之间的相对熵性质非负性不对称性熵的性质非负性（等号当且仅当\(p_i=1\)时取得）$$ H(X)=H(p_1,p_2,\cdots,p_n)\geqslant0 $$确定性$$ H(0,1)=H(1,0,\cdots,0)=0 $$只要信源符号中有一个符号的出现概率为1，则该信源的信源熵就为0，因为在概率空间中，如果有两个基本事件，一个为必然事件的话，另外一个就是不可能事件，由此可推断到n维概率空间对称性：熵函数所有变元可以互换，不影响函数值$$ H(p_1,p_2,\cdots,p_n)=H(p_2,p_1,\cdots,p_n) $$香农辅助定理$$ H(p_1,p_2,\cdots,p_n)=-\sum_{i=1}^np_i\mathrm{log}p_i\leqslant-\sum_{i=1}^np_i\mathrm{log}q_i $$对于任意概率分布\(p_i\)，它对其他概率分布\(q_i\)的自信息量取数学期望时，必大于\(p_i\)本身的熵该不等式也称为吉布斯不等式最大熵定理$$ H(X)\leqslant H(\frac{1}{M},\frac{1}{M},\cdots,\frac{1}{M})=\mathrm{log}M $$当且仅当离散无记忆信源输出的各符号等概率时，信源熵最大。可以理解为每种符号出现的可能性相等，很难确定哪个符号出现，不确定性大条件熵小于无穷熵$$ H(Y|X)\leqslant H(Y) $$上式当且仅当\(y\)和\(x\)相互独立时取等号$$ H(Z|X,Y)\leqslant H(Z|Y) $$上式当且仅当\(p(z|x,y)=p(z|y)\)时取等号$$ H(X,Y)\leqslant H(X)+H(Y) $$上式当且仅当两集合相互独立时取等号扩展性$$ \lim_{\epsilon \to0}H_{n+1}(p_1,\cdots,p_n-\epsilon,\epsilon)=H_n(p_1,p_2,\cdots,p_n) $$可加性$$ H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y) $$递增性$$ \begin {align} &H_{n-m+1}(p_1,p_2,\cdots,p_{n-1},q_1,q_2,\cdots,q_m)\\ &=H_n(p_1,p_2,\cdots,p_{n-1},p_n)+p_nH_m(\frac{q_1}{p_n},\frac{q_2}{p_n},\cdots,\frac{q_m}{p_n}) \end {align} $$若信源\(X\)中有一元素被划分成\(m\)个元素（符号），而这\(m\)个元素的概率之和等于原元素的概率，则新信源的熵会增加，增加是源自于划分而产生的不确定性离散序列信源的熵离散无记忆信源的序列熵定义此时信源输出是一个序列，用矢量表示$$ \mathbf{X}=(X_1,X_2,\cdots,X_l,\cdots,X_L),X_l\in \{x_1,x_2,\cdots,x_n\},l=1,2,\cdots,L $$随机序列的概率$$ \begin {align} p(\mathbf{X=x_i})&=p(X_1=x_{i_1},X_2=x_{i_2},\cdots,X_L=x_{i_L}),i=1,2,\cdots,n^L;i_l=1,2,\cdots,n\\ &=p(x_{i_1})p(x_{i_2}|x_{i_1})p(x_{i_3}|x_{i_1},x_{i_2})\cdots p(x_{i_L}|x_{i_1},x_{i_2},\cdots,x_{i_{L-1}})\\ &=p(x_{i_1})p(x_{i_2}|x_{i_1})p(x_{i_3}|x_{i_1}^2)\cdots p(x_{i_L}|x_{i_1}^{L-1}) \end{align} $$信源序列熵为$$ H(\mathbf{X})=-\sum_{i=1}^{n^L}p(\mathbf{x_i})\mathrm{log}p(\mathbf{x_i})=-\sum_{i_1=1}^n\sum_{i_2=1}^n\cdots\sum_{i_L=1}^np(x_{i_1},x_{i_2},\cdots,x_{i_L})\mathrm{log}p(x_{i_1},x_{i_2},\cdots,x_{i_L}) $$无记忆情况下$$ \begin {align} &p(\mathbf{x_i})=p(x_{i_1},x_{i_2},\cdots,x_{i_L})=p(x_{i_1})p(x_{i_2})p(x_{i_3})\cdots p(x_{i_L})\\ &H(\mathbf{X})=-\sum_{i_1=1}^n\sum_{i_2=1}^n\cdots\sum_{i_L=1}^np(x_{i_1})p(x_{i_2})p(x_{i_3})\cdots p(x_{i_L})[\mathrm{log}p(x_{i_1})+\cdots+\mathrm{log}p(x_{i_L})]=\sum_{l=1}^LH(X_l) \end {align} $$平均符号熵$$ H_L(\mathbf{X})=\frac {1} {L}H(\mathbf{X}) $$平稳情况下$$ H(X_1)=H(X_2)=\cdots=H(X_L),H(\mathbf{X})=LH(X_l) $$离散有记忆信源的序列熵定义$$ \begin {align} H(\mathbf{X})&=H(X_1,X_2,\cdots,X_L)\\&=H(X_1)+H(X_2|X_1)+\cdots+H(X_L|X_1,X_2,\cdots,X_{L-1})\\ &=H(X_L)=\sum_{l=1}^LH(X_l|X^{L-l}) \end {align} $$其他结论与定义与无记忆信源的完全一致无记忆信源是有记忆信源的一个特例离散平稳信源满足的几个结论结论1$$ H(X_L|X^{L-1})是L的单调非增函数 $$随着L的增大，该值减小或与前值相等条件熵始终小于或等于无条件熵，条件较多的熵小于或等于减少一些条件的熵，因此满足单调非增（要么小于，要么等于，不是严格的递减）结论2$$ H_L(\mathbf{X})\geqslant H(X_L|X^{L-1}) $$由平均值的定义可以推出，一组数的平均值一定大于这组数中的最小值，结合结论1可得到该结论结论3\(H_L(\mathbf{X})\)是\(L\)的单调非增函数，满足：$$ \begin {matrix} LH_L(\mathbf{X})=(L-1)H_{L-1}(\mathbf{X})+H(X_L|X^{L-1})\\ \because H_L(\mathbf{X})\geqslant H(X_L|X^{L-1})\\ \therefore \cdots H_{L-1}(\mathbf{X})\geqslant H_{L}(\mathbf{X})\geqslant H_{L+1}(\mathbf{X})\cdots\\ \end {matrix} $$随着L的增大，总熵值中增加项的值就越来越小（由结论1得），从而导致整体得平均值减小或不变。例如\((4,3,2)\)的平均值是3，当增加一个更小的数\((4,3,2,1)\)，平均值仍是3（对应不变的情况），而\((4,3,2,0.5)\)的平均值是2.375<3（对应减小的情况），因此使得总平均值单调非增结论4$$ L\to\infty时，H_\infty(\mathbf{X})=\lim_{L\to \infty}H_L(\mathbf{X})=\lim_{L\to\infty}H(X_L|X^{L-1}) $$极限信息熵才能最真实地反映信源的实际情况马尔可夫信源的熵用极限熵表示$$ \begin {align} H_\infty(\mathbf{X})&=\sum_ip(s_i)H(X|s_i)\\ &=-\sum_ip(s_i)H(X|s_i)\sum_jp(x_j|s_i)\mathrm{log}p(x_j|s_i) \end {align} $$\(p(s_i)\)表示马尔可夫链的稳态概率\(H(X|s_i)\)表示信源处于某一状态si时发出一个消息符号的平均不确定性连续信源的熵和互信息幅度连续的单个符号信源熵定义$$ H(X)=\lim_{n\to \infty}H_n(X)=-\int_a^bp_X(x_i)\log p_X(x_i)\mathrm d x-\lim_{\Delta x \to 0}\log \Delta x $$第二项为无穷大，舍弃，于是得到微分熵表达式$$ H_c(X)=-\int_{-\infty}^{\infty}p_X(x)\mathrm{log}p_X(x)\mathrm{d}x $$联合熵$$ H_c(X,Y)=-\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}p_{X,Y}(x,y)\log p_{X,Y}(x,y)\mathrm{d}x\mathrm{d}y $$条件熵$$ H_c(Y|X)=-\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}p_X(x)p_Y(y|x)\log p_Y(y|x)\mathrm d x \mathrm d y $$理解连续信源熵的形式和离散信源熵相同，但物理意义不同。理论上来说连续信源的不确定度应该为无穷大，因其可当作一个不可数的无限多个幅度值的信源，需要无数个二进制数来表示，熵无穷实际问题中可以采用上式来定义连续信源的熵，因为常遇到的是求熵之间的差的问题，如互信息$$ I(X;Y)=H_c(X)-H_c(X|Y)=H_c(Y)-H_c(Y|X) $$性质相对性：连续信源的熵具有相对性，在取两熵肢健的差值时才具有信息的特性可加性$$ H_c(X,Y)=H_c(X)+H_c(Y|X)=H_c(Y)+H_c(X|Y) $$波形信源的熵定义平稳随机矢量的连续熵$$ H_c(\mathbf X)=H_c(X_1,X_2,\cdots,X_L)=-\int_\mathbf{R}p_X(\mathbf{x})\log p_X(\mathbf{x})\mathrm d x $$条件熵$$ H_c(\mathbf{Y|X})=H_c(Y_1,Y_2,\cdots,Y_L|X_1,X_2,\cdots,X_L)=-\int_{\mathbf R}\int_{\mathbf R}p_\mathbf{X}(\mathbf {x,y})\log p_\mathrm Y(\mathbf{y|x})\mathrm d \mathbf x \mathrm d \mathbf y $$限频限时的平稳随机过程（采样后）的熵$$ H_c(\mathbf X)=H_c(X_1,X_2,\cdots,X_L)=\sum_{l=1}^LH_c(X_l|X^{L-l})\leqslant H_c(X_1)+H_c(X_2)+\cdots+H_c(X_L) $$理解实际过程中信源的输入和输出都是幅值连续、时间或频率连续的波形，可以用两个平稳随机过程\(x(t)\)和\(y(t)\)来表示，而平稳随机过程可以通过采样变换成时间或频率上离散、幅值连续的平稳随机序列，因而平稳随机过程的熵可以理解为平稳随机序列的熵定义中的公式只有在平稳、各变量统计独立时成立最大熵定理限峰功率最大熵定理对于定义域为有限的随机变量\(X\)，当它满足均匀分布时，具有最大熵，该结论与离散信源在以等概率出现时达到最大熵的结论相似数学表示为当$$ p_X(x)=\left \{\begin {matrix} \frac 1 {b-a}, &a\leqslant x\leqslant b \\ 0, &其他 \end {matrix} \right. $$时，信源达到最大熵$$ H_c(X)=\log(b-a) $$限平均功率最大熵定理对于相关矩阵一定的随机变量X，当它满足正态分布时具有最大熵数学表示为当\(X\)满足概率分布$$ p_X(x)=\frac 1 {\sqrt{2\pi \sigma^2}} e^{\frac {-(x-m)^2}{2\sigma^2}} $$时连续熵可写作$$ H_c(X)=\frac 1 2 \log(2\pi e\sigma^2) $$仅与\(\sigma^2\)有关理解为当信源概率密度符合正态分布时，其连续熵仅与随机变量的方差\(\sigma^2\)有关，从物理意义上来说，方差\(\sigma^2\)表示信号的交流功率。因此在限制信号平均功率的条件下，正态分布的信源可以输出最大连续熵如上式所示，随平均功率增加而增加拓展：如果噪声满足正态分布，则噪声熵最大，因此高斯白噪声是最有害的干扰，因此在通信系统的各种设计中，都以高斯白噪声作为标准，不仅是为了简化分析，更是为了保证系统效果信息冗余度定义信息效率$$ \eta=\frac {H_\infty(X)} {H_m(X)} $$冗余度$$ \gamma = 1-\eta =1-\frac {H_\infty(X)} {H_m(X)} $$理解冗余度也叫多余度或剩余度，表示给定信源在实际发出信息时所包含的多余信息如果一个消息所包含的符号比表达这个消息所需要的符号多，那么这样的消息就存在冗余度信息效率表示不肯定性的程度，表示用能传送\(H_m(X)\)的手段取传送具有\(H_\infty (X)\)的信源的效率（这是一种很不经济的行为）冗余度则表示肯定性的程度，既然是肯定的，那就不能为我们提供有效的信息量，因此是多余的，其计算式为\(1-\eta\)，即多出来的我们不需要的部分的比重是测定\(m\)维分布后所能得到的信息，若所有维分布都能测定，即\(m=\infty\)，这一部分就无需再传送了，即对应了冗余度公式中的分子$$ H_O(X)-H_m(X)\geqslant 0 $$来源信源符号间得相关性：信源输出符号间的依赖关系使得信源熵减小，即信源的相关性。相关程度越大，信源熵越小，趋于极限熵；相关程度越小，实际熵就越大信源符号分布的不均匀性：由之前的推导可得，当信源符号等概率分布时信源熵最大，而在实际问题中更多的是不均匀分布，使得实际熵减小。当信源输出符号间彼此不存在依赖关系且为等概率分布时，信源实际熵将趋于最大熵\(H_0(X)\)应用当只知道信源符号有\(n\)个可能的取值，而对其概率特性一无所知时，可以通过假设\(n\)个取值等概而求出其熵的最大值$$ H_O(X)=\log n $$信源的编码和解码即压缩和恢复冗余度的过程，前者是为了让传输过程更加高效，后者是为了服务信宿，让信宿更好理解
第1章 绪论信息论的形成与发展产生背景原始通信方式：烽火通信、信鸽报信等技术准备从原始方式到电气表征、传输有线通信的发明：电报、电话、电码无线通信的发明需要解决的问题：如何远距离传输三极管的发明放大器放大电路理论准备核心问题：如何提高信道利用率滤波器的发明：频分复用采样定理的提出：时分复用信息测度：确定性观点体系产生核心问题：远距离传输中的噪声与抗干扰问题引入概率论，描述随机过程，研究随机信号对噪声的研究：S.O.Rice于1944-1945年发表的Mathemetical Analysis of Random Noise控制论观点：N.Wiener于1948年发表的Etrapolation, interpolation and smoothing of stationary times series信息论的最终产生：Shannon于1948年发表的A Mathematical Theory of communication技术发展核心问题：信源编码与信道编码的具体构造方法及保密通信问题的研究无失真信源编码：提高有效性信道编码：提高可靠性限失真信源编码保密编码：提高安全性（DES, EES, AES）未来发展网络信息论的兴起从双路通信，到多元接入信道，到广播信道，再到中继信道（解决高并发、高容量问题）MIMO技术在不增加带宽的前提下，成倍地提高系统的容量和频谱利用率协同通信在多用户通信环境中共享天线协同发送物理层安全途径密码学、物理层安全途径6G技术基于Shannon信息论及其扩展形式，探讨未来6G移动通信系统性能提升的潜能参考文献：[1]尤肖虎.Shannon信息论与未来6G技术潜能[J].中国科学:信息科学,2020,50(09):1377-1394.深度学习应用基于信息论，对数据进行特征提取，应用于深度学习人工智能领域参考文献：[1]李春晓.基于信息论的有监督特征选择算法研究.2022.吉林大学,MA thesis.信息论的研究内容狭义信息论主要研究信息测度、信道容量、信息率失真函数以及和他们相对应的香农三定理，信源编码，信道编码广义信息论研究所有与信息有关的领域，如心理学、遗传学、神经生理学、语言学、社会学等一般信息论主要研究信息传输和处理问题，是广义通信中客观存在的问题的理论提升通信系统模型框图模块作用信源向系统提供消息的人或机器，消息的“源头”信道传送物理信号的设施，消息的“传递通道”干扰源通信系统中干扰的集中反映，干扰的“源头”密钥源产生密钥的“源头”信宿接收消息的人或机器，消息的“归宿”评价指标可靠性有效性安全性信息论的应用领域生物学生物信息收集、基因测序、药物设计等医学把生命系统看作接收和传递信息的调节控制系统管理科学物流与信息流经济学经济学作用于信息领域用经济学的观点研究信息的一般问题信息论作用于经济学用信息科学的观点和方法重新认识和探讨经济活动的规律