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

/

CircularConvolutionFFT.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
55 lines (48 loc) · 1.85 KB
/

CircularConvolutionFFT.java

Copy path

File metadata and controls

55 lines (48 loc) · 1.85 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
package com.maths;
import java.util.ArrayList;
/**
* Class for circular convolution of two discrete signals using the convolution theorem.
*
* @author Ioannis Karavitsis
* @version 1.0
*/
public class CircularConvolutionFFT {
/**
* 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 circular convolution function. It uses the convolution theorem for discrete signals:
* convolved = IDFT(DFT(a)*DFT(b)). 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
*
* @param a The first signal.
* @param b The other signal.
* @return The convolved signal.
*/
public static ArrayList<FFT.Complex> fftCircularConvolution(
ArrayList<FFT.Complex> a, ArrayList<FFT.Complex> b) {
int convolvedSize =
Math.max(
a.size(), b.size()); // The two signals must have the same size equal to the bigger one
padding(a, convolvedSize); // Zero padding the smaller signal
padding(b, convolvedSize);
/* Find the FFTs of both signal. Here we use the Bluestein algorithm because we want the FFT to have the same length with the signal and not bigger */
FFTBluestein.fftBluestein(a, false);
FFTBluestein.fftBluestein(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)
FFTBluestein.fftBluestein(convolved, true); // IFFT
return convolved;
}
}
Morty Proxy This is a proxified and sanitized view of the page, visit original site.