this is for holding javascript data
Michela Ceria edited bits3.tex
over 7 years ago
Commit id: f922656a0cda1f30327b239447fd1c4dbe6a5b55
deletions | additions
diff --git a/bits3.tex b/bits3.tex
index ebf6daa..ab08014 100644
--- a/bits3.tex
+++ b/bits3.tex
...
Another structure useful to manage ordered sets, like vectors, is the set of
polynomials described in Section \ref{Sec:Polynomials}.
We recall that the sum of two polynomials, $x+1, x^2+1 \in
\Fb$, \Fb[x]$, is %that is $$(x+1) + (x^2+1)= x^2 + x+(1+1).$$ Since in $\Fb$ $1+1=0$, we finally get
\begin{equation}\label{eq:pol}
(x+1) + (x^2+1)= x^2+x.
\end{equation}
...
\end{enumerate}
%
Fact (1) is a property that is shared by many LFSR's. It is enough to use
any polynomial $f\in
F_2[x]$ \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 vector and obtain all other nonzero vectors, then we must use very special polynomials, called \emph{primitive} polynomials.
%
\begin{Definition}\label{Primitive}
We call primitive any polynomial $f\in
\FF_2[x]$ \Fb[x]$ of degree $n$ that, used as feedback polynomials of a LFSR, can generate all the non-zero
$n$-tuples of bits,i.e. all the $n$-tuples but $(0,0,0,...,0,0)$, using as initial
state any of these.
\end{Definition}