杭电-媒体信号编码计算题整理

1、补充计算题：第4 ，5， 6，9章4.1Huffman编码4.1.1Huffman码的构造1. 最佳码和最佳编码定理对于某一信源和某一码符号集来说，若有一个唯一可译码，其平均长度小于所有其它唯一可译码的平均长度，则该码称为紧致码，或称最佳码。变字长最佳编码定理：在变字长编码中，对于概率大的信源符号编以短字长的码，对于概率小的符号编以长字长的码；2.Huffman编码码字本身和码长序列不是唯一的，但是平均码长是唯一的。码方差越小，说明越接近等长码，因而质量越好。在Huffman编码过程中，为得到码方差最小的码，当重新排列缩减信源的概率分布时，应使合并的概率和尽量处于最高的位置。3. 对于r元编码

2、，信源X的符号个数q必须满足 q=(r1)+r (4-2)其中, 表示缩减的次数，r1为每次缩减所减少的信源符号个数。若q不满足式q=(r1)+r时，则增补一些概率为零的信源符号，即Pq+1=Pq+2=Pq+t=0使得q+t满足式q+t=(r1)+r。这样得到的r元Huffman码一定是紧致码。 【例4-3】信源X有6种符号，输出概率为0.32、0.22、0.18、0.16、0.08和0.04，试用三元Huffman码编码该信源。【解】在本例中，r=3，若取q=6，则不能找到满足q=(r1)q+r的整数。因此必须采用虚设符号方法，添设1个概率为0的符号，使得q=7，=2，从而满足式q=(r1)

3、+r。图4-2表4-3中三元Huffman码的码树4.4.2算术编码的基本原理1.借鉴香农用n个符号序列Sn出现的概率的累计分布C(Sn)，在区间C(Sn)，C(Sn)+A(Sn)选取一点，用其二进制小数表示编码，并把C(Sn)和A(Sn)的计算转换成递归运算。A(Sn)称为符号序列Sn编码可用空间或值域(Range)，它的大小=p(Sn)，即符号序列Sn的出现概率。设在上一时刻信息的符号序列为S，这一时刻信源发出符号x，序列发展成为新的序列Sx。递归计算序列Sx的累计分布函数C(Sx)和编码可用空间A(Sx)的递推公式如下： (1) 累计分布函数的递推：C(Sx)=C(S)+A(S)P(x)

4、(2) 编码可用空间的递推：A(Sx)=p(Sx)=p(x)A(S) p(x)为符号出现的概率，P(x)为符号x的累积概率，如式(4-7)所示。2.可见，算术编码在传输任何符号x之前，信息的完整范围是C()，C()+A()=0，1)。当处理符号x后区间宽度就依据x的出现概率p(x)变窄，大概率符号比小概率符号使区间变窄的范围要小。然后在区间C(S)，C(S)+A(S)找一代表点，对其值进行编码。符号序列越长，相应的子区间就越窄，编码表示该子区间所需的比特数也就越多。3【例4-9】信源符号集S=a，b，c，d，e，!，其中前5个符号为实际信源符号，最后一个符号“！”用来表示编码结束。各概率和初始

5、区间范围如表4-15所示，试编码字符串dead。【解】编码过程如下：“d”，C(Sd)=C()+P(d)A()=P(d)= 0.4 A(Sd)=p(d)A()=0.3 区间C(S)，C(S)+A(S)=0.4，0.7)“e”，C(Se)=C(S)+P(e)A(S)=0.4+0.70.3=0.61 A(Se)=p(e)A(S)=0.20.3=0.06 区间0.61，0.67)“a”， C(Sa)=C(S)+P(a)A(S)=0.61 A(Sa)=p(a)A(S)=0.20.06=0.012 区间0.61，0.622)“d”，C(Sd)=C(S)+P(d)A(S)=0.61+0.40.012=0.

6、6148 A(Sd)=p(d)A(S) =0.30.012=0.0036 区间0.6148，0.6184)编码符号“!”后的区间为0.61804，0.6184)，区间宽度A(S) =0.000 36。（C(S!)=C(S)+P(!)A(S)=0.6148+0.90.0036=0.61804）解码器无需知道最终区间的两个端点值，只知道区间内的一个值就够了。比如知道值0.6182，解码端的过程如下：由于0.61820.4，0.7)，故知道第1个符号为d；则下一个符号的区间范围应该为：a0.4，0.46)，b 0.46，0.49)，c 0.49，0.52)，d0.52，0.61)，e 0.61，0.

7、67)，! 0.67，0.7)。由于0.61820.61，0.67)，故知道第2个符号为e；注：00.2 0.20.3 0.30.4 0.40.7 0.70.9 0.91 0.6182 0.40.46 0.460.49 0.490.52 0.520.61 0.610.67 0.670.7以此类推，可以解码出符号a，d，！。当解码出！符号时，解码完成。4.3.2Golomb编码如果b2k，前缀码位数：+1, 尾码是对的余数r=n1qb的二进制编码，r0, 1, , b1。余数前个用比特编码，后面用比特编码，且最高位为1。（例b=3，余数列出：0,1,2。余数前1位用1比特编码，记0；后面三个每个

8、用2比特编码，记10,11）(2) 如果b=2k，前缀码产生规则同b2k时相同；尾码则直接用n的二进制表示的最低k位表示。（例n=1，二进制表示001；b=4=22，k=2,取后两位01；n=2,010，取后两位10）【例4-6】给出b=3，4，5时的Golomb码。【解】尾码：如果取b=3，则可能的余数为0、1、2，第1个余数用=1比特编码；后面余数用=2比特编码，高位为1保持尾码的前缀性；因此余数与尾码的对应关系为00、110、211； 前缀码：根据前缀码位数+1，对于n=1, 2, ，其前缀码的位数分别为1, 1, 1, 2, 2, 2，位。若取表4-9右边一列的一元码字，则分别为1,

9、1, 1, 01, 01, 01，。4.5.2 LZW算法图4-9LZW编码算法流程【例4-12】试对一个最简单的2字符串“ABBBABAAB”作LZW编码。【解】根据图4-9给出的LZW编码算法流程，可以得到如下的编码步骤：步骤0：将A及B字符存入字典里，编码成索引值1及2；并读入第一字符A，前缀串S=A。步骤1：读入下一个字符c=B，串Sc=AB不在码表中，输出串S=A在字典里的索引值1；并将新的字符串AB存入字典里，索引值=3；最后置S=B。步骤2：读入下一个字符c=B，串Sc=BB不在码表中，输出串S=B在字典里的索引值2；并将新的字符串BB存入字典里，索引值=4；最后置S=B。步骤3

10、：读入下一个字符c=B，串Sc=BB已经在码表中，置S=BB。步骤4：读入下一个字符c=A，串Sc=BBA不在码表中，输出串S=BB在字典里的索引值4；并将新的字符串BBA存入字典里，其索引值=5；最后置S=A。步骤5：读入下一个字符c=B，串Sc=AB已经在码表中，置S=AB。步骤6：读入下一个字符c=A，串Sc=ABA不在码表中，输出串S=AB在字典里的索引值3；并将新的字符串ABA存入字典里，其索引值=6；最后置S=A。步骤7：读入下一个字符c=A，串Sc=AA不在码表中，输出串S=A在字典里的索引值1；并将新的字符串AA存入字典里，其索引值等于7；最后置S=A。 步骤8：读入下一个字符

11、c=B，串Sc=AB已经在码表中，置S=AB。 步骤9：读入下一个字符c= ，输入已经穷尽，输出串S=AB在字典里的索引值3，编码结束。第五章5-20、设有如下图所示的8*8灰度图像，求： 计算该图像的熵； 对该图像做前值预测（即列差值，8*8区域外图像取零值），试给出误差图像及其熵值； 再对上步误差图像做行差值，继续计算误差图像及其熵值； 试比较上述三个熵值，可能得出什么结论？解：灰度值3、4、5、6、7的个数分别为：7、32、16、8、1；所以该图像的熵为：前值预测图像为：（前一列赋给当前列）所以误差图像为：(就是原图像每个元素-前值预测)3.对上步误差图像做行差值：(前一行赋给当前行)误

12、差图像为：比较上述三个熵值可看出误差图像的熵值越来越小，即误差图像所携带的信息量在减小，所以相邻像素间的相关性减小，从而保证了重建图像与原始图像的一致性。第六章6-2 试对协方差矩阵，求KTL矩阵，并验证该矩阵可以将 对角化。解:由 求得正交矩阵为有 ，即矩阵可以将对角化6-11、试对题6-5所示的图像数据进行哈尔小波变换（取），并求出重建图像数据。 解:求均值与差值：R0=142,144,151,156,156,157,156,156(第一行像素值) N0= 143, 153.5, 156.5, 156, -1, -2.5, -0.5, 0(前4个数：R0每一对像素平均值，后4个数：R0每一对像素差值的一半) N1= 148.25, 156.25, -5.25, 0.25, -1,-2.5, -0.5,0（前4个数：前2个N0前4个数每一对像素平均值，后2数N0前4个数每一对像素差值的一半；后4个数：直接复制N0对应位置） N2=152.25,-4 , -5.25, 0