Farey Fourier Window

The classic method use different method of windowing in wich is better to compute more armonics of the signal for obtaining an accurate aproximation:
http://en.wikipedia.org/wiki/Window_function
This technique can be used in the algorithms for: detection, selection, rejection of targets/clutter.
We can see from the programs from below that the leakage of the spectrum density is better for the Farey method vs. rectangular method. The leakage of the spectrum density shows how much each armonics from the Fourier series contribute to the energy of spectrum. The windowing methods want to eliminate the big errors of calculus that can appear at the limits of the sample analyzed. We can see also in the graphics of the spectum density of energy that the values near these boundary are smaller – their armonics do not contribute so much in the final result of the Fourier approximation; only the values near the middle of the graphics on the OX axis.

A program for generating in a file the Farey numbers.

//
//Optimizat cu Programare Dinamica
//
// N maxim = 328 => 32751 termeni
//

# include ;
# include ;
# include ;
# include ;

int N;
int v_N[3280], v_D[3280];
int v_Y[3280], v_X[3280];

FILE * pf;
int x,y,k,NT,i,j;

//
int Y(int n);
int X(int n)
{
if(n==0) {v_X[0]=0;return 0;}
else if(n==1) {v_X[1]=1;return 1;}
else
{
if(v_X[n]!=0) return v_X[n];
else
{
v_X[n]=floor( (v_Y[n-2]+N)/v_Y[n-1] )*v_X[n-1] - v_X[n-2];
return ( floor( (Y(n-2)+N)/Y(n-1) )*X(n-1) - X(n-2) );
}
}
}
int Y(int n)
{
if(n==0) {v_Y[0]=1;return 1;}
else if(n==1) {v_Y[1]=N;return N;}
else
{
if(v_Y[n]!=0) return v_Y[n];
else
{
v_Y[n]=floor( (v_Y[n-2]+N)/v_Y[n-1] )*v_Y[n-1] - v_Y[n-2];
return ( floor( (Y(n-2)+N)/Y(n-1) )*Y(n-1) - Y(n-2) );
}
}
}
//

void main()
{

//clrscr();
cout<<"Intr n= ";
cin>>N;
pf=fopen("FAREY.txt","w+");

k=0;
v_N[k]=x=X(k);
v_D[k]=y=Y(k);

while( (x!=y) && ((float)x/y<=0.5) )
{
cout< fprintf(pf,"%d/%d, ",x,y);
k++;
v_N[k]=x=X(k);
v_D[k]=y=Y(k);
}
NT=k;

//Calculez ceilalti termeni

if(N!=1)
k--;

i=1;
for(j=k-1;j>0;j--)
{
v_N[k+i]=v_D[j]-v_N[j];
v_D[k+i]=v_D[j];

cout< fprintf(pf,"1-%d/%d, ",v_N[k+i],v_D[k+i]);

i++;
NT++;
}

//

cout<<"1"<<"/"<<"1";
fprintf(pf,"%d/%d ",1,1);

v_N[NT]=1;
v_D[NT]=1;
NT++;

cout<<"\nNr de termeni = "<
fclose(pf);

getche();
}


The numbers that are bigger than the ½ are substracted from 1 and the final result is multiplied with 2 to respect the propriety of a window function: it has to have an amplitude equal with 1 and at the limits of interval it must be near 0.


A program in MATLAB with smaller modification from the programs of wikipedia.
The vector “w” can be generated fastest inside the program; it contains the values obtained from Farey series to generate an window function.

N=33;
k=0:N-1;

dr = 60;
w = [0/1, 1/10, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 3/10, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 1-5/9, 1-4/7, 1-3/5, 1-5/8, 1-2/3, 1-7/10, 1-5/7, 1-3/4, 1-7/9, 1-4/5, 1-5/6, 1-6/7, 1-7/8, 1-8/9, 1-9/10, 0 ] * 2;
%w = ones(1,N)

B = N*sum(w.^2)/sum(w)^2; % noise bandwidth (bins)

H = abs(fft([w zeros(1,7*N)]));
H = fftshift(H);
H = H/max(H);
H = 20*log10(H);
H = max(0,dr+H);

figure
area(k,w,'FaceColor', [0 .4 .6])
xlim([0 N-1])
ylim([0 2])
set(gca,'XTick', [0 : 1/8 : 1]*(N-1))
set(gca,'XTickLabel','0| | | | | | | |N-1')
grid on
ylabel('amplitude')
xlabel('samples')
title('Window function (Farey)')

figure
stem(([1:(8*N)]-1-4*N)/8,H,'-');
set(findobj('Type','line'),'Marker','none','Color',[.871 .49 0])
xlim([-4*N 4*N]/8)
ylim([0 dr])
set(gca,'YTickLabel','-60|-50|-40|-30|-20|-10|0')
grid on
ylabel('decibels')
xlabel('DFT bins')
title('Spectral "leakage" from a Farey windowed sinusoid')




The advantages of using the Farey windowing are that only the first armonics must be computed and this is obtained for rectangular window or others only for big values of samples (N big).
This window function not use sin of other function that use more steps in the computer to be aproximated.
The Farey nunbers can be generated faster or can be use an Farey extension/generalisation fore each interval and computed than.
Only for big values of samples (N == 1500 here) the first armonics aproximate in more steps for Fourier calculation the signal.
In this way the clutter or the detection of the targets can be done faster.