unit DSXFastFourier;
interface
uses
Windows, Messages, SysUtils, Classes,math;
procedure Register;
type
TComplex = Record
Real :do
uble;
imag :do
uble;
end;
TOnGetDataEvent = procedure(index : integer;
var Value : TComplex) of Object;
TComplexArray = array [0..0] of TComplex;
PComplexArray = ^TComplexArray;
EFastFourierError = class(Exception);
TDSXFastFourier = Class(TComponent)
private
FNumSamples : integer;
FInBuffer : PComplexArray;
FOutBuffer : PComplexArray;
FOnGetData : TOnGetDataEvent;
function IsPowerOfTwo ( x: word ): boolean;
function NumberOfBitsNeeded ( PowerOfTwo: word ): word;
function ReverseBits ( index, NumBits: word ): word;
procedure FourierTransform ( AngleNumerator: do
uble );
procedure SetNumSamples(value : integer);
function GetTransformedData(idx : integer) : TComplex;
constructor
create(AOwner : TComponent);
destructor
destroy;
public
procedure fft;
procedure ifft;
procedure CalcFrequency (FrequencyIndex: word);
published
property OnGetData : TOnGetDataEvent read FOnGetData write FOnGetData;
property NumSamples : integer read FNumSamples write SetNumSamples;
property SampleCount : Integer read FNumSamples;
property TransformedData[idx : integer] : TComplex read GetTransformedData;
end;
implementation
constructor TDSXFastFourier.Create(AOwner : TComponent);
begin
inherited create(AOwner);
end;
destructor TDSXFastFourier.Destroy;
begin
if Assigned(FInBuffer) then
FreeMem(FinBuffer);
if Assigned(FOutBuffer) then
FreeMem(FOutBuffer);
end;
procedure TDSXFastFourier.SetNumSamples(value : integer);
begin
FNumSamples := value;
if Assigned(FInBuffer) then
FreeMem(FinBuffer);
if Assigned(FOutBuffer) then
FreeMem(FOutBuffer);
try
getMem(FInBuffer, sizeof(TComplex)*FNumSamples);
getMem(FOutBuffer, sizeof(TComplex)*FNumSamples);
except on EOutOfMemorydo
raise EFastFourierError.Create('Could not allocate memory for complex arrays');
end;
end;
function TDSXFastFourier.GetTransformedData(idx : integer) : TComplex;
begin
Result := FOutBuffer[idx];
end;
function TDSXFastFourier.IsPowerOfTwo ( x: word ): boolean;
var i, y: word;
begin
y := 2;
for i := 1 to 31do
begin
if x = y then
begin
IsPowerOfTwo := TRUE;
exit;
end;
y := y SHL 1;
end;
IsPowerOfTwo := FALSE;
end;
function TDSXFastFourier.NumberOfBitsNeeded ( PowerOfTwo: word ): word;
var i: word;
begin
for i := 0 to 16do
begin
if (PowerOfTwo AND (1 SHL i)) <> 0 then
begin
NumberOfBitsNeeded := i;
exit;
end;
end;
end;
function TDSXFastFourier.ReverseBits ( index, NumBits: word ): word;
var i, rev: word;
begin
rev := 0;
for i := 0 to NumBits-1do
begin
rev := (rev SHL 1) OR (index AND 1);
index := index SHR 1;
end;
ReverseBits := rev;
end;
procedure TDSXFastFourier.FourierTransform ( AngleNumerator: do
uble);
var
NumBits, i, j, k, n, BlockSize, BlockEnd: word;
delta_angle, delta_ar:do
uble;
alpha, beta:do
uble;
tr, ti, ar, ai:do
uble;
begin
if not IsPowerOfTwo(FNumSamples) or (FNumSamples<2) then
raise EFastFourierError.Create('NumSamples is not a positive integer power of 2');
if not assigned(FOnGetData) then
raise EFastFourierError.Create('You must specify an OnGetData handler');
NumBits := NumberOfBitsNeeded (FNumSamples);
for i := 0 to FNumSamples-1do
begin
j := ReverseBits ( i, NumBits );
FOnGetData(i,FInBuffer);
FOutBuffer[j] := FInBuffer;
end;
BlockEnd := 1;
BlockSize := 2;
while BlockSize <= FNumSamplesdo
begin
delta_angle := AngleNumerator / BlockSize;
alpha := sin ( 0.5 * delta_angle );
alpha := 2.0 * alpha * alpha;
beta := sin ( delta_angle );
i := 0;
while i < FNumSamplesdo
begin
ar := 1.0;
(* cos(0) *)
ai := 0.0;
(* sin(0) *)
j := i;
for n := 0 to BlockEnd-1do
begin
k := j + Blockend;
tr := ar*FOutBuffer[k].Real - ai*FOutBuffer[k].Imag;
ti := ar*FOutBuffer[k].Imag + ai*FOutBuffer[k].Real;
FOutBuffer[k].Real := FOutBuffer[j].Real - tr;
FOutBuffer[k].Imag := FOutBuffer[j].Imag - ti;
FOutBuffer[j].Real := FOutBuffer[j].Real + tr;
FOutBuffer[j].Imag := FOutBuffer[j].Imag + ti;
delta_ar := alpha*ar + beta*ai;
ai := ai - (alpha*ai - beta*ar);
ar := ar - delta_ar;
INC(j);
end;
i := i + BlockSize;
end;
BlockEnd := BlockSize;
BlockSize := BlockSize SHL 1;
end;
end;
procedure TDSXFastFourier.fft;
begin
FourierTransform ( 2*PI);
end;
procedure TDSXFastFourier.ifft;
var
i: word;
begin
FourierTransform ( -2*PI);
(* Normalize the resulting time samples... *)
for i := 0 to FNumSamples-1do
begin
FOutBuffer.Real := FOutBuffer.Real / FNumSamples;
FOutBuffer.Imag := FOutBuffer.Imag / FNumSamples;
end;
end;
procedure TDSXFastFourier.CalcFrequency (FrequencyIndex: word);
var
k: word;
cos1, cos2, cos3, theta, beta:do
uble;
sin1, sin2, sin3:do
uble;
begin
FOutBuffer[0].Real := 0.0;
FOutBuffer[0].Imag := 0.0;
theta := 2*PI * FrequencyIndex / FNumSamples;
sin1 := sin ( -2 * theta );
sin2 := sin ( -theta );
cos1 := cos ( -2 * theta );
cos2 := cos ( -theta );
beta := 2 * cos2;
for k := 0 to FNumSamples-1do
begin
sin3 := beta*sin2 - sin1;
sin1 := sin2;
sin2 := sin3;
cos3 := beta*cos2 - cos1;
cos1 := cos2;
cos2 := cos3;
FOutBuffer[0].Real := FOutBuffer[0].Real + FInBuffer[k].Real*cos3 - FInBuffer[k].Imag*sin3;
FOutBuffer[0].Imag := FOutBuffer[0].Imag + FInBuffer[k].Imag*cos3 + FInBuffer[k].Real*sin3;
end;
end;
procedure Register;
begin
RegisterComponents('Free', [TDSXFastFourier]);
end;
end.