Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Expand file tree

/

ConvolutionFFT.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
60 lines (53 loc) · 2.22 KB
/

ConvolutionFFT.java

Copy path

File metadata and controls

60 lines (53 loc) · 2.22 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package com.maths;
import java.util.ArrayList;
/**
* Class for linear convolution of two discrete signals using the convolution theorem.
*
* @author Ioannis Karavitsis
* @version 1.0
*/
public class ConvolutionFFT {
/**
* This method pads the signal with zeros until it reaches the new size.
*
* @param x The signal to be padded.
* @param newSize The new size of the signal.
*/
private static void padding(ArrayList<FFT.Complex> x, int newSize) {
if (x.size() < newSize) {
int diff = newSize - x.size();
for (int i = 0; i < diff; i++) x.add(new FFT.Complex());
}
}
/**
* Discrete linear convolution function. It uses the convolution theorem for discrete signals
* convolved: = IDFT(DFT(a)*DFT(b)). This is true for circular convolution. In order to get the
* linear convolution of the two signals we first pad the two signals to have the same size equal
* to the convolved signal (a.size() + b.size() - 1). Then we use the FFT algorithm for faster
* calculations of the two DFTs and the final IDFT.
*
* <p>More info: https://en.wikipedia.org/wiki/Convolution_theorem
* https://ccrma.stanford.edu/~jos/ReviewFourier/FFT_Convolution.html
*
* @param a The first signal.
* @param b The other signal.
* @return The convolved signal.
*/
public static ArrayList<FFT.Complex> convolutionFFT(
ArrayList<FFT.Complex> a, ArrayList<FFT.Complex> b) {
int convolvedSize = a.size() + b.size() - 1; // The size of the convolved signal
padding(a, convolvedSize); // Zero padding both signals
padding(b, convolvedSize);
/* Find the FFTs of both signals (Note that the size of the FFTs will be bigger than the convolvedSize because of the extra zero padding in FFT algorithm) */
FFT.fft(a, false);
FFT.fft(b, false);
ArrayList<FFT.Complex> convolved = new ArrayList<>();
for (int i = 0; i < a.size(); i++) convolved.add(a.get(i).multiply(b.get(i))); // FFT(a)*FFT(b)
FFT.fft(convolved, true); // IFFT
convolved
.subList(convolvedSize, convolved.size())
.clear(); // Remove the remaining zeros after the convolvedSize. These extra zeros came from
// paddingPowerOfTwo() method inside the fft() method.
return convolved;
}
}
Morty Proxy This is a proxified and sanitized view of the page, visit original site.