實(shí)現(xiàn)卷積運(yùn)算的兩種方法為何得到結(jié)果的長度不一樣？

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

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

提問分析(Analaysis)

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

• 方法 1: 直接在時(shí)域利用公式計(jì)算；方法 2: 利用快速傅里葉變換加速計(jì)算；

這個(gè)問題涉及到關(guān)于卷積、相關(guān)運(yùn)算的如何定義、結(jié)果長度是多少、如何加速卷積相關(guān)運(yùn)算等問題。下面來分析一下其中的理由。

基礎(chǔ)理論(Principle)

1. 相關(guān)與卷積

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

兩個(gè)信號(hào)的相關(guān)運(yùn)算為：

對(duì)于實(shí)值信號(hào)來講，這兩個(gè)運(yùn)算主要區(qū)別就在于積分號(hào)內(nèi)部，第二個(gè)信號(hào)是否需要反褶[2]。如果參與運(yùn)算的第二個(gè)信號(hào)是偶信號(hào)[^3]，那么這兩個(gè)運(yùn)算就幾乎相同。因此，你所說它們?cè)谝欢ǔ潭壬鲜且粯泳哂幸欢ǖ牡览怼?/p>

當(dāng)然，這兩種運(yùn)算在使用目的、數(shù)學(xué)性質(zhì)方面還是有一定的差異。下面分析就主要以卷積運(yùn)算進(jìn)行討論。

當(dāng)信號(hào)為離散時(shí)間序列時(shí)，相應(yīng)的運(yùn)算就是累加和的形式。以卷積運(yùn)算為例：

卷積也可以擴(kuò)展到高維信號(hào)運(yùn)算。下面是二維圖像信號(hào)的離散卷積運(yùn)算。它被廣泛應(yīng)用到深度學(xué)習(xí)中的卷積神經(jīng)網(wǎng)絡(luò)中。

▲ 二維離散卷積和運(yùn)算

?

2. 有限長信號(hào)運(yùn)算結(jié)果長度

根據(jù)卷積運(yùn)算公式可以看出，參與卷積運(yùn)算的兩個(gè)信號(hào)，任選其中一個(gè)信號(hào)進(jìn)行反褶、平移，然后在于另外一個(gè)信號(hào)進(jìn)行相乘、積分便得到計(jì)算結(jié)果。

如果參與運(yùn)算的兩個(gè)信號(hào)的長度都是有限長，分別是，那么它們卷積結(jié)果也是一個(gè)有限長的信號(hào)，長度等于。

對(duì)于有限長的離散時(shí)間序列信號(hào)，它們的卷積結(jié)果的長度等于參與卷積的兩個(gè)信號(hào)長度之和，再減去 1。這些結(jié)論可以通過如下卷積運(yùn)算的圖解過程分析可得。

▲ 卷積運(yùn)算的圖解過程

相關(guān)運(yùn)算結(jié)果的長度也是類似的。

3. 計(jì)算復(fù)雜度

你的問題中提到了使用快速傅里葉變換（FFT）來加快計(jì)算卷積結(jié)果。相比于兩個(gè)信號(hào)的乘積運(yùn)算，信號(hào)的卷積（相關(guān)）運(yùn)算的確復(fù)雜。要獲得每一個(gè)結(jié)果值，都需要完成相應(yīng)的積分（累加和）。

比如，對(duì)于長度分別為的兩個(gè)序列，得到對(duì)應(yīng)長度為卷積結(jié)果，需要的乘法次數(shù)為，加法次數(shù)為。

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

▲ 利用 FFT 加速卷積運(yùn)算的示意圖

?

看似傅里葉變換“真香”，但它也會(huì)帶來麻煩。比如，兩個(gè)信號(hào)的時(shí)域乘積運(yùn)算，經(jīng)過傅里葉變換之后，在頻域又變成了卷積運(yùn)算。這還不是主要的問題，最主要的是，這種變化所完成的計(jì)算結(jié)果，是兩個(gè)信號(hào)的“圓卷積”。

4. 線卷積與圓卷積

由于快速傅里葉變換（FFT），是離散傅里葉變換（DFT）的快速算法，而離散傅里葉變換的公式來源于周期序列信號(hào)的傅里葉級(jí)數(shù)分解（DTFS）的 公式。所以本質(zhì)上講，他們反映的是周期離散序列信號(hào)中在一個(gè)周期內(nèi)有限個(gè)波形數(shù)據(jù)，與它的頻譜，也是一個(gè)周期序列信號(hào)，在一個(gè)周期內(nèi)的有限個(gè)頻譜數(shù)據(jù)之間的對(duì)應(yīng)關(guān)系。因此，通常對(duì)信號(hào)的平移、反褶等操作，都需要按照?qǐng)A位移、圓反褶來進(jìn)行，即先把信號(hào)拓展長一個(gè)周期信號(hào)，然后進(jìn)行相應(yīng)的平移，反褶。然后在結(jié)果的基礎(chǔ)上在提取其中的一個(gè)主周期[3]的數(shù)據(jù)。

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

▲ 圓位移示意圖

?

將卷積運(yùn)算中的反褶、位移都替換成圓反褶、圓位移，就形成了兩個(gè)信號(hào)的圓卷積操作。兩個(gè)信號(hào)進(jìn)行圓卷積，它們必須長度相同，圓卷積的結(jié)果等于兩個(gè)信號(hào)的長度本身，而不是它們的長度之和，再減一。

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

到此為止，我們知道為什么使用 FFT 加速卷積計(jì)算的結(jié)果與直接使用公式計(jì)算所得到的結(jié)果長度不同了。這是因?yàn)槔?FFT 所得到的卷積結(jié)果是兩個(gè)等長序列的圓卷積，與兩個(gè)序列的線卷積的結(jié)果是不同的。

那么，怎么解決這個(gè)問題呢？

問題解決(Problem)

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

圓卷積運(yùn)算要求參與運(yùn)算的兩個(gè)信號(hào)長度必須相同，滿足這一點(diǎn)是通過對(duì)短序列后面補(bǔ)零來實(shí)現(xiàn)。同樣，為了使得圓卷積也能夠得到和線卷積相同長度的結(jié)果，只要將兩個(gè)序列（長度分別為）長度通過補(bǔ)零延長到即可。這樣通過圓卷積所得到的結(jié)果不僅長度和線卷積的長度相同，實(shí)際上，結(jié)果也是一樣的。

下圖中顯示了兩個(gè)長度分別為 4,6 的信號(hào)，線卷積和圓卷積的結(jié)果，顯然它們是不同的。右邊通過補(bǔ)零，將它們的長度都擴(kuò)展到，所得到的圓卷積結(jié)果就與線卷積相同了。

▲ 圓卷積、線卷積、補(bǔ)零后的圓卷積

?

實(shí)驗(yàn)觀察(Laboratory)

下面是兩個(gè)序列以及它們的線卷積結(jié)果。

▲ 線卷積結(jié)果

?

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

▲ 線卷積的不同結(jié)果

?

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 可以實(shí)現(xiàn)圓卷積，需要將 mode 設(shè)置為"wrap"即可。

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

▲ 圓卷積結(jié)果

?

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

▲ 長度變化后的圓卷積結(jié)果

?

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)

擴(kuò)展聯(lián)系(Extention)

通過卷積、相關(guān)運(yùn)算，可以獲得豐富的信號(hào)處理能力。相關(guān)運(yùn)算就可以用于檢測(cè)信號(hào)之間的相似程度，并用于信號(hào)的位置檢測(cè)。

兩個(gè)有限長信號(hào)的相關(guān)運(yùn)算

使用快速傅里葉變換來加速卷積，相關(guān)運(yùn)算，可以達(dá)到實(shí)時(shí)信號(hào)處理的目的。通過在頻域數(shù)據(jù)的補(bǔ)零，還可以實(shí)現(xiàn)對(duì)卷積結(jié)果的理想插值。

其他相關(guān)提問

卓大大，有些同學(xué)提議學(xué)習(xí)美賽分成兩個(gè)時(shí)間段來做，我覺得這個(gè)建議不是特別妥當(dāng)。因?yàn)楣狡鹨娍隙ㄒ刂谱兞浚荣惌h(huán)節(jié)需要盡量一致。退一萬步說，一屆比賽獲獎(jiǎng)結(jié)果也是需要一起比較得出來的，即便是美賽也是一起評(píng)的獎(jiǎng)，八月份的比賽結(jié)果總不能等到寒假再出成績吧。望大大三思而后行。

博士您好，我在廣州的學(xué)校，學(xué)校通知六月底畢業(yè)生返校，我們這些大三的這學(xué)期估計(jì)沒辦法返校，就是有點(diǎn)擔(dān)心比賽的事情怎么進(jìn)行，畢竟三個(gè)組員沒辦法協(xié)同工作

卓大大，雙車組可以使用現(xiàn)成的電磁鐵模塊嗎，如圖。

?

▲ 電磁鐵模塊

回復(fù)：可以的。

參考資料

[1]十種信號(hào)運(yùn)算: 、相加、相乘、反褶、位移、尺度、微分、積分、卷積和相關(guān)

[2]說明: 信號(hào)反褶:信號(hào)的自變量改變符號(hào)，引起信號(hào)左右反轉(zhuǎn)對(duì)調(diào)。

[3]說明: 周期序列的主周期:定義為 0~N-1 對(duì)應(yīng)的一個(gè)周期內(nèi)的數(shù)據(jù)