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!
Looking for the whitest sequence of 1's and 0's
Started by ●July 6, 2016
Reply by ●July 6, 20162016-07-06
On Wed, 06 Jul 2016 15:59:42 -0500, Tim Wescott <seemywebsite@myfooter.really> 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?Is a PN sequence not sufficient? There are PN generators that will produce very long sequences. Otherwise you can generate random bytes and put an 8b10b code around it to balance DC...although I'm not quite sure what that will do to the spectrum.
Reply by ●July 6, 20162016-07-06
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. What you want instead is to generate random permutations of a vector that is balanced, e.g. [ 0 0 .... 0 1 1 ... 1 ]. There is a random permutation algorithm due to Knuth that is reasonably speedy. Then you would test these results for whiteness. Steve
Reply by ●July 6, 20162016-07-06
On Wed, 06 Jul 2016 23:12:03 +0000, 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. > > What you want instead is to generate random permutations of a vector > that is balanced, e.g. [ 0 0 .... 0 1 1 ... 1 ]. There is a random > permutation algorithm due to Knuth that is reasonably speedy. Then you > would test these results for whiteness. > > SteveThat's what I'm doing. Scilab is cranking away on it at the moment, in fact. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!
Reply by ●July 6, 20162016-07-06
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.
Reply by ●July 6, 20162016-07-06
On Wednesday, July 6, 2016 at 1:59:50 PM UTC-7, Tim Wescott wrote:> 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?There is an algorithm for taking a non-uniform sequence of 0's and 1's, and making a more uniform sequence, though with fewer bits. This allows one to generate uniform random bits from a non-uniform source. But, following random walk, a true random bit sequence, such as flips of a fair coin, of N bits will statistically deviate from equal by sqrt(N). In the limit of N goes to infinity, the Fourier transform will be zero, but I think not for smaller N. Setting N-1 Fourier coefficients to zero, puts N-1 conditions on the bits. Seems to me that leaves only two possible bit sequences.
Reply by ●July 6, 20162016-07-06
On Wednesday, July 6, 2016 at 1:59:50 PM UTC-7, Tim Wescott wrote:> 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.Note that equal 0's and 1's doesn't make the Fourier components zero. -- glen
Reply by ●July 6, 20162016-07-06
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. -- Randy Yates, DSP/Embedded Firmware Developer Digital Signal Labs http://www.digitalsignallabs.com
Reply by ●July 7, 20162016-07-07
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. -- 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
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>>>>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.Well, maximal length sequences only are guaranteed to exist for lengths of the form p^n - 1 for prime p and non-negative integer n. So yes, one can create a balanced sequence of length 2 * (p^n - 1) but the desired vector may not be of such a length. I interpreted Tim's question as applying to vectors of an arbitrary even length.>> 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."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.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
