常用信源编码

1、2.10常用信源编码信源编码也称为有效性编码，通过编码的方式，压缩信源的冗余度，从而提高了了通信的有效性。2.10.1山农费诺编码山农费诺编码是一种常见的信源编码，其编码的步骤如下：(1)将信源的符号按其概率从大到小排列。(2)将这一列符号分成尽可能概率接近或相同的两组。(3)上面一组符号编为0，下面一组符号编为1，或反之。(4)已分的组再按（2）、（3）步骤重复做，直至不能再分组。(5)自左至右写出各码字。例2.10.1有一单符号离散无记忆信源X如下，要求进行山农费诺编码因为信源有8个符号，其理论最大熵为 lb8=3比特/符号，而实际熵为2.55比特/符号，如采用三位二进制等长编码，则效率

2、=2.55/3 = 85%，或者说采用定长编码效率较低。如采用山农费诺编码，则效率会提高不少。2.10.2哈夫曼编码哈夫曼编码是效率比较高的又一种无失真信源编码，二进制哈夫曼编码步骤如下：(1) 把信源符号按概率从大到小排成一列；(2) 把概率最小的两个分成一组，上面一个编为0，下面一个编为1，并将这两个符号的概率加起来，其结果再和尚未处理过的符号重新按大小排序；(3) 重复步骤2，直到所有信源符号都处理完。(4) 从右向左依据编码路径返回，就得到各码字。例2.10.2同前例,编码过程见下图2.10.2：（PPT 001第四章）2.10.3冗余位编码冗余的信息完全可以不全部传送（压缩掉），从而

3、提高了传输效率。1LD编码现在来讨论一种由林绪（Lynch）和达维生（Davission）分别独立提出的冗余位编码法，称为LD编码。例如有一二元序列，其中的一串1000共二进制15位，其余的也可分割成15位一串，称为一帧。现在研究压缩冗余的方法。显然对该帧可确切描述为：（1） 帧长为15。（2） 共有两个1。（3） 第一个1在第4位。（4） 第二个1在第12位。可简写为：N=15,Q=2,n1=4,n2=12其中N为帧长，Q表示帧中1的个数，n1,n2表示1的位置.再来分析包括这些信息至少要二进制多少位，显然1的个数可能为015个共16种情况，需要的二进制符号数为4，而1的位置的可能性应为N中

4、取Q的组合数。需要用二进制的位数为6.7，取最小整数7位。于是共需4+7=11位二进制，可见有1511=4位冗余可压缩掉。Q很好处理，直接用4位二进制数表示即可。难点是n1,n2，如何把它们综合起来，成为一个7位的二进制数，而在译码时又能从这一个7位的二进制数中唯一地求出n1,n2来。解题步骤P110-P111根据上例可归纳出LD码编码方法：(1) 将冗余序列截成N位二进制的一帧。(2) 根据1的数目写出Q，根据1的位置写出n1。(3) 根据公式求出T。(4) 根据公式A求压缩后的二进制位数，前一项表示1的数目，后一项表示所有1的位置。(5) 用二进制表示QT。 LD译码方法(1)用尝试的方法

5、从K=N-1起，根据下式求出K，进而求出nQ;(2)再令，从L=K-1起求适合下式的L，进而求出nQ-1; (3)重复（2）直至nQ-1= n1。 (4)根据Q,n恢复出原冗余位序列。例1 ：=消息U 概率pi 编码CU1 1/2 0 0 1 0U2 1/4 0 10 1/2 1U3 1/8 0 110 1/4 1U4 1/8 1 111编码规则：1) 将信源消息U按概率大小排序（由大至小）。2) 从最小两个概率开始编码，并赋予一定规则，如下支路小概率为“1”，上支路大概率为“0”。若两支路概率相等，仍为下支为“1”上支为“0”。3) 将已编码两支路概率合并，重新排队，编码。4) 重复步骤3）

6、直至合并概率归一时为止。5) 从概率归一端沿树图路线逆行至对应消息编码，如U3为“110”。例2. = 0.20 , 0.19 , 0.18 , 0.17 , 0.15 , 0.10 , 0.01 编码 0.20 0.26 0.35 0.39 0.61 10 1.0 0.19 0.20 0.26 0.35 0 0.39 11 0.18 0.19 0.20 0 0.26 1 000 0.39 0.17 0.18 0 0.19 1 001 0.35 0.15 0 0.17 1 010 0.10 0 0.26 0110 0.11 1 0.01 1 0111例3. = 0.4 , 0.1 , 0.2

7、, 0.2 , 0.1 编码 0.4 0.4 0.6 0 1 1.0 0.2 0.4 0 0.4 1 01 0.6 0.2 0 0.2 1 000 0.4 0.1 0 0010 0.2 1 0.1 1 0011 编码 0.4 0.4 0.4 0.6 00 1.0 0.2 0.2 0.4 0.4 10 0.6 0.2 0.2 0 0.2 11 0.4 0.1 0 0.2 1 010 0.2 0.1 1 011可见，编成的码C 和C不一样，这说明哈夫曼编码并不唯一，这是由于哈夫曼编码是与信源统计特性相匹配的编码，而不是某个信源固定特性相匹配，不唯一性是明显的，但是只要在编码和译码过程中遵守同一规则

8、，译码是唯一的。虽然C和C不一样，但是两者都是哈夫曼编码，并且码长相等。Kc=0.41+0.22+0.23+20.14=2.2Kc =0.42+0.222+0.132=2.2 但是，若从二阶矩来看，即方差来看，C的方差大，C的方差小，所以C优于C下面讨论哈夫曼编码应用中的一些问题：1)首先讨论误差扩散：哈夫曼编码是一种无失真信源最佳编码，但是在实际信道中是有失真的。噪声的引入必然要破坏长码结构，而且是变长码，错误不但影响受干扰位，还要进一步扩散。目前对扩散还没有很有效的方法，工程上克服方法有两种：一是限制哈夫曼码仅能应用于优质信道（=10-6）以限制扩散的可能性；二是采用定期清洗，防止扩散区域

9、增大。但是它是靠牺牲有效性换取的。2)其次是速率匹配问题：由于绝大多数信源是不等概率的，由它编成的码长度与速率是可变的。然而实际信道则要求其输入端速率是固定的。所以信源与信道之间还存在一个速率匹配问题。在工程上解决这一问题的方法是在两者之间加一个类似与水库的缓存器，它变速入，恒速出，以解决两者速率的匹配。3)第三是与信源统计特性匹配的问题。其中：1）、小消息（符号）集信源不易匹配可采用信源消息集不断扩展的方法来解决，但是太复杂。2）、信源统计特性未知时，怎么办？可采用所谓通用编码的方法来解决。2游程编码例如,其中连在一起的0段称为0游程，同样连在一起的1段称为1游程， 由00000可编码成一个

10、游程序列，一般游程越长，压缩越有效。接下来可以用其它方法例如多元哈夫曼编码进一步消除冗余，提高效率。思考题 已知12个球中有一个球的重量与其它球不同，其它球均等重。问用无砝码的天平至少须几次才能找出此球？解：天平有3种状态，即平衡，左重，左轻，所以每称一次消除的不确定性为log3，12个球中的不等重球（可较轻，也可较重）的不确定性为： 因为 3log3log243次测量可以找出该球具体称法略。例一一副充分洗乱了的牌（含52张牌），试问：(1) 任一特定排列所给出的信息量是多少？(2) 若从中抽取13张牌，所给出的点数都不相同能得到多少信息量？(1)任意排列共有种，则任一排列的自信息量为：。(2

11、)应将点数相同花色不同的牌看作一类，则任意抽取的13张牌应在13类中分别进行。其概率为：， 信息量。例二 已知随机变量X和Y的联合概率分布满足：试求能使H(XY)取最大值的联合概率分布。H(X Y) H(X) + H(Y) 等号在X、Y独立时取得P() = P() = P() = P() = P() = P() = P() = P() = P() = 满足 H(XY) 取最大值例三求证：I(X;Y;Z)=H(XYZ)-H(X)-H(Y)-H(Z)+I(X;Y)+I(Y;Z)+I(Z;X)例4令X为掷钱币直至其正面第一次朝上所需的次数，求H(X)P(X=n) = = H(X) = = = 2 b

12、it例5一个无记忆信源有四种符号0，1，2，3。已知。试求由6000个符号构成的消息所含的信息量。解：先计算一个符号所含的平均自信息量，即信源熵HH= =1.9056bit无记忆信源由6000个符号构成的符号序列消息例6发出二重符号序列消息的信源熵为而一阶马尔可夫信源的信源熵为试比较这两者的大小，并说明原因。 解：根据公式，当Y和X为同一集合时，有，各种熵和条件熵均为非负值，当且仅当X中只含有一个确定性事件时才出现H（X）=0。当X中含有二个或二个以上事件时，有H（X）0，及H（X2）0，H（X|X）0，因为H（X）0所以H（X2）H（X|X）说明，在一般情况下，发二重符号序列的信源的信源熵H

13、（X2）大于一阶马尔可夫过程的信源熵H（X|X）例7有一个马尔可夫信源，已知，试画出该信源的概率转移图，并求出信源熵。解：该信源的概率转移图为： 1/3 2/3 (x1) 1 (x2) 在计算信源熵之前，先用转移概率求稳定状态下二个状态x1和 x2 的概率和立方程：+= + = =1 得 马尔可夫信源熵H = 得 H=0.689bit/符号本章作业与练习1 某大学设置五个学院，每个学院的学生数分别为 学院： 数学物理外语外贸 医学 人数： 300 400 500 600 200 问“某学生王某是外语学院学生”这一消息提供的信息量是多少？2 某电子厂共能生产A、B、C、D四种仪器，其中A因技术落

14、后停产了，B占全部产量的20%，C占30%，D占50%。有两个消息“现在完成1台仪器B”，和“现在完成1台仪器C”，试确定哪一种消息提供的信息量大些？其中有什么规律?3 试求（1）在一付标准的扑克牌中抽出一张（每张牌均认为是不同的）的平均信息量。（2）若扑克牌仅按它的等级鉴定而不问它的花色(大、小王属同一等级)，重复上述计算。4 某地的天气预报为：晴（占4/8），多云（占2/8），雨（占1/8），雪（占1/8）, 冰雹（占0/8）而当地老农对天气的预测只能做到：晴（占7/8），雨（占1/8） 试求两者对天气预报各自提供的平均信息量。5 有一二元数字通信系统，传送“0”和“1”的概率分别为1/4

15、和3/4。为了可靠地传输这一消息，重复传输3次，试求剩余度为多少，如果采用重复传输4次的方案呢？这样做是否合理？6 有一个生产A、B、C、D四种消息的信源其出现的概率相等，通过某一通信系统传输时，B和C无误，A以1/4概率传为A，以1/4概率误传为B、C、D，而D以1/2概率正确传输，以1/2概率误传为C，试求其可疑度？收到的信号中哪一个最可靠？其散布度为多少？7 有一以“点”和“划”构成的老式电报系统，“点”的长度为30毫秒，“划”的长度为150毫秒，“点”和“划”出现的概率分别为0.8和0.2，试求信息速率为多少？“点”、“划”出现的概率相等时，信息速率为多少？是否“点”、“划”出现的概率

16、相等时信息速率一定最高？是否和理论相矛盾？为什么？8 有一传输“0”和“1”的二元数字通信系统，以1 000码元/秒的速率传输，传送“0”和“1”的概率分别为：p(0)=1/3 p(1)=2/3由于信道有噪声，误码率为pe=0.2*10-2，试求接收的信息速率？9 设有6个消息，其出现概率分别为AB C D E F1/16 1/16 2/16 3/16 4/16 5/16将它们分别进行山农编码和霍夫曼编码，并比较编码效率。是否在任何情况下山农编码比霍夫曼编码效率都低？10连续信源变量x的取值为正，其平均值为，试求信源熵最大时的概率分布密度函数以及最大熵。11已知一个平均功率受限的连续信号，通过

17、带宽W=1MHz的高斯白噪声信道，试求（1）若信噪比为10，信道容量为多少？（2）若信道容量不变，信噪比降为5，信道带宽应为多少？（3）其中有什么规律可总结？14设有一个信源，它产生0，1序列的信息，它在任意时间而且不论以前发生过什么符号，均按 ， 的概率发出符号（1）试问这个信源是否是平稳的？（2）试计算，及；（3）试计算并写出信源中可能有的所有符号。15黑白电视消息只有黑色(B)和白色(W)两种，即信源X=(B,W)，设黑色出现的概率为P(B)=0.3，白色出现的概率P(W)=0.7。（1）假设图上黑白消息出现前后没有相关性，求熵H(X)；（2）假设消息前后有相关性，其依赖关系为p(W/W

18、)=0.9，p(B/W)=0.1，p(W/B)=0.2，p(B/B)=0.8，求此一阶马尔可夫信源的熵H2(X)；（3）分别求上述两种信源的剩余度，比较H(X)和H2(X)的大小，并说明其物理意义。16设信源 通过一干扰信道，接收符号为信道传递矩阵为。求；（1）信源中符号 和分别含有的自信息量。（2）收到消息 后，获得的关于 的信息量。（3）信源和信宿的信息熵。（4）信道疑义度和噪声熵。（5）接收到信息后获得的平均互信息量。17设二元对称信道的传递矩阵为（1）若p(0)=3/4，p(1)=1/4，求H(X)，H(X/Y)，H(Y/X)和I(X;Y)；（2）求该信道的信道容量及其达到信道容量时的

19、输入概率分布。18若X，Y，Z是三个随机变量，试证明（1）；（2）；（3），当且仅当是马氏链时等式成立。19若三个离散随机变量，有如下关系：，其中X和Y相互独立。试证明20有一个二元对称信道，其信道矩阵为设该信源以1500符号/秒的速度传输输入符号。现有一消息序列共有14000个二元符号，并设其符号等概分布，问从信息传输的角度来考虑，10秒钟内能否将这消息序列无失真地传递完？21有一冗余位序列，N=15，码字为0000，试将其编成LD码。 第二章习题解答1.总人数为：300+400+500+600+200=2000人是外语学院学生的概率为：该消息提供的信息量：比特/消息。2.因为以及消息提供的

20、信息量与其出现概率倒数的对数成正比，所以，即”现在完成一台仪器B”提供的信息量大于”现在完成一台仪器C”提供的信息量。规律：(1)出现概率为零的消息可略去。(2)概率小的消息出现时提供的信息量大于概率大的消息出现时提供的信息量。3.(1) 比特/每张牌(2)出现的概率为：王出现的概率为：比特/每张牌。4.天气预报：比特/每次预报老农预报：比特/每次预报。5解：信源熵 比特/消息二元信源的最大熵 比特/消息冗余度 重复三次信源熵 比特/消息冗余度 重复四次信源熵 比特/消息冗余度 重复四次不合理，因2比2时就不能采用最大似然法判决。6解：先写出再根据式求各联合概率同样得求Y端概率空间的各同样得求各熵比特/每对消息比特/消息比特/消息接收可靠的依据是根据下式求,越大表示越可靠可见接收信号A最可靠7.解：求信源熵比特/消息消息/秒比特/秒如果点,划出现的概率相等时,则比特/消息消息/秒比特/秒可见信息速率反而降低了.但与理论不矛盾,因为该信源的两个消息是非同价代码(每个码元(消息)的时间长度不同),因此才有此结果。8.解:先写出根据公式计算联合熵求信宿端符号分布概率根据公式计