你提的問題應該是在課堂上學習過

時間：2020-05-06 16:32:08

關鍵字： FFT LENGTH 位移 TC

手機看文章

掃描二維碼
隨時隨地手機看文章

[導讀]卓大大，打擾一下。我想問下您就是互相關運算和卷積在一定程度上是一樣的運算吧？那為什么卷積之后序列長度是2N-1，而互相關運算的結果按照那個頻域相乘再求快速傅里葉的逆變換得到的序列長度應該是就是之前的序列長度N吧？為啥和卷積的長度不一致呢？? 這里

卓大大，打擾一下。我想問下您就是互相關運算和卷積在一定程度上是一樣的運算吧？那為什么卷積之后序列長度是2N-1，而互相關運算的結果按照那個頻域相乘再求快速傅里葉的逆變換得到的序列長度應該是就是之前的序列長度N吧？為啥和卷積的長度不一致呢？

這里的頻域相乘應該就是對應的序列相乘吧？比如X[1]=a[1]*b[1]，這樣子我是哪里想錯了呢？麻煩卓大大解惑啦。

提問分析(Analaysis)

你所提出的問題是關于“信號與系統(tǒng)”學科中十種信號^[1]中的主要兩種復雜運算形式：卷積運算和相關運算。具體疑問是實現卷積運算的兩種方法為何得到結果的長度不一樣？

方法1: 直接在時域利用公式計算；
方法2: 利用快速傅里葉變換加速計算；

這個問題涉及到關于卷積、相關運算的如何定義、結果長度是多少、如何加速卷積相關運算等問題。下面來分析一下其中的理由。

基礎理論(Principle)

1. 相關與卷積

你一開始提到相關運算和卷積運算在一定程度上是一樣的運算吧？對的，這兩種運算的確很相像。從它們的公式就可以看出來：兩個連續(xù)時間信號的卷積運算為：

兩個信號的相關運算為：

對于實值信號來講，這兩個運算主要區(qū)別就在于積分號內部，第二個信號是否需要反褶^[2]。如果參與運算的第二個信號是偶信號[^3]，那么這兩個運算就幾乎相同。因此，你所說它們在一定程度上是一樣具有一定的道理。

當然，這兩種運算在使用目的、數學性質方面還是有一定的差異。下面分析就主要以卷積運算進行討論。

當信號為離散時間序列時，相應的運算就是累加和的形式。以卷積運算為例：

卷積也可以擴展到高維信號運算。下面是二維圖像信號的離散卷積運算。它被廣泛應用到深度學習中的卷積神經網絡中。

▲ 二維離散卷積和運算

2. 有限長信號運算結果長度

根據卷積運算公式可以看出，參與卷積運算的兩個信號，任選其中一個信號進行反褶、平移，然后在于另外一個信號進行相乘、積分便得到計算結果。

如果參與運算的兩個信號的長度都是有限長，分別是，那么它們卷積結果也是一個有限長的信號，長度等于。

對于有限長的離散時間序列信號，它們的卷積結果的長度等于參與卷積的兩個信號長度之和，再減去1。這些結論可以通過如下卷積運算的圖解過程分析可得。

▲ 卷積運算的圖解過程

相關運算結果的長度也是類似的。

3. 計算復雜度

你的問題中提到了使用快速傅里葉變換（FFT）來加快計算卷積結果。相比于兩個信號的乘積運算，信號的卷積（相關）運算的確復雜。要獲得每一個結果值，都需要完成相應的積分（累加和）。

比如，對于長度分別為的兩個序列，得到對應長度為卷積結果，需要的乘法次數為，加法次數為。

如何加快卷積運算呢？在數學上可以利用傅里葉變換的卷積定理，來將時域空間中的卷積運算轉換成頻域（變換域）中的乘積運算。由于存在著快速傅里葉變換變換算法，這就整體提高了計算的效率。

▲ 利用FFT加速卷積運算的示意圖

看似傅里葉變換“真香”，但它也會帶來麻煩。比如，兩個信號的時域乘積運算，經過傅里葉變換之后，在頻域又變成了卷積運算。這還不是主要的問題，最主要的是，這種變化所完成的計算結果，是兩個信號的“圓卷積”。

4. 線卷積與圓卷積

由于快速傅里葉變換（FFT），是離散傅里葉變換（DFT）的快速算法，而離散傅里葉變換的公式來源于周期序列信號的傅里葉級數分解（DTFS）的公式。所以本質上講，他們反映的是周期離散序列信號中在一個周期內有限個波形數據，與它的頻譜，也是一個周期序列信號，在一個周期內的有限個頻譜數據之間的對應關系。因此，通常對信號的平移、反褶等操作，都需要按照圓位移、圓反褶來進行，即先把信號拓展長一個周期信號，然后進行相應的平移，反褶。然后在結果的基礎上在提取其中的一個主周期^[3]的數據。

下圖顯示了圓位移的過程。

▲ 圓位移示意圖

將卷積運算中的反褶、位移都替換成圓反褶、圓位移，就形成了兩個信號的圓卷積操作。兩個信號進行圓卷積，它們必須長度相同，圓卷積的結果等于兩個信號的長度本身，而不是它們的長度之和，再減一。

由于有了圓卷積的定義，所以將原來的普通卷積稱為線卷積。

到此為止，我們知道為什么使用FFT加速卷積計算的結果與直接使用公式計算所得到的結果長度不同了。這是因為利用FFT所得到的卷積結果是兩個等長序列的圓卷積，與兩個序列的線卷積的結果是不同的。

那么，怎么解決這個問題呢？

問題解決(Problem)

解決方法很簡單，那就是補零，即在序列后面通過增加若干個0，來增加序列的長度。

圓卷積運算要求參與運算的兩個信號長度必須相同，滿足這一點是通過對短序列后面補零來實現。同樣，為了使得圓卷積也能夠得到和線卷積相同長度的結果，只要將兩個序列（長度分別為）長度通過補零延長到即可。這樣通過圓卷積所得到的結果不僅長度和線卷積的長度相同，實際上，結果也是一樣的。

下圖中顯示了兩個長度分別為4,6的信號，線卷積和圓卷積的結果，顯然它們是不同的。右邊通過補零，將它們的長度都擴展到，所得到的圓卷積結果就與線卷積相同了。

▲ 圓卷積、線卷積、補零后的圓卷積

實驗觀察(Laboratory)

下面是兩個序列以及它們的線卷積結果。

▲ 線卷積結果

計算結果調用了scipy.signal中的fftconvolve指令。參與運算的長度分別為10,14，線卷積結果的長度為23。在fftconvolve命令中，還可以通過改變參數mode，使其分別為“same”,"valide"，分別抽取結果中的長度為10,5的結果中心部分，這樣就可以獲得與參與卷積運算的最短序列相同，以及兩個序列完全重合的結果。

▲ 線卷積的不同結果

t = linspace(0, 10, 10, endpoint=False)[newaxis]d = ones((1, 14), dtype=int16)cv1 = fftconvolve(t, d, 'full')cv2 = fftconvolve(t, d, 'same')cv3 = fftconvolve(t, d, 'valid')

使用scipy.ndimage中的convolve可以實現圓卷積，需要將mode設置為"wrap"即可。

t = linspace(0, 10, 10, endpoint=False)[newaxis]d = ones((1, 14), dtype=int16)cvc = scipy.ndimage.convolve(t, d, mode='wrap')

▲ 圓卷積結果

下面是設定長度增加的圓卷積結果，長度從14一直增加到30?？梢钥吹綀A卷積的結果逐步與線卷積變得相同。直道長度大于23之后，圓卷積所得到的結果就變得與線卷積一樣了。

▲ 長度變化后的圓卷積結果

for i in range(30): length = 14+i t = linspace(0, length, length, endpoint=False)[newaxis] d = ones((1, length), dtype=int16)
 t[0][10:] = 0 d[0][14:] = 0

 cvc =scipy.ndimage.convolve(t,d, mode='wrap')
 plt.clf() plt.subplot(3,1,1) plt.stem(t[0]) plt.axis([0, length+1, 0, 10])
 plt.subplot(3,1,2) plt.stem(d[0]) plt.axis([0, length+1, 0, 5])
 plt.subplot(3,1,3) plt.stem(cvc[0]) plt.axis([0, length+1, 0, 100]) plt.draw() plt.pause(.5)