简介
编辑在信息论中,信源编码定理(或无噪声编码定理)确定了可能的数据压缩的限制,以及香农熵的操作意义。
源编码定理以克劳德·香农命名,它表明(在极限情况下,随着独立同分布随机变量 (i.i.d.) 数据流的长度趋于无穷大)不可能压缩数据使得码率 (每个符号的平均位数)小于源的 Shannon 熵,实际上不能确定信息会丢失。然而,有可能获得任意接近香农熵的码率,损失概率可以忽略不计。
符号代码的源编码定理在代码字的最小可能预期长度上设置了上限和下限,作为输入字(被视为随机变量)的熵和目标字母表大小的函数。
声明
编辑源编码是从信息源的(一系列)符号到一系列字母符号(通常是位)的映射,使得源符号可以从二进制位(无损源编码)中准确地恢复或在一定失真范围内恢复( 有损源编码)。 这是数据压缩背后的概念。
源编码定理
编辑在信息论中,源编码定理非正式地指出:
Ni.i.d. 每个具有熵 H(X) 的随机变量都可以压缩成多于 N H(X) 位,信息丢失的风险可以忽略不计,因为 N → ∞; 但相反,如果它们被压缩成少于 N H(X) 位,则几乎可以肯定信息会丢失。
编码序列以双义方式表示压缩消息,假设解码器知道源。从实际的角度来看,这个假设并不总是正确的。通常,表征源的信息被插入到传输消息的开头。
符号代码的源编码定理
编辑令 Σ1, Σ2 表示两个有限字母表,令 Σ∗1 和 Σ∗2 分别表示这些字母表中所有有限词的集合。
假设 X 是一个随机变量,取 Σ1 中的值,让⟩f⟩ 是从 Σ∗1 到 Σ 的唯一可解码代码 ∗2 其中|Σ2| =一个。 令 S 表示由码字长度 ⟩f⟩(X) 给出的随机变量。
证明:源编码定理
编辑给定 X 是 i.i.d. 源,它的时间序列 X1, …, Xn 是 i.i.d. 在离散值情况下具有熵 H(X),在连续值情况下具有微分熵。 源编码定理指出,对于任何 ε > 0,即对于大于源熵的任何速率 H(X) + ε,都有足够大的 n 和一个采用 n i.i.d 的编码器。 重复源 X1:n,并将其映射到 n(H(X) + ε) 个二进制位,这样源符号 X1:n 可以从二进制位恢复,概率至少为 1 − ε。
内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/193721/