deletions | additions
diff --git a/bits3.tex b/bits3.tex
index 7e0a96f..d996401 100644
--- a/bits3.tex
+++ b/bits3.tex
...
\hline
\end{tabular}
\end{center}
so we have a new three-bit vector, that we call again
\emph{state}.\\ state.\\
We now need to compute the new mysterious value ?, and so we proceed
with the same algorithm, by taking the two bits at positions $x$ (i.e., $1$) and $1$ (i.e., $0$).\\
We will then get $1+0=1$ and so
...
\end{tabular}
\end{center}
%
which becomes, after another shift to the right, the following
state
%
\begin{center}
\begin{tabular}{ |c ||c|| c | c | c |}
...
\end{tabular}
\end{center}
%
with the last shift
we find the final state, which is the same as the initial state.
%
\begin{center}
\begin{tabular}{ |c ||c|| c | c | c |}
...
We notice the following facts:
\begin{enumerate}
\item[(1)] After having performed the above algorithm seven times, we get again the initial
state vector $(1,0,1)$.
\item[(2)] While performing the above algorithm, we find all seven nonzero $3$-bit strings
%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.
\end{enumerate}
...
any polynomial $f\in \Fb[x]$ of the form $f=x^n+\ldots+1$ to construct an LFSR
producing $n$-bit vectors and such that any initial state is got again after
a finite number of iterations.\\
Fact (2) is more difficult to generalize. If we want an LFSR that can start from any initial nonzero
state vector and obtain all other nonzero
vectors as states, vectors, then we must use very special polynomials, called \emph{primitive} polynomials.
%
\begin{Definition}\label{Primitive}
We call primitive any polynomial $f\in \Fb[x]$ of degree $n$ that, used as feedback polynomials of a LFSR, can generate all the non-zero
...
\end{tabular}
\end{center}
After a shift to the right, we obtain
the second state
\begin{center}
...
\end{center}
and, after a shift to the right, we get
the third state
\begin{center}
\begin{tabular}{ |c ||c|| c | c | c |}
...
\end{tabular}
\end{center}
From now on, we are
stuck with a zero state. Indeed stuck; indeed the mysterious bit will always be equal to $0$ and so, after the shift to the right,
the state we will always
remain obtain $(0,0,0)$.
\end{Example}
We recall the notion of irreducible polynomial (Definition \ref{REDIRR}). An irreducible polynomial cannot be written as product of two non-trivial factors. It turns out that there is a close links between primitive polynomials and irreducible polynomials, as shown in the following theorem.
\begin{Theorem}
...
Verify that $x^4 + x^3 + x^2 + x + 1$ is not primitive via a LFSR.
\end{Exercise}
The polynomials in $\Fb[x]$ are infinite. We describe a way to make it finite and bounded by a certain degree through a "polynomial relation". For example fix the relations to be $x^3=x+1$, or equivalently $x^3+x+1=0$, as in the example above. We can limit the number of elements in $\Fb[x]$ in this way: each time we find a monomial of degree greater than or equal to $3$ we substitute $x^3$ by $x+1$. At the end of this process we obtain a new polynomial of degree strictly less than $3$. For example
\[
x^4+x^2=x(x^3)+x^2=x(x+1)+x^2=x^2+x+x^2=x.
\]
One can obtain the same result dividing the polynomial $x^4+x^2$ by the polynomial $x^3+x+1$. The remainder is $x$.
Hence the polynomials defined in the set
\[
\Fb[x], \mbox{ where }x^3+x+1=0
\]
are the polynomials
\[
0, 1, x, x+1, x^2, x^2+x, x^2+1, x^2+x+1.
\]
These polynomials are $8=2^3$. This number can be obtained directly if we consider that the generic polynomial of degree $2$ is
\[
a_2 x^2+ a_1 x+ a_0,
\]
where $a_2,a_1,a_0\in \Fb$.
\begin{Definition}\label{RemPol}
We define the set of polynomials $A$ as
\[
\Fb[x], \mbox{ where }p=0
\]
\end{Definition}
The finite set $A$ inherits the operations of sum and product defined in the polynomial ring $\Fb[x]$. Moreover the following fact holds
\begin{Theorem}
The finite set $A$ is a field if and only if $p$ is an irreducible polynomial.
\end{Theorem}
\begin{Example}
\textbf{Nota (M)}: non capisco cosa intendi comunicare con l'esempio...
Let $A$ defined by $\Fb[x]$ where we fix the relation $x^2+x+1=0$, that is $x^2=x+1$. The finite set $A$ is $\{0,1,x,x+1\}$. We observed that $x^2+x+1$ is irreducible. And in fact all the elements different from $0$ in $A$ have an inverse: the inverse of $1$ is $1$; the inverse of $x$ is $x+1$ (try it); the inverse of $x+1$ is $x$.
%In fact $x(x+1)=x^2+x=x+1+x=1$.
Now consider the reducible polynomial $x^2$. Then $A$ is defined by $\Fb[x]$ where $x^2=0$. Even in this case the set $A$ is $\{0,1,x,x+1\}$, but this time the inverse of $x$ does not exist.
In fact multiplying $x$ by each element in $\{0,1,x,x+1\}$ we have either $0$ or $x$. In fact
\[
x\cdot 0=0, x\cdot 1 =x, x\cdot x=x^2=0, x\cdot (x+1)=x^2+x=x.
\]
That is $x$ is not invertible.
%In algebra we call $x$ a $0$-divisor.
\end{Example}
