信源编码(1)_离散信源编码11.11

1、第5章 信源编码编码的意义编码的意义编码定义编码定义最佳编码方法信源编码的目的：信源编码的目的： 1、便于信道的传输、便于信道的传输 例如：语音信号的数字传输例如：语音信号的数字传输 2、提高有效性、提高有效性 例：设某计算机终端用来控制检查流水线上产品的质量，按优、中、劣三级来分类记录。从统计中已知产品在三级中的比例为优、劣各占1/4，中占1/2。以下研究如何将检查结果编成二进制码，以通过网络传送到主机中进行存储和处理。第一种编码方法： 产 品 等级出现概率编码优1/411中1/210劣1/400平均编码长度：L1=1/4*2+1/2*2+1/4*2 =2bit/符号产 品 等级出现概率编码

2、优1/41中1/210劣1/400第二种编码方法平均编码长度：L2=1/4*1+1/2*2+1/4*2 =1.75bit/符号产 品 等级出现概率编码优1/411中1/21劣1/400第三种编码方法平均编码长度：L3=1/4*2+1/2*1+1/4*2 =1.5bit/符号结论： 1、不同的编码方法，平均的编码长度不一样 2、L1L2L3结论：概率越大，用的码越短，则平均编码长度则越小。二、编码定义1、等长码和变长码 如果一种码的各个码字都是由同样多个码元构成的，则成为等长码。例如：00，01，103、码树 码树是表示元素之间的结构层次的方法。5、平均编码长度 设N个码字中的第I个码字的长度为

3、ni,他所代表的编码对象xi的概率为p(xi),则码字的平均编码长度为： L=p(xi) ni6、编码效率 最小的平均编码长度和实际的编码长度的比值。 Lmin=H(X)/logD =Lmin/L 编码的剩余度r=1- 产 品 等级出现概率编码优1/411中1/21劣1/400例:平均编码长度：L3=1/4*2+1/2*1+1/4*2 =1.5bit/符号Lmin=1.5 =1三、最佳编码方法 满足两个条件：1、唯一可译性 2、码长是最小的l 目的：提高通信的有效性。目的：提高通信的有效性。l 途径：通过压缩信源的冗余度来实现。途径：通过压缩信源的冗余度来实现。l 方法：压缩每个信源符号的平均

4、比特数或信方法：压缩每个信源符号的平均比特数或信源的码率。同样多的信息用较少的码率来传源的码率。同样多的信息用较少的码率来传送，使单位时间内传送的平均信息量增加，送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。从而提高通信的有效性。使序列中的各个符号尽可能地互相独立，即解使序列中的各个符号尽可能地互相独立，即解除相关性；除相关性；使编码中各个符号出现的概率尽可能地相等，使编码中各个符号出现的概率尽可能地相等，即概率均匀化。即概率均匀化。理论基础：是信息论中的两个编码定理：理论基础：是信息论中的两个编码定理：n 无失真编码定理。只适用于离散信源。只适用于离散信源。n 限失真编码定理。

5、对于连续信源，只能在对于连续信源，只能在失真受限制的情况下进行失真受限制的情况下进行限失真编码。1110110100 0111011010 110010 10100 125. 0125. 025. 05 . 04321DCBAaaaa码码码码码码码码概概率率消消息息判断以下码字是否可分离？异前置码即时码可分离有延时可分离分离不可分离不可例例5.1.112121.()().()( )1nnniiaaap ap ap ap a设有离散无记忆信源设有离散无记忆信源12香农编码方法的步骤香农编码方法的步骤按信源符号的的顺序排队)(.)()(21napapap不妨设不妨设个个码码字字的的累累加加概概率率

6、表表示示第第，用用令令iijapapja1),(0)(011( )( ) 1jajiip ap a22log( )1 log( )iiiikp akp a 确定 ，使其满足()ajiipaka把用二进制表示，用小数点后的 位作为 的码字3405. 01 . 015. 02 . 025. 025. 0)(654321aaaaaaXPX设有一单符号离散无记忆信源设有一单符号离散无记忆信源试对该信源编二进制香农码。试对该信源编二进制香农码。11110595. 005. 01101485. 01 . 010137 . 015. 010035 . 02 . 001225. 025. 0002025. 0

7、)(654321aaaaaakapija码字码字10)()(jiijaapap617 .2)(iiikapKKmLKR2log()2.42325H X (X)89.75%HR对概率按m进行分组，使每组尽可能相等；给每个分组分配一个码元；对每个分组重复2、3步，直到不可分为止。1234按信源符号的概率的顺序排队)(.)()(21napapap不妨设不妨设04. 008. 016. 018. 022. 032. 0)(654321aaaaaaXPX设有一单符号离散无记忆信源设有一单符号离散无记忆信源试对该信源编二进制费诺码。试对该信源编二进制费诺码。1a2a3a4a5a6a32. 022. 018

8、. 016. 008. 004. 0001010011000110110111011111编码过程编码过程)/(35. 2)(synbitXHmLKR2log%92.97)(RXH61)/(4 .2)(iiikapK符符号号比比特特可以看出本例中费诺码有较高的编码效率。费可以看出本例中费诺码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。诺码比较适合于每次分组概率都很接近的信源。00000111111a2a3a4a5a6a将信源符号顺序排队。给位，将其概率相加后合并作为一个新的符号，与剩下的符号一起，。给中概率最小的二个符号各分配一个码位。重复步骤2、3直至概率和为1。21430

9、4. 005. 006. 007. 01 . 01 . 018. 04 . 0)(87654321aaaaaaaaXPX设有一单符号离散无记忆信源设有一单符号离散无记忆信源试对该信源编二进制赫夫曼码。试对该信源编二进制赫夫曼码。09. 013. 019. 023. 037. 06 . 00000000111111104. 005. 006. 007. 01 . 01 . 018. 04 . 01a2a3a4a5a6a7x8a1001011000001000101000100001100010001007a编码过程编码过程()2.55(/)H Xbit sym2.61K( )97.7%H xR。

10、率提高了可见，哈夫曼编码的效则编码效率若采用定长编码，码长7 .1285355. 2, 3KHuffman码的编码方法不是唯一的。码的编码方法不是唯一的。 首先，每次对缩减信源两个最小的符号分配首先，每次对缩减信源两个最小的符号分配“0”和和“1”码元试任意的，所以可得到不同的码字。只要码元试任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。不同的码元分配，得到的具体码字到可分离码字。不同的码元分配，得到的具体码字不同，但码长，平均码长都不变，所以没有本质区不同，但码长，平均码长都不变，所以没有本质区别。别。

11、 其次，若合并后的新符号的概率与其他符号的概率其次，若合并后的新符号的概率与其他符号的概率相等，从编码的方法上来说，这几个符号的次序可相等，从编码的方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不任意排列，编出的码都是正确的，但得到的码字不同。不同的编法得到的码字长度也不尽相同。同。不同的编法得到的码字长度也不尽相同。设有离散无记忆信源设有离散无记忆信源1 . 01 . 02 . 02 . 04 . 0)(54321xxxxxXPX用两种不同的方法对其编二进制用两种不同的方法对其编二进制huffmanhuffman码码方法一方法一方法二方法二信源符号信源符号ai概率概

12、率p(ai)码字码字Wi1码长码长Ki1码字码字Wi2码长码长Ki2a10.41 1002a20.2012102a30.20003112a40.1001040103a50.1001140113两种不同的编码方法得到的码字和码长的对比两种不同的编码方法得到的码字和码长的对比平均码长和编码效率平均码长和编码效率两种编码方法编出的码字的码长方差比较两种编码方法编出的码字的码长方差比较进行赫夫曼编码时，为得到进行赫夫曼编码时，为得到码方差码方差最小的最小的码，应使合并的信源符号位于缩减信源序码，应使合并的信源符号位于缩减信源序列列尽可能高的位置尽可能高的位置上，以减少再次合并的上，以减少再次合并的次数

13、，充分利用短码。次数，充分利用短码。 游程序列游程 前面的几种编码方法主要时针对无记忆信源，对有前面的几种编码方法主要时针对无记忆信源，对有记忆信源，这些编码方法的效率并不高，特别是对二记忆信源，这些编码方法的效率并不高，特别是对二元相关信源，需要一些其它的方法。游程编码就是这元相关信源，需要一些其它的方法。游程编码就是这样的方法，对相关信源的编码更有效。样的方法，对相关信源的编码更有效。 指数字序列中连续出现相同符号的一段。在指数字序列中连续出现相同符号的一段。在二元信源中，连续的一段二元信源中，连续的一段00称为一个称为一个00游程，游程，00的个数称为此游程的长度，同样，也有的个数称为此

14、游程的长度，同样，也有11游程。游程。 用交替出现的用交替出现的00游程、游程、11游程的游程的长度，来表示任意二元序列而产生的一个新序列。它长度，来表示任意二元序列而产生的一个新序列。它和二元序列是一个一一对应的变换。和二元序列是一个一一对应的变换。二元序列：二元序列：000101110010001游程序列：游程序列：31132131二元序列二元序列赫夫赫夫曼编码曼编码 0：长度为1的“0”游程0000：长度为4的“0”游程 111：长度为3的“1”游程 长度为n的“1”游程11:1n多元序列也存在相应的游程序列多元序列也存在相应的游程序列 多元序列变换成游程序列再进行压缩编多元序列变换成游

15、程序列再进行压缩编码没有多大意义码没有多大意义 游游程编码只适用于二元序列，对于多游游程编码只适用于二元序列，对于多元信源，一般不能直接利用游程编码元信源，一般不能直接利用游程编码 因为游程变换是一一对应的可逆变换，所以游程变换后，熵不变。组合编码可获得较高的编码效率：游程编码赫夫曼编码“0”、“1”的概率分别为的概率分别为p0、p1长度长度i的的“0”游程概率：游程概率： 01001 iilp lpp长度长度j的的“1”游程概率：游程概率： 11110 jljp lpp00110 11iilpp lp11011 11jjlpp lp0p00010111001000131132131因为游程变

16、换是一一对应的可逆变换，所以游程变换后，熵不变。游程编码赫夫曼编码组合编码可获得较高的编码效率：010.6,0.4pp例例“0”游程长度信游程长度信源源二元序列：00010111001000011110011000101110001234()0.40.240.1440.0864LP L010203040.40.240.1440.0864llll000111100010011“1”游程长度信游程长度信源源111234()0.60.240.0960.0384LP L111213140.40.240.0960.0384llll010101101110011000101110010000111100110001011100,100,11000,0101111100001000100110,1111111010011100000111110010010011101信号序列码序列冗余位冗余位信源序列中不携带信息的符号。多元信源序列：1211 12, , , ,mmmyyyx xxxx111000,000111,100,111,211121mmmxxxxx上面二元上面二元1表示信息位，表示信息位，0表示冗余位表示冗余位 冗余位序列游程编码信息序