Talk:Linear-feedback shift register

16-bit Fibonacci LFSR wrongly tapped

The register should have been tapped at location 15 (consider 1-16 numbering), but it is tapped at location 14. Even the polynomial equation mentions it to be 15. — Preceding unsigned comment added by 202.83.19.101 (talk) 06:53, 27 May 2016 (UTC)

Why can't we store?

"A list of alternative maximal-length polynomials for shift-register lengths 4-32 (beyond which it becomes unfeasible to store or transfer them) can be found here"

Uh, why does it become unfeasable? It's just a list of exponents, and later we link to a document that contains them up to 168! This seems contradictory or it's unclear and I'm misinterpreting it. — Preceding unsigned comment added by 208.54.80.175 (talk) 22:13, 2 March 2013 (UTC)

Full lists of alternative exponents become infeasible to store because the number of alternatives increase quickly. There are 67,108,864 32-bit alternative polynomials in the 186MB file 32.dat.gz at http://users.ece.cmu.edu/~koopman/lfsr/index.html . Presumably the 33 bit list of alternatives would be another 180MB file. The https://web.archive.org/web/20161007061934/http://courses.cse.tamu.edu/csce680/walker/lfsr_table.pdf is has a table with polynomials up to 786 plus for 1024, 2048 and 4096. Drf5n (talk) 01:38, 5 January 2022 (UTC)

Animation

if the animation is wrong maybe we should eliminate it.

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

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 $2^{6}-1=63$ rather than $2^{6-1}=32$.

"In one period of a maximal LFSR, $2^{n}-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, $2^{n}-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)

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)

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)

Could someone figure out which book that was in, and add it as a citation to this article? (Possibly the "TTL Cookbook" or "CMOS Cookbook" ?) --DavidCary (talk) 17:28, 31 July 2013 (UTC)

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://wiki.riteme.site/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)

I really think this statement about taps having to be relatively prime is too vague, and perhaps not correct. It would be better to say that proper polynomial (I only know how to define it for the Galios structure, as defined below) must be primitive. DMJ001 (talk) 00:21, 25 March 2009 (UTC)

The section is quite generally a mess and even the set of tabs is not well defined. E.g. the tabs of the feedback polynomial $x^{16}+x^{14}+x^{13}+x^{11}+1$ is [16, 14, 13, 11, 1] in the intro, then [16, 14, 13, 11] when the editors claim that the number of tabs must be even and finally [16, 14, 13, 11, 0] when they construct an equivalent sequence. The claim that not every tab must be divisible by some integer a> 1 is certainly correct, because then every output bit only depends on bits on positions that preceed it by a multiple of a, but that does not imply that the feedback polynomial is divisible by $x^{a}+1$ as claimed above. A counterexample is $x^{6}+x^{3}+1$, which is not divisible by $x^{3}+1$. 92.107.127.170 (talk) 07:50, 25 March 2009 (UTC)

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)

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)

If you can profile a run time difference between the implementation-defined code and the implementation-agnostic code, file a problem report with your compiler publisher. The optimizer is supposed to fix that for you. --Damian Yerrick (talk | stalk) 19:33, 16 January 2010 (UTC)

Yes, the point of the source code here is to add clarity, not give implementations that run 1% faster on certain platforms. It's ridiculous that the code should rely on negation of 1 yielding all bits set; this isn't a page about the C language, it's about LFSRs. If the code must put the entire operation in a single expression, I think multiply is clearest, as it doesn't even use the conditional operator:

lfsr = (lfsr >> 1) ^ ((lfsr & 1) * 0xD0000001)

66.90.165.35 (talk) 11:00, 22 July 2010 (UTC)

For clarity, I would even go for the dreaded "if": lsb = lsfr & 1; lsfr >>= 1; if (lsb) lsfr ^= toggle; - IMO this translates better from/to the graphic representation. Applying a (potentially platform specific) optimization to clear code is probably easier than deciphering the algorithm from optimized code. What do you think? (FWIW, it's a factor of 3 on my machine) Peter-HHH (talk) 16:43, 15 March 2016 (UTC)

Has the primitive polynomial 0xd0000001u been verified? I tested it and it gives a non-maximal period over the bit range (specifically 1/2 period). However 0x80200003 does give a maximal period.Codekaizen (talk) 02:23, 21 June 2012 (UTC)

Is it important to make sure that the code is both valid C and valid C++? If we were to drop the requirement of being valid C++, we could make the assumption of 16-bit and 32-bit integers explicit by using the exact-width integer types of <stdint.h> that C has had for over a decade. But until C++0x is standardized and <cstdint> enters the standard library, we can't say the same about standard C++. --Damian Yerrick (talk | stalk) 01:19, 3 August 2011 (UTC)

It has come to my attention that C++11 is the standard now. Did <cstdint> make it in? --Damian Yerrick (talk | stalk) 02:26, 17 August 2011 (UTC)

(caw edit 2012.08.09) Use (~X)+1 to mean -X. This is the formal twos compliment for an unsigned integer type. — Preceding unsigned comment added by 199.209.144.241 (talk) 20:01, 9 August 2012 (UTC)

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 I have brightened the red.
• 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) Cuddlyable3 (talk) 09:09, 14 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)

Would someone like to check whether Fibonacci registers with taps in the Xilinx table [Xilinx table] for 12 13 14 16 or 19 bits are maximal as claimed? Cuddlyable3 (talk) 09:53, 14 June 2008 (UTC)

Hmmm, no takers? The reason I ask is because my own test gives interesting results, but unless someone confirms them independently, WP:OR prohibits them from the article.Cuddlyable3 (talk) 19:51, 23 July 2008 (UTC)

Cryptographic strength

The wording in section Uses in cryptography implies that an encryption system based on an LFSR is unbreakable, i.e. an attacker has no resort other than brute force search to crack the cipher. Although LFSR-based scrambling is used in some applications (idem), and while a one time pad is unbreakable, a stream from an LFSR is not necessarily a perfectly unpredictable stream of random bits and so a citation is needed to show that the search space of such a cipher is 2ⁿ (or less, as the case may be.) -- Regregex (talk) 20:38, 2 August 2008 (UTC)

I removed the entire paragraph. It simply isn't true, as the subsequent paragraph makes clear. --agr (talk) 10:15, 3 August 2008 (UTC)

Relationship between Galois LFSR and conventional (Fibonacci) LFSR, and the meaning of the word "output".

The article does not clearly define what is meant by the "output" of the LFSR, and worse, uses an inconsistent definition.

In some cases, the word "output" is used to refer to the right most bit, as in the sentence "The taps are XOR'd sequentially with the output and then fed back into the leftmost bit." But sometimes it is used to refer to all of the bits of the internal state of the LFSR, as in the sentence "The outputs that influence the input are called taps."

The reason that this can be a problem is in the section describing the Galois LFSR:

Currently the text claims "[a Galois LFSR] is an alternate structure that can generate the same[citation needed] output sequences as a conventional LFSR." And later, "To generate the same output sequence, the order of the taps is the counterpart (see above) of the order for the conventional LFSR, otherwise the sequence will be in reverse."

This is true only with the "output is rightmost bit" definition. When using the "output means internal state" definition, however, it is provably false... and it is not until you read the caveat: "Note that the internal state of the LFSR is not necessarily the same." when one first realizes that there is something strange afoot.

I suggest altering the article so that the terms "rightmost bit" and "LFSR state" are used in place of the word "output". For example: "The taps are XOR'd sequentially with the rightmost bit and then fed back into the leftmost bit." "The positions in the internal state which influence the input are called taps."

Thoughts?

Rossc719 (talk) 02:07, 13 November 2008 (UTC)

I'll go ahead and make those changes then if there are no objections...

Rossc719 (talk) 07:05, 14 November 2008 (UTC)

But sometimes one takes all the register bits as an output e.g. when using the LFSR as a counter. Cuddlyable3 (talk) 14:21, 19 November 2008 (UTC)

 Fixed. Good job, Rossc719. I see the article no longer uses the ambiguous word "output" alone, but always uses the discriminating phrases "output bit", "bit positions, "output sequence", or "state". Cuddlyable3 has a good point, but I think re-phrasing that fact as "When using the LFSR as a counter, one uses the entire LFSR state" is less ambiguous. --68.0.124.33 (talk) 15:34, 18 January 2009 (UTC)

"The output stream is reversible; an LFSR with mirrored taps will cycle through the states in reverse order." This is wrong. The output sequence is reversed, but the LFSR with mirrored taps does not run through the same states as the original LFSR in reverse order. Fixed that. Ludwig Weinzierl (talk) 17:08, 15 July 2010 (UTC)

A LFSR with mirrored taps can be used to find the internal states of the original LFSR in reverse order -- by reversing the order of the bits in the state (bit-reversal permutation).

• For example, a Fibonacci LFSR with taps at 000_0011 in state 000_0010 will step forward to step 100_0001 and then 110_0000. If we bit-reverse that final state (producing 000_0011) and load it into the "mirrored" Fibonacci LFSR -- i.e., the one with taps at 100_0001 -- then stepping it forward produces state 100_0001 (the bit-reversal of 100_0001) and then 010_0000 (the bit-reversal of the original state 000_0010).
• The same is true of any Galois LFSR and the corresponding "mirrored" Golois LFSR.

Would it make this article better to discuss "reversing", or is this too much information? --DavidCary (talk) 17:28, 31 July 2013 (UTC)

It definitely needs an example. This section of the article made no sense until reading the comments (or using a computer or programmable calculator to experiment with this hint)! 97.32.66.211 (talk) 00:28, 4 March 2016 (UTC)

Calculating Time Offset

I was able to get the two version to produce the same output at "bit 1", but there is a time offset of 656. I mention the time offset in the text. This is the code that I used to find the offset:

   for ( uint16 offset = 0; offset < 0xFFFF; ++offset) {
       
       unsigned short lfsr1 = 0xFFFF;
       unsigned short lfsr2 =  0xFFFF;
       unsigned int in, bit10, bit11, bit20, bit21;
       unsigned int period = 0;
       
       for( int a = 0;; a++ )
           {
               // taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1
               
               in  = ((lfsr1 >> 15) ^ (lfsr1 >> 13) ^ (lfsr1 >> 12) ^ (lfsr1 >> 10)) & 1;
               lfsr1 =  (lfsr1 << 1) | in;
               bit10 = lfsr1 & 1;
               bit11 = (lfsr1 >> 15) & 1;
               
               if (a >= offset) {
                   in = lfsr2 & 1u;
                   lfsr2 = (lfsr2 >> 1) ^ ((in << 15) | (in << 13) | (in << 12) | (in << 10));   
                   bit20 = lfsr2 & 1;
                   bit21 = (lfsr2 >> 15) & 1;
                                     
                   if (bit10 != bit20) break;

                   printf( "%d %d %d %d %d %d %d %d %s %s\n",
                           offset, a,
                           bit10, bit11, bit20, bit21, 
                           lfsr1, lfsr2,
                           byte_to_binaryN(lfsr1,16).c_str(), byte_to_binaryN(lfsr2,16).c_str() );
                   
               }

           } 
   }

Quanticles (talk) 17:45, 5 October 2012 (UTC)

Maximal Polynomials

The maximal polynomials in the table are incorrect. I had fixed the 8-bit case but it has been reverted. The coefficients in that case are 8,6,5,4. As the gcd of 8,4 is 2 these are not relatively prime and so either the claim in the article is wrong or this polynomial is wrong. Please provide the sequence that you believe this polynomial generates. Amoss (talk) 02:25, 19 November 2008 (UTC)

8-bit Fibonacci LFSR. Taps 8 6 5 4

40 20 10 88 C4 E2 71 38 1C 8E 47 23 91 48 A4 D2 E9 74 3A 1D 0E 07 03 81 C0 60 30 98 4C 26 93 49 24 92 C9 64 B2 D9 EC 76 3B 9D 4E 27 13 09 04 82 41 A0 50 A8 D4 6A B5 DA 6D B6 5B AD D6 6B 35 9A 4D A6 D3 69 34 1A 0D 86 C3 E1 F0 F8 7C BE DF 6F B7 DB ED F6 7B BD 5E AF D7 EB 75 BA 5D 2E 17 8B 45 22 11 08 84 C2 61 B0 D8 6C 36 1B 8D C6 E3 F1 78 3C 9E CF E7 73 39 9C CE 67 33 19 8C 46 A3 D1 68 B4 5A 2D 96 4B 25 12 89 44 A2 51 28 94 4A A5 52 A9 54 2A 95 CA E5 72 B9 DC EE 77 BB DD 6E 37 9B CD E6 F3 79 BC DE EF F7 FB FD 7E BF 5F 2F 97 CB 65 32 99 CC 66 B3 59 AC 56 2B 15 8A C5 62 31 18 0C 06 83 C1 E0 70 B8 5C AE 57 AB 55 AA D5 EA F5 FA 7D 3E 9F 4F A7 53 29 14 0A 85 42 21 90 C8 E4 F2 F9 FC FE FF 7F 3F 1F 0F 87 43 A1 D0 E8 F4 7A 3D 1E 8F C7 63 B1 58 2C 16 0B 05 02 01

8-bit Fibonacci LFSR. Taps 8 7 5 3

40 20 90 48 A4 D2 E9 F4 FA FD FE FF 7F 3F 1F 8F C7 63 B1 58 AC 56 AB 55 AA D5 EA F5 7A BD DE 6F 37 9B CD 66 33 99 4C A6 53 29 94 4A 25 12 89 44 22 11 88 C4 62 31 18 8C C6 E3 F1 78 3C 1E 0F 87 43 21 10 08 84 42 A1 50 28 14 0A 05 82 C1 E0 F0 F8 7C 3E 9F CF E7 F3 F9 FC 7E BF 5F AF 57 2B 15 8A 45 A2 51 A8 54 2A 95 CA 65 32 19 0C 86 C3 61 30 98 CC E6 73 B9 DC EE F7 FB 7D BE DF EF 77 BB 5D 2E 97 4B A5 52 A9 D4 6A B5 5A 2D 96 CB E5 72 39 9C CE 67 B3 D9 6C 36 1B 8D 46 A3 D1 E8 74 BA DD 6E B7 DB ED F6 7B 3D 9E 4F A7 D3 69 B4 DA 6D B6 5B AD D6 EB 75 3A 9D 4E 27 93 49 24 92 C9 64 B2 59 2C 16 8B C5 E2 71 38 1C 8E 47 23 91 C8 E4 F2 79 BC 5E 2F 17 0B 85 C2 E1 70 B8 5C AE D7 6B 35 1A 0D 06 83 41 A0 D0 68 34 9A 4D 26 13 09 04 02 81 C0 60 B0 D8 EC 76 3B 1D 0E 07 03 01

Cuddlyable3 (talk) 14:09, 19 November 2008 (UTC)

Galois LFSRs wrong taps?

I think the example code for Galois LFSR has an error. Someone messed up the taps. In the section before that the polynom x^32 + x^30 + x^29 + 1 was given. This should end up in the bitmask 0x60000001u, but the code differs from that. A classical Fencepost error?

lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xd0000001u); /* taps 32 31 29 1 */

By the way, auto correlation should be mentioned. The example polynom has very poor properties from that view, but the xilinx example is much better.

Sorry for my bad english --Biezl (talk) 19:16, 30 November 2008 (UTC)

Biezl please define what you mean by poor auto correlation property. How is this property measured? Cuddlyable3 (talk) 10:33, 10 December 2008 (UTC)

The source of the bitmask error is this edit[3]. I can't comment on which taps give the maximal sequence of 2³²-1 without embarking on a long search.

I agree that auto correlation should be mentioned. However defining taps for the best correlation property involves an enormous search if done by brute force, which is the only method that I know and trust.

Your english is good. Cuddlyable3 (talk) 13:13, 2 December 2008 (UTC)

The C hex literal corresponding to the polynomial x^32 + x^30 + x^29 + 1 is 0xb0000001u, not 0x60000001u. A classical fencepost error, I guess :). Note that neither 0xb0000001u nor 0x60000001u are maximal-period polynomials. The one used in the example (0xd0000001u) on the other hand, is maximal period. Ufretin (talk) 09:19, 4 December 2008 (UTC)

You don't "see" the x^32 term as a "1" bit in the mask because it represents the input to the LFSR. 0x60000001u looks right to me. Ufretin please show what you know about it being a sub-maximal polynomial. (It's not practical to show a whole sequence but seeing a few steps would reassure me that we are talking about the same thing.) Cuddlyable3 (talk) 22:18, 4 December 2008 (UTC)

If I'm not mistaken, the picture illustrates the polynomial x^16 + x^14 + x^13 + x^11 + 1. In the C code example the given polynomial is 0xB400, which has bits 16,14,13 and 11 set. So here, the x^16 term shows up as a "1" bit, and the example code correctly produces 0xE270 (and has a period of 0xFFFF), as expected. Here's the rationale:

After an unsigned right shift by one in C(++), the MSB will always be zero. Therefore, a naïve implementation could be comprised of the following:

1. Right shift all bits in the state by one

2. Iff the rightmost bit was set, XOR the state with the mask

3. Iff the rightmost bit was set, set the leftmost bit to "1"

Keeping the largest term as a bit in the mask makes step 3 redundant, because the leftmost bit will always be "1" after an XOR with the mask and "0" otherwise. That's why I implemented it that way. Besides, it seemed intuitive to me that each term would correspond to a bit in the mask. I hope this makes sense.

But I seem to have made another mistake in assuming that the "+ 1" term corresponds to a bit in the mask, which is does not. The rightmost bit corresponds to "+ x^1". So the C hex literal for (x^32 + x^30 + x^29 + 1) would be 0xB0000000u. Note also that the mask used (0xD0000001u) corresponds to (x^32 + x^31 + x^29 + x + 1), which I got from here [4], not from the previous section.

Oh, and I've verified that my interpretation is valid for the xilinx polynomial too, successfully producing a maximal period sequence using 0x80200003u. So I see no reason not to use that instead, if it has better properties. Ufretin (talk) 14:32, 5 December 2008 (UTC)

MOSMATH

WP:MOSMATH actually exists. Really. It does. If found this in the article:

[n,n-C,n-B,n-A,0]

I changed it to this:

[n, n − C, n − B, n − A, 0]

Do some people really think the former looks like the latter? Michael Hardy (talk) 21:48, 18 February 2009 (UTC)

Image colour scheme

Why are all the images in reversed colours? Oli Filth^{(talk|contribs)} 20:11, 1 March 2009 (UTC)

Because that's how I made them. Cheers. Cuddlyable3 (talk) 21:04, 2 March 2009 (UTC)

I also made them public domain so you are free to try different colours. To do that use a hex editor (such as Hexplorer which is free) and make changes to the palette of the gif file. I think the present colours look well on a screen (where most Wikipedia viewing is done) but are less good for printouts. Cuddlyable3 (talk) 10:39, 4 March 2009 (UTC)

Personally, I love white-on-black. --Andreas Rejbrand (talk) 19:18, 8 January 2010 (UTC)

However, the static images should be vector graphical, i.e. SVGs. --Andreas Rejbrand (talk) 19:18, 8 January 2010 (UTC)

Yes, MediaWiki should support SVG animation, but at least when I made file:Dual boot icon.svg, it didn't. --Damian Yerrick (talk | stalk) 22:18, 16 January 2010 (UTC)

Linear functions of single bits

"The only linear functions of single bits are xor and inverse-xor; thus it is a shift register whose input bit is driven by the exclusive-or (xor) of some bits of the overall shift register value."

It is unclear what this means. The first clause appears to refer to a linear map from one n-dimensional binary vector space to another. Is the function of the map XOR some constant n-tuple? In this case, the clause is false. Consider a one dimensional binary vector space and a map function constant of 1. XOR 1 is just negation. However ~e1 + ~e2 != ~(e1 + e2), where e1 and e2 are element of the first vector space. Hence, XOR is not a valid linear map. —Preceding unsigned comment added by 72.15.8.14 (talk) 23:59, 19 May 2009 (UTC)

XOR is integer addition modulo 2, and ~x = 1 + x. Of course (1+e1) + (1+e2) != 1+(e1 + e2), because addition of a constant is never a linear map, but addition of the arguments (without a constant) is linear. Therefore, a polynomial counter using the XNOR function would not strictly be an LFSR because it is not linear, even though the sequence is the complement of the corresponding XOR counter. But are there any sources that distinguish XOR counters from XNOR ones and call only the former LFSRs? --Damian Yerrick (talk | stalk) 19:43, 16 January 2010 (UTC)

A recent edit to this article assumes that linear means an affine map as opposed to a linear map, which would make XNOR also linear. I've brought up this definition dispute in Talk:Linear#Boolean functions. --Damian Yerrick (talk | stalk) 00:52, 3 August 2011 (UTC)

Usefulness as counters

I reinstated the sub-section Uses as counters. The usefulness is notable because 1) LFSR's uniquely provide any desired count (i.e. cycle length or division ratio) with the minimum amount of logic gates excluding only simple ripple-through counters that are unsuitable for fast synchronous circuits; and 2) their speed advantage, especially in the Galois configuration. Tables 1 and 2 of the Xilinx source cited describe this application of LFSRs to "Counters with a shorter cycle [that] require additional decoding of the feedback signal". Cuddlyable3 (talk) 10:16, 31 May 2009 (UTC)

Fair enough! I removed it because it sounded like OR, and I had assumed (without checking) that the link was just a table of polynomials. But you're absolutely right, the app note does describe their use in this context. Oli Filth^{(talk|contribs)} 10:23, 31 May 2009 (UTC)

XNOR register question

There is the statement that:

As an alternative to the XOR based feedback in an LFSR, one can also use XNOR.[1] This function is not linear, but it results in an equivalent polynomial counter whose state of this counter is the complement of the state of an LFSR. A state with all ones is illegal when using an XNOR feedback, in the same way as a state with all zeroes is illegal when using XOR. This state is considered illegal because the counter would remain "locked-up" in this state.

It seems to me that with an odd number of XNOR inputs that this isn't true. If you XOR an odd number of ones the result will be one, invert that and it is zero. The all ones state is not the stationary state for such register. There will still be one, but that isn't it. Gah4 (talk) 04:19, 6 February 2010 (UTC)

True but AFAIK one never needs an odd number of taps to generate a maximal sequence. Cuddlyable3 (talk) 20:38, 6 February 2010 (UTC)

No that's not true. If all-zeros and all-ones can't be stationary states there is none because all other patterns are variable under the bitshift operation. This is not proof that there is a single 2^n step sequence. Perhaps, instead there are two or more disjoint sequences? Jasen betts (talk) 11:39, 23 September 2010 (UTC)

Grammar Question

To native english speakers, the phrase ".. an LFSR .. " is preferred to ".. a LFSR". The usage of "a" vs. "an" depends on whether the _sound_ of the syllable which follows is that of a vowel or consonant:

- An Apple (Apple begins with a vowel sound)

- A Rabbit (Rabbit begins with a consonant sound)

Even though "LFSR" begins with a letter, when something is written as an abbreviation it would be read aloud letter by letter: "an Ell eff es are" reads normally. In the article, there are several examples written as "a Ell eff es are" which forces the reader to try to see if LFSR can be pronounced as a word. It cannot be pronounced by the normal rules of English pronunciation because lfsr doesn't contain any vowels. So then the reader reads a third time, mentally editing the "a" into an "an," which reads normally. This mental process slows normal reading.

There is a certain ambiguity here because some people DO pronounce acronyms as words. But here, a dictionary and spelling will tell the difference. If an acronym becomes a word, like radar, it is no longer written in CAPS. So in the case where the acronym can be pronounced, and if you mean to lead the vanguard, write the acronym in lowercase if you mean it to be pronounced. Otherwise, write the acronym in all uppercase letters if you mean it to be read letter-by-letter (it always will be).

Does Wikipedia have a grammar rule for this? —Preceding unsigned comment added by 142.68.233.4 (talk) 09:54, 31 March 2010 (UTC)

Agree that ".. an LFSR .." reads naturally. I corrected the heading to "Grammar". Cuddlyable3 (talk) 18:03, 11 April 2010 (UTC)

Verifying polynomials

I reverted a deletion of the section on Testing LFSRs. There is a lack of information about what are the polynomials that give maximal sequences. The article provides a table of "some" polynomials but that alone is inadequate because there are many such polynomials for each number of bits n. The table must be limited in size and does not reach to the important 32-bit case that is encountered in applications such as CRCs and software Pseudorandom number generators. Wikipedia content must be verifiable and in this case the reader can do so using no more than the ubiquitous PC. If we delete the section we abandon the reader to reference that says "There is no quick way to determine if a tap sequence is maximal length." Cuddlyable3 (talk) 08:48, 12 April 2010 (UTC)

I deleted the section because it reads like how-to instructions, because it was written in assembler (which is essentially unreadable to most people), and what's more is very platform-specific (and OS-specific). In my opinion, all we really need is something to the effect of describing that "maximal-length" means it takes 2ⁿ-1 iterations to get back to the value you initialised it at; any interested reader with a clue ought to be able to derive a suitable test based on that description.

If we're worried about verifiability, surely we can find a reputable source that lists the low-order polynomials that we currently have in the article? (which, presumably, the Xilinx app-note is. If not a table up to length-34 is listed in "Digital Communications" by Proakis) Oli Filth^{(talk|contribs)} 09:03, 12 April 2010 (UTC)

The assembler mnemonics do not need to be understood, merely entered. The explanations in italics are there to help anyone who is curious but they can be ignored. I agree that WP:NOTHOWTO and giving the little recipe is not going to teach anyone much, nor is that its goal. The article already explains that maximal length is 2ⁿ − 1 states but it does not clarify fully what polynomials can achieve this. Finding and verifying those polynomials is, even for a reader with a clue, a challenging problem. The difficulties are three-fold: A) A table, such as the article presents, gives necessarily only an arbitrary selection from the multiple polynomials that work. A consequence of this arbitrariness is the confusion of a user recently who says "I use a different sequence so either the article or my polynomial is wrong." My concern about verifiability is not about a lack of sources because there are several (and Proakis is a reliable one) but that the source tables confuse because they differ, due to their arbitrariness. B) The maximal sequences become so long as to defy searches by brute force. I know this because that is the method I used to tabulate the polynomials in the article; just to find one certain polynomial for n=19 took several hours. The only practical way to verify the longer polynomials is with the speed advantage of assembly code or to build special hardware e.g. around a Xilinx FPGA ( ! ). C) For long LFSRs there are many "dense" polynomials (i.e. many taps) that work, see some examples at Cyclic redundancy check. For most purposes one wants the minimum number of taps, but a mathematician advises me that it remains an open problem whether "2 or 4 taps always suffices". You are right that the debug tool is specific to a platform. It has survived from the early days of MS-DOS for 28 years so that now "every" PC user running Windows (any version) has it available. The test recipe that I put in the article is simple because it is limited to LFSR's up to 32 bits. Testing anything longer would need code that is different, longer and slower. The present section is enough to show the principle. Cuddlyable3 (talk) 21:33, 12 April 2010 (UTC)

This section is original research and hence does not belong into wikipedia. Moreover, as you also admit it is unreadable. Furthermore, the algorithm used to verify the polynomials is not state of the art. I.e., one common algorithm used to test if a LFSR has maximal length is to first check if the feedback polynomial is irreducible, i.e. by trying to factor the polynomial. If the polynomial is irreducible then one tests if it is primitive, by computing the order of x in the corresponding Galois field. Since the order of an element divides the order of the field this can be done many times faster than by stepping through the entire state. If we want to add material about how to test feedback polynomials then we should add references to appropriate literature and not try to reinvent the wheel. In the mean time I'm going to remove the section again. 83.79.174.251 (talk) 22:14, 12 April 2010 (UTC)

The section is hardly original research and is prior art to anyone who actually works with LFSRs. No wheel is reinvented here. Please do not put "admit it is unreadable" in my mouth, even if you feel that justifies your wish to remove the section. You correctly describe in outline an algorithm that IMHO belongs in the article about m-sequences. It is a general theoretical method of generating a vast number of tap configurations, more amenable to mathematicians than engineers. I support including a link to that theoretical method. Cuddlyable3 (talk) 12:03, 13 April 2010 (UTC)

You contradict yourself. Let me quote you "The assembler mnemonics do not need to be understood, merely entered". The problem is that on one hand you use a language that is hard to understand, but on the other hand you optimize an algorithm that is extremely slow. That does not make sense. It does not help to understand LFSRs and just adds unecessary clutter to this article. 85.3.204.220 (talk) 21:26, 13 April 2010 (UTC)

I don't understand what the complainant means by "an algorithm that is extremely slow". If by algorithm they mean the LFSR configuration itself then that is simply the subject of the article and is well known to be one of the fastest ways of generating a sequence in hardware or software. It seems this SPA's sentence "That does not make sense" ironically characterises their allegation of a problem in the preceeding sentence. Cuddlyable3 (talk) 14:06, 14 May 2010 (UTC)

The "extremely slow" simply refers to the fact that the algorithm that you used to verify polynomials has exponential time complexity. But there are algorithms that are polynimial in the size of the LFSR, assuming that we know the factorization of 2^n-1. I.e. to verify that a LFSR with feedback polynomial f(x) has period m=2^n-1 on checks that x^m mod f(x) = 1 and x^d mod f(x) != 1 for every proper divisor d of m. Implementing this requires only little algebra and some rather simple algorithms such as square and multiply. 85.1.147.193 (talk) 19:34, 14 May 2010 (UTC)

@User 85.1.147.193 since you answer for User 85.3.204.220 you seem to be the same SPA user. Please consider registering an account with a name that you would sign. Your description of an algorithm is in outline only with some hand waving assumptions. It might help the article to provide some more useable text than your opinion that "only little algebra and some rather simple algorithms" is involved. I suspect (but please prove me wrong) that your input will not help an average reader because of your mindset that a few assembly mnemonics are too hard to understand while the pure math of irreducible polynomials over finite fields is too trivial to expound. Cuddlyable3 (talk) 21:56, 14 May 2010 (UTC)

Cuddlyable3, this discussion is about your claim "The only practical way to verify the longer polynomials is with the speed advantage of assembly code or to build special hardware e.g. around a Xilinx FPGA ( ! )", which you used as a justification of your assembly code. This claim can be disproven by pointing out that there are faster ways to verify that a polynomial is primitive. Above, I've described a condition that can be used to check polynomials. If that is not enough to convince you, then maybe you should ask yourself how one would verify that the polynomial x^128 + x^7 + x^2 + x + 1 used in several cryptographic standards (e.g. Galois/Counter Mode) is primitive. To get the factorization of 2^n-1 for larger degrees n, one can either look them up e.g. in the Cunningham tables or chose n such that 2^n-1 is a Mersenne prime. For practical purposes (e.g. cryptographic protocols) that is enough. Hence assuming that we know the factorization of 2^n-1 is not a hand waving assumption. Finally, the existence of a fast algorithm does not depend on whether I register or not, so your accusations of sock puppetry are distracting and irrelevant. 85.3.220.95 (talk) 06:06, 1 June 2010 (UTC)

@User 85.1.147.193/85.3.204.220/85.3.220.95 it is obvious that you are one user who communicated from different IP addresses. That is an observation expressed only to be clear to whom one is replying. You are being ridiculous to call that an accusation. You have likely used different PCs or an ISP that reassigns IP addresses, both of which are legitimate possibilities. Also check WP:SOCK before protesting imagined accusations that could not even apply. The introduction at WP:SOCK gives reasons for registering that you may consider. No one has claimed that has any connection to the existence of an algorithm so your denial of that is also pointless. Cuddlyable3 (talk) 10:47, 29 November 2010 (UTC)

I'm not sure the purpose of this article is to explain to people how to verify whether a given polynomial generates a maximal-length sequence, much less how to find them (at best, that information should probably live at primitive polynomial or similar), especially given that others have already done the hard work for us! From your three-fold problem, (A) can be solved by a disclaimer to the effect of "This table lists a selection of polynomials; there are many others...". (B) seems to be a contradiction; your code snippet is a brute-force approach (incidentally, why did n=19 take so long, it's only 0.5 million iterations?), but as the IP states, there are other approaches (although I don't claim to understand them really). I'm not sure why (C) is an issue here!

If we absolutely must have a code snippet (and I don't believe that we do), then let's please at least have it in a pseudocode form that illustrates the point rather than the terse assembler; it's definitely up to the reader to convert it to a suitable implementation. Oli Filth^{(talk|contribs)} 22:55, 12 April 2010 (UTC)

I see potential for continuing disagreement if one presents the LFSR as the trivial embodiment of math that has been concluded once and for all, while another knows the method of connecting blocks as an LFSR is an open-ended construction art of logic that must be adapted to different applications. Referring to the points: (A) Did you miss the qualifier Some polynomials for maximal LFSRs in the section title? That qualifier already covers the facts that none of the tabulated polkynomials is unique for a bit length and that the table length is limited. The point is not solved by adding a disclaimer that is already in the article nor does that address helpfully the problem raised for readers by arbitrary selections of polynomials. (B) Did you miss the word "'searches by brute force"? A search is different from a verification. (For n=19 my inital search space was 2¹⁹ tap configurations. Supposing a desired polynomial will be found half-way through the search predicts 2¹⁹/2 x (2^¹⁹-1) iterations. I suggest you time that exercise for yourself using a high-level language such as C++. I am the first to admit that I could hardly have chosen a slower way to obtain a convincingly confirmed result for the encyclopedia.) You are surely not alone in finding the finite field theory approach demanding. (C) is my explanation of why polynomial selection is arbitrary, plus reply to your comment that putting assembly mnemonics directly to a PC is platform specific. If you like to present pseudocode then please put it here first. Pseudocode does not address processing speed optimisations and is a high-level description comparable with tutorial material to which WP:NOTHOWTO can be an objection. Cuddlyable3 (talk) 12:03, 13 April 2010 (UTC)

I suppose I do believe that construction of an LFSR is "trivial" once one has polynomials. I'm not sure what you mean by "an open-ended construction art of logic...". I'm not claiming that the search for primtive polynomials is concluded "once and for all", but any discussion on such a search surely ought to be in the article on the underlying theory, rather than this article on a specific application?

Regarding (A); I did notice the section title, of course, but I was assuming that you were nevertheless claiming that it was not sufficient. I'm not sure how your additions to the article address this! Either the reader understands there's more than one polynomial, or they don't. A bunch of assembler won't help them understand this; a prosaic explanation such as my addition to the article might.

Regarding (B); yes I did miss "search"; why were you trying a brute-force search in order to verify the given polynomials? I agree that a search would take on the order of 2ⁿ times longer.

Regarding (C); ok. But the only other option is to list all known polynomials for each order!

To summarise my position:

1. This is the wrong article for this content
2. Assembler (along with "how-to" use debug.exe, etc.) is completely the wrong presentation format for this content (no more than it would be appropriate for an algorithm to calculate Pi, for instance); seriously, can you point me at another article that attempts to present a solution with assembler?
3. I'm not clear that it addresses any of the shortcomings that you perceive with this article
4. I'm not clear that any of these perceived shortcomings are really a problem
5. As the IP suggests, there are more sophisticated methods for implementing a search (the brute-force approach is completely inpractical for anything beyond about n=30, so why bother when the work's already been done by others?).

Oli Filth^{(talk|contribs)} 12:28, 13 April 2010 (UTC)

You believe construction of an LFSR is trivial once one has the polynomials. A mathematician may believe that engineering is there to serve maths but that is not the world that I live in. What you call trivial hides the significant tasks of selecting one polynomial from many and then verifying what the resulting LFSR actually produces. Here we are talking only about the sequence length that is maximal if the polynomial is irreducible. There are also constraints for the intended application (such as autocorrelation, frequency spectrum, runs distribution, and let's not get into the subject of cryptography). I find it hard to explain better what "an open-ended construction art of logic..." means. I have not suggested that the LFSR article should describe how to search for polynomials and agree that belongs elsewhere. Again: A search is different from a verification. Referring again to the points: (A) The section title that began as "Polynomials for maximal LFSRs", was modified to "Some Polynomials for Maximal LFSRs" and to which you added a disclaimer is satisfactory as far as it goes. Your prosaic addition doesn't help anyone who has to use an LFSR for some specific purpose and is not content to rely exclusively on finite field theory that is incomplete and understood by few (yourself?) or on someone else's table. The test recipe is for getting verification and has no purpose of teaching about the multiplicity of polynomials. (B) was originally about assembly code being the only practical coding for fully running longer sequences in software but since you ask I can answer about what I did to make the table of polynomials. I perceived that there was a need for a table of verified polynomials and the way I could provide this was to set up a search program that would quite crudely go after the minimum number of taps for each n. That program is in high-level language, it did the job including laying out the table, and by n=19 I felt the table was big enough. I could go on but it had to stop somewhere. The exercise satisfied my curiosity about which n values in the range could or could not achieve maximal sequences with only two taps, a question that number field theory AFAIK cannot answer. Otherwise there were no surprises and I can stand by my note that you may have noticed in the editor window: "Since alternative polynomials are possible I have verified independently those tabulated here." (C) Listing all known polynomials is not an option.

Thank you for summarising your position. I comment:

1. I don't believe you acknowledge any article as a home for the section on Testing LFSRs.
2. WP:OTHERCRAPEXISTS surely makes citing other examples of assembler irrelevant. Our article Assembler language has a copious section "Current usage" that includes "using processor-specific instructions not exploited by or available to the compiler. A common example is the bitwise rotation instruction at the core of many encryption algorithms." (If you were serious about a deep precision calculation of pi then I think you would want a hardware-level control of your computer. However not everyone is serious about producing results.)
3. The section Testing LFSRs addresses the difficulty of verifying a single candidate polynomial that might give a maximal sequence.
4. Understood.
5. If the rhetoric here is to justify your deleting the section then your fallacy is to attack a strawman. There exist sophisticated methods from the theory of finite fields for generating a plethora of polynomials but if your understanding of that leads you to say "Why bother [writing an encyclopedia to be helpful to non-specialist mathematicians] when the work's already been done (actually it has not all been done) by others?" then I suggest we seek a 3rd opinion about that. I reiterate that brute-force searching is not the issue. If you mean that verifying one maximal sequence for more than n=30 bits on a general purpose PC is completely impractical(sp) I suggest you type the given assembly menemonics into your own PC and see what happens with the 32-bit example after about 60 seconds. Cuddlyable3 (talk) 21:17, 13 April 2010 (UTC)

I agree with you that this discussion could go on ad infinitum, and a 3rd opinion would be beneficial. However, in your response to your responses:

1. m-sequence or primitive polynomial would certainly make better homes for this material (in the guise of "searching for polynomials" or similar). I'm not necessarily endorsing this suggestion, though!
2. I don't think I'm invoking WP:OTHERCRAPEXISTS. What I'm suggesting that there is no precedent for this sort of presentation, which is perhaps a clue that it's not a particularly appropriate one. And of course an article about assembler will have snippets; I was implying that no articles about maths, algorithms etc. drop to such a low level, pseudocode at best is the typical approach (see articles on sorting algorithms, for instance). Yes, in the example of pi, one would want highly-optimised code if one were serious about creating a calculator, but it's not WP's place to provide it.
3. I'm still not clear whether your additions are addressing a perceived need to verify the given polynomials, or to form part of a search for alternatives. In the case of the former, it's unnecessary as there are reliable sources. In the case of the latter, then I still think there are better places to home this material.
4. ok
5. Again, verifying is redundant due to the existence of reliable sources (I agree that this will not take too long for n=30, although n=168 is a different matter!). Searching is also a different matter, and really will be intractable even on banks of FPGAs beyond about 30. Given that there's better approaches out there (admittedly, I haven't looked for suitable sources), I don't see what the point of this material is, in the same way that I wouldn't see the point in presenting an "optimised" brute-force approach to calculating the millionth digit of pi.

(Incidentally, I was under the impression that a maximal-length sequence always obeys the same properties in terms of frequency-response/autocorrelation and run distribution. Therefore, I'm not sure why the specific polynomial choice matters that much. However, I could be wrong!) Oli Filth^{(talk|contribs)} 22:22, 13 April 2010 (UTC)

IP user 85.3.204.220 presumably represents a 3rd opinion, although I hope that SPA won't be used again to decry my contribution as "Vanity edits" [5] which is ad hominem. I accept the 2:1 consensus for not including the section as it now stands. Cuddlyable3 (talk) 16:11, 14 April 2010 (UTC)

In my opinion it's an interesting and clever example, but I have to agree that it should not be in the article, mainly because of the initial reasons given by Oli Filth. I also very much object to characterizing others' contributions as "vanity edits". decltype (talk) 15:35, 29 May 2010 (UTC)

Response to third opinion request:

In my opinion, assembly language is not a reasonable presentation medium. If you must describe the algorithm in detail, use either pseudocode or C / C++. Better yet, if possible, cite a source which talks about the verification problem; a detailed recipe of your own, without a source, arguably violates WP:OR.—Richwales (talk) 03:07, 30 May 2010 (UTC)

A5 and E0

There is a note that citations are needed for the security weaknesses in A5 and E0. What is the appropriate way to indicate that the citations are present in the articles on A5/1, A5/2, and E0? Thanks Doctorhook (talk) 00:31, 23 June 2010 (UTC)

By re-citing the relevant citations. Effectively citing other articles looks evasive IMHO. -- Regregex (talk) 10:06, 23 June 2010 (UTC)

Okay, I added a few. Does the article still need more citations? If so I'll try to help, but I don't see where. Otherwise we should remove the tag. Doctorhook (talk) 15:07, 24 June 2010 (UTC)

Xorshift

Is Marsagalia's Xorshift algorithm a linear feedback shift register? It seems similar but I'm not sure. Should there be a mention on the page? Hiiiiiiiiiiiiiiiiiiiii (talk) 02:56, 16 May 2011 (UTC)

Polynomial wrong

The polynomial listed (X^16 + X^14 + X^13 + X^11 + 1) I believe is incorrect for the pictures shown. The numbers match the numbers in the pictures but I don't think that is "standard." http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm has a different numbering method which I think is correct. Using the wikipedia method to get the polynomial for an LFSR shown in a patent made the math not work, but using this other method did. I believe the polynominal you have is X^16 + X^5 + X^3 + X^2 + 1. Both polynomials are primitive.

There are questions above about the "relatively prime" aspect. I'm not sure if it is correct or not, but with your numbering being different than the polynomial I would wonder "which numbers must be relatively prime." I found a link that talks about this subject: http://www.usna.edu/Users/math/wdj/book/node100.html But the context here is general polynomials (normal math), not the finite field related terms. "primitive polynomial" is used in both cases, so this may just be a rule from "normal" math that doesn't apply to finite fields. --129.42.161.36 (talk) 22:43, 19 May 2011 (UTC)

I agree that the polynomials are not "standard". One problem I see with the current state of the article are missing definitions and motivation. A common way to describe a Galois LFSR is to define the state s_n after n steps as

$s_{n}=s_{0}x^{n}\,{\bmod {f}}(x)$

where $f(x)\in GF(2)[x]$ is the feedback polynomial. Similarly the state of a Fibonacci LFSR would be

$s_{n}=s_{0}x^{-n}\,{\bmod {f}}(x)$

When using these definitions then numbering of the bits would be the reverse of the current numbering in the article. Possibly some implementations of LFSRs reverse the order of the coefficients, i.e. store the coefficient of the term x^0 into the most significant bit. This may save a few cycles on some CPUs. Doing the same in an overview article seems quite confusing to me. Rather than having a lot of C code the article should concentrate on clarity, have correct definitions and point out the relationship between LFSRs and arithmetic in finite fields. 85.1.187.187 (talk) 06:21, 17 August 2011 (UTC)

Pitfall!

There is a really cool application of LFSRs in the classic Atari game "Pitfall!":

http://www.gdcvault.com/play/1014632/Classic-Game-Postmortem-PITFALL

Check out the section "polynomial counter" — Preceding unsigned comment added by 70.91.166.181 (talk) 00:28, 12 June 2011 (UTC)

Yes. A reversible sequence was generated. The way of doing this could be added to the "Uses as counters" section. Cuddlyable3 (talk) 11:14, 4 August 2011 (UTC)

Why are tap bits "XOR'd sequentially?" Is this some hardware issue? Can't we do it in parallel with the same result? Slohr10 (talk) 21:20, 7 December 2014 (UTC)

Merge Maximum length sequence to here

First of all, I just changed the redirect for PN sequences to go to here. Another pseudonym or synonym for LFSR sequence (besides *"PN sequence"*) is Maximum length sequence, but there is already an article there.

"LFSR sequences", "PN sequences", "Maximum length sequences" (MLS), and binary Galois fields" (GF(2)) are all about the same thing. While I certainly do not propose merging this with the Galios field page, the first three should be merged and presented in the Computer science or Electrical engineering context. Not in a pure mathematics context.

I am and will remain an anonymous IP. But will some Wikipedians with accounts join in this effort to fix this problem? Please discuss below. 71.184.228.118 (talk) 03:35, 30 July 2016 (UTC)

A pseudo-noise sequence can be generated in many way, not just by LFSRs (so I undid your change of the redirect). And not all LFSR sequences are maximum length. And GF(2) is good for lots of things besides LFSRs. So how about a more precise proposal? Dicklyon (talk) 04:34, 30 July 2016 (UTC)

I won't undo your undo. The proposal is already precise. It's about merging the content of Maximum length sequences to here. And yes, not all LFSR sequences are MLS, but every MLS is an LFSR sequence. 71.184.228.118 (talk) 04:53, 30 July 2016 (UTC)

Oppose: Maximal length is also a property of other pseudo-random generators provided certain conditions are met. (For example, linear congruential generators.) -- KCAuXy4p (talk) 10:11, 14 February 2017 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 2 external links on Linear-feedback shift register. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Corrected formatting/usage for http://courses.cse.tamu.edu/csce680/walker/lfsr_table.pdf
• Added archive https://web.archive.org/web/20060111183721/http://homepage.mac.com/afj/lfsr.html to http://homepage.mac.com/afj/lfsr.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 09:56, 16 May 2017 (UTC)

LFSR as bit-serial cellular automata

Current generation bits are shifting, but not yet inputs to any XOR. 16bit example on Wiki would then contain 10 cells of one generation.

From first XOR onward, consider those bits to be previous generation. 16bit example on Wiki would then contain 6 cells of prior generation.

For 10celled generations, display only every 10th bit-serial iteration. Format the output accordingly to see the cellular automata at work.

CA behavior becomes more obvious with longer LFSRs, and simple rules of narrow span.

Try a 48bit LFSR with single XOR, or Wolfram's Rule30: XOR(A,OR(B,C)).

CA may place a mirror on one boundary to assure symmetry will evolve beside and never inside the register.

LFSR uses the arrow of time to extend one boundary, a similar but not identical break of symmetry.

76.8.25.170 (talk) 02:43, 30 July 2017 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Linear-feedback shift register. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20060315203220/http://www.yikes.com/~ptolemy/lfsr_web/index.htm to http://www.yikes.com/~ptolemy/lfsr_web/index.htm

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 18:39, 23 December 2017 (UTC)

"The taps are XOR'd sequentially with the output bit"

Hello fellow Wikipedians,

The text says "In the diagram the taps are [16,14,13,11]" - this seems to indicate that location 16, the "output", is a "tap". Therefore it's awkward (wrong?) to state "The taps are XOR'd sequentially with the output bit" because that means the output bit is to be XOR'd with itself (tab 16) effectively.

Cheers Mike (talk) 18:31, 29 August 2018 (UTC)

This article needs more Galois field theory

I think this article needs more Galois field theory. In particular the "Fibonacci" (I have never heard this term before) feedback system is calculating successive powers of x mod a primitive polynomial over GF(2). The feedback reduces the result after each shift by the primitive polynomial. If the polynomial is irreducible and not primitive then the cycle is not of maximum length. Note that the multiplicative group of a finite field is cyclic of order p^n-1 so has a generator that generates the entire multiplicative group.

Note that the field operators for GF(2) are XOR for plus and ordinary multiplication for times. For GF(2^n) a representation is polynomials over GF(2) mod a primitive polynomial. (An irreducible polynomial also works but powers of x do not cover all of the non-zero elements.)

Some proofs that the output of a maximal LFS sequence mimics white noise would also be appropriate.

I am willing to try to add this material.

References:

Berlekamp - Algebraic Coding Theory

Peterson - Error Correcting Codes

RochesterRetired (talk) 21:54, 28 December 2019 (UTC)

Notation backwards from industry/academic standard

Others have mentioned this, but to summarize: the Galois and Fibonacci LFSR should have the numbering of their taps reversed.

Specifications like USB define Galois polynomials e.g. x^16 + x^5 + x^4 + x^3 + 1 which corresponds to taps at 16, 5, 4, 3. However, for industry, this is defined for a Galois LFSR with numbering starting from the left. If you implement with the notation used in this article, your LFSR will produce an incorrect output. Metzkorn (talk) 16:37, 14 April 2022 (UTC)

There are a few different ways to build actual hardware LFSRs, resulting in different numbers in the table, but they should agree with one polynomial. I suspect that a polynomial with the taps numbered from the other end also works, but am not fast enough to show it. (Especially not in the margin of this page.) Note especially that the C software implementation is usually different from the hardware shift register implementation. Gah4 (talk) 00:35, 16 April 2022 (UTC)

Your suspicion is definitely right. Taps numbered the other way works. My main point here is, intuitively, it makes more sense to number the taps to match the polynomial (e.g. for the polynomial above, taps at 16, 5, 4, 3 as opposed to 13, 12, 11, 0). Metzkorn (talk) 16:44, 17 April 2022 (UTC)

Galois Parallel computation claim seems too hasty to generalize from an example

The claim "State and resulting bits can also be combined and computed in parallel. " seems overstated. The `prgs63` function is given as an example to prove the point. This particular polynomial x^63+x^62+1 supports computing 32 bits in parallel at a time (twice) because the polynomial has no nonzero coefficients in the low 32 bits (except the implicit x^0).

I think the generalization here is that you can create a number of parallel outputs at or less than the length of the feedback loop := number of trailing zeros in the "taps" description (which omits the implicit x^0). Mborg (talk) 22:19, 21 December 2023 (UTC)