南邮信息论期末小结.ppt

第5章 信源编码 编码分为信源编码和信道编码，其中信源编码又分为无失真和限失真。 一般称 无失真信源编码定理为第一极限定理； 信道编码定理（包括离散和连续信道）称为第 二极限定理； 限失真信源编码定理称为第三极限定理。 由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。 信源编码的基本途径有两个： 使序列中的各个符号尽可能地互相独立，即解除相关性； 使编码中各个符号出现的概率尽可能地相等，即概率均匀化。 信源编码的基础是信息论中的两个编码定理： 无失真编码定理 限失真编码定理 无失真编码只适用于离散信源 对于连续信源，只能在失真受限制的情况下进行限失真编码 唯一可译码存在的充分和必要条件 各码字的长度Ki 应符合克劳夫特不等式： 无失真的信源编码定理 定长编码定理 K是定值 且惟一可译码 变长编码定理 码长K是变化的 根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。（统计匹配） 定长编码定理说明， 反之，当 时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。 时，则为临界状态，可能无失真，也可能有失真。 在连续信源的情况下，由于信源的信息量趋于无限，显然不能用离散符号序列来完成无失真编码，而只能进行限失真编码。 定义 为编码效率，编码效率总是小于1，且最佳编码效率为 单个符号变长编码定理：若离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式 离散平稳无记忆序列变长编码定理：对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式 其中?为任意小正数。 用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。 能获得最佳码的编码方法主要有： 香农（Shannon） 费诺（Fano） 哈夫曼（Huffman）等 进行哈夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。 哈夫曼码是用概率匹配方法进行信源编码。 哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码； 缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。 限失真信源编码定理 信息率RR(D)，平均失真可以=D 信息率RR(D)，平均失真一定D 算术编码 非分组码的编码方法之一——算术码 采用累积概率P(S)表示码字C(S)，符号概率p(S)表示状态区间A(S) 第6章 信道编码 有扰离散信道的编码定理 纠错编译码的基本原理与分析方法 线性分组码 香农信道编码定理 正定理：只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。 逆定理：信道容量C是可靠通信系统传信率R的上边界，如果R C，就不可能有任何一种编码能使差错概率任意小。 6.2.2最优译码与最大似然译码 最佳译码，也叫最大后验概率译码(MAP) 最大似然译码( MLD) BSC信道的最大似然译码可以简化为最小汉明距离译码。 由于BSC信道是对称的，只要发送的码字独立、等概，汉明距离译码也就是最佳译码。 线性分组码 G、G’、 H、 C、dmin、t、d 、S-E 缩短码、扩展码 汉明码（完备码） 循环码 g(x) 、 h(x) 系统循环码 ｍ(x) 、 g(x) 、 r(x) 、 c(x)关系 G、G’、 H、 C、dmin、t、d 、S-E 第7章 加密编码 加密编码的基础知识 数据加密标准DES 公开密钥加密法 密码学的基本概念： 明文、密文、加密、解密、破译、密钥、密码体制 必威体育官网网址性、真实性 对称密钥体制、非对称密钥体制 密码学中的熵概念 密码体制必须满足三个要求： 对所有密钥，加密解密都必须迅速有效 容易使用 体制的安全性只依赖于密钥的必威体育官网网址性，而不依赖于E、D的必威体育官网网址性 通信系统模型 一个必威体育官网网址系统：如果 H（M |C）=H（M）或 I（M；C）=0， 则该必威体育官网网址系统称为是完善的或无条件的必威体育官网网址系统，绝对安全 I(M;C) H(M)-H(K) 必威体育官网网址系统的密钥量越少，密钥熵H(K)就越小，其密文中含有的关于明文的信息量I(M;C)就越大。 完善必威体育官网网址系统I(M;C) =0，所以H(K) H(M) 数据加密标准DES 换位和替代密码 DES密