信息论与编码复习总结
I (xi y j ) log p(xi y j )
• 注意: • 当 xi,yj 相互独立时,有 p(xiyj)=p(xi)p(yj),那么就有 I(xiyj)=I(xi)+I(yj)。 • xiyj 所包含的不确定度在数值上也等于它们的自信息量。 条件自信息量 在事件 yj 出现的条件下,随机事件 xi 发生的条件概率为 p(xi | yj) ,则它的条件自信息量定 义为条件概率对数的负值:
X P
x1 p(x1
)
x2 p(x2 )
xn p(xn )
如果知道事件 xi 已发生,则该事件所含有的信息量定义为: I (xi ) log p(xi )
I (xi) 含义: – 当事件 xi 发生以前,表示事件 xi 发生的不确定性 – 当事件 xi 发生以后,表示事件 xi 所含有的信息量
简答题: 一、 信源编码与信道编码的区别
答:信源编码是压缩信源发出的信息的冗余度,是为了提高信息传输的有效性;而信 道编码是在信源编码器输出的代码组上有目的地增加了一些监督码元,增大了信息的 冗余度,以提高传输信息的可靠性。 二、 能否将三种码(信源编码、信道编码、密码)合成一种码进行编译?
答:提高有效性必须去掉信源符号中的冗余部分,此时信道误码会使接收端不能恢复原 来的信息,也就是必须相应提高传送的可靠性,不然会使通信质量下降;
ij
p(xi , y j ) log p(xi , y j )
ij
联合熵 H(X,Y)表示 X 和 Y 同时发生的不确定度。 H(XY)与 H(X)、H(X/Y)之间的关系 H(X,Y)=H(X)+H(Y|X) H(X,Y)=H(Y)+H(X|Y)
单符号序列 马尔科夫信源,m 阶马尔科夫信源(了解)
条件熵 H(x|y)、H(x|Y)
在给定 yj 条件下,xi 的条件自信息量为 I(xi| yj), X 集合的条件熵 H(X|yj)为
H ( X | y j ) p(xi | y j )I (xi | y j )
i
在给定 Y(即各个 yj )条件下,X 集合的条件熵 H(X|Y)
H ( X | Y ) p( y j )H ( X | y j ) p( y j )p(xi | y j )I (xi | y j )
信息论与编码理论复习资料
By 疯狂阿德
第一章 绪论
考点: 信息、消息、信号的区别 通信系统模型 香农 1. 信息、消息、信号的区别
信息:指事物运动的状态或存在方式的不确定性的描述。 消息:包含信息的语言、文字、图像等。 信号:信息的物理体现。 在通信系统中,实际传输的是信号,但实质内容是信息,信息包含在信号中,信号是信息 的载体,通信的结果是消除或部分消除不确定性,从而获得信息。 2. 通信系统模型
– 信源的基本特性:具有随机不确定性。 香农信息论的基本点: 一、用随机变量和随机矢量来表示信源;
二、用概率论和随机过程来研究信息。 信源的分类:
连续信源:指发出在时间和幅度上都是连续的消息(模拟消息)的信源。 离散信源:指发出在时间和幅度上都是离散分布的离散消息的信源。
离散无记忆信源:所发出的各个符号是相互独立的,发出的符号序列中的各个符号之间没 有统计关联性,各个符号的出现概率是它自身的先验概率。
发出符号信源的有记忆信源:用信源发出的一个符号序列的整体概率(即联合概率)反映有 记忆信源的特征
发出符号序列的马尔可夫信源:一个符号出现的概率只与前面一个或有限个符号有关,而不 依赖更前面的那些符号
不确定度 定义:随机事件的不确定度在数量上等于它的自信息量。 两者的单位相同,但含义却不相同。 具有某种概率分布的随机事件不管发生与否,都存在不确定度,不确定度表征了该事件的特性, 而自信息量是在该事件发生后给予观察者的信息量。
马尔科夫信源:一类相对简单的离散平稳信源,该信源在某一时刻发出字母的概率除与该 信源有关外,只与此前发出的有限个字母有关。
m 阶马尔科夫信源:信源输出的某一符号的概率只与以前的 m 个符号有关,而与更前面的 符号无关。 马氏链的基本概念 一阶马尔科夫信源:
p(x1, x2 , x3, xL ) p(x1) p(x2 | x1) p(xL1 | xL2 ) p(xL | xL1)
ij
p(xi , y j ) log p( y j | xi )
ij
联合熵 H(X,Y) H(X,Y)=H(X)+H(Y|X)
联合熵是联合符号集合(X,Y)上的每个元素对(xi,yj)的自信息量的概率加权统计平均值。
H ( X ,Y ) p(xi , y j )I (xi , y j )
• 若把有限个字母记作一个状态 S,则信源发出某一字母的概率除与该字母有关外, 只与该时刻信源所处的状态有关。
• 信源将来的状态及其送出的字母将只与信源现在的状态有关,而与信源过去的状 态无关。
• 令 si = (xi1, xi2, …xim) xi1,,xi2, …xim ∈(a1, a2, …an) • 状态集 S ={ s1,s2,…,sQ} Q = nm • 信源输出的随机符号序列为:x1, x2,…x i-1, x i… • 信源所处的随机状态序列为:s1,s2,…si-1 ,si,… • 例:二元序列为…01011100… • 考虑 m = 2,Q = nm =22= 4
通信系统模型 信源:信息输出的源。分离散信源和模拟信源。 信宿:信息归宿之意,意即收信者或用户,是信息传送的终点或目的地。 信道:传送信息的物理媒介。 密钥源:产生密钥 k 的源。信号 x 经过 k 的加密运算后,就把明文 x 变换为密文 y。
一般地说,通信系统的性能指标主要是有效性、可靠性、安全性和经济性。除了经济性外, 这些指标正是信息论的研究对象。 信源编码:信源编码器的作用:一、将信源发出的信息变换成基带信号;二、压缩冗余度, 提高效率(有效性)。 信道编码:在信源编码器输出的代码组上有目的地增加一些监督码元,使之具有检错和纠 错能力。信道译码器具有检错和纠错能力,它能将在其检错或纠错能力范围内的错传码元 检测出来并加以纠正,以提高传输信息的可靠性。信道编码包括调制解调和纠错检错编译 码。信道中的干扰通常使通信质量下降,对于模拟信号,表现在受到的信号的信噪比下降; 对于数字信号就是误码率增大。信道编码的主要方法是增大码率或频带,即增大所需的信 道容量。这恰与信源编码相反。 3. 香农
他在 1941 年至 1944 年对通信和密码进行深入研究,并用概率论的方法研究通信系统, 揭示了通信系统传递的对象就是信息,并对信息给以科学的定量描述,提出了信息熵的概 念。还指出通信系统的中心问题是在噪声下如何有效而可靠地传送信息,而实现这一目标 的主要方法是编码等。这一成果于 1948 年在《贝尔系统技术杂志》以《通信的数学理论》 为题公开发表,次年,他又在同一杂志上发表了《噪声下的通信》香农因此成为信息论的 奠基人。
这种三码合一的设想是当前众所关心的课题,但因理论上和技术上的复杂性,要 取得有用的结果,还是相当困难。
第二章 信源与信息熵
考点: 自信息
概率空间
X P
x1 p( x1 )
x2 p(x2 )
xn p(xn )
样本空间:某事物各种可能出现的不同状态。
先验概率 p(xi):选择符号 xi 作为消息的概率。
I (xi | y j ) log p(xi | y j )
信源 – 产生消息(符号)、消息序列和连续消息的来源 – 产生随机变量、随机序列和随机过程的源。
– 在通信系统中收信者在未收到消息以前对信源发出什么消息是不确定的,是随机 的,所以可用随机变量、随机序列或随机过程来描述信源输出的消息,或者说用 一个样本空间及其概率测度—概率空间来描述信源
平均自信息 平均不确定度 信源熵(公式一定要记住)
H(X):平均信息量,称为信源 X 的熵。 信源熵、香农熵
离散信源熵 H(X)
(平均不确定度/平均信息量/平均自信息量)
定义:信源的平均不确定度 H(X)为信源中各个符号不确定度的数学期望,即:
H ( X ) p(xi )I (xi ) p(xi ) log p(xi )
i
i
单位为比特/符号或比特/符号序列
信息熵:从平均意义上来表征信源的总体信息测度的一个量。
自信息:指某一信源发出某一消息所含有的信息量。
所发出的消息不同,它们所含有的信息量也就不同。
自信息 I (xi)是一个随机变量,不能用它来作为整个信源的信息测度。 信源熵具有以下三种物理含意:
– 信息熵 H(X)表示信源输出后,每个离散消息所提供的平均信息量。 – 信息熵 H(X)表示信源输出前,信源的平均不确定性。 – 信息熵 H(X)反映了变量 X 的随机性
X P
x1 1/ 6
x2 1/ 6
x3 1/ 6
x4 1/ 6
x5 1/ 6
x6 1/ 6
• • 信源的描述
发出单个符号的信源 – 指信源每次只发出一个符号代表一个消息;
发出符号序列的信源 – 指信源每次发出一组含二个以上符号的符号序列代表一个消息
离散有记忆信源:所发出的各个符号的概率是有关联的。
即统计独立信源的信息量等于它们分别的信息量之和。 • 一个出现概率接近于 1 的随机事件,发生的可能性很大,所以它包含的不确定度就很
小; • 一个出现概率很小的随机事件,很难猜测在某个时刻它能否发生,所以它包含的不确
定度就很大; • 若是确定性事件,出现概率为 1,则它包含的不确定度为 0。 联合自信息量 两个消息 xi,yj 同时出现的联合自信息量
• s1 = 00 s2 = 01 s3 = 10 s4 = 11 • 变换成对应的状态序列为