第3章通信信源与信源编码 第3章通信信源与信源编码 3.1信源特性及信源分类 3.1.1信源的基本特性 通信信源是通信系统的源端，它所产生的输出信号是一种随机过程。 信源可分为有记忆和无记忆两大类，也可以分为连续和离散两大类。 无记忆信源在不同时刻所产生的输出是相互独立的，它在任意不同时刻的两个样点都是两 个互不相关的随机变量。 有记忆信源在不同时刻所产生的输出值是相互关联的，当前输出值的概率分布与前面出现 的值有关，例如：那些可用马尔可夫过程、短时平稳过程或循环平稳过程描述的信号，都可 以看作是由有记亿信源所产生的输出。 通信信源所产生的输出是用来携带信息进行通信的：因此无论是离散信源还是连续信源， 一般都是利用收发两端共知的一个由有限个信源字符etter或symbol)组成的字符集 (alphabet)来表示信息的：按表达信息内容的需要，一次又一次地从字符集中选择一个适当 的字符作为输出来携带信息进行传输。这些信源字符的传输和存储，一般采用某种物理量（例 如：声、光、电)的一组数值或一种波形来表现，因此有些表现为离散信源，有些表现为连续 信源。 3.1.2离散信源 一个离散信源所发出的信源字符，一般属于一个字符数目有限的字符集，例如汉字的国标 一级字表，共有3763个常用汉字。一个通信系统的发端和收端都利用同一个字符集，以便进 行编码和译码。 无记忆离散信源的统计特性可以用字符集中各种字符出现的概率分布来描述：当它为均匀 分布时携带信息的效率最高。 有记忆离散信源当前输出什么字符，与过去或将来输出的字符统计相关。这种相关性在时 域表现为马尔可夫性，在频域表现为功率密度谱不平坦，即自相关函数不是6函数。有记忆 信源的统计特性的描述，需要采用多维随机变量的联合概率分布及自相关函数来描述。信源 的记忆性或相关性反映信息的冗余性，因此同样大小信源字符集的信源，无记忆信源携带信 息的效率高于有记忆信源 西安电子科技大学
第 3 章 通信信源与信源编码 西安电子科技大学 1 第 3 章 通信信源与信源编码 3.1 信源特性及信源分类 3.1.1 信源的基本特性 通信信源是通信系统的源端，它所产生的输出信号是一种随机过程。 信源可分为有记忆和无记忆两大类，也可以分为连续和离散两大类。 无记忆信源在不同时刻所产生的输出是相互独立的，它在任意不同时刻的两个样点都是两 个互不相关的随机变量。 有记忆信源在不同时刻所产生的输出值是相互关联的，当前输出值的概率分布与前面出现 的值有关，例如：那些可用马尔可夫过程、短时平稳过程或循环平稳过程描述的信号，都可 以看作是由有记忆信源所产生的输出。 通信信源所产生的输出是用来携带信息进行通信的；因此无论是离散信源还是连续信源， 一般都是利用收发两端共知的一个由有限个信源字符(letter 或 symbol)组成的字符集 （alphabet）来表示信息的；按表达信息内容的需要，一次又一次地从字符集中选择一个适当 的字符作为输出来携带信息进行传输。这些信源字符的传输和存储，一般采用某种物理量(例 如：声、光、电)的一组数值或一种波形来表现，因此有些表现为离散信源，有些表现为连续 信源。 3.1.2 离散信源 一个离散信源所发出的信源字符，一般属于一个字符数目有限的字符集，例如汉字的国标 一级字表，共有 3763 个常用汉字。一个通信系统的发端和收端都利用同一个字符集，以便进 行编码和译码。 无记忆离散信源的统计特性可以用字符集中各种字符出现的概率分布来描述；当它为均匀 分布时携带信息的效率最高。 有记忆离散信源当前输出什么字符，与过去或将来输出的字符统计相关。这种相关性在时 域表现为马尔可夫性，在频域表现为功率密度谱不平坦，即自相关函数不是 δ 函数。有记忆 信源的统计特性的描述，需要采用多维随机变量的联合概率分布及自相关函数来描述。信源 的记忆性或相关性反映信息的冗余性，因此同样大小信源字符集的信源，无记忆信源携带信 息的效率高于有记忆信源
第3章通信信源与信源编码 3.13连续信源 连续信源产生的输出是一种连续随机过程，如果它是频带有限的，那么可以以适当的采 样间隔采样为离散随机过程。 3.1.4采样定理 ()随机过程的采样 如果随机过程X)是频带有限的，设带宽小于等于W,那么X()可以用一个以随机变量 序列{X(n/2W),n=-0,-l,0,l,∞}为系数的级数表示： X()=x(nl2W)Sine(2W(-n/2W)) (3-1-10 =2Xa12mm2-n12m】 2xW(t-n/2W) 其中{X(m/2)}为X)以时间间隔T=1《2)采样得到的样点序列；它是X)在正交基 函数族{Sinc(2xWt-n/2W》:n=0,-1,0,l,o}上的投影。 (2)确知信号的采样 【采样定理1】设连续信号x()的频谱X)是频带有限的，即当川≥人时X)-0;那么对 它进行均匀间隔采样得到离散信号{x(m)},如果采样间隔T满足T<12f),则由{x)}可以精 确地重构x),即： 0=2切1-n0 号(t-nT) (3-1-2a) 并且其频谱xX(刀也可由离散信号{x()}或其频谱)唯一确定，即 =72ms=0[品别 (3-1-2b) 【采样定理2】以T为采样间隔采样连续信号x()得到的离散信号{x(m)},无论是否满 足采样定理1的条件，二者的颜谱都存在如下关系： 0=Σxw+ (3-1-3) 西安电子科技大学
第 3 章 通信信源与信源编码 西安电子科技大学 2 3.1.3 连续信源 连续信源产生的输出是一种连续随机过程，如果它是频带有限的，那么可以以适当的采 样间隔采样为离散随机过程。 3.1.4 采样定理 (1)随机过程的采样 如果随机过程 X ( )t 是频带有限的，设带宽小于等于W ，那么 X ( )t 可以用一个以随机变量 序列{ X ( /2 ) n W ，n = −∞ − ∞ ,., 1, 0,1,., }为系数的级数表示： X ( )t = ( / 2 ) (2 ( / 2 )) n X n W Sinc W t n W π ∞ =−∞ ∑ − = sin[2 ( / 2 )] ( /2 ) n 2 ( /2 ) Wt n W Xn W Wt n W π π ∞ =−∞ − − ∑ (3-1-1) 其中{ X ( /2 ) n W }为 X ( )t 以时间间隔T W = 1/(2 ) 采样得到的样点序列；它是 X ( )t 在正交基 函数族{Sinc(2 ( / 2 )) πWt n W − ；n = −∞ − ∞ ,., 1,0,1,., }上的投影。 (2)确知信号的采样 【采样定理 1】设连续信号 x(t)的频谱 X ( ) f 是频带有限的，即当|f| c ≥ f 时 X ( ) f =0；那么对 它进行均匀间隔采样得到离散信号{ x( ) n }，如果采样间隔T 满足 1/(2 )c T < f ，则由{ x( ) n }可以精 确地重构 x( )t ，即： sin ( ) ( ) ( ) ( ) T n T t nT x n t nT x t π π +∞ =−∞ − − = ∑ (3-1-2a) 并且其频谱 X ( ) f 也可由离散信号{ x( ) n }或其频谱 X ( ) f 唯一确定，即 X ( ) f = 2 1 1 , 2 2 () ( ) j fnT n f T T T xne X f π +∞ − =−∞ − = ∈ ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ ∑ (3-1-2b) 【采样定理 2】 以 T 为采样间隔采样连续信号 x( )t 得到的离散信号{ x( ) n }，无论是否满 足采样定理 1 的条件，二者的频谱都存在如下关系： () ( ) m m Xf Xf T +∞ =−∞ = + ∑ (3-1-3)
第3章通信信源与信源编码 3 这个定理的(3-l-3)式给出了因不满足采样定理1而产生频谱混叠失真(aliasing)的规律。 【推论】设采样率为的离散信号{(m)}的频谱为求)，对{m)}进行g:1的下采样后得 到采样率为5/g离散信号{礼m)},其颜谱为)，则这两个频谱总存在以下关系： 0=∑U+mM1g) (3-1-4) (f)的周期为方，而)的周期为51q。 【采样定理3】设x()是一个下界频率为f和上界频率为的带通实信号，且满足 人>m2:若采样频率了=1/T满足 m=12,3. (3-1-5 其中m为某个合适的正整数，那么x)可用其采样信号{()}和∫，精确地重构而无混叠失真： 如果x()是一个频带为(，了m)的带通解析信号，那么重构信号不出现混叠失真的充分必要条 件是：fr>(m-) 定理证明的要点： 1)对x()以时间间隔T进行采样，相当于用一个周期为T周期性的Kroneker6函数与它 相乘，频域为二者之卷积；而周期性的Kroneker6函数的频谱函数是一个周期为l/T的6函 数。要想使二者的卷积不出现频谱混叠现象，只要在卷积过程中任何时刻都没有两个6脉冲同 时对准x()的正频率频谱和它的镜像频谱就行。 2)如果对于x()的复解析信号x()进行采样，即正交采样，则只要采样频率大于1/T, 在卷积过程中就没有两个δ脉冲同时对准频谱的现象，因为它没有镜像频谱。 3)当带通实信号的边界频率不满足f>f,2时，就找不到比2∫还低的采样频率，因此 不能采用上述定理。 采样信号的频谱是周期为的周期性频谱，每个周期中包含有一个正频率频谱X()的复 本和它的镜像的复本，如图3-1-1所示。 4X0成0 (m+1>24 图3-11带通信号及其采样信号的频谱 西安电子科技大学
第 3 章 通信信源与信源编码 西安电子科技大学 3 这个定理的(3-1-3)式给出了因不满足采样定理 1 而产生频谱混叠失真（aliasing）的规律。 【推论】设采样率为 Tf 的离散信号{x( ) n }的频谱为 X ( ) f ，对{x( ) n }进行q :1的下采样后得 到采样率为 / T f q 离散信号{ x( ) m }，其频谱为 X ( ) f ，则这两个频谱总存在以下关系： 1 0 () ( ) / q m T X f X f mf q − = = + ∑ (3-1-4) X ( ) f 的周期为 Tf ，而 X ( ) f 的周期为 / T f q 。 【采样定理 3】设 x(t) 是一个下界频率为 Lf 和上界频率为 Hf 的带通实信号，且满足 Lf > Hf /2；若采样频率 T f =1/ T 满足 2 2 1 H L T f f f m m − f f 。 定理证明的要点： 1）对 x(t)以时间间隔T 进行采样，相当于用一个周期为T 周期性的 Kroneker δ 函数与它 相乘，频域为二者之卷积；而周期性的 Kroneker δ 函数的频谱函数是一个周期为 1/T 的δ 函 数。要想使二者的卷积不出现频谱混叠现象，只要在卷积过程中任何时刻都没有两个δ 脉冲同 时对准 x(t)的正频率频谱和它的镜像频谱就行。 2）如果对于 x(t)的复解析信号x( )t 进行采样，即正交采样，则只要采样频率大于 1/T ， 在卷积过程中就没有两个δ 脉冲同时对准频谱的现象，因为它没有镜像频谱。 3）当带通实信号的边界频率不满足 Lf > Hf /2 时，就找不到比 2 Hf 还低的采样频率，因此 不能采用上述定理。 采样信号的频谱是周期为 Tf 的周期性频谱，每个周期中包含有一个正频率频谱 X ( ) f 的复 本和它的镜像的复本，如图 3-1-1 所示。 . . -fT -fT fT fT -kfT -kfT kfT kfT fL fL fH fH -(k+1)fT -(k+1)fT (k+1)fT (k+1)fT mfT2fH f f X(f)/X(f) 图 3-1-1 带通信号及其采样信号的频谱
第3章通信信源与信源编码 3.2信息的度量和信源熵 3.2.1信息量的度量单位 ·信息的度量和单位： 因此用L0g(1/P)来衡量信源字符集中第1个信源字符所携带的信息量。 当Log,1/P)-1时，该字符所携带的信息量定义为1比特(bi): 当LI/P)=1时，该字符所携带的信息量定义为1奈特Nat: 当Logo(1/P)=1时，该字符所携带的信息量定义为1哈特Hart): 1nate1.44bit,1Hart3.32bit:数字通信中通常以二进制为基础，因此采用比特作为信息量 单位最为常用。 。互信息： 设两个离散随机变量X和Y的取值范围分别为{：，书，x}和{，2，y),其概率分布分 别为{P(x,P(x,P(x)}和{P(y )P(y,PUy)}:如果二者存在相关性，定义Ay)为在出现 事件了=y,的条件下事件X=x出现的概率，那么事件y=y,的出现提供关于事件X=x的信息 量定义为： Ixy)=Log[P(x,Iy,)/Px】 (3-2-1) I(xy,)称为X=x和Y=y,之间的互信息。 ·平均互信息： 离散随机变量X和Y之间的平均互信息为： P(xy) xn-2Mux)-22us品 (3-2-2) X和y之间的平均互信息可以用条件熵来表示： I(X:Y)=H()-H(XY)=H(Y)-H(YX) (3-2-3) 3.2.2信源熵 一个信源的熵定义为该信源每发送一个字符所携带信息量的平均值。 ()无记忆离散信源的熵 如果一个信源共有n个信源符号{x,x2,xn},各个符号的概率分布为 西安电子科技大学
第 3 章 通信信源与信源编码 西安电子科技大学 4 3.2 信息的度量和信源熵 3.2.1 信息量的度量单位 z 信息的度量和单位： 因此用 (1/ ) Log Pi 来衡量信源字符集中第i 个信源字符所携带的信息量。 当 2 og (1/ ) L Pi =1 时，该字符所携带的信息量定义为 1 比特(bit)； 当 (1/ ) Ln Pi =1 时，该字符所携带的信息量定义为 1 奈特(Nat)； 当 10 og (1/ ) L Pi =1 时，该字符所携带的信息量定义为 1 哈特(Hart)； 1nat≈1.44bit，1Hart≈3.32bit；数字通信中通常以二进制为基础，因此采用比特作为信息量 单位最为常用。 z 互信息： 设两个离散随机变量 X 和Y 的取值范围分别为 1 2 { , ,., }n x x x 和 1 2 { , ,., ) m y y y ，其概率分布分 别为{ 1 2 ( ), ( ),., ( ) Px Px Pxn }和{ 1 2 ( ), ( ),., ( ) Py Py Pym }；如果二者存在相关性，定义 ( | ) i j P x y 为在出现 事件Y = j y 的条件下事件 X = i x 出现的概率，那么事件Y = j y 的出现提供关于事件 X = i x 的信息 量定义为： ( ; ) [ ( | ) / ( )] ij i j i I x y Log P x y P x = (3-2-1) (; ) i j I x y 称为 X = i x 和Y = j y 之间的互信息。 z 平均互信息： 离散随机变量 X 和Y 之间的平均互信息为： 1 1 ( ; ) ( , )( ; ) n m ij ij i j IXY Px y Ix y = = = ∑∑ 1 1 (, ) ( , ). ()( ) n m i j i j i j i j Px y P x y Log = = Px Py = ∑∑ (3-2-2) X 和Y 之间的平均互信息可以用条件熵来表示： I XY H X H X Y HY HY X ( ;) ( ) ( | ) () ( | ) = − =− (3-2-3) 3.2.2 信源熵 一个信源的熵定义为该信源每发送一个字符所携带信息量的平均值。 (1) 无记忆离散信源的熵 如果一个信源共有 n 个信源符号 { n x , x ,., x 1 2 } ，各个符号的概率分布为
第3章通信信源与信源编码 P(X=x)=p,i=1,2,n,并且n+p,++p。=1;那么其痛为： HX=-∑p,logp, (3-2-4) (2)有记忆信源的熵 有记忆随机过程的统计特性要用联合概率来描述，因此记忆长度为L的信源，其熵也应该 用L维联合概率分布函数P(X,X,X,)来计算，则相邻L个字符的熵为： H(X.X)=->P(X.X.X)log P(X.X:) (3-2-5) 平均每个字符的嫡为： H(X)=H(X.X.X)/L (3-2-6) 如果把前面L-1个随机变量作为条件，则可求得最后一个变量的熵，称为条件熵 H,(X2IX,X2,X)。那么，H(X)可表示为 H,(X)=[H(X)+H(X1X)+H(XlX,X)+.+H,(XzIX,X,X-/L(3-2-7) 条件概率空间的概率分布一般要比无条件概率空间的概率分布更集中，因此条件熵小于 无条件熵：条件越多其熵值越小，再考虑到平稳性，则有如下递增关系： H(XX.Xx)sHXX)=HXX) H(XX.X.X)=H(XIX.X:.X) ≤HXlX.XX=HXlX,XX4) (3-2-8) ≤HXIX)sHX) 由此可见(3-2-)式给出的平均每个字符的熵H,(X)的值，介于无条件熵HX)与条件熵 H(X2lX.X,X4)之间。 (仔)离散马尔可夫信源的熵 如果一个信源字符樂大小为的一阶马尔可夫信源所产生的输出是一个各态历经的一阶 平稳马尔可夫链，那么其极限分布（即各个信源字符出现的概率）可由下述K-C方程求得： p,=∑P,P j=12n (3-2-9) 其中{P,j=L,2,n}为状态转移概率矩阵，P:为前一步处于状态1，而当前一步转移到状态 西安电子科技大学
第 3 章 通信信源与信源编码 西安电子科技大学 5 ( ) 1, 2,., P Xx pi n i i == = ，并且 1 2 . 1 n pp p + ++ = ；那么其熵为： 1 ( ) log n i i i HX p p = = −∑ (3-2-4) (2) 有记忆信源的熵 有记忆随机过程的统计特性要用联合概率来描述，因此记忆长度为 L 的信源，其熵也应该 用 L 维联合概率分布函数 P( 1 2 , ,., X X XL )来计算，则相邻 L 个字符的熵为： 12 12 12 ( , ,., ) ( , ,., ) log ( , ,., ) HX X X PX X X PX X X L L L = −∑ (3-2-5) 平均每个字符的熵为： ( ) H X L = 1 2 ( , ,., ) / HX X X L L (3-2-6) 如果把前面 L −1个随机变量作为条件，则可求得最后一个变量的熵，称为条件熵 12 1 ( | , ,., ) HX XX X LL L− 。那么， ( ) H X L 可表示为： ( ) H X L = 1 [( ) H X + 2 1 HX X (|) + 3 12 HX X X (|,)+.+ 12 1 ( | , ,., )]/ HX XX X L LL L− (3-2-7) 条件概率空间的概率分布一般要比无条件概率空间的概率分布更集中，因此条件熵小于 无条件熵；条件越多其熵值越小，再考虑到平稳性，则有如下递增关系： 12 1 ( | , ,., ) HX XX X LL L− 23 1 ( | , ,., ) HX X X X L L− ≤ = 1 12 2 ( | , ,., ) HX X X X L L − − 1 23 2 ( | , ,., ) HX X X X L L − − ≤ = 2 12 3 ( | , ,., ) HX X X X L L − − 2 23 3 ( | , ,., ) HX X X X L L − − ≤ = 3 12 4 ( | , ,., ) HX X X X L L − − . 2 1 ≤ HX X (|) 1 ≤ H X( ) (3-2-8) 由此可见(3-2-7)式给出的平均每个字符的熵 ( ) H X L 的值，介于无条件熵 1 H X( ) 与条件熵 12 1 ( | , ,., ) HX XX X LL L− 之间。 (3) 离散马尔可夫信源的熵 如果一个信源字符集大小为 n 的一阶马尔可夫信源所产生的输出是一个各态历经的一阶 平稳马尔可夫链，那么其极限分布(即各个信源字符出现的概率)可由下述 K-C 方程求得： p j = ij n i ∑ pi p =1 j n = 1, 2,., (3-2-9) 其中{ pij ，ij n , 1, 2,., = }为状态转移概率矩阵, pij 为前一步处于状态 i,而当前一步转移到状态
第3章通信信導与信源编码 了的概率。于是，这个一阶马尔可夫信源的嫡为： H(X)=H(XX) (3-2-10) (④)连续信源的差熵 连续随机变量不能像离散随机变量那样定义自信息，因而也不能相应地定义熵，但可类 似地定义一种嫡，称为差嫡 p)Logn( (3-2-11) (⑤)连续信源的平均互信息 设连续随机变量X和Y的联合PDF为p(x,y),它们的边沿PDF分别为p(x,py),那么X和 Y之间的平均互信息定义为： x:)=[p)p(yLoddy p(x)p(y) (3-2-12) Y己知时X的平均条件熵定义为： H(XIY)=-[[p(x.y)Logp(xly)dxdy (3-2-13) 于是有 I(X:Y)=H(X)-H(X Y)=H(Y)-H(YX) (3-2-14) 3.3离散信源信息的编码 3.3.1定长编码 一个字符集大小为L的无记忆离散信源X,当各字符的概率相等时其熵的值最大，即： H(X)≤LogL (3-3-1) 采用固定长度码字，对于字符集大小为L的无记忆离散信源所发出的字符序列逐个地进行 无失真编码，则每个码字的长度需要比特： r=mlog2(L-l]+】 (3-3-2) 这里表示舍尾取整，因此应取r比特才能确保L种字符都有对应的码字，即2≥L。 【离散信源定长编码定理】对于一个信源熵等于H(X)比特的无记忆离散平稳信源X,可以 将信源发出的字符序列每J个字符分为一组，用N比特长的码字进行编码，对于任意小的正数 8,只要J选择的足够大，并使码率R满足 西安电子科技大学
第 3 章 通信信源与信源编码 西安电子科技大学 6 j 的概率。于是，这个一阶马尔可夫信源的熵为： 2 1 HX HX X () ( | ) = (3-2-10) (4) 连续信源的差熵 连续随机变量不能像离散随机变量那样定义自信息，因而也不能相应地定义熵，但可类 似地定义一种熵，称为差熵： H X p x Logp x dx ( ) () () ∞ −∞ = − ∫ (3-2-11) (5) 连续信源的平均互信息 设连续随机变量 X 和Y的联合PDF为 p(, ) x y ,它们的边沿PDF分别为 p( ), ( ) x py ,那么 X 和 Y 之间的平均互信息定义为： () ( | ) ( ; ) () ( | ) () () pxpy x I X Y p x p y x Log dxdy pxpy ∞ ∞ −∞ −∞ = ∫ ∫ (3-2-12) Y 已知时 X 的平均条件熵定义为: H X Y p x y Logp x y dxdy ( | ) (, ) ( | ) ∞ ∞ −∞ −∞ = −∫ ∫ (3-2-13) 于是有 IXY HX HX Y (;) ( ) ( |) = − = HY HY X () ( | ) − (3-2-14) 3.3 离散信源信息的编码 3.3.1 定长编码 一个字符集大小为 L 的无记忆离散信源 X ，当各字符的概率相等时其熵的值最大,即： H X LogL ( ) ≤ (3-3-1) 采用固定长度码字，对于字符集大小为 L 的无记忆离散信源所发出的字符序列逐个地进行 无失真编码，则每个码字的长度需要 r 比特： 2 r Int L = −+ [log ( 1)] 1 (3-3-2) 这里 Int 表示舍尾取整，因此应取r 比特才能确保 L 种字符都有对应的码字，即2r ≥ L 。 【离散信源定长编码定理】对于一个信源熵等于 H X( ) 比特的无记忆离散平稳信源 X ,可以 将信源发出的字符序列每 J 个字符分为一组，用 N 比特长的码字进行编码，对于任意小的正数 ε，只要 J 选择的足够大，并使码率 R 满足
第3章通信信源与信源编码 7 R=N≥HX)+E (3-3-3) 就可以保证编码失败的码组出现的概率P。可以任意小：反之，若码率 R=NSH(X)-6 (3-3-4) 则编码失败码组出现的概率P。将随J的增大而趋于100%. 此定理的含义是：对一个信源发出的符号序列进行定长分组编码，只要码率大于信源熵， 码组又足够长，则无失真编码失败的概率可以无穷小：而若码率小于信源嫡，无失真编码失败 的可能性非常大。 【例】将一本中文书看作一个信源，如果所用汉字都包含在国标一级字表的3763个汉字之中，则国标 一级字表就是信源字符集。将书中的汉字用代码表示，本来需要用12比特长的代码才能表示一个汉字。但 是，假如根据该书中各种汉字出现的概率求得的信源熵H(X)=7.9比特/字符，而将书中每J个汉字看作 个码组用一个N比特的代码表示，那么只要N/J>7.9,即平均每个汉字8比特以上，就有可能成功表示各 种可能的码组，但要使表示失败的概率任意小，则要求J足够大。 3.3.2变长编码 对于非等概率分布的无记忆离散信源的编码，采用可变长度的码字进行编码可获得更高 的编码效率，但其码字必须满足前缀条件，即任意一个码字不能是任何其它码字的前缀。 。Kraft不等式 一个包括有L个码字且都满足前缀条件的码字集是否存在，其充分和必要条件是： 22.s1 (3-3-5) 其中m,m2,n,分别为各个码字的长度 ·离散信源变长编码定理 【定理1】若一离散无记忆信源的熵为H(X),每个信源字符用m进制码字进行变长编码， 则一定存在一种无失真编码方法其码字平均长度下满足不等式： H≤R<W+1 logm logm (3-3-6) 【定理2】对于一个字符熵为H(X)的离散无记忆信源进行变长编码，必定存在一种无失 真编码方法，其平均信息率R满足不等式： 西安电子科技大学
第 3 章 通信信源与信源编码 西安电子科技大学 7 ( ) N R HX J ≡≥ + ε (3-3-3) 就可以保证编码失败的码组出现的概率 Pe可以任意小；反之，若码率 ( ) N R HX J ≡≤ − ε (3-3-4) 则编码失败码组出现的概率 Pe将随 J 的增大而趋于 100%。 此定理的含义是：对一个信源发出的符号序列进行定长分组编码，只要码率大于信源熵， 码组又足够长，则无失真编码失败的概率可以无穷小；而若码率小于信源熵，无失真编码失败 的可能性非常大。 【例】将一本中文书看作一个信源，如果所用汉字都包含在国标一级字表的 3763 个汉字之中，则国标 一级字表就是信源字符集。将书中的汉字用代码表示，本来需要用 12 比特长的代码才能表示一个汉字。但 是，假如根据该书中各种汉字出现的概率求得的信源熵 H X( ) =7.9 比特/字符，而将书中每 J 个汉字看作一 个码组用一个 N 比特的代码表示，那么只要 N / J >7.9，即平均每个汉字 8 比特以上，就有可能成功表示各 种可能的码组，但要使表示失败的概率任意小，则要求 J 足够大。 3.3.2 变长编码 对于非等概率分布的无记忆离散信源的编码，采用可变长度的码字进行编码可获得更高 的编码效率，但其码字必须满足前缀条件，即任意一个码字不能是任何其它码字的前缀。 z Kraft 不等式 一个包括有 L 个码字且都满足前缀条件的码字集是否存在，其充分和必要条件是： ∑= − ≤ L k nk 1 2 1 (3-3-5) 其中 L n ,n ,.,n 1 2 分别为各个码字的长度。 z 离散信源变长编码定理 【定理 1】若一离散无记忆信源的熵为 H X( )，每个信源字符用m 进制码字进行变长编码， 则一定存在一种无失真编码方法其码字平均长度 K 满足不等式： () () 1 log log HX HX K m m ≤< + (3-3-6) 【定理 2】对于一个字符熵为 H X( )的离散无记忆信源进行变长编码，必定存在一种无失 真编码方法，其平均信息率 R 满足不等式：
第3查通信信源与信源缩码 H(X)≤RH(X),就可以确保编码成功。 【例】仍以一本中文书中汉字编码为例，因为信源痛是H(X)=7.9比特序符：但因包含J个汉字的各 种可能码组出现的概率不同，我们采用m种比特数不同的码字表示各个码组，概率高的用短码，概率低的 用长码：那么只要码率（平均每个汉字编码的比特数）大于H(X),就可以确保编码成功。 3.3.3 Huffman编码算法 设一个离散信源共有n个信源字符{x,x2,x。}，字符的概率分布为： P(X=x)=p,i=l,2,n,并且B,+P,+.+p.=l:则采用Huffiman树形结构算法可以生成 个非等长的二进制码字集{G,92,C,},即码书，使码字集中各码字分别与信源字符集相对 应，即对应于x。该码书生成的步骤如下： ①比较n个概率值{P,P,P}的大小，将概率最小的两个字符，例如x和x,所对应码 字c和c,的最后一个比特分别指定为0和1； ②将这两个最小概率值合并，即P,=p+P,并用P取代P和P,得到树中第1个节点。 ③将P,与其它n-2个概率值进行比较，重新找出两个概率最小的，如果这两个概率值所 对应的信源字符，例如是x,和x,而不是前述的，和x,则将这两个信源字符所对应的码字c 和c的最后1比特分别指定为0和1：如果x与前述两个字符中的一个相同，例如x,=x,即 曾经分配过1比特，则将c,的倒数第2比特指定为0或1。 ④再次将两个新的最小概率值合并，得到树中一个新的节点，将此概率值与其它的-3 个（也可能还有n-2)概率值进行比较，重新找出两个概率最小的，如果这两个概率值所对应的 信源字符不包括在前面己分配过比特的码字，则将这两个码字的最后1比特分别指定为0和1： 如果这两个码字中有一个（或两个）曾经分配过比特，则将它所涉及的码字的前一比特指定为 0或1。 如此重复进行，直到所有的概率值合并为1，由此得到长短不一的n个码字，即构成一个 uffman树形码书。 【例】由7个字符构成的信源字符集，各字符出现概率分别为0.005,0.005,0.04,0.1,0.2,0.3， 0.35:那么按照上述编码方法设计Huffman码书的7个码字分别为：11111,11110,1110,110， 10,01,00。 西安电子科技大学
第 3 章 通信信源与信源编码 西安电子科技大学 8 HX R HX () () ≤ H X( ) ，就可以确保编码成功。 【例】仍以一本中文书中汉字编码为例，因为信源熵是 H X( ) =7.9 比特/字符；但因包含 J 个汉字的各 种可能码组出现的概率不同，我们采用 m 种比特数不同的码字表示各个码组，概率高的用短码，概率低的 用长码；那么只要码率（平均每个汉字编码的比特数）大于 H X( ) ，就可以确保编码成功。 3.3.3 Huffman 编码算法 设一个离散信源共有 n 个信源字符 { n x , x ,., x 1 2 } ，字符的概率分布为： ( ) 1, 2,., i i PX x p i n == = ，并且 1 2 . 1 n pp p + ++ = ；则采用 Huffman 树形结构算法可以生成 一个非等长的二进制码字集{ 1 2 , ,., n cc c }，即码书，使码字集中各码字分别与信源字符集相对 应，即 i c 对应于 i x 。该码书生成的步骤如下： ① 比较n 个概率值{ 1 2 , ,., n p p p }的大小，将概率最小的两个字符，例如 i x 和 j x 所对应码 字 i c 和 j c 的最后一个比特分别指定为 0 和 1； ② 将这两个最小概率值合并，即 ij p = i p + j p ，并用 ij p 取代 i p 和 j p ，得到树中第 1 个节点。 ③ 将 ij p 与其它n -2 个概率值进行比较，重新找出两个概率最小的，如果这两个概率值所 对应的信源字符，例如是 i' x 和 j' x ，而不是前述的 i x 和 j x ，则将这两个信源字符所对应的码字 i' c 和 j' c 的最后 1 比特分别指定为 0 和 1；如果 i' x 与前述两个字符中的一个相同，例如 i' x = i x ，即 曾经分配过 1 比特，则将 i c 的倒数第 2 比特指定为 0 或 1。 ④ 再次将两个新的最小概率值合并，得到树中一个新的节点，将此概率值与其它的n -3 个（也可能还有n -2）概率值进行比较,重新找出两个概率最小的,如果这两个概率值所对应的 信源字符不包括在前面已分配过比特的码字,则将这两个码字的最后 1 比特分别指定为 0 和 1； 如果这两个码字中有一个（或两个）曾经分配过比特，则将它所涉及的码字的前一比特指定为 0 或 1。 如此重复进行，直到所有的概率值合并为 1，由此得到长短不一的n 个码字，即构成一个 Huffman 树形码书。 【例】由7个字符构成的信源字符集，各字符出现概率分别为0.005, 0.005, 0.04, 0.1, 0.2, 0.3, 0.35;那么按照上述编码方法设计 Huffman 码书的 7 个码字分别为：11111，11110，1110，110， 10，01，00
第3章通信信源与信源编码 字概率自信码 X3 88 0.04 0.00576438 7 04 0.005 HX0=2.1 =2.21 图3.3-1 Huffman编码举例 3.3.4 Lempel-Ziv编码算法 L-Z算法6，刀是一种不涉及信源统计特性的通用编码算法，它是一种可变一固定码长的无失 真编码方法，广泛用于计算机文件压缩。 ·算法简述 LV算法是一种由变长到定长的编码。待编码的信源符号序列被划分为许多长短不同的 片段(phrases),并同时自动产生一个字典，然后用这个字典中的码字对于各个片段进行编码， 接收端采用同样的字典进行译码。 设片段长度的最大值预定为L,缓存器的长度为则编码器采用固定长度L的码字对 各个片段进行编码时，码长L应满足下式才能完全成功编码而又不产生缓存器溢出： L.=1+Int(Log(n-L.))+Ini(LogL,) (3-3-8) 3.4无记忆序列的压缩编码 一个连续随机过程，在按照采样定理离散化为样点序列或矢量序列后，各个样点或矢量的 分量都还是模拟量，要表示为有限字长的数字需要进行量化和编码：如何进行量化和压缩编码 才能效率高而代价小，需要定义失真测度和率失真函数来衡量失真代价的大小。 3.4.1率失真函数 ·率失真函数的定义 一个无记忆信源X,设x表示该信源输出的某个样点的值，×表示x经编码后恢复的值， d(x,x)表示二者的相对失真量，Ed(x,x】为编码大量样点时每个样点所产生的平均失真量。 为了以小于或等于平均失真量D对这个信源的输出进行编码，平均每个信源符号所需的最低 比特率R(D),称为率失真函数(Rate-distortion Function): 西安电子科技大学
第 3 章 通信信源与信源编码 西安电子科技大学 9 图 3-3-1 Huffman 编码举例 3.3.4 Lempel-Ziv 编码算法 L-Z 算法[6,7]是一种不涉及信源统计特性的通用编码算法，它是一种可变—固定码长的无失 真编码方法，广泛用于计算机文件压缩。 z 算法简述 L-V 算法是一种由变长到定长的编码, 待编码的信源符号序列被划分为许多长短不同的 片段(phrases)，并同时自动产生一个字典，然后用这个字典中的码字对于各个片段进行编码， 接收端采用同样的字典进行译码。 设片段长度的最大值预定为 Ls ，缓存器的长度为n ；则编码器采用固定长度 Lc 的码字对 各个片段进行编码时，码长 Lc 应满足下式才能完全成功编码而又不产生缓存器溢出： 1 ( ( )) ( ) c ss L Int Log n L Int LogL =+ − + (3-3-8) 3.4 无记忆序列的压缩编码 一个连续随机过程，在按照采样定理离散化为样点序列或矢量序列后，各个样点或矢量的 分量都还是模拟量，要表示为有限字长的数字需要进行量化和编码；如何进行量化和压缩编码 才能效率高而代价小，需要定义失真测度和率失真函数来衡量失真代价的大小。 3.4.1 率失真函数 z 率失真函数的定义 一个无记忆信源 X ，设 x 表示该信源输出的某个样点的值， x'表示 x 经编码后恢复的值， dxx ( , ')表示二者的相对失真量， E[d(x, x')]为编码大量样点时每个样点所产生的平均失真量。 为了以小于或等于平均失真量 D 对这个信源的输出进行编码，平均每个信源符号所需的最低 比特率 R( ) D ，称为率失真函数(Rate-distortion Function)： 字 概率 自信 码 x2 0.30 1.7370 01 x3 0.20 2.3219 10 x5 0.04 4.6439 1110 x6 0.005 7.6439 1111 x7 0.005 7.6439 1111 H(X)=2.11 R =2.21
第3章通信信導与信源编码 10 R()=min (3-4-1) 其中1(X,X)是信源原始输出和信源编码结果之间的互信息。 对于无记忆矢量序列中矢量的编码，同样可以定义率失真函数，矢量x经编码再恢复后的 矢量为x,其失真量为d(x,x)。 ·无记忆高斯信源的率失真函数 如果用每个符号的均方误差来度量失真，那么表示一个时间高散、幅度连续、无记忆高斯 信源的输出所需的最低信息速率应为： R(D)=2 :1D) (3-4-2) 0 当D≥o2J 【限失真的信源编码定理】对于任意给定的失真D,一定存在一种编码方式，其最小信息速 率为(D)比特/符号，而译码恢复信源输出时所产生平均每个符号的失真值可以任意逼近D。 【定理一(D)的上界】对于零均值、有限方差σ：（采用均方差失真测度）、幅度连续的 无记忆信源，其率失真函数的上界为： R(D)1D)(0sD≤) (3-4-3) 2.0 1.0 0应的暖 图34-1连续幅度无记忆高斯信源的率失真函数 这个上界就是高斯信源的率失真函数，如图341所示。本定理表明：在指定均方误差的 限制下，表示一个高斯信源输出信息所需的信息速率是最高的，比其它任何信源的都高。 3.4.2采样信号的量化编码 连续信号x)的采样通常采用固定的时间间隔，采样值被量化为L=2“种电平 {x,x,x,那么每一个样点值可以用一个K比特的二进制数表示：如果输入样点值x)与 x之间失真测度值d((),x)最小，就将x)量化为x,而将其下标k作为其编码。 西安电子科技大学
第 3 章 通信信源与信源编码 西安电子科技大学 10 R( ) D = ( '| ): [ ( , ')] min ( , ') p x x Ed xx D I X X ≤ (3-4-1) 其中 IXX ( , ') 是信源原始输出和信源编码结果之间的互信息。 对于无记忆矢量序列中矢量的编码，同样可以定义率失真函数，矢量x 经编码再恢复后的 矢量为x， ，其失真量为d(, ) x x， 。 z 无记忆高斯信源的率失真函数 如果用每个符号的均方误差来度量失真，那么表示一个时间离散、幅度连续、无记忆高斯 信源的输出所需的最低信息速率应为： 2 2 2 2 1 ( /) 0 2 0 ( ) x x x g Log D D D R D σ σ σ ≤ ≤ ≥ = ⎧ ⎫ ⎪ ⎪ ⎨ ⎬ ⎪ ⎪ ⎩ ⎭ 当 当 (3-4-2) 【限失真的信源编码定理】对于任意给定的失真 D ，一定存在一种编码方式，其最小信息速 率为 R( ) D 比特/符号，而译码恢复信源输出时所产生平均每个符号的失真值可以任意逼近 D。 【定理— R( ) D 的上界】对于零均值、有限方差 2 σ x （采用均方差失真测度）、幅度连续的 无记忆信源，其率失真函数的上界为： R( ) D 2 2 1 ( /) 2 Log D σ x ≤ (0≤ D ≤ 2 σ x ) (3-4-3) 2 / D σ x 图 3-4-1 连续幅度无记忆高斯信源的率失真函数 这个上界就是高斯信源的率失真函数，如图 3-4-1 所示。本定理表明：在指定均方误差的 限制下，表示一个高斯信源输出信息所需的信息速率是最高的，比其它任何信源的都高。 3.4.2 采样信号的量化编码 连续信号 x( )t 的采样通常采用固定的时间间隔，采样值被量化为 2K L = 种电平 { L x , x ,., x 1 2 }，那么每一个样点值可以用一个 K 比特的二进制数表示；如果输入样点值 x( )t 与 k x 之间失真测度值 ( ( ), ) k d xt x 最小，就将 x( )t 量化为 k x ，而将其下标k 作为其编码