m-Sequence is a kind of (special kind of) LFSR sequence. So in order for you to understand m-sequence, first you need to understand the concept of LFSR sequence.

• What is special about an m-sequence ?
• How do you read the polynomial column ?
• Why do some rows have two taps and others four ?
• Does every row in the table work ?
• What properties make an m-sequence useful ?
• Where are m-sequences used, and where do they fail ?

What is special about an m-sequence ?

What is so special about m-sequence comparing to typical LFSR ? If you generate a sequence with LFSR, the output eventually repeats itself. But in most of the application, the purpose is to generate the longest possible non-repeating sequence with a given number of shift registers (Taps). m-Squence is a special type of LFSR which gives the longest non-repeating sequence for each give number of taps. The well-known m-sequence for various taps is shown in the following table.

The word longest has an exact value, and it is worth writing down. A register of n stages has 2ⁿ possible states, and one of them is a dead end. All zeros feeds back a zero forever, so the register stops there. Every other state is available, which makes 2ⁿ - 1 the longest period any n stage register can reach. That is the number an m-sequence achieves and the reason for its name.

Reaching it is the part that needs the table. The taps decide how the 15 non-zero states of a four stage register are arranged, and only some tap choices place all 15 on one cycle. Other choices break them into several shorter cycles, and the register then walks round whichever one its starting state belongs to. Figure 1 shows three tap choices for the same four flip-flops.

Figure 1. The hardware is identical in all three rows, and only the feedback taps differ. A polynomial that is not primitive still produces a working shift register, and it produces a short sequence whose length depends on where you started it.

• The all-zero state is why the period is 2ⁿ - 1 : that state maps to itself, so it sits outside every cycle. A running register can never enter it and never leave it.
• A bad tap choice is not a broken circuit : [4 2 0] gives cycles of 6, 6 and 3. The register runs, the output looks like a sequence, and the period is a fifth of what you wanted.
• The starting state stops mattering once the taps are right : with 15 states on one cycle, any non-zero start gives the same sequence at some offset. With shorter cycles, different starts give genuinely different sequences.

How do you read the polynomial column ?

Each entry is a list of exponents rather than a list of coefficients, and the two forms appear in different tools. Reading the wrong one into a generator is a common way to lose an afternoon, so it is worth being explicit about which is which.

Take the row for 4 taps, which reads [4 3 0]. Every number is a power of X that is present in the polynomial, so the entry means X⁴ + X³ + 1. The 0 at the end is the constant term, and it appears in every row. A polynomial without it divides by X, and such a polynomial can never be primitive.

The coefficient form of the same polynomial is [1 1 0 0 1], which lists every power from 4 down to 0 including the absent ones. The LFSR page uses that form, because the Matlab example on it expects a vector of length n + 1. Count the entries to tell the two apart. The exponent form is short, and its first number is the degree. The coefficient form always has exactly n + 1 entries and starts with 1.

One more thing the table does not say. Each row gives one polynomial, and it is never the only one. The count of primitive polynomials of degree n is phi(2ⁿ - 1) divided by n, where phi is Euler's totient function. Degree 4 has 2 of them, degree 5 has 6, degree 8 has 16, and degree 16 has 2048. The table is a convenient pick rather than a definition.

• Exponent form, not coefficient form : [4 3 0] means X⁴ + X³ + 1. The same polynomial written for Matlab is [1 1 0 0 1]. Check which one your generator expects before pasting anything.
• The trailing 0 is not padding : it is the constant term, and a primitive polynomial always has it. A row ending in anything else would be wrong on its face.
• Each degree has many valid answers : phi(2ⁿ - 1) over n of them. Two systems can both use maximum length sequences of the same length and still share nothing.

Why do some rows have two taps and others four ?

The entries in the polynomial column take two shapes. Most rows hold three numbers, which means two taps, and the rest hold five, which means four. The split looks arbitrary, and testing it shows that it is not arbitrary at all.

A three number entry is a trinomial, Xⁿ + X^a + 1. It needs one XOR gate, so it is the cheapest feedback a register can have. Four taps need three XOR gates, which is why nobody would choose five terms if three would do.

I tested every degree from 2 to 32 against that idea, by searching for a primitive trinomial at each degree. The result has no exceptions. Every three term row in the table sits at a degree where a primitive trinomial exists, and every five term row sits at a degree where none exists. The table is not mixing conventions. It uses two taps wherever two taps are possible.

Degree 8 and degree 9 make the point side by side. Degree 8 has no primitive trinomial at all, so its row reads [8 6 5 4 0]. Degree 9 has several, and its row reads [9 5 0]. One extra stage changes the cost of the feedback by two gates.

Part of the pattern has a known cause. Part of it is forced rather than chosen. Every degree in the table that is a multiple of 8 carries five terms, and a classical result on trinomials over GF(2) explains why. That result, usually credited to Swan, rules out primitive trinomials whenever the degree divides by 8. I confirmed it for degrees 8, 16, 24, 32, 40 and 48. The other five term degrees, such as 12, 13, 14 and 19, have no rule that simple behind them.

• Three numbers means two taps and one gate : the table uses a trinomial whenever one exists, because the feedback is then a single XOR.
• The five term rows are forced, not stylistic : at those degrees no primitive trinomial exists, so four taps is the smallest that works. A check of every degree from 2 to 32 finds no exception.
• Degrees divisible by 8 never have one : 8, 16, 24, 32, 40 and 48 all carry five terms for that reason. Remember it before searching for a two tap answer that cannot exist.

Does every row in the table work ?

I checked all 52 rows rather than trust them, because a tap table is exactly the kind of thing that gets copied from one page to another without testing. Fifty one rows pass. One does not, and it is worth knowing which before you build anything from it.

The row for 46 taps reads [46 21 10 1 0], which is X⁴⁶ + X²¹ + X¹⁰ + X + 1. That polynomial factors. It divides exactly by X³ + X² + 1, leaving a polynomial of degree 43, and a polynomial that factors can never be primitive. Two separate tests agree. The order of X modulo it is not 2⁴⁶ - 1, and the standard greatest common divisor test for irreducibility finds the cubic factor.

The effect on a bench is mild and annoying. Forty six flip-flops with those taps still run, and they still produce a sequence. The period is not 2⁴⁶ - 1, and the sequence has none of the properties the next section describes.

A single mistyped digit would be the comfortable explanation, and it does not survive a check of the neighbours. I moved each of the three exponents by one and by two in both directions, and none of the resulting polynomials is primitive either. Degree 46 does genuinely need four taps, because it has no primitive trinomial. The polynomial [46 8 7 6 0] is primitive, and the same two tests confirm it.

The table above is left exactly as it was written, so it still matches whatever other copy of it you may be holding. Treat this section as the correction rather than the table. The wider lesson is that a tap set is cheap to test. Start the register from any non-zero state, count steps until the state repeats, and compare the count against 2ⁿ - 1.

• The row for 46 does not give a maximum length sequence : X⁴⁶ + X²¹ + X¹⁰ + X + 1 has X³ + X² + 1 as a factor. A reducible polynomial is never primitive.
• Use [46 8 7 6 0] instead : it is primitive by the order of X and by an irreducibility test, both checked.
• Test a tap set before you trust it : counting states until the register repeats settles any degree small enough to simulate. The order of X settles the rest.

What properties make an m-sequence useful ?

Maximum length is the definition, and it is not the reason anyone uses these sequences. Four properties follow from it, and the last of the four is what put m-sequences into every spread spectrum system ever built.

The first is balance. One period holds 2^n-1 ones and 2^n-1 - 1 zeros, so the count differs by exactly one and never by more. For the 15 bit sequence from [4 3 0], which is 111100010011010, that is 8 ones against 7 zeros. I confirmed the rule for every degree from 2 to 8.

The second is the run distribution. Those 15 bits break into 8 runs : four of length 1, two of length 2, one of length 3 and one of length 4. Half the runs have length 1, a quarter have length 2, and the halving continues to the end. Random bits would give the same distribution on average, and an m-sequence gives it exactly, every period.

The third is shift and add. Take an m-sequence, XOR it with a shifted copy of itself, and the result is the same sequence at some third shift. Nothing new is produced, whatever shift you pick. This property is what makes the algebra of these sequences tractable, and Gold codes are built on top of it.

The fourth is autocorrelation, and it is the one that matters in a receiver. Map 0 to plus one and 1 to minus one, then correlate one period against a shifted copy of itself. The answer is 2ⁿ - 1 at zero shift and exactly minus one at every other shift. Two values, and nothing in between. Figure 2 draws it for the 15 bit case.

Figure 2. The shape a receiver depends on. Correlating against a stored copy gives one unmistakable peak, and a floor that is flat and almost zero. The position of the peak therefore measures delay with no ambiguity anywhere in the period.

• The correlation takes two values and no others : 2ⁿ - 1 at the right alignment and minus one everywhere else. Sliding a local copy past the signal therefore produces one sharp answer.
• The floor is minus one, not zero : it is one part in 2ⁿ - 1 of the peak. The longer the sequence, the closer that floor comes to nothing.
• Balance and runs follow from maximum length : they are consequences rather than separate design choices, which is why one property settles all four.

Where are m-sequences used, and where do they fail ?

Every application uses Figure 2 in the same way. Correlate the incoming signal against a stored copy, find the peak, and read something off its position or its size. What differs between applications is which of those two numbers you want.

Synchronisation wants the position. A receiver may know the sequence and not the timing. It slides a local copy along until the correlation jumps, and the offset at which it jumps is the start of the frame. Channel sounding wants the whole correlation curve. An autocorrelation this close to an impulse makes the correlator output the impulse response of the channel, measured directly.

Scrambling and spreading want the sequence itself rather than the correlation. The pseudo-random sequence that runs through LTE and NR is a Gold sequence built from two m-sequences. No clearer sign exists of how much practical work these generators do.

Two limits matter, and the first explains why Gold codes exist. Autocorrelation is excellent and cross-correlation is not. Take two different m-sequences of the same length and correlate one against the other, and the result is neither small nor predictable. A system that hands every user a different m-sequence therefore separates them badly. Gold codes solve it by combining two m-sequences from a preferred pair, which trades a little autocorrelation for a bounded cross-correlation across a large family.

The second limit is linearity, and it is absolute. The feedback is a sum in GF(2) with no products and no thresholds, so 2n consecutive output bits determine both the taps and the state. Berlekamp-Massey does it in time proportional to n squared. A 46 stage register is broken by 92 observed bits, which is why a bare m-sequence is a scrambler and never a cipher. The LFSR page covers that attack.

• Position or size, and the application picks one : synchronisation reads where the peak is, and channel sounding reads the shape around it.
• Good alone, poor in a family : the autocorrelation of one m-sequence is ideal, and the cross-correlation between two of them is not. That gap is the entire reason for Gold codes.
• 2n bits give the whole generator away : a short observation yields the taps and the state together. Predictability is a property of the design rather than a weakness of one implementation.
• The longer the sequence, the cleaner the peak : the correlation floor is one part in 2ⁿ - 1. Adding stages therefore improves detection and costs only registers.