FFT.java

packagecom.thealgorithms.maths;

importjava.util.ArrayList;
importjava.util.Collection;
importjava.util.Collections;

/**
 * Class for calculating the Fast Fourier Transform (FFT) of a discrete signal
 * using the Cooley-Tukey algorithm.
 *
 * @author Ioannis Karavitsis
 * @version 1.0
 */
publicfinalclassFFT {
privateFFT() {
 }

/**
 * This class represents a complex number and has methods for basic
 * operations.
 *
 * <p>
 * More info:
 * https://introcs.cs.princeton.edu/java/32class/Complex.java.html
 */
staticclassComplex {

privatedoublereal;
privatedoubleimg;

/**
 * Default Constructor. Creates the complex number 0.
 */
Complex() {
real = 0;
img = 0;
 }

/**
 * Constructor. Creates a complex number.
 *
 * @param r The real part of the number.
 * @param i The imaginary part of the number.
 */
Complex(doubler, doublei) {
real = r;
img = i;
 }

/**
 * Returns the real part of the complex number.
 *
 * @return The real part of the complex number.
 */
publicdoublegetReal() {
returnreal;
 }

/**
 * Returns the imaginary part of the complex number.
 *
 * @return The imaginary part of the complex number.
 */
publicdoublegetImaginary() {
returnimg;
 }

/**
 * Adds this complex number to another.
 *
 * @param z The number to be added.
 * @return The sum.
 */
publicComplexadd(Complexz) {
Complextemp = newComplex();
temp.real = this.real + z.real;
temp.img = this.img + z.img;
returntemp;
 }

/**
 * Subtracts a number from this complex number.
 *
 * @param z The number to be subtracted.
 * @return The difference.
 */
publicComplexsubtract(Complexz) {
Complextemp = newComplex();
temp.real = this.real - z.real;
temp.img = this.img - z.img;
returntemp;
 }

/**
 * Multiplies this complex number by another.
 *
 * @param z The number to be multiplied.
 * @return The product.
 */
publicComplexmultiply(Complexz) {
Complextemp = newComplex();
temp.real = this.real * z.real - this.img * z.img;
temp.img = this.real * z.img + this.img * z.real;
returntemp;
 }

/**
 * Multiplies this complex number by a scalar.
 *
 * @param n The real number to be multiplied.
 * @return The product.
 */
publicComplexmultiply(doublen) {
Complextemp = newComplex();
temp.real = this.real * n;
temp.img = this.img * n;
returntemp;
 }

/**
 * Finds the conjugate of this complex number.
 *
 * @return The conjugate.
 */
publicComplexconjugate() {
Complextemp = newComplex();
temp.real = this.real;
temp.img = -this.img;
returntemp;
 }

/**
 * Finds the magnitude of the complex number.
 *
 * @return The magnitude.
 */
publicdoubleabs() {
returnMath.hypot(this.real, this.img);
 }

/**
 * Divides this complex number by another.
 *
 * @param z The divisor.
 * @return The quotient.
 */
publicComplexdivide(Complexz) {
Complextemp = newComplex();
doubled = z.abs() * z.abs();
d = (double) Math.round(d * 1000000000d) / 1000000000d;
temp.real = (this.real * z.real + this.img * z.img) / (d);
temp.img = (this.img * z.real - this.real * z.img) / (d);
returntemp;
 }

/**
 * Divides this complex number by a scalar.
 *
 * @param n The divisor which is a real number.
 * @return The quotient.
 */
publicComplexdivide(doublen) {
Complextemp = newComplex();
temp.real = this.real / n;
temp.img = this.img / n;
returntemp;
 }

publicdoublereal() {
returnreal;
 }

publicdoubleimaginary() {
returnimg;
 }
 }

/**
 * Iterative In-Place Radix-2 Cooley-Tukey Fast Fourier Transform Algorithm
 * with Bit-Reversal. The size of the input signal must be a power of 2. If
 * it isn't then it is padded with zeros and the output FFT will be bigger
 * than the input signal.
 *
 * <p>
 * More info:
 * https://www.algorithm-archive.org/contents/cooley_tukey/cooley_tukey.html
 * https://www.geeksforgeeks.org/iterative-fast-fourier-transformation-polynomial-multiplication/
 * https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
 * https://cp-algorithms.com/algebra/fft.html
 * @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.
 * @return
 */
publicstaticArrayList<Complex> fft(ArrayList<Complex> x, booleaninverse) {
/* Pad the signal with zeros if necessary */
paddingPowerOfTwo(x);
intn = x.size();
intlog2n = findLog2(n);
x = fftBitReversal(n, log2n, x);
intdirection = inverse ? -1 : 1;

/* Main loop of the algorithm */
for (intlen = 2; len <= n; len *= 2) {
doubleangle = -2 * Math.PI / len * direction;
Complexwlen = newComplex(Math.cos(angle), Math.sin(angle));
for (inti = 0; i < n; i += len) {
Complexw = newComplex(1, 0);
for (intj = 0; j < len / 2; j++) {
Complexu = x.get(i + j);
Complexv = w.multiply(x.get(i + j + len / 2));
x.set(i + j, u.add(v));
x.set(i + j + len / 2, u.subtract(v));
w = w.multiply(wlen);
 }
 }
 }
x = inverseFFT(n, inverse, x);
returnx;
 }

/* Find the log2(n) */
publicstaticintfindLog2(intn) {
intlog2n = 0;
while ((1 << log2n) < n) {
log2n++;
 }
returnlog2n;
 }

/* Swap the values of the signal with bit-reversal method */
publicstaticArrayList<Complex> fftBitReversal(intn, intlog2n, ArrayList<Complex> x) {
intreverse;
for (inti = 0; i < n; i++) {
reverse = reverseBits(i, log2n);
if (i < reverse) {
Collections.swap(x, i, reverse);
 }
 }
returnx;
 }

/* Divide by n if we want the inverse FFT */
publicstaticArrayList<Complex> inverseFFT(intn, booleaninverse, ArrayList<Complex> x) {
if (inverse) {
for (inti = 0; i < x.size(); i++) {
Complexz = x.get(i);
x.set(i, z.divide(n));
 }
 }
returnx;
 }

/**
 * This function reverses the bits of a number. It is used in Cooley-Tukey
 * FFT algorithm.
 *
 * <p>
 * E.g. num = 13 = 00001101 in binary log2n = 8 Then reversed = 176 =
 * 10110000 in binary
 *
 * <p>
 * More info: https://cp-algorithms.com/algebra/fft.html
 * https://www.geeksforgeeks.org/write-an-efficient-c-program-to-reverse-bits-of-a-number/
 *
 * @param num The integer you want to reverse its bits.
 * @param log2n The number of bits you want to reverse.
 * @return The reversed number
 */
privatestaticintreverseBits(intnum, intlog2n) {
intreversed = 0;
for (inti = 0; i < log2n; i++) {
if ((num & (1 << i)) != 0) {
reversed |= 1 << (log2n - 1 - i);
 }
 }
returnreversed;
 }

/**
 * This method pads an ArrayList with zeros in order to have a size equal to
 * the next power of two of the previous size.
 *
 * @param x The ArrayList to be padded.
 */
privatestaticvoidpaddingPowerOfTwo(Collection<Complex> x) {
intn = 1;
intoldSize = x.size();
while (n < oldSize) {
n *= 2;
 }
for (inti = 0; i < n - oldSize; i++) {
x.add(newComplex());
 }
 }
}