Talk:Linear feedback shift register

From Wikipedia, the free encyclopedia

This is the talk page for discussing improvements to the Linear feedback shift register article.
Article policies

Contents

[edit] Animation

if the animation is wrong maybe we should eliminate it.

Agreed and done. Cuddlyable3 (talk) 21:13, 3 January 2008 (UTC)

[edit] Discursion

Hi, I think the paragraph submitted by 69.238.5.10 on 19:08, 22 June 2006 is not meant to be part of the content for this article. Instead, the submitter is referring to an error in the animation image.

"The animation below is erroneous. In one stage of the cycle the values of the taps do not correspond to the values stored in bit positions 14 and 16. The values of the taps rather than the values in the bit positions are then used to calculate the code, thus propagating the error into the feedback. This occurs when the last 3 bits are 100."

Matt Crypto, can you update the animation and republish? -daniel.kho

Oops, silly mistake, sorry about that. I can't access the sources images right now, but I'll try and get to them shortly. — Matt Crypto 13:22, 14 September 2006 (UTC)

Maybe Rob.derosa is correct. The runlength (or pattern length) of a 6-bit LFSR should be 26 − 1 = 63 rather than 26 − 1 = 32.

"In one period of a maximal LFSR, 2n − 1 runs occurs (for example, a six bit LFSR will have 63 runs)."

I suggest introducing hyphenation for clarity:

"In one period of a maximal LFSR, 2n − 1 runs occurs (for example, a six-bit LFSR will have 63 runs). Exactly 1 / 2 of these runs will be one-bit long, 1 / 4 will be two-bit long, up to a single run of zeroes (n − 1)-bit long, and a single run of ones n-bit long." -daniel.kho

No. In one period of a maximal LFSR (which is 2^n - 1) it produces 2^n-1 BITS. You cannot have 2^n-1 RUNS in 2^n-1 BITS (well, unless you have only 1 bit runs: "010101010101010101...", which doesn't happen). I suppose you will have 2^(n-1) runs? —Preceding unsigned comment added by 195.212.29.163 (talk • contribs)

[edit] Where is the period of maximal LFSR stated?

Hi, I don't see where it is stated that the LFSR maximal period is 2^N,with N the number of state bits, am I missing something here?

See the table I added. The maximal period is 2^N - 1. Cuddlyable3 (talk) 21:15, 3 January 2008 (UTC)

[edit] Galois source code

I recently cleaned up the C source code for the Galois LFSR. However, I am considering removing everything but the actual implementation of the LFSR (2-3 lines of code), because I think most people would find that more useful (and less confusing). I am also unsure how "optimized" the code should be. Any opinions? -Ufretin 14:40, 16 January 2007 (UTC)

I guess it depends on the usage of the LFSR, but it doesn't seem that useful that the example code still generates one bit at a time. If you're looking for a multi-bit result, you generally want to avoid values that are obviously related by a bit shift -- two examples being generating random audio samples and bi-level noise patterns. A better way to take advantage of the Galois form is to keep the multiple bit shifts, but generate multiple bits at a time, i.e.:

 // generate 8 bits at a time with 2^16-1 period
 v = ((v << 8) + (((v >> 3) ^ (v >> 4) ^ (v >> 5) ^ (v >> 8)) & 0xff)) & 0xffff;

I think a Don Lancaster book once described this as "running the LFSR backwards," which is to me a more intuitive description, but not one that is that readily discernible from the existing diagram. 24.4.102.10 08:12, 22 August 2007 (UTC)

[edit] The tap values in a maximal LFSR will be relatively prime

Is there a proof for this statement? How shall the tap values be taken? The polynomial 0133 is a maximum length polynomial, if it is written as x^6 + x^4 + x^3 + x^1 + 1, the tap values would contain 6 and 3, which have 3 as a common factor. 84.161.181.208 19:48, 28 January 2007 (UTC)

I just tested a 10-bit LFSR (software implementation) with taps at position 3, 6, and 10. 3 and 6 are not relatively prime, nor are 6 and 10, yet the LFSR had a period of 1027, which is 2^10-1, so it is maximal. More evidence that the tap values need not be relatively prime. Primarscources 03:34, 5 August 2007 (UTC)

Heck, 1027 is 2^10+3, so it's supramaximal!

Primarscources has posted original "research" with an incorrect report of his LFSR period. The decent thing to do is to remove such disinformation. Cuddlyable3 23:35, 1 December 2007 (UTC)

Hey, it was a typo. Also, I selected the taps incorrectly. But this time I've got actual proof! A 10-bit LFSR with taps at positions 4, 5, 8, and 10 is maximal, with a period of 1023. Clearly 4, 8, and 10 are not relatively prime. Can someone confirm my result? Primarscources 04:13, 2 December 2007 (UTC)

I confirm that LFSR period = 1023.Cuddlyable3 21:05, 3 December 2007 (UTC)
You've misunderstood what they mean by relatively prime. The entire set must be relatively prime with respect to each other, not just pairwise. 4, 5, 8, and 10 are not relatively prime. See the distinction in http://en.wikipedia.org/wiki/Relatively_prime between a group of numbers being relatively prime and being pairwise relatively prime. If all taps are divisible by some number a, then the polynomial will be divisible by x^a + 1, and hence obviously not be primitive. This is the same principle that forces the number of taps to be even (or else x + 1 divides the polynomial). —Preceding unsigned comment added by 70.110.22.198 (talk) 14:47, 29 April 2008 (UTC)

[edit] Polynomials

I believe the section "Polynomials for Maximal LFSRs" should be removed. As it is stated a few line above this section, any even (2 or 4) number of taps can produce the maximal LFSRs. If number of taps increased, the LFSR produces sequence of numbers which is harder to be guessed. —Preceding unsigned comment added by 66.104.249.162 (talk) 02:36, 29 January 2008 (UTC)

This claim is wrong: "any even (2 or 4) number of taps can produce the maximal LFSRs." The error lies in the word "any" which comes from the anonymous user, not the article. Finding which 2 or 4 taps give the maximal sequence demanded an intensive search which resulted in the confirmed table of polynomials. In each case, the minimum number of taps was sought.Cuddlyable3 (talk)

[edit] Simulated in simulated C

From [1]:

Below is example of 32-bit maximal period Galois LFSR simulated in C:
 unsigned int lfsr = 1; 
 for (;;)
   lfsr = (lfsr >> 1) ^ (-(signed int)(lfsr & 1) & 0xd0000001u); /* taps 32 31 29 1 */

Doesn't look like any C I know. The cast from unsigned to signed, negation and back produces implementation-defined results according to the C specification. This should be fixed — if I knew how. ~ Jafet (spam) 02:49, 6 January 2008 (UTC)

-(signed int) changes the MSB bit. —Preceding unsigned comment added by 66.104.249.162 (talk) 02:42, 29 January 2008 (UTC)

No. The MSB is unchanged by the conversion. I still believe that the result is well-defined, although I am not a C programmer. After negation, the temporary signed int will hold either -1 or 0. Converting back to unsigned int:
In the case of 0, 6.3.1.3.p1 applies (so the result is 0u). In the case of -1, 6.3.1.3p2 applies, and the result is the mathematical result of ((-1) + (UINT_MAX + 1)), which is UINT_MAX. If you remove the (redundant) cast the result should be the same. Please let me know if I've overlooked something. Either way I will make clarifying changes to the article Ufretin (talk) 06:20, 29 January 2008 (UTC)
I see. ~0u would be more correct than -1, however. ~ Jafet (spam) 07:11, 16 February 2008 (UTC)

The following should always compile and is independent from signed/unsigned conversions A. de Muijnck (talk) 13:04, 31 March 2008 (UTC):

  lfsr = (lfsr >> 1) ^ ((lfsr & 1)? 0xd0000001u: 0); /* taps 32 31 29 1 */
It does, but the code is likely to be slower than the non-conditional one.Ufretin (talk) 14:19, 31 March 2008 (UTC)

[edit] Tap Wiring Configuration

The article includes "Galois LFSRs do not concatenate every tap to produce the new input (the XOR'ing is done within the LFSR and no XOR gates are run in serial, therefore the propagation times are reduced to that of one XOR rather than a whole chain), thus it is possible for each tap to be computed in parallel, increasing the speed of execution."

True; but the Fibonacci LFSR diagram shows the input generated by the chain (((16 XOR 14) XOR 13) XOR 11) which maximises the propagation delay to 3 units. There is no need to use a chain configuration. If the gates were connected as the tree ((16 XOR 14) XOR (13 XOR 11)) the delay would be only 2 units.

More generally, for N taps a chain configuration as shown delays by N-1 units, whereas a tree configuration delays by Ceil(Log2(N)) units, which is smaller whenever N>3.

You are right about reducing the delay in the Fibonacci configuration from 3 to 2 XOR gates. However that is all the gates one ever needs for maximal count. Cuddlyable3 (talk) 08:23, 9 June 2008 (UTC)

In an implementation using MSI ICs, I think that the XORing could be done with a parity generator chip. It would at least keep the connections between XORs internal, which would be quicker; and it could maybe introduce internally a possibly-faster scheme such as ROM lookup.

There is nothing much faster than an LSI XOR gate (with gate(s) to spare in the package!). Cuddlyable3 (talk) 08:23, 9 June 2008 (UTC)

I don't suppose that it makes very much difference.

By the way

  • I find the diagrams hard to read; please change the red to something much brighter.
  • The first and second paras of the intro describe Fibonacci but exclude Galois. Perhaps Galois is not really a LFSR, as the SR is discontinuous.
  • The article does not appear to say whether or not it is always possible, with a given length N, to obtain a maximum-length sequence with only a single XOR. http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr/8stages.txt implies that it is not.
  • The link in the Table did not work.

82.163.24.100 (talk) 12:56, 8 June 2008 (UTC)

By the way
  • noted
  • be bold and edit! Fibonacci uses feedback, Galois uses feedforward.
  • all the tabulated registers use the minimum numbers of taps. I know because I searched.
  • I fixed the link.
User 82.163.24.100 please excuse my interpolating answers to multiple points within your post above. I suggest you get a Wikipedia account and sign your posts. Cuddlyable3 (talk) 08:23, 9 June 2008 (UTC)
Interpolation was appropriate. I will only get an account if/when I'm sufficiently familiar with the system; and I will then use my real name as I do elsewhere. I only edit articles where I am really certain; normally, I prefer the check of having someone else do it.
Re the need for only 2 or 4 taps - it would be nice to see whether that's been proved for all N, or just tested for many values.
Re the aforesaid XILINX link - it cites Scholefield's paper. Interesting, since he gave me a copy and I've actually found it today. It shows a scheme which at first sight may be a Fibonacci/Galois hybrid.
82.163.24.100 (talk) 15:36, 9 June 2008 (UTC)
I guess you have P.H.R Scholefield, "Shift Registers Generating Maximum-Length Sequences", Electronic Technology, pp. 389-394, 10-1960. I don't. Another on-line cornucopian reference: [2]
I agree a proof that 2 or 4 taps suffice to give maximal sequence for any N registers would be nice if possible - for theoreticians because we engineers can already make as long maximal registers as we shall probably ever need.
I have not checked the taps in the Xilinx table for 12 13 14 16 or 19 bits nor do I see any symmetrical relationship between them and the taps in Wikipedia that I know do work. I think there is an open question whether the pattern of ALL maxima tap arrangements for ALL register lengths is chaotic, prime-based or systematic in a way that yields the above proof.Cuddlyable3 (talk) 09:04, 10 June 2008 (UTC)