[sdiy] Shift register sequence period

[Tim Stinchcombe]

Hi list,

> Rest assured if I do get it sussed, I will let the list know 
> (that's if anyone else is still following this...!?).

Well I finally understand this to my satisfaction, so for the record, here
are the (rather terse and) gory details!

As the circuit stands, yes it is linear, but the effect of the inverter (in
this case) is to make it 'inhomogeneous', that is we get an awkward '+1'
term: this stops us writing the characteristic polynomial, because (from the
book I'm mostly referring to, Lidl & Niederreiter, 'Intro to Finite Fields &
their Appns') the poly is only defined for the homogeneous case.

>From the circuit, the recurrence relation is:

s_(n+18) = s_(n+13) + s_(n+9) + s_n + 1

where the 's_n' are the bits, and the inversion gives the '+1', being the
'inhomogeneous' part. Fortunately there is a simple way to make a k'th order
inhomogeneous recurrence relation into a (k+1)'th order homogeneous one
(page 196 L+N) - write the 'n+1' version of the above, then subtract the two
(or add, it's binary, so no difference), so the '+1's will cancel. This then
gives

s_(n+19) = s_(n+18) + s_(n+14) + s_(n+13) + s_(n+10) + s_(n+9) +  s_(n+1) +
s_n

from which we *can* extract the polynomial:

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

which is what I reported I got earlier from the Berlekamp-Massey algorithm.
This factorizes as: 

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

The order of the factor (1+x)^3 turns out to be 4 (L+N Thm 3.8 p 79), and by
getting Mathematica to factor x^65535+1, giving 4115 factors in total, I
established the larger factor *is* one of these, and so the order of the
large factor is 65535 = 2^16 -1. The period of the sequence is then the
product of these orders = 4*(2^16-1) = 2^18-4 =262140, as previously
established from direct calculation.

In the original circuit, the other 4 states form a periodic sequence on
their own:

011001100110011001
110011001100110011
100110011001100110
001100110011001100

so both the all-1s and all-0s states are in the longer sequence. Even if we
assume that it is equiprobable that any given stage in the register can be
either a 0 or 1 at start-up, it is highly unlikely we'd get into this cycle,
and I'm guessing they're more likely to be mostly 1s or mostly 0s, but not a
mixture, so this makes this cycle even more unlikely. The length-19
homogeneous equivalent presumably has other cycles that the shorter register
cannot generate, because it does have more states, but I'm not interested in
these anyway.

I also discovered the circuit turns up in quite a few places: Barry Klein's
book mentions it, and says it's used in the Maplin 3800 & 5600, which must
equate to the ETI 3800 & 5600, as it is in those too; also the ETI 4600; the
Elektor Formant; plus the others I mentioned before. Which came first is
anybody's guess.

Thanks to those who chipped in with useful thoughts, insights and
calculations.

Tim
__________________________________________________________
Tim Stinchcombe 

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