兰州网站seo优化,比较好的购物网站,做网站的市场怎么样,网站宣传的劣势信息论
香农信息论发表于1948/1949年#xff0c;它由三部分组成#xff1a;信号采样、信源编码、信道编码#xff1b; 信号采样#xff1a;采样理论研究在何种条件下对连续信号进行采样#xff0c;从而得到的离散型号可以可逆地恢复出采样前的连续信号。采样得到的离散实…信息论
香农信息论发表于1948/1949年它由三部分组成信号采样、信源编码、信道编码 信号采样采样理论研究在何种条件下对连续信号进行采样从而得到的离散型号可以可逆地恢复出采样前的连续信号。采样得到的离散实数值代表着原来的信号信号通常有限精度量化成一个有限的符号集中。 信源编码信源编码研究如何将采样得到的离散数字信号编码成二进制序列它利用了信号的统计分布来将采集到的数字信号编码成最紧凑的二进制码。 信道编码信道编码研究如何给已经编码的序列中添加冗余性从而使它对传输中引入的错误或者攻击比如某些比特位存一定概率的翻转更具有鲁邦性它有时候也叫做纠错码理论。
信号采样
1.1 模拟信号与数字信号
为了能够利用数学工具分析性能数学建模通常建立在连续信号也称为模拟信号上。连续信号的设定的目的是为了能够表示物理世界采集到的真实信号比如从麦克风、数字相机或者医疗设备等传感器硬件采集的输入信号。模拟信号是一个一维函数 f 0 ∈ L 2 ( [ 0 , 1 ] ) f_0\in L^2([0,1]) f0∈L2([0,1])其中 [ 0 , 1 ] [0,1] [0,1]表示的信号采集域比如通常可能是时间轴。图像的模拟信号是一个二维函数 f 0 ∈ L 2 ( [ 0 , 1 ] 2 ) f_0\in L^2([0,1]^2) f0∈L2([0,1]2)其中单位正方形区域 [ 0 , 1 ] 2 [0,1]^2 [0,1]2是图像空间区域。 尽管目前仅仅关注在声音和自然图像信号的处理中但是这些方法中绝大部分都可以延伸到多维信号数据集的处理上多维信号具有更高的维度间的映射 f 0 : [ 0 , 1 ] d → [ 0 , 1 ] 2 f_0:[0,1]^d\rightarrow [0,1]^2 f0:[0,1]d→[0,1]2
其中 d d d是输入空间的维度 d 1 d1 d1表示声音信号 d 2 d2 d2表示图像信号 s s s表示特征空间的维度。比如对于灰度图像 d 2 , s 1 d2,s1 d2,s1对于视频图像 d 3 , s 1 d3,s1 d3,s1对于彩色图像 d 2 , s 3 d2,s3 d2,s3因为彩色图像有R/G/B三个通道。对于多光谱图像 d 2 , s ≫ 3 d2,s\gg 3 d2,s≫3因为它由大量的不同波段信号的采样。图1.1和图1.2是这样信号的一些基本例子。 1.1.1 信号获取与采样
信号采集是一个通过硬件设备将连续信号采集成离散信号的低维投影映射。麦克风是一维信号采样的例子数字相机是二维采样的例子采样操作对应这将连续函数信号映射到N维向量N的过程可以用如下公式表示 f 0 ∈ L 2 ( [ 0 , 1 ] d ) → f ∈ C N f_0\in L^2([0,1]^d)\rightarrow f\in \mathbb{C}^N f0∈L2([0,1]d)→f∈CN
图1.3是一些离散信号的例子 1.1.2 线性移不变采样器
线性移不变采样器执行采样操作是将连续信号和一个不变的脉冲响应 h h h在采样位置进行卷积运算 f n ∫ − S / 2 S / 2 f 0 ( x ) h ( n / N − x ) d x f 0 ⋆ h ( n / N ) (1.1) f_n\int_{-S/2}^{S/2}f_0(x)h(n/N-x)dxf_0\star h(n/N) \tag{1.1} fn∫−S/2S/2f0(x)h(n/N−x)dxf0⋆h(n/N)(1.1)
函数 h ( x ) h(x) h(x)的精确形状取决于采样设备它通常是一个低通滤波器并且在0附近取得最大值。采样器的尺寸 S S S决定了采样设备的采样精度它通常是与 1 / N 1/N 1/N同数量级的如果S太大会模糊信号如果S太小则会产生混叠现象。
1.2 香农采样定理
傅里叶变换回顾对于 f ∈ L 1 ( R ) f\in L^1(\mathbb{R}) f∈L1(R)它的傅里叶变换定义为 ∀ ω ∈ R , f ^ ( ω ) ∫ R f ( x ) e − i x ω d x . (1.2) \forall\omega\in\mathbb{R},\hat{f}(\omega)\int_{\mathbb{R}}f(x)e^{-ix\omega}dx.\tag{1.2} ∀ω∈R,f^(ω)∫Rf(x)e−ixωdx.(1.2)
由于有 ∣ ∣ f ^ ∣ ∣ 2 ( 2 π ) − 1 ∣ ∣ f ∣ ∣ 2 ||\hat{f}||^2(2\pi)^{-1}||f||^2 ∣∣f^∣∣2(2π)−1∣∣f∣∣2因此 f → f ^ f\rightarrow\hat{f} f→f^可以扩展到连续的 L 2 ( R ) L^2(\mathbb{R}) L2(R)这样计算函数 f f f的傅里叶变换 f ^ \hat{f} f^可以看做 l i m T → ∞ ∫ − T T f ( x ) e − i x ω d x lim_{T\rightarrow \infty}\int_{-T}^{T}f(x)e^{-ix\omega}dx limT→∞∫−TTf(x)e−ixωdx。当 f ^ ∈ L 1 ( R ) \hat{f}\in L^1(\mathbb{R}) f^∈L1(R)我们可以得到傅里叶逆变换 f ( x ) 1 2 π ∫ R f ^ ( ω ) e i x ω d ω , (1.3) f(x)\frac{1}{2\pi}\int_{\mathbb{R}}\hat{f}(\omega)e^{ix\omega}d\omega, \tag{1.3} f(x)2π1∫Rf^(ω)eixωdω,(1.3)
这表示了函数 f f f是连续的并且在 ± ∞ \pm\infty ±∞处极限趋于0。 傅里叶变换 F : f → f ^ \mathcal{F} :f\rightarrow\hat{f} F:f→f^交换了函数的正则性和衰减性。例如如果 f ∈ C p ( R ) f\in C^p(\mathbb{R}) f∈Cp(R)具有可积的傅里叶变换那么 F ( f ( p ) ) ( ω ) ( i ω ) p f ^ ( ω ) \mathcal{F}(f^{(p)})(\omega)(i\omega)^{p}\hat{f}(\omega) F(f(p))(ω)(iω)pf^(ω)因此 ∣ f ^ ( ω ) ∣ O ( 1 / ∣ ω ∣ p ) |\hat{f}(\omega)|O(1/|\omega|^p) ∣f^(ω)∣O(1/∣ω∣p)。相反地 ∫ R ( 1 ∣ ω ∣ ) p ∣ f ^ ( ω ) ∣ d ω ∞ ⇒ f ∈ C p ( R ) (1.4) \int_{\mathbb{R}}(1|\omega|)^p|\hat{f}(\omega)|d\omega\infty\Rightarrow f\in C^p(\mathbb{R}) \tag{1.4} ∫R(1∣ω∣)p∣f^(ω)∣dω∞⇒f∈Cp(R)(1.4)
例如当 f ^ ( ω ) O ( 1 / ∣ ω ∣ p 2 ) \hat{f}(\omega) O(1/|\omega|^{p2}) f^(ω)O(1/∣ω∣p2)可以推出 f ∈ C p ( R ) f\in C^p(\mathbb{R}) f∈Cp(R)。
傅里叶级数回顾我们记 T R / 2 π Z \mathbb{T}\mathbb{R}/2\pi\mathbb{Z} TR/2πZ为一系列的 2 π 2\pi 2π为周期的区间列。函数 f ∈ L 2 ( T ) f\in L^2(\mathbb{T}) f∈L2(T)是一个以 2 π 2\pi 2π为周期的函数它可以看成 f ∈ L 2 ( [ 0 , 2 π ] ) f\in L^2([0,2\pi]) f∈L2([0,2π])于是它的傅里叶系数为 ∀ n ∈ Z , f n ^ 1 2 π ∫ 0 2 π f ( x ) e − i x n d x . \forall n\in\mathbb{Z},\hat{f_n}\frac{1}{2\pi}\int_{0}^{2\pi}f(x)e^{-ixn}dx. ∀n∈Z,fn^2π1∫02πf(x)e−ixndx.
这个公式等价于求函数 f f f与基函数 e n e_n en的内积 f n ^ f , e n \hat{f_n}f,e_n fn^f,en内积定义为 f , g 1 2 π ∫ T f ( x ) g ‾ ( x ) d x f,g\frac{1}{2\pi}\int_{\mathbb{T}}f(x)\overline{g}(x)dx f,g2π1∫Tf(x)g(x)dx。在这里的内积中 e n e_n en是希尔伯特空间中的正交基这意味着可以通过如下收敛级数进行重建 f ∑ n ∈ Z f , e n e n (1.5) f\sum_{n\in\mathbb{Z}}f,e_ne_n \tag{1.5} fn∈Z∑f,enen(1.5)
这意味着在 N → ∞ N\rightarrow \infty N→∞时 ∣ ∣ f − ∑ n − N N f , e n e n ∣ ∣ L 2 ( T ) → 0 ||f-\sum_{n-N}^{N}f,e_ne_n||_{L^2(\mathbb{T})}\rightarrow 0 ∣∣f−∑n−NNf,enen∣∣L2(T)→0。如果函数 f f f可微那么在 x ∈ T x\in\mathbb{T} x∈T上可以保证公式1.5按点收敛。如果函数存在阶跃点那么在这些点数存在Gibbs震荡从而不能保证一致收敛但是级数仍然收敛域该点的左极限和右极限的一半。
泊松公式泊松公式连接了傅里叶变换与傅里叶技术到信号采样与周期化操作。对于某个定义在 R \mathbb{R} R的函数 h ( ω ) h(\omega) h(ω)它的周期化为 h P ( ω ) ∑ n h ( ω − 2 π n ) (1.6) h_P(\omega)\sum_{n}h(\omega-2\pi n) \tag{1.6} hP(ω)n∑h(ω−2πn)(1.6)
这个公式有意义的前提是 h ∈ L 1 ( R ) h\in L^1(\mathbb{R}) h∈L1(R) 并且在这种情况下 ∣ ∣ h P ∣ ∣ L 1 ( T ) ≤ ∣ ∣ h ∣ ∣ L 1 ( R ) ||h_P||_{L^1(\mathbb{T})}\le ||h||_{L^1(\mathbb{R})} ∣∣hP∣∣L1(T)≤∣∣h∣∣L1(R)。泊松公式阐明了如下关系 1信号 f ( x ) f(x) f(x)通过采样得到采样序列 ( f ( n ) ) n (f(n))_n (f(n))n对采样采样序列的傅里叶级数为 ∑ n f ( n ) e − i ω n \sum_{n}f(n)e^{-i\omega n} ∑nf(n)e−iωn 2信号 f ( x ) f(x) f(x)做傅里叶变换得到 f ^ ( ω ) \hat{f}(\omega) f^(ω)对傅里叶此福利也变化进行周期化得到傅里叶级数 ∑ n f ( n ) e − i ω n \sum_{n}f(n)e^{-i\omega n} ∑nf(n)e−iωn
引理1 泊松公式假设 f ^ \hat{f} f^是紧支撑的并且 ∣ f ( x ) ∣ ≤ C ( 1 ∣ x ∣ ) − 3 |f(x)|\le C(1|x|)^{-3} ∣f(x)∣≤C(1∣x∣)−3其中C为某个常数于是有 ∀ ω ∈ R , ∑ n f ( n ) e − i ω n f ^ P ( ω ) . (1.7) \forall\omega\in\mathbb{R}, \sum_{n}f(n)e^{-i\omega n}\hat{f}_P(\omega). \tag{1.7} ∀ω∈R,n∑f(n)e−iωnf^P(ω).(1.7)
证明由于 f ^ \hat{f} f^是紧支撑的 f ^ P \hat{f}_P f^P是良定义的并且 f f f很快衰减由公式1.4可知 ( f ^ ) P (\hat{f})_P (f^)P是 C 1 C^1 C1。于是可以由傅里叶级数展开 ( f ^ ) P ( ω ) ∑ k c k e i k ω (1.8) (\hat{f})_P(\omega)\sum_{k}c_ke^{ik\omega} \tag{1.8} (f^)P(ω)k∑ckeikω(1.8)
其中 c k 1 2 π ∫ 0 2 π ( f ^ ) P ( ω ) e − i k ω d ω 1 2 π ∫ 0 2 π ∑ n f ^ ( ω − 2 π n ) e − i k ω d ω c_k\frac{1}{2\pi}\int_{0}^{2\pi}(\hat{f})_P(\omega)e^{-ik\omega}d\omega\frac{1}{2\pi}\int_{0}^{2\pi}\sum_{n}\hat{f}(\omega-2\pi n)e^{-ik\omega}d\omega ck2π1∫02π(f^)P(ω)e−ikωdω2π1∫02πn∑f^(ω−2πn)e−ikωdω
又有 ∫ 0 2 π ∑ n ∣ f ^ ( ω − i π n ) e − i k ω ∣ d ω ∫ R ∣ f ^ ∣ \int_{0}^{2\pi}\sum_{n}|\hat{f}(\omega-i\pi n)e^{-ik\omega}|d\omega \int_{\mathbb{R}}|\hat{f}| ∫02πn∑∣f^(ω−iπn)e−ikω∣dω∫R∣f^∣
由于 f ^ ∈ L 1 ( R ) \hat{f}\in L^{1}(\mathbb{R}) f^∈L1(R)是有界的因此可以交换求和符号与积分号的运算顺序 c k ∑ n 1 2 π ∫ 0 2 π f ^ ( ω − 2 π n ) e − i k ω d ω 1 2 π ∫ m a t h b b R f ^ ( ω ) e − i k ω d ω f ( − k ) c_k\sum_{n}\frac{1}{2\pi}\int_{0}^{2\pi}\hat{f}(\omega-2\pi n)e^{-ik\omega}d\omega\frac{1}{2\pi}\int_{mathbb{R}}\hat{f}(\omega)e^{-ik\omega}d\omegaf(-k) ckn∑2π1∫02πf^(ω−2πn)e−ikωdω2π1∫mathbbRf^(ω)e−ikωdωf(−k)
由于 f ^ ∈ L 1 ( R ) \hat{f}\in L^1(\mathbb{R}) f^∈L1(R)因此这里我们运用1.3式中的傅里叶反变换是合理的。
注这里我们进一步解释一下引理1的内容信号 f ( t ) f(t) f(t)的傅里叶变换为 f ^ ( ω ) \hat{f}(\omega) f^(ω)我们对信号 f ( t ) f(t) f(t)在离散点 n n n处进行采样得到离散信号 f ( n ) f(n) f(n)离散信号 f ( n ) f(n) f(n)的福利变换为 ∑ n f ( n ) e − i ω n \sum_{n}f(n)e^{-i\omega n} ∑nf(n)e−iωn而引理1则说明了离散采样信号 f ( n ) f(n) f(n)的傅里叶变换等于原始连续信号 f ( t ) f(t) f(t)的傅里叶变换按照以 2 π 2\pi 2π为周期进行周期化的结果。
香农采样定理香农采样定理描述在什么采样步长 s 0 s0 s0的采样操作 f → ( f ( n s ) ) n f\rightarrow (f(ns))_n f→(f(ns))n下信号可以可逆恢复出原始信号的充分条件。它需要采样信号的频谱满足 s u p p ( f ^ ) ⊂ [ − π / s , π / s ] supp(\hat{f})\subset [-\pi/s,\pi/s] supp(f^)⊂[−π/s,π/s]。这个定理被奈奎斯特在1928年重新证明。它由于香农将其放于数字通信的论文中而变得非常出名。 定理1如果对于某个常数C有 ∣ f ( x ) ∣ ≤ C ( 1 ∣ x ∣ ) − 3 |f(x)|\le C(1|x|)^{-3} ∣f(x)∣≤C(1∣x∣)−3且 s u p p f ^ ⊂ [ − π / s , π / s ] supp\hat{f}\subset [-\pi/s,\pi/s] suppf^⊂[−π/s,π/s]于是有 ∀ x ∈ R f ( x ) ∑ n f ( n s ) s i n c ( x / s − n ) 其中 s i n c ( u ) s i n ( π u ) π u (1.9) \forall x\in\mathbb{R}f(x)\sum_{n}f(ns)sinc(x/s-n)其中sinc(u)\frac{sin(\pi u)}{\pi u} \tag{1.9} ∀x∈Rf(x)n∑f(ns)sinc(x/s−n)其中sinc(u)πusin(πu)(1.9)
一致收敛。 证明令 g ( x ) f ( s x ) g(x)f(sx) g(x)f(sx)那么 g ^ ( ω ) 1 / s f ^ ( ω / s ) \hat{g}(\omega)1/s\hat{f}(\omega/s) g^(ω)1/sf^(ω/s)事实上令 z s x zsx zsx那么有 g ^ ( ω ) ∫ f ( s x ) e − i ω x d x 1 s ∫ f ( z ) e − i ( ω / s ) z d z f ^ ( ω / s ) / s , \hat{g}(\omega)\int f(sx)e^{-i\omega x}dx\frac{1}{s}\int f(z)e^{-i(\omega/s)z}dz\hat{f}(\omega/s)/s, g^(ω)∫f(sx)e−iωxdxs1∫f(z)e−i(ω/s)zdzf^(ω/s)/s,
为了研究方便我们把 s s s置为1。紧支撑假设含有 f ^ ( ω ) 1 [ − p i , p i ] ( ω ) f ^ P ( ω ) \hat{f}(\omega)1_{[-pi,pi]}(\omega)\hat{f}_P(\omega) f^(ω)1[−pi,pi](ω)f^P(ω)。联合1.3式的逆变换与泊松公式1.8有 f ( x ) 1 2 π ∫ − ∞ ∞ f ^ ( ω ) e i ω x d ω 1 2 π ∫ π π f ^ P ( ω ) e i ω x 1 2 π ∫ − π π ∑ n f ( n ) e i ω ( x − n ) d ω . f(x)\frac{1}{2\pi}\int_{-\infty}^{\infty}\hat{f}(\omega)e^{i\omega x}d\omega\frac{1}{2\pi}\int_{\pi}^{\pi}\hat{f}_P(\omega)e^{i\omega x}\frac{1}{2\pi}\int_{-\pi}^{\pi}\sum_nf(n)e^{i\omega (x-n)}d\omega. f(x)2π1∫−∞∞f^(ω)eiωxdω2π1∫ππf^P(ω)eiωx2π1∫−ππn∑f(n)eiω(x−n)dω. 由于 f f f很快衰减于是 ∫ − π π ∑ n ∣ f ( n ) e i ω ( x − n ) ∣ d ω ∑ n ∣ f ( n ) ∣ ∞ \int_{-\pi}^{\pi}\sum_{n}|f(n)e^{i\omega(x-n)}|d\omega\sum_n|f(n)|\infty ∫−ππ∑n∣f(n)eiω(x−n)∣dω∑n∣f(n)∣∞因此可以交换求和与积分运算顺序于是有 f ( x ) ∑ n f ( n ) 1 2 π ∫ − π π e i ω ( x − n ) d ω ∑ n f ( x ) s i n c ( x − n ) f(x)\sum_{n}f(n)\frac{1}{2\pi}\int_{-\pi}^{\pi}e^{i\omega (x-n)}d\omega\sum_{n}f(x)sinc(x-n) f(x)n∑f(n)2π1∫−ππeiω(x−n)dωn∑f(x)sinc(x−n)
对于 s s s取其他值上面的证明过程类似。 定理1的重构公式存在一个问题它用了一个衰减缓慢且震荡剧烈的 s i n c ( x ) sinc(x) sinc(x)核函数。在实际应用中我们很少用这样的核函数的来插值而是更新换选择更光滑且局部性能更好的核函数。如果 s u p p ( f ^ ) ⊂ [ − π / s ′ , π / s ′ ] supp(\hat{f})\subset [-\pi/s^{},\pi/s^{}] supp(f^)⊂[−π/s′,π/s′]其中 s ′ s s^{}s s′s也就是具有更窄的频带我们也可以重新证明这个采样与重构过程于是可以具有更多的自由度来设计重构核函数现在可以选则在频域更窄在时域指数衰减的核函数。 样条插值函数的定义为 ϕ 0 1 [ − 1 / 2 , 1 / 2 ] \phi_01_{[-1/2,1/2]} ϕ01[−1/2,1/2]且 ϕ k ϕ k − 1 ∗ ϕ 0 \phi_k\phi_{k-1}*\phi_0 ϕkϕk−1∗ϕ0它是一个分线多项式函数阶数为 k k k并且有 k k k阶有界导数在区间 [ − ( k 1 ) / 2 , ( k 1 ) / 2 ] [-(k1)/2,(k1)/2] [−(k1)/2,(k1)/2]上紧支撑。采用样条函数作为插值核函数的重构公式为 f ( x ) ≈ f ~ ( x ) ∑ n a n ϕ ( x − n ) f(x)\approx\tilde{f}(x)\sum_{n}a_n\phi(x-n) f(x)≈f~(x)∑nanϕ(x−n)其中 ( a n ) n (a_n)_n (an)n通过 ( f ( n ) ) n (f(n))_n (f(n))n求解线性系统求得。仅在 k ∈ 0 , 1 k\in {0,1} k∈0,1时有 a n f ( n ) a_n f(n) anf(n)。在实际经常用的是三次样条插值对应的 k 3 k3 k3。 这个理论也解释了在信号 f f f的傅里叶变换 f ^ \hat{f} f^的支撑区间不是 [ − π / s , p i / s ] [-\pi/s,pi/s] [−π/s,pi/s]时会发生什么。这是会发生信号混叠现象在支撑区间 [ − π / s , p i / s ] [-\pi/s,pi/s] [−π/s,pi/s]的高频信号引起低频信号的的混乱叠加通常称为混叠现象。如果输入信号不是带宽有限的那么在采样之前进行一个预滤波平滑过滤掉频率支撑区间 [ − π / s , p i / s ] [-\pi/s,pi/s] [−π/s,pi/s]之外的高频信号非常重要这样可以有效的避免混叠现象。 量化在已经采集得到信号的离散序列之后为了能够有效存储和传输需要把信号用有限精度去量化。后面的信号压缩章节会详细降到如何通过变换编码在变换域中进行高效编码与量化这对于增强信源编码的性能非常有用。然而常用的量化策略是直接在采样信号上进行量化操作。 例如在采样步长为 s 1 / N s1/N s1/N时采集到长度问N的信号向量 ( u n f ( n / N ) ) n 1 N ∈ R N (u_nf(n/N))_{n1}^{N}\in \mathbb{R}^N (unf(n/N))n1N∈RN由于函数 f f f在有限的空间区间与香农采样定理需要函数的傅里叶变换 f ^ \hat{f} f^也是带宽有限互相矛盾因为一个函数 f f f不可能同时在时间域与频率域同时具有紧支撑特性因此在有限的存储空间上完美重构信号是不可能的。 选择一个量化步长 T T T量化算子 v n Q T ( u n ) ∈ Z v_nQ_T(u_n)\in\mathbb{Z} vnQT(un)∈Z在距离 T T T的整数倍附近取整例如 v Q t ( u ) ⇔ v − 1 2 ≤ u / T v 1 2 , vQ_t(u)\Leftrightarrow v-\frac{1}{2}\le u/T \lt v\frac{1}{2}, vQt(u)⇔v−21≤u/Tv21,
如图1.8所示。恢复信号的过程需要去量化最好的重构是 D T ( v ) T v D_T(v)Tv DT(v)Tv。量化然后取量化过程引入的最大误差是 T / 2 T/2 T/2因为 ∣ D T ( Q T ( u ) ) − u ∣ ≤ T / 2 |D_T(Q_T(u))-u|\le T/2 ∣DT(QT(u))−u∣≤T/2。量化过程是香农标准过程中唯一的误差引入源。 信号与图像的编码理论后续会单独开一个章节详细讲述这里暂时略过。 信道编码及纠错码理论是数字通信领域的核心内容数字通信不是我们研究的重点后续章节变不会继续论述。
注未经授权严谨转载
如有错误或者不解欢迎批评指正欢迎私信笔者讨论。
