LFSR but uses inverse of 17th bit?

[NivagSwerdna]

I've been looking at the architecture of several old arcade games and am currently musing about star field generators.... 

The central principle of this generator is a 17-bit LFSR made up of two 8 bit shift registers and a flip-flop... so far so good.

The Feedback for the circuit is taps 5 and 17... again all good

But I notice that the input to the feedback XOR is tap 5 but NOT tap 17

Maybe this is an adaptation that allows initialisation with all zeros?  Is it still maximal length?

Thanks

(Seems to repeat after 131071 so looks maximal)

PS
I did a bit of reading and found documentation suggesting using an XNOR but this isn't quite the case here since only one input of the XOR is inverted? Hm... writing out the truth table... a XOR with a NOT on one input has the same table as a XNOR... maybe that's it?)

[Nusa]

Yup. In logic terms, an XOR has an even number of inverted inputs+output. A XNOR has an odd number of inverted inputs+output.

As for how your circuit functions, I suggest you manually step through what the shift register contents will be until you understand the pattern and how it repeats. Assume an initial state of 0's, since all the IC's have a clear line. Then observe that the contents of the shift register are used in parallel to do something elsewhere on the schematic.

You should answer some of your own questions, asked and unasked, along the way.

[NivagSwerdna]

Yup. In logic terms, an XOR has an even number of inverted inputs+output. A XNOR has an odd number of inverted inputs+output.

So it is equivalent to a 17bit LFSR with taps at 5, 17 and the zero state works as part of the sequence due to the XNOR.  Very clever.
It's a starfield generator, you get a star if the least significant 8 bits are zero with the colour of the star dependent on higher order bits.
Thanks.

[NivagSwerdna]

Exorcising my old thread...

So I am looking at a hardware implementation of an LFSR...



Now this is a 17bit shift... 8 bits in each 74LS164 and another bit in the 74LS74

What I don't understand is how in the circuit tap comes from 12 if you count the XOR input at bit 0 (complement)

Depending on where you look... e.g. https://en.wikipedia.org/wiki/Linear-feedback_shift_register it suggests using taps 17 and 14

I assumed that in order to get a maximal count you would need to follow the recipe i.e. 17,14

So it seems there are actually several possible taps that give Maximal with 17bits?

It seems the tap can be at 3, 5, 6, 11, 12, or 14?  Weird?

[ejd.pol]

Hi,

LFSRs behave according to some wonderful mathematics. No, it is not weird to have multiple feedback configurations that generate maximal cycles.
And you have been looking only at feedback configurations with only two taps! There are many more maximal configurations with three taps or more.
I can't tell you how to _derive_ or _predict_ maximal configurations, but you can easily check (and from what you wrote, you know how to do that).

Cheers, Evert-Jan

 

[coppice]

There are a number of feedback patterns on a chain of dividers used for random numbers, CRCs, scramblers and so on which work well. Most potential patterns don't work at all, or have poor behaviour. That might be bias in a PRBS sequence, or a lack of self-synchronisation for a data scrambler.There are a number of more complex patterns, like the Galois approaches, where logic is inserted between the divider stages. Some of those work well, but most do not. Nobody has a really solid way of deriving from first principals which camp any feedback pattern will fall into. Even for patterns which give the general characteristic you want, like maximal length for a PRBS generator, many will produce clear patterns in some parts of the sequence, so they are weak as PRBS generators. If you have a sequence that behaves well for your needs, be happy.