Skip to content

Commit 6e63a05

Browse files
trekhlebtrekhleb
committed
Add Inverse Discrete Fourier Transform.
1 parent 351a745 commit 6e63a05

5 files changed

Lines changed: 112 additions & 22 deletions

File tree

‎README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -73,7 +73,7 @@ a set of rules that precisely define a sequence of operations.
7373
* `B` [Radian & Degree](src/algorithms/math/radian) - radians to degree and backwards conversion
7474
* `A` [Integer Partition](src/algorithms/math/integer-partition)
7575
* `A` [Liu Hui π Algorithm](src/algorithms/math/liu-hui) - approximate π calculations based on N-gons
76-
* `A` [Fourier Transform (DFT, FFT)](src/algorithms/math/fourier-transform) - decompose a function of time (a signal) into the frequencies that make it up
76+
* `A` [Fourier Transform (DFT, IDFT, FFT)](src/algorithms/math/fourier-transform) - decompose a function of time (a signal) into the frequencies that make it up
7777
* **Sets**
7878
* `B` [Cartesian Product](src/algorithms/sets/cartesian-product) - product of multiple sets
7979
* `B` [Fisher–Yates Shuffle](src/algorithms/sets/fisher-yates) - random permutation of a finite sequence

‎src/algorithms/math/fourier-transform/__test__/FourierTester.js‎

Lines changed: 38 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
import ComplexNumber from '../../complex-number/ComplexNumber';
22

3-
export const fourierDirectTestCases = [
3+
export const fourierTestCases = [
44
{
55
input: [
66
{ amplitude: 1 },
@@ -47,13 +47,13 @@ export const fourierDirectTestCases = [
4747
],
4848
output: [
4949
{
50-
frequency: 0, amplitude: 0.3333, phase: 0, re: 0.3333, im: 0,
50+
frequency: 0, amplitude: 0.33333, phase: 0, re: 0.33333, im: 0,
5151
},
5252
{
53-
frequency: 1, amplitude: 0.3333, phase: 0, re: 0.3333, im: 0,
53+
frequency: 1, amplitude: 0.33333, phase: 0, re: 0.33333, im: 0,
5454
},
5555
{
56-
frequency: 2, amplitude: 0.3333, phase: 0, re: 0.3333, im: 0,
56+
frequency: 2, amplitude: 0.33333, phase: 0, re: 0.33333, im: 0,
5757
},
5858
],
5959
},
@@ -179,13 +179,13 @@ export const fourierDirectTestCases = [
179179
frequency: 0, amplitude: 1.75, phase: 0, re: 1.75, im: 0,
180180
},
181181
{
182-
frequency: 1, amplitude: 1.03077, phase: 14.0362, re: 0.99999, im: 0.25,
182+
frequency: 1, amplitude: 1.03077, phase: 14.03624, re: 0.99999, im: 0.25,
183183
},
184184
{
185185
frequency: 2, amplitude: 0.25, phase: 0, re: 0.25, im: 0,
186186
},
187187
{
188-
frequency: 3, amplitude: 1.03077, phase: -14.0362, re: 1, im: -0.25,
188+
frequency: 3, amplitude: 1.03077, phase: -14.03624, re: 1, im: -0.25,
189189
},
190190
],
191191
},
@@ -201,7 +201,7 @@ export const fourierDirectTestCases = [
201201
frequency: 0, amplitude: 1, phase: 0, re: 1, im: 0,
202202
},
203203
{
204-
frequency: 1, amplitude: 1.76776, phase: 8.1301, re: 1.75, im: 0.25,
204+
frequency: 1, amplitude: 1.76776, phase: 8.13010, re: 1.75, im: 0.25,
205205
},
206206
{
207207
frequency: 2, amplitude: 0.5, phase: 180, re: -0.5, im: 0,
@@ -240,17 +240,15 @@ export default class FourierTester {
240240
* @param {function} fourierTransform
241241
*/
242242
static testDirectFourierTransform(fourierTransform) {
243-
fourierDirectTestCases.forEach((testCase) => {
243+
fourierTestCases.forEach((testCase) => {
244244
const { input, output: expectedOutput } = testCase;
245245

246-
// Convert input into complex numbers.
247-
const complexInput = input.map(sample => new ComplexNumber({ re: sample.amplitude }));
248-
249246
// Try to split input signal into sequence of pure sinusoids.
250-
const currentOutput = fourierTransform(complexInput);
247+
const formattedInput = input.map(sample => sample.amplitude);
248+
const currentOutput = fourierTransform(formattedInput);
251249

252250
// Check the signal has been split into proper amount of sub-signals.
253-
expect(currentOutput.length).toBeGreaterThanOrEqual(complexInput.length);
251+
expect(currentOutput.length).toBeGreaterThanOrEqual(formattedInput.length);
254252

255253
// Now go through all the signals and check their frequency, amplitude and phase.
256254
expectedOutput.forEach((expectedSignal, frequency) => {
@@ -267,4 +265,31 @@ export default class FourierTester {
267265
});
268266
});
269267
}
268+
269+
/**
270+
* @param {function} inverseFourierTransform
271+
*/
272+
static testInverseFourierTransform(inverseFourierTransform) {
273+
fourierTestCases.forEach((testCase) => {
274+
const { input: expectedOutput, output: inputFrequencies } = testCase;
275+
276+
// Try to join frequencies into time signal.
277+
const formattedInput = inputFrequencies.map((frequency) => {
278+
return new ComplexNumber({ re: frequency.re, im: frequency.im });
279+
});
280+
const currentOutput = inverseFourierTransform(formattedInput);
281+
282+
// Check the signal has been combined of proper amount of time samples.
283+
expect(currentOutput.length).toBeLessThanOrEqual(formattedInput.length);
284+
285+
// Now go through all the amplitudes and check their values.
286+
expectedOutput.forEach((expectedAmplitudes, timer) => {
287+
// Get template data we want to test against.
288+
const currentAmplitude = currentOutput[timer];
289+
290+
// Check if current amplitude is close enough to the calculated one.
291+
expect(currentAmplitude).toBeCloseTo(expectedAmplitudes.amplitude, 4);
292+
});
293+
});
294+
}
270295
}

‎src/algorithms/math/fourier-transform/__test__/inverseDiscreteFourierTransform.test.js‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
import inverseDiscreteFourierTransform from '../inverseDiscreteFourierTransform';
2+
import FourierTester from './FourierTester';
3+
4+
describe('inverseDiscreteFourierTransform', () => {
5+
it('should calculate output signal out of input frequencies', () => {
6+
FourierTester.testInverseFourierTransform(inverseDiscreteFourierTransform);
7+
});
8+
});

‎src/algorithms/math/fourier-transform/discreteFourierTransform.js‎

Lines changed: 7 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -3,12 +3,14 @@ import ComplexNumber from '../complex-number/ComplexNumber';
33
const CLOSE_TO_ZERO_THRESHOLD = 1e-10;
44

55
/**
6-
* Discrete Fourier Transform.
6+
* Discrete Fourier Transform (DFT): time to frequencies.
77
*
88
* Time complexity: O(N^2)
99
*
10-
* @param {ComplexNumber[]} complexInputAmplitudes - Input signal amplitudes over time (complex
10+
* @param {number[]} inputAmplitudes - Input signal amplitudes over time (complex
1111
* numbers with real parts only).
12+
* @param {number} zeroThreshold - Threshold that is used to convert real and imaginary numbers
13+
* to zero in case if they are smaller then this.
1214
*
1315
* @return {ComplexNumber[]} - Array of complex number. Each of the number represents the frequency
1416
* or signal. All signals together will form input signal over discrete time periods. Each signal's
@@ -17,10 +19,7 @@ const CLOSE_TO_ZERO_THRESHOLD = 1e-10;
1719
* @see https://gist.github.com/anonymous/129d477ddb1c8025c9ac
1820
* @see https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/
1921
*/
20-
export default function dft(complexInputAmplitudes) {
21-
// Convert complex amplitudes into real ones.
22-
const inputAmplitudes = complexInputAmplitudes.map(complexAmplitude => complexAmplitude.re);
23-
22+
export default function dft(inputAmplitudes, zeroThreshold = CLOSE_TO_ZERO_THRESHOLD) {
2423
const N = inputAmplitudes.length;
2524
const signals = [];
2625

@@ -48,11 +47,11 @@ export default function dft(complexInputAmplitudes) {
4847
}
4948

5049
// Close to zero? You're zero.
51-
if (Math.abs(frequencySignal.re) < CLOSE_TO_ZERO_THRESHOLD) {
50+
if (Math.abs(frequencySignal.re) < zeroThreshold) {
5251
frequencySignal.re = 0;
5352
}
5453

55-
if (Math.abs(frequencySignal.im) < CLOSE_TO_ZERO_THRESHOLD) {
54+
if (Math.abs(frequencySignal.im) < zeroThreshold) {
5655
frequencySignal.im = 0;
5756
}
5857

‎src/algorithms/math/fourier-transform/inverseDiscreteFourierTransform.js‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
import ComplexNumber from '../complex-number/ComplexNumber';
2+
3+
const CLOSE_TO_ZERO_THRESHOLD = 1e-10;
4+
5+
/**
6+
* Inverse Discrete Fourier Transform (IDFT): frequencies to time.
7+
*
8+
* Time complexity: O(N^2)
9+
*
10+
* @param {ComplexNumber[]} frequencies - Frequencies summands of the final signal.
11+
* @param {number} zeroThreshold - Threshold that is used to convert real and imaginary numbers
12+
* to zero in case if they are smaller then this.
13+
*
14+
* @return {number[]} - Discrete amplitudes distributed in time.
15+
*/
16+
export default function inverseDiscreteFourierTransform(
17+
frequencies,
18+
zeroThreshold = CLOSE_TO_ZERO_THRESHOLD,
19+
) {
20+
const N = frequencies.length;
21+
const amplitudes = [];
22+
23+
// Go through every discrete point of time.
24+
for (let timer = 0; timer < N; timer += 1) {
25+
// Compound amplitude at current time.
26+
let amplitude = new ComplexNumber();
27+
28+
// Go through all discrete frequencies.
29+
for (let frequency = 0; frequency < N; frequency += 1) {
30+
const currentFrequency = frequencies[frequency];
31+
32+
// Calculate rotation angle.
33+
const rotationAngle = (2 * Math.PI) * frequency * (timer / N);
34+
35+
// Remember that e^ix = cos(x) + i * sin(x);
36+
const frequencyContribution = new ComplexNumber({
37+
re: Math.cos(rotationAngle),
38+
im: Math.sin(rotationAngle),
39+
}).multiply(currentFrequency);
40+
41+
amplitude = amplitude.add(frequencyContribution);
42+
}
43+
44+
// Close to zero? You're zero.
45+
if (Math.abs(amplitude.re) < zeroThreshold) {
46+
amplitude.re = 0;
47+
}
48+
49+
if (Math.abs(amplitude.im) < zeroThreshold) {
50+
amplitude.im = 0;
51+
}
52+
53+
// Add current frequency signal to the list of compound signals.
54+
amplitudes[timer] = amplitude.re;
55+
}
56+
57+
return amplitudes;
58+
}

0 commit comments

Comments
 (0)