[sdiy] Shift register sequence period

[Tim Stinchcombe]

Hi list,
	I thought I'd send one reply to save space and time, so thanks to
everyone who responded, particularly Eric and Dave who managed to get some
calculations going in about a tenth of the time it took me (had to dust my
copy of Mathematica off, it doesn't come out very often, and when it does, I
find I have forgotten even basic things like 'For' loops etc...).

So I *have* now got some calcs up and running myself and concur that the
length is indeed 262140. I also checked that the sequence from the 19-stage
equivalent *linear* register, as given by the Berlekamp-Massey algorithm run
I did, does also give the same sequence.

First, having done some calcs, the proof that it *is* non-linear is
virtually immediate. If you start with a '1' in stage 1, and 0s for the
rest, at the first shift the feedback is easily seen to be 0, and we then
shift the only 1 out of the register and a 0 in, i.e. it is now filled with
*18* zeroes - thus it *cannot* be linear as it would stick in this state for
ever. And of course this would explain why we need one more stage to
implement it as a linear register, as it *can* cope with 18 0s and one 1.

My original 'working' for believing it was non-linear was this: first assume
the inverter isn't there, so build up the feedback poly as:
1. x^13+1 from first xor
2. xor'ed with x^9 to get x^13+x^9+1
3. whole poly then x^18+x^13+x^9+1

But (so I reasoned) the inverter adds a '1' at step 1., and as we are
implicitly working mod 2, we get x^13+1+1 = x^13. Thus when added at step 2.
we get x^13+x^9 = x^9(x^4+1), which is non-linear (never mind adding the
x^18, which I'm not even sure is a valid thing to do in this case). However
I'm not now convinced that adding this '+1' is valid - I need to go back to
the definition of how the poly is defined from the (linear) recurrence, to
see if that makes sense in those terms. If I could remember how to calculate
the sequence directly from the poly (I seem to recall something about using
the 'trace' function), and I did get the sequence from the non-linear one
above, I think that would clinch it.

I will also read up on how to find the period from any old poly defining a
sequence (I think I need to find the least k for which the poly divides
x^k+1, but I could be wrong), as if I do so for the length-19 polynomial, I
should then be able to verify how the 262140 = 2^18-4 arises. The length 19
poly is:

x^19+x^18+x^14+x^13+x^10+x^9+x+1 =

(1+x)^3(1+x^2+x^4+x^6+x^8+x^9+x^10+x^11+x^12+x^14+x^16)

Curiously, if we factor the poly without the inverter (back to the 18-stage
register):

x^18+x^13+x^9+1 we get

(1+x)^2(1+x^2+x^4+x^6+x^8+x^9+x^10+x^11+x^12+x^14+x^16)

which just cannot be coincidental that what we lose is a '1+x' term which is
basically what inversion is?!

Tim
__________________________________________________________
Tim Stinchcombe 

Cheltenham, Glos, UK
email: tim102 at tstinchcombe.freeserve.co.uk

> -----Original Message-----
> From: synth-diy-bounces at dropmix.xs4all.nl 
> [mailto:synth-diy-bounces at dropmix.xs4all.nl] On Behalf Of Tim 
> Stinchcombe
> Sent: 05 May 2008 20:28
> To: synth-diy at dropmix.xs4all.nl
> Subject: [sdiy] Shift register sequence period
> 
> 
> Hi list,
> 	I've been trying to establish the length of the 
> sequence from a particular 4006 shift register setup. It is 
> used in the Doepfer A-117, which is where I came across it; 
> Ken Stone also uses it in his 'Digital Noise'
> module:
> 
> http://www.cgs.synth.net/modules/cgs31_digital_noise.html
> 
> and the earliest reference I've found to it so far is in a 
> 1990 book by Ray Marston, 'Integrated Circuit and Waveform 
> Generator Handbook'.
> 
> At first I thought the inverter in the feedback (middle 4030 
> gate in Ken's circuit above) would mean that the length of 
> the sequence would be some what less than 2^18-1. Then in 
> attempting to translate the gates into polynomials (if I've 
> got it right) the inverting action seems to make the feedback 
> non-linear, and so the normal theory of LFSRs no longer 
> applies. So I 'captured' a few bit sequences on my scope (the 
> longest being 59 bits), and ran it through the 
> Berlekamp-Massey algorithm, which appears to say that the 
> length of the minimum *linear* feedback shift register which 
> could generate this sequence is actually 19 stages, i.e. one 
> more than the 18 available in the 4006! I'm hoping that this 
> 'anomaly' *is* due to the non-linearity...
> 
> Has anyone done any analysis of this or similar circuits, 
> i.e. with an inverter in the feedback? Or if anyone steer me 
> in the right direction, or toward a decent analysis of this 
> circuit, then I'd appreciate it. (I can't find anything 
> similar in Electronotes; not much seems to turn up in the 
> Synth DIY archives; but I note the EDP Wasp and Gnat use 
> similar circuits, but with a different arrangement of taps 
> and inverter.)
> 
> Cheers,
> 	Tim
> 
> P.S. I have a copy of Golomb's 'Shift Register Sequences', 
> but I'm kinda hoping to get at least a semi-cogent sense of 
> what is happening without resorting to 3 months hard graft... 
> __________________________________________________________
> Tim Stinchcombe 
> 
> Cheltenham, Glos, UK
> email: tim102 at tstinchcombe.freeserve.co.uk
> 
> 
> 
> 
> _______________________________________________
> Synth-diy mailing list
> Synth-diy at dropmix.xs4all.nl 
> http://dropmix.xs4all.nl/mailman/listinfo/synth-diy
> 
>