Clay wrote:> On Oct 28, 9:00 am, dvsarwate <dvsarw...@yahoo.com> wrote: > >>On Oct 28, 6:44 am, Vladimir Vassilevsky <nos...@nowhere.com> >>commented: >> >> >>>Incredible observation. How about 2 x 2 = 4 ? >> >>Well, that one requires higher math and is worth >>noting. I only got as far as 2 + 2 = 4 in my studies. >>:-) > > > A better one is Oct 31 = Dec 25A 1-st April joke can result in the New year gift. VLV
An efficient storage scheme for Fourier data
Started by ●October 27, 2010
Reply by ●October 28, 20102010-10-28
Reply by ●October 28, 20102010-10-28
On 10/27/2010 10:53 PM, brent wrote:> On Oct 28, 12:00 am, Tim Wescott<t...@seemywebsite.com> wrote: >> On 10/27/2010 07:03 PM, Bryan wrote: >> >> >> >>> On Oct 27, 4:11 pm, Sebastian Garth<sebastianga...@gmail.com> wrote: >>>> The fourier transform (FT), of course, maps a real signal to the >>>> complex plane. Unfortunately, this also means that the result is twice >>>> as large as the original signal. As it turns out, though, fully half >>>> of that information is completely redundant! Let's see how this is >>>> possible. Suppose we are working with a signal containing 8 samples. >>>> After performing the FT, we see a pattern emerge: >> >>>> Reals: >>>> [W][A][B][C][X][C][B][A] >> >>>> Imaginaries: >>>> [Y][D][E][F][Z][-F][-E][-D] >> >>>> Notice how all of the coefficients straddling X are "reflections" of >>>> eachother, and those of Z are "negative reflections". Also note that Y >>>> and Z are *always* zero (or extremely close to it). In other words, >>>> all we really need to reconstruct the two planes are: >> >>>> Composite: >>>> [W][A][B][C][X][-F][-E][-D] >> >>>> Translated to C: >> >>>> Code: >> >>>> int is_power_of_two( int n ) >>>> { >>>> int >>>> bits = 0; >>>> while( n ) >>>> { >>>> if( n& 1 ) >>>> ++bits; >>>> n>>= 1; >>>> } >>>> return bits == 1; >> >>>> } >> >>>> void compress_fft_result( const double reals[ ], const double >>>> imags[ ], double composite[ ], int size ) >>>> { >>>> if( !is_power_of_two( size ) ) >>>> return; >>>> for( int idx = 0, mid = size>> 1; idx< size; ++idx ) >>>> { >>>> if( idx<= mid ) >>>> composite[ idx ] = reals[ idx ]; >>>> else >>>> composite[ idx ] = imags[ idx ]; >>>> } >> >>>> } >> >>>> void decompress_fft_result( const double composite[ ], double >>>> reals[ ], double imags[ ], int size ) >>>> { >>>> if( !is_power_of_two( size ) ) >>>> return; >>>> int >>>> mid = size>> 1; >>>> for( int idx = 0; idx< size; ++idx ) >>>> { >>>> if( idx<= mid ) >>>> { >>>> reals[ idx ] = composite[ idx ]; >>>> imags[ idx ] = -composite[ mid + ( mid - idx ) ]; >>>> } >>>> else >>>> { >>>> reals[ idx ] = composite[ mid - ( idx - mid ) ]; >>>> imags[ idx ] = composite[ idx ]; >>>> } >>>> } >>>> imags[ 0 ] = imags[ mid ] = 0; >> >>>> } >> >>>> The only constraint, of course, it that the sample size must be a >>>> power of two. >> >>>> Cheers! >> >>> These are basic properties of the Fourier transform. And you forgot >>> the constraint that the input be purely real, otherwise the DC offset >>> may not be zero and the "redundancy" (it's called Hermitian symmetry) >>> no longer holds. >> >> And the fact that with all real inputs you can speed the algorithm up a bit. >> >> -- >> >> Tim Wescott >> Wescott Design Serviceshttp://www.wescottdesign.com >> >> Do you need to implement control loops in software? >> "Applied Control Theory for Embedded Systems" was written for you. >> See details athttp://www.wescottdesign.com/actfes/actfes.html > > When I first messed with this stuff I thought "Well all inputs will be > real" Then I realized that if you have an I/Q data stream you are > processing that it is not true, and also if you have an inverse FFT > you want to perform you have to deal with imaginary numbers, although > when deling with an inverse FFT you can still get the processing > advantages back in reverse, but you still are dealing with a complex > input.I was specifically referring to the situation cited by the OP. Indeed, different situations are different. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" was written for you. See details at http://www.wescottdesign.com/actfes/actfes.html
