Looking for the whitest sequence of 1's and 0's

ML sequences look perfectly white if the fft length matches the sequence length exactly.  
However, let's say that you make a ML sequence that repeats after an hour with fs=48khz, and you play the 1's and 0's through a speaker. You can't guarantee that 5 minutes of that 1 hour sequence won't sound like the "Star Wars" theme song, while still maintaining "perfect whiteness" when analyzed over the entire 1 hour sequence length. 

Bob

Michael Shonle  <mike.shonle@gmail.com> 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?
>> 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?

You can, but the result would not be bipolar, it would be
real-valued.

Tim states "a vector filled with binary numbers".  (I think he
meant bipolar, or bi-valued, or whatever the correct terminology
du jour is.)

Steve

<lito844@gmail.com> wrote:

>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.

Thanks.

I am going to define "whiteness" as follows.

Suppose a sequence is time-limited and also is non zero only at
values N*T for integers N.  This sequence is white if its Laplace
transform is constant for all frequencies F where F = M*(1/T)
for positive integers M.

Now I need to go back and convince myself that M-sequences satisfy
this.

Steve

On Thu, 07 Jul 2016 17:51:50 -0700, radams2000 wrote:

> ML sequences look perfectly white if the fft length matches the sequence
> length exactly.
> However, let's say that you make a ML sequence that repeats after an
> hour with fs=48khz, and you play the 1's and 0's through a speaker. You
> can't guarantee that 5 minutes of that 1 hour sequence won't sound like
> the "Star Wars" theme song, while still maintaining "perfect whiteness"
> when analyzed over the entire 1 hour sequence length.
> 
> Bob

Could you give me the polynomial for the sequence in question?  I want to 
try it.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

I'm looking for work -- see my website!

On Fri, 8 Jul 2016 02:20:39 +0000 (UTC), spope33@speedymail.org (Steve
Pope) wrote:

>Michael Shonle  <mike.shonle@gmail.com> 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?
>>> 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?
>
>You can, but the result would not be bipolar, it would be
>real-valued.

Only if it is symmetric about DC.   This is easily avoidable.

And real-valued and antipodal and not mutually exclusive.

>Tim states "a vector filled with binary numbers".  (I think he
>meant bipolar, or bi-valued, or whatever the correct terminology
>du jour is.)
>
>Steve

On Thu, 7 Jul 2016 17:51:50 -0700 (PDT), radams2000@gmail.com wrote:

>ML sequences look perfectly white if the fft length matches the sequence le=
>ngth exactly. =20
>However, let's say that you make a ML sequence that repeats after an hour w=
>ith fs=3D48khz, and you play the 1's and 0's through a speaker. You can't g=
>uarantee that 5 minutes of that 1 hour sequence won't sound like the "Star =
>Wars" theme song, while still maintaining "perfect whiteness" when analyzed=
> over the entire 1 hour sequence length.=20
>
>Bob

Absolutely.   This is why the specs matter...it's relatively easy to
make something "white" and "DC balanced" over a specific interval, but
to make it also hold those properties simultaneously over other
intervals gets harder.

On Fri, 08 Jul 2016 02:20:39 +0000, Steve Pope wrote:

> Michael Shonle  <mike.shonle@gmail.com> 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?
>>> 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?
> 
> You can, but the result would not be bipolar, it would be real-valued.
> 
> Tim states "a vector filled with binary numbers".  (I think he meant
> bipolar, or bi-valued, or whatever the correct terminology du jour is.)

That's correct.  Bipolar but not in a medication-needing sort of way.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

I'm looking for work -- see my website!

On Thursday, July 7, 2016 at 8:51:54 PM UTC-4, radam...@gmail.com wrote:
> ML sequences look perfectly white if the fft length matches the sequence length exactly.  
> However, let's say that you make a ML sequence that repeats after an hour with fs=48khz, and you play the 1's and 0's through a speaker. You can't guarantee that 5 minutes of that 1 hour sequence won't sound like the "Star Wars" theme song, while still maintaining "perfect whiteness" when analyzed over the entire 1 hour sequence length. 
> 
> Bob

Here's a quick empircal test to get a feel for the 'whiteness' of small segments of a larger M-sequence.  

The Matlab code below generates a length 2^22-1 (~4.2e6 samples) M-sequence as well as the same length sample of a normal distribution.

For each block of 16k samples compare the circular correlation of each record.  What I observe is that a segment of M-sequence looks very simiar to the same length segment of wgn in terms of correlation.

An easy modification to quantify the difference is to compute a correlation 'SNR' such as the ratio of the max correlation to the next highest value.  With such a metric the M-sequence loses about 2-3dB compared to wgn depending on block size.

% Generator poly: x^22 + x^21 + 1
hpn=comm.PNSequence('Polynomial',[22 21 0],'SamplesPerFrame','2^22-1, ...
'InitialConditions',[zeros(1,21) 1]);

x=(1-2*step(hpn));
n=randn(size(x));

block=2^14;
count=0;
m=count*block;
while m+block<length(x)
  xx=cconv(x(m+1:m+block),x(m+block:-1:m+1),2*block);
  nn=cconv(n(m+1:m+block),n(m+block:-1:m+1),2*block);
  plot([xx nn]);
  title(sprintf('block %d',count));
  disp('pause');
  pause;
  count = count + 1;
  m = count * block;
end;

In article <8f1a3db2-5bc3-4626-8e99-3e42aca6e7be@googlegroups.com>,
 <lito844@gmail.com> wrote:
>On Thursday, July 7, 2016 at 8:51:54 PM UTC-4, radam...@gmail.com wrote:
>> ML sequences look perfectly white if the fft length matches the
>sequence length exactly.  
>> However, let's say that you make a ML sequence that repeats after an
>hour with fs=48khz, and you play the 1's and 0's through a speaker. You
>can't guarantee that 5 minutes of that 1 hour sequence won't sound like
>the "Star Wars" theme song, while still maintaining "perfect whiteness"
>when analyzed over the entire 1 hour sequence length. 
>> 
>> Bob
>
>Here's a quick empircal test to get a feel for the 'whiteness' of small
>segments of a larger M-sequence.  
>
>The Matlab code below generates a length 2^22-1 (~4.2e6 samples)
>M-sequence as well as the same length sample of a normal distribution.

How do you know this is an M-sequence?  (Just wondering.)

Steve

On Friday, July 8, 2016 at 11:00:50 AM UTC-4, Steve Pope wrote:
> >M-sequence as well as the same length sample of a normal distribution.
> 
> How do you know this is an M-sequence?  (Just wondering.)
> 
> Steve

Source: Horowitz & Hill "The Art of Electronics" Cambridge University Press

There's a chapter entitled Pseudo-Random Bit Sequences and Noise Generation which includes a table of taps (generator polynomials) for maximal length sequences.  Chapter number varies depending on edition.

For degree m polynomial some taps they provide are listed below:

m   n
3   2
4   3
5   3
6   5
7   6
9   5
10  7
11  9
15  14
17  14
18  11
20  17
21  19
22  21
23  18
25  22
28  25
29  27
31  28