Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit6e63a05

Browse files
committed
Add Inverse Discrete Fourier Transform.
1 parent351a745 commit6e63a05

File tree

5 files changed

+112
-22
lines changed

5 files changed

+112
-22
lines changed

‎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
importComplexNumberfrom'../../complex-number/ComplexNumber';
22

3-
exportconstfourierDirectTestCases=[
3+
exportconstfourierTestCases=[
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
statictestDirectFourierTransform(fourierTransform){
243-
fourierDirectTestCases.forEach((testCase)=>{
243+
fourierTestCases.forEach((testCase)=>{
244244
const{ input,output:expectedOutput}=testCase;
245245

246-
// Convert input into complex numbers.
247-
constcomplexInput=input.map(sample=>newComplexNumber({re:sample.amplitude}));
248-
249246
// Try to split input signal into sequence of pure sinusoids.
250-
constcurrentOutput=fourierTransform(complexInput);
247+
constformattedInput=input.map(sample=>sample.amplitude);
248+
constcurrentOutput=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+
statictestInverseFourierTransform(inverseFourierTransform){
273+
fourierTestCases.forEach((testCase)=>{
274+
const{input:expectedOutput,output:inputFrequencies}=testCase;
275+
276+
// Try to join frequencies into time signal.
277+
constformattedInput=inputFrequencies.map((frequency)=>{
278+
returnnewComplexNumber({re:frequency.re,im:frequency.im});
279+
});
280+
constcurrentOutput=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+
constcurrentAmplitude=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
}
Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
importinverseDiscreteFourierTransformfrom'../inverseDiscreteFourierTransform';
2+
importFourierTesterfrom'./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
constCLOSE_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-
exportdefaultfunctiondft(complexInputAmplitudes){
21-
// Convert complex amplitudes into real ones.
22-
constinputAmplitudes=complexInputAmplitudes.map(complexAmplitude=>complexAmplitude.re);
23-
22+
exportdefaultfunctiondft(inputAmplitudes,zeroThreshold=CLOSE_TO_ZERO_THRESHOLD){
2423
constN=inputAmplitudes.length;
2524
constsignals=[];
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

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
importComplexNumberfrom'../complex-number/ComplexNumber';
2+
3+
constCLOSE_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+
exportdefaultfunctioninverseDiscreteFourierTransform(
17+
frequencies,
18+
zeroThreshold=CLOSE_TO_ZERO_THRESHOLD,
19+
){
20+
constN=frequencies.length;
21+
constamplitudes=[];
22+
23+
// Go through every discrete point of time.
24+
for(lettimer=0;timer<N;timer+=1){
25+
// Compound amplitude at current time.
26+
letamplitude=newComplexNumber();
27+
28+
// Go through all discrete frequencies.
29+
for(letfrequency=0;frequency<N;frequency+=1){
30+
constcurrentFrequency=frequencies[frequency];
31+
32+
// Calculate rotation angle.
33+
constrotationAngle=(2*Math.PI)*frequency*(timer/N);
34+
35+
// Remember that e^ix = cos(x) + i * sin(x);
36+
constfrequencyContribution=newComplexNumber({
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+
returnamplitudes;
58+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp