From: cd@lri.fr (Charles Delorme)
Newsgroups: sci.nonlinear,sci.math
Subject: Re: Bit sequences
Date: 23 Oct 1996 07:50:51 GMT
In article <326D8176.1259@gibbs.ucsd.edu>, "Misha (Mikhail) Sushchik"
writes:
|> From: "Misha (Mikhail) Sushchik"
|> Newsgroups: sci.nonlinear,sci.math
|> Subject: Bit sequences
|> Date: Tue, 22 Oct 1996 19:22:46 -0700
|> Organization: UCSD,INLS,RPI,ANSLLC
|> NNTP-Posting-Host: sdts2-44.znet.com
|> Mime-Version: 1.0
|> Content-Type: text/plain; charset=us-ascii
|> Content-Transfer-Encoding: 7bit
|> X-Mailer: Mozilla 2.02 (WinNT; I)
|>
|> I have a problem and so far I could not come up
|> with a solution. Maybe someone had seen something
|> like this before.
|>
|> Consider a bit sequence:
|>
|> 1010001010101000101010101010100110100101.....
|>
|> I select N-bit words from this sequence according
|> to the rule:
|>
|> b1,b2,b3,b4,...bN
|> b2,b3,b4,b5,...b(N+1)
|> .......
|> where b1 is the first bit in the sequence, b2 is
|> the second and so forth.
|>
|> I want to construct the *shortest* bit sequence
|> from which I could get all possible N-bit words,
|> if I use the rule shown above. How can I do this?
|>
|> Thanks everybody who gives this a thought.
|>
|> M. Sushchik
This problem has been solved by N. G. de Bruijn in 1946;
here is a reference
N. G. de Bruijn, A combinatorial problem,
Koninglijke Nederland Akademie van Wetenschappen ser A
vol. 49 1946
p. 758-764
--
Charles Delorme tous les megalomanes
LRI ont une signature
cd@lri.lri.fr a etages
==============================================================================
Newsgroups: sci.nonlinear,sci.math
From: matthew g hudelson
Subject: Re: Bit sequences
Date: Thu, 24 Oct 1996 17:07:07 GMT
On Thu, 24 Oct 1996, matthew b charlap apmt stnt wrote:
> In article <326D8176.1259@gibbs.ucsd.edu>,
> Misha (Mikhail) Sushchik wrote:
> >I have a problem and so far I could not come up
> >with a solution. Maybe someone had seen something
> >like this before.
> >
> >Consider a bit sequence:
> >
> >1010001010101000101010101010100110100101.....
> >
> >I select N-bit words from this sequence according
> >to the rule:
> >
> >b1,b2,b3,b4,...bN
> >b2,b3,b4,b5,...b(N+1)
> >.......
> >where b1 is the first bit in the sequence, b2 is
> >the second and so forth.
> >
> >I want to construct the *shortest* bit sequence
> >from which I could get all possible N-bit words,
> >if I use the rule shown above. How can I do this?
> >
> >Thanks everybody who gives this a thought.
> >
> > M. Sushchik
>
> A good first try would probably be some sort of induction scheme. I have
> an idea of the answer, but now way to prove it:
>
> case : N=1
> solution: 01
> N=2:
> solution (there are multiple answers, this is 1): 01100
>
> at a first guess, I would think the minimum number of characters (bits)
> would work (i.e. length=2^N+(N-1))- this is the smallest length that
> could possibly have all bit strings of length N. you may want to try to
> explicitly solve for N=3,4, and maybe 5 (since the strings are fairly short
> up to here), and maybe see if you can find a pattern.
> N=3: 1110001011 (note: this is 10 bits=2^3+(3-1))
> If my conjecture is true, N=4 should have a minimum length of 19, and N=5
> should have length=36. These are still small enough to try to verify. As for
> how to prove this- I have no idea.
>
> --Matthew
>
>
Such sequences exist and are described in section 10.5 ofBondy and Murty's
Graph Theory with Applications. There, they describe a circular
"efficient computer drum" with 2^n sections containing the bits of a
circular sequence which contains all 2^n binary words of length n on
adjacent bits. This is ultimately related to finding Eulerian cycles on
members of a special class of digraphs, each vertex having in-degree and
out-degree equal to two.
-- Matt Hudelson
==============================================================================
From: Doug Moore
Newsgroups: sci.math
Subject: Re: Bit sequences
Date: Thu, 24 Oct 1996 14:24:29 -0500
matthew b charlap apmt stnt wrote:
>
> In article <326D8176.1259@gibbs.ucsd.edu>,
> Misha (Mikhail) Sushchik wrote:
> >
> >Consider a bit sequence:
> >
> >1010001010101000101010101010100110100101.....
> >
> >I select N-bit words from this sequence according
> >to the rule:
> >
> >b1,b2,b3,b4,...bN
> >b2,b3,b4,b5,...b(N+1)
> >.......
> >where b1 is the first bit in the sequence, b2 is
> >the second and so forth.
> >
> >I want to construct the *shortest* bit sequence
> >from which I could get all possible N-bit words,
>
A bit sequence of length 2**N+N-1 can do this, if you generate it using
polynomial arithmetic over GF(2). Pick a primitive polynomial f(x) of
degree N. Generate
x**p mod F(x)
for p = 1 up to 2**N + N - 2. The coefficients of the low order terms
of the expressions x**p mod F(x) form the bit sequence you want,
excepting that there is no sequence of N consecutive zeroes. Add a zero
at the end and you've got it.
Example: N=4
F(x) = x**4 + X + 1
coefficients of
p x**p mod F(x)
1 0010
2 0100
3 1000
4 0011
5 0110
6 1100
7 1011
8 0101
9 1010
10 0111
11 1110
12 1111
13 1101
14 1001
15 0001
16 0010
17 0100
18 1000
The resulting bit pattern:
0001001101011110000
Does what you want.
--
Doug Moore
Research Scientist/Lecturer
Computer Science/Computational and Applied Math
(dougm@rice.edu)
==============================================================================
From: mbrundag@cco.caltech.edu (Michael L. Brundage)
Newsgroups: sci.nonlinear,sci.math
Subject: Re: Bit sequences
Date: 26 Oct 1996 03:19:34 GMT
matthew g hudelson writes:
>> In article <326D8176.1259@gibbs.ucsd.edu>,
>> Misha (Mikhail) Sushchik wrote:
>> >I have a problem and so far I could not come up
>> >with a solution. Maybe someone had seen something
>> >like this before.
>> >
>> >Consider a bit sequence:
>> >
>> >1010001010101000101010101010100110100101.....
>> >
>> >I select N-bit words from this sequence according
>> >to the rule:
>> >
>> >b1,b2,b3,b4,...bN
>> >b2,b3,b4,b5,...b(N+1)
>> >.......
>> >where b1 is the first bit in the sequence, b2 is
>> >the second and so forth.
>> >
>> >I want to construct the *shortest* bit sequence
>> >from which I could get all possible N-bit words,
>> >if I use the rule shown above. How can I do this?
>> >
>Such sequences exist and are described in section 10.5 ofBondy and Murty's
>Graph Theory with Applications. There, they describe a circular
>"efficient computer drum" with 2^n sections containing the bits of a
>circular sequence which contains all 2^n binary words of length n on
>adjacent bits. This is ultimately related to finding Eulerian cycles on
>members of a special class of digraphs, each vertex having in-degree and
>out-degree equal to two.
They are also described in Wilson and Van Lint's recent combinatorics book,
which has the advantages over Bondy and Murty of being both widely available
(the local Barnes & Noble carries it; Bondy and Murty is out of print) and
more current.
Cheers,
michael
brundage@ipac.caltech.edu
[P.S. Hi Matt!]
==============================================================================
From: truman.prevatt@netsqr.com (Truman Prevatt)
Newsgroups: sci.nonlinear,sci.math
Subject: Re: Bit sequences
Date: Wed, 30 Oct 1996 16:33:33 -0500
In article <54m7sb$4pe@news.dgsys.com>, qnd@dgsys.com (Randy Poe) wrote:
See - Robert McEliece, "Finite Fields for Computer Scientists and Engineers"
Kluwer Academic Publishers , 1987
> In article <326D8176.1259@gibbs.ucsd.edu>, mick@gibbs.ucsd.edu says...
> >
> >I have a problem and so far I could not come up
> >with a solution. Maybe someone had seen something
> >like this before.
> >
> >Consider a bit sequence:
> >
> >1010001010101000101010101010100110100101.....
> >
> >I select N-bit words from this sequence according
> >to the rule:
> >
> >b1,b2,b3,b4,...bN
> >b2,b3,b4,b5,...b(N+1)
> >.......
> >where b1 is the first bit in the sequence, b2 is
> >the second and so forth.
> >
> >I want to construct the *shortest* bit sequence
> >from which I could get all possible N-bit words,
> >if I use the rule shown above. How can I do this?
> >
>
> There are shift-register random-number generators that do this.
> The theory has something to do with Galois fields, and Solomon
> Golumb's name is attached there somewhere too, but I'm fuzzy
> on the details.
>
> All I remember is this: A shift register has a rule
> for generating the next bit based on the previous N. With rules involving
> certain polynomials (and Boolean math), you get shift-register
> sequences that produce exactly one copy of each possible N-bit
> pattern before cycling back to the starting bit sequence.
> The pattern 00...0 is excluded, because under this arithmetic
> the next bit will always be 0 when starting with all 0's.
>
> Thus the shift register has a cycle of 2^N - 1 bits before
> starting over. Hence, since a sequence of length 2^N - 1
> exists, the answer to your question is <= 2^N - 1.
>
> However, since there are 2^N -1 possible nonzero patterns,
> the answer to your question is also "at least 2^N - 1".
>
> Thus, the shift-register produces the shortest possible
> such sequence.
>
> One final note: it seems to me the coefficients and starting
> patterns of these sequences come from tables called "irreducible
> polynomials on Galois fields" or something like that.
>
>
> ----------------------------------------------------------
> Randy Poe
> Q & D Software Solutions Johns Hopkins University
> POB 10058, Silver Spring, MD 20914 Dept. of Math. Sciences
> qnd@dgsys.com poe@jhu.edu
> We sell solutions, not just advice.
> ------------------------------------------------------------
==============================================================================