[sdiy] Shift register sequence period

[Eric Brombaugh]

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

Interesting little problem. I don't quite understand why the inversion 
in the feedback calculation would make the sequence non-linear (not even 
sure what non-linear means in this sense) - seems to me that it just 
gives you a different sequence. Looking through the circuit explanation 
on Ken's site it's obvious that it's just there to insert a transient 
into the register to get it going - the RC time constant is kind of like 
a reset pulse.

Not being much for theoretical approaches I cranked out a quick C 
program to measure the length of the sequence. After a few milliseconds 
of execution time it came up as 262140 - 4 less than 2^18.

Here's the C code:

#include <stdio.h>

int main(int argc, char **argv)
{
	unsigned long sr, newbit;
	unsigned long cnt;
	
	cnt = 0;
	
	sr = 1;
	
	do
	{
		newbit = (sr >> 8) ^ ~((sr >> 4) ^ (sr >> 17));
		sr = (sr << 1) | (newbit & 1);
		cnt++;
	}
	while((sr & 0x3ffff) != 1);
	
	printf("Count = %d\n", cnt);
}

So it seems your initial instinct that the inversion just shortens the 
sequence was correct. Now if you want firm theoretical reason _why_ that 
is then you'll have to stick t' yer book larnin'. :)

Interestingly enough, removing the inversion shortens the sequence to 
2^17-2. Using different start/end criteria can lead to degenerate cases 
with shorter lengths as well. Odd...

Eric