<ZipCPU>
Alright, this is gonna hurt ... just when I put the whole description of a butterfly together, I double check my code to see how the three multiplies work and discover I'm doing the other type of butterfly.
emeb_mac has quit [Ping timeout: 272 seconds]
emeb_mac has joined #yosys
<ZipCPU>
Nvm ... I think I just put a parenthesis in the wrong place.
azonenberg_work has quit [Ping timeout: 252 seconds]
azonenberg_work has joined #yosys
azonenberg_work has quit [Quit: Leaving.]
azonenberg_work has joined #yosys
digshadow has joined #yosys
rohitksingh has joined #yosys
rohitksingh has quit [Quit: Leaving.]
rohitksingh has joined #yosys
emeb_mac has quit [Quit: Leaving.]
FL4SHK has quit [Ping timeout: 250 seconds]
_whitelogger has joined #yosys
rohitksingh has quit [Quit: Leaving.]
rohitksingh has joined #yosys
dys has quit [Ping timeout: 240 seconds]
dys has joined #yosys
kuldeep has quit [Ping timeout: 252 seconds]
rohitksingh has quit [Quit: Leaving.]
kuldeep has joined #yosys
rohitksingh has joined #yosys
kuldeep has quit [Read error: Connection reset by peer]
maikmerten has joined #yosys
rohitksingh has quit [Ping timeout: 240 seconds]
rohitksingh has joined #yosys
rohitksingh has quit [Quit: Leaving.]
_whitelogger has joined #yosys
<edmoore>
ZipCPU: is this still the FFT?
<ZipCPU>
edmoore: Yes.
<ZipCPU>
I'm trying to write a blog post about it, to present it to others, and share how I did the formal proof of it.
<edmoore>
Cool
<edmoore>
Yes that would be fascinating
<edmoore>
I dont think ive actually considered how one works since college
<ZipCPU>
That's usually the right answer. It works until ... you need to build one.
<edmoore>
Ive just been a passive user of fftw (or some layer of abstraction above it) ever since
<edmoore>
I remember a homework question where we had to design a radix-3 fft
<edmoore>
Not because it was good but because it was annoying (but i presume showed you had sufficiently digested the technique)
<ZipCPU>
Ever needed an FFT in an FPGA project, and yet still wanted to simulate the project using open source tools? (i.e. Verilator) That's when you need to get an open source FFT.
<ZipCPU>
radix-3 ... yeah, I can see that being sufficiently annoying, and yet a good class exercise as well.
<ZipCPU>
Where I'm getting confused is in the difference between decimation in time and decimation in frequency.
<ZipCPU>
What's making my confusion worse is that the algorithm is already written--I know it works, now I have to make certain I've got figured out which of the two I'm using.
<edmoore>
Yes
<edmoore>
Is it a mechanics question or more one of how mathematical notation is actually a bit ambiguous
<edmoore>
And you only realise when you try and be super rigorous
<ZipCPU>
It's a notation struggle. The implementation has to work at this time. There's no other explanation for why I'd be getting good results.
<edmoore>
Yes
<edmoore>
SICM (fabulous book) implemented its own mathematical notation to get around this problem
<edmoore>
The best homework q i had at college (bearing in mind i was an engineer not a physicist so this wasn’t ‘obvious’) was in a stats and inference course where we had to take the FT of a gaussian distribution
<ZipCPU>
I think I managed to get them right (finally)
<ZipCPU>
At issue is the final line, y1 = W(x0-x1). I somehow had gotten into my head that I was implementing y1 = x0 - W x1
<edmoore>
A little throwaway part at the end was to suppose that position and momentum (in the particle sense) were the inverse of each other, and you know position with varience ‘a’, how confident are you of its momentum
<edmoore>
And you crank it through and get 1/a and think nothing more of it
<ZipCPU>
You remember the FT of a Gaussian is a Gaussian, right? That would be an important property to start from.
<edmoore>
Yes
<edmoore>
So a gaussian of var a FTs to var 1/a
<ZipCPU>
Yep, that'd be it.
<ZipCPU>
If I were more of a physicist, I'd know what to do with the position and momentum comment you just made a moment ago as well.
<edmoore>
And so 3 hours later i was like [excuse my french] ‘MOTHER FU***R THATS HEISENBERGS UNCERTAINTY PRINCIPLE!!!!’
<edmoore>
Which our lecturer had just thrown in as a little candy at the end
<ZipCPU>
Sounds like someone was having some fun
<edmoore>
I.e more confident you are of permission, the less you are of momentum
<edmoore>
And it almost made me religious
<edmoore>
So obvious and simple and elegant
m_t has joined #yosys
<ZipCPU>
I've dealt with a similar uncertainty principle that wikipedia can't seem to get quite right.
<ZipCPU>
It's not Heisenberg's, but it is very related and often confused with it
<edmoore>
Oh?
<ZipCPU>
Let's see ... to describe this one, assume you have a signal x(t). You can know its time distribution with such things as Integral of |x(t)|^2 and its frequency distribution with Integral of |X(f)|^2
<ZipCPU>
The minimum product of the variance of these two distributions is then limited to something like 1/2 or some such
<ZipCPU>
I forget how I last put it together, but that's the one I deal with most.
<ZipCPU>
It gets quite important in determining optimal FFT window functions and so forth.
<ZipCPU>
Did you ever see my FFT window function / frequency estimation teaser?
<ZipCPU>
In your notation, is "n" an integer, or continuous?
<sensille>
there might be a slightly different perspective to look onto the problem that simplifies it
<sensille>
integer
<ZipCPU>
How often are the coefficients changing?
<sensille>
not very
<ZipCPU>
Have you engineered the transitions yet?
<sensille>
< 100 sets/s i guess
<sensille>
i thought i had, but it is not correct
<sensille>
so either i load all values, or just the lower ones, staggered, one per clock
<sensille>
and looked at it this way all this (n-1)(n-2)(n-3) might go away, but i'm not sure
<sensille>
maybe i shouldn't look at the values at once, but with 1 clock distance between them
* ZipCPU
steps away
<sensille>
:)
<sensille>
i'll do that for a while, too, often that helps
bb has joined #yosys
<ZipCPU>
sensille: Sounds like you need to step away from your FPGA for a moment and just run some algorithm simulations
bb has quit [Quit: Leaving]
bb has joined #yosys
rohitksingh has quit [Quit: Leaving.]
<sensille>
i'm currently doing that
<sensille>
i'm even one step farther away, with pencil and paper
<sensille>
(and wolfram alpha)
xerpi has joined #yosys
kuldeep has joined #yosys
<ZipCPU>
sensille: May I ask the method you are using to ensure the transitions from one polynomial to the next are "nice"?
<sensille>
i calculate the polynomial by using value + 2 derivatives at start and end, giving me 6 parameters for 5th order polynomial. so i only need to feed the end values of the previous polynomial as the start values for the next
<ZipCPU>
Are you calculating it like a spline, forcing the various sections to be continuous?
<sensille>
yes
<ZipCPU>
Forcing continuous velocities between the segments as well as continuous accelerations?
<sensille>
exactly
* ZipCPU
tugs at his beard
<qu1j0t3>
hey careful the adhesive is only so strong
<ZipCPU>
qu1j0t3: You crack me up ;)
dxld has quit [Quit: Bye]
dxld has joined #yosys
kuldeep has quit [Read error: Connection reset by peer]
kuldeep has joined #yosys
rohitksingh has joined #yosys
<awygle>
Time frequency uncertainty is super cool
<ZipCPU>
Yep!
<ZipCPU>
awygle: I was surprised at how low the T/F uncertainty was in the Hann window
<ZipCPU>
Because the time uncertainty is so good, the product is nearly ideal
<awygle>
Yup
xerpi has quit [Remote host closed the connection]
xerpi has joined #yosys
kuldeep has quit [Quit: Its never too late!]
kuldeep has joined #yosys
seldridge has joined #yosys
m_t has quit [Read error: Connection reset by peer]
rohitksingh has quit [Quit: Leaving.]
rohitksingh has joined #yosys
emeb has joined #yosys
xerpi has quit [Remote host closed the connection]
xerpi has joined #yosys
emeb has quit [Ping timeout: 252 seconds]
emeb has joined #yosys
seldridge has quit [Ping timeout: 244 seconds]
s_frit has joined #yosys
xerpi has quit [Remote host closed the connection]
ym has joined #yosys
ym has quit [Client Quit]
rohitksingh has quit [Quit: Leaving.]
<sensille>
ZipCPU: more math (please ignore me if i'm boring you): https://pastebin.com/jZMP7K15 if i calculate the steps this way, i'm directly calculating f(x)=ax^5+bx^4+cx^3+dx^2+ex+f, making the transformation easy. but it also looks prohibitively expensive to implent, compared to the current version
<sensille>
(i'm probably just rediscovering basic algebra for me...)
<ZipCPU>
Your irc statement doesn't match the equations you posted./
<sensille>
it does (hopefully), but probably i just don't explain enough
rohitksingh has joined #yosys
<sensille>
each clock increments x by one
<ZipCPU>
No it doesn't, if for no other reason then there are no "x"s in your pastebin post.
<ZipCPU>
Is position = f?
<sensille>
you load a-f into the fpga, and have the value for f(0) in f. each clock executes the block. after n clocks you have f(n) in f
<ZipCPU>
Why would you do it this way?
<sensille>
this way e and d represent velocity and acceleration directly. when i load the next segment, which has identical f, e and d, i only need to load c, b and a
<sensille>
on the above version i need to load e-a
<ZipCPU>
Does your application need and not have any multiplies?
<sensille>
i still think it's cheaper to implement with only additions, but to be sure should implement a version with multiplies
<sensille>
*I should implement
<ZipCPU>
I would agree that its cheaper not to use multiplies, but you may also find the multiplies are simpler to implement since they match the mathematics better.
<ZipCPU>
What hardware are you using again?
<ZipCPU>
ie what FPGA?
<sensille>
artix-7 (which can surely do the multiplies), with the option to go down to hx8k, if possible
<sensille>
otherwise the smallest spartan-6 which fits
<ZipCPU>
'Cause I have a soft multiply generator that works *really* nice on the low logic hx8k's
<ZipCPU>
It's not a 1-clock multiply, but takes roughly 1 clock per resulting bit.
<ZipCPU>
At the same time, if you are working with even timesteps, I can see how just additions might be a better option
<sensille>
and with multiplies, it might be hard to get to 20MHz output rate
<sensille>
i'd need quite a lot of multipliers
<ZipCPU>
Do you need to calculate a new value of 'f' on every clock?
<sensille>
basically yes. i need to decide on each clock whether to advance the stepper or not
<sensille>
anyway, i was just surprised that i managed to bring the additions in a form that they directly model the polynomial
<ZipCPU>
sensille: Here's what I don't get ... I don't see a big difference between your two approaches
<sensille>
in one approach i need to reload all parameters, while in the latter i only need to reload some
<sensille>
it's probably not worth it, though
<ZipCPU>
Why not reload all, but still use the older approach?
emeb has quit [Quit: Leaving.]
<sensille>
i will probably do that, but i was hoping to get around that by changing the algorithm a bit. while that failed, i found the result interesting
rohitksingh has quit [Quit: Leaving.]
seldridge has joined #yosys
seldridge has quit [Ping timeout: 245 seconds]
m_t has joined #yosys
maikmerten has quit [Remote host closed the connection]
seldridge has joined #yosys
dys has quit [Ping timeout: 272 seconds]
seldridge has quit [Ping timeout: 244 seconds]
dys has joined #yosys
azonenberg_work has quit [Ping timeout: 240 seconds]
azonenberg_work has joined #yosys
xerpi has joined #yosys
emeb_mac has joined #yosys
m_t has quit [Read error: Connection reset by peer]
xerpi has quit [Remote host closed the connection]
xerpi has joined #yosys
emeb_mac has quit [Ping timeout: 272 seconds]
emeb_mac has joined #yosys
xerpi has quit [Remote host closed the connection]