^C.E. Shannon, "A Mathematical Theory of Communication (页面存档备份,存于互联网档案馆)", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948
^David J. C. MacKay. Information Theory, Inference, and Learning Algorithms (页面存档备份,存于互联网档案馆) Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
^Cover, Thomas M. Chapter 5: Data Compression. Elements of Information Theory. John Wiley & Sons. 2006. ISBN 0-471-24195-4.
八月 13, 2023
信源编码定理, 此條目介紹的是信源编码的数据压缩理论, 关于计算机编程术语, 请见, 源代码, 在信息论中, 香农的, 或无噪声编码定理, 确立了数据压缩的限度, 以及香农熵的操作意义, 表明, 在极限情况下, 随着独立同分布随机变量数据流的长度趋于无穷, 不可能把数据压缩得码率, 每个符号的比特的平均数, 比信源的香农熵还小, 又不丢失信息, 但是有可能使码率任意接近香农熵, 且损失的概率极小, 码符号的把码字的最小可能期望长度看作输入字, 看作随机变量, 的熵和目标编码表的大小的一个函数, 给出了此函数的上界和. 此條目介紹的是信源编码的数据压缩理论 关于计算机编程术语 请见 源代码 在信息论中 香农的信源编码定理 或无噪声编码定理 确立了数据压缩的限度 以及香农熵的操作意义 信源编码定理表明 在极限情况下 随着独立同分布随机变量数据流的长度趋于无穷 不可能把数据压缩得码率 每个符号的比特的平均数 比信源的香农熵还小 又不丢失信息 但是有可能使码率任意接近香农熵 且损失的概率极小 码符号的信源编码定理把码字的最小可能期望长度看作输入字 看作随机变量 的熵和目标编码表的大小的一个函数 给出了此函数的上界和下界 目录 1 陈述 1 1 信源编码定理 1 2 码符号的信源编码定理 2 证明 码符号的信源编码定理 3 参考资料陈述 编辑信源编码是从信息源的符号 序列 到码符号集 通常是bit 的映射 使得信源符号可以从二进制位元 无损信源编码 或有一些失真 有损信源编码 中准确恢复 这是在数据压缩的概念 信源编码定理 编辑 在信息论中 信源编码定理 1 非正式地陈述 2 3 为 N 个熵均为 H X 的独立同分布的随机变量在 N 时 可以很小的信息损失风险压缩成多于 N H X bit 但相反地 若压缩到少于 N H X bit 则信息几乎一定会丢失 码符号的信源编码定理 编辑 令 S1 S2 表示两个有限编码表 并令 S 1 和 S 2 分别 表示来自那些编码表的所有有限字的集合 设 X 为从 S1 取值的随机变量 令 f 为从 S 1 到 S 2 的唯一可译码 其中 S2 a 令 S 表示字长 f X 给出的随机变量 如果 f 是对 X 拥有最小期望字长的最佳码 那么 Shannon 1948 H X log 2 a E S lt H X log 2 a 1 displaystyle frac H X log 2 a leq mathbb E S lt frac H X log 2 a 1 证明 码符号的信源编码定理 编辑对于 1 i n 令 si 表示每个可能的 xi 的字长 定义 q i a s i C displaystyle q i a s i C 其中 C 会使得 q1 qn 1 于是 H X i 1 n p i log 2 p i i 1 n p i log 2 q i i 1 n p i log 2 a s i i 1 n p i log 2 C i 1 n p i log 2 a s i log 2 C i 1 n s i p i log 2 a E S log 2 a displaystyle begin aligned H X amp sum i 1 n p i log 2 p i amp leq sum i 1 n p i log 2 q i amp sum i 1 n p i log 2 a s i sum i 1 n p i log 2 C amp sum i 1 n p i log 2 a s i log 2 C amp leq sum i 1 n s i p i log 2 a amp leq mathbb E S log 2 a end aligned 其中第二行由吉布斯不等式推出 而第五行由克拉夫特不等式推出 C i 1 n a s i 1 displaystyle C sum i 1 n a s i leq 1 因此 log C 0 对第二个不等式我们可以令 s i log a p i displaystyle s i lceil log a p i rceil 于是 log a p i s i lt log a p i 1 displaystyle log a p i leq s i lt log a p i 1 因此 a s i p i displaystyle a s i leq p i 并且 a s i p i 1 displaystyle sum a s i leq sum p i 1 因此由克拉夫特不等式 存在一种有这些字长的无前缀编码 因此最小的 S 满足 E S p i s i lt p i log a p i 1 p i log 2 p i log 2 a 1 H X log 2 a 1 displaystyle begin aligned mathbb E S amp sum p i s i amp lt sum p i left log a p i 1 right amp sum p i frac log 2 p i log 2 a 1 amp frac H X log 2 a 1 end aligned 参考资料 编辑 C E Shannon A Mathematical Theory of Communication 页面存档备份 存于互联网档案馆 Bell System Technical Journal vol 27 pp 379 423 623 656 July October 1948 David J C MacKay Information Theory Inference and Learning Algorithms 页面存档备份 存于互联网档案馆 Cambridge Cambridge University Press 2003 ISBN 0 521 64298 1 Cover Thomas M Chapter 5 Data Compression Elements of Information Theory John Wiley amp Sons 2006 ISBN 0 471 24195 4 取自 https zh wikipedia org w index php title 信源编码定理 amp oldid 76068494, 维基百科,wiki,书籍,书籍,图书馆,