\section{Error Detection}

% -----------------------------------------------------------------
\begin{slide}{}

\subsection{Cyclic Redundancy Check}

   \begin{sitem}
      \item Add $k$ bits of redundant data to an $n$-bit message.

      \bigskip
      \item Represent $n$-bit message as an $n-1$ degree polynomial;
            e.g., MSG=10011010 corresponds to $M(x) = x^7 + x^4 + x^3 + x^1$.

      \bigskip
      \item Let $k$ be the degree of some divisor polynomial $C(x)$;
       e.g., $C(x) = x^3 + x^2 + 1$.

      \bigskip
      \item Transmit polynomial $P(x)$ that is evenly divisible by $C(x)$,
       and receive polynomial $P(x) + E(x)$; $E(x)$=0 implies no errors.

      \bigskip
      \item Recipient divides $(P(x) + E(x))$ by $C(x)$; the remainder
       will be zero in only two cases: $E(x)$ was zero (i.e. there was no
       error), or $E(x)$ is exactly divisible by $C(x)$. Choose
       $C(x)$ to make second case extremely rare.
   \end{sitem}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}
   \begin{sitem}
      \item Sender: 
      \begin{sitem}
         \item multiply $M(x)$ by $x^k$; for our example, we get
          $x^{10} + x^7 + x^6 + x^4$ (10011010000);

         \item divide result by $C(x)$ (1101);

         \pichere{crcalc.eps,height=4in}

         \item Send 10011010000 - 101 = 10011010101, since this must be 
          exactly divisible by $C(x)$;
      \end{sitem}
   \end{sitem}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   Want to ensure that $C(x)$ does not divide evenly into polynomial $E(x)$.

   \begin{sitem}

      \item All single-bit errors, as long as the $x^{k}$ and $x^{0}$ terms
       have non-zero coefficients.

      \item All double-bit errors, as long as $C(x)$ has a factor with at least
       three terms.

      \item Any odd number of errors, as long as $C(x)$ contains the factor
       $(x + 1)$.

      \item Any `burst' error (i.e sequence of consecutive errored bits) for
       which the length of the burst is less than $k$ bits. 

      \item Most burst errors of larger than $k$ bits can also be detected.
   \end{sitem}

   \bigskip
   Common polynomials for $C(x)$:

   \begin{center}
   \begin{tabular}{l|l}
   \hline
   CRC  & $C(x)$\\
   \hline
      CRC-8     & $x^8 + x^2 + x^1 +1$ \\
      CRC-10    & $x^{10} + x^9 + x^5 + x^4 + x^1 + 1$ \\
      CRC-12    & $x^{12} + x^{11} + x^3 + x^2 + 1$  \\
      CRC-16    & $x^{16} + x^{15} + x^2 + 1$  \\
      CRC-CCITT & $x^{16} + x^{12} + x^5 + 1$  \\
      CRC-32    & $x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} +$\\
	& $x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1$ \\ 
   \hline
   \end{tabular}
   \end{center}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Two-Dimensional Parity}

   \pichere{2dparity.eps,height=4in}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Internet Checksum Algorithm}

   Idea: view message as a sequence of 16-bit integers. Add these integers
   together using 16-bit ones complement arithmetic, and then take the ones
   complement of the result. That 16-bit number is the checksum.

   \begin{verbatim}
   u_short
   cksum(u_short *buf, int count)
   {
       register u_long sum = 0;
    
       while (count--) 
       {
           sum += *buf++;
           if (sum & 0xFFFF0000) 
           {
               /* carry occurred, so wrap around */
               sum &= 0xFFFF;
               sum++;
           }
       }
       return ~(sum & 0xFFFF);
   }
   \end{verbatim}
\end{slide}
