On 07.07.2016 7:15, Steve Pope wrote:>> This astonished me when I noticed it, so I went and tested >> a bunch of others, and found that perfect whiteness is _not_ >> a general property of maximal length sequences. > > You are saying this is a finite length discrete-time sequence, bipolar > (WLOG its values are from {-1, 1}, and the absolute value of its > Laplace transform is a constant, and it is not the Dirac delta function. > > I would have thought this was impossible. I am astonished as well. > > And I wonder how to construct more such sequences. > > Steve >Steve, I wouldn't rule that out, because a Fourier transform is complex, so each bin has phase, too (not just the absolute value). Moreover, the condition of "whiteness" doesn't impose any restriction on possible arrangements of bin phases. Still doesn't mean anything, just seems a little bit less weird. Gene
Looking for the whitest sequence of 1's and 0's
Started by ●July 6, 2016
Reply by ●July 7, 20162016-07-07
Reply by ●July 7, 20162016-07-07
On Wednesday, July 6, 2016 at 11:12:26 PM UTC-4, Tim Wescott wrote:> > It depends on the sequence. The sequence that is used to generate the > short sequence for CDMA, before 0-stuffing, is perfectly white. This > astonished me when I noticed it, so I went and tested a bunch of others, > and found that perfect whiteness is _not_ a general property of maximal > length sequences. >All M-sequences are spectrally flat (except for DC) as a consequence of their correlation property, namely R(0)=1 and R(n)=1/N 0<n<N where R() is the circular correlation of the bipolar M-sequence. Note that not all LFSR generated sequences are M-sequences.
Reply by ●July 7, 20162016-07-07
On Thursday, July 7, 2016 at 7:05:00 AM UTC-4, lit...@gmail.com wrote:> On Wednesday, July 6, 2016 at 11:12:26 PM UTC-4, Tim Wescott wrote: > > > > It depends on the sequence. The sequence that is used to generate the > > short sequence for CDMA, before 0-stuffing, is perfectly white. This > > astonished me when I noticed it, so I went and tested a bunch of others, > > and found that perfect whiteness is _not_ a general property of maximal > > length sequences. > > > > All M-sequences are spectrally flat (except for DC) as a consequence of their correlation property, namely R(0)=1 and R(n)=1/N 0<n<N where R() is the circular correlation of the bipolar M-sequence. > > Note that not all LFSR generated sequences are M-sequences.Correction: R(0)=1 and R(n) = -1/N 0<n<N Clarification: N is the sequence length
Reply by ●July 7, 20162016-07-07
Tim Wescott <tim@seemywebsite.com> writes:> The sequence that is used to generate the short sequence for CDMA, > before 0-stuffing, is perfectly white.What is the definition of "perfectly white?" I would think it would be R(\tau) = \sigma^2 \delta(\tau), but no MLS sequence has that property as they are periodic. -- Randy Yates, DSP/Embedded Firmware Developer Digital Signal Labs http://www.digitalsignallabs.com
Reply by ●July 7, 20162016-07-07
On Wednesday, July 6, 2016 at 4:59:50 PM UTC-4, Tim Wescott wrote:> No, I'm not suddenly turning racist -- this is about signal processing. > > I want to fill a vector with binary numbers, evenly balanced between ones > and zeros, such that (with the exception of the honkin' big spike at DC) > its FFT is as flat as possible. > > Is there an algorithm for doing this? > > -- > > Tim Wescott > Wescott Design Services > http://www.wescottdesign.com > > I'm looking for work -- see my website!I think m-sequences are what you need: https://en.wikipedia.org/wiki/Maximum_length_sequence#Balance_property They have a dirac delta autocorrelation, balanced number of 1/0s, and are cheap to implement
Reply by ●July 7, 20162016-07-07
On Wednesday, July 6, 2016 at 4:59:50 PM UTC-4, Tim Wescott wrote:> No, I'm not suddenly turning racist -- this is about signal processing. > > I want to fill a vector with binary numbers, evenly balanced between ones > and zeros, such that (with the exception of the honkin' big spike at DC) > its FFT is as flat as possible. > > Is there an algorithm for doing this? >you guys remember Grant Griffen? a couple of decades ago he put this comp.dsp post of mine on his website: http://dspguru.com/dsp/tutorials/a-little-mls-tutorial not that it proves anything new. so we know that if a[n] is a maximum length PN sequence (of 0 and 1), then the autocorrelation of (-1)^a[n] is a kronecker delta function that repeats as often as the MLS repeats (with a very small DC bias). but that does not mean if you construct an W-bit word from those bits, that the binary words would have the same autocorrellation. i wonder what would happen if you took W totally separate MLS generators of the same length, but with totally different primitive polynomials that form the basis of generating the MLS and assign the white output of each to one particular bit of the W-bit word. anyone know? r b-j
Reply by ●July 7, 20162016-07-07
On Thu, 07 Jul 2016 09:07:10 -0400, Randy Yates wrote:> Tim Wescott <tim@seemywebsite.com> writes: > >> The sequence that is used to generate the short sequence for CDMA, >> before 0-stuffing, is perfectly white. > > What is the definition of "perfectly white?" I would think it would be > R(\tau) = \sigma^2 \delta(\tau), but no MLS sequence has that property > as they are periodic.White in an FFT, at least. All these clarifications are making me think I should go back and verify before I get embarrassed. This list needs grad students, to let us senior guys send someone _else_ off to do stuff like this. -- Tim Wescott Control systems, embedded software and circuit design I'm looking for work! See my website if you're interested http://www.wescottdesign.com
Reply by ●July 7, 20162016-07-07
On Wed, 06 Jul 2016 22:12:18 -0500, Tim Wescott <tim@seemywebsite.com> wrote:>On Wed, 06 Jul 2016 22:49:53 -0400, Randy Yates wrote: > >> eric.jacobsen@ieee.org (Eric Jacobsen) writes: >> >>> On Wed, 6 Jul 2016 23:12:03 +0000 (UTC), spope33@speedymail.org (Steve >>> Pope) wrote: >>> >>>>Eric Jacobsen <eric.jacobsen@ieee.org> wrote: >>>> >>>>>On Wed, 06 Jul 2016 15:59:42 -0500, Tim Wescott >>>> >>>>>>I want to fill a vector with binary numbers, evenly balanced between >>>>>>ones and zeros, such that (with the exception of the honkin' big >>>>>>spike at DC) its FFT is as flat as possible. >>>> >>>>>>Is there an algorithm for doing this? >>>> >>>>>Is a PN sequence not sufficient? There are PN generators that will >>>>>produce very long sequences. >>>> >>>>The PN sequence will not automatically balance the numbers of ones and >>>>zeros, and for long vectors the chances of these being balanced for a >>>>randomly selected PN sequence becomes very tiny, thwarting attempts to >>>>find such balanced vectors by means of random search. >>> >>> Actually, all Maximal Length PN sequences are odd length and the number >>> of ones and zeros differ by only 1. One can easily balance the system >>> by transmitting the sequence and then its inverse. >> >> Excellent point, Eric. I wonder how balanced MLS sequences compare with >> permuted vectors in whiteness tests. > >It depends on the sequence. The sequence that is used to generate the >short sequence for CDMA, before 0-stuffing, is perfectly white. This >astonished me when I noticed it, so I went and tested a bunch of others, >and found that perfect whiteness is _not_ a general property of maximal >length sequences. >What is your "perfectly white" specification? As has been mentioned by others, ML sequences have favorable auto-correlation and spectral properties for this sort of thing, and also meet the DC-balance pretty closely, so I'm not sure what's missing. Also, what are your length requirements, since that may narrow the selection candidates down quite a bit?
Reply by ●July 7, 20162016-07-07
On Wednesday, July 6, 2016 at 4:59:50 PM UTC-4, Tim Wescott wrote:> No, I'm not suddenly turning racist -- this is about signal processing. > > I want to fill a vector with binary numbers, evenly balanced between ones > and zeros, such that (with the exception of the honkin' big spike at DC) > its FFT is as flat as possible. > > Is there an algorithm for doing this? > > -- > > Tim Wescott > Wescott Design Services > http://www.wescottdesign.com > > I'm looking for work -- see my website!So cant' you just start from the frequency domain, fill a vector with random phase and constant magnitude and take the inverse? -Mike
Reply by ●July 7, 20162016-07-07
On Thu, 07 Jul 2016 15:58:32 -0700, Michael Shonle wrote:> On Wednesday, July 6, 2016 at 4:59:50 PM UTC-4, Tim Wescott wrote: >> No, I'm not suddenly turning racist -- this is about signal processing. >> >> I want to fill a vector with binary numbers, evenly balanced between >> ones and zeros, such that (with the exception of the honkin' big spike >> at DC) its FFT is as flat as possible. >> >> Is there an algorithm for doing this? >> >> -- >> >> Tim Wescott Wescott Design Services http://www.wescottdesign.com >> >> I'm looking for work -- see my website! > > So cant' you just start from the frequency domain, fill a vector with > random phase and constant magnitude and take the inverse?Yes, but I suspect that when I take the step of turning it into zeros and ones, I won't be happy. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!
