采样定理
采样定理是数字信号处理领域的重要定理。定理內容是连续信号(通常称作“模拟信号”)与离散信号(通常称作“数字信号”)之间的一个基本桥梁。它确定了信号带宽的上限,或能捕获连续信号的所有信息的离散采样信号所允许的采样频率的下限。
严格地说,定理仅适用于具有傅里叶变换的一类数学函数,即频率在有限区域以外为零(参照图1)。离散时间傅里叶变换(泊松求和公式的一种形式)提供了实际信号的解析延拓,但只能近似该条件。直观上我们希望,当把连续函数化为采样值(叫做“样本”)的离散序列并插值到连续函数中,结果的保真度取决于原始采样的密度(或采样率)。采样定理介绍了对带宽限制的函数类型来说保真度足够完整的采样率的概念;在采样过程中"信息"实际没有损失。定理用函数的带宽来表示采样率。定理也导出了一个数学上理想的原连续信号的重构公式。
该定理没有排除一些并不满足采样率准则的特殊情况下完整重构的可能性。(参见下文非基带信号采样,以及壓縮感知。)
奈奎斯特–香农采样定理的名字是为了紀念哈里·奈奎斯特和克劳德·香农。该定理及其在插值理论中的原型曾被奥古斯丁-路易·柯西、埃米尔·博雷尔、雅克·阿达马、夏尔-让·德拉瓦莱·普桑、埃德蒙·泰勒·惠特克、弗拉基米尔·亚历山德罗维奇·科捷利尼科夫等人发现或研究[1]:1-4。所以它还叫做奈奎斯特–香农–科捷利尼科夫定理、惠特克–香农–科捷利尼科夫定理、惠特克–奈奎斯特–科捷利尼科夫–香农定理及插值基本定理。
简介
采样是将一个信号(例如时间或空间上连续的函数)转换为数字序列(时间或空间上离散的函数)的过程。这个定理的香农版本陈述为:[2]
如果週期函數 x(t) 不包含高于 B cps(次/秒)的频率,那麼,一系列小於 1/(2B) 秒的x(t)函數值將會受到前一個週期的x(t)函數值影響。
因此 2B 样本/秒或更高的采样频率將能使函數不受干擾。相對的,对于一个给定的采样频率 fs,完全重构的频带限制为 B < fs/2。
在频带限制过高(或根本沒有频带限制)的情形下,重构表现出的缺陷称为混疊。現在對於此定義的陳述有時會很小心的指出x(t)必須不包括頻率恰好為B的正弦曲線,或是B必須小於½的取樣頻率。這二個門檻,2B及fs/2會稱為奈奎斯特速率及奈奎斯特频率。這些是x(t)及取樣設備的屬性。上述的不等式會稱為奈奎斯特準則,有時會稱為拉贝準則(Raabe condition)。此定理也可以用在其他定義域(例如離散系統)的函數下,唯一的不同是量測t, fs和B的單位。
符號 T = 1/fs 常用來表示二次取樣之間的時間間隔,稱為取樣周期或是取樣區間。函數x(t)的取樣常用x[n] = x(nT)表示(較早期的文獻會用xn),其中n為正整數。在數學上理想的取樣還原(插值)和Sinc函数有關,每次的取樣都用中心點在取樣時間nT,振幅是取樣值x[n]的Sinc函数代替。最後將Sinc函数加總,得到連續的函數。數學上等效的方式是將Sinc函数和一連串的狄拉克δ函数卷積,再依取樣到的值來加權。不過這些方式在數學上都是不實際的。不過有些有限長度的函數可以近似Sinc函数,這種因為近似的不完美造成的誤差稱為插值誤差(interpolation error)。
實際的數位類比轉換器既不會產生加權而有延遲的Sinc函数,也不會產生理想的狄拉克δ函数,若是其類比重建是用零階保持,其輸出的是由不同振幅及有延遲的矩形函数組成的阶跃函数,一般後面會有抗鏡像濾波器(anti-imaging filter)來清除假的高頻成份。
混疊
如果不能满足上述采样条件,采样后信号的频率就会重叠,即高于采样频率一半的频率成分将被重建成低于采样频率一半的信号。这种频谱的重叠导致的失真称为混叠,而重建出来的信号称为原信号的混叠替身,因为这两个信号有同样的样本值。
若x(t)為一函數,其傅里叶变换X(f)為:
泊松求和公式指出x(t)的取樣x(nT)足以產生X(f)的週期和,結果為:
是一個週期函數,等效為傅里叶级数,係數為T•x(nT)。此函數也稱為數列T•x(nT)的离散时间傅里叶变换 (DTFT),n為整數。
如图4所示,X(f) 的拷贝被平移了 fs 的倍数,并相加合并。对于一个带限函数(对所有 |f| ≥ B,X(f) = 0),在 fs 足够大的时候,这些拷贝之间仍然分得清楚。但如果奈奎斯特准则并不满足,相邻部分就会重叠,一般就不能明确辨别出 X(f)。任何超过 fs/2 的频率分量都会与较低的频率分量难以区分,称作与其中一个拷贝发生“混叠”。在这种情况下,通常的插值法就会产生混叠,而不是原始的分量了。
以下两种措施可避免混叠的发生:
当采样率预先由其他因素(如行业标准)确定的时候,x(t) 通常要先滤波以将高频分量减少到可以接受的水平,再进行采样。所需的滤波器的种类为低通滤波器,而在这种应用中叫做抗混叠滤波器。抗混叠滤波器可限制信号的带宽,使之满足采样定理的条件。这在理论上是可行的,但是在实际情况中不可能做到。因为滤波器不可能完全滤除奈奎斯特频率之上的信号,所以,采样定理要求的带宽之外总有一些“小的”能量。不过抗混叠滤波器可使这些能量足够小,以至可忽略不计。
由泊松求和的特例來推導
從圖5中可以看到,若X(f)的複本(也稱為鏡像)之間沒有和k = 0的項重疊,可以由Xs(f)用以下的乘積來還原:
- where:
此時證明了采样定理,因此X(f)可以確定x(t),而且只有唯一解。
剩下的就只有推導重構的公式。H(f)不需在[B, fs − B]的區域有準確的定義,因為Xs(f)在此區域為零。不過最壞的情形是B = fs/2,奈奎斯特频率。一個在此情形及其他較輕微的條件下都適用的函數為:
其中rect(•)為矩形函数,因此:
等式二側反轉換,可以得到惠特克-香農插值公式
上式就是用取樣值x(nT)來重構x(t)的方式。
- 若fs大於所需值,也就是T較小,稱為過取樣(oversampling),由圖5可以看出過取樣對重構訊號沒有任何效果,但可以提供一塊「轉態區」,此區域內的H(f)可以是一些非零的值。相反的,欠取樣會造成混疊,一般而言無法重構原始信號。
- 理論上,插值公式可以用低通滤波器來實現,其脈衝響應為sinc(t/T),輸入為,即為一個被取樣信號調變過的脈波序列函數。實際的數位類比轉換器(DAC)會用零階保持器來近似,此時過取樣可以減少近似的誤差。
香农的原始证明
泊松证明了Eq.1中的傅里叶级数会产生 X(f) 的周期求和,不管 fs 和 B 是什么值。然而香农只推导了 fs = 2B 情形下级数的系数。 几乎引用了香农原始的论文:
- 令 為 的频谱。则
- 因为假设在频带 以外 为零。若我们令
- 其中 n 为任意正整数或负整数,我们得到
- 在等式左邊的是在取樣點的數值,右邊的積分在本質上可以視為是的n次係數,以–B至B為其基礎週期[note 1]。這表示的取樣值也決定了傅立葉展開的第n次係數。對於比B低的頻率,若其傅立葉係數確定了,也就確定了,而在高於B的頻率,其數值為零,因此整個都可以確定。因為一函數的頻譜若確定了,其函數也就確定了,因此可以完全的決定原始函數,也就表示原始的取樣可以完整的決定函數。
香农對於此定理的證明已經完成了,不過香农進一步探討用Sinc函数重構原函數,也就是今日的惠特克–夏農內插公式,他沒有推導或是證明sinc函數的性質,但這些對於當時閱讀其作品的工程師不會覺得陌生,因為當時已經知道矩形函数和Sinc函数的傅立葉對關係。
- 令為第n個取樣點,則函數可以表示為:
和其他證明類似,此處假設原函數的傅立葉變換存在,因此證明中沒有說明採樣定理是否可以延伸到有限頻寬的固定隨機過程。
腳註
在多變數信號及圖形上的應用
采样定理常表示為單一變數的函數,因此定理可以直接應用到和時間相關的一維信號。不過采样定理可以直接延伸到任意數量變數的函數。例如像灰階影像常表示為二維的實數陣列(或是矩陣),其中的實數表示在對應行及列的取樣位置下,像素的相對強度。因此圖案會需要二個獨立的變數來表示其位置,一個表示對應的行,一個表示對應的列。
彩色影像一般會包括三個獨立的灰階值,分別表示紅色、綠色及藍色等三原色(三原色光模式,簡稱RGB)的強度。其他用三個元素的向量表示一個點的顏色空間有HSL和HSV色彩空间、CIELAB及XYZ等。而像CMYK則是用淺藍色、紫紅色、黃色及黑色的強度來表示。這些色彩空間都是二維空間上的向量值函數。
和一維離散信號的情形類似,若圖形的採樣解析度(或是像素密度)不適當,可能會有混疊的情形。例如密條紋襯衫若是用的數值若是用數位相機的图像传感器取樣時,可能會造成混疊,這種二維的混疊會形成莫列波紋,改善方式是提高空間的取樣率,例如拍照時更靠近襯衫,用高解析度的感測器,或是在取樣前先進行光學模糊處理。
另一個例子是右邊的方格條紋,上方的圖是不滿足采样定理下的信號。下方則是先經過低通濾波器再降采样,得到一個較小,但沒有莫列波紋。上圖則是直接降采样,沒有先經過低通處理後的圖。
采样定理在影像上的應用需小心的進行。例如相機中標準影像感測器(CCD或CMOS)的取樣程序和理想的取樣程序有相當的差距,理想的取樣程序會在一個點量測其影像強度,但影像感測器中為了獲得足夠的光量,其感測影像的區域較。換句話說,感測器是一個有限寬度的点扩散函数。一般而言這類感測器采樣到的類比光學資訊不是有限頻寬的,而不理想的采樣本身即為低通濾波器,不過不一定可以移除會造成混疊的高頻雜訊。若取樣區域(感測器大小)沒有大到可以有反鋸齒效果時,一般會需要獨立的反鋸齒濾鏡(光學低通濾鏡)來使影像模糊。雖然影像有這些和采樣定理有關的問題,不過采樣定理可以描述提升采样及减采样的基礎。
臨界頻率
為了描述fs > 2B的必要性,考慮右圖(圖8)中的一組弦波,公式如下,但θ值各有不同:
其中fs = 2B或是可以寫為T = 1/(2B),採樣值為:
和θ值無關。上述的歧義是采樣定理中使用嚴格的不等式,不允許等式的原因。
對於非基帶訊號的采样
香農曾提到[2]:
若頻帶的最小值不是零,而是由其他較大的值,也可以產生類似的結果,可以用線性轉換(對應物理上的单边带调制)到最小值為零的頻帶來證明。此例中基本脈波是单边带调制下的sin(x)/x。
因此這是一個針對沒有基帶成份信號(其頻帶有一部份的信號非零,但此寬度又和最大頻率無關)進行取樣的充份條件。
帶通條件為X(f) = 0,針對在所有在開區域範圍以外的非負f:
針對某非負整數N。此公式包括一般的基帶條件,N=0。
對應的內插函數為理想Sinc带通滤波器的脈衝響應,(而不是之前用的理想Sinc低通滤波器),會切掉頻帶的上方及下方,這也是一組低通滤波器脈衝響應的差:
其他的推廣,例如信號在數個不連續的頻帶,也是可行的。甚至是最廣義的取樣定理也不一定有一個可能正確的反例。也就是說無法確定是否只要不滿足取樣定理,就一定會有信號的喪失。不過以工程的角度來看,比較保守的作法是假設若不滿足取樣定理,就很可能會有信號的喪失。
非均勻採樣
香農的采样定理可以延伸到非均勻採樣,也就是採樣的時間間隔非一定值。非均勻採樣的采样定理指出針對band-limited的訊號,只要平均採樣頻率滿足奈奎斯特條件,就可以從採樣訊號完整重建原始訊號[4]。因此雖然均勻採樣在訊號重建的演算法上比較簡單,但這不是完整重建的必要條件。
非基帶及非均勻採樣的泛用理論是在1967年由亨利·藍道提出[5]。簡單的說,藍道證明了平均取樣率至少需要是信號佔據頻寬的二倍,但前提是已知信號的頻譜及其佔據的頻寬。 在1990年代末期,此研究已延伸到信號佔據頻寬的數量已知,但實際在頻譜上位置未知的情形[6]。在2000年代已利用壓縮感知發展了一個完整的理論。此理論用信號處理的語言寫成,在2009年的論文中發表[7]。論文中證明,若頻率的位置未知,則取樣頻率需至少為奈奎斯特準則的二倍。換句話說,因為不知道光學頻譜的位置,需要將取樣頻率乘二為代價。注意此最小取樣頻率的要求不一定保證其数值稳定性。
欠采样
当一个信号被欠采样时,必须满足采样定理以避免混叠。为了满足采样定理的要求,信号在进行减采样操作前,必须通过一个具有适当截止频率的低通滤波器。这个用于避免混叠的低通滤波器,称为抗混叠滤波器。
在奈奎斯特速率以下,有額外限制條件的采样
奈奎斯特–夏農取樣定理是對於帶限函數取樣及重建的充分条件。若是用惠特克–夏農內插公式重建原訊號,奈奎斯特準則也是避免混疊的必要條件,因為若採樣速率小於信號頻帶限制的二倍,可能有些信號無法正確重建。不過若信號有其他的限制,則奈奎斯特準則就不是混疊的必要條件了。
像近來在進行研究的壓縮感知就是一個利用對信號額外假設來進行壓縮的例子,壓縮感知可以用奈奎斯特速率要慢的速率採樣,然後可以完整的重建原訊號。這特別用在信號在一些層面較稀疏(或可壓縮)的情形。像壓縮感知可以處理有效頻寬(EB))很低,但不確定其頻率分佈位置的信號(此時采样定理就不適用了)。換句話說,其頻譜較稀疏。若用采样定理,最小的採樣速率是2B,若是用壓縮感知,採樣速率若略低於2EB,仍可以完整的重建。不過此作法的重建已不再是用公式處理,而是要求解凸優化,需要有良好研究,而可能是非線性的方式處理。
歷史背景
哈里·奈奎斯特1928年的論文《Certain topics in telegraph transmission theory》中就已隱含了采样定理,他證明了一個頻寬為B的系統可以傳送最多2B個獨立的脈波,不過他沒有直接處理連續信號取樣及重建的問題。同一時期的卡爾·庫普夫米勒證明了類似的結果[8],也討論到頻帶限制濾波器的sinc函數冲激响应,以及其積分,步階響應的三角积分,頻帶限制濾波器及信號重建濾波器是採樣定理的核心,因此在一些地區會將這二個濾波器稱為Küpfmüller filter。
采样定理是在香农在1949年《Communication in the presence of noise》中提出。之前相關的研究有V. A. Kotelnikov在1933年《在電纜及"以太"中電子通訊的傳輸能力》(翻譯自俄文),以及數學家埃德蒙·泰勒·惠特克在1915年的《Expansions of the Interpolation-Theory》(Theorie der Kardinalfunktionen)、J. M. Whittaker在1935年的《Interpolatory function theory》以及丹尼斯·加博尔1946年提出的《Theory of communication》。1999年時愛德華萊茵基金會給予科捷利尼科夫基礎研究獎,原因是「第一位提出理論正確的採樣定理」[9]。
相關條目
參考資料
- ^ John J. Benedetto, Paulo J. S. G. Ferreira (编). Modern Sampling Theory: Mathematics and Applications. Applied and Numerical Harmonic Analysis. Boston, MA, USA: Birkhäuser. 2001. ISBN 978-0-8176-4023-1 (英语).
- ^ 2.0 2.1 , "Communication in the presence of noise", Proc. Institute of Radio Engineers, vol. 37, no. 1, pp. 10–21, Jan. 1949. Reprint as classic paper in: Proc. IEEE, vol. 86, no. 2, (Feb. 1998) 互联网档案馆的存檔,存档日期2010-02-08.
- ^ sinc函數依照傅里叶变换表的202行及102行
- ^ Nonuniform Sampling, Theory and Practice (ed. F. Marvasti), Kluwer Academic/Plenum Publishers, New York, 2000
- ^ Landau, H. J. Necessary density conditions for sampling and interpolation of certain entire functions. Acta Math. 1967, 117 (1): 37–52. doi:10.1007/BF02395039.
- ^ see, e.g., Feng, P. Universal minimum-rate sampling and spectrum-blind reconstruction for multiband signals. Ph.D. dissertation, University of Illinois at Urbana-Champaign. 1997.
- ^ Mishali, Moshe; Eldar, Yonina C. Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals. IEEE Trans. Signal Processing. March 2009, 57 (3). CiteSeerX: 10.1.1.154.4255.
- ^ Küpfmüller, Karl. Über die Dynamik der selbsttätigen Verstärkungsregler. Elektrische Nachrichtentechnik. 1928, 5 (11): 459–467 (德语). (English translation 2005) (页面存档备份,存于互联网档案馆).
- ^ Basic Research Award 1999 互联网档案馆的存檔,存档日期2015-02-02.
- E. T. Whittaker, "On the Functions Which are Represented by the Expansions of the Interpolation Theory," Proc. Royal Soc. Edinburgh, Sec. A, vol.35, pp.181-194, 1915
- H. Nyquist, "Certain topics in telegraph transmission theory," Trans. AIEE, vol. 47, pp. 617-644, Apr. 1928.
- V. A. Kotelnikov, "On the carrying capacity of the ether and wire in telecommunications," Material for the First All-Union Conference on Questions of Communication, Izd. Red. Upr. Svyazi RKKA, Moscow, 1933 (Russian).
- C. E. Shannon, "Communication in the presence of noise", Proc. Institute of Radio Engineers, vol. 37, no.1, pp. 10-21, Jan. 1949.
- J. R. Higgins: Five short stories about the cardinal series, Bulletin of the AMS 12(1985)
- V. A. Kotelnikov, "On the carrying capacity of the ether and wire in telecommunications", Material for the First All-Union Conference on Questions of Communication, Izd. Red. Upr. Svyazi RKKA, Moscow, 1933 (Russian). (english translation, PDF) (页面存档备份,存于互联网档案馆)
- Karl Küpfmüller, "Utjämningsförlopp inom Telegraf- och Telefontekniken", ("Transients in telegraph and telephone engineering"), Teknisk Tidskrift, no. 9 pp. 153–160 and 10 pp. 178–182, 1931. [1] (页面存档备份,存于互联网档案馆) [2] (页面存档备份,存于互联网档案馆)
- R.J. Marks II: Introduction to Shannon Sampling and Interpolation Theory (页面存档备份,存于互联网档案馆), Spinger-Verlag, 1991.
- R.J. Marks II, Editor: Advanced Topics in Shannon Sampling and Interpolation Theory (页面存档备份,存于互联网档案馆), Springer-Verlag, 1993.
- R.J. Marks II, Handbook of Fourier Analysis and Its Applications, Oxford University Press, (2009), Chapters 5-8. Google books (页面存档备份,存于互联网档案馆).
- H. Nyquist, "Certain topics in telegraph transmission theory", Trans. AIEE, vol. 47, pp. 617–644, Apr. 1928 Reprint as classic paper in: Proc. IEEE, Vol. 90, No. 2, Feb 2002.
- Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP, Section 13.11. Numerical Use of the Sampling Theorem, Numerical Recipes: The Art of Scientific Computing 3rd, New York: Cambridge University Press, 2007 [2016-03-16], ISBN 978-0-521-88068-8, (原始内容存档于2011-08-11)
- C. E. Shannon, "Communication in the presence of noise", Proc. Institute of Radio Engineers, vol. 37, no.1, pp. 10–21, Jan. 1949. Reprint as classic paper in: Proc. IEEE, Vol. 86, No. 2, (Feb 1998)
- Michael Unser: Sampling-50 Years after Shannon (页面存档备份,存于互联网档案馆), Proc. IEEE, vol. 88, no. 4, pp. 569–587, April 2000
- E. T. Whittaker, "On the Functions Which are Represented by the Expansions of the Interpolation Theory", Proc. Royal Soc. Edinburgh, Sec. A, vol.35, pp. 181–194, 1915
- J. M. Whittaker, Interpolatory Function Theory, Cambridge Univ. Press, Cambridge, England, 1935.
外部連結
- Learning by Simulations (页面存档备份,存于互联网档案馆) Interactive simulation of the effects of inadequate sampling
- Interactive presentation of the sampling and reconstruction in a web-demo Institute of Telecommunications, University of Stuttgart
- Undersampling and an application of it (页面存档备份,存于互联网档案馆)
- Sampling Theory For Digital Audio
- Journal devoted to Sampling Theory (页面存档备份,存于互联网档案馆)
- Sampling Theorem with Constant Amplitude Variable Width Pulse (页面存档备份,存于互联网档案馆)
- "The Origins of the Sampling Theorem" by Hans Dieter Lüke published in "IEEE Communications Magazine" April 1999. CiteSeerX: 10.1.1.163.2887.