# 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:
#### 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://en.eeworld.com/bbs/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:
#### 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.