哈夫曼编码平均码字长度_哈夫曼压缩算法

（机器学习）信息论与编码基础（总复习笔记）　　首先，老规矩：　　未经允许禁止转载(防止某些人乱转，转着转着就到蛮牛之类的地方去了) 　　B站:Heskey0 　　Part 1 公式　　第二章信息量与信息熵　　信息的特征是不确定性自信息量：度量某一事件，信源某一具体符号的不确定性
$I(x_i)=-\log p(x_i)$ 信息熵：信源的平均不确定度
$H(X)=E[I(X)]=-\sum_ip(x_i)\log p(x_i)$ 条件熵：已知 X 后，关于 Y 的平均不确定度
$H(Y|X)=-\sum_{ij}p(x_i,y_j)\log p(y_j|x_i)=\sum_ip(x_i)H(Y|x_i)$ 联合熵：表示 X 和 Y 同时发生的不确定度
H(X,Y)=H(X)+H(Y|X)\\
XY独立时，H(X,Y)=H(X)+H(Y)” eeimg=”1″>互信息量：已知某一条件 Y，使得对 X 的不确定度减少了。衡量条件 Y 提供了多少关于 X 的信息量　　
$I(x_i;y_j)=\log\frac{p(x_i|y_j)}{p(x_i)}=\log\frac{后验概率}{先验概率}$ 平均互信息量：平均意义上的互信息量　　
$I(X;Y)=\sum_{i,j}p(x_i,y_j)\log\frac{p(x_i|y_j)}{p(x_i)}$ 　　
　　不等关系：
$H(X|Y)\le H(X)$
$H(XY)\le H(X)+H(Y)$ 　　关系：

　　通信模型：信源：发出的信息量
H(X) 信道：信道中损失的信息量
H(X|Y) 信宿：接收端获得的信息量
I(X;Y) 　　衍生概念：
H(X|Y) ：疑义度，表示由于信道上存在干扰和噪声而损失掉的平均信息量
H(Y|X) ：噪声熵全损信道：干扰很大，难以从 Y 中提取 X 的有效信息，信源发出的所有信息都损失在信道中
例如：加密编码　　无损信道：没有干扰，接收端能完全收到信源发出的信息
　　第三章信道容量　　信道容量：信道所能传送的最大信息量　　
$C=\max_{p(x_i)}I(X;Y)$ 单位时间的信道容量：单位时间内信道所能传送的最大信息量　　
$C_t=\frac1t\max_{p(x_i)}I(X;Y)$ 对称DMC信道如果概率转移矩阵 P 的每一行都是第一行的置换(即包含相同素)，称该矩阵是输入对称的如果概率转移矩阵 P 的每一列都是第一列的置换(即包含相同素)，称该矩阵是输出对称的DMC信道：输入输出都对称的离散无记忆信道信道容量：　　
$C=\log m-H(Y|x_i)=\log m+\sum^m_{j=1}p_{ij}\log p_{ij}$
指转移矩阵的列数BSC信道（二进制对称DMC信道）信道容量：
$C=\log2-H(\epsilon,1-\epsilon)=1-H(\epsilon)$ 　　香农公式：计算 AWGN 信道的信道容量
$C=W\log(1+SNR)=W\log(1+\frac{P_S}{N_0W})$
：信道频带宽度，简称带宽，单位 Hz
SNR ：signal to noise ratio，信噪比，是信号功率（单位为W）与噪声功率（单位为W）的比值
P_S ：信号发射功率
N_0 ：高斯白噪声的单边功率谱密度　　提升信道容量的方式提升信道带宽提升信噪比提升发射功率降低信道噪声　　香农限：当带宽不受限制时，传送1比特信息，信噪比最低只需 -1.6dB 　　第五章信源编码　　目的：提升通信系统的有效性　　define:
: 输入编码器的信息位长度
: 进制数
K_L : 编码后的码字长度定长编码中，
K_L 是定值变长编码中，
$\bar{K}_L$ 是码字平均长度　　
$\mu$ : 编码前后的信息量比值平均码长
$\bar K$ : 每一个信息位用几位编码来表示
L=1 ，二进制的情况下，
$\bar K_L=\bar K$ 　　定长编码：无失真条件
$R\ge H(X)$ 输出信息率
$R=\frac{K_L}{L}\log m$ 编码效率
$\mu=\frac{H(X)}{R}$ 　　变长编码：无失真条件
$H(X)\le\bar R<H(X)+\frac{\log m}{L}$ 平均输出信息率
$\bar R=\frac{\bar K_L}{L}\log m$ 编码效率
$\mu=\frac{H(X)}{\bar R}$ 码字平均长度
$\bar K_L=\sum_ip(x_i)K_i$ 平均码长
$\bar K=\bar K_L/L$ 　　常见编码方法：哈夫曼编码，算数编码　　第六章信道编码　　信源编码目的：提高数字通信系统的有效性　　信道编码目的：提高数字通信系统的可靠性　　差错控制系统：前向纠错：发送端信息经过纠错编码后实行传送，而接收端通过独立的纠错编码，自动纠正传递过程的差错自动反馈重传：接收端若发现接收码字有错，则通过反向信道通知发送端重新发送该码字，如此反复，直到接收端认为接收正确为止混合纠错：前向纠错和反馈重传的结合，兼有检错和纠错两种能力　　有扰离散信道编码定理信道编码器的码率
$R\le$ 信道容量
时，一定存在一种信道编码方式可以实现无差错传输　　汉明距离：两个（相同长度）码字对应位不同的数量对两个码字进行异或云打算，并统计结果为1的个数　　汉明重量：码字对应于相同长度的零字符串的汉明距离，也就是码字中非零素的个数　　常见的信道编码方法：线性分组码汉明码循环码CRC校验码　　卷积码　　Part 2 理论　　第二章离散信源及其信息测度　　1. 自信息　　信息量的计算要带单位，是物理量，有物理意义一般采用以2为底的对数，常省略2不写　　单位与对数的底有关，底为2时，单位为比特自信息具有非负性事件发生前，描述该事件发生的的不确定性大小事件发生后，该事件所含有的信息量　　2. 信息熵　　熵函数的重要性质：可加性：
上凸性：
是概率分布
的严格上凸函数极值性：当且仅当符号概率都相等即
$p_i=\frac1n$ ，熵最大
$H(p_1,...p_n)\le H(\frac1n,...\frac1n)=\log n$ 　　信源输出前，描述信源的平均不确定性（自信息的数学期望）信源输出后，每个消息(符号)给出的平均信息量变量X随机性的大小变量X的最小描述复杂度　　3. 信源的分类　　离散无记忆信源：符号序列中生成每个符号的互相独立，且概率分布相同符号序列中前后符号的出现彼此无关　　离散有记忆信源：符号序列中生成每个符号之间存在依赖关系　　扩展信源：多符号信源例如
N次扩展信源
X^N ：把N个符号组成的N长序列看做一个整体
$\alpha$ 　　平均符号熵：
$H_N(\vec X)=\frac1NH(X_1X_2...X_N)$ 　　N次扩展信源
X^N 的熵：
　　离散平稳信源：不同时刻消息的概率分布相同　　N维平稳信源：N次扩展信源+离散平稳信源　　N维平稳必然N-1维平稳　　离散平稳有记忆信源，考虑记忆长度无穷，则平稳信源极限熵（熵率）：
$H_\infin=\lim_{N\rightarrow\infin}H_N(\vec X)=\lim_{N\rightarrow\infin}H(X_N|X_1...X_{N-1})$ 　　极限熵的求法：条件熵平稳有限记忆长度为m+1的信源（ m+1 维平稳信源）极限熵，就等于m阶的条件熵
$H_\infin=H(X_{m+1}|X_1...X_m)=H_{m+1}$ 式子中
m+1 为记忆长度如：二维平稳信源(极限)熵：
如：三维平稳信源(极限)熵：
　　4. 马尔可夫信源　　M阶马尔可夫信源定义：一类非平稳离散有记忆信源在某一时刻发出某一符号的概率，只与此前发出的m个符号有关（用条件概率表示，条件长度为m）熵
$H_{m+1}=H(X_{m+1}|X_1X_2...X_m)$ 　　状态转移：k步转移概率：
$p^{(k)}_{ij}=P\{X_{m+k}=j|X_m=i\}$ 转移概率（条件概率）与起始时刻
，转移的步数
以及所处的状态
和
都有关　　时齐(齐次)马尔可夫链：时齐马尔可夫链的状态转移概率与时刻无关（平稳转移概率）齐次马氏链可以用转移概率矩阵来描述。　　
\begin{bmatrix}
0.65 & 0.28 & 0.07 \\
0.15 & 0.67 & 0.18 \\
0.12 & 0.36 & 0.52

\end{bmatrix}
\end{gathered}” eeimg=”1″>矩阵中每个素非负，并且每一行之和为1。　　各态历经性：对于时齐，有限状态的马氏链，若存在正整数，使转移矩阵
$P^{(r)}$ 中任意素都大于0 ，则马氏链具有遍历性（各态历经性），即存在　　
$\lim_{n\rightarrow\infin}p_{ij}^{(n)}=W_j$ 　　极限分布/稳态分布：向量
$W=[W_1\quad W_2...\quad W_J]$
WP=W 若转移概率矩阵或其矩阵乘积，每个素都大于0，则稳态分布存在计算极限分布之前，一定要先验证其极限分布存在
$m\ne1$ 时，状态的稳态分布和符号的稳态分布不同符号稳态分布：通过状态稳态分布
，符号条件矩阵
$P_{X|S}$ 计算
$P_a=WP_{a|S}$ 　　求状态极限分布：解线性方程组　　
W_1+W_2+…+W_j=1″ eeimg=”1″> 　　马尔可夫信源的熵：可以用平稳信源的熵性质计算　　
H_\infin=H_{m+1}&=H(X_{m+1}|X_1X_2…X_m)\\
&=H(X_{m+1}|S)\\
&=\sum_ip(s_i)H(X|s_i)
\end{aligned}” eeimg=”1″>极限熵计算使用符号条件概率矩阵，而不是状态转移矩阵　　总结：对于时齐马尔可夫链来说，一步转移概率完全决定了k步转移概率。转移概率仅仅是条件概率，不包含初始概率分布。由初始分布及各时刻的一步转移概率才能完整描述马尔可夫链的统计特性。由初始分布及一步转移概率就能完整描述齐次马尔可夫链的统计特性。　　对同一信源，采用不同的模型计算得到的熵的关系为：　　
$H_0\ge H_1\ge...\ge H_\infin$ 　　信源的剩余度：存在剩余度的原因是分布不等概
$R=1-\frac{H_\infin}{H_0}$ 其中
H_0 为等概分布的熵，即
$\log n$ 　　熵的相对率：
$\mu=\frac{H_\infin}{H_0}$ 　　第三章离散信道及其信道容量　　1. 离散信道　　随机干扰：存在于输入和输出之间的关系　　信道传递概率：用
$P(\vec Y|\vec X)$ 表示离散无记忆信道（DMC），满足
$p(\vec Y|\vec X)=\prod_{n=1}^Np(Y_n|X_n)$
离散无记忆恒参（平稳）信道，满足
一般，不加说明，离散无记忆信道都看做是离散无记忆恒参信道因此，离散无记忆信道的研究只需研究单个符号的传输即可，所以也叫单符号离散信道　　单符号离散信道：信道转移概率：
可以用信道矩阵
表示，
，
　　2. 平均互信息　　信道疑义度：表示接收端收到信道输出的一个符号之后对信道输入的符号仍然存在的平均不确定性。
$H(X|Y)=\sum_jp(y_j)H(X|y_j)=-\sum_{i}\sum_{j}p(x_iy_j)\log p(x_i|y_j)$ 其中
表示接收输出符号
y_j 后关于
的后验熵　　互信息量：收到
y_j 后的关于发送符号
x_i 的信息量
$I(x_i;y_j)=I(x_i)-I(x_i|y_j)=\log\frac{p(x_i|y_j)}{p(x_i)}=\log\frac{后验概率}{先验概率}$
表示事件
y_j 出现后关于事件
x_i 的不确定性减少的量
表示事件
y_j 出现后关于事件
x_i 仍然存在的信息量事件
y_j 出现以后信宿获得的关于事件
x_i 的信息量　　互信息量的性质：互易性：
可为0（
x_j,y_j 相互独立），可正可负任何两个事件之间的互信息不可能大于其中任一事件的自信息
I(x_i;y_j)\le I(y_i)” eeimg=”1″> 　　平均互信息：互信息
在联合概率空间
P(XY) 中的统计平均值
I(X;Y)&=E[I(x_i;y_j)]\\
&=H(X)-H(X|Y)\\
&=H(Y)-H(Y|X)\\
&=H(X)+H(Y)-H(XY)
\end{aligned}” eeimg=”1″>表示接收到Y以后，平均每个符号获得的关于输入变量X的信息量，是信道实际传输信息的数量（从
获得的关于
的平均信息量）
H(X) 是信源输出的信息量，而真正被接收者收到的信息量则是
I(X;Y) 　　维拉图：可以用图判断公式对不对
等价于
$\cup$
　　
等价于
$\cap$
　　
等价于

　　平均互信息的性质：非负性互易性是信源概率分布
P(X) 的上凸函数极值性
H(X;Y)\le H(Y)” eeimg=”1″> 　　一：平均互信息的计算：
H(X;Y) 先求概率分布（矩阵）：条件分布
$P_{Y|X}$ 和边缘分布
$P_{Y}=P_XP_{Y|X}$ 求联合概率：
矩阵中素相乘
$H(Y|X)=\sum p(x_i,y_j)\log p(y_j|x_i)$
　　3. 信道容量　　信息传输率：
信道中平均每个符号所传送的信息量。
　　信道容量：
最大的信息传输率
$C=\max\{I(X;Y)\}$ ，相应的输入概率分布被称为最佳输入分布与信源的概率分布无关，是完全描述信道特性的参量是信道能够传输的最大信息量　　求解信道容量：无噪无损信道无噪无损信道矩阵为单位阵（r=s）
得
则
$C=\max_{p(x)}H(X)=\log r=\log s$ 　　有噪无损信道
$C=\log r$ ，最佳输入：等概分布　　无噪有损信道
$C=\log s$ ，最佳输入：不唯一，使输出等概分布　　无记忆扩展信道：输入和输出是一个随机变量序列每一个随机变量均取值于同一输入或输出符号集　　4. 对称信道　　离散输入对称信道：信道矩阵每一行都是相同素的排列组合　　离散输出对称信道：信道矩阵每一列都是相同素的排列　　对称信道：输入对称+输出对称　　准对称信道：信道矩阵可以按列分为一些对称的子阵划分子集只有一个时，就是对称信道　　准对称信道和对称信道容量的最佳输入分布都是等概分布。　　5. 信道组合　　级联信道：串联信道一：
P(Y|X) ，输入
，输出
信道二：
P(Z|XY) ，输入
，输出

$I(XY;Z)\ge I(Y;Z)$ 一般来说，串联信道中，随机变量序列（ XYZ ）可构成马氏链，即， Z与X没有直接的依赖关系
$I(X;Z)\le I(X;Y)$ ：信息不增（一般总是丢失信息的）　　信源与信道匹配：当信源与信道连接时，若信息传输率达到了信道容量，则称此信源与信道达到匹配。否则，认为信道有剩余　　信道的剩余度：
　　第四章波形信源和波形信道　　1. 连续信源熵　　微分熵：也叫差熵，可以为负
$h(X)=-\int_a^bp(x)\log p(x)dx$ 　　最大熵：即输出幅度受限的情况下，服从均匀分布的随机变量具有最大熵对于平均功率受限的连续随机变量，当服从高斯分布时具有最大熵　　熵功率：设限定的平均功率为P，某连续信源的实际熵为h(X)，则与它具有相同熵的高斯信源的平均功率被定义为熵功率
$\bar P=\frac1{2\pi e}e^{2h(X)}$ 　　剩余度：平均功率和熵功率之差
$P-\bar P$ 　　2. 香农公式　　会用公式算就行　　对于连续信源，当幅度（峰值功率）受限时，均匀分布具有最大熵；当平均功率受限时，高斯分布具有最大熵　　编码：多做几个题就行　　第五章无失真信源编码　　1. 码的分类　　信源符号集：
$S=\{s_1,s_2,...,s_q\}$ 　　码字：编码器的输出　　码符号集：用来组成码字的符号的集　　定长码：码字等长　　分组码：信源符号集和码符号集为一对一或多对一（不能一对多），分类：非奇异码：信源符号和码字一一对应，不一定是唯一可译码奇异码：信源符号和码字不是一一对应，一定不是唯一可译码　　信源编码目的：提高数字通信系统的有效性　　信道编码目的：提高数字通信系统的可靠性　　唯一可译码：任意一串有限长的码符号序列只能被唯一地译为对应的信源符号序列（看PPT的例子）唯一可译码的充要条件：编码的任意次扩展均为非奇异码定长非奇异码一定是唯一可译码，但非充要条件（有可能是非定长即时码）　　唯一可译码可分为两类：即时码：某个唯一可译码在接收到一个完整的码字时无需参考后续的码符号就能立即译码充要条件：码组中任一码字都不是其它码字的前缀　　非即时码　　平均码长：假设信源的分布：
$s_i\sim p(s_i)$ ，码字对应长度
则平均码长：
$\bar L=\sum_{i=1}^qp(s_i)l_i$ 　　紧致码/最佳码：平均码长最小的唯一可译码　　2. 定长编码定理　　定理1：如果对
次扩展信源
S^N 进行定长编码，要满足非奇异性，需满足
$q^N\le r^l$ 　　定长信源编码定理：设离散平稳无记忆信源的熵为H(S), 若对N次扩展信源进行
定长编码(r个编码符号)，则对于任意
0″ eeimg=”1″>，只要满足　　
$\frac{l}{N}\ge\frac{H(S)+\epsilon}{\log r}$ 　　则当N足够大时，可实现几乎无失真编码，即译码错误概率
P_E 为任意小　　反之，如果：　　
$\frac{l}{N}\le\frac{H(S)-2\epsilon}{\log r}$ 　　则不可能实现无失真编码，当N足够大时，译码错误概率
P_E 为1 　　3. 变长码　　设：信源符号集
$S=\{s_1,s_2,...,s_1\}$ 码符号集
$X=\{x_1,x_2,...x_r\}$ 码字
$C=\{W_1,W_2,...,W_q\}$ 其码长分别为
　　Kraft不等式：即时码、唯一可译码存在的充分必要条件　　
$\sum^q_{i=1}r^{-l_i}\le1$ 注意:该定理可以作为判断一种码不是即时码（或唯一可译码）的判断依据。该定理不能作为判断一种码是即时码（或唯一可译码）的判断依据　　唯一可译码判别准则：看PPT或者B站搜　　编码信息率：R 　　
$R=\frac{H(S)}{\bar L}$ 　　香农第一定理：　　对扩展信源
S^N 编码，总可找到一种无失真信源编码，构成唯一可译码，使其平均码长满足：　　
$\frac{H(S)}{\log r}\le \frac{\bar L_N}{N}<\frac{H(S)}{\log r}+\frac1N$ 编码下界记作：
$H_r(S)=\frac{H(S)}{\log r}$ 　　编码效率：　　
$\eta=\frac R{\log r}$ 　　Huffman码：哈夫曼码的构造过程建议看B站/PPT 　　第六章有噪信道编码　　信道编码：按照一定的规则给信源编码后的码符号序列增加一些冗余信息，使其变成具有一定数学规律的码符号序列　　信道译码：接收到码符号序列后，按照与信道编码器相同的数学规律，去掉符号序列中的冗余符号　　1. 译码规则/错误概率　　设：输入符号集
$X=\{x_1,x_2,...,x_r\}$ 输出符号集
$Y=\{y_1,y_2,...,y_s\}$ 　　译码规则：函数
F(y_j) ，输出为
x_i 　　错误概率：设译码规则为
$F(y_j)=x_i^\star$ 当输入符号是
$x_i^\star$ 时，译码正确正确译码的概率：
$p[F(y_j)|y_j]=p(x_i^\star|y_j)$ 平均正确译码概率：　　
$\bar P_E=\sum^S_{j=1}p(x^\star y_j)$ 当输入符号是除
$x_i^\star$ 以外的
(r-1) 种符号时，译码错误错误译码的概率　　
p(e|y_j)&=\sum_{k\ne i}p(x_k|y_j)\\
&=1-p(x_i^\star|y_j)=1-p[F(y_j)|y_j]
\end{aligned}” eeimg=”1″>平均错误译码概率：
$P_E=\sum^S_{j=1}p(y_j)p(e|y_j)=1-\sum^S_{j=1}p(x_i^\star y_j)$ 　　错误概率的影响因素：信道统计特性：信源概率分布和信道转移概率分布译码准则：
$F(y_j)=x_i^\star$ ，这里
$x^\star$ 即目标
x_i 　　常用的两个重要译码规则：最大后验概率规则(最佳译码准则，也称最小错误概率译码准则)-MAP令，
$F(y_j)=x^\star$ ，若
$p(x^\star|y_j)\ge p(x_i|y_j)$ ，即
$p(x^\star y_j)\ge p(x_iy_j)$ 则译码规则为MAP准则
$P_E=1-\sum_{Y,X^\star}p(x_iy_j)=1-\sum_{Y,X^\star}p(x_i)p(y_j|x_i)$ 具体使用：看PPT，有例题，懒得抄取
$P_{XY}$ 的每一列的最大，加起来
$\sum$ 之后得到
$P_E=1-\sum$ 　　极大似然译码规则-ML在MAP的基础上，输入符号等概分布，则
$p(y_j|x^\star)\ge p(y_j|x_i)$
$P_E=1-\frac1r\sum_{Y,X^\star} p(y_j|x_i)$ 具体使用：看PPT，懒得抄取信道矩阵
$P_{Y|X}$ 的每一列的最大，加起来
$\sum$ 之后得到
$P_E=1-\sum$ 　　Fano不等式：说明了信道疑义度和
P_E 之间的关系　　
$H(X|Y)\le H(P_E)+P_E\log(r-1)$ 其中
H(X|Y) 是信道疑义度PPT上有一个Fano不等式的图像　　Fano不等式的物理意义：当信源、信道给定，信道疑义度就给定了译码错误概率的下限　　2. 编码方法　　加强输入符号序列间的相关性，降低信道疑义度
H(X|Y) ，从而给
P_E 减小创造前提　　汉明距离：设两个长度为
的码符号序列：
$a_i=x_{i_1}x_{i_2}...x_{i_n}$
$\beta_j=y_{i_1}y_{i_2}...y_{i_n}$ 　　它们之间的汉明距离：（异或运算：同0异1）
$D(\alpha_i,\beta_j)=\sum_{k=1}^nx_{i_k}\oplus y_{j_k}$ 　　性质：非负性对称性三角不等式　　最小汉明距离：在二码C中，任意两个码字之间的汉明距离的最小值　　最小汉明译码准则-MD：最大似然译码准则用汉明距离的概念可表述为：收到
$\beta_j$ 后译成与之距离最小的输入码符号序列
$\alpha^\star$ 汉明距离越小表示两个码符号序列越相似，这就是“最大似然”的含意　　3. 有噪信道编码定理　　联合
$\epsilon$ 典型序列：联合
$\epsilon$ 典型序列是那些平均联合自信息以
$\epsilon$ 任意小地接近联合熵的
长序列对的集合　　联合渐进等分割性：　　香农第二定理：设有一离散无记忆平稳信道，其信道容量为
，只要信道编码信息率
R<C ，当码长
足够大时，则至少存在一种编码，使译码错误概率任意小香农第二定理指出了“高效率、高可靠性”的信道编码存在性，（1）“高效率”的含义是信息传输率接近信道容量;（2）“高可靠性” 的含义是译码差错任意小;（3）存在这种信道编码的必要条件是
R<C 　　只要码率小于信道容量，一个离散无记忆平稳信道的错误概率便可以做到想多小就多小　　第七章限失真信源编码　　失真函数：非负函数
失真矩阵：
　　函数形式可根据需要定义常用失真函数有：见PPT汉明失真平方误差失真绝对失真相对失真　　定量描述发出符号与接收符号之间的差异（失真）　　平均失真度：
$D=\sum_{i=1}^n\sum_{j=1}^mp(x_iy_j)d(x_i,y_j)$ 　　矢量传输的失真度：设输入N长符号序列
$\alpha=X_1X_2...X_N$ 输出N长符号序列
$\beta=Y_1Y_2...Y_N$ 则失真函数：
$d(\alpha,\beta)=\sum^N_{i=1}d(X_i,Y_i)$ N长信源序列的平均失真度
$D_N=\frac1ND(N)$ 设信源序列第
个分量的平均失真度：
D_i 则如果是平稳信源：
当信源和信道均为无记忆时
$D(N)=\sum^N_{i=1}D_i$ 　　保真度准则：设预先规定的平均失真度为
$D^\star$ ，压缩后的失真度为
保真度准则：
$D\le D^\star$
$D^\star$ 允许的试验信道：满足保真度准则的所有信道　　率失真函数：性质：
R(D) 是关于
的下凸函数在定义区间是严格递减函数　　香农第三定理：只要满足
R(D)” eeimg=”1″>当信源序列长度N足够大时，一定存在一种编码方法，使译码失真
$\le D+\epsilon$ ，其中
$\epsilon$ 是任意小的正数　　第九章纠错编码　　1. 基本概念　　反馈重传（ARQ）：发送端经编码后发出能够发现错误的码，接收端收到后经检验，如果发现传输中有错误，则通过反馈系统把这一判断结果反馈回发端，然后发送端把前面发出的信息重新传送一次，直到接收端认为正确地收到信息为止　　前向纠错（FEC）：发送端发出的是具有纠错能力的纠错码，接收端根据译码规则进行译码。当误码个数在码的纠错能力范围内时，译码器可以自动纠正错误特点：无需反馈延迟小，实时性好　　混合纠错（HEC）：错误不严重时，自动纠错错误严重时，反馈重传　　纠错码分类：看PPT按功能分检错码：仅能检测误码纠错码：可纠正误码纠删码　　按信息码与监督码之间的检验关系分：线性码：满足线性关系，满足一组线性方程非线性码　　按信息码与监督码之间的约束方式不同分：分组码：本码组的监督码仅和本码组的信息相关卷积码　　按信息码在编码后是否保持原形式不变：系统码：信息码与监督码在分组内有确定位置，编码后的信息码保持不变非系统码：信息位打乱，与编码前不同　　2. 线性分组码　　(n,k)分组码：信息码组由
个信息码组成，共有
2^k 个不同的信息码组, 即能表示
2^k 个消息, 即码字的数目共有
2^k ，这
2^k 个码字的集合称为 (n,k) 分组码编码器输出长度为
的码字附加了
r=n-k 个校验码　　线性分组码分类：汉明码循环码BCH码，RS码等　　线性分组码一定满足封闭性：线性分组码中任意两个码字之和仍然是该码的码字　　校验矩阵，生成矩阵：以(7,3)线性分组码为例码字为
其中
为信息，
为校验校验可由下面方程组计算得到：
c_5=c_1+c_2+c_3\\
c_6=c_1+c_2\\
c_7=c_2+c_3″ eeimg=”1″>即（因为二进制没有-，
，所以
c_4 前没有负号）
c_1+c_2+c_3+c_5=0\\
c_1+c_2+c_6=0\\
c_2+c_3+c_7=0″ eeimg=”1″> 　　校验矩阵/监督矩阵：
$H=[Q\quad I]$ 上面方程组对应的矩阵（有几个校验位，校验矩阵就有几行）（
为单位矩阵）
\begin{array}{1}
1&0&1&1&0&0&0\\
1&1&1&0&1&0&0\\
1&1&0&0&0&1&0\\
0&1&1&0&0&0&1
\end{array}
\right]” eeimg=”1″>对(n,k)线性分组码，校验矩阵为
$(n-k)\times n$ 维矩阵生成矩阵：
$G=[I\quad P]$ ( 信息位在前，校验位在后 )（
为单位矩阵）在上面方程组的基础上增加：
c_1=c_1 ，
c_2=c_2 ，
c_3=c_3
\left[
\begin{array}{1}
1&0&0&1&1&1&0\\
0&1&0&0&1&1&1\\
0&0&1&1&1&0&1
\end{array}
\right]” eeimg=”1″>生成矩阵为
$k\times n$ 维　　监督矩阵和生成矩阵的关系：
HG^T=0 线性系统码的
和
之间可以直接互换：
Q=P^T （
$H=[Q\quad I]$ ，
$G=[I\quad P]$ ）　　线性分组码的伴随式：又称监督子、校验子伴随接收码字的n-k维向量，反映“信道对码字造成的干扰”设发送码字为
，接收到的码序列为
，令伴随式
S=YH^T 或

S=0 时，说明
是一个码字，传输过程没有产生误码　　对于已给线性分组码，一个伴随式对应一种错误图样，即可纠正对应的错误。则n-k位的伴随式有
$2^{n-k}$ 种，其与可纠正错误数目u的关系纠错步骤：确定校验矩阵
求解伴随式：
根据伴随式，推断出错码位置，求解错误图样
纠错
Y+E=C 　　完备码：　　
$2^{n-k}\ge\sum^u_{i=0}C^i_n$ 伴随式个数与错误图样个数相同的码，被称为完备码上式等号成立则为完备码　　线性分组码最小汉明距离的判定方法1设
$d_{min}$ 为线性分组码的最小汉明距离该码具备纠正
个以内错误的充分必要条件是
$d_{min}=2u+1$ ，看PPT上的图该码具备检测
个以内错误的充分必要条件是
$d_{min}=l+1$ 该码具备纠正
个错误，同时可以发现
t)” eeimg=”1″> 个错误的充分必要条件是
$d_{min}=t+l+1$ 　　线性分组码最小汉明距离的判定方法2若H中的任意 t 列线性无关，而存在 t +1 列线性相关，则该码的最小汉明距离
$d_{min}$ 为
t +1 　　3. 汉明码　　汉明码：是一种能够纠正单个错误的线性分组码最小码距：
$d_{min}=3$ 设监督码共有
位，则汉明码长必为
n=2^r-1 设计汉明码：看PPT例题：设计一个r=4的汉明码　　4. 循环码　　循环码：循环码除了具有线性分组码的一般性质外，还具有循环性：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组　　码多项式：设循环码码字
$C=[c_1\, c_2\,...\, c_n]$ 则码多项式：
$C(x)=c_1x^{n-1}+c_2x^{n-2}...+c_n$ （ x仅是码位置的标记，并无取值的含义）　　生成多项式：从码中取出一个前面
k-1 位都是0的码字，定义这个码字的码多项式为生成多项式
g(x) （该多项式的次数为
n-k ，即监督码的位数）所有码多项式必定为
g(x) 的倍式为了保证构成的生成矩阵G的各行线性不相关，通常用
g(x) 来构造生成矩阵：
\begin{array}{1}
x^{k-1}g(x)\\
x^{k-2}g(x)\\
…\\
g(x)
\end{array}
\right]” eeimg=”1″>例如 (7,3) 循环码

\begin{array}{1}
x^2g(x)\\
xg(x)\\
g(x)
\end{array}
\right]
=\left[
\begin{array}{1}
x^6+x^4+x^2\\
x^5+x^3+x\\
x^4+x^2+1
\end{array}
\right]
=\left[
\begin{array}{1}
1&0&1&0&1&0&0\\
0&1&0&1&0&1&0\\
0&0&1&0&1&0&1
\end{array}
\right]” eeimg=”1″>生成多项式直接构造的生成矩阵，对应的码一定不是系统码　　系统循环码的编码方法：用
$x^{n-k}$ 乘信息多项式
m(x) （把信息码左移
n-k 位，即附加
n-k 个0）求
r(x) ：化简
$\frac{m(x)x^{n-k}}{g(x)}$ ，余式为监督多项式/监督位
r(x) 系统码：
$C(x)=m(x)x^{n-k}+r(x)$ 看一下PPT上例题9.5。系统循环码生成多项式的一般表示形式为
G=[I|P] 　　得到系统循环码的生成矩阵有两种方法：先求监督位用典型生成阵的信息位所对应多项式左移n-k位，对生成多项式除法求余，得到相应监督多项式（监督位），继而得到生成矩阵　　先求非系统码的生成矩阵：根据生成多项式和循环码的定义，得到非系统码的生成矩阵，然后对该矩阵进行初等变换，变成系统码的生成矩阵　　Part 3 计算题　　记公式：用维拉图　　第二章　　符号等概分布时，
H(X) 熵最大为
$\log n$ 　　马尔可夫信源的极限熵的计算：
$H_\infin=H_{m+1}$ 　　二阶马尔可夫信源的符号稳态分布和状态稳态分布第二章作业：补充题　　第三章　　互信息量：
$I(x_i;y_j)=\log\frac{p(x_i|y_j)}{p(x_i)}$ 　　平均互信息的计算：
I(X;Y) 先求概率分布（矩阵）：条件分布
$P_{Y|X}$ 和边缘分布
$P_{Y}=P_XP_{Y|X}$ 求联合概率：
矩阵中素相乘
$H(Y|X)=-\sum p(x_i,y_j)\log p(y_j|x_i)$
第三章例题3.4 　　信道容量的计算：
$C=\max I(X;Y)$ 对称信道的信道容量设输入等概分布
P_X 求
I(X;Y) 　　第四章　　香农公式：计算 AWGN 信道的信道容量　　
$C=W\log(1+SNR)=W\log(1+\frac{P_S}{P_N})$
：信道频带宽度，简称带宽，单位 Hz
SNR ：signal to noise ratio，信噪比，是信号功率（单位为W）与噪声功率（单位为W）的比值
P_S ：信号发射功率
N_0 ：高斯白噪声的单边功率谱密度　　香农公式的计算：例如题目给出信噪比为20dB
$SNR=10\lg\frac{P_S}{P_N}=20$ 解得
　　代香农公式　　第六章　　MAP译码准则（最大后验概率准则）取
$P_{XY}$ 的每一列的最大，加起来
$\sum$ 之后得到
$P_E=1-\sum$ 　　ML译码准则取信道矩阵
$P_{Y|X}$ 的每一列的最大，加起来
$\sum$ 之后得到
$P_E=1-\sum$ 　　最小汉明距离译码：码能够纠正几位码的错误：

d=2u+1 其中
为最小汉明距离　　第九章　　求系统码的码字：算n, k用
$x^{n-k}$ 乘信息多项式
m(x) （把信息码左移
n-k 位，即附加
n-k 个0）求
r(x) ：化简
$\frac{m(x)x^{n-k}}{g(x)}$ ，余式为监督多项式/监督位
r(x) 系统码：
$C(x)=m(x)x^{n-k}+r(x)$ 　　判断是否是误码：由
g(x) 写出
$G=[I\, P]$ 注意要补
k-1 个0
进行初等行变换，将左边化成单位矩阵　　
$H=[Q\, I]=[P^T\, I]$
判断
是否是零向量（如果结果是零向量，就没有出错）　　Part 4 测试　　看着名词，回想起概念：　　第一章消息/信号/信息的区别　　第二章自信息/信息熵的物理意义/性质，N维平稳信源，扩展信源的熵，马尔科夫链的熵，时齐马尔科夫链，遍历性，二阶马尔可夫信源的符号稳态分布/状态稳态分布，信源存在剩余度的原因　　第三章信道疑义度，互信息量的物理意义，互信息量的性质，平均互信息量的物理意义，平均互信息的性质，维拉图，信道容量，信息传输率，配对，信道剩余度，BSC信道的信道容量，对称信道　　第五章：信源/信道编码的目的，非奇异码，唯一可译码，平均码长，定长信源编码定理，Kraft不等式，编码信息率，编码效率，香农第一定理　　第六章：译码规则，（平均）错误译码概率，MAP准则，ML准则，Fano不等式物理意义，汉明距离，最小汉明译码准则，联合渐进等分割性，香农第二定理　　第七章：失真函数，失真矩阵，平均失真度，保真度准则，率失真函数的性质，香农第三定理　　第九章：反馈重传，前向纠错，混合纠错，(n,k)分组码，线性分组码的分类，封闭性，校验矩阵/生成矩阵的关系，伴随式，纠错步骤，完备码，线性分组码最小汉明距离的判定方法，设计一个r=4的汉明码循环码，码多项式，生成多项式，系统循环码的编码方法，判断是否是误码本文使用 Zhihu On VSCode 创作并发布

哈夫曼编码平均码字长度_哈夫曼压缩算法

相关推荐