Forum: GNU Radio Re: Correct method for "compressing" a power spectrum

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Firas A. (Guest)
on 2009-03-09 08:38
(Received via mailing list)
Hi,


> From: Marcus D. Leech <removed_email_address@domain.invalid>
>
> Let's say I have an FFT output that's  many, many, bins wide, and I want
> to compress that information into a narrower display (let's say from 4M > bins down to 
1024 bins).
>
> My approach has been to sum up each set of [4M/1024] bins, and use that
> as the final output. 
>
> Marcus L.

I think adding FFT bins is the correct way. But, for me I always select
the maximum in these bins. I'm not sure that this is right but it gives
me a good look over my spectrum data.


Best Regards,

Firas
Jens E. (Guest)
on 2009-03-09 09:46
(Received via mailing list)
> I think adding FFT bins is the correct way. But, for me I always select the maximum in 
these bins. I'm not sure that this is right but it gives me a good look over my spectrum 
data.
Spectrum Estimation is not trivial - I highly recommend having a look at
"Introduction to Spectral Analysis" by Stoica and Moses. A mathematical
yet readable introduction.

To solve you problem in a mathematically way, you can use windowing
in the time domain with subsequent overlapping block averaging
(Welch's method).

Gives a good practical estimate. Code for GNU Radio is here:

https://www.cgran.org/wiki/SpecEst

Integrating the FFT bins is just fine, but you probably loose frequency
resolution that way (if that doesn't matter, just leave it).

Best regards,
Jens
Brian P. (Guest)
on 2009-03-09 15:01
(Received via mailing list)
On Mon, Mar 9, 2009 at 3:45 AM, Jens E. <removed_email_address@domain.invalid> 
wrote:
> Gives a good practical estimate. Code for GNU Radio is here:
>
> https://www.cgran.org/wiki/SpecEst

Good to see CGRAN being put to good use!

> Integrating the FFT bins is just fine, but you probably loose frequency
> resolution that way (if that doesn't matter, just leave it).

As per the original question, I am wondering what the reason for
taking the time to do a 4M point FFT and then compressing the
frequency information?  I would think you're just throwing away
frequency resolution at that point and, inherently, wasting CPU
cycles.

So - back to Marcus - what is the overall goal of "compressing" your
FFT data?  I have a feeling it's for visualization of your data as
opposed to actually performing math or computational analysis, right?

If that is the case, I think you would want to come up with a clever
way of visually compressing the original data without compromising the
frequency resolution you're computing.  I'm not sure if anyone has
done this before, but you could possibly overlay your lines on top of
each other - and use colors to determine how many of the bins overlap
- this way if you have a spike in one bin, it will be instantly
recognizable and "zooming in" could reveal exactly which bin it was.
Moreover, if all the bins have a large frequency content to them,
that, too, would be instant recognizable as a wider bandwidth signal
as opposed to just a single Hz spike.

I suppose this would constitute a visual averaging without
computationally losing the frequency resolution you've worked so hard
to achieve.

If it is not the case that you want to visualize the data, and,
indeed, you just need to clump your bins together - please disregard
this entire e-mail and idea.

Brian
John Ackermann N8UR (Guest)
on 2009-03-09 15:26
(Received via mailing list)
One thing you might look at is the "Rosenfell" algorithm used in some HP
spectrum analyzers (like the 8566).  As I recall, they alternately take
the maximum and minimum values in the bins -- ie, if you're collapsing
three bins into one and the original values are

010 050 010|010 050 010|120 130 120|120 130 120|010 050 010|010 050 010

You'd end up with

050 010 130 120 050 010

The idea is that this looks more like the "grass" that you would see on
a non-digital analyzer and accentuates the difference between noise and
stable signal, where averaging the bins would lose that distinction --
it has the effect of removing indicators that you're looking at noise.

Not sure if this might be applicable to the application, and not sure I
got the details just right from memory, but I think searching
"Rosenfell" would find more details.

John
Marcus D. Leech (Guest)
on 2009-03-09 15:50
(Received via mailing list)
Brian P. wrote:
> opposed to actually performing math or computational analysis, right?
>
The original {1,2,4,8,16}M-bin data are used for SETI analysis, while
the "compressed" version
  is used for a quick visual, "conventional" spectral display.


--
Marcus L.
Principal Investigator, Shirleys Bay Radio Astronomy Consortium
http://www.sbrac.org
Brian P. (Guest)
on 2009-03-09 16:29
(Received via mailing list)
On Mon, Mar 9, 2009 at 8:47 AM, Marcus D. Leech 
<removed_email_address@domain.invalid>
wrote:
> The original {1,2,4,8,16}M-bin data are used for SETI analysis, while
> the "compressed" version
>  is used for a quick visual, "conventional" spectral display.

In SETI analysis, is it more interesting to see a wider bandwidth
signal, or single frequency bins of larger magnitudes?

If you would rather see wider bandwidths, it might be interesting to
set each of N bins to an opacity of 1/N and draw them on top of each
other.  That way the more that are drawn on top of each other appear
darker in appearance (wider bandwidth) as opposed to a single outlier
skewing all results.  Moreover, for zooming, I think this would be the
most dynamic while maintaining full fidelity of the signal
representation.

I think there are a lot of good visualizations that can be done
without compromising the frequency resolution you have obtained with
such large FFTs.

I'd be interested to hear what method you end up using, and what is
important in your SETI analysis.

Brian
Bob McGwier (Guest)
on 2009-03-09 17:52
(Received via mailing list)
I suggest that the best algorithm for this would be the rank order mean
alternated with the max so long as you are going to insert "heuristic
grass".  So it would be max, ROM, max, ROM, .....


Let [B1, B2, B3, B4, ... BN]  be powers of five adjacent bins.

Put them in rank order

[R1, R2, R3, R4,  ... RN]

If N is even,  the rank order mean is (R_(N/2) + R_/(N/2 +1)*0.5.
If N is odd,  the rank order mean is R_(N/2 +0.5)

But I still see a problem:

I suggest that in order to prevent "scalloping" of a swept tone across
this algorithm or any other like it,  that some "bin"  in the lossy
compression set of bins must ALWAYS be forced to take on the large of
the power spectrum otherwise your alternative min/max/min/max might jump
up and down as you sweep a tone through it.  Or did I miss something?

Bob

John Ackermann N8UR wrote:
>
> John
>
>
> _______________________________________________
> Discuss-gnuradio mailing list
> removed_email_address@domain.invalid
> http://lists.gnu.org/mailman/listinfo/discuss-gnuradio
>


--
(Co)Author: DttSP, Quiktrak, PowerSDR, GnuRadio
Member: ARRL, AMSAT, AMSAT-DL, TAPR, Packrats,
NJQRP, QRP ARCI, QCWA, FRC.
"It is human nature to think wisely and act in
an absurd fashion.", Anatole France.
Twitter:rwmcgwier
Active: Facebook,Myspace,LinkedIn
Frank B. (Guest)
on 2009-03-09 18:10
(Received via mailing list)
On Mon, Mar 9, 2009 at 8:49 AM, Bob McGwier 
<removed_email_address@domain.invalid> wrote:


> Let [B1, B2, B3, B4, ... BN]  be powers of five adjacent bins.
>
> Put them in rank order
>
> [R1, R2, R3, R4,  ... RN]
>
> If N is even,  the rank order mean is (R_(N/2) + R_/(N/2 +1))*0.5.
> If N is odd,  the rank order mean is R_(N/2 +0.5)


Here the rank-order mean *is* the median: the quantile value for
#quantiles
= 2.


> But I still see a problem:
>
> I suggest that in order to prevent "scalloping" of a swept tone across this
> algorithm or any other like it,  that some "bin"  in the lossy compression
> set of bins must ALWAYS be forced to take on the large of the power spectrum
> otherwise your alternative min/max/min/max might jump up and down as you
> sweep a tone through it.  Or did I miss something?


Most surely. Why not some kind of VQ-codebook based on deltas between
successive frames? Apart from the amount of the research required to
build
it, of course...

Neural net fans invited to take this on also! ;-)

Frank
Marcus D. Leech (Guest)
on 2009-03-09 18:20
(Received via mailing list)
Brian P. wrote:
> On Mon, Mar 9, 2009 at 8:47 AM, Marcus D. Leech <removed_email_address@domain.invalid> 
wrote:
>
>> The original {1,2,4,8,16}M-bin data are used for SETI analysis, while
>> the "compressed" version
>>  is used for a quick visual, "conventional" spectral display.
>>
>
> In SETI analysis, is it more interesting to see a wider bandwidth
> signal, or single frequency bins of larger magnitudes?
>
Ah, the very crux of the signal-detection arguments in SETI!   The most
popular hypothesis is
  that our ET friends will use as narrow a signal as possible, since
that concentrates all the transmitter
  power over a single frequency.  But there are other theories around
about what else ET might
  do to let us know that they're there.  Modulating the microwave output
of the stellar corona, for example
  (See SASER project).   Something like that would be wideband, and not
terribly coherent.
> such large FFTs.
>
> I'd be interested to hear what method you end up using, and what is
> important in your SETI analysis.
>
I have two different "visualizations" available.   The "compressed"
spectrum is all about the "usual"
  fairly-coarse spectrum you might want for mapping radial velocities of
neutral hydrogen, for example.
  The full-resolution spectrum is used both for automated analysis, with
a companion visualizer using
  a completely-conventional "waterfall" display, in which you can
display any given segment with
  full resolution.

At very high resolutions, these waterfall plots produce some fairly
spectacular-looking stuff particularly
  when the low-noise feed is sitting in an office full of computers,
pointing at the ceiling.

--
Marcus L.
Principal Investigator, Shirleys Bay Radio Astronomy Consortium
http://www.sbrac.org
Marcus D. Leech (Guest)
on 2009-03-09 18:28
(Received via mailing list)
Bob McGwier wrote:
> [R1, R2, R3, R4,  ... RN]
> jump up and down as you sweep a tone through it.  Or did I miss
> something?
>
> Bob
I love that phrase, Bob.   "Heuristic grass".

I think that the real answer is to "play with it, and see what best
suits the application".   Ranking the bin might end up being
  expensive.  I'd probably use qsort(),  but I can't remember what its
computational complexity is. Just looked it up.  Worst case
  is O(N**2), and best-case is O(NlogN).   For worst-case, that's rather
brutal at 4M bins (and even worse at my maximum of
  16M bins).

This discussion has ended up being much more fascinating than I had
predicted.   Keep it up everybody!

--
Marcus L.
Principal Investigator, Shirleys Bay Radio Astronomy Consortium
http://www.sbrac.org
Bob McGwier (Guest)
on 2009-03-09 22:34
(Received via mailing list)
Franks comments are right on median and ROM in this case.    I stayed up
to 4 AM and went to work at  after having breakfast and a cup of coffee
and arrived by 9.  It is showing.

The entire gist of my comments amount to nothing more than don't allow
"aliasing" of the spectral changes as your traverse the compressed power
spectrum to cause you to miss a peak that is ABOVE the detection
threshold.


So,  pardon me but,  is this a pretty picture exercise or a real
detection problem?  If it is a detection problem,  then you might as
well just compress to the largest value in the bins to be pushed
together so you assure that your threshold is exceeded when it should
be.  If it is a pretty picture problem,  just prevent scalloping by any
old heuristic, just make it as fleet of calculation feet as possible and
throw in some pretty grassy stuff to make it look nice.

Bob



Marcus D. Leech wrote:
>>
>> the power spectrum otherwise your alternative min/max/min/max might
> computational complexity is. Just looked it up.  Worst case
>   is O(N**2), and best-case is O(NlogN).   For worst-case, that's rather
> brutal at 4M bins (and even worse at my maximum of
>   16M bins).
>
> This discussion has ended up being much more fascinating than I had
> predicted.   Keep it up everybody!
>
>


--
(Co)Author: DttSP, Quiktrak, PowerSDR, GnuRadio
Member: ARRL, AMSAT, AMSAT-DL, TAPR, Packrats,
NJQRP, QRP ARCI, QCWA, FRC.
"It is human nature to think wisely and act in
an absurd fashion.", Anatole France.
Twitter:rwmcgwier
Active: Facebook,Myspace,LinkedIn
Marcus D. Leech (Guest)
on 2009-03-10 01:06
(Received via mailing list)
Bob McGwier wrote:
> Franks comments are right on median and ROM in this case.    I stayed
> up to 4 AM and went to work at  after having breakfast and a cup of
> coffee and arrived by 9.  It is showing.
>
> The entire gist of my comments amount to nothing more than don't allow
> "aliasing" of the spectral changes as your traverse the compressed
> power spectrum to cause you to miss a peak that is ABOVE the detection
> threshold.
>
The detection algorithm works on the full-resolution FFT output (several
million bins), but for purposes of having
  an "overview" to look at, it needs to be compressed.


--
Marcus L.
Principal Investigator, Shirleys Bay Radio Astronomy Consortium
http://www.sbrac.org
Frank B. (Guest)
on 2009-03-10 01:44
(Received via mailing list)
On Mon, Mar 9, 2009 at 1:08 PM, Bob McGwier 
<removed_email_address@domain.invalid> wrote:


> So,  pardon me but,  is this a pretty picture exercise or a real detection
> problem?  If it is a detection problem,  then you might as well just
> compress to the largest value in the bins to be pushed together so you
> assure that your threshold is exceeded when it should be.  If it is a pretty
> picture problem,  just prevent scalloping by any old heuristic, just make it
> as fleet of calculation feet as possible and throw in some pretty grassy
> stuff to make it look nice.


Amen to that.

To say so is not to dismiss the level of art required by heuristic
grass,
however. That's pretty much what MELP adds, and it makes a world of
difference to the user.

Frank
unknown (Guest)
on 2009-03-10 18:40
(Received via mailing list)
Oh horrors. Please let it not be true that the phrase I am remembered
most
for is heuristic grass.

Your comments about MELP were insightful and now that you have said it,
more becomes crystal clear. I raise another absinthe in your honor ....
or
was that dishonor.


On Mar 9, 2009 6:49pm, Frank B. <removed_email_address@domain.invalid> wrote:
> On Mon, Mar 9, 2009 at 1:08 PM, Bob McGwier removed_email_address@domain.invalid> wrote:



> So, pardon me but, is this a pretty picture exercise or a real detection
> problem? If it is a detection problem, then you might as well just
> compress to the largest value in the bins to be pushed together so you
> assure that your threshold is exceeded when it should be. If it is a
> pretty picture problem, just prevent scalloping by any old heuristic,
> just make it as fleet of calculation feet as possible and throw in some
> pretty grassy stuff to make it look nice.

> Amen to that.

> To say so is not to dismiss the level of art required by heuristic grass,
> however. That's pretty much what MELP adds, and it makes a world of
> difference to the user.
Frank B. (Guest)
on 2009-03-10 18:47
(Received via mailing list)
On Tue, Mar 10, 2009 at 9:39 AM, <removed_email_address@domain.invalid> wrote:

Oh horrors. Please let it not be true that the phrase I am remembered
most
> for is heuristic grass.


Isn't heuristic grass what gives absinthe the green color?

Frank
Marcus D. Leech (Guest)
on 2009-03-10 18:51
(Received via mailing list)
removed_email_address@domain.invalid wrote:
> Oh horrors. Please let it not be true that the phrase I am remembered
> most for is heuristic grass.
>
I'm near-certain that you've said more memorable things than that,
Bob.   But that's the one that is proximate right now :-)


--
Marcus L.
Principal Investigator, Shirleys Bay Radio Astronomy Consortium
http://www.sbrac.org
John Ackermann N8UR (Guest)
on 2009-03-10 19:03
(Received via mailing list)
Frank B. wrote:
> On Tue, Mar 10, 2009 at 9:39 AM, <removed_email_address@domain.invalid
> <mailto:removed_email_address@domain.invalid>> wrote:
>
>     Oh horrors. Please let it not be true that the phrase I am
>     remembered most for is heuristic grass.
>
>
> Isn't heuristic grass what gives absinthe the green color?

Just remember -- absinthe makes the tart grow blonder.

John
Marcus D. Leech (Guest)
on 2009-03-10 19:16
(Received via mailing list)
John Ackermann N8UR wrote:
>
> Just remember -- absinthe makes the tart grow blonder.
>
> John
>
You clearly know a more interesting class of tart than I do :-)

--
Marcus L.
Principal Investigator, Shirleys Bay Radio Astronomy Consortium
http://www.sbrac.org
Frank B. (Guest)
on 2009-03-10 19:26
(Received via mailing list)
On Tue, Mar 10, 2009 at 10:02 AM, John Ackermann N8UR 
<removed_email_address@domain.invalid>
wrote:


> Just remember -- absinthe makes the tart grow blonder.


Sigh. With fronds like these, who needs anemones?

(Sorry -- done now.)

Frank
Marcus D. Leech (Guest)
on 2009-03-10 20:12
(Received via mailing list)
Frank B. wrote:
>
> --
> For an omnipotent and omniscient being, God has made some really lousy
> earthly staffing decisions. -- John Cole
OK, so I decided to use the averaging method, rather than the maximum
method.  It produces reasonably good looking plots:

http://www.science-radio-labs.com/files/spectral_example.ps

(The GUI toolkit I'm using allows you to take a PostScript dump of the
XYPlot object).

--
Marcus L.
Principal Investigator, Shirleys Bay Radio Astronomy Consortium
http://www.sbrac.org
Frank B. (Guest)
on 2009-03-10 20:27
(Received via mailing list)
On Tue, Mar 10, 2009 at 11:10 AM, Marcus D. Leech 
<removed_email_address@domain.invalid>
wrote:


> OK, so I decided to use the averaging method, rather than the maximum
> method.  It produces reasonably good looking plots:
>
> http://www.science-radio-labs.com/files/spectral_example.ps


True, not bad. One surprise, though -- what's that notch around 1420.5?

It definitely has an "averaged" look to it -- much like what you'd
expect
from time smoothing and not frequency necessarily. One thing that
low-level
heuristic grass might give you is a feeling that the relatively flat
segments are alive at least, sort of like comfort noise during vocoder
silence. If that matters.

Frank
Marcus D. Leech (Guest)
on 2009-03-10 20:45
(Received via mailing list)
Frank B. wrote:
>
>
> --
> For an omnipotent and omniscient being, God has made some really lousy
> earthly staffing decisions. -- John Cole
The Fc is 1420.4058e6Hz, and since it's a direct-conversion receiver,
there's always a little spectral artifact near DC.

--
Marcus L.
Principal Investigator, Shirleys Bay Radio Astronomy Consortium
http://www.sbrac.org
Marcus D. Leech (Guest)
on 2009-03-10 20:50
(Received via mailing list)
Frank B. wrote:
>
>
This is averaged both in frequency, and time.   Each bin is smoothed
with an integrator--needed for doing astronomical work, like
  showing the HI line, etc.  The HI line is strong in relative terms,
but in absolute terms, it's terribly weak :-(


--
Marcus L.
Principal Investigator, Shirleys Bay Radio Astronomy Consortium
http://www.sbrac.org
Firas A. (Guest)
on 2009-03-10 20:53
(Received via mailing list)
Hi,

> From: Marcus D. Leech <removed_email_address@domain.invalid>
> OK, so I decided to use the averaging method, rather than
> the maximum
> method.  It produces reasonably good looking plots:
> Marcus L.

Can you post a link to what you saw by the maximum method ?

Best Regards,

Firas
Marcus D. Leech (Guest)
on 2009-03-10 21:37
(Received via mailing list)
Firas A. wrote:
> Can you post a link to what you saw by the maximum method ?
>
> Best Regards,
>
> Firas
>
>
I think what I'll do is have an option in the spectrum window that
selects the compression method.  Once I have that done, I'll
  post results.

Cheers

--
Marcus L.
Principal Investigator, Shirleys Bay Radio Astronomy Consortium
http://www.sbrac.org
Marcus D. Leech (Guest)
on 2009-03-10 22:18
(Received via mailing list)
Firas A. wrote:
> Can you post a link to what you saw by the maximum method ?
>
> Best Regards,
>
> Firas
>
>
This is using the "max" method, at the same resolution and scale as the
average method:

http://www.radio-science-labs.com/files/spectrum_e...



--
Marcus L.
Principal Investigator, Shirleys Bay Radio Astronomy Consortium
http://www.sbrac.org
This topic is locked and can not be replied to.