[HN Gopher] An Interactive Introduction to Fourier Transforms (2...
___________________________________________________________________
An Interactive Introduction to Fourier Transforms (2019)
Author : zerojames
Score : 108 points
Date : 2023-05-17 10:26 UTC (1 days ago)
(HTM) web link (www.jezzamon.com)
(TXT) w3m dump (www.jezzamon.com)
| dang wrote:
| Related:
|
| _An Interactive Introduction to Fourier Transforms_ -
| https://news.ycombinator.com/item?id=25095724 - Nov 2020 (52
| comments)
|
| _An Interactive Introduction to Fourier Transforms_ -
| https://news.ycombinator.com/item?id=20934347 - Sept 2019 (44
| comments)
|
| _An Interactive Introduction to Fourier Transforms_ -
| https://news.ycombinator.com/item?id=18879957 - Jan 2019 (22
| comments)
| ithkuil wrote:
| For a moment I thought it would also draw each of the circles
| that draw themselves
| hinkley wrote:
| Paging Randall Munroe.
| zerojames wrote:
| This post was inspired by:
| https://news.ycombinator.com/item?id=35971785
|
| I love interactive visualizations like this one for the fourier
| transformation.
| sillyinseattle wrote:
| How cool! Free of jargon and loads of intuition
| moglito wrote:
| That first audio example just blew my mind! I can't believe I've
| lived my whole life to learn only now that our ears essentially
| just pick out all the sine waves in a complicated wave. Thank
| you!
| baby wrote:
| What I find really intriguing is how versatile and powerful
| fourier transforms in the discrete setting are. In a finite field
| you can use them to interpolate or evaluate polynomials quickly,
| to generate lagrange basis, etc.
|
| It'd be interested to read more about this if someone has a link.
| Not just how it works, but why it works.
| meindnoch wrote:
| The Fourier transform of the coefficient vector of an Nth order
| polynomial is the evaluation of the polynomial at N powers of a
| primitive Nth root of unity. The inverse Fourier transform is
| the same, except in reverse order of the coefficients, and some
| scaling factor.
|
| You can say that the Fourier transform is a way to convert
| between the coefficient representation and the evaluation point
| representation of polynomials - _with the caveat that the
| evaluation points must be powers of a primitive Nth root of
| unity_.
|
| Luckily, the multiplicative group of the finite field GF(q) is
| cyclic, so every nonzero element is going to be some power of
| the primitive (q-1)th root of unity!
|
| In other words: in finite fields there's no restriction on the
| evaluation points; the (inverse)Fourier transform is always
| applicable for mass-evaluating polynomials (Fourier transform)
| or doing Lagrange interpolation (inverse Fourier transform).
| ithinkso wrote:
| > In other words: in finite fields there's no restriction on
| the evaluation points
|
| What about prime-power order? Does it also hold?
| meindnoch wrote:
| I meant GF(q) to be the general finite field, i.e. GF(p^m)
| for prime p, and n >= 1
|
| The multiplicative group of a finite field is always cyclic
| of order one less than the order of the field.
|
| What's more interesting to ask is what happens when you're
| working over GF(q) and want to do evaluate polynomials of
| length N, if N does not divide q-1? You see, the Fourier
| transform needs a primitive Nth root of unity to work, but
| in GF(q) there's no Nth root of unity if N doesn't divide
| q-1.
|
| Maybe if we extend the polynomial with zero coefficients we
| can upgrade our Fourier transform from length N < q-1 to
| length q-1? It sounds workable. But is there a similar
| trick for Lagrange interpolation?
| Nurbek-F wrote:
| As a graduate electronics engineer, I wish teachers could explain
| in a similar interactive way.
| hinkley wrote:
| Is there a variation of FFT that works with square wave functions
| instead of sine waves?
|
| It seems like for DSP it might be worthwhile to build something
| that works on discrete signals out of the box instead of
| approximating them with sine functions.
| cherryteastain wrote:
| The reason why the Fourier basis works so well is because it
| forms an orthogonal basis for all smooth real-valued functions.
| We'd need a similar way to define square waves which form an
| orthogonal basis. Found one paper doing that: A REVIEW OF
| ORTHOGONAL SQUARE-WAVE FUNCTIONS AND THEIR APPLICATION TO
| LINEAR NETWORKS [1]
|
| Give it a try!
|
| [1]
| https://www.sciencedirect.com/science/article/abs/pii/001600...
| jezzamon wrote:
| Nice to see this being shared again! I'm the author, let me know
| if you have any questions! :)
| el_don_almighty wrote:
| WOW! I just had more fun than I ever imagined. That was like
| cotton candy.
|
| I really enjoyed that.
| Workaccount2 wrote:
| Fun!
| zvmaz wrote:
| This is a marvelous piece of art! Many thanks to the author.
| CrampusDestrus wrote:
| This was a really good visualization and the quality of the
| interaction really made it worth the visit!
___________________________________________________________________
(page generated 2023-05-18 23:01 UTC)