this is for holding javascript data
Michela Ceria edited bits2.tex
about 8 years ago
Commit id: 69beb452062fc680c33c1192e7d574de6ea9588d
deletions | additions
diff --git a/bits2.tex b/bits2.tex
index 67928e0..a8a938b 100644
--- a/bits2.tex
+++ b/bits2.tex
...
\\
In this section we will introduce these polynomials, together with their
operations. \\
A polynomial in the variable $x$ and coefficients in $\Fb$ (i.e. a polynomial
\emph{over the field of bits})
is an expression of the form $a_0+a_1x+a_2x^2+...+a_nx^n$, where $a_0,...,a_n \i \Fb$ are
bits.
\\
The set containing all the polynomials in the variable $x$, whose coefficients
are bits is denoted by $\Fb
[x]$, meaning that we are defining polynomials
\emph{over the field of bits}: [x]$:
$$\Fb [x] := \{1,x,x+1,x^2,x^2+x,....\}.$$
The notation is the analogue of that for polynomials over $\RR$, whose set is
usually denoted by $\RR[x]$.\\
In analogy with $\RR[x]$, we can define the \emph{degree} of a monomial
$x^\alpha \in \Fb[x]$ as the \emph{positive integer number} $\alpha$. For
example, the degree of $x^5$ is actually $5$.\\
The degree of a polynomial $p$ is the maximal degree of the monomials appearing
in $p$ with nonzero coefficient. Since the monomials in $\Fb[x]$ are only power
of $x$, the degree of $p$ is actually the maximal power of $x$ appearing in $p$.
The degree of the polynomial $p=0$ is conventionally set to $-\infty$.
As an example, the degree of $x^5+x^4+x^2+x$ is again $5$.
We explain now how to sum two polynomials.
Actually, the operation is defined exactly as that with polynomials over
$\mathbb{R}$, but one has to take into account that the coefficients are bits,
...
As we explained for multiples, we can underline that also raising to powers is
an operation with peculiar properties, making this process different from the
analogous for polynomials over $\RR$.
\begin{Exercise}\label{degree}
Find the degree of the following polynomials
\begin{itemize}
\item $(x^4+x^3+1)\cdot (x^3+x^2+1) $
\item $(x^3+x^2+x)+(x^4+x^3)$
\item $(x^2+x+1)+(x^2+x)$
\end{itemize}
Give your comments on the degree of $p\cdot q$ and $p+q$, with $p,q \in \Fb[x]$
and prove them.
\end{Exercise}
Consider for example the polynomial $p(x)=x+1\in \Fb[x]$ and suppose to compute
...
\end{Exercise}
In analogy with $\RR[x]$, we can define the \emph{degree} of a monomial
$x^\alpha \in \Fb[x]$ as the \emph{positive integer number} $\alpha$. For
example, the degree of $x^5$ is actually $5$.\\
The degree of a polynomial $p$ is the maximal degree of the monomials appearing
in $p$ with nonzero coefficient. Since the monomials in $\Fb[x]$ are only power
of $x$, the degree of $p$ is actually the maximal power of $x$ appearing in $p$.
The degree of the polynomial $p=0$ is conventionally set to $-\infty$.
As an example, the degree of $x^5+x^4+x^2+x$ is again $5$.
\begin{Exercise}\label{degree}
Find the degree of the following polynomials
\begin{itemize}
\item $(x^4+x^3+1)\cdot (x^3+x^2+1) $
\item $(x^3+x^2+x)+(x^4+x^3)$
\item $(x^2+x+1)+(x^2+x)$
\end{itemize}
Give your comments on the degree of $p\cdot q$ and $p+q$, with $p,q \in \Fb[x]$
and prove them.
\end{Exercise}
Each polynomial $p \in \Fb[x]$ is associated to a function
$$\widetilde{p}: \Fb \rightarrow \Fb $$
called \emph{evaluation} and defined as follows