Anonymous user
Fast Fourier transform: Difference between revisions
Adding PHP FFT & iFFT example
(Adding PHP FFT & iFFT example) |
|||
Line 2,369:
{ 0.000000, 0.000000},
{ 0.000000, 0.000000}}
</pre>
=={{header|PHP}}==
Complex Fourier transform the inverse reimplemented from the C++, Python & JavaScript variants on this page.
Complex Class File:
<lang PHP>
<?php
class Complex
{
public $real;
public $imaginary;
function __construct($real, $imaginary){
$this->real = $real;
$this->imaginary = $imaginary;
}
function Add($other, $dst){
$dst->real = $this->real + $other->real;
$dst->imaginary = $this->imaginary + $other->imaginary;
return $dst;
}
function Subtract($other, $dst){
$dst->real = $this->real - $other->real;
$dst->imaginary = $this->imaginary - $other->imaginary;
return $dst;
}
function Multiply($other, $dst){
//cache real in case dst === this
$r = $this->real * $other->real - $this->imaginary * $other->imaginary;
$dst->imaginary = $this->real * $other->imaginary + $this->imaginary * $other->real;
$dst->real = $r;
return $dst;
}
function ComplexExponential($dst){
$er = exp($this->real);
$dst->real = $er * cos($this->imaginary);
$dst->imaginary = $er * sin($this->imaginary);
return $dst;
}
}
</lang>
Example:
<lang PHP>
<?php
include 'complex.class.php';
function IFFT($amplitudes)
{
$N = count($amplitudes);
$iN = 1 / $N;
// Conjugate if imaginary part is not 0
for($i = 0; $i < $N; ++$i){
if($amplitudes[$i] instanceof Complex){
$amplitudes[$i]->imaginary = -$amplitudes[$i]->imaginary;
}
}
// Apply Fourier Transform
$amplitudes = FFT($amplitudes);
for($i = 0; $i < $N; ++$i){
//Conjugate again
$amplitudes[$i]->imaginary = -$amplitudes[$i]->imaginary;
// Scale
$amplitudes[$i]->real *= $iN;
$amplitudes[$i]->imaginary *= $iN;
}
return $amplitudes;
}
function FFT($amplitudes)
{
$N = count($amplitudes);
if($N <= 1){
return $amplitudes;
}
$hN = $N / 2;
$even = array_pad(array() , $hN, 0);
$odd = array_pad(array() , $hN, 0);
for($i = 0; $i < $hN; ++$i){
$even[$i] = $amplitudes[$i*2];
$odd[$i] = $amplitudes[$i*2+1];
}
$even = FFT($even);
$odd = FFT($odd);
$a = -2*PI();
for($k = 0; $k < $hN; ++$k){
if(!($even[$k] instanceof Complex)){
$even[$k] = new Complex($even[$k], 0);
}
if(!($odd[$k] instanceof Complex)){
$odd[$k] = new Complex($odd[$k], 0);
}
$p = $k/$N;
$t = new Complex(0, $a * $p);
$t->ComplexExponential($t);
$t->Multiply($odd[$k], $t);
$amplitudes[$k] = $even[$k]->Add($t, $odd[$k]);
$amplitudes[$k + $hN] = $even[$k]->Subtract($t, $even[$k]);
}
return $amplitudes;
}
function EchoSamples(&$samples){
echo "Index\tReal\t\t\t\tImaginary" . PHP_EOL;
foreach($samples as $key=>&$sample){
echo "$key\t" . number_format($sample->real, 13) . "\t\t\t\t" . number_format($sample->imaginary, 13) . PHP_EOL;
}
}
// Input Amplitudes
$time_amplitude_samples = array(1,1,1,1,0,0,0,0);
// echo input for reference
echo 'Input '. PHP_EOL;
echo "Index\tReal" . PHP_EOL;
foreach($time_amplitude_samples as $key=>&$sample){
echo "$key\t" . number_format($sample, 13) . PHP_EOL;
}
echo PHP_EOL;
// Do FFT and echo results
echo 'FFT '. PHP_EOL;
$frequency_amplitude_samples = FFT($time_amplitude_samples);
EchoSamples($frequency_amplitude_samples);
echo PHP_EOL;
// Do inverse FFT and echo results
echo 'Inverse FFT '. PHP_EOL;
$frequency_back_to_time_amplitude_samples = IFFT($frequency_amplitude_samples);
EchoSamples($frequency_back_to_time_amplitude_samples);
echo PHP_EOL;
</lang>
{{out}}
<pre>
Input
Index Real
0 1.0000000000000
1 1.0000000000000
2 1.0000000000000
3 1.0000000000000
4 0.0000000000000
5 0.0000000000000
6 0.0000000000000
7 0.0000000000000
FFT
Index Real Imaginary
0 4.0000000000000 0.0000000000000
1 1.0000000000000 -2.4142135623731
2 0.0000000000000 0.0000000000000
3 1.0000000000000 -0.4142135623731
4 0.0000000000000 0.0000000000000
5 1.0000000000000 0.4142135623731
6 0.0000000000000 0.0000000000000
7 1.0000000000000 2.4142135623731
Inverse FFT
Index Real Imaginary
0 1.0000000000000 0.0000000000000
1 1.0000000000000 0.0000000000000
2 1.0000000000000 0.0000000000000
3 1.0000000000000 0.0000000000000
4 0.0000000000000 0.0000000000000
5 0.0000000000000 0.0000000000000
6 0.0000000000000 0.0000000000000
7 0.0000000000000 0.0000000000000
</pre>
| |||