yates@ieee.org (Randy Yates) wrote in message news:<567ce618.0306250841.698282f8@posting.google.com>...> Then the inverse FT lies?Well, that's an interesting question... the truth is, I have never seen a good treatment of the Inverse Discrete Fourier Transform. I believe the continuous case was treated by Papoulis in his nowhere-to-be-found book, but the *discrete* inverse transform has eluded me (does anybody know of such a treatment?). As far as I can remember, we always computed forward transforms and implemented the inverse transform by "recognizing X(f) as the transformed x(t)" by means of table lookup. I wouldn't be surprised if answering your questions would require the full math-chinery, and very careful evaluation and analysis of some more or less obscure boundary condition. Rune
sinc() question
Started by ●June 24, 2003
Reply by ●June 26, 20032003-06-26
Reply by ●June 26, 20032003-06-26
Rune Allnor wrote:> > yates@ieee.org (Randy Yates) wrote in message news:<567ce618.0306250841.698282f8@posting.google.com>... > > > Then the inverse FT lies? > > Well, that's an interesting question... the truth is, I have never > seen a good treatment of the Inverse Discrete Fourier Transform. > > I believe the continuous case was treated by Papoulis in his > nowhere-to-be-found book, but the *discrete* inverse transform > has eluded me (does anybody know of such a treatment?). > > As far as I can remember, we always computed forward transforms > and implemented the inverse transform by "recognizing X(f) as the > transformed x(t)" by means of table lookup. I wouldn't be surprised > if answering your questions would require the full math-chinery, and > very careful evaluation and analysis of some more or less obscure > boundary condition. > > RuneSort of apropos: a "mentee"'s homework was to write two-dimentional DFT, then test the code with an image that is a uniform gray. His code produced a transform that was zero everywhere. Clearly, it needs to be zero a.e., but the "DC" term needs a value, else all shades of gray, when DFTed then IDFTed would return black. That argument was enough to convince him that he had a bug. But the DFT is zero everywhere with a single exception. Hmmm. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●June 26, 20032003-06-26
"Rune Allnor" <allnor@tele.ntnu.no> wrote in message news:f56893ae.0306260414.2a72e7c2@posting.google.com...> yates@ieee.org (Randy Yates) wrote in messagenews:<567ce618.0306250841.698282f8@posting.google.com>...> > > Then the inverse FT lies? > > Well, that's an interesting question... the truth is, I have never > seen a good treatment of the Inverse Discrete Fourier Transform. > > I believe the continuous case was treated by Papoulis in his > nowhere-to-be-found book, but the *discrete* inverse transform > has eluded me (does anybody know of such a treatment?). > > As far as I can remember, we always computed forward transforms > and implemented the inverse transform by "recognizing X(f) as the > transformed x(t)" by means of table lookup. I wouldn't be surprised > if answering your questions would require the full math-chinery, and > very careful evaluation and analysis of some more or less obscure > boundary condition. > > RuneRune, I think the reason for this is Duality. If you know one, you know the other. If you Google on [duality "discrete fourier transform"] you may find something that makes sense for you. Or, did you mean something else? Fred
Reply by ●June 26, 20032003-06-26
"Jerry Avins" <jya@ieee.org> wrote in message news:3EFAF198.43303370@ieee.org...> Rune Allnor wrote: > > > > yates@ieee.org (Randy Yates) wrote in messagenews:<567ce618.0306250841.698282f8@posting.google.com>...> > > > > Then the inverse FT lies? > > > > Well, that's an interesting question... the truth is, I have never > > seen a good treatment of the Inverse Discrete Fourier Transform. > > > > I believe the continuous case was treated by Papoulis in his > > nowhere-to-be-found book, but the *discrete* inverse transform > > has eluded me (does anybody know of such a treatment?). > > > > As far as I can remember, we always computed forward transforms > > and implemented the inverse transform by "recognizing X(f) as the > > transformed x(t)" by means of table lookup. I wouldn't be surprised > > if answering your questions would require the full math-chinery, and > > very careful evaluation and analysis of some more or less obscure > > boundary condition. > > > > Rune > > Sort of apropos: a "mentee"'s homework was to write two-dimentional DFT, > then test the code with an image that is a uniform gray. His code > produced a transform that was zero everywhere. Clearly, it needs to be > zero a.e., but the "DC" term needs a value, else all shades of gray, > when DFTed then IDFTed would return black. That argument was enough to > convince him that he had a bug. But the DFT is zero everywhere with a > single exception. Hmmm. > > JerryJerry, Do you mean that he/she had a bug or that the 2DFT was truly zero everywhere? It shouldn't be, should it? The gray scale value should return a spike - which I take to be your "single exception"? Fred
Reply by ●June 26, 20032003-06-26
Fred Marshall wrote:> > "Jerry Avins" <jya@ieee.org> wrote in message > news:3EFAF198.43303370@ieee.org... > > Rune Allnor wrote: > > > > > > yates@ieee.org (Randy Yates) wrote in message > news:<567ce618.0306250841.698282f8@posting.google.com>... > > > > > > > Then the inverse FT lies? > > > > > > Well, that's an interesting question... the truth is, I have never > > > seen a good treatment of the Inverse Discrete Fourier Transform. > > > > > > I believe the continuous case was treated by Papoulis in his > > > nowhere-to-be-found book, but the *discrete* inverse transform > > > has eluded me (does anybody know of such a treatment?). > > > > > > As far as I can remember, we always computed forward transforms > > > and implemented the inverse transform by "recognizing X(f) as the > > > transformed x(t)" by means of table lookup. I wouldn't be surprised > > > if answering your questions would require the full math-chinery, and > > > very careful evaluation and analysis of some more or less obscure > > > boundary condition. > > > > > > Rune > > > > Sort of apropos: a "mentee"'s homework was to write two-dimentional DFT, > > then test the code with an image that is a uniform gray. His code > > produced a transform that was zero everywhere. Clearly, it needs to be > > zero a.e., but the "DC" term needs a value, else all shades of gray, > > when DFTed then IDFTed would return black. That argument was enough to > > convince him that he had a bug. But the DFT is zero everywhere with a > > single exception. Hmmm. > > > > Jerry > > Jerry, > > Do you mean that he/she had a bug or that the 2DFT was truly zero > everywhere? It shouldn't be, should it? The gray scale value should return > a spike - which I take to be your "single exception"? > > FredExactly so! I'm learning along with him, only faster. He tends to think that what looks right and doesn't bomb, is right. In his case it's wishful thinking, not hubris, but it leads to the same error. (He bears the burden of chasing down the bug and doing it over, so I have no incentive to think wishfully.) Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●June 26, 20032003-06-26
Hello Rune, comments below: "Rune Allnor" <allnor@tele.ntnu.no> wrote in message news:f56893ae.0306260414.2a72e7c2@posting.google.com...> yates@ieee.org (Randy Yates) wrote in messagenews:<567ce618.0306250841.698282f8@posting.google.com>...> > > Then the inverse FT lies? > > Well, that's an interesting question... the truth is, I have never > seen a good treatment of the Inverse Discrete Fourier Transform. > > I believe the continuous case was treated by Papoulis in his > nowhere-to-be-found book, but the *discrete* inverse transform > has eluded me (does anybody know of such a treatment?).A proof of the continuous case can be found on line at: http://kr.cs.ait.ac.th/~radok/math/mat9/04c.htm about halfway down And I found a proof for the discrete case in E. Oran Brigham's "The Fast Fourier Transform" pp 98-99 He shows all of the steps except where you need to apply L'Hospital's rule to see that a certain term reduces to a Kronecker Delta. He just cites that identity. I don't see it as a flaw, since this can be easily verified using freshman calculus.> > As far as I can remember, we always computed forward transforms > and implemented the inverse transform by "recognizing X(f) as the > transformed x(t)" by means of table lookup.This is certainly like the LaGrange approach to integration. Everytime you do a derivative put it in a table so you can work it bachwards when needed. And certainly this approach works well for many types of integral transforms. Even some discrete transforms, Fourier and Z, benefit from this approach. We are certainly able to easily find the FT of a Rect(t) function by simple integration. Going the other way takes a little more effort, so most resort to the duality theorem to avoid the effort. Integrating sin(x)/x can be done as in the above link or it can easily done by contour integration of an analytic extention of the original integral.> I wouldn't be surprised > if answering your questions would require the full math-chinery, and > very careful evaluation and analysis of some more or less obscure > boundary condition.I think most of the answer for Randy's question can be found in the above link since the Dirichlet Discontinous Factor is a generalization of the sin(x)/ x problem. The DDF also includes a cosine factor which can be reduced to one for this case. Clay> > Rune
Reply by ●June 27, 20032003-06-27
"Clay S. Turner" <physics@bellsouth.net> wrote in message news:<uPFKa.41022$uK1.9683@fe05.atl2.webusenet.com>...> Hello Rune, > comments below: > > "Rune Allnor" <allnor@tele.ntnu.no> wrote in message > news:f56893ae.0306260414.2a72e7c2@posting.google.com... > > yates@ieee.org (Randy Yates) wrote in message > news:<567ce618.0306250841.698282f8@posting.google.com>... > > > > > Then the inverse FT lies? > > > > Well, that's an interesting question... the truth is, I have never > > seen a good treatment of the Inverse Discrete Fourier Transform. > > > > I believe the continuous case was treated by Papoulis in his > > nowhere-to-be-found book, but the *discrete* inverse transform > > has eluded me (does anybody know of such a treatment?). > > A proof of the continuous case can be found on line at: > > http://kr.cs.ait.ac.th/~radok/math/mat9/04c.htm about halfway down > > And I found a proof for the discrete case in E. Oran Brigham's "The Fast > Fourier Transform" pp 98-99Thanks. I'll have to check that one out some time.> He shows all of the steps except where you need to apply L'Hospital's rule > to see that a certain term reduces to a Kronecker Delta. He just cites that > identity. I don't see it as a flaw, since this can be easily verified using > freshman calculus. > > > > > As far as I can remember, we always computed forward transforms > > and implemented the inverse transform by "recognizing X(f) as the > > transformed x(t)" by means of table lookup. > > This is certainly like the LaGrange approach to integration. Everytime you > do a derivative put it in a table so you can work it bachwards when needed. > And certainly this approach works well for many types of integral > transforms. Even some discrete transforms, Fourier and Z, benefit from this > approach.Table lookup is convenient, as long as what you look for already is in the table. What Randy's question is conserned, I think it can be answered better if one actually does the exercise of analytically computing the inverse DFT. See below.> We are certainly able to easily find the FT of a Rect(t) function by simple > integration. Going the other way takes a little more effort, so most resort > to the duality theorem to avoid the effort. Integrating sin(x)/x can be done > as in the above link or it can easily done by contour integration of an > analytic extention of the original integral.Yep, right. Now, I have a very vague recollection of having done contour integration in some class more than ten years ago. It was a general maths course aimed at maths students and PhD students from other departments. I got the impression that the professor just checked items on a list, what the curriculum was concerned. There was some mentioning of applications to the inverse (D)FT at the end of the course, but nothing near pointing this out as a conclusion of the course; or even noting the importance of the I(D)FT. I have seen remarks by mathematicians on real analysis, which I suppose apply to complex function theory as well, that the subject was "almost exhausted" from a research point of view (in the afterword to Young: "Introduction to Hilbert Space", 1988). It seems to me as if the mathematicians don't teach the techiques and the engineers are happy with the Plug'n Pray solutions the tables in reality are. I don't know what to make of it, though...> > I wouldn't be surprised > > if answering your questions would require the full math-chinery, and > > very careful evaluation and analysis of some more or less obscure > > boundary condition. > > I think most of the answer for Randy's question can be found in the above > link since the Dirichlet Discontinous Factor is a generalization of the > sin(x)/ x problem. The DDF also includes a cosine factor which can be > reduced to one for this case. > > > ClayRune
Reply by ●June 27, 20032003-06-27
"Clay S. Turner" wrote:> [...] > Integrating sin(x)/x can be done > as in the above link or it can easily done by contour integration of an > analytic extention of the original integral.Isn't the inverse Fourier transform a special case of the inverse Laplace transform, and the inverse Laplace transform is a Bromwich integral, i.e., a complex contour integral around a special half-circle contour in the complex plane? -- % Randy Yates % "...the answer lies within your soul %% Fuquay-Varina, NC % 'cause no one knows which side %%% 919-577-9882 % the coin will fall." %%%% <yates@ieee.org> % 'Big Wheels', *Out of the Blue*, ELO http://home.earthlink.net/~yatescr
Reply by ●June 30, 20032003-06-30
Hello Randy, Basically the answer is yes. I had a prof (for PDEs) who loosely stated the relationship between Fourier and LaPlace transformation. All you are really doing is changing the domain from infinite to semi-infinite and the argument from real to complex. I.e., whether or not the argument of the exponential in the kernal explicitly includes the imiginary number i. However the contour for the Bromwich integral is taken to be a vertical line to the right of all singularities. Also the line can be legally deformed into a semicircle if kept to the right of all sings. Clay "Randy Yates" <yates@ieee.org> wrote in message news:3EFCFAE5.18D16CE6@ieee.org...> "Clay S. Turner" wrote: > > [...] > > Integrating sin(x)/x can be done > > as in the above link or it can easily done by contour integration of an > > analytic extention of the original integral. > > Isn't the inverse Fourier transform a special case of the inverse > Laplace transform, and the inverse Laplace transform is a Bromwich > integral, i.e., a complex contour integral around a special half-circle > contour in the complex plane? > -- > % Randy Yates % "...the answer lies within your soul > %% Fuquay-Varina, NC % 'cause no one knows which side > %%% 919-577-9882 % the coin will fall." > %%%% <yates@ieee.org> % 'Big Wheels', *Out of the Blue*, ELO > http://home.earthlink.net/~yatescr
Reply by ●July 1, 20032003-07-01
"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message news:<k4EKa.1728$Jk5.809467@feed2.centurytel.net>...> "Rune Allnor" <allnor@tele.ntnu.no> wrote in message > news:f56893ae.0306260414.2a72e7c2@posting.google.com... > > yates@ieee.org (Randy Yates) wrote in message > news:<567ce618.0306250841.698282f8@posting.google.com>... > > > > > Then the inverse FT lies? > > > > Well, that's an interesting question... the truth is, I have never > > seen a good treatment of the Inverse Discrete Fourier Transform. > > > > I believe the continuous case was treated by Papoulis in his > > nowhere-to-be-found book, but the *discrete* inverse transform > > has eluded me (does anybody know of such a treatment?). > > > > As far as I can remember, we always computed forward transforms > > and implemented the inverse transform by "recognizing X(f) as the > > transformed x(t)" by means of table lookup. I wouldn't be surprised > > if answering your questions would require the full math-chinery, and > > very careful evaluation and analysis of some more or less obscure > > boundary condition. > > > > Rune > > Rune, > > I think the reason for this is Duality. If you know one, you know the > other. If you Google on [duality "discrete fourier transform"] you may find > something that makes sense for you. Or, did you mean something else?Duality is no problem. My problem is the technicalities when manipulating Fourier integrals of complex-valued functions. This thread has made it embarrasingly clear to me that I have relied solely on the Plug'n Pray method for evaluating the inverse Fourier transform, and that I'm in way over my head once the functions in question (as well as the questions!) depart from the "everybody knows" answers to "standard" problems. Rune> Fred
