當(dāng)前位置:首頁 > 公眾號(hào)精選 > TsinghuaJoking
[導(dǎo)讀]卓大大,打擾一下。我想問下您就是互相關(guān)運(yùn)算和卷積在一定程度上是一樣的運(yùn)算吧?那為什么卷積之后序列長(zhǎng)度是2N-1,而互相關(guān)運(yùn)算的結(jié)果按照那個(gè)頻域相乘再求快速傅里葉的逆變換得到的序列長(zhǎng)度應(yīng)該是就是之前的序列長(zhǎng)度N吧?為啥和卷積的長(zhǎng)度不一致呢?? 這里

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

這里的頻域相乘應(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é)果的長(zhǎng)度不一樣?

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

這個(gè)問題涉及到關(guān)于卷積、相關(guān)運(yùn)算的如何定義、結(jié)果長(zhǎng)度是多少、如何加速卷積相關(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. 有限長(zhǎng)信號(hào)運(yùn)算結(jié)果長(zhǎng)度

根據(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) 的長(zhǎng)度都是有限長(zhǎng),分別是 ,那么它們卷積結(jié)果 也是一個(gè)有限長(zhǎng)的信號(hào),長(zhǎng)度等于 。

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

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

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

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

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

比如,對(duì)于長(zhǎng)度分別為 的兩個(gè)序列,得到對(duì)應(yīng)長(zhǎ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)的平移、反褶等操作,都需要按照圓位移、圓反褶來進(jìn)行,即先把信號(hào)拓展長(zhǎng)一個(gè)周期信號(hào),然后進(jìn)行相應(yīng)的平移,反褶。然后在結(jié)果的基礎(chǔ)上在提取其中的一個(gè)主周期[3]的數(shù)據(jù)。

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

▲ 圓位移示意圖

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

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

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

那么,怎么解決這個(gè)問題呢?

問題解決(Problem)

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

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

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

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

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

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

▲ 線卷積結(jié)果

計(jì)算結(jié)果調(diào)用了scipy.signal中的fftconvolve指令。參與運(yùn)算的 長(zhǎng)度分別為10,14,線卷積結(jié)果的長(zhǎng)度為23。在fftconvolve命令中,還可以通過改變參數(shù)mode,使其分別為“same”,"valide",分別抽取結(jié)果中的長(zhǎng)度為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è)定長(zhǎng)度增加的圓卷積結(jié)果,長(zhǎng)度從14一直增加到30??梢钥吹綀A卷積的結(jié)果逐步與線卷積變得相同。直道長(zhǎng)度大于23之后,圓卷積所得到的結(jié)果就變得與線卷積一樣了。

▲ 長(zhǎng)度變化后的圓卷積結(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è)有限長(zhǎng)信號(hào)的相關(guān)運(yùn)算

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

應(yīng)用于今年智能車競(jìng)賽信標(biāo)組比賽的相關(guān)文獻(xiàn)如下:

  1. 室外聲音信標(biāo)可行性分析[4]

  2. 聲音信標(biāo)調(diào)試[5]

  3. 聲音信標(biāo)長(zhǎng)啥樣子?[6]

  4. 信標(biāo)的信號(hào)[7]

今天討論的這個(gè)問題,是本學(xué)期“信號(hào)與系統(tǒng)”課程中的具體應(yīng)用。在很多情況下,同學(xué)們也許不清楚其中的基本原理,也可以直接使用各種軟件工具獲得結(jié)果。在課堂中的學(xué)習(xí)可能更多的是這些原理的數(shù)學(xué)描述。

如果沒有具體的應(yīng)用背景,同學(xué)們可否能夠在課堂學(xué)習(xí)中激發(fā)起濃厚的興趣呢?這是我在教學(xué)中一直在擔(dān)心的一個(gè)主要問題。

還好吧,對(duì)于清華的同學(xué)來講,他們不愁找不到學(xué)習(xí)的理由。


其他相關(guān)提問

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

博士您好,我在廣州的學(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ù)

[4]

室外聲音信標(biāo)可行性分析: https://zhuoqing.blog.csdn.net/article/details/104231420

[5]

聲音信標(biāo)調(diào)試: https://zhuoqing.blog.csdn.net/article/details/105004283

[6]

聲音信標(biāo)長(zhǎng)啥樣子?: https://zhuoqing.blog.csdn.net/article/details/105207528

[7]

信標(biāo)的信號(hào): https://zhuoqing.blog.csdn.net/article/details/105575349

免責(zé)聲明:本文內(nèi)容由21ic獲得授權(quán)后發(fā)布,版權(quán)歸原作者所有,本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn),不代表本平臺(tái)立場(chǎng),如有問題,請(qǐng)聯(lián)系我們,謝謝!

本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請(qǐng)及時(shí)聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫?dú)角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時(shí)1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動(dòng) BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時(shí)企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險(xiǎn),如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報(bào)道,騰訊和網(wǎng)易近期正在縮減他們對(duì)日本游戲市場(chǎng)的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn): 有效應(yīng)對(duì)環(huán)境變化,經(jīng)營(yíng)業(yè)績(jī)穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤(rùn)率延續(xù)升勢(shì) 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長(zhǎng) 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競(jìng)爭(zhēng)力 堅(jiān)持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競(jìng)爭(zhēng)優(yōu)勢(shì)...

關(guān)鍵字: 通信 BSP 電信運(yùn)營(yíng)商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺(tái)與中國電影電視技術(shù)學(xué)會(huì)聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會(huì)上宣布正式成立。 活動(dòng)現(xiàn)場(chǎng) NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長(zhǎng)三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會(huì)上,軟通動(dòng)力信息技術(shù)(集團(tuán))股份有限公司(以下簡(jiǎn)稱"軟通動(dòng)力")與長(zhǎng)三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉