Skip to content

Commit b9dcb85

Browse files
author
JohnKara
committed
convolution, FFT, Bluestein's FFT, circular convolution and linear convolution using FFT
1 parent 452fa56 commit b9dcb85

10 files changed

+867
-0
lines changed

‎src/main/java/com/maths/CircularConvolutionFFT.java

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package com.maths;
2+
3+
import java.util.ArrayList;
4+
5+
/**
6+
* Class for circular convolution of two discrete signals using the convolution theorem.
7+
*
8+
* @author Ioannis Karavitsis
9+
* @version 1.0
10+
* */
11+
public class CircularConvolutionFFT
12+
{
13+
/**
14+
* This method pads the signal with zeros until it reaches the new size.
15+
*
16+
* @param x The signal to be padded.
17+
* @param newSize The new size of the signal.
18+
* */
19+
private static void padding(ArrayList<FFT.Complex> x, int newSize)
20+
{
21+
if(x.size() < newSize)
22+
{
23+
int diff = newSize - x.size();
24+
for(int i = 0; i < diff; i++)
25+
x.add(new FFT.Complex());
26+
}
27+
}
28+
29+
/**
30+
* Discrete circular convolution function. It uses the convolution theorem for discrete signals: convolved = IDFT(DFT(a)*DFT(b)).
31+
* Then we use the FFT algorithm for faster calculations of the two DFTs and the final IDFT.
32+
*
33+
* More info:
34+
* https://en.wikipedia.org/wiki/Convolution_theorem
35+
*
36+
* @param a The first signal.
37+
* @param b The other signal.
38+
* @return The convolved signal.
39+
* */
40+
public static ArrayList<FFT.Complex> fftCircularConvolution(ArrayList<FFT.Complex> a, ArrayList<FFT.Complex> b)
41+
{
42+
int convolvedSize = Math.max(a.size(), b.size()); //The two signals must have the same size equal to the bigger one
43+
padding(a, convolvedSize); //Zero padding the smaller signal
44+
padding(b, convolvedSize);
45+
46+
/* 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 */
47+
FFTBluestein.fftBluestein(a, false);
48+
FFTBluestein.fftBluestein(b, false);
49+
ArrayList<FFT.Complex> convolved = new ArrayList<>();
50+
51+
for(int i = 0; i < a.size(); i++)
52+
convolved.add(a.get(i).multiply(b.get(i))); //FFT(a)*FFT(b)
53+
54+
FFTBluestein.fftBluestein(convolved, true); //IFFT
55+
56+
return convolved;
57+
}
58+
}

‎src/main/java/com/maths/Convolution.java

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package com.maths;
2+
3+
/**
4+
* Class for linear convolution of two discrete signals
5+
*
6+
* @author Ioannis Karavitsis
7+
* @version 1.0
8+
* */
9+
public class Convolution
10+
{
11+
/**
12+
* Discrete linear convolution function. Both input signals and the output signal must start from 0.
13+
* If you have a signal that has values before 0 then shift it to start from 0.
14+
*
15+
* @param A The first discrete signal
16+
* @param B The second discrete signal
17+
* @return The convolved signal
18+
* */
19+
public static double[] convolution(double[] A, double[] B)
20+
{
21+
double[] convolved = new double[A.length + B.length - 1];
22+
23+
/*
24+
The discrete convolution of two signals A and B is defined as:
25+
26+
A.length
27+
C[i] = Σ (A[k]*B[i-k])
28+
k=0
29+
30+
It's obvious that: 0 <= k <= A.length , 0 <= i <= A.length + B.length - 2 and 0 <= i-k <= B.length - 1
31+
From the last inequality we get that: i - B.length + 1 <= k <= i and thus we get the conditions below.
32+
*/
33+
for(int i = 0; i < convolved.length; i++)
34+
{
35+
convolved[i] = 0;
36+
int k = Math.max(i - B.length + 1, 0);
37+
38+
while(k < i + 1 && k < A.length)
39+
{
40+
convolved[i] += A[k] * B[i - k];
41+
k++;
42+
}
43+
}
44+
45+
return convolved;
46+
}
47+
}

‎src/main/java/com/maths/ConvolutionFFT.java

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package com.maths;
2+
3+
import java.util.ArrayList;
4+
5+
/**
6+
* Class for linear convolution of two discrete signals using the convolution theorem.
7+
*
8+
* @author Ioannis Karavitsis
9+
* @version 1.0
10+
* */
11+
public class ConvolutionFFT
12+
{
13+
/**
14+
* This method pads the signal with zeros until it reaches the new size.
15+
*
16+
* @param x The signal to be padded.
17+
* @param newSize The new size of the signal.
18+
* */
19+
private static void padding(ArrayList<FFT.Complex> x, int newSize)
20+
{
21+
if(x.size() < newSize)
22+
{
23+
int diff = newSize - x.size();
24+
for(int i = 0; i < diff; i++)
25+
x.add(new FFT.Complex());
26+
}
27+
}
28+
29+
/**
30+
* Discrete linear convolution function. It uses the convolution theorem for discrete signals convolved: = IDFT(DFT(a)*DFT(b)).
31+
* 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).
32+
* Then we use the FFT algorithm for faster calculations of the two DFTs and the final IDFT.
33+
*
34+
* More info:
35+
* https://en.wikipedia.org/wiki/Convolution_theorem
36+
* https://ccrma.stanford.edu/~jos/ReviewFourier/FFT_Convolution.html
37+
*
38+
* @param a The first signal.
39+
* @param b The other signal.
40+
* @return The convolved signal.
41+
* */
42+
public static ArrayList<FFT.Complex> convolutionFFT(ArrayList<FFT.Complex> a, ArrayList<FFT.Complex> b)
43+
{
44+
int convolvedSize = a.size() + b.size() - 1; //The size of the convolved signal
45+
padding(a, convolvedSize); //Zero padding both signals
46+
padding(b, convolvedSize);
47+
48+
/* 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) */
49+
FFT.fft(a, false);
50+
FFT.fft(b, false);
51+
ArrayList<FFT.Complex> convolved = new ArrayList<>();
52+
53+
for(int i = 0; i < a.size(); i++)
54+
convolved.add(a.get(i).multiply(b.get(i))); //FFT(a)*FFT(b)
55+
56+
FFT.fft(convolved, true); //IFFT
57+
convolved.subList(convolvedSize, convolved.size()).clear(); //Remove the remaining zeros after the convolvedSize. These extra zeros came from paddingPowerOfTwo() method inside the fft() method.
58+
59+
return convolved;
60+
}
61+
}

0 commit comments

Comments
 (0)