0
\$\begingroup\$

can you explain me in simple words how does a linear feedback shift register work for generating a code?

Consider for instance this scheme: enter image description here

If I have understood it correctly, each block is a D Flip Flop whose output bit becomes equal to its input bit after a clock cycle.

So, let's suppose the first sequence of bit equal to 1011

  1. How do we decide this sequence? It is the random sequence which is generated when flip flops are activated?.

At the input of M1 there is 1 + 1 + 1 = 1 (in binary arithmetic). So at the next clock cycle we will have: 1101. At the input of M1 there is 1 + 0 + 1 = 0. So at the next clock cycle we will have 0110 etc.

  1. Which is the number of coded bits we see at the output?

  2. Does it generate a periodic sequence? If yes, how?

\$\endgroup\$
2
  • \$\begingroup\$ There is a single forbidden state for a maximal length implementation; there is a great deal of information available online. It can start from any other state. \$\endgroup\$ – Peter Smith Dec 8 '19 at 16:57
  • \$\begingroup\$ Does the term "Galois field" mean anything to you? \$\endgroup\$ – The Photon Dec 8 '19 at 17:18
0
\$\begingroup\$

Let's suppose the first sequence of bit equal to 1011 (first question: how do we decide this sequence? It is the random sequence which is generated when flip flops are activated?

Normally you'd provide a SET or RESET input to the flip-flops to ensure they start up in the state you want.

For an LFSR using XOR gates, any starting state besides all-0's can be used. If using XNOR gates, then any starting state besides all-1's can be used.

The second question is: which is the number of coded bits we see at the output?

As drawn, you'd take one of the flip-flop outputs as your LFSR output. The output would be only one bit.

There are ways to arrange to take more than one bit at a time as output, but they require changes to the logic.

Third question: does it generate a periodic sequence?

Consider

  1. Four flip-flops can only encode \$2^4=16\$ different states.

  2. The all-zeros state is not allowed (because 0 XOR 0 = 0, this state won't cause any change on the next cycle)

  3. The state transitions are entirely deterministic, so we know if we are in (for example) state 0110, the next state will always be 1011.

Therefore the system must repeat its sequence of states at most every 15 cycles. And its output will be a periodic signal with period no more than \$15 T\$ where \$T\$ is the clock period.

The trick is to choose how to connect the XOR gates so that the state sequence uses all 15 possible states and gives the maximum period. Rather than work it out from scratch, tables are widely available giving the required "tap" positions for various LFSR lengths.

\$\endgroup\$
3
  • \$\begingroup\$ Another question: is there an algorithm (or method) to understand which is the input sequence that, for a given structure, let us to use all the available flip flop states? \$\endgroup\$ – Kinka-Byo Dec 12 '19 at 17:28
  • \$\begingroup\$ @Kinka-Byo, not without going into Galois Field theory which I mentioned in a comment on the question. And I'm not claiming I even understand the Galois Field theory or could explain it to somebody else. \$\endgroup\$ – The Photon Dec 12 '19 at 17:31
  • \$\begingroup\$ Perfect, thank you very much. \$\endgroup\$ – Kinka-Byo Dec 12 '19 at 17:45
0
\$\begingroup\$

Simple Words.

It is a binary sum of "certain" bits in a shift register of length N to give some undefined cycle bit pattern. There is an optimal configuration of feedback which has certain math properties of a flat freqeuncy response or even spectral density of frequencies (with constaints). (not obvious with only 4 bits) This is used for bit pattern generators and cyphers.

These called Max-length pseudo-random sequence generators. Your example is not one of them.

You are showing a non-inverted XOR symbols so we know that a forbidden starting point is all 0's and would never change.

So one starts with PRESET or all 1's or adds an inverter to the feedback, to allow a starting with a master RESET or all 0's.

This requirement for choosing the polarity of feedback (+/-) is necessary to determine the forbidden state.

N bits determines the maximum number of clock cycles for the repeating "Pseudo-Random" (PR) pattern". Since it repeats, it is not truly random.

There is a range of different cycle patterns for any random connection of feedback . There may be short or long cycles. Your schematic is not ideal. , for which I have taken the liberty to simulate.

Details

Monic Polynomials which can be used to express the stages for feedback terms for a maximal length random sequence. Consider the + 1 as an odd parity term with negative feedback or an inverted XOR sum. $$ PRBS.4 = x^{{4}}+x^{{3}}+1 $$

. $$ PRBS.7 = x^{{7}}+x^{{6}}+1 $$

$$ PRBS.9 = x^{9}+x^{5}+1 $$

$$ PRBS.11 = x^{11}+x^{9}+1$$

$$ PRBS.15 = x^{{15}}+x^{{14}}+1$$

$$ PRBS.20 = x^{20}+x^{3}+1$$

$$ PRBS23 = x^{{23}}+x^{{18}}+1$$

$$ PRBS31 = x^{{31}}+x^{{28}}+1$$ etc

Your schematic is wrong for maximal length and has taps on 1,3,4 instead of 3,4 shown above in 1st equation in reverse order.

My simulation has a (mouse) switch ( ignore floating input for simplicity) to go between your schematic and the maximal length sequence for N=4 bits. Note that this becomes a divide by 15 counter on the AND gate pulse output thus 100Hz /15= 6.66 Hz a the Fourier spectrum of one of the outputs is shown in Red. With all the harmonics as expected. This would be a smoother flat spectrum with more bits e.g. N=15 or N=31

enter image description here

But are special conditions to produce a maximal length pseudo-random sequence generated (ML-PRSG). This determines the n stage that need to be added for feedback. This pattern length is \$2^N -1\$ clock cycles.

If you are guessing you could end up with a shorter length sequence , which is not very useful. ;)

Here is a list of taps to the polynomials represented by each stage of delay using a shift register of D FF's. , some of which are above.

REFS:
https://en.wikipedia.org/wiki/Pseudorandom_binary_sequence#Practical_implementation https://en.wikipedia.org/wiki/Linear-feedback_shift_register
https://en.wikipedia.org/wiki/Pseudorandom_number_generator

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.