I'm having difficulty finding good reference citations (i.e., published papers) regarding Cellular Automata Shift Register generation of maximal-length sequences. I have some of the basics, but not detailed references. A paper I have from the late 90's says that maximal length, minimal cost CASRs of arbitrary lengths are well documented in literature. I'm trying to find some of that literature without much success. Does anybody know of any references? Google hasn't been much help. Eric Jacobsen Minister of Algorithms Abineau Communications http://www.abineau.com
Maximal-length CASR sequence generation
Started by ●October 7, 2010
Reply by ●October 7, 20102010-10-07
On Oct 7, 7:34�pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:> I'm having difficulty finding good reference citations (i.e., > published papers) regarding Cellular Automata Shift Register > generation of maximal-length sequences. � I have some of the basics, > but not detailed references. �A paper I have from the late 90's says > that maximal length, minimal cost CASRs of arbitrary lengths are well > documented in literature. > > I'm trying to find some of that literature without much success. > Does anybody know of any references? � �Google hasn't been much help. > > Eric Jacobsen > Minister of Algorithms > Abineau Communicationshttp://www.abineau.comInteresting topic I had never heard of, great writeup on Wolfram site. None of the references there are useful? http://www.stephenwolfram.com/publications/articles/ca/86-random/17/text.html John
Reply by ●October 7, 20102010-10-07
On 10/07/2010 04:34 PM, Eric Jacobsen wrote:> I'm having difficulty finding good reference citations (i.e., > published papers) regarding Cellular Automata Shift Register > generation of maximal-length sequences. I have some of the basics, > but not detailed references. A paper I have from the late 90's says > that maximal length, minimal cost CASRs of arbitrary lengths are well > documented in literature. > > I'm trying to find some of that literature without much success. > Does anybody know of any references? Google hasn't been much help. >I'll bet you can't see the King's new cloths, either. I hate that "well documented in the literature" stuff. If it's so freaking well documented, why can't you put a textbook in your bibliography to help out some poor ignorant bastard like _me_!!! Obviously I'm no help -- good luck. I assume you've Googled. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" was written for you. See details at http://www.wescottdesign.com/actfes/actfes.html
Reply by ●October 7, 20102010-10-07
Tim Wescott <tim@seemywebsite.com> wrote:> On 10/07/2010 04:34 PM, Eric Jacobsen wrote: >> I'm having difficulty finding good reference citations (i.e., >> published papers) regarding Cellular Automata Shift Register >> generation of maximal-length sequences. I have some of the basics, >> but not detailed references. A paper I have from the late 90's says >> that maximal length, minimal cost CASRs of arbitrary lengths are well >> documented in literature.(snip)> I hate that "well documented in the literature" stuff. If it's so > freaking well documented, why can't you put a textbook in your > bibliography to help out some poor ignorant bastard like _me_!!!Realizing that I actually have Wolfram's "A New Kind of Science," pretty much the whole book on CA, I tried looking it up there. It doesn't say much, but does have some description on LFSR (in terms of CA, but pretty much the same), and also some on non-linear feedback shift registers. So, my guess is that CASR includes both LFSR and NLFSR. If nothing else, there is a lot to learn in that book. (The book is big and the print is small.) -- glen
Reply by ●October 7, 20102010-10-07
On Oct 7, 6:13�pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:> Tim Wescott <t...@seemywebsite.com> wrote: > > On 10/07/2010 04:34 PM, Eric Jacobsen wrote: > >> I'm having difficulty finding good reference citations (i.e., > >> published papers) regarding Cellular Automata Shift Register > >> generation of maximal-length sequences. � I have some of the basics, > >> but not detailed references. �A paper I have from the late 90's says > >> that maximal length, minimal cost CASRs of arbitrary lengths are well > >> documented in literature. > > (snip) > > > I hate that "well documented in the literature" stuff. �If it's so > > freaking well documented, why can't you put a textbook in your > > bibliography to help out some poor ignorant bastard like _me_!!! > > Realizing that I actually have Wolfram's "A New Kind of Science," > pretty much the whole book on CA, I tried looking it up there. > > It doesn't say much, but does have some description on LFSR > (in terms of CA, but pretty much the same), and also some on > non-linear feedback shift registers. > > So, my guess is that CASR includes both LFSR and NLFSR. > > If nothing else, there is a lot to learn in that book. > (The book is big and the print is small.) > > -- glen1st google hit I got on the subject was from Wolfram. Had a pretty good description in it, but I assume Eric already had seen that. Eric
Reply by ●October 7, 20102010-10-07
Eric Jacobsen wrote:> I'm having difficulty finding good reference citations (i.e., > published papers) regarding Cellular Automata Shift Register > generation of maximal-length sequences. I have some of the basics, > but not detailed references. A paper I have from the late 90's says > that maximal length, minimal cost CASRs of arbitrary lengths are well > documented in literature. > > I'm trying to find some of that literature without much success. > Does anybody know of any references? Google hasn't been much help.P. Fan, M. Darnell. �Sequence design for communications applications� ISBN 0-471-96557 Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●October 8, 20102010-10-08
On Fri, 8 Oct 2010 01:13:52 +0000 (UTC), glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:>Tim Wescott <tim@seemywebsite.com> wrote: >> On 10/07/2010 04:34 PM, Eric Jacobsen wrote: >>> I'm having difficulty finding good reference citations (i.e., >>> published papers) regarding Cellular Automata Shift Register >>> generation of maximal-length sequences. I have some of the basics, >>> but not detailed references. A paper I have from the late 90's says >>> that maximal length, minimal cost CASRs of arbitrary lengths are well >>> documented in literature. >(snip) > >> I hate that "well documented in the literature" stuff. If it's so >> freaking well documented, why can't you put a textbook in your >> bibliography to help out some poor ignorant bastard like _me_!!! > >Realizing that I actually have Wolfram's "A New Kind of Science," >pretty much the whole book on CA, I tried looking it up there. > >It doesn't say much, but does have some description on LFSR >(in terms of CA, but pretty much the same), and also some on >non-linear feedback shift registers. > >So, my guess is that CASR includes both LFSR and NLFSR. > >If nothing else, there is a lot to learn in that book. >(The book is big and the print is small.) > >-- glenCASR is a bit different animal than an LFSR, and generates a different sequence. I've got a pretty good idea of how to put one together, but I don't have the generator definitions for the lengths I'm interested in. So I really just need a generator table or something, preferrably in terms of what are called CA150 and CA90 rules. Seems tough to find, though... :( Eric Jacobsen Minister of Algorithms Abineau Communications http://www.abineau.com
Reply by ●October 8, 20102010-10-08
On Thu, 07 Oct 2010 21:17:50 -0500, Vladimir Vassilevsky <nospam@nowhere.com> wrote:> > >Eric Jacobsen wrote: > >> I'm having difficulty finding good reference citations (i.e., >> published papers) regarding Cellular Automata Shift Register >> generation of maximal-length sequences. I have some of the basics, >> but not detailed references. A paper I have from the late 90's says >> that maximal length, minimal cost CASRs of arbitrary lengths are well >> documented in literature. >>=20 >> I'm trying to find some of that literature without much success. >> Does anybody know of any references? Google hasn't been much help. > >P. Fan, M. Darnell. =93Sequence design for communications applications=94= > >ISBN 0-471-96557 > > >Vladimir Vassilevsky >DSP and Mixed Signal Design Consultant >http://www.abvolt.com >The table of contents isn't assuring that it covers the topic or provides the definitions for different lengths. Eric Jacobsen Minister of Algorithms Abineau Communications http://www.abineau.com
Reply by ●October 8, 20102010-10-08
On Fri, 08 Oct 2010 15:09:51 GMT, eric.jacobsen@ieee.org (Eric Jacobsen) wrote:>On Fri, 8 Oct 2010 01:13:52 +0000 (UTC), glen herrmannsfeldt ><gah@ugcs.caltech.edu> wrote: > >>Tim Wescott <tim@seemywebsite.com> wrote: >>> On 10/07/2010 04:34 PM, Eric Jacobsen wrote: >>>> I'm having difficulty finding good reference citations (i.e., >>>> published papers) regarding Cellular Automata Shift Register >>>> generation of maximal-length sequences. I have some of the basics, >>>> but not detailed references. A paper I have from the late 90's says >>>> that maximal length, minimal cost CASRs of arbitrary lengths are well >>>> documented in literature. >>(snip) >> >>> I hate that "well documented in the literature" stuff. If it's so >>> freaking well documented, why can't you put a textbook in your >>> bibliography to help out some poor ignorant bastard like _me_!!! >> >>Realizing that I actually have Wolfram's "A New Kind of Science," >>pretty much the whole book on CA, I tried looking it up there. >> >>It doesn't say much, but does have some description on LFSR >>(in terms of CA, but pretty much the same), and also some on >>non-linear feedback shift registers. >> >>So, my guess is that CASR includes both LFSR and NLFSR. >> >>If nothing else, there is a lot to learn in that book. >>(The book is big and the print is small.) >> >>-- glen > >CASR is a bit different animal than an LFSR, and generates a different >sequence. I've got a pretty good idea of how to put one together, but >I don't have the generator definitions for the lengths I'm interested >in. So I really just need a generator table or something, >preferrably in terms of what are called CA150 and CA90 rules. > >Seems tough to find, though... :(Does this help? http://www.stephenwolfram.com/publications/articles/ca/86-random/index.html -- Muzaffer Kal DSPIA INC. ASIC/FPGA Design Services http://www.dspia.com
Reply by ●October 8, 20102010-10-08
Eric Jacobsen <eric.jacobsen@ieee.org> wrote: (snip, I wrote)>>Realizing that I actually have Wolfram's "A New Kind of Science," >>pretty much the whole book on CA, I tried looking it up there.>>It doesn't say much, but does have some description on LFSR >>(in terms of CA, but pretty much the same), and also some on >>non-linear feedback shift registers.>>So, my guess is that CASR includes both LFSR and NLFSR.(snip)> CASR is a bit different animal than an LFSR, and generates a different > sequence. I've got a pretty good idea of how to put one together, but > I don't have the generator definitions for the lengths I'm interested > in. So I really just need a generator table or something, > preferrably in terms of what are called CA150 and CA90 rules.Well, I said both LFSR and NLFSR. It is NLFSR if the feedback includes anything other than just XOR and inverters. With N bits of state, the period can't be any longer than 2**N. I believe it is shorter than the 2**N-1 of the maximal LFSR. The generated bits might be more random than from an LFSR, though. When I looked in the book, the section on NLFSR was pretty small, but it might assume that you read the rest of the book.> Seems tough to find, though... :(-- glen
