primary-code-test
diff --git a/‎Maths/CircularConvolutionFFT.java‎
Lines changed: 58 additions & 0 deletions b/‎Maths/CircularConvolutionFFT.java‎
Lines changed: 58 additions & 0 deletions
diff --git a/‎Maths/Convolution.java‎
Lines changed: 47 additions & 0 deletions b/‎Maths/Convolution.java‎
Lines changed: 47 additions & 0 deletions
diff --git a/‎Maths/ConvolutionFFT.java‎
Lines changed: 61 additions & 0 deletions b/‎Maths/ConvolutionFFT.java‎
Lines changed: 61 additions & 0 deletions
@@ -0,0 +1,58 @@
+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.
+     *
+     * 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;
+    }
+}
@@ -0,0 +1,47 @@
+package com.maths;
+
+/**
+ * Class for linear convolution of two discrete signals
+ *
+ * @author Ioannis Karavitsis
+ * @version 1.0
+ * */
+public class Convolution
+{
+    /**
+     * Discrete linear convolution function. Both input signals and the output signal must start from 0.
+     * If you have a signal that has values before 0 then shift it to start from 0.
+     *
+     * @param A The first discrete signal
+     * @param B The second discrete signal
+     * @return The convolved signal
+     * */
+    public static double[] convolution(double[] A, double[] B)
+    {
+        double[] convolved = new double[A.length + B.length - 1];
+
+        /*
+        The discrete convolution of two signals A and B is defined as:
+
+              A.length
+        C[i] = Σ (A[k]*B[i-k])
+              k=0
+
+        It's obvious that:  0 <= k <= A.length , 0 <= i <= A.length + B.length - 2  and  0 <= i-k <= B.length - 1
+        From the last inequality we get that:  i - B.length + 1 <= k <= i and thus we get the conditions below.
+        */
+        for(int i = 0; i < convolved.length; i++)
+        {
+            convolved[i] = 0;
+            int k = Math.max(i - B.length + 1, 0);
+
+            while(k < i + 1 && k < A.length)
+            {
+                convolved[i] += A[k] * B[i - k];
+                k++;
+            }
+        }
+
+        return convolved;
+    }
+}
@@ -0,0 +1,61 @@
+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.
+     *
+     * 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;
+    }
+}