信息论与编码 曹雪芹 Chap2

信源与信息熵第二章22.1信源的描述和分类2.2离散信源熵和互信息2.3离散序列信源的熵2.4冗余度内容32.1信源的描述和分类4信源•信源–产生消息(符号)、消息序列和连续消息的来源–产生随机变量、随机序列和随机过程的源。•在通信系统中收信者在未收到消息以前对信源发出什么消息是不确定的,是随机的，所以可用随机变量、随机序列或随机过程来描述信源输出的消息,或者说用一个样本空间及其概率测度—概率空间来描述信源•信源的基本特性：具有随机不确定性。5香农信息论的基本点•用随机变量或随机矢量来表示信源•用概率论和随机过程的理论来研究信息6{信源离散信源:连续信源:信源的分类•按照信源发出的消息在时间上和幅度上的分布情况可将信源分成离散信源和连续信源两大类•连续信源–指发出在时间和幅度上都是连续分布的连续消息（模拟消息）的信源，如语言、图像、图形等都是连续消息。文字、数据、电报—随机序列话音、图像—随机过程7离散信源{离散无记忆信源离散有记忆信源{{发出单个符号的无记忆信源发出符号序列的无记忆信源发出符号序列的有记忆信源发出符号序列的马尔可夫信源信源的分类•离散信源–指发出在时间和幅度上都是离散分布的离散消息的信源，如文字、数字、数据等符号都是离散消息。82.1.1无记忆信源•离散无记忆信源–所发出的各个符号是相互独立的，发出的符号序列中的各个符号之间没有统计关联性，各个符号的出现概率是它自身的先验概率。6/16/16/16/16/16/1654321xxxxxxPX•例如扔骰子，每次试验结果必然是1～6点中的某一个面朝上。•用一个离散型随机变量X来描述这个信源输出的消息。9•发出单个符号的信源–指信源每次只发出一个符号代表一个消息；•发出符号序列的信源–指信源每次发出一组含二个以上符号的符号序列代表一个消息离散无记忆信源6/16/16/16/16/16/1654321PX10信源的描述•一个离散信源发出的各个符号消息的集合为：},,,{21nxxxX)}(,),(),({21nxpxpxpP•它们的概率分别为•p(xi):xi的先验概率•单符号离散信源的数学模型—概率空间)()()(2121nnxpxpxpxxxPX1)(0)(1niiixpxpa,b,c,…z11离散信源的统计特性•离散消息是从有限个符号组成的符号集中选择排列组成的随机序列（组成离散消息的信息源的符号个数是有限的）•在形成消息时，从符号集中选择各个符号的概率不同。•组成消息的基本符号之间有一定的统计相关特性。12信源的描述•连续信源：–输出在时间和幅度上都是连续分布的消息•单符号连续无记忆信源的概率空间)(),(xpbaPXX1)(0)(baXxdxxpxp随机取一节干电池测其电压值作为输出符号,符号取值为[0,1.5]之间的所有实数。该信源就是发出单符号的连续无记忆信源13信源的描述•发出符号序列的信源0000010100111001011101111/81/81/81/81/81/81/81/8XP•设信源输出的随机序列为X=(X1X2…Xl…XL)•序列中的变量Xl∈{x1,x2,…xn}•这种由信源X输出的L长随机序列X所描述的信源称为离散无记忆信源X的L次扩展信源14信源的描述•随机序列的概率LllLlLlxpxpxpxpxpxxxxp12121)()()()()()(•当信源无记忆时),,(),|(),|(),,(),|(),,,(2211211112111321LLLLLLLLLxxxpxxxpxxxpxxxpxxxpxxxxp15•一般情况下,信源在不同时刻发出的符号之间是相互依赖的，也就是信源输出的平稳随机序列X中，各随机变量Xl之间是有依赖的。•如在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的。•表述有记忆信源要比表述无记忆信源困难得多•离散有记忆信源–所发出的各个符号的概率是有关联的。•发出符号序列的有记忆信源•发出符号序列的马尔可夫信源2.1.2有记忆信源用信源发出的一个符号序列的整体概率(即联合概率)反映有记忆信源的特征一个符号出现的概率只与前面一个或有限个符号有关,而不依赖更前面的那些符号16概率论基础•无条件概率、条件概率、联合概率的性质和关系⑴⑵⑶1)()|()|()()(0jijiijjiyxpyxpxypypxp，，，，mjnijimjijnijimjjniiyxpxypyxpypxp1111111)(,1)|(,1)|(,1)(,1)()()(),()(11imjjijnijixpyxpypyxp17概率论基础•无条件概率、条件概率、联合概率的性质和关系⑷⑸⑹)|()()|()()(jijijijiyxpypxypxpyxp，，相互独立时，与当)()|()()|()()()(ijijijjijixpyxpypxypypxpyxpYXmjjijiijnijijijiyxpyxpxypyxpyxpyxp11)()()|()()()|(，182.1.3马尔可夫信源•马尔可夫信源–一类相对简单的离散平稳信源–该信源在某一时刻发出字母的概率除与该字母有关外,只与此前发出的有限个字母有关•m阶马尔可夫信源：–信源输出某一符号的概率仅与以前的m个符号有关，而与更前面的符号无关。•条件概率11(|,)LLpxxx1(|,)LLLmpxxx19马氏链的基本概念)|()|()|()(),,,(121121321LLLLLxxpxxpxxpxpxxxxp•一阶马尔可夫信源：•若把有限个字母记作一个状态S，则信源发出某一字母的概率除与该字母有关外，只与该时刻信源所处的状态有关。•信源将来的状态及其送出的字母将只与信源现在的状态有关，而与信源过去的状态无关。20马氏链的基本概念•令si=(xi1,xi2,…xim)xi1,,xi2,…xim∈(a1,a2,…an)•状态集S={s1,s2,…,sQ}Q=nm•信源输出的随机符号序列为：x1,x2,…xi-1,xi…•信源所处的随机状态序列为：s1,s2,…si-1,si,…•例：二元序列为…01011100…•考虑m=2，Q=nm=22=4•s1=00s2=01s3=10s4=11•变换成对应的状态序列为…s2s3s2s4s4s3s1…21马尔可夫信源•设信源在时刻m处于si状态,它在下一时刻(m+1)状态转移到sj的转移概率为：pij(m)=p{Sm+1=sj|Sm=si}=p{sj|si}•pij(m)：基本转移概率（一步转移概率）•若pij(m)与m的取值无关,则称为齐次马尔可夫链pij=p{Sm+1=sj|Sm=si}=p{S2=sj|S1=si}•pij具有下列性质：pij≥0jijp122•若信源处于某一状态si,当它发出一个符号后,所处状态就变了,任何时候信源处于什么状态完全由前一时刻的状态和发出符号决定。•系统在任一时刻可处于状态空间S={s1,s2,…,sQ}中的任意一个状态,状态转移时,转移概率矩阵QQQQijppppsspP1111)|(QnQnijppppsxpP1111)|(•符号条件概率矩阵23•例2-1，如图所示是一个相对码编码器,输入的码Xr(r=1,2,…)是相互独立的，取值0或1，且已知P(X=0)=p,P(X=1)=1－p=q，输出的码是Yr，显然TXrYrYr-1+,,12211YXYXY•Yr是一个马氏链,Yr确定后,Yr+1概率分布只与Yr有关,与Yr-1、Yr-2…等无关,且知Yr序列的条件概率24sos1pqqpp00=P(Y2=0/Y1=0)pqqpPp10=P(Y2=0/Y1=1)=P(X=1)=qp11=P(Y2=1/Y1=1)=P(X=0)=pp01=P(Y2=1/Y1=0)=P(X=0)=p=P(X=1)=q25马尔可夫信源•状态转移图–齐次马尔可夫链可以用其状态转移图(香农线图)表示–每个圆圈代表一种状态–状态之间的有向线代表某一状态向另一状态的转移–有向线一侧的符号和数字分别代表发出的符号和条件概率sos11/0.60/0.30/0.4s21/0.20/0.81/0.726s3s2s4s5s1s6周期性的：在常返态中,有些状态仅当k能被某整数d＞1整除时才有pii(k)＞0,x5:1非周期性的：对于pii(k)＞0的所有k值，其最大公约数为1。常返态：经有限步后迟早要返回的状态，x4:1x3:1/2x2:1/2x3:1/2x2:1/2x2:1/2x4:1/4x1:1/4x6:1x6:1/4图中的周期为2；27马尔可夫信源•遍历状态：–非周期的、常返的状态,如图中的状态s2和s3•闭集：–状态空间中的某一子集中的任何一状态都不能到达子集以外的任何状态•不可约的：–闭集中除自身全体外再没有其他闭集的闭集28马尔可夫信源•一个不可约的、非周期的、状态有限的马尔可夫链其k步转移概率pij(k)在k→∞时趋于一个和初始状态无关的极限概率Wj，它是满足方程组的唯一解；•Wj：马尔可夫链的一个平稳分布，•Wj[p(sj)]就是系统此时处于状态sj的概率。1jjiijijWpWW29sos11/0.60/0.30/0.4s21/0.20/0.81/0.70.60.40(|)0.300.70.200.8jipssijpijiWW例01200.60.30.2010.4WW1220.70.801210120.3571,0.1429,0.530•例2-2：有一个二元二阶马尔可夫信源,其信源符号集为{0，1}，已知符号条件概率：p(0|00)=1/2p(1|00)=1/2p(0|01)=1/3p(1|01)=2/3p(0|10)=1/4p(1|10)=3/4p(0|11)=1/5p(1|11)=4/5•求：⑴信源全部状态及状态转移概率⑵画出完整的二阶马尔可夫信源状态转移图。⑶求平稳分布概率31121234()()()1/21/2()1/32/3(|)()1/43/4(0100011011)1/54/5jiaasspasss•状态转移概率矩阵•符号条件概率矩阵5/45/100004/34/13/23/100002/12/1)|(43214321sssssspssssij(1)1/2(0)1/2(0)1/3(1)2/300011110s2s1s4s3(1)3/4(0)1/4(0)1/5(1)4/532•稳态分布概率154325131432121214321442342231131•稳态后的符号概率分布11()(|)()iiipapasps221326364426()(|)()2353354355735iiipapasps131616149235335435573533•例一个二元二阶马尔可夫信源,其信源符号集为{0,1}信源开始时：p(0)=p(1)=0.5发出随机变量X1。下一单位时间：输出随机变量X2与X1有依赖关系x2x10100.30.410.70.6p(x2|x1)再下一单位时间：输出随机变量X3与X2X1有依赖关系x3x1x20001101100.40.20.30.410.60.80.70.6p(x3|x1x2)34•从第四单位时间开始，随机变量Xi只与前面二个单位时间的随机变量Xi-2Xi-1有依赖关系:p(xi|xi-1