Michela Ceria edited bits3.tex  about 8 years ago

Commit id: 8b5469ab38f368e4f7190b7c698ff45ba84cf8aa

deletions | additions      

       

We notice the following facts:  \begin{itemize}  \item performing the algorithm a finite number of times we get again the initial vectore $(1,0,1)$  \item there are only the numbers $1,2,3,4,5,6,7$ can be written using three bits not all zero and, performing the algorithm, we found all these numbers. This is not true in general. The feedback polynomials for which this property holds is called \emph{primitive}.  \end{itemize} \begin{Example}  We see now an example of non primitive polynomial. Let us consider $f(x)=x^3+1$ and we start again from $(1,0,1)$  \begin{center}  \begin{tabular}{ |c || c | c | c |}  \hline  1&1 & 0& 1 \\  \hline  \end{tabular}  \end{center}  \begin{center}  \begin{tabular}{ |c || c | c | c |}  \hline  ?&1 & 1& 0 \\  \hline  \end{tabular}  \end{center}  then  \begin{center}  \begin{tabular}{ |c || c | c | c |}  \hline  0&1 & 0& 1 \\  \hline  \end{tabular}  \end{center}  \begin{center}  \begin{tabular}{ |c || c | c | c |}  \hline  ?&0 & 1& 0 \\  \hline  \end{tabular}  \end{center}  \end{Example}  \begin{center}  \begin{tabular}{ |c || c | c | c |}  \hline  0&0 & 1& 0 \\  \hline  \end{tabular}  \end{center}  \begin{center}  \begin{tabular}{ |c || c | c | c |}  \hline  ?&0 & 0& 1 \\  \hline  \end{tabular}  \end{center}  \begin{center}  \begin{tabular}{ |c || c | c | c |}  \hline  1&0 & 0& 1 \\  \hline    \begin{center}  \begin{tabular}{ |c || c | c | c |}  \hline  ?&1 & 0& 0 \\  \hline  \end{tabular}  \end{center}  \begin{center}  \begin{tabular}{ |c || c | c | c |}  \hline  ?&0 & 1& 0 \\  \hline  \end{tabular}  \end{center}  \end{Example}  \end{tabular}  \end{center}  \end{Example}  \begin{center}  \begin{tabular}{ |c || c | c | c |}  \hline  ?&0 & 1& 0 \\  \hline  \end{tabular}  \end{center}  \end{Example}  Primitive polynomials are irreducible but the vice versa does not hold. For example, the polynomial $x^4 + x^3 + x^2 + x + 1$ is irreducible but it is not primitive.  \begin{Exercise}  Verify that $x^4 + x^3 + x^2 + x + 1$ is not primitive via a LFSR.  \end{Exercise}