DSP_12離散傅立葉變換-循環(huán)卷積

1、利用循環(huán)卷積計(jì)算線性卷積利用循環(huán)卷積計(jì)算線性卷積 Linear Convolution Computation by Circular Convolution2022-4-272一個(gè)問題一個(gè)問題許多實(shí)際問題中常需要計(jì)算線性卷積，如一個(gè)許多實(shí)際問題中常需要計(jì)算線性卷積，如一個(gè)FIR數(shù)字?jǐn)?shù)字濾波器的輸出就等于輸入與濾波器的單位取樣響應(yīng)的濾波器的輸出就等于輸入與濾波器的單位取樣響應(yīng)的線性卷積。而循環(huán)卷積可以利用后面介紹的線性卷積。而循環(huán)卷積可以利用后面介紹的FFT進(jìn)行快進(jìn)行快速計(jì)算，因此就提出一個(gè)問題：如何利用循環(huán)卷積計(jì)速計(jì)算，因此就提出一個(gè)問題：如何利用循環(huán)卷積計(jì)算線性卷積，或者是，算線性卷積，或

2、者是，在什么條件下循環(huán)卷積等于線在什么條件下循環(huán)卷積等于線性卷積？性卷積？2022-4-273一個(gè)結(jié)論一個(gè)結(jié)論設(shè)進(jìn)行線性卷積的兩個(gè)序列設(shè)進(jìn)行線性卷積的兩個(gè)序列 和和 的長度分的長度分別為別為 M 和和 N，則在它們的后面添加零使它們成為長度，則在它們的后面添加零使它們成為長度的序列，再求它們的的序列，再求它們的 L 點(diǎn)的循環(huán)卷積，結(jié)果序列長度點(diǎn)的循環(huán)卷積，結(jié)果序列長度為為 L 。則循環(huán)卷積結(jié)果就是線性卷積，即。則循環(huán)卷積結(jié)果就是線性卷積，即 nx1 nx21NML 1212x nxnx nxn2022-4-274利用利用FFT進(jìn)行線性卷積計(jì)算進(jìn)行線性卷積計(jì)算根據(jù)上面結(jié)論，利用根據(jù)上面結(jié)論，利用

3、FFT計(jì)算兩序列的線性卷積過程如計(jì)算兩序列的線性卷積過程如下。設(shè)進(jìn)行線性卷積的兩序列為下。設(shè)進(jìn)行線性卷積的兩序列為 和和n=length(x1); m=length(x2); L=m+n-1y=ifft(fft(x1,L).*fft(x2,L); nx1 nx22022-4-275為什么在序列擴(kuò)展成長度為什么在序列擴(kuò)展成長度 后它們的循環(huán)卷積就后它們的循環(huán)卷積就是它們的線性卷積。是它們的線性卷積。1NML5N8M12L反折2右移1L右移 0y 2y1Ly圖形解釋圖形解釋2022-4-276圓周卷積(循環(huán)卷積)和線性卷積間的關(guān)系1120( )()( )NNmrx mx nrNm Rn1120(

4、)()( )NNrmx m x nrNm Rn()( )lNry nrNRn對x1(n)和x2(n)補(bǔ)零，使其長度均為N點(diǎn)；222( )( )()Nrx nxnx nrN對x2(n)周期延拓：1120( )( )() ( )NcNNmy nx m xnmRn圓周卷積：2022-4-277121NNNN即 當(dāng)圓周卷積長度時(shí)， 點(diǎn)圓周卷積能代表線性卷積12( )1ly nNN而的長度為( )( )NclNy ny n點(diǎn)圓周卷積是線性卷積以 為周期的周期延拓序列的主值序列。12-1( )lNNNy nN只有當(dāng)時(shí)，以 為周期進(jìn)行周期延拓才無混疊現(xiàn)象N1212( ) ( )( )*( )x nx nx

5、nx n1212102NNNnNN圓周卷積和線性卷積間的關(guān)系2022-4-278頻率取樣頻率取樣 Frequency Sampling頻率取樣是指對序列的傅立葉變換或系統(tǒng)的頻率特性進(jìn)行頻率取樣是指對序列的傅立葉變換或系統(tǒng)的頻率特性進(jìn)行取樣。本節(jié)討論在上面條件下能夠用得到的頻譜取樣值無取樣。本節(jié)討論在上面條件下能夠用得到的頻譜取樣值無失真地恢復(fù)原信號或系統(tǒng)。失真地恢復(fù)原信號或系統(tǒng)。設(shè)任意長序列設(shè)任意長序列 絕對可和，其絕對可和，其Z變換為變換為如果在單位圓上對如果在單位圓上對 進(jìn)行等角距取樣，取樣點(diǎn)數(shù)為進(jìn)行等角距取樣，取樣點(diǎn)數(shù)為 M，則得則得 nx nnznxzX zX nkMnWzWnxzXk

6、XkM2022-4-279頻率取樣頻率取樣 Frequency Sampling根據(jù)根據(jù)DFT的定義，對的定義，對 求反變換得求反變換得代入代入 ，得，得而而 nkMMkpWkXMnx101 kX kX 101010111MkmnkMmnkMMkmkMmnkMMkpWMmxWWmxMWkXMnxrMnmrMnmWMMkmnkM, 0, 11102022-4-2710頻率取樣頻率取樣 Frequency Sampling所以所以該式表明，該式表明，在在Z平面的單位圓上對序列的平面的單位圓上對序列的Z變換進(jìn)行等角距變換進(jìn)行等角距取樣，將導(dǎo)致時(shí)間序列的周期化取樣，將導(dǎo)致時(shí)間序列的周期化。這一結(jié)果與對

7、連續(xù)時(shí)間。這一結(jié)果與對連續(xù)時(shí)間信號取樣導(dǎo)致頻譜周期化類似。信號取樣導(dǎo)致頻譜周期化類似。 是一個(gè)周期序列，是一個(gè)周期序列，其主值為其主值為 rprMnxnx nxp nRrMnxnRnxnxNrNpN2022-4-2711頻率取樣頻率取樣 Frequency Sampling在在 為有限長度為有限長度 N 的情況下，如果取樣點(diǎn)的情況下，如果取樣點(diǎn) ，那么那么 周期延拓的結(jié)果不會產(chǎn)生混疊。這時(shí)周期延拓的結(jié)果不會產(chǎn)生混疊。這時(shí) 的主值的主值 與原序列與原序列 一樣，因此一樣，因此 完全能代完全能代表原序列表原序列 。如果。如果 ，則，則 周期延拓后一定周期延拓后一定產(chǎn)生混疊，因而產(chǎn)生混疊，因而 不能

8、無失真地代表原信號不能無失真地代表原信號 。在。在 為無限長的情況下，對為無限長的情況下，對Z變換取樣必然導(dǎo)致混疊失真，因變換取樣必然導(dǎo)致混疊失真，因此此 不能代表原序列不能代表原序列 。用。用MATLAB演示：演示：x=1:8; xf=freqz(x, 1, 6, whole); ifft(xf) nxNM nx nxp nxN nx nxN nxNM nx nxN nx nx nxNx=1:8; xf=freqz(x, 1, 8, whole); ifft(xf)2022-4-2712頻率取樣頻率取樣 Frequency Sampling對于長度為對于長度為 N 的有限長序列，對的有限長序

9、列，對Z變換取樣即頻率取樣不變換取樣即頻率取樣不失真的條件是取樣點(diǎn)數(shù)失真的條件是取樣點(diǎn)數(shù) M 應(yīng)等于或大于原序列的長度應(yīng)等于或大于原序列的長度 N，即即 。在。在 時(shí)，時(shí)，Z變換的取樣即變換的取樣即DFT，也，也即即 ，利用，利用IDFT公式可由公式可由 恢復(fù)原序列恢復(fù)原序列 ，即，即進(jìn)一步利用進(jìn)一步利用Z變換公式還可恢復(fù)變換公式還可恢復(fù)Z變換，變換，NM kX nx nkNNkWkXNnx101NM kX2022-4-2713頻率取樣頻率取樣 Frequency Sampling即即或或其中其中 101101101010101011111111NkkNNNkkNNNkNNkNnnnkNnnkNNnNknNnzWzkXNzWzWkXNzWkXNzWkXNznxzX 10NkzkXzX 111zWNzzkNN該式是用該式是用 在單位圓上的在單位圓上的N個(gè)取樣值表示個(gè)取樣值表示 的的內(nèi)插公式內(nèi)插公式這個(gè)是這個(gè)是內(nèi)插函數(shù)內(nèi)插函數(shù) zX zX2022-4-2714頻率取樣頻率取樣 Frequency Sampling將將 代入內(nèi)插公式，便得到傅立葉變換的內(nèi)插公式代入內(nèi)插公式，便得到傅立葉變換的內(nèi)插公式其中其中函數(shù)函數(shù) 在在 時(shí)的模值均為時(shí)的模值均為