Fast Fourier Transform of Convolution and Correlation of Discrete Sequences

bqgup

Fast Fourier Transform of Convolution and Correlation of Discrete Sequences [Copy link]

<div class='showpostmsg'># Convolution operation of discrete sequence and fast Fourier transform of correlation operation# Convolution operation of discrete sequence and fast Fourier transform#### The convolution of discrete sequence signals f(n), g(n) is: 
<ignore_js_op>

<div class="tip tip_4 aimg_tip" id="aimg_466780_menu" style="position: absolute; display: none" disautofocus="true">
<div class="xs0">
<p><strong>1.png</strong> <em class="xg1">(2.87 KB, downloads: 0)</em></p>
<p>
<a href="javascript:;" class="loginf" >download attach</a>

<a href="javascript:;" onclick="showWindow(this.id, this.getAttribute('url'), 'get', 0);" id="savephoto_466780" url="home.php?mod=spacecp&ac=album&op=saveforumphoto&aid=466780&handlekey=savephoto_466780">save to album</a>

</p>

</div>
<div class="tip_horn"></div>
</div>

</ignore_js_op>
 #### If the convolution operation is performed directly, each value of f(n) must be multiplied by each value of g(n). If the length of f(n) and g(n) is the same, N square multiplication operations are also required, which places high demands on the performance of the processor and wastes time. ``` %%%% Ordinary method for convolution a = [1 2 3 4]; % Sequence 1 b = [4 6 8 2]; % Sequence 2 c = conv(a,b); % Find the convolution sum of two sequences c c = 4 14 32 52 52 38 8 ``` #### If the discrete convolution is changed to discrete circular convolution, the previous post mentioned: [Correlation operations of signals and algorithm analysis in the application of single-chip microcomputer programs (Part 2)](https://bbs.eeworld.com.cn/forum.php?mod=viewthread&tid=1114861&fromuid=1014845 "Correlation operations of signals and algorithm analysis in the application of single-chip microcomputer programs (Part 2)") and with the help of FFT, the workload of direct convolution can be reduced. #### Approximate process: #### 1. Calculate the Fourier transform of the two sequences respectively; #### 2. Calculate the product of frequency domain multiplication; #### 3. Inverse Fourier transform; ``` %%%% FFT convolutiona = [1 2 3 4]; % Sequence 1 b = [4 6 8 2]; % Sequence 2 c = conv(a,b); % Calculate the convolution and sum of the two sequencesa1 = [1 2 3 4 0 0 0];% The expanded dimension is consistent with the dimension of the convolution resultb1 = [4 6 8 2 0 0 0];% The expanded dimension is consistent with the dimension of the convolution resulta_f = fft(a1); % Sequence Fourier transformb_f = fft(b1); % Sequence Fourier transformc_f = a_f .* b_f; % Frequency domain multiplicationC = ifft(c_f); % Inverse Fourier transform C C = 4.0000 14.0000 32.0000 52.0000 52.0000 38.0000 8.0000 ``` #### It can be found that the results of c and C obtained by the ordinary method and the FFT method are exactly the same, and the FFT operation speed is faster (this can be felt in the operation). # Discrete sequence correlation operation and fast Fourier transform#### The correlation operation of discrete sequence signals f(n), g(n) is: 
<ignore_js_op>

<div class="tip tip_4 aimg_tip" id="aimg_466814_menu" style="position: absolute; display: none" disautofocus="true">
<div class="xs0">
<p><strong>2.png</strong> <em class="xg1">(2.58 KB, downloads: 0)</em></p>
<p>
<a href="javascript:;" class="loginf" >download attach</a>

<a href="javascript:;" onclick="showWindow(this.id, this.getAttribute('url'), 'get', 0);" id="savephoto_466814" url="home.php?mod=spacecp&ac=album&op=saveforumphoto&aid=466814&handlekey=savephoto_466814">save to album</a>

</p>

</div>
<div class="tip_horn"></div>
</div>

</ignore_js_op>
 #### Compared with the convolution operation, the correlation operation lacks a time reversal. ``` %%%% Ordinary correlation operation a = [1 2 3 4]; % Sequence 1 b = [4 6 8 2]; % Sequence 2 c = xcorr(a,b); % Calculate the correlation operation of two sequences c c = 2.0000 12.0000 28.0000 48.0000 58.0000 36.0000 16.0000 ``` #### Let's analyze with the help of FFT algorithm: #### 1. Perform Fourier transform on the two sequences to obtain A(k) and B(k); #### 2. Conjugate multiply A(k) and B(k), A(k)B*(k); #### 3. Inverse Fourier transform; ``` %%%% FFT correlation operation a = [1 2 3 4]; % Sequence 1 b = [4 6 8 2]; % Sequence 2 2]; % Sequence 2 c = xcorr(a,b); % Calculate the correlation of two sequences a1 = [1 2 3 4 0 0 0]; % Expand the dimension to be consistent with the dimension of the correlation result b1 = [4 6 8 2 0 0 0]; % Expand the dimension to be consistent with the dimension of the correlation result a_f = fft(a1); % Sequence Fourier transform b_f = fft(b1); % Sequence Fourier transform b_F = conj(b_f); % Take the conjugate c_f = a_f .* b_F; % Frequency domain multiplication C = ifft(c_f); % Inverse Fourier transform C = fftshift(C); % Move the zero frequency point to the middle of the spectrum >> C C = 2.0000 12.0000 28.0000 48.0000 58.0000 36.0000 16.0000 ``` #### The results are the same after verification. # Conclusion#### Under the premise of the same operation results, the operation speed of FFT will be faster. # References [1] Fu Xiaolin. Research on Fast Fourier Simulation of Discrete Convolution and Correlation Operations [J]. Journal of Chongqing Jiaotong University, 2003(04):76-79.
</div><script>				var loginstr = '<div class="locked">To view all the contents of the essence post, please <a href="/bbs/member.php?mod=logging&action=login"   style="color:#e60000" class="loginf">log in</a> or <a href="/bbs/member.php?mod=register_eeworld.php&action=wechat" style="color:#e60000" target="_blank">register</a></div>';
				
				if(parseInt(discuz_uid)==0){
					
				}
</script><script type="text/javascript">(function(d,c){var a=d.createElement("script"),m=d.getElementsByTagName("script")[0],eewurl="//counter.eeworld.com.cn/pv/count/";a.src=eewurl+c;m.parentNode.insertBefore(a,m)})(document,523)</script>

兰博

Thank you, the host, it's very well said

Fast Fourier Transform of Convolution and Correlation of Discrete Sequences [Copy link]

Latest reply

赞赏