File:FFTexample16T.png: Difference between revisions
imported>Dmitrii Kouznetsov ({{Image_Details|user |description = Application of the FFT operator to the array that approximates the self-Fourier gaussian |author = ~~~ |date-created = 9 October 2011 |pub-country = Japan |notes = Comparison of the discrete Fourier transform, shown with red, of a self–Fourier function <math>A(x)=\exp(-x^2/2)</math>, shown with black dots, to the result of the numerical evaluation of the the Fourier operator of array <math>A</math>, shown with blue. The disc...) |
imported>Dmitrii Kouznetsov |
||
Line 8: | Line 8: | ||
of a [[self–Fourier function]] <math>A(x)=\exp(-x^2/2)</math>, shown with black dots, to the result of the numerical evaluation of the the [[Fourier operator]] of array <math>A</math>, shown with blue. The discrete representation is performed with number of nodes <math>n\!=\!16</math>. | of a [[self–Fourier function]] <math>A(x)=\exp(-x^2/2)</math>, shown with black dots, to the result of the numerical evaluation of the the [[Fourier operator]] of array <math>A</math>, shown with blue. The discrete representation is performed with number of nodes <math>n\!=\!16</math>. | ||
The function <math>A</math> is represented at the mesh with nodes <math>x_n=\sqrt{\frac{\pi}{8}} (n\!-\!8)~,~ n=0 .. 15</math> in such a way that <math>A_n=A(x_n)</math> | |||
The [[FFT]] of array <math>A</math> is performed with the routine | |||
void fft(z_type *a, int N, int o) // Arry is FIRST! | |||
{z_type u,w,t; int i,j,k,l,e=1,L,p,q,m; | |||
q=N/2; p=2; for(m=1;p<N;m++) p*=2; | |||
p=N-1; z_type y=z_type(0.,M_PI*o); j=0; | |||
for(i=0;i<p;i++){ if(i<j) { t=a[j]; a[j]=a[i]; a[i]=t;} | |||
k=q; while(k<=j){ j-=k; k/=2;} | |||
j+=k; } | |||
for(l=0;l<m;l++) | |||
{ L=e; e*=2; u=1.; w=exp(y/((double)L)); | |||
for(j=0;j<L;j++) | |||
{ for(i=j;i<N;i+=e){k=i+L; t=a[k]*u; a[k]=a[i]-t; a[i]+=t;} | |||
u*=w; | |||
} } | |||
} | |||
However, the transformation with the routine [[fafo.cin]] would return practically the same array, while the routine fafo is the discrete analogy of the [[Fourier operator]] and function <math>A</math> is [[self Fourier]]. | |||
The figure shows difference between [[FFT]] and the discrete implementation of the [[Fourier operator]]. For the self-Fourier Gaussian, the Fourier operator returns the same array, while the [[FFT]] returns the saw-like structure. For the physical applications, [[fafo.cin]] seems to be more suitable. | |||
==[[C++]] generator of curves== | ==[[C++]] generator of curves== | ||
File [[fafo.cin]] should be loaded to the working directory for the compilation of the code below. | // The picture is generated with the | ||
//File [[fafo.cin]] should be loaded to the working directory for the compilation of the code below. | |||
#include<math.h> | #include<math.h> | ||
Line 89: | Line 112: | ||
The result is concerted to the [[PNG]] format with default reaolution. | The result is concerted to the [[PNG]] format with default reaolution. | ||
|versions = | |versions = The image is loaded from http://tori.ils.uec.ac.jp/TORI/index.php/File:FFTexample16T.png | ||
}} | }} | ||
==Latex generator of labels== | |||
The labels are drawn with the [[Latex]] document below. File FFTexample16.pdf is supposed to be already generated with the [[C++]] code above and stored in the working directory. | |||
<nowiki> | |||
\documentclass[12pt]{article} %<br> | |||
\usepackage{geometry} %<br> | |||
\paperwidth 1012pt %<br> | |||
\paperheight 740pt %<br> | |||
\textheight 800pt | |||
\topmargin -104pt %<br> | |||
\oddsidemargin -92pt %<br> | |||
\parindent 0pt %<br> | |||
\pagestyle{empty} %<br> | |||
\usepackage{graphicx} %<br> | |||
\newcommand \sx \scalebox %<br> | |||
\begin{document} %<br> | |||
\begin{picture}(1024,742) %<br> | |||
\put(4,0){\includegraphics{FFTexample16}} %<br> | |||
%\put(510,732){\sx{2.4}{$y$}} %<br> | |||
\put(510,634){\sx{2.5}{$y$}} %<br> | |||
\put(510,532){\sx{2.4}{$2$}} %<br> | |||
\put(510,432){\sx{2.4}{$1$}} %<br> | |||
%\put(510,320){\sx{2.4}{$0$}} %<br> | |||
\put(496,232){\sx{2.4}{$-\!1$}} %<br> | |||
\put(496,132){\sx{2.4}{$-\!2$}} %<br> | |||
\put(496, 32){\sx{2.4}{$-\!3$}} %<br> | |||
%<br> | |||
\put(104,310){\sx{2.4}{$-4$}} %<br> | |||
\put(204,310){\sx{2.4}{$-3$}} %<br> | |||
\put(304,310){\sx{2.4}{$-2$}} %<br> | |||
\put(404,310){\sx{2.4}{$-1$}} %<br> | |||
\put(522,310){\sx{2.4}{$0$}} %<br> | |||
\put(622,310){\sx{2.4}{$1$}} %<br> | |||
\put(722,310){\sx{2.4}{$2$}} %<br> | |||
\put(822,310){\sx{2.4}{$3$}} %<br> | |||
\put(923,310){\sx{2.4}{$4$}} %<br> | |||
\put(1016,311){\sx{2.5}{$x$}} %<br> | |||
\put(19,360){\sx{2.6}{$x_0$}} %<br> | |||
\put(79,360){\sx{2.6}{$x_1$}} %<br> | |||
\put(140,360){\sx{2.6}{$x_2$}} %<br> | |||
\put(199,360){\sx{2.6}{$x_3$}} %<br> | |||
\put(261,360){\sx{2.6}{$x_4$}} %<br> | |||
\put(327,360){\sx{2.6}{$x_5$}} %<br> | |||
\put(388,360){\sx{2.6}{$x_6$}} %<br> | |||
\put(450,360){\sx{2.6}{$x_7$}} %<br> | |||
\put(518,360){\sx{2.6}{$x_8$}} %<br> | |||
\put(578,360){\sx{2.6}{$x_9$}} %<br> | |||
\put(640,360){\sx{2.6}{$x_{10}$}} %<br> | |||
\put(704,360){\sx{2.6}{$x_{11}$}} %<br> | |||
\put(767,360){\sx{2.6}{$x_{12}$}} %<br> | |||
\put(829,360){\sx{2.6}{$x_{13}$}} %<br> | |||
\put(890,360){\sx{2.6}{$x_{14}$}} %<br> | |||
\put(950,360){\sx{2.6}{$x_{15}$}} %<br> | |||
\end{picture} %<br> | |||
\end{document} | |||
%</nowiki> | |||
==Keywords== | |||
[[Fourier operator]], | |||
[[Explicit plots]], | |||
[[FFT]] | |||
== Licensing == | == Licensing == | ||
{{CC|by|3.0}} | {{CC|by|3.0}} |
Revision as of 08:49, 4 September 2012
Summary
Title / Description
|
Application of the FFT operator to the array that approximates the self-Fourier gaussian |
---|---|
Citizendium author & Copyright holder
|
Copyright © Dmitrii Kouznetsov. See below for licence/re-use information. |
Date created
|
9 October 2011 |
Country of first publication
|
Japan |
Notes
|
Comparison of the discrete Fourier transform, shown with red,
of a self–Fourier function , shown with black dots, to the result of the numerical evaluation of the the Fourier operator of array , shown with blue. The discrete representation is performed with number of nodes . The function is represented at the mesh with nodes in such a way that The FFT of array is performed with the routine void fft(z_type *a, int N, int o) // Arry is FIRST! {z_type u,w,t; int i,j,k,l,e=1,L,p,q,m; q=N/2; p=2; for(m=1;p<N;m++) p*=2; p=N-1; z_type y=z_type(0.,M_PI*o); j=0; for(i=0;i<p;i++){ if(i<j) { t=a[j]; a[j]=a[i]; a[i]=t;} k=q; while(k<=j){ j-=k; k/=2;} j+=k; } for(l=0;l<m;l++) { L=e; e*=2; u=1.; w=exp(y/((double)L)); for(j=0;j<L;j++) { for(i=j;i<N;i+=e){k=i+L; t=a[k]*u; a[k]=a[i]-t; a[i]+=t;} u*=w; } } } However, the transformation with the routine fafo.cin would return practically the same array, while the routine fafo is the discrete analogy of the Fourier operator and function is self Fourier. The figure shows difference between FFT and the discrete implementation of the Fourier operator. For the self-Fourier Gaussian, the Fourier operator returns the same array, while the FFT returns the saw-like structure. For the physical applications, fafo.cin seems to be more suitable. C++ generator of curves// The picture is generated with the //File fafo.cin should be loaded to the working directory for the compilation of the code below. #include<math.h> #include<stdio.h> #include <stdlib.h> #include <complex> using namespace std; #define z_type complex<double> #define Re(x) x.real() #define Im(x) x.imag() #define RI(x) x.real(),x.imag() #define DB double #define DO(x,y) for(x=0;x<y;x++) void ado(FILE *O, int X, int Y) { fprintf(O,"%c!PS-Adobe-2.0 EPSF-2.0\n",'%'); fprintf(O,"%c%cBoundingBox: 0 0 %d %d\n",'%','%',X,Y); fprintf(O,"/M {moveto} bind def\n"); fprintf(O,"/L {lineto} bind def\n"); fprintf(O,"/S {stroke} bind def\n"); fprintf(O,"/s {show newpath} bind def\n"); fprintf(O,"/C {closepath} bind def\n"); fprintf(O,"/F {fill} bind def\n"); fprintf(O,"/o {.025 0 360 arc C F} bind def\n"); fprintf(O,"/times-Roman findfont 20 scalefont setfont\n"); fprintf(O,"/W {setlinewidth} bind def\n"); fprintf(O,"/RGB {setrgbcolor} bind def\n");} // #include "ado.cin" #include"fafo.cin" // DB F(DB x){DB u=x*x; return u*(-3.+u)*exp(-x*x/2.);} DB F(DB x){ return exp(-x*x/2.);} main(){z_type * a, *b, c; int j,m,n, N=16; FILE *o; double step=sqrt(2*M_PI/N),x,y,u; a=(z_type *) malloc((size_t)((N+1)*sizeof(z_type))); b=(z_type *) malloc((size_t)((N+1)*sizeof(z_type))); //for(j=0;j<N;j++) { x=step*(j-N/2); u=x*x; a[j]=b[j]=(3.+u*(-6.+u))*exp(-x*x/2); } for(j=0;j<N;j++) { x=step*(j-N/2); u=x*x; a[j]=b[j]=F(x); } fft(b,N,1); for(j=0;j<N;j++) printf("%2d %18.15f %18.15f %18.15f %18.15f\n", j, RI(a[j]), RI(b[j]) ); o=fopen("FFTexample16.eps","w"); ado(o,1024,780); #define M(x,y) fprintf(o,"%6.4f %6.4f M\n",0.+x,0.+y); #define L(x,y) fprintf(o,"%6.4f %6.4f L\n",0.+x,0.+y); #define o(x,y) fprintf(o,"%6.4f %6.4f o\n",0.+x,0.+y); fprintf(o,"522 340 translate 100 100 scale\n"); // M(-5,0) L(5,0) M(0,0) L(0,1) fprintf(o,".01 W S\n"); // M(-5,1) L(5,1) M(-5,-1) L(5,-1) for(m=-5;m<6;m++) {M(m,-3) L(m,3)} fprintf(o,".004 W S\n"); for(m=-3;m<4;m++) {M(-5,m) L(5,m)} fprintf(o,".004 W S\n"); fprintf(o,"1 setlinejoin 1 setlinecap\n"); DB *X; X=(DB *) malloc((size_t)((N+1)*sizeof(DB))); DO(j,N){ x=step*(j-N/2); X[j]=x; } DO(j,N){x=X[j]; M(x,0)L(x,.15)} fprintf(o,".01 W S\n"); DO(j,N){x=X[j];y=Re(a[j]); if(j==0)M(x,y)else L(x,y);} fprintf(o,".04 W 0 .4 1 RGB S\n"); DO(j,N){x=X[j];y=Re(b[j]); if(j==0)M(x,y)else L(x,y);} fprintf(o,".04 W 1 0 0 RGB S\n"); // DO(j,N){x=X[j];y=Im(b[j]); if(j==0)M(x,y)else L(x,y);} fprintf(o,".04 W 1 0 0 RGB S\n"); // DO(j,N){x=X[j];y=100.*(Re(b[j])-F(x)); if(j==0)M(x,y)else L(x,y);} fprintf(o,"0.007 W 0 0 .3 RGB S\n"); printf("X[0]=%9.5f step=%9.6f\n",X[0],step); // DO(m,101){x=-5.+.1*m; y=F(x); if(m/2*2==m)M(x,y)else L(x,y);} fprintf(o,".01 W 0 0 0 RGB S\n"); fprintf(o,".01 W 0 0 0 RGB S\n"); DO(m,101){x=-5.+.1*m; y=F(x); o(x,y)} fprintf(o,"showpage\n%cTrailer",'%'); fclose(o); system("epstopdf FFTexample16.eps"); system( "open FFTexample16.pdf"); //these 2 commands may be specific for macintosh getchar(); system("killall Preview");// if run at another operational system, may need to modify free(a); free(b); free(X); } The image is generated in the following way. The lines are drawn in the EPS format by the C++ code below. The result is concerted to PDF format. The labels are added in the latex document below. The result is concerted to the PNG format with default reaolution. |
Other versions
|
The image is loaded from http://tori.ils.uec.ac.jp/TORI/index.php/File:FFTexample16T.png |
Using this image on CZ
|
| , then copy the code below to add this image to a Citizendium article, changing the size, alignment, and caption as necessary.
Please send email to manager A T citizendium.org .
Latex generator of labels
The labels are drawn with the Latex document below. File FFTexample16.pdf is supposed to be already generated with the C++ code above and stored in the working directory.
\documentclass[12pt]{article} %<br> \usepackage{geometry} %<br> \paperwidth 1012pt %<br> \paperheight 740pt %<br> \textheight 800pt \topmargin -104pt %<br> \oddsidemargin -92pt %<br> \parindent 0pt %<br> \pagestyle{empty} %<br> \usepackage{graphicx} %<br> \newcommand \sx \scalebox %<br> \begin{document} %<br> \begin{picture}(1024,742) %<br> \put(4,0){\includegraphics{FFTexample16}} %<br> %\put(510,732){\sx{2.4}{$y$}} %<br> \put(510,634){\sx{2.5}{$y$}} %<br> \put(510,532){\sx{2.4}{$2$}} %<br> \put(510,432){\sx{2.4}{$1$}} %<br> %\put(510,320){\sx{2.4}{$0$}} %<br> \put(496,232){\sx{2.4}{$-\!1$}} %<br> \put(496,132){\sx{2.4}{$-\!2$}} %<br> \put(496, 32){\sx{2.4}{$-\!3$}} %<br> %<br> \put(104,310){\sx{2.4}{$-4$}} %<br> \put(204,310){\sx{2.4}{$-3$}} %<br> \put(304,310){\sx{2.4}{$-2$}} %<br> \put(404,310){\sx{2.4}{$-1$}} %<br> \put(522,310){\sx{2.4}{$0$}} %<br> \put(622,310){\sx{2.4}{$1$}} %<br> \put(722,310){\sx{2.4}{$2$}} %<br> \put(822,310){\sx{2.4}{$3$}} %<br> \put(923,310){\sx{2.4}{$4$}} %<br> \put(1016,311){\sx{2.5}{$x$}} %<br> \put(19,360){\sx{2.6}{$x_0$}} %<br> \put(79,360){\sx{2.6}{$x_1$}} %<br> \put(140,360){\sx{2.6}{$x_2$}} %<br> \put(199,360){\sx{2.6}{$x_3$}} %<br> \put(261,360){\sx{2.6}{$x_4$}} %<br> \put(327,360){\sx{2.6}{$x_5$}} %<br> \put(388,360){\sx{2.6}{$x_6$}} %<br> \put(450,360){\sx{2.6}{$x_7$}} %<br> \put(518,360){\sx{2.6}{$x_8$}} %<br> \put(578,360){\sx{2.6}{$x_9$}} %<br> \put(640,360){\sx{2.6}{$x_{10}$}} %<br> \put(704,360){\sx{2.6}{$x_{11}$}} %<br> \put(767,360){\sx{2.6}{$x_{12}$}} %<br> \put(829,360){\sx{2.6}{$x_{13}$}} %<br> \put(890,360){\sx{2.6}{$x_{14}$}} %<br> \put(950,360){\sx{2.6}{$x_{15}$}} %<br> \end{picture} %<br> \end{document} %
Keywords
Fourier operator, Explicit plots, FFT
Licensing
This media, FFTexample16T.png, is licenced under the Creative Commons Attribution 3.0 Unported License
You are free:
To Share — To copy, distribute and transmit the work; To Remix — To adapt the work.
Under the following conditions:
Attribution — You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work).
For any reuse or distribution, you must make clear to others the licence terms of this work (the best way to do this is with a link to this licence's web page). Any of the above conditions can be waived if you get permission from the copyright holder. Nothing in this licence impairs or restricts the author's moral rights.
Read the full licence.
File history
Click on a date/time to view the file as it appeared at that time.
Date/Time | Thumbnail | Dimensions | User | Comment | |
---|---|---|---|---|---|
current | 18:57, 11 March 2022 | 2,101 × 1,536 (155 KB) | Maintenance script (talk | contribs) | == Summary == Importing file |
You cannot overwrite this file.
File usage
The following page uses this file: