电子科技大学计算机学院信息论与编码复习,内容主要来自于上课时的ppt,以及网上其他文章(后续均会列出)
第一章 概述
按照性质的不同可以把信息划分成语法信息、语义信息和语用信息三个基本类型
香农信息论主要讨论的是语法信息中的概率信息
通信系统基本模型:
第二章 离散信源熵
信息度量最常用的方法是统计度量,用事件统计发生概率的对数描述事物的不确定性,得到消息的信息量,建立熵的概念。
信源熵的物理含义
- 信源熵H(X)表示信源输出后,离散消息所提供的平均信息量
- 表示信源输出前,信源的平均不确定度
- 反映了变量X的随机性
信源熵的基本性质和定理
- 非负性
- 对称性
- 最大离散熵定理
- 扩展性
- 确定性
- 可加性
- 极值性
- 上凸性
第三章 无失真离散信源编码
信源编码:直接对发送信号进行变换或处理
- 目的:提高通信的有效性
- 实现:压缩信源的冗余度
无失真编码-------离散信源
限失真编码-------连续信源
离散无失真信源编码定理
- 定长编码定理:
- 变长编码定理:
香农编码
- 按信源符号的概率从大到小的顺序排队
- 求累加概率Pa(Xi)
- 求码长Ki,根据自信息量
- 将累加概率用二进制表示,取Ki个
费诺编码
- 按信源符号的概率从大到小的顺序排队
- 对概率按m(编码用的符号个数)进行分组,使每组概率和尽可能相等
- 给每个分组分配一个码元
- 对每个分组重复2、3步,直到不可分为止
赫夫曼编码
- 将信源符号按概率由大到小顺序排队
- 给两个概率最小的符号各分配一个码位,将其概率相加后合并作为一个新的符号,与剩下的符号一起,再重新排队
- 给缩减信源中概率最小的符号各分配一个码位
- 重复步骤2、3直至概率和为1
PS:
- 进行赫夫曼编码时,如果有几个符号概率相等,应使合并后的信源符号尽可能排在缩减信源序列的前面,以减少再次合并的次数,充分利用短码。
- 从后往前得到码字
- 用n进制编哈夫曼时,需确定第一步用几个数进行合并。
计算m+k(m-1)=x, 不用码字数s=x-n, 则取m-s个数进行合并
第四章 离散信道容量
互信息量的性质
- 对称性
- 当X和Y相互独立时,互信息为0
- 互信息量可为正值或负值
平均互信息量的物理意义
- 平均互信息量是收到Y前、后关于X的不确定度减少的量,即由Y获得的关于X的平均信息量
- 平均互信息量是发送X前、后,关于Y的平均不确定度减少的量
- 平均互信息量等于通信前、后,整个系统不确定度减少的量
平均互信息量的性质
- 对称性
- 非负性
- 极值性
凸函数性
- 是信源概率的上凸函数
- 是信道转移概率的下凸函数
信道容量定义
特殊离散信道的信道容量
无噪信道
- 具有一一对应关系的无噪信道:C=log n
- 具有扩展性能的无噪信道:C=log n
- 具有归并性能的无噪信道:C=log m
- 强对称离散信道的信道容量
- 对称离散信道的信道容量---行、列可排列
- 准对称离散信道的信道容量---行可排列
第五章 纠错编码---信道编码
作用:提高信息传输时的抗干扰能力
目的:增加信息传输的可靠性
手段:增加信息冗余度
差错控制系统模型及分类:前向纠错方式、反馈重传方式、混合纠错方式
信道编码定理:
线性分组码的基本参数:
当G 给定时,线性分组码有如下性质:
- 零向量θ=(0,0,⋯,0)一定是一个码字,称为零码字
- 任意两码字的和或差仍是一个码字---线性性
- 任意码字c是G的行向量g0,g1, ⋯, g(k-1)的线性组合---对称性
- 线性分组码的最小距离等于最小非零码字重量
生成矩阵与一致校验矩阵的关系:
系统码:
G和H的角色可以互换,即H作为生成矩阵,G为校验矩阵。由H生成的码字称为c的对偶码
伴随式纠错译码步骤:
- 计算伴随式,构造伴随式-差错图案表(s,e)
- 对接收向量计算伴随式s=eH^T
- 查(s,e)表得e
- 纠错:
循环码的生成多项式:若g(x)是一个(n-k)次多项式,且是(x^n-1)的因式,则由g(x)可以生成一个(n,k)循环码,g(x)称为该循环码的生成多项式
(n,k)循环码的构造:对(x^n-1)做因式分解,找出(n – k)次因式
一致校验多项式:x^n-1 = g(x)·h(x)
注意生成矩阵的行向量为g(x)系数的升幂排列时,对应的一致校验矩阵h(x)系数为降幂排列;如果G为降幂排列,则H为升幂排列
第七章 信息率失真函数
信息率失真函数(简称率失真函数)R(D)
性质
信源的最小平均失真度:
信源的最大平均失真度:
二元信源呈等概率分布时
n元信源呈等概率分布时
第九章 密码安全性的信息论测度方法
完善保密性---不能从密文中获得有关明文的信息(唯密文攻击)
完善保密性的必要条件:
唯一解距离---破译密码所需的最小密文长度
其中H0代表明文最大熵
唯一解距离是理论下界,达到唯一解距离不代表一定能破译密码
提高密码安全性的两条途径:
- 扩展密钥空间或加大密码算法复杂度,从而提高密钥熵
- 对明文压缩编码以减少信息冗余度
1 条评论
(☆ω☆)