Xilinx XAPP052 LFSR and its understanding

Hi,
I want to generate a random number in a FPGA chip and in a natural way
it leads to a famous paper Xilinx XAPP052 authored by Peter Alfke:
"Efficient Shift Register, LFSR Counters, and Long Pseudo-Random
Sequence Generators".

I have two problems with the note.

1. I don't understand "Divide-by-5 to 16 counter". I appreciate if
someone explain the Table 2 and Figure 2 in more details.

2. In Figure 5, there is an equation: (Q3 xnor Q4) xor (Q1 and Q2 and
Q3 and Q4).
(Q3 xnor Q4) is required to generate 4-bit LFSR counter. (Q1 and Q2
and Q3 and Q4) is used to avoid a dead-lock situation from happening
when Q1-Q4 = '1'.

Now the 4-bit LFSR counter dead-lock situation should be extended to
any bits long LFSR counter if 2 elements XNOR operation is needed.
Especially in Figure 5 for 63-bit LFSR counter. When all 63-bits are
'1', it would be dead-locked into the all '1' position, because (Q62
xnor Q63) = '1' if both Q63 and Q62 are '1'.  But the situation is
excluded into the equation in Figure 5.

In another words, if a seed data is closing or equal to all '1'
situation, the LFSR is a shorter random number generator than its
claim of a 63-bit length generator. There is no way to exactly know if
a seed data is closing to all '1' situation.

We can add logic equation as 4-bit situation does as follows:
(Q62 xnor Q63) xor (Q1 and Q2 and ... and Q63).

There is a new question: If there is a more clever idea to do the same
things to avoid the 63-bit dead-lock situation from happening?

Weng

Weng Tianxiang <wtxwtx@gmail.com> wrote:
(snip)
 
> In another words, if a seed data is closing or equal to all '1'
> situation, the LFSR is a shorter random number generator than its
> claim of a 63-bit length generator. There is no way to exactly know if
> a seed data is closing to all '1' situation.

There is much written about LFSR, so we don't need to explain
it all here.  Just to be sure you understand, if you start with
a state that isn't all '1' then it will never get to that
state.  (Assuming proper design.)   You do have to be sure
not to start in that state, though.  

-- glen

On Mar 18, 10:04=A0am, Weng Tianxiang <wtx...@gmail.com> wrote:
> Hi,
> I want to generate a random number in a FPGA chip and in a natural way
> it leads to a famous paper Xilinx XAPP052 authored by Peter Alfke:
> "Efficient Shift Register, LFSR Counters, and Long Pseudo-Random
> Sequence Generators".
>
> I have two problems with the note.
>
> 1. I don't understand "Divide-by-5 to 16 counter". I appreciate if
> someone explain the Table 2 and Figure 2 in more details.
>
> 2. In Figure 5, there is an equation: (Q3 xnor Q4) xor (Q1 and Q2 and
> Q3 and Q4).
> (Q3 xnor Q4) is required to generate 4-bit LFSR counter. (Q1 and Q2
> and Q3 and Q4) is used to avoid a dead-lock situation from happening
> when Q1-Q4 =3D '1'.
>
> Now the 4-bit LFSR counter dead-lock situation should be extended to
> any bits long LFSR counter if 2 elements XNOR operation is needed.
> Especially in Figure 5 for 63-bit LFSR counter. When all 63-bits are
> '1', it would be dead-locked into the all '1' position, because (Q62
> xnor Q63) =3D '1' if both Q63 and Q62 are '1'. =A0But the situation is
> excluded into the equation in Figure 5.
>
> In another words, if a seed data is closing or equal to all '1'
> situation, the LFSR is a shorter random number generator than its
> claim of a 63-bit length generator. There is no way to exactly know if
> a seed data is closing to all '1' situation.
>
> We can add logic equation as 4-bit situation does as follows:
> (Q62 xnor Q63) xor (Q1 and Q2 and ... and Q63).
>
> There is a new question: If there is a more clever idea to do the same
> things to avoid the 63-bit dead-lock situation from happening?
>
> Weng

Weng, there is no mystery. All the LFSRs that I described count by (2
exp n)-1, since they naturally will never get into the all-ones state.
If you want them to include that state, you need to decode the state
one prior, use one gate to invert the input, and the same gate gets
you out of it again. The "high" cost is that one very wide gate,
nothing else. LFSRs are well-documented. I had just dug up some old
information that I had generated at Fairchild Applications in the
'sixties.
Peter Alfke

On Mar 18, 8:39=A0pm, Peter Alfke <al...@sbcglobal.net> wrote:
> On Mar 18, 10:04=A0am, Weng Tianxiang <wtx...@gmail.com> wrote:
>
>
>
>
>
> > Hi,
> > I want to generate a random number in a FPGA chip and in a natural way
> > it leads to a famous paper Xilinx XAPP052 authored by Peter Alfke:
> > "Efficient Shift Register, LFSR Counters, and Long Pseudo-Random
> > Sequence Generators".
>
> > I have two problems with the note.
>
> > 1. I don't understand "Divide-by-5 to 16 counter". I appreciate if
> > someone explain the Table 2 and Figure 2 in more details.
>
> > 2. In Figure 5, there is an equation: (Q3 xnor Q4) xor (Q1 and Q2 and
> > Q3 and Q4).
> > (Q3 xnor Q4) is required to generate 4-bit LFSR counter. (Q1 and Q2
> > and Q3 and Q4) is used to avoid a dead-lock situation from happening
> > when Q1-Q4 =3D '1'.
>
> > Now the 4-bit LFSR counter dead-lock situation should be extended to
> > any bits long LFSR counter if 2 elements XNOR operation is needed.
> > Especially in Figure 5 for 63-bit LFSR counter. When all 63-bits are
> > '1', it would be dead-locked into the all '1' position, because (Q62
> > xnor Q63) =3D '1' if both Q63 and Q62 are '1'. =A0But the situation is
> > excluded into the equation in Figure 5.
>
> > In another words, if a seed data is closing or equal to all '1'
> > situation, the LFSR is a shorter random number generator than its
> > claim of a 63-bit length generator. There is no way to exactly know if
> > a seed data is closing to all '1' situation.
>
> > We can add logic equation as 4-bit situation does as follows:
> > (Q62 xnor Q63) xor (Q1 and Q2 and ... and Q63).
>
> > There is a new question: If there is a more clever idea to do the same
> > things to avoid the 63-bit dead-lock situation from happening?
>
> > Weng
>
> Weng, there is no mystery. All the LFSRs that I described count by (2
> exp n)-1, since they naturally will never get into the all-ones state.
> If you want them to include that state, you need to decode the state
> one prior, use one gate to invert the input, and the same gate gets
> you out of it again. The "high" cost is that one very wide gate,
> nothing else. LFSRs are well-documented. I had just dug up some old
> information that I had generated at Fairchild Applications in the
> 'sixties.
> Peter Alfke- Hide quoted text -
>
> - Show quoted text -

Hi Peter,
Thank you.

The reason I want to exclude the dead-lock situation is that in my
project, I use the random number generator to generate random number
to detect design errors. If there is an error, my design will detect
it. But if all numbers generated are the same from some point, there
is no error generated and my testing is just waiting time, giving a
false correct indicator.

But many zeros in seed may guarantee that the situation of all '1'
will never happen.

Weng

>But many zeros in seed may guarantee that the situation of all '1'
>will never happen.

What are you using for a seed?  The whole register?  If so, the
only seed that will get stuck in a loop is all 1s itself, so
just "don't do that".

Or mask off one of the bits in hardware.  Any one, it doesn't
matter.  Just something to make sure the whole register
can't get loaded with all 1s.


-- 
These are my opinions, not necessarily my employer's.  I hate spam.

Weng Tianxiang <wtxwtx@gmail.com> wrote:
 
> The reason I want to exclude the dead-lock situation is that in my
> project, I use the random number generator to generate random number
> to detect design errors. If there is an error, my design will detect
> it. But if all numbers generated are the same from some point, there
> is no error generated and my testing is just waiting time, giving a
> false correct indicator.
 
> But many zeros in seed may guarantee that the situation of all '1'
> will never happen.

Any zeros in the seed will guarantee that it never happens.

The only way to get to the all ones state is to start there.
(Well, there is also cosmic rays going through and changing
the bits, but if that happens you have other problems, too.)

That does assume a properly designed LFSR.  If you randomly
choose taps it is likely that you get one with short cycles.

-- glen

On Mar 18, 11:39=A0pm, Peter Alfke <al...@sbcglobal.net> wrote:
> On Mar 18, 10:04=A0am, Weng Tianxiang <wtx...@gmail.com> wrote:
>
>
>
> > Hi,
> > I want to generate a random number in a FPGA chip and in a natural way
> > it leads to a famous paper Xilinx XAPP052 authored by Peter Alfke:
> > "Efficient Shift Register, LFSR Counters, and Long Pseudo-Random
> > Sequence Generators".
>
> > I have two problems with the note.
>
> > 1. I don't understand "Divide-by-5 to 16 counter". I appreciate if
> > someone explain the Table 2 and Figure 2 in more details.
>
> > 2. In Figure 5, there is an equation: (Q3 xnor Q4) xor (Q1 and Q2 and
> > Q3 and Q4).
> > (Q3 xnor Q4) is required to generate 4-bit LFSR counter. (Q1 and Q2
> > and Q3 and Q4) is used to avoid a dead-lock situation from happening
> > when Q1-Q4 =3D '1'.
>
> > Now the 4-bit LFSR counter dead-lock situation should be extended to
> > any bits long LFSR counter if 2 elements XNOR operation is needed.
> > Especially in Figure 5 for 63-bit LFSR counter. When all 63-bits are
> > '1', it would be dead-locked into the all '1' position, because (Q62
> > xnor Q63) =3D '1' if both Q63 and Q62 are '1'. =A0But the situation is
> > excluded into the equation in Figure 5.
>
> > In another words, if a seed data is closing or equal to all '1'
> > situation, the LFSR is a shorter random number generator than its
> > claim of a 63-bit length generator. There is no way to exactly know if
> > a seed data is closing to all '1' situation.
>
> > We can add logic equation as 4-bit situation does as follows:
> > (Q62 xnor Q63) xor (Q1 and Q2 and ... and Q63).
>
> > There is a new question: If there is a more clever idea to do the same
> > things to avoid the 63-bit dead-lock situation from happening?
>
> > Weng
>
> Weng, there is no mystery. All the LFSRs that I described count by (2
> exp n)-1, since they naturally will never get into the all-ones state.
> If you want them to include that state, you need to decode the state
> one prior, use one gate to invert the input, and the same gate gets
> you out of it again. The "high" cost is that one very wide gate,
> nothing else. LFSRs are well-documented. I had just dug up some old
> information that I had generated at Fairchild Applications in the
> 'sixties.
> Peter Alfke

Depending on the LFSR construction, you may be able to use a
counter instead of a "wide gate".  For example, if your LFSR
is the type where the XOR gates feed only bit 1, you just need
to detect N successive 1's going into bit 1 (where N is the
LFSR length) to find the state where all bits go high.  For
a very long LFSR this approach generally uses much less
resources than the wide gate.  For a "safe mode" LFSR, you
would detect N-1 1's in a row and inject a 0 into bit 1
on the next cycle to prevent lock-up.

Regards,
Gabor

On Mar 19, 12:46=A0am, glen herrmannsfeldt <g...@ugcs.caltech.edu>
wrote:
> Weng Tianxiang <wtx...@gmail.com> wrote:
> > The reason I want to exclude the dead-lock situation is that in my
> > project, I use the random number generator to generate random number
> > to detect design errors. If there is an error, my design will detect
> > it. But if all numbers generated are the same from some point, there
> > is no error generated and my testing is just waiting time, giving a
> > false correct indicator.
> > But many zeros in seed may guarantee that the situation of all '1'
> > will never happen.
>
> Any zeros in the seed will guarantee that it never happens.
>
> The only way to get to the all ones state is to start there.
> (Well, there is also cosmic rays going through and changing
> the bits, but if that happens you have other problems, too.)
>
> That does assume a properly designed LFSR. =A0If you randomly
> choose taps it is likely that you get one with short cycles.
>
> -- glen

glen,
"Any zeros in the seed will guarantee that it never happens."

Your claim is wrong.

My LFSR is based on the famous paper Xilinx XAPP052 authored by Peter
Alfke:
"Efficient Shift Register, LFSR Counters, and Long Pseudo-Random
Sequence Generators". For a 63-bit LFSR, XNOR operation is done on its
62th-bit and 63th-bit to generate first-bit input.

Actually we don't have to see what structure of LFSR is.

If a LFSR claims to have a good behavior, it is natural for it to
generate all '1' situation. The one before it certainly has '0' in it.

Weng

On Mar 19, 5:52=A0am, gabor <ga...@alacron.com> wrote:
> On Mar 18, 11:39=A0pm, Peter Alfke <al...@sbcglobal.net> wrote:
>
>
>
>
>
> > On Mar 18, 10:04=A0am, Weng Tianxiang <wtx...@gmail.com> wrote:
>
> > > Hi,
> > > I want to generate a random number in a FPGA chip and in a natural wa=
y
> > > it leads to a famous paper Xilinx XAPP052 authored by Peter Alfke:
> > > "Efficient Shift Register, LFSR Counters, and Long Pseudo-Random
> > > Sequence Generators".
>
> > > I have two problems with the note.
>
> > > 1. I don't understand "Divide-by-5 to 16 counter". I appreciate if
> > > someone explain the Table 2 and Figure 2 in more details.
>
> > > 2. In Figure 5, there is an equation: (Q3 xnor Q4) xor (Q1 and Q2 and
> > > Q3 and Q4).
> > > (Q3 xnor Q4) is required to generate 4-bit LFSR counter. (Q1 and Q2
> > > and Q3 and Q4) is used to avoid a dead-lock situation from happening
> > > when Q1-Q4 =3D '1'.
>
> > > Now the 4-bit LFSR counter dead-lock situation should be extended to
> > > any bits long LFSR counter if 2 elements XNOR operation is needed.
> > > Especially in Figure 5 for 63-bit LFSR counter. When all 63-bits are
> > > '1', it would be dead-locked into the all '1' position, because (Q62
> > > xnor Q63) =3D '1' if both Q63 and Q62 are '1'. =A0But the situation i=
s
> > > excluded into the equation in Figure 5.
>
> > > In another words, if a seed data is closing or equal to all '1'
> > > situation, the LFSR is a shorter random number generator than its
> > > claim of a 63-bit length generator. There is no way to exactly know i=
f
> > > a seed data is closing to all '1' situation.
>
> > > We can add logic equation as 4-bit situation does as follows:
> > > (Q62 xnor Q63) xor (Q1 and Q2 and ... and Q63).
>
> > > There is a new question: If there is a more clever idea to do the sam=
e
> > > things to avoid the 63-bit dead-lock situation from happening?
>
> > > Weng
>
> > Weng, there is no mystery. All the LFSRs that I described count by (2
> > exp n)-1, since they naturally will never get into the all-ones state.
> > If you want them to include that state, you need to decode the state
> > one prior, use one gate to invert the input, and the same gate gets
> > you out of it again. The "high" cost is that one very wide gate,
> > nothing else. LFSRs are well-documented. I had just dug up some old
> > information that I had generated at Fairchild Applications in the
> > 'sixties.
> > Peter Alfke
>
> Depending on the LFSR construction, you may be able to use a
> counter instead of a "wide gate". =A0For example, if your LFSR
> is the type where the XOR gates feed only bit 1, you just need
> to detect N successive 1's going into bit 1 (where N is the
> LFSR length) to find the state where all bits go high. =A0For
> a very long LFSR this approach generally uses much less
> resources than the wide gate. =A0For a "safe mode" LFSR, you
> would detect N-1 1's in a row and inject a 0 into bit 1
> on the next cycle to prevent lock-up.
>
> Regards,
> Gabor- Hide quoted text -
>
> - Show quoted text -

Hi Gabor,
Your method is what I am interested in and your response is a hit.

Your method at most generates n same data (n =3D length of LFSR). For my
project purpose, it is a full fit.

But I will change a little bit to your idea to make it generate no
same data.

!!!Thank you very much for your bright idea!!!

Later I will post my coding for it: the code should use the least
amoung of Xilinx FPGA resources to do the 63-bit LFSR:
a 63-bits shift register with initial value.

Weng

Weng Tianxiang <wtxwtx@gmail.com> wrote:
(snip, I wrote)
> "Any zeros in the seed will guarantee that it never happens."
 
> Your claim is wrong.
 
> My LFSR is based on the famous paper Xilinx XAPP052 authored by Peter
> Alfke:
> "Efficient Shift Register, LFSR Counters, and Long Pseudo-Random
> Sequence Generators". For a 63-bit LFSR, XNOR operation is done on its
> 62th-bit and 63th-bit to generate first-bit input.

A good N bit LFSR has a 2**N-1 cycle and a 1 cycle.  
As I understand it, the 1 cycle for these are supposed to
be the all 1 state.  Whichever cycle you start in you
stay in, and that should not be the 1 cycle for good random
numbers.
 
> Actually we don't have to see what structure of LFSR is.
 
> If a LFSR claims to have a good behavior, it is natural for it to
> generate all '1' situation. The one before it certainly has '0' in it.

If the all '1' situation is a 1 cycle then the one before
it is also all '1's.  It isn't hard to compute what the one
before is, and the one after.

The description in "Numerical Recipes" includes some of
the math, but is reasonably readable, too.  You might look
at that one.

-- glen