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