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!
An efficient storage scheme for Fourier data
Started by ●October 27, 2010
Reply by ●October 27, 20102010-10-27
On Oct 27, 7: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!Wow, this is breathtaking.
Reply by ●October 27, 20102010-10-27
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.
Reply by ●October 27, 20102010-10-27
On Oct 27, 9:01�pm, John <sampson...@gmail.com> wrote:> On Oct 27, 7: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! > > Wow, this is breathtaking.Some how you made me laugh. I saw his name and wanted to just say ---- Garth Tator
Reply by ●October 28, 20102010-10-28
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 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
Reply by ●October 28, 20102010-10-28
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.htmlWhen 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.
Reply by ●October 28, 20102010-10-28
Sebastian Garth 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!Incredible observation. How about 2 x 2 = 4 ? VLV
Reply by ●October 28, 20102010-10-28
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. :-)
Reply by ●October 28, 20102010-10-28
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 25 Clay
Reply by ●October 28, 20102010-10-28
On Oct 28, 6:44�am, Vladimir Vassilevsky <nos...@nowhere.com> wrote:> Sebastian Garth 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! > > Incredible observation. How about 2 x 2 = 4 ? > > VLVOkay, fair enough. I was just thinking out loud...disregard!
