[sdiy] Shift register sequence period

[Dave Manley]

Tim Stinchcombe wrote:
> 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 

Hi Tim,

I simulated this in verilog and found the length is 262140, which is 
three less than what would be expected for a maximal length polynomial.

The inversion doesn't cause a problem, the feedback on an LFSR can be 
inverted or not.  Whether you invert or not determines the one illegal 
state for a maximal length polynomial.  In the case of xor feedback the 
illegal state is when the shift register is filled with 0's, since 0 xor 
0 is 0, and the state will never change. The is why the maximal length 
is 2^n - 1, the -1 is for the illegal state.

In the circuit as shown the feedback is:

	din = ~(d13 ^ d0) ^ d9.

This is the same as ~(d13 ^ d9 ^d0), which is just an xnor.

~(a^b)^c = ~(a^b^c)

Where d17 is the din flop, and d0 is the last flop.

This feedback doesn't correspond to any of the maximal length
polynomials give here: http://www.ece.cmu.edu/~koopman/lfsr/18.txt
(I'm assuming their tables are correct).  Of course, there are many 
feedback tap arrangements which don't give maximal length and this is 
one of them.

-Dave

P.S. The reset circuit of the resistor and cap is unreliable if power is 
cycled quickly, there really should be a diode across the resistor to 
discharge the cap when the power is turned off.