Linear Feedback Shift Register

1696868916147

Linear Feedback Shift Register, LFSR, is used as the linear driving part to generate pseudo-random codes, which is the optimal solution in mathematical sense, and its autocorrelation function has the maximum flatness except for the main peak.

Introduction to LFSR#

Several registers are arranged in a row, with each register storing a binary number. The shift register outputs the rightmost (end) digit each time, and then shifts the entire register to the right. At the same time, it has a feedback function, which uses certain sequences already present in the register as the input to the feedback function, and fills the output of the feedback function into the leftmost end of the shift register. In this way, a shift register with a feedback function is called a feedback shift register.

Feedback Function#

The feedback function of LFSR simply XORs certain bits in the shift register and fills the XOR result into the leftmost end of the LFSR. For each bit of data in the LFSR, it can participate in XOR or not. Among them, the bits that participate in XOR are called taps.

b_{n+1} = c_1b_1 \oplus c_2b_2 \oplus \ldots \oplus c_nb_n

Order#

The order of LFSR is the number of registers in it. An LFSR with $n$ order can store up to $2^n-1$ different states, because the feedback value of the all-zero state is always zero. As for why it can traverse up to $2^n-1$ different states, it will be explained later. The maximum period of an LFSR with $n$ order is $2^n-1$ , and the sequence generated by an LFSR with a period of $2^n-1$ is called an $m$ sequence.

Characteristic Polynomial#

From the above equation, we can obtain a recursive relationship for an LFSR, and this recursive relationship corresponds to a characteristic polynomial.

f(x) = c_nx^n + c_{n-1} + \ldots + c_2x^2 + c_1x + 1

Here, $c_i$ is the same as the previous definition, indicating whether it is a tap. The resulting characteristic polynomial only retains the terms with taps and adds one. It can be understood that different characteristic polynomials of an LFSR correspond to different feedback functions.

Primitive Polynomial#

First, let's state a conclusion.

An $n$ -order LFSR can generate an $m$ sequence if and only if its characteristic polynomial is a primitive polynomial.

Next, let's introduce irreducible polynomial and primitive polynomial.

Irreducible Polynomial. A polynomial that cannot be factored over a specified field is called an irreducible polynomial, which means it cannot be equal to the product of polynomials with smaller degrees.

The finite field used in LFSR is $GF(2^n)$ , which means the coefficients of the polynomial must be less than 2, i.e., 0 or 1, and the highest degree of the polynomial cannot be greater than or equal to $n$ . For example, in $GF(2^3)$ , the polynomials are $0, 1, x, x+1$ .

Primitive Polynomial. A primitive polynomial is itself an irreducible polynomial, but it needs to satisfy the following three conditions: for an $n$ -degree primitive polynomial $F(x)$ ,

$F(x)$ is irreducible and cannot be factored further.

$F(x)$ divides $x^p+1$ , where $p = 2^n-1$ .

$F(x)$ does not divide $x^q+1$ , where $q<p$ .

From the primitive polynomial, we can obtain the feedback function that generates the $m$ sequence. For example, when $n=10$ , the primitive polynomial is

F(x) = x^{10} + x^3 + 1

Then, the feedback function is represented as [0,0,1,0,0,0,0,0,0,1], which means the XOR of the values in the 3rd register and the 10th register is assigned to the leftmost register to achieve shift feedback.

The primpoly function in MATLAB can be used to view primitive polynomials of any degree.

Properties of $m$ Sequence#

The $m$ sequence is actually what we call a pseudo-random code or a spreading code.

Balance Property#

In one period of the $m$ sequence, the number of 0s and 1s is roughly equal, with one more 1 than 0.

Shift Additivity#

When an $m$ sequence $m_1$ is XORed (added modulo 2) with another sequence $m_2$ generated by shifting $m_1$ with any delay, the result is still a delayed sequence of $m_1$ .

Autocorrelation#

Since the number of 1s is always one more than the number of 0s, the autocorrelation process will always yield a value of -1, which is significantly different from a completely random signal.

R(\tau) = \left\{ \begin{align*} &1, &\tau = 0\\ &-\frac{1}{N}, &\mathrm{else} \end{align*}\right.

Run Distribution#

Consecutive elements with the same value in the $m$ sequence are called a "run", and the number of elements in a run is called the run length. In an $n$ -bit LFSR-generated $m$ sequence, there are a total of $2^{n-1}$ runs, with runs of length 1 accounting for 1/2 of the total runs, runs of length 2 accounting for 1/4 of the total runs, and runs of length $k$ accounting for $2^{-k}$ of the total runs. In runs of length $k$ , the number of runs with consecutive 0s and consecutive 1s is equal. The run distribution has good balance.

For example, in the sequence 1000010010110011111000110111010, there are $2^{5-1}=16$ runs in total, and the distribution of runs of different lengths is as follows:

The number of runs of length 1 is 8, including 4 runs of 1s and 4 runs of 0s.
The number of runs of length 2 is 4, including 2 runs of 11 and 2 runs of 00.
The number of runs of length 3 is 2, including 1 run of 111 and 1 run of 000.
The number of runs of length 4 is 1, a run of consecutive 0s.
The number of runs of length 5 is 1, a run of consecutive 1s.

Appendix#

Due to time constraints, the generation and proof of primitive polynomials have been omitted. If there is time in the future, you can refer to other literature.