1、第一讲 概述及内容G通信原理II的内容n信息论初步及在信源编码中的应用（3次）n信道及信道编码理论（2次）n信道编码（8次）n伪随机序列与扩频通信（4次）概述n通信系统回顾n上学期内容n本学期内容关注n信源部分的处理（有效性）n信道编码部分处理（可靠性）通信系统信源信源编码解密信道解码解调信道信道编码加密调制信源译码信宿信源n数字信源n文本、文件n数字化语音n数字化图象n数字化视频n带限模拟信号可以通过抽样、量化得到数字化信源（奈奎斯特定理）n因此，信源编码可以从研究数字化信源开始。信源编码n信源的统计特性各异n不同信源特性不同n如何用最经济的方式表示信源n经济：“最简短的语言”、“言简意赅”
2、n好处：传输代价小、频带利用率高、存储代价低等 例：文件压缩减小存储空间、语音编码使移动通信信道利用率提高等n两类n无失真信源编码n限失真信源编码无失真信源编码（压缩）n1948年Shannon文章“A Mathematical Theory of Communication,”开始建立了无失真编码的理论。n最大可能的压缩程度n无论任何压缩技术，压缩后的信源熵率大于等于原始信源熵率Hn信源熵率H取决于信源的统计特性信源模型n假设你去图书馆借一本英文书：nX1表示书的第一个字符，X2第二个n设Xi是A集合中的一个字符，n为了压缩这本书，建立统计模型信源模型n零阶模型n设27个字母等概出现，则按此
3、统计模型写书可能出现如下文本：“xfoml rxkhrjffjuj zlpwcfwkcyj ffjeyvkcqsghyd qpaamkbzaacibzlhjqd”n一阶模型n考虑英文单词，字母出现的频度不同。例如：a,e的出现概率比z大。其典型文本：“ocroh hli rgwr nmielwis eu ll nbnesebya th eei alhenhttpa oobttva nah brl”信源模型n二阶模型n前述模型认为字母出现是前后独立的，考虑英语词汇特点，例如：d后出现e的概率比z大。设Xi的出现概率与Xi-1有关，而与其它字符独立，其典型文本为：“on ie antsoutiny
4、s are t inctore st be s deamy achin d ilonasive tucoowe at teasonare fuso tizin andy tobe seace ctisbe”n三阶模型n设Xi的出现概率与Xi-1，Xi2有关，与其它字符独立，典型文本为“in no ist lat whey cratict froure birs grocid pondenome of demonstures of the reptagin is regoactiona of cre”n信源熵率n设符号集A为有限，元素个数为m，则n零阶模型：n一阶模型n二阶模型n三阶模型|2|1
5、1log/mmijijiijHpppbits character|,2|,111log/mmmijik i jk i jijkHppppbits character 信源编码n一般模型n根据Shannon的统计n零阶 4.75 bits/charactern一阶 4.07 bits/charactern二阶 3.36 bits/charactern三阶 2.77 bits/charactern无限阶 2.3bits/character 122121lim,.,log,.,LLLHP x xxP x xxLX限失真信源编码n不要求译码输出与编码输入是无失真的n定义失真度d(i,j)表示i编码后输
6、出j时的失真，则限失真编码是如下的优化问题：|211|1|111minlogmin;01,1,j ij immjiijimQQijj kkmmmjijiijijijQR DpQI X YQQQpQ d i jD 离散信源熵n无记忆信源（单符号信源）n概率分布n符号信息量n信源熵（符号的平均信息量）01101.1.MMppp 10logMiiippXHipiXIlog例、n四进制不等概、独立信源，概率分布（0.125,0.125,0.5,0.25）n四进制等概、独立信源n证明：H(x)=0，且信源等概时熵最大。n(lnx=H(X|Y)，I(X;Y)=0信源剩余度n定义n若存在n可证 121,.,
7、LLHH x xxLX 121lim,.,LLHH x xxLX 11lim|,.,LLLHH xxxX信源剩余度n定义信源效率n定义剩余度（冗余度）n注：H(X)表示了前后的相关信息量，如果为0，则意味着发送的当前符号可以完全由以前的发送符号确定，此时再发送当前符号属于一种“浪费”。n信源编码的目的是使冗余度尽可能小。02logHXHXHXN1R 信源编码n编码n将符号、字母或数字按一定规则编成不同的序列，称为编码。n信源编码n为了减小信源输出符号中的冗余度，对信源实施的一种编码。n好的信源编码 输出符号没有相关性（前后）输出符号等概（单个符号熵最大化）信源编码n若输入信源(x1,x2,xL
8、),信源编码输出(s1,s2,sK)n设输入信源等概（等概序列等概），输出等概序列，则 为了唯一表示输入信源序列，输出信源序列应该满足条件（无失真表示）loglogLKKnnmLm信源编码n若输入信源序列不等概，输出序列等概n例如：独立同分布、但不等概符号构成的序列(x1,x2,xL),xi0,1,p(0)=1/4,p(1)=3/4，则序列(1,1,1)的概率比(0,0,0)大。n存在所谓的“典型序列”“典型序列”是出现概率最大的序列的集合，当L趋于无穷时，“典型序列”的个数为2LH(x),且各序列出现的概率相等，约为2-LH(x)，典型序列集出现的概率趋于1。注：严格证明请参见信息论的一些书
9、籍，这里说明一点：由于当L很大时，非典型序列的概率很低，因此可以另外处理。例如：限失真的编码可舍去这部分的编码；无失真的编码可以考虑用不等长的编码来区分“典型序列”与“非典型序列”，从而使平均编码长度减小。典型序列（理解）n考虑二进制I.I.d.序列，设概率分布为p,1-p，则长度为N的序列，发生概率为，n当N趋于无穷时，则序列中1的个数趋于N(1-p)，即含N(1-p)个“1”的序列出现的可能性最大，且每个这样的序列基本等概出现。这些序列的集合称为“典型序列”1N kkpp等长信源编码n无失真编码需要满足n限失真情况下，n若允许译码误差小于任意给定的0，则可以找到L满足n的编码，其译码误差小
10、于。loglogLKKnnmLm2log()KmH XL不等长信源编码n存在一种变长编码，其平均码长满足如下关系n变长码可以实现无失真编码。其基本想法为：出现概率大的符号编成段的比特组，出现概率小的符号编成长的比特组，这样平均输出比特长度小。n编码效率221loglogH XH XKmLLmH XK不等长编码n可以有很多方法实现不等长编码，且其平均输出码长逼近H(x)。n但实际使用中，由于变长编码会带来“断句”的问题，即收到一串比特流时，是否能够唯一译码？n采用“剪枝树”的方法可以构造出能唯一译码的变长编码。n若任何一个码字均不是其它码字的前缀，则可以唯一译码，这种码称为“前缀码”剪枝树010
11、10110111011011010 10,111,0,110,110,10Huffman编码nHuffman编码是一种无失真的变长信源编码，编码效率高。0.350.300.200.100.040.0050.005101010100101Huffman编码结果x1 0.35 0 x2 0.30 10 x3 0.20 110 x4 0.10 1110 x5 0.04 11110 x6 0.005 111110 x7 0.005 111111图象编码中的应用nJPEG、MPEGDCTZ扫描及量化Huffman编码Huffman解码系数排列反量化IDCTLZ压缩算法nLempelZiv简称n目前的许多
12、压缩程序基于LZ算法，如Unix的compress、uncompress、Gzip，gunzip，Windows的Winzip等n压缩效率 自适应Huffman编码 LZ编码nLatex 66 44n语音文件 65 64n图象文件 94 88n利用Linux下的Gzip压缩英文书，达到效率2.9bits/CharacterLZ算法简介n编码思想n通过分析输入序列，将输入序列分成不重叠的子块，并生成子块的字典，对子块根据字典的索引进行编码。n编码算法n1、初始化字典，包含序列中可能出现的单个字符n2、根据字典中的最长字匹配序列当前位置，断句wn3、根据字典的索引对w进行编码n4、将w与后一个字符
13、结合加入到字典中并编号n5、返回2LZ编码算法例LZ算法n理论上，字典可以无限长，但实际上受限。Welch建议12bit（4096）n字典索引可以是变长码，变长码提高压缩效率n通常对输入短序列而言，LZ观察不到压缩的效果n档输入序列足够长、冗余大时，LZ压缩效果明显。建议课后阅读参考文献1.D.A.Huffman,A Method for the Construction of Minimum Redundancy Codes,Proceedings of the IRE,Vol.40,pp.1098-1101,1952.2.J.Ziv and A.Lempel,A Universal Alg
14、orithm for Sequential Data Compression,IEEE Transactions on Information Theory,Vol.23,pp.337-342,1977.3.J.Ziv and A.Lempel,Compression of Individual Sequences Via Variable-Rate Coding,IEEE Transactions on Information Theory,Vol.24,pp.530-536,1978.4.T.A.Welch,A Technique for High-Performance Data Compression,Computer,pp.8-18,1984.
