第5章 信源编码part2v1(74p)

第5章信源编码信源编码（主要内容）信源编码定理信源编码概念香农第一定理香农第三定理信源编码方法离散信源编码连续信源编码相关信源编码变换编码2024/3/202变长码的编码方法发展比较成熟，常见的方法有：香农编码费诺编码霍夫曼编码游程编码冗余位编码2024/3/203香农编码设有离散无记忆信源，记作：香农编码的编码步骤如下：(2)令，并用表示第个码字之前的累加概率，即：。

将信源符号按概率从大到小依次排列。设排序后的消息分别记为，对应概率为(4)将累加概率用二进制表示，去除小数点，根据码长并取小数点后共

位作为的编码。(3)确定满足下列不等式的整数,并令为第个码字的长度。编码步骤香农编码-例1解:(1)按概率从大到小依次排列(2)计算累加概率例

对信源编香农码。page7(3)计算码字长度注意：是对算自信息量，而不是对算。大于等于自信息量最小整数page8(4)根据累加概率进行编码注意：此处是按

进行编码，而不是按

编码。十进制小数二进制小数十进制整数二进制整数码字码字码字注意补零注意补零page10码字码字码字注意补零码字注意补零page11码字码字注意补零码字注意补零码字码字page12码字码字码字码字码字码字注意补零注意补零检验是否为即时码？计算编码效率折算后，平均每个信源符号的最大可能载信量要求平均每个信源符号传递的信息量通过以上实例发现，香农码的效率并不算高。当所有消息的概率为效率可达100%。香农编码-例2page15解:(1)按概率从大到小依次排列例编二进制香农码。对(2)计算累加概率(3)计算各码字长度码字01011101101111(4)根据进行编码(5)计算编码效率变长码的编码方法发展比较成熟，常见的方法有：香农编码费诺编码霍夫曼编码游程编码冗余位编码2024/3/2018费诺编码设有离散无记忆信源，编码步骤如下：

将信源符号按概率从大到小依次排列。设排序后的消息分别记为x1,x2,…,xn。(2)将信源符号按概率分成若干组，使每组的概率的和尽量接近或相等。若编二元码就分两组，编元码就分成组。(3)给每组分配一位码元，码元的分配是任意的。(4)对每一分组按上述原则继续分组，直到概率不可分。page20例

对信源编二元费诺码。解:(1)按概率从大到小依次排列(2)按概率分组(3)为每组分配码元(4)继续分组page21检验是否为即时码？计算编码效率

从计算结果可看出，编码效率较高。但这并不意味着费诺码的效率一定高于香农码。

实践表明，费诺码比较适合于每次分组的概率的和比较接近的情况。最理想的情况是：每次分组的概率的和都恰好相等，这时编码效率可达100%。例

对信源编二元费诺码。解:(1)按概率从大到小依次排列(2)按概率分组(3)为每组分配码元(4)继续分组(5)编码效率变长码的编码方法发展比较成熟，常见的方法有：香农编码费诺编码霍夫曼编码（哈夫曼编码）游程编码冗余位编码2024/3/2024哈夫曼编码设有离散无记忆信源，二元码的编码步骤如下：

将信源符号按概率从大到小依次排列。设排序后的消息分别记为。

给两个概率最小的信源符号和各分配一个码符号“0”和“1”，将这两个信源符号合并成一个新符号，并用作为新符号的概率，结果得到一个只包含个信源符号的新信源。将该信源称为第一次缩减信源，用表示。page26(3)将缩减信源的符号仍按概率从大到小的顺序排列，重复步骤2，得到只含个符号的缩减信源。(4)重复上述步骤，直至缩减信源只剩两个符号为止。此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。例

对编二元哈夫曼码(1)排序(2)第一次缩减信源(3)第二，三，…次缩减信源(4)最后一级概率码字page28检验是否为即时码？计算编码效率：从计算结果可看出，编码效率较高。page30问题：哈夫曼方法所编的码字是否唯一？例

对编二元哈夫曼码。解:(1)排序答案：不唯一。

1.每次分配码字，0和1都是任意的。

2.当新符号的概率与已有符号相等时，这些符号谁在前，谁在后，也会导致编码结果不同；而且所得编码方案性能也有差异。page31(2)第一次缩减信源(3)第二，三，…次缩减信源(4)最后一级概率码字方案一：每次符号概率相等时，新码字都排在最后面。码元/符号page32概率码字方案二：每次符号概率相等时，新码字都排在最上面。码元/符号page33方案一方案二从直观上看，方案二的各码字之间，码字长度更均匀。由此得出结论：

在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠上的位置，这样可使合并后的新符号重复编码次数减少，码字间长度更加均匀。练习：设有信源

(1)编二进制哈夫曼码(2)计算平均码长及编码效率码字概率(1)(2)计算平均码长及编码效率比特/符号多元哈夫曼编码page36多（）元码的编码步骤：(1)按概率从大到小排序。(2)挑出概率最小的

个信源符号，分别赋予码符号，并将概率的和赋予合并后的新符号，得到。(3)按相同步骤计算。(4)直到最后一级，倒序读出码字。多元码的编码过程与二元码基本类似，但可能会遇到如下问题：可能出现最后一级信源，信源符号数不足

个的情况。page38在码树图中，某些分枝从第一级就被砍掉，从而造成平均码长偏长的情况。解决办法：从最后一级缩减信源倒着排，保证最后一级有m个符号。要求最后一级缩减信源保证有m个符号，则有：倒数第二级倒数第三级……第一级例：，求：第一级信源符号所需保留个数。为保证每次缩减均为m个变1个，第一级符号所缺的个数：第一级符号保留的个数：第一级保留【保留+欠缺=m】其中：*page40方案1：码元/符号方案2：码元/符号page41计算方案2的编码效率：练习：(1)编三进制哈夫曼码(2)计算平均码长及编码效率第一级应保留解：(1)关键是求第一级信源应保留的符号个数page42(2)计算平均码长及编码效率码元/符号比特/符号2024/3/2043r元霍夫曼码二进制霍夫曼码的编码方法可以很容易推广到r进制的情况。只是编码过程中构成缩减信源时，每次都是将r个概率最小的符号合并，并分别用0,1,…,(r-1)码符号表示。例设有离散无记忆信源码符号集X＝(0,1,2)，试构造一种三进制霍夫曼码。2024/3/2044其中信源s9是增补的，令其概率为零.码符号集X＝(0,1,2)，试构造一种三进制霍夫曼码page45定理：哈夫曼码是紧致码。说明：这里只证明二元哈夫曼码是紧致码，其结论可推广到多元哈夫曼码。思路：采用类似数学归纳法的证明方法。证明最后一级缩减信源是紧致码假设级缩减信源是紧致码证明级缩减信源是紧致码证明：对于二元码，最后一级缩减信源只有2个信源符号，因此一定是紧致码。消息数级缩减信源的平均码长第i个消息的概率第i个消息的码长在所有可能的唯一可译码编码方案中，的长度最短。假设级缩减信源对应的编码是紧致码，因此有：对于级缩减信源，一定有条消息，而且其中某两个消息的概率的和一定为级某消息的概率。page47只要是紧致码，则缩减前信源的编码也是紧致码与码长无关的常数变长码的编码方法发展比较成熟，常见的方法有：香农编码费诺编码霍夫曼编码游程编码冗余位编码2024/3/2048游程编码与游程变换2024/3/2049“0”游程“1”游程游程长度序列(游程序列)：何谓游程？回答：数字序列中连续出现相同符号的一段。例：二元序列：…000101110010001…前面方法针对无记忆信源，对于有记忆信源前面方法编码效率不高，一般采用其它编码。如：游程编码。游程变换:

用交替出现的“0”游程和“1”游程的长度，来表示任意二元序列…31132131…为多元序列游程编码与游程变换说明说明：游程变换规定游程序列从“0”开始游程变换是一一对应变换，也是可逆变换它减弱了二元序列的相关性可对变换得到的多元序列采用其它编码方法，如：哈夫曼编码，可进一步压缩信源，提高通信效率多元序列也可以变换成游程序列，但是需要增加标志位，可能会抵消压缩编码得到的好处，意义不大。所以主要讨论二元序列。2024/3/2050游程序列的概率特性2024/3/2051问题：变换得到的游程序列的概率特性？分析：若二元序列的概率特性已知，可计算出游程序列的概率特性。因为原因二元序列与游程序列一一对应。“0”游程长度概率为：p[L(0)]=p0L(0)-1p1;

“0”游程长度的熵为：H[L(0)]=H(p0)/p1;“0”游程序列的平均长度为：l0=E[L(0)]=1/p1设二元序列为独立序列，其中“0”和“1”出现的概率分别为p0和p1，L(0)为某“0”游程长度，则可以推出：游程序列的概率特性2024/3/2052当二元序列有相关性时，需要讨论联合（或条件）概率，有类似结论。下面进行推导。算得原二元序列的熵为：H(X)={H[L(0)]+H[L(1)]}/(l0+l1)=H(p0)=H(p1)“1”游程可推出类似结论：p[L(1)]=p1L(1)-1p0;H[L(1)]=H(p0)/p0;l1=E[L(1)]=1/p02024/3/20530/1游程长度的概率：p[L(0)]/p[L(1)]0/1游程长度的概率：p[L(0)]/p[L(1)]2024/3/2054同理，有2024/3/2055平均游程长度：E[L(0)]/E[L(1)]平均游程长度：2024/3/20560/1游程长度的熵：H[L(0)]/H[L(1)]0/1游程长度的熵：H[L(0)]/H[L(1)]57二元序列的熵H(X)0游程序列的熵与1游程序列的熵之和除以它们的平均游程长度之和。H(X)={H[L(0)]+H[L(1)]}/(l0+l1)={H(p0)/p1+H(p0)/p0

}/(1/

p1+1/p0)=H(p0)=H(p1)游程变换后符号熵没有变。原因：游程变换是一一对应变换2024/3/2058有相关性的二元序列游程变换若原二元序列是二阶马氏链，由它变换而来的游程序列将是独立序列。0游程：10X；1游程：01X对于高阶马氏链，若阶数大于2，经变换的游程序列将不再是独立序列。如三阶马氏链：Y10X→一阶马氏链一般k阶马氏链，由之变换而来的游程序列将为k-2阶马氏链。2024/3/2059游程序列编码从前面可知，通过游程变换来解除或减弱二元序列的相关性是相当有效的，因此对游程序列进行哈夫曼编码可达到较高的编码效率。分别对“0”游程和“1”游程的长度进行哈夫曼编码，当0游程和1游程的编码效率都很高时，采用游程编码的效率也很高。游程长度：60建立游程长度和码字间的码表困难实际上，游程长，出现概率小概率小的码字对平均码长影响小对长码进行截断处理游程长度与码字之间的码表2024/3/2061取适当值n，游程长度为1,2,…,2n-1,2n，所有大于2n者，都按2n处理。所有长度大于等于2n的游程，只有一个码字C，需要按右表进一步区分。当游程长度大于或等于2n+1时，需要两个或两个以上的C。概率小，码字长。0游程和1游程应分别编码，建立各自的码字和码表。码字可重复，C必须不同。如：C0

或C1游程长度≥2nC之后为一个n位的自然码（C0

或C1）2nC00…002n+1C00…01……2n+1-1C11…112n+1

C00…00C00…002n+2-1C00…00C11…11……变长码的编码方法发展比较成熟，常见的方法有：香农编码哈夫曼编码费诺编码游程编码冗余位编码2024/3/2062冗余位编码（Lynch-Davission）何谓冗余位？回答：信源序列中不携带信息的符号。

比如：语音中的话语间歇、图像的单一背景部分。2024/3/2063分析：此类符号，除了符号数目或所占时长外，可不必传送，去掉一部分可以提高通信效率。冗余位编码：

分解信源序列为冗余位序列和冗余位序列，分别编码。冗余位编码（Lynch-Davission）设有多元信源序列：x

为信息位；y

冗余位x1,x2,…xm1,y,y,…,y,xm1+1,xm1+2,…,xm2,y,y,…

可用下面两个序列来代替：冗余位序列：111,…,100,…,000111,…,111000信息位序列：x1,x2,…xm1,xm1+1,xm1+2,…,xm2,…2024/3/2064一个多元信源序列=

一个二元序列+一个缩短的多元序列对两个序列分别编码，可有效地压缩信源二元序列进行游程编码多元序列直接采用哈夫曼编码分帧传送冗余位序列：L-D编码要求同时传送两个序列，才能在接收端实时恢复出原来的多元信源序列，实用上有困难，通常采用分帧传送的方式L-D编码：在冗余位序列中取N个符号作为一帧，编成一个码字，其后就把本帧中的信息位按序排列，再取下一帧作同样处理。在接收端根据这些码字和信息序列进行译码。每个码字中含有：信息位的数量Q和位置信息T2024/3/2065L-D编码的译码过程收端收到Q和T后，如下译码，求解出信息位的位置：2024/3/2066编码Q和TQ可以取0到N的各种值，共N+1种，故2024/3/2067例：对一冗余位序列编L-D码2024/3/2068一冗余位序列：001000000010000，N=15这里Q=2，n1=3，n2=11，则Q=2和T=47的译码过程收端收到Q=2和T=47后，如下译码：2024/3/2069Q=2和T=47的译码过程-续2024/3/2070对例题的说明当Q为0或N时，相当于全0或全1序列，此时T值为0，在编码时只需编Q值，对于N=15，得0000或1111L-D编码与哈夫曼码不同，不需要已知概率特性。也就是编成的码字与概率特性无关，而与一