FFTBluestein.java

packagecom.thealgorithms.maths;

importjava.util.ArrayList;
importjava.util.List;

/**
 * Class for calculating the Fast Fourier Transform (FFT) of a discrete signal
 * using the Bluestein's algorithm.
 *
 * @author Ioannis Karavitsis
 * @version 1.0
 */
publicfinalclassFFTBluestein {
privateFFTBluestein() {
 }

/**
 * Bluestein's FFT Algorithm.
 *
 * <p>
 * More info:
 * https://en.wikipedia.org/wiki/Chirp_Z-transform#Bluestein.27s_algorithm
 * http://tka4.org/materials/lib/Articles-Books/Numerical%20Algorithms/Hartley_Trasform/Bluestein%27s%20FFT%20algorithm%20-%20Wikipedia,%20the%20free%20encyclopedia.htm
 *
 * @param x The discrete signal which is then converted to the FFT or the
 * IFFT of signal x.
 * @param inverse True if you want to find the inverse FFT.
 */
publicstaticvoidfftBluestein(List<FFT.Complex> x, booleaninverse) {
intn = x.size();
intbnSize = 2 * n - 1;
intdirection = inverse ? -1 : 1;
ArrayList<FFT.Complex> an = newArrayList<>();
ArrayList<FFT.Complex> bn = newArrayList<>();

/* Initialization of the b(n) sequence (see Wikipedia's article above for the symbols
 * used)*/
for (inti = 0; i < bnSize; i++) {
bn.add(newFFT.Complex());
 }

for (inti = 0; i < n; i++) {
doubleangle = (i - n + 1) * (i - n + 1) * Math.PI / n * direction;
bn.set(i, newFFT.Complex(Math.cos(angle), Math.sin(angle)));
bn.set(bnSize - i - 1, newFFT.Complex(Math.cos(angle), Math.sin(angle)));
 }

/* Initialization of the a(n) sequence */
for (inti = 0; i < n; i++) {
doubleangle = -i * i * Math.PI / n * direction;
an.add(x.get(i).multiply(newFFT.Complex(Math.cos(angle), Math.sin(angle))));
 }

ArrayList<FFT.Complex> convolution = ConvolutionFFT.convolutionFFT(an, bn);

/* The final multiplication of the convolution with the b*(k) factor */
for (inti = 0; i < n; i++) {
doubleangle = -1 * i * i * Math.PI / n * direction;
FFT.Complexbk = newFFT.Complex(Math.cos(angle), Math.sin(angle));
x.set(i, bk.multiply(convolution.get(i + n - 1)));
 }

/* Divide by n if we want the inverse FFT */
if (inverse) {
for (inti = 0; i < n; i++) {
FFT.Complexz = x.get(i);
x.set(i, z.divide(n));
 }
 }
 }
}