## 3 Efficient LFSR Implementation
### Computation of Shifts  
All decimated sequences \(D^{j}\) have the same primitive minimal polynomial \(p(x)\), obtained using Algorithm 1. Hence, all of them are shifted versions of the others. The shift \(\theta_{j}\) of \(D^{j}\) with respect to \(D^{0}\) allows one to obtain the state of the \(j\)-th LFSR (the one that generates \(D^{j}\)) from the state of the \(0\)-th LFSR as follows:  
\[(d_{0,j},d_{1,j},\ldots,d_{n\cdot L-1,j})=(d_{0,0},d_{1,0},\ldots,d_{n\cdot L-1,0})A^{\theta_{j}}, \tag{9}\]  
where \(A\) is the connection matrix of \(p(x)\), that is:  
\[A=\begin{bmatrix}0&0&\cdots&0&c_{n\cdot L}\\ 1&0&\cdots&0&c_{n\cdot L-1}\\ 0&1&\cdots&0&c_{n\cdot L-2}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&1&c_{1}\end{bmatrix} \tag{10}\]  
The computation of \(\theta_{j}\) is not an easy task. Furthermore, the computation of \(A^{\theta_{j}}\) is time-consuming. Instead, we can obtain the matrix \(A^{(j)}=A^{\theta_{j}}\) solving the linear equation system of Equation (9). Note that we have \(n\) matrices \(A^{(j)}\) to compute and thus \(n\) linear systems to solve. The linear system in Equation (9), stated using the first \(nL\) element, the seed, has \(nL\) equations and \(n^{2}L^{2}\) unknowns. Each new element of the sequence defines \(nL\) new equations with the same unknowns. Hence, the \(2 Ln+1\) elements of the \(m\)-sequence in \(GF(2^{n})\) generated in Algorithm 1 to obtain \(p(x)\) provide enough equations to solve the systems. As an example, we consider a 3-stage LFSR defined in \(GF(2^{4})\), that is, the LFSR \(<3,f(x),4>\), where \(f(x)=1+x+(0x9)x^{3}\) is primitive over \(GF(2^{4})\) and the primitive polynomial \(x^{4}+x+1\) has been used to construct \(GF(2^{4})\). From the initial seed \((1,1,1,1),(0,0,0,0),(0,1,1,0)\) or, equivalently, \((1+\alpha+\alpha^{2}+\alpha^{3},0,\alpha+\alpha^{2})\), \(\alpha\) being a root of \(x^{4}+x+1\), the LFSR \(<3,f(x),4>\) generates the following sequence:  
\[\begin{array}{l}001000001100111010010000\cdots\\ 101001011000000001010001\cdots\\ 1011101000000011101000\cdots\\ 001110000001000101100011\cdots\end{array} \tag{11}\]  
where the elements of \(GF(2^{4})\) are represented in columns with the least significant bit at the top. The four decimated sequences are all generated by the same primitive polynomial  
Figure 3: LFSR seeds in the binary equivalent model.  
\(p(x)=x^{12}+x^{6}+x^{5}+x^{3}+1\) and, hence, all of them are shifted versions of the same \(m\)-sequence. Solving the system in Equation (9), we obtain the matrices \(A^{(1)},A^{(2)},A^{(3)}\):  
\[A^{(1)}=\begin{bmatrix}1000000000110\\ 0100000000011\\ 101000000001\\ 110100000000\\ 011010000000\\ 0011010000000\\ 00011010010\\ 000011010101\\ 000001101010\\ 000000110101\\ 000000110101\\ 000000011001\\ 0000000001100\end{bmatrix}A^{(2)}=\begin{bmatrix}000000101010\\ 0000000010101\\ 10000000010101\\ 110000000010101\\ 1110000000101\\ 0111100000001111\\ 010111111111\\ 0010111111111\\ 000101010101\\ 000001010101\\ 000001010101\\ 00000001111111\\ 001111111111\\ 000000001\\ 11111111111\\ 000001010101\end{bmatrix}A^{(3)}=\begin{bmatrix}000111111111\\ 000011111111\\ 000001111111\\ 0000001111111\\ 101111111000\\ 10000000111111\\ 010111111111\\ 0010101010000001\\ 111111111111\\ 0000000011\\ 111111111111\\ 00000101010101\end{bmatrix} \tag{12}\]  
Since the decimated sequences have a small period of \(2^{12}-1=4095\), we have also compared them to obtain the shifts \(\theta_{1}=3276\), \(\theta_{2}=3549\), and \(\theta_{3}=3822\). In a real scenario, \(\theta_{j}\) is not going to be computed. It is important to point out that the calculation of the \(A^{(j)}\) matrices can be performed prior to the normal operation of the LFSR since they do not depend on the seeds.