Help! Maximal Length Shift Register, General Solution?
Chris Vecchio
location) of a maximal length shift register of arbitrary length?
I have a chart of tap locations for registers up to 39 bits in length
but I want to create one that is 300,000 bits in length (yes 300k!).
Even an explanation of how the charts for smaller registers are
derived would be helpful.
Thanks,
Chris
Joseph Legris
Why do you need such a long register? It has such a long cycle that no
conceivable computer could ever come close to generating even a tiny
fraction of it.
For example, to generate new states at 10 Ghz (10^10 states/sec), with a
maximal length cycle that repeats once each life-time of the universe
(15 billion years) you only need an 85-bit register. You can put the
remaining 299,915 bits to good use somewhere else.
--
Best regards,
Joseph Legris
Mike
"Chris Vecchio" <merti...@yahoo.com> wrote in message
news:29be4e95.02072...@posting.google.com...
I don't know of an algorithm, but the mathematical name for LFSRs is De
Bruijn sequences. Google for more information.
One wonders why you need 300,000 bits, though. Consider that a 100 tap LFSR
has 1.27E30 states, and if clocked at 10GHz it would take over 4 trillion
years to cycle through all of its states just once.
Can you enlighten us?
-- Mike --
Alan Fowler
Chris,
Do a Google search for "pseudo-random sequence
generator" (or similar topics)
I built a couple of variable length PSRGs about 30
years ago using 74 series logic shift registers
Th maximum length is usually 2^n - 1 where n is the
number of stages.
Alan.
John Woodgate
<cun09.27726$Fq6.2...@news2.west.cox.net>) about 'Help! Maximal
Length Shift Register, General Solution?', on Sat, 27 Jul 2002:
assumed that needs a 300 Kb register.
--
Regards, John Woodgate, OOO - Own Opinions Only. http://www.jmwa.demon.co.uk
Interested in professional sound reinforcement and distribution? Then go to
http://www.isce.org.uk
PLEASE do NOT copy news posts to me by E-MAIL!
Falk Brunner
news:29be4e95.02072...@posting.google.com...
> Does anyone know if there is a general solution to the design (tap
> location) of a maximal length shift register of arbitrary length?
> I have a chart of tap locations for registers up to 39 bits in length
> but I want to create one that is 300,000 bits in length (yes 300k!).
Go into the support section, ther you will fin an application note about
LFSRs, including a table for up to 168 bit registers.
--
MfG
Falk
John Woodgate
<amfo...@melbpc.org.au> wrote (in <3d4551b7...@news.melbpc.org.au
>) about 'Help! Maximal Length Shift Register, General Solution?', on
Sat, 27 Jul 2002:
feedback, ANDed from taps at several stages of the register, to repeat
after 300000. Finding the optimum tap configuration to get that is non-
trivial.
Kevin Aylward
news:j1NNrQAg...@jmwa.demon.co.uk...
Indeed it is non trivial in general. It is also usually done with ex-ors
as well, not ands. However, for stages below about 128, someone will
have done it already so that one can copy from.
Kevin Aylward
ke...@anasoft.co.uk
http://www.anasoft.co.uk
SuperSpice, a very affordable Mixed-Mode
Windows Simulator with Schematic Capture,
Waveform Display, FFT's and Filter Design.
Tim Hubberstey
I am aware of tables for maximal length LFSRs of up to 168 bits. I
believe there must be a general solution since these sizes cannot be
physically tested. The Xilinx application note containing these tables,
XAPP 052, has a fairly long list of references that would be a good
starting point.
You do, of course, realize that your LFSR will take on the order of
10**90300 years to repeat (give or take a few hundred billion years)?
--
Tim Hubberstey, P.Eng. . . . . . Hardware/Software Consulting Engineer
Marmot Engineering . . . . . . . VHDL, ASICs, FPGAs, embedded systems
Vancouver, BC, Canada . . . . . . . . . . . http://www.marmot-eng.com
Mike
news:j1NNrQAg...@jmwa.demon.co.uk...
> So a 19 stage register will repeat after 524287 bits, and needs multiple
> feedback, ANDed from taps at several stages of the register, to repeat
> after 300000. Finding the optimum tap configuration to get that is non-
> trivial.
It might be non-trivial, but it's not that difficult. What I'd do is write a
short C program to calculate the 299,999th state, and use an AND tree to
generate the reset.
-- Mike --
Kevin Aylward
news:3D42DFB3...@no.spam...
> Chris VCXO wrote:
> >
> > Does anyone know if there is a general solution to the design (tap
> > location) of a maximal length shift register of arbitrary length?
> > I have a chart of tap locations for registers up to 39 bits in
length
> > but I want to create one that is 300,000 bits in length (yes 300k!).
> > Even an explanation of how the charts for smaller registers are
> > derived would be helpful.
>
> I am aware of tables for maximal length LFSRs of up to 168 bits. I
> believe there must be a general solution since these sizes cannot be
> physically tested.
I have not looked at this for probably 20 years, but when I did, I
believe it was understood that ther was no general technique available.
Its somthing to do with the following issue:-)
"The obvious mathematical breakthrough would be development of an easy
way to factor large prime numbers." -- Bill Gates from "The Road Ahead,"
p. 265 ...
Kevin Aylward
news:ZjB09.28985$Fq6.3...@news2.west.cox.net...
I don't follow what you are saying here. The maximum length sequence is
usually generated from specific ex-or taps. Arguable the reason for this
is that mathematically, ex-or (modular sum) addition is much more
easier/useful to analyse then other arrangements. Are you suggesting
that you trial and error every possible combination of taps?
John Woodgate
<ZjB09.28985$Fq6.3...@news2.west.cox.net>) about 'Help! Maximal
Length Shift Register, General Solution?', on Sat, 27 Jul 2002:
narrowest gate that will work.
bogax
> multiple
> > > feedback, ANDed from taps at several stages of the register, to
> repeat
> > > after 300000. Finding the optimum tap configuration to get that is
> non-
> > > trivial.
note: 19 stages would give you (2^19 - 1) x 19 bits
> I don't follow what you are saying here. The maximum length sequence is
> usually generated from specific ex-or taps. Arguable the reason for this
> is that mathematically, ex-or (modular sum) addition is much more
> easier/useful to analyse then other arrangements. Are you suggesting
> that you trial and error every possible combination of taps?
>
surely what he means is:
imagine it's a 19 bit counter and you only want it to count 299,999
bogax
> believe there must be a general solution since these sizes cannot be
> physically tested.
I'm no expert but I think it's generally done either brute force
or random probes.
a couple of interesting links
ftp://helsbreth.org/pub/helsbret/random/lfsr_s.c
http://www.ece.cmu.edu/~koopman/./lfsr/index.html
(I've never been able to get the tables from that last one
to unzip, if any one can, please tell me how!)
It's possible to build up longer sequences from smaller generators
(the so called combined Tauseworthe generators)(although, a Tauseworthe
generator is not an LFSR they're basically equivalent I believe)
and, with some care, improve the statistical properties.
I know I've seen code for combined Tauseworthe generators several
places on the web, but I couldn't point to any.
Mike
"Kevin Aylward" <ke...@anasoft.co.uk> wrote in message
news:Q%B09.3121$U45.1...@newsfep1-win.server.ntli.net...
> "Mike" <mi...@nospam.com> wrote in message
> news:ZjB09.28985$Fq6.3...@news2.west.cox.net...
> > "John Woodgate" <j...@jmwa.demon.contraspam.yuk> wrote in message
> > news:j1NNrQAg...@jmwa.demon.co.uk...
> >
> > > So a 19 stage register will repeat after 524287 bits, and needs
> multiple
> > > feedback, ANDed from taps at several stages of the register, to
> repeat
> > > after 300000. Finding the optimum tap configuration to get that is
> non-
> > > trivial.
> >
> > It might be non-trivial, but it's not that difficult. What I'd do is
> write a
> > short C program to calculate the 299,999th state, and use an AND tree
> to
> > generate the reset.
> >
>
> I don't follow what you are saying here. The maximum length sequence is
> usually generated from specific ex-or taps. Arguable the reason for this
> is that mathematically, ex-or (modular sum) addition is much more
> easier/useful to analyse then other arrangements. Are you suggesting
> that you trial and error every possible combination of taps?
Once the initial state is known, every other state follows, except that they
don't follow in a nice sequential manner that lets you predict, from
inspection, what the 299,999th state is.
-- Mike --
Mike
"John Woodgate" <j...@jmwa.demon.contraspam.yuk> wrote in message
> I read in sci.electronics.design that Mike <mi...@nospam.com> wrote (in
> <ZjB09.28985$Fq6.3...@news2.west.cox.net>) about 'Help! Maximal
> Length Shift Register, General Solution?', on Sat, 27 Jul 2002:
> >"John Woodgate" <j...@jmwa.demon.contraspam.yuk> wrote in message
> >news:j1NNrQAg...@jmwa.demon.co.uk...
> >
> >> So a 19 stage register will repeat after 524287 bits, and needs
multiple
> >> feedback, ANDed from taps at several stages of the register, to repeat
> >> after 300000. Finding the optimum tap configuration to get that is non-
> >> trivial.
> >
> >It might be non-trivial, but it's not that difficult. What I'd do is
write a
> >short C program to calculate the 299,999th state, and use an AND tree to
> >generate the reset.
> >
> Yes, but you might find that needs an 18-wide gate. The *optimum* is the
> narrowest gate that will work.
Hmmm. My original thought was that there probably wasn't any way to get by
with less than a 19 input gate, but I'm not so sure that's the case. In any
event, proving that you can use a narrower gate, and finding the minimum,
would definitely move the problem into the non-trivial category.
-- Mike --
Tom Bruhns
300k bits, connected for maximal length, or do you want a sequence
which is 300k states long? If you really want to use an extremely
long register, then look up http://www.mersenne.org/prime.htm. If you
have a number which is a mersenne prime, it is _relatively_ easy to
find a maximal length polynomial. Actually, it's not too bad if you
can just tell us the factors of 2^300000 - 1. But I gotta know, how
are you going to implement the shift register? In software?
Now if you want a _sequence_ which is 300000 states long and is also
generated by a maximal length polynomial, then I'd ask you to first
find a solution to 300000 = p^n-1, for some integer p and n, and we
can go from there. If you don't find one, I'll have to ask you to
adjust the 300000 value to something else that will work for you,
because maximal length polynomials, by definition, always generate
p^n-1 states in one of their two loops, and one state in the other
loop.
I could give you a recipe for finding all the maximal length
polynomials for a given n and p (you're likely only thinking of p=2,
for a binary shift register), but you probably wouldn't like it very
much. I have to say, I like mine a little better than the one I've
commonly seen published. Basically, you have to test a polynomial to
make sure that it generates a sequence which repeats at exactly 2^n-1
cycles, and not before. It is necessary but not sufficient that the
polynomial not be factorable. You know that it must have an odd
number of terms (else it would be divisible by s+1), and that the s^0
term be 1 (else it would be divisible by s), and that the s^n term
must be 1 (else it wouldn't be expressing an nth order system). A
rather amazing number of the polynomials that are left end up being
maximal length. Once you have one, you can generate the others.
...
But first, we await word on just what it is you're trying to
accomplish.
By the way, you should be able to find lists of taps up to rather a
higher number than 39 bits. Have a look on the Xilinx website, and
look for ap notes on generating pseudorandom numbers. Seems to me
their list goes up well above 100 bits, maybe to 200.
Cheers,
Tom
merti...@yahoo.com (Chris Vecchio) wrote in message news:<29be4e95.02072...@posting.google.com>...
Kevin Aylward
news:3D4315...@diespammer.earthlink.net...
I ruled this out, becuase I am asumming when one talks about a max
length shift registar, that it implies a connection that gives a
standard pseudo random sequence. Making a simple counter is obviously a
triviality to which there would be no point to the original post imo.
John Woodgate
(in <3200347.02072...@posting.google.com>) about 'Help!
Maximal Length Shift Register, General Solution?', on Sat, 27 Jul 2002:
>adjust the 300000 value to something else that will work for you,
>because maximal length polynomials, by definition, always generate
>p^n-1 states in one of their two loops, and one state in the other
>loop.
You make a sequence repeat after any length less than the maximum by
combined feedback from intermediate taps on the register.
bogax
> length shift registar, that it implies a connection that gives a
> standard pseudo random sequence. Making a simple counter is obviously a
> triviality to which there would be no point to the original post imo.
>
LFSRs have some times been refered to as "polynomial counters" (and used
as
counters)
Perhaps I should have been more explicit.
You seem to be thinking that he's talking about generating the feed back
from the polynomial. I took him to be describing how to limit the cycle
to some specific number less than the maximal length once you've got
a working LFSR and in a fashion similar to what you might do if, eg,
you
wanted to make a 4 bit binary counter count to, say, 9 (this I take to
be
a common example of one way of making a decade counter)
In other words, I think you're talking about two different things.
(of course, I may be wrong, it wouldn't really be a maximal length
counter,
but then, how could it be with 300k states?)
Tom Bruhns
> I read in sci.electronics.design that Tom Bruhns <k7...@aol.com> wrote
> (in <3200347.02072...@posting.google.com>) about 'Help!
> Maximal Length Shift Register, General Solution?', on Sat, 27 Jul 2002:
> >If you don't find one, I'll have to ask you to
> >adjust the 300000 value to something else that will work for you,
> >because maximal length polynomials, by definition, always generate
> >p^n-1 states in one of their two loops, and one state in the other
> >loop.
>
> You make a sequence repeat after any length less than the maximum by
> combined feedback from intermediate taps on the register.
Indeed, you can get any length sequence you want, so long as you have
enough bits to hold the required number of states. But anything
shorter than p^n-1 won't be "maximal length" which is what the OP
asked for. I guess I should allow that he may not really care that
it's "maximal length" though! And in that case, there are plenty of
non-maximal-length _linear_ feedback taps, as well as plenty of
non-linear ways to truncate (and repeat at shorter cycle length) a
longer sequence. One trouble with non-maximal-length linear-feedback
sets is that you better be sure you start in a cycle that has the
length you want. (That's also true of the maximal length, but usually
the trivial cycle is easy to avoid.)
Cheers,
Tom
Kevin Aylward
It is difficult to follow exactly what he wrote
***
Does anyone know if there is a general solution to the design (tap
location) of [a maximal length shift register] of [arbitrary length]?
***
My []. So I interpret this as he wants a maximum length register, but he
wanted that rmax length one , to be different lengths.
***
I want to create one that is 300,000 bits in length (yes 300k!).
****
One reflection, I would interpret that he wanted a sequence length of
300k.
What does seems rather inconsiderate of the poster is that, despite all
the replies, he has not clarified what he wants.
Alan Fowler
ex-ors not AND gates.
Thank you for the correction. I'm getting rusty
after 30 years,
Alan.
Chris Vecchio
> the replies, he has not clarified what he wants.
Indeed!
My sincere apologies,
It was taking a while for my message to appear
so I didn't check back for a few days.
Thanks for all the spirited discussion and suggestions.
Now for some explanation:
> One reflection, I would interpret that he wanted
> a sequence length of 300k.
I would in fact like to create a maximal length
shift register of roughly 300k bits in length
- not 300k states (as mentioned, that could be done with 19 bits).
I also realize that it would take any computer many times the age of
the universe to cycle though the 2^300,000 states. But the project is
more of a conceptual one than a practical one. I've been collaborating
with/assisting an artist. She wants to create a software-based work
consisting of a 640x480 pixel image that cycles though every possible
pattern once and only once.
The pixels are binary - either black or white (you see I've been
trying to keep the problem tractable!) - so the number of states is
2^(640x480) = 2^307,200
Of course we could just make the thing start at all black (all 307200
bits = 0) and count up to all white (all bits 1) but that's not very
visually interesting. Only the few lower order bits/pixels can be
seen changing, plus after several solar lifetimes, the screen still
will be 99% black.
If we move through all the possible states in a random manner,
however, the screen will be a riot of snow-storm activity. I've
simulated this effect by using the PC random number generator to
continuously toggle random pixels. But this is "cheating" since it
removes the conceptual underpinning of the work. That is, it's highly
unlikely that the image will ever repeat - but there's no guarantee
that it won't. A maximal length pseudo-random sequence guarantees
that you'll never see the same image twice - not in a google years.
Joseph Legris
But if you factor in the probability of a malfunction in the computer
caused by, for example, incident cosmic rays or a radioactive decay,
then it is certain that that the image will repeat many times before the
maximal length sequence ever gets a chance to run all the way through.
So much for conceptual underpinnings. Interesting idea. Maybe you should
just put a frame around that.
Mike
merti...@yahoo.com says...
> Does anyone know if there is a general solution to the design (tap
> location) of a maximal length shift register of arbitrary length?
> I have a chart of tap locations for registers up to 39 bits in length
> but I want to create one that is 300,000 bits in length (yes 300k!).
> Even an explanation of how the charts for smaller registers are
> derived would be helpful.
>
> Thanks,
> Chris
>
You can find lots of info and references about LFBSRs, prime polynomials
and other fascinating stuff in the Spread Spectrum Handbook. I got mine
from McGraw Hill and sorry, it looks like it's lost and in need of
replacement. The table of taps (polynomial coefficients) does go up to
at least 128 bits, however. I will point out, though, that there are 2
configurations for this type of PN generator, Fibbinocci and Gallois
(spelling?) the first config has each feedback XOR feeding the next
whereas the latter has the XORs between flip-flops and the book above
shows the difference in configuration as related to the polynomial being
used. Actually, it's not that clear and you'll need to study the
chapter/section well.
Can't remember how it's done, but the stage numbers for one config are 1
to n and 0 to n-1 for the other, so the XORs go in different places.
IMHO, the book is a must read and one reason is that because in the
Fibbinocci config, the propagation delays of the XORs add. So for fast
switching speeds and/or high number of stages, the feedback bit will
arrive at the input after the shift that it was intended to influence.
I'm not sure (data book in storage, now) but I seem to recall an ECL
chip with 2 flip-flops with an XOR on the clock or data input in an old
(10yrs ?) Motorola ECL data book. This would be ideal for a Gallois
config register.
Anyway, get the book. It's got lots of good stuff in it as well as a
chapter on history where you can read about the mathematicians behind
all this. Here's some SS trivia for you. Heddy Lamar (Lemar?) - who was
married to an Austrian who was Hitler's Munitions Minister - worked with
her producer to develope an SS system to confuse German torpedos. The
system generated random freqs recorded on a player piano scroll. I kind
of like that story.
Here's an music application for the war effort ... Our local radio
station finnaly got around to playing Hendrx's "Star Spangled Banner" -
or maybe the title is "National Anthem" - a week or so after 9-11. I
thought it would make a good Psy-Ops tactic in Afganistan, like we did
in 'Nam. I can picture them running and screaming from the sound of
unfamiliar sensations.
Hey Kevin, pick up your axe and grind it for Uncle Sam ;-) ( no negative
connotation implied, here.) Tap into those loudspeakers they use at the
Mosque. (PAs used here - maybe they just talk loud over there. No
traffic at prayer time to mask the sound.)
Just kidding. I figure the clerics who claim that Islam is not about
terrorism are being truthful and that the terrorists are
following/living a distortion of the religion. At least I hope that's
the case. I did read the beginning of the Koran (Quaran?) that came on a
CD. I did get the impression that that book is anti-semitic, though, and
that the "enemy" should be crushed. But I didn't read the whole thing. I
could easily interpret one small part of the Bible and act on it, but
the whole book wouldn't neccesarily support my interpretation or condone
my actions. It's hard to imagine a whole population buying into the
theory that killing innocent people is righteous, regardless of what
religion teaches. After all, even after generations of brainwashing, the
people of the former Soviet Union weren't fooled. Just goes to show that
most people are basically descent and no amount of manipulation by the
scammers in power will ever be able to destroy that.
ok, if this 'causes the thread to go off-topic, so be it. These
digressions are usually refreshing, humorous, and educational - thanks
to the contributors.
mike
Mike
amfo...@melbpc.org.au says...
the max is always 2^n-1
mike
>
> Alan.
>
>
Mike
j...@jmwa.demon.contraspam.yuk says...
> I read in sci.electronics.design that Alan Fowler
> <amfo...@melbpc.org.au> wrote (in <3d4551b7...@news.melbpc.org.au
> >) about 'Help! Maximal Length Shift Register, General Solution?', on
> Sat, 27 Jul 2002:
> >merti...@yahoo.com (Chris Vecchio) wrote:
> >
> >>Does anyone know if there is a general solution to the design (tap
> >>location) of a maximal length shift register of arbitrary length?
> >>I have a chart of tap locations for registers up to 39 bits in length
> >>but I want to create one that is 300,000 bits in length (yes 300k!).
> >>Even an explanation of how the charts for smaller registers are
> >>derived would be helpful.
> >>
> >>Thanks,
> >
> >Chris,
> > Do a Google search for "pseudo-random sequence
> >generator" (or similar topics)
> >
> > I built a couple of variable length PSRGs about 30
> >years ago using 74 series logic shift registers
> >
> > Th maximum length is usually 2^n - 1 where n is the
> >number of stages.
> >
> So a 19 stage register will repeat after 524287 bits, and needs multiple
> feedback, ANDed from taps at several stages of the register, to repeat
> after 300000. Finding the optimum tap configuration to get that is non-
> trivial.
no kiddin'. for a second, i thought you said trivial. Even the spread
spectrum handbook with the appendix on finite field arithmetic doesn't
make it any easier. you have to find the prime polynomial.
mike
>
Mike C
says...
There's not only the spread spectrum handbook and another "Commercial
Applications of ... " (???) book (lost also?) , but "The Art of
Electronics" shows the Fibbinocci config. the output of the last flip-
flop is sent back to the first and on the way, the bit is modified
(XOR'd) by the value of the stages that correspond to any term of the
prime polynomial with a coefficient of 1. the other terms are non-
existent once you see that a zero coefficient cancels them. I've never
seen any article, book or implementation of the LFBSR that uses anything
other than 2 input XORs. Also, the all 0's state vector is not allowed.
in the Gallois config, the output is used to modify the input to those
stages corresponding to ... but the terms are numbered differently as
to how they correspond to the stage. on config is 0 to n-1 and the other
is 1 to n. my response to the original post expounds on this some and
then goes off topic.
Mike C
> -- Mike --
>
>
>
Mike C
says...
excellent response and thanks for tha link! my books are missing. do you
know of any ASICs used for PN and RAKE processing? Other than what i
might find at the link above, that is.
Mike C.
>
>
>
>
>
Mike C
> Chris VCXO wrote:
> >
> > Does anyone know if there is a general solution to the design (tap
> > location) of a maximal length shift register of arbitrary length?
> > I have a chart of tap locations for registers up to 39 bits in length
> > but I want to create one that is 300,000 bits in length (yes 300k!).
> > Even an explanation of how the charts for smaller registers are
> > derived would be helpful.
>
> I am aware of tables for maximal length LFSRs of up to 168 bits. I
> believe there must be a general solution since these sizes cannot be
> physically tested. The Xilinx application note containing these tables,
> XAPP 052, has a fairly long list of references that would be a good
> starting point.
>
> You do, of course, realize that your LFSR will take on the order of
> 10**90300 years to repeat (give or take a few hundred billion years)?
>
the initial post. You'll need to convert to Galois config.
Mike C.
Mike C
ke...@anasoft.co.uk says...
> "Tim Hubberstey" <sen...@no.spam> wrote in message
> news:3D42DFB3...@no.spam...
> > Chris VCXO wrote:
> > >
> > > Does anyone know if there is a general solution to the design (tap
> > > location) of a maximal length shift register of arbitrary length?
> > > I have a chart of tap locations for registers up to 39 bits in
> length
> > > but I want to create one that is 300,000 bits in length (yes 300k!).
> > > Even an explanation of how the charts for smaller registers are
> > > derived would be helpful.
> >
> > I am aware of tables for maximal length LFSRs of up to 168 bits. I
> > believe there must be a general solution since these sizes cannot be
> > physically tested.
>
> I have not looked at this for probably 20 years, but when I did, I
> believe it was understood that ther was no general technique available.
>
Hi again, Kevin:
> Its somthing to do with the following issue:-)
>
the :-) means you see bill's error, right?
> "The obvious mathematical breakthrough would be development of an easy
> way to factor large prime numbers." -- Bill Gates from "The Road Ahead,"
> p. 265 ...
sounds like Public Key encryption but you can't factor a prime into
anything other than 1 and itself. so bill's just blathering. PK uses a
product of two large primes, i seem to recall.
LFSRs are from prime polynomials and we are talking more than basic math
here.
Mike C
Mike C
j...@jmwa.demon.contraspam.yuk says...
> I read in sci.electronics.design that Tom Bruhns <k7...@aol.com> wrote
> (in <3200347.02072...@posting.google.com>) about 'Help!
> Maximal Length Shift Register, General Solution?', on Sat, 27 Jul 2002:
> >If you don't find one, I'll have to ask you to
> >adjust the 300000 value to something else that will work for you,
> >because maximal length polynomials, by definition, always generate
> >p^n-1 states in one of their two loops, and one state in the other
> >loop.
>
> You make a sequence repeat after any length less than the maximum by
> combined feedback from intermediate taps on the register.
>
the sequence just repeats. forcing anything screws upo the statistical
balance of the output which is supposed to mimic gausian random white
noise. Using NLFF (non-linear feed-forward) to thwart the enemy and/or
jammers attempts to guess the code ( 2(?) register lengths of key sent
in the clear - remember, these codes are to be combined with data which
is not known and there for random - is enought to calculate the code
sequence. See The Spread Spectrum Handbook) is a trial and error thing.
There are general guidelines in SSHB - the idea is to maintain a
statistically balanced code - equal numbers of j-tuples - while altering
the output in such a way as to prevent the interceptor from guessing
code accidentally sent in the clear - like an image with a bunch of 0's
representing black.
Mike C
Allan Herriman
Other posts in this thread have mentioned this app note:
http://www.xilinx.com/xapp/xapp052.pdf
which describes the use of non-linear feedback (using a wide and gate)
to modify the sequence. In particular, the lockup with the all 0's
state vector can be avoided, and the sequence length can be extended
to 2^N.
See also
http://www.xilinx.com/xapp/xapp210.pdf
Of course, since the feedback is non-linear, it shouldn't be called an
LFSR.
Regards,
Allan.
Allan Herriman
The high speed implementations are bit-parallel, so the distinction
between the Fibonacci and Galois arrangements is lost.
(The parallel LFSR has exactly the same structure as the feedback part
of a parallel CRC.)
I guess it depends on what you mean by high speed though. The highest
speed LFSRs are used for BER testing and bit scrambling on optical
links. Spread spectrum is rather slow in comparison.
You could use ECL in a serial implementation up to perhaps a few GHz
(and then only if you are very good).
An FPGA (using a parallel LFSR) perhaps could be two orders of
magnitude faster.
[off topic text snipped]
Regards,
Allan.
Mike C
k7...@aol.com says...
wrong. a maximal length LFSR cycles though ALL posible states (state
vectors) except the not allowed all 0's state and therefor can start in
any state. the j-tuples are balance - you'll have ... (poss memory prob
again) ... say, n 1s followed by 0s; n-1 0s followed by 1s; n/2 11s
followed by 0; (n-1)/2 00s followed by 1. In this way, the spectrum
generated contains all frequency components from the repetition freq to
the clock freq spaced at intervals equal to the repetition freq.
I never heard of a "trivial" (or "non-trivial" for that matter) cycle. I
don't think there is such a thing in the context of max LFSRs.
with non-maximal, having to always start with a specific state vector
ruins the random nature of the key unless you delay by a random number
of bits before XORing in the data.
i'm glad to see some excellent responses here at the (currently) end of
this thread and especially appreciate the links. SS/CDMA is one of my
favorite topics. Thanks to everyone and also the OP for getting this
thread going.
Mike C
Mike C
allan_herrim...@agilent.com says...
all these links should keep me pretty busy. I failed to state that the
all 0s state never occurs in an LFSR unless you load it with 0s or
possibly if the XOR FB propagation delays of the Fibbinocci config cause
a zero to be loaded instead of a 1 - e.g stateN = 0001 and the incoming
1 is delayed so the (late) previous 0 is shifted in (trailing 1 shifted
out) when it should have been a 1. of course, in this case we never had
anything more than crap to begin with.
i'll look at that app note. most of what i remember is non-linear feed
FORWARD - i.e. NL modification of the output stream with state vector
bits usually anded and added to the output. that's where certain rules
of thumb come into play. It's important with NLFF to preserve the
statistical balance of the key. BTW the SSHB is compiled from the works
of those who did this stuff for the military. Certain codes used for
syncronization (correlation) of sequences at the reciever (e.g. gold
codes) while speeding up sync, weaken the codes in some cases. I think
the gold codes were generated by combining two LFSR stages with known
correlation peaks to arrive at an easily sync'd code. I think it was
found that the combined codes resulted in a length less than what would
be achieved with a single LFSR having the same # if stages as the 2
separate LFSRs. Something like that. The application was for pilot to
pilot commo, so a weak code could be acceptable as long as it was robust
enough to resist jamming attempts. Figure that even if it could be
decoded later, 1. we change the code regularly to thwart interception
and jamming and 2. so what if the enemy finds out later (i.e., after the
fact) that you radioed your wingman and he blew up one of your guys. Or
you were inbound to a target. too late!
I hope the OP considers the sync prob of that humongous key he wants.
sending sync info with a weaker code will be the achilles heel of the
whole project. even sending a known sequence encrypted with a strong key
is dangerous. send 110001100111 added to the key; reciever recieves
000111111111 and adds this to the expected sequence; search on the
result for correlation and you know where to start your key. Interceptor
somehow determines the known sequence and does the same. oops! best to
use PK encryption on top of another crypto scheme and use the PN
sequence on top of that for signal hiding purposes.
mike c
Mike C
terms!!! the ones with zero coefficients drop out, but you need to find
300k coeficients. I hope to find more math on this and maybe there's an
good way to code this in C++. some shortcut like you use for an fft. i
don't recall anything like this in "Numerical (whatever it 's called -
'Solutions', i think) in C++."
> > One reflection, I would interpret that he wanted
> > a sequence length of 300k.
i thought you (CV) were pretty clear although your terminology might
confuse. yes 524287 states is what you get from a 19 "STAGE" LFSR. the
use of "bits in length" is ambiguous. Brings to mind why my ex-GF isn't
speaking to me. But that's due to her inability to speak plain everyday
English so don't get me wrong - you just didn't know the tech terms.
your english seems fine. sorry.. she's got me pissed and there's no
outlet here. GGGGGGGGGRRRRRRRRRRRRRRRR!!!!!!!!!!! the caffeine isn't
making thing any better, either.
but you definitely picked the right way to realize your app. you will
get a different picture for each state, but if all black is all 0s,
you'll have to force it since all 0s will lock the LFSR in that state.
Mike C
lg...@diespammer.earthlink.net says...
about that unzip prob ...
i went there and clicked on 16.dat.qz . it unzipped in IE5.5 but when i
saved the link, neither WinRAR nor WinZip could deal with it. 16 is the
highest that IE would open, also. so I'm not sure what's up, but you can
rest assured it's not a problem unique to your system.
thanks for the links.
mike c
Mike
ke...@anasoft.co.uk says...
> > news:j1NNrQAg...@jmwa.demon.co.uk...
> >
> > > So a 19 stage register will repeat after 524287 bits, and needs
> multiple
> > > feedback, ANDed from taps at several stages of the register, to
> repeat
> > > after 300000. Finding the optimum tap configuration to get that is
> non-
> > > trivial.
> >
> > It might be non-trivial, but it's not that difficult. What I'd do is
> write a
> > short C program to calculate the 299,999th state, and use an AND tree
> to
> > generate the reset.
> >
>
> I don't follow what you are saying here.
me either. there is no reset involved, for one thing. The contents of
each gate at a given time is known as the state vector and all zeros are
a no-no - the register would stay in the all 0's state. the feedback is
injected at the beginning of the register for Fibbinocci configs and
into the XORs for those stages that have a 1 coeficient for the
polynomial term in the Gallois config.
>The maximum length sequence is
> usually generated from specific ex-or taps. Arguable the reason for this
> is that mathematically, ex-or (modular sum) addition is much more
> easier/useful to analyse then other arrangements.
Sort of. If you check that SS handbook ( see the post that my news
client "should have" put down below as a reply to the original poster )
you'll find all the great math. The RAKE processor is one topic i
enjoyed. I kind of remember a factor used to convert between 1,0 and
-1,1 binary systems which would make the analysis more cumbersome. But
the term is still there in the derivation. My point is - after all the
math was done, the resulting equation yielded something we could realize
in hardware.
I think the math came first, Kevin. Just like the harmonic motion eq for
the pendulum or better yet, the spring, weight, damper was later found
to be analogous to he RLC tank. But of course the spring, etc. was here
before the math to explain it was derived. bad example.
What came first, the integral or the op-amp integrator? Once we
developed the latter, we were able to make filters without coils, right?
We didn't derive mathematical integration to explain the circuit.
> Are you suggesting
> that you trial and error every possible combination of taps?
that would suck. also, the SS handbook has a chart that shows the
coefficients (tap locations) that give a backward maximal sequence.
sorry, had to tack a last initial on my handle to avoid confusion with
the other mike and this is the first post that reflects that.
Kevin, i'm sorry i haven't had a chance to test your CAD program for PCB
netlist export. I hopefully have it on CD somewhere and will try it some
time. The reason i didn't get to it was because your program was not
that easy to figure out quickly and I didn't have much time to play.
Mike C -- soon to be MDC due to all the mikes in the world - only a
matter of time before another Mike C shows up here.
Mike C
allan_herrim...@agilent.com says...
only because of FCC regulation. limited spread of 1MHz for ISA-95, i
think. maybe it was 10MHz.
>
> You could use ECL in a serial implementation up to perhaps a few GHz
> (and then only if you are very good).
i definitely want to prove to myself that i am and that i can deal with
the ground bounce. there's a book from Signetics (?) on ECL that may
help me as well as "High Speed Digital Design." Didn't lose that one.
> An FPGA (using a parallel LFSR) perhaps could be two orders of
> magnitude faster.
>
> [off topic text snipped]
>
> Regards,
> Allan.
>
Hi Allan:
good idea... saving bandwidth by snipping the off topic stuff :-) I
don't recall seeing any parallel implementations but i'm interested.
where could i find this? don't reply if it's in the links you provided
earlier - right, Xilinx = FPGA = solution. i'm visiting those in between
other tasks. i find the concept of a parallel shift register
interesting. the stuff i've worked on had SRs that were loaded with the
init state in a parallel manner like a presettable SR chip, but they
were potted JK-FF with S/R modules made of discrete components.
everything still shifted. i'm havng a hard time picturing a parallel SR.
multiple registers not shifting, but loading the next? i think i like
it. of course, i like the old way, too.
sorry to go off topic, again, but here's a related project ...
never mind. that's for my web-site. i'll organize all my clips of it and
put the page up. if you want to read a good EE / psuedo-science story,
just e-mail me. i'll send the link as soon as it's ready. i need to get
that done just to get it off my chest. i just changed my reply address
to md_cola@even_link.net (damn those spam chain letters!) so just remove
the underscores.
Best Regards,
mike c.
Allan Herriman
Even without FCC regulations, I can't imagine DSSS radios using chip
rates of 40GHz.
(A quick web search for "oc768 BER test" will find several 40Gb/s BER
testers and - surprise - the first hit in Google is one of ours!)
more below...
>> You could use ECL in a serial implementation up to perhaps a few GHz
>> (and then only if you are very good).
>
>i definitely want to prove to myself that i am and that i can deal with
>the ground bounce. there's a book from Signetics (?) on ECL that may
>help me as well as "High Speed Digital Design." Didn't lose that one.
>> An FPGA (using a parallel LFSR) perhaps could be two orders of
>> magnitude faster.
>>
>> [off topic text snipped]
>>
>> Regards,
>> Allan.
>>
>
>Hi Allan:
>
>good idea... saving bandwidth by snipping the off topic stuff :-) I
>don't recall seeing any parallel implementations but i'm interested.
>where could i find this? don't reply if it's in the links you provided
>earlier - right, Xilinx = FPGA = solution. i'm visiting those in between
>other tasks. i find the concept of a parallel shift register
>interesting. the stuff i've worked on had SRs that were loaded with the
>init state in a parallel manner like a presettable SR chip, but they
>were potted JK-FF with S/R modules made of discrete components.
>everything still shifted. i'm havng a hard time picturing a parallel SR.
>multiple registers not shifting, but loading the next? i think i like
>it. of course, i like the old way, too.
Here's a thread about the implementation of a parallel CRC at 10Gb/s :
http://groups.google.com/groups?threadm=c2088d4a.0111290138.10577818%40posting.google.com
(you'll need to read the entire thread)
A parallel LFSR has an identical structure, except the XOR tree will
not have a data input - it will just have the feedback terms.
If your LFSR polynomial is N bits long, and if you know N adjacent
bits of the sequence (call them the 'seed'), you can calculate all
future bits in the sequence.
Here's the good bit: the complexity of the logic required to determine
the value of a future bit is independent of how far into the future we
go.
The logic is just a linear function of the N seed bits (i.e. it's an
XOR tree).
On average, each future bit will require about N/2 of the seed bits to
be XOR'ed together. (Different bits in the future require a different
subset of the seed bits to be XOR'ed.)
So we can calculate a whole lot of future bits in parallel, then take
the last N of them and use them as the new seed for the next clock.
Note that only N of the bits have feedback - the other bits can be
pipelined as much as you want.
In an FPGA (which use 4 input lookup tables to implement logic
functions), the depth of the feedback logic will be
ceiling(log4(N/2)), which means that a 32 bit LFSR polynomial will
require 2 - 3 levels of logic. This allows a clock frequency of a few
hundred MHz.
In an ASIC, if we use 2 input XOR gates, the number of levels of logic
will be
ceiling(log2(N/2)), which leads to about 4 - 5 levels of logic, and
the clock could be ... I dunno, fast, very fast.
The overall data rate will be equal to the clock frequency multiplied
by the output bus width.
Here's the other good bit: we can generate as many future bits as we
want from the seed, until we run into a fanout limit or until we run
out of pipelining flip flops. Practical high speed designs can use
buses hundreds of bits wide.
Regards,
Allan.
gorible
Looks like you're watching this group - do you still IRC? I'm still at
the
same email address and have some family news.
Tom Bruhns
seems to me you go on to agree with what I posted. The trivial cycle
is the one containing all zeros; its length is one. In a maximal
length sequence, there is only one other cycle, and it's p^n-1 --
2^n-1 for a binary sequence. (There's not a requirement that the
shift registers be binary, but that's usually what folk think of.)
But...how does the OP figure out (in a practical way) the taps to use
in his 300,000-stage shift register to get maximal length? ;-) I can
guarantee that there will be a lot--a huge number--of polynomials
which are maximal length for that size register, but I'm not aware of
an easy way to find one. (Give me one, and the rest are relatively
easy.)
Cheers,
Tom
Mike C <mdc...@evenlink.net> wrote in message news:<MPG.17b368fcf...@news.evenlink.net>...
Allan Herriman
>You say, "wrong," but I don't see what you are saying is wrong! It
>seems to me you go on to agree with what I posted. The trivial cycle
>is the one containing all zeros; its length is one. In a maximal
>length sequence, there is only one other cycle, and it's p^n-1 --
>2^n-1 for a binary sequence. (There's not a requirement that the
>shift registers be binary, but that's usually what folk think of.)
>
>But...how does the OP figure out (in a practical way) the taps to use
>in his 300,000-stage shift register to get maximal length? ;-) I can
>guarantee that there will be a lot--a huge number--of polynomials
>which are maximal length for that size register, but I'm not aware of
>an easy way to find one. (Give me one, and the rest are relatively
>easy.)
Hi Tom,
I think the easiest way would be to post in news:sci.math and ask
about how to determine whether a polynomial of order 300000 in GF(2)
is primitive and irreducible.
I've crossposted this to sci.math.
Regards,
Allan.
Merlin_M
> "Chris Vecchio" <merti...@yahoo.com> schrieb im Newsbeitrag
> news:29be4e95.02072...@posting.google.com...
> > location) of a maximal length shift register of arbitrary length?
> > I have a chart of tap locations for registers up to 39 bits in length
> > but I want to create one that is 300,000 bits in length (yes 300k!).
>
>
> Go into the support section, ther you will fin an application note about
> LFSRs, including a table for up to 168 bit registers.
>
Merlin.