信息论基础与编码(第五章)

信息论基础与编码(第五章)5-1有一信源，它有六种可能的输出，其概率分布如下表所示，表中给出了对应的六种编码和。（1）求这些码中哪些是唯一可译码；（2）求哪些是非延长码（即时码）；（3）对所有唯一可译码求出其平均码长。消息概率1/20000001011/40010110100000011/1601001111011010011001/160110111111011000101011/16100011111111010011101101/161010111111111101111110111解：（1）1,2,3,6是唯一可译码；(2)1,3,6是即时码。5-2证明若存在一个码长为的唯一可译码，则一定存在具有相同码长的即时码。证明：由定理可知若存在一个码长为的唯一可译码，则必定满足kraft不等式1。由定理4可知若码长满足kraft不等式，则一定存在这样码长的即时码。所以若存在码长的唯一可译码，则一定存在具有相同码长P（y=0）的即时码。5-3设信源，。将此信源编码成为r元唯一可译变长码（即码符号集），其对应的码长为（）=（1，1，2，3，2，3），求r值的最小下限。解：要将此信源编码成为 r元唯一可译变长码，其码字对应的码长（l1,l2,l3,l4,l5,l6）=(1,1,2,3,2,3)必须满足克拉夫特不等式，即所以要满足，其中r是大于或等于1的正整数。可见，当r=1时，不能满足Kraft不等式。当r=2,，不能满足Kraft。当r=3,，满足Kraft。所以，求得r的最大值下限值等于3。5-4设某城市有805门公务电话和60000门居民电话。作为系统师，你需要为这些用户分配电话号码。所有号码均是十进制数，且不考虑电话系统中0、1不可用在号码首位的限制。（提示：用异前缀码概念）（1）如果所有公务电话号码为3位长，所有居民电话号码等长，求居民号码长度的最小值；（2）设城市分为A、B两个区，其中A区有9000门电话，B区有51000门电话。现进一步要求A区的电话号码比B区的短1位，试求A区号码长度的最小值。解：(a)805门电话要占用1000个3位数中的805个，即要占用首位为0～7的所有数字及以8为首的5个数字。因为要求居民电话号码等长，以9为首的数字5位长可定义10000个号码，6位长可定义100000个号码。所以。或由Craft不等式，有解得，即(b)在(a)的基础上，将80为首的数字用于最后5个公务电话，81～86为首的6位数用于B区51000个号码，以9为首的5位数用于A区9000个号码。所以，。或由Draft不等式，有或解得即5-5求概率分布为的信源的二元霍夫曼码。讨论此码对于概率分布为的信源也是最佳二元码。解：信源的概率分布为：二元霍夫曼码：00，10，11，010，011，码长：2，2，2，3，3当信源给定时，二元霍夫曼码是最佳二元码。所以对于概率分布为的信源，其最佳二元码就是二元霍夫曼码。这二元霍夫曼码一定是三个信源符号的码长为2（码符号/信源符号），另二个信源符号的码长为3（码符号/信源符号），其平均码长最短。因此，上述对概率分布为信源所编的二元霍夫曼码也是概略分布为信源的最佳二元码。5-6设二元霍夫曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这些霍夫曼码的信源的所有概率分布。解：由意假设信源所发出的是个符号的概率为由霍夫曼编码的特点知：根据霍夫曼编码的，每次概率最小的两个信源符号合并成一个符号，构成新的缩减信源，直至最后只剩两个符号。而且当缩减信源中的所有符号概率相等时，总是将合并的符号放在最上面。所以，对于二元霍夫曼码为（00，01，10，11）来说，每个信源都要缩减一次，所以要大于和，这时必有同理对于二元霍夫曼码为（0，10，110，111）有信源概率分布满足以上条件则其霍夫曼编码符合题意。5-7设一信源有K=6个符号，其概率分别为：，，，对该信源进行霍夫曼二进制编码，并求编码效率。解：相应的Huffman编码是：{1,01,001,0001,00000,00001}。平均码长=1.95，熵=1.945-8设信源概率空间为：=，（1）求和信源冗余度；（2）设码符号为X={0,1}，编出S的紧致码，并求紧致码的平均码长；（3）把信源的N次无记忆扩展信源编成紧致码，试求N=2，3，4，时的平均码长；（4）计算上述N=1，2，3，4这四种码的编码效率和码冗余度。解：（1）信源其0.469比特/符号剩余度0.531=53.1％（2）码符号X={0,1}，对信源S编紧致码为：，其平均码长=1码符号/信源符号(3)当N=2时=紧致码（即霍夫曼码）为码字0,10,110,111码长1,2,3,3平均码长=0.645码符号/信源符号N=3时，=对信源进行霍夫曼编码，其紧致码为码字0,100,101,110,11100,11101,11110,11111码长1,3,3,3,5,5,5,5平均码长=0.533码符号/信源符号N=4时，=对信源进行霍夫曼编码，其紧致码为码字0,100,101,110,1110,111110,1111000,1111001,码长1,3,3,3,4,6,7,7,码字1111010,1111011,1111110,111111101,111111110,111111111,1111111000,1111111001码长7,7,7,9,9,9,10,10平均码长=0.493码符号/信源符号N=时，根据香农第一定理，其紧致码的平均码长=0.469码符号/信源符号(4)编码效率(r=2)码剩余度1－(r=2)所以N=1编码效率0.469码剩余度0.531=53.1%N=20.7270.273=27.3%N=30.8800.120=12%N=40.9510.049=4.9%从本题讨论可知，对于变长紧致码，当N不很大时，就可以达到高效的无失真信源编码。5-9设信源空间为：=，码符号为X={0,1,2}，试构造一种三元紧致码。解：得信源符号s1s2s3s4s5s6s7s8三元紧致码100022021220100115-10某气象员报告气象状态，有四种可能的消息：晴、云、雨和雾。若每个消息是等概的，那么发送每个消息最少所需的二元脉冲数是多少？又若四个消息出现的概率分别是1/4，1/8，1/8和1/2，问在此情况下消息所需的二元脉冲数是多少？如何编码？解：第一种情况：需要二元脉冲数两个，可表示四种状态，满足我们的要求。第二种情况：我们采用霍夫曼可编为1/2编为1；1/4编为01，1/8编为000和001，脉冲数显然。5-11若某一信源有个符号，并且每个符号等概率出现，对这信源用最佳霍夫曼码进行二元编码，问当和（是正整数）时，每个码字的长度等于多少？平均码长是多少？解：当时用霍夫曼编码方法进行最佳编码，由于每个符号是等概率分布的，所以每个符号码长应相等，这样平均码长最短，而且信源符号个数正好等于，则满足：，所以每个码字的码长。当个1时，因为每个符号等概率分布出现，所以每个符号的码长也应该基本相等，但现在信源符号个数不是正好等于，所以必须有两个信源符号的码长延长一位码长，这样平均码长最短。所以时个码字的码长为，其余2个码字的码长为。平均码长。5-12若有一信源每秒钟发出2.66个信源符号。将此信源的输出符号送入某一个二元信道中进行传输（假设信道是无噪无损的），而信道每秒钟只传递2个二元符号。试问信源不通过编码能否直接与信道连接？若通过适当编码能否在此信道中进行无失真传输？若能连接，试说明如何编码并说明原因。解：信源，其信源熵而其每秒钟发出2.66个信源符号，所以信源输出的信息速率为：送入一个二元无噪无损信道，此信道的最大信息传输率（信道容量）。而信道每秒钟只传输两个二元符号，所以信道的最大信息传输速率为：可见：。根据无噪信道编码定理（即无失真信源编码定理），因。所以总能对信源的输出进行适当的编码，使此信源能在此信道中进行无失真地传输。如果对信源不进行编码，直接将信源符号以“0”符号传送，以“1”符号传送，这时因为信源输出为2.66（二元信源符号/秒），大于2（二元信道符号/秒），就会使信道输入端造成信源符号的堆积，信息不能按时发送出去。所以，不通过编码此信源不能直接与信道连接。若要连接，必须对信源的输出符号序列进行编码，也就是对此信源的N次扩展信源进行编码。但扩展次数越大，编码越复杂，设备的代价也越大，所以尽量使扩展的次数N少，而又能使信源在此信道中无失真传输。先考虑，并对二次扩展信源进行霍夫曼编码，得：二元霍夫曼码得：二次扩展编码后，送入信道的传输速率为：所以，必须考虑即对三次扩展信源进行霍夫曼编码，得：二元霍夫曼码得：三次扩展码后，送入信道额传输速率为：此时，就可以在信道中进行无失真传输了。5-13现有一幅已离散量化后的图像，图像的灰度量化分成8级，如下表所示。表中数字为相应像素上的灰度级。1111111111111111111111111111111111111111222222222222222222223333333333444444444455555566667777788888另有一无噪无损二元信道，单位时间（秒）内传输100个二元符号。（1）现将图像通过给定的信道传输，不考虑图像的任何统计特性，并采用二元等长码，问需多长时间才能传送完这幅图像？（2）若考虑图像的统计特性（不考虑图像的像素之间的依赖性），求这图像的信源熵，并对每个灰度级进行霍夫曼最佳二元编码，问平均每个像素需用多少二元码符号来表示？这时需多少时间才能传送完这幅图像？（3）从理论上简要说明这幅图像还可以压缩，而且平均每个像素所需的二元码符号数可以小于比特。解：（1）3秒。（2）2.59秒。5-14设某无记忆二元信源，概率=P(1)=0.1，=P(0)=0.9，采用下述游程编码:第一步，根据0的游程长度编成8个码字，第二步，将8个码字变换成二元变长码，如下表所示：信源符号序列中间码二元码字1S0100001S11001001S210100001S3101100001S41100000001S511010000001S6111000000001S7111100000000S80试问最后的二元变长码是否是唯一可译码；试求中间码对应的信源序列的平均长度；试求中间码对应的变长码二元码码字的平均长度；计算比值，解释它的意义，并计算这种游程编码的编码效率；（5）若用霍夫曼编码，对信源的四次扩展信源进行直接编码，求它的平均码长(对应于每一个信源符号)，并计算编码效率，试将此方法与游程编码方法进行比较；（6）将上述游程编码方法一般化，可把个信源序列(上例中s=3)变换成二元变长码，即个连零的信源序列编为码字0，而其他信源序列都编成s+1位的码字.若信源输出零的概率为，求/的一般表达式，并求=0.995时s的最佳值。解:(1)根据唯一可译码的判断方法可知，最后的二元变长码是非延长码(即时码，所以它是唯一可译码。(2)因为信源是二元无记忆信源，所以有P(si)=P(si1)P(s2)…P(sin)其中si=(si1si2…sin)si1,si2,…sin{0,1}已知p1=P(1)=0.1，p0=P(0)=0.9，可求得信源符号序列的概率P(si)。根据编码，可排出下列表信源符号序列序列的概率P(si)信源符号序列长度l1i中间码二元码码长l2i10.11S04010.092S140010.0813S2400010.07294S34000010.065615S440000010.0590496S5400000010.05314417S64000000010.047829698S74000000000.430467218S84根据表可计算1=≈5.6953信源符号/中间码(3)根据表计算2=≈2.7086二元码/中间码(4)≈0.4756二元码/信源符号此值为每个信源符号所需的二元码符号数，也就是无记忆二元信源采用游程编码后每个二元信源符号所需的平均码长。可计算无记忆二元信源的信息熵H(S)=-≈0.4690比特/信源符号所以，这种游程编码的效率η=≈0.986≈98.6%(其中因为二元编码所以Hr(S)=H(S))(5)若对无记忆二元信源的次扩展信源直接进行霍夫曼编码，可得S4P(si)码字Wi码长liS4P(si)码字Wi码长li00000.65610110010.00811111010700010.0729110310100.00811111011700100.0729100311000.00811111110701000.0729101301110.0009111111100910000.07291110410110.0009111111101900110.0081111110611010.0009111111110901010.00811111000711100.000911111111101001100.00811111001711110.00011111111111104=≈1.9702二元码/4个信源符号得=0.4926二元码/信源符号编码效率η=≈0.952≈95.2%此编码效率低于游程编码方法。这是因为霍夫曼码只考虑N=4(固定值)时进行压缩，使概率大的对应于短码，概率小的对应于长码。但无记忆二元信源符号“0”出现的概率p0很大，所以在信源输出序列中符号“0”连续出现的概率较大，而连续出现符号“1”的概率极小。游程编码正是考虑了这些特性，使N较长(N=8)的连续出现的符号“0”序列压缩成一个二元码符号。所以，游程编码的编码效率较高。当然，当N很大时(N=8)霍夫曼编码效率会提高，但其编码方法没有游程编码方法来得简单。(6)一般游程编码方法是将2s+1个信源序列中一个2s个连续为零的序列编成码字0，而其他信源序列编成码长为s+1的码字，所以根据表中类似计算可得1=其中p0为信源中符号“0”出现的概率，p1为符号“1”出现的概率，有p0+p1=1。展开上式，得1=p0+2p1p0+3p1+…++=(1-p0)[(1+2p0+3+…+)]+=(1+2p0+3+…++)-(p0+2+3+…+)=(1+p0++…+)=根据表中类似计算，得2=(s+1)=(s+1)[(1-p0)(1+p0++…+)]+=(s+1)(1-)+=1+s(1-)得的一般表达式为==当p0=0.995，p1=0.005时，求s的最佳值，也就是求s取某值时最短。可采用将对s求偏导来解，但所得为超越方程，所以我们采用数值求解方法。令s=22s=4=0.262s=32s=8=0.1422s=42s=16=0.0849s=52s=32=0.0587s=62s=64=0.482s=72s=128=0.0456s=82s=256=0.0469所以得最佳当p0=0.995时二元信源的信息熵H(S)=H(0.995)≈0.0454比特/信源符号可见，当s=7时，已极接近H(S)，编码效率达到99.5%5-15有两个信源和如下：（1）分别用霍夫曼码编成二元变长唯一可译码，并计算编码效率；（2）分别用香农编码法编成二元变长唯一可译码，并计算编码效率；（3）分别用费诺编码法编成二元变长唯一可译码，并计算编码效率；（4）从，两种不同信源来比较这三种编码方法的优缺点。5-16将幅度为3.25V、频率为800Hz的正弦信号输入采样频率为8000Hz采样保持器后，通过一个如题图5-16所示量化数为8的中升均匀量化器。试画出均匀量化器的输出波形。题图5-165-17已知某采样时刻的信号值x的概率密度函数如题图5-17所示，将x通过一个量化数为4的中升均匀量化器得到输出。试求：输出的平均功率;量化噪声的平均功率；量化信噪比。题图5-175-18在CD播放机中，假设音乐是均匀分布，采样频率为44.1kHz，采用16比特的中升均匀量化器进行量化。试确定50分钟音乐所需要的比特数，并求量化信噪比。5-19采用13折线A律非均匀量化编码，设最小量化间隔为，已知某采样时刻的信号值x=635。试求该非均匀量化编码，并求其量化噪声e；试求对应于该非均匀量化编码的12位均匀量化编码。5-20将正弦信号输入采样频率为8kHz采样保持器后通过13折线A律非均匀量化编码器，设该编码器的输入范围是[-1,1]。试求在一个周期内信号值，的非均匀量化编码，。5-21将正弦信号输入采样频率为4kHz采样保持器后通过差分脉冲编码调制器，设该调制器的初始值，，采用码长为4的均匀量化编码，量化间隔=0.03125。试求在半个周期内信号值，的差分脉冲编码和量化值，。