\documentclass[11pt]{article}
\usepackage{handout2e}
\usepackage[pdftex]{graphicx}
\begin{document}
\input{epsf}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\answer}[1]{}
\head{CSG250}{Wireless Networks}{Spring 2007}{13 February 2007}{4}

\begin{center}
\Large{\bf Sample Solutions to Problem Set 2}
\end{center}

{\bf 1. (10 points) Frequency-hopping spread spectrum}

Problem 7.5.

{\bf Answer:}
\begin{itemize}
\item[{\bf a.}] 15.

\item[{\bf b.}] The FSK used is clearly MFSK since the same bit is
modulated on a different frequency within the same channel (see times
0 and 8).  The given data is consistent with MFSK, with number of
levels $M = 4$.  In the channel given by frequencies $\{f_0, f_1, f_2,
f_3\}$, the association is $00 \rightarrow f_0, 01 \rightarrow f_1, 10
\rightarrow f_2, 11 \rightarrow f_3$

\item[{\bf c.}] $\log_2 M = 2$.

\item[{\bf d.}] $M = 4$.

\item[{\bf e.}] 3 bits per hop.

\item[{\bf f.}] This is a fast FH system since the hopping rate, 1 per
time unit, is faster than the symbol rate, which is 1 every 2 time
units.

\item[{\bf g.}] $2^3 = 8$.

\item[{\bf h.}] When we consider the dehopped frequencies, we can
replace $f_i$ by $f_j$ where $j = i \bmod 4$ (by projecting all
frequencies to the first channel).  So the variation of the dehopped
frequency with time can be given by:

\[
f_1, f_1, f_3, f_3, f_3, f_3, f_2, f_2, f_0, f_0, f_2, f_2, f_1, f_1,
f_3, f_3, f_2, f_2, f_2, f_2.
\]
\end{itemize}


{\bf 2. (2 points) Maximum packet length in Bluetooth}

In commercial wireless packet data networks using FHSS, such as
Bluetooth, the chip duration is designed long enough to allow
transmission of a full packet in each hop.  The hopping rate of
Bluetooth devices is 1600 hops/s.  Assuming a data transmission rate
of 1 Mb/s, what is the size of the largest packet that can be
transmitted?

{\bf Answer:} The size of the largest packet is $10^6/1600 = 625$
bits.

{\bf 3. (8 points) Near-far problem in BPSK-DSSS}

Two 100 mW BPSK DSSS mobile terminals with processing gains of 20 dB
communicate with the same base station, using two different spreading
codes.  One of the mobiles communicates as an information source, and
the other terminal acts as a source of wideband interference.  Answer
the following questions under the assumptions given below.
\begin{itemize}
\item[{\bf (a)}]
Give the signal-to-interference ratio as a function of the distances
between the two terminals and the base station.

\item[{\bf (b)}]
Plot the bit error rate versus the ratio of the distance of the target
terminal and the interfering signal from the base station.  At what
relative distance ratio does the interfering terminal push the bit
error rate below $0.01$. 
\end{itemize}

{\em Path loss model:} Assume that the distance power gradient (the
exponent in the path loss equation) is 3.

{\em Noise:} Assume that there is no other background noise.

{\em BPSK:} Assume that the transmission bandwidth required for BPSK
is twice the data rate and the Bit-Error-Rate (BER) is given by the
following formula:
\[
BER = \int_{\sqrt{2E_b/N_0}}^{\infty} \frac{1}{\sqrt{2\pi}}
e^{-\frac{u^2}{2}} du.
\]
(To calculate the above numerically, you can use the complement of the
error function used in statistical analysis -- e.g., the ERFC function
in Excel.)

{\bf Answer:} The processing gain is $10^{20/10} = 100$.  If the
distance from target terminal to base station is $t_1$ and the
distance from interfering signal to base station is $t_2$, then, after
applying path loss and processing gain, we obtain SNR to be $100
(d_2/d_1)^3$.

If the ratio of distances $d_2/d_1$ is $r$, then ratio of powers is $r^3$.  So
SNR is $100r^3$.  Since the transmission bandwidth is twice the data
rate, we obtain that $E_b/N_0$ equals $200r^3$.  Therefore, we need to
graph the following function.
\[
BER = \int_{\sqrt{400r^3}}^{\infty} \frac{1}{\sqrt{2\pi}}
e^{-\frac{u^2}{2}} du.
\]

The plots are given in the Figures~\ref{fig:3b} and~\ref{fig:3blog}.
In each case, the x-axis is the ration $r$ and the y-axis is the BER
(in log-scale, in the second figure).
\begin{figure}[ht]
\begin{center}
%\epsfig{file=convolution.eps,width=0.5\textwidth}
\centerline{\epsfxsize = 4in \epsffile{3b.eps}}
%\includegraphics[width=0.5\textwidth]{3b}
\caption{\label{fig:3b}}
\end{center}
\end{figure}

\begin{figure}[ht]
\begin{center}
\centerline{\epsfxsize = 4in \epsffile{3blog.eps}}
%\epsfig{file=convolution.eps,width=0.5\textwidth}
%\includegraphics[width=0.5\textwidth]{3blog}
\caption{\label{fig:3blog}}
\end{center}
\end{figure}

{\bf 4. (6 points) Pseudo-random number generation} 

Problem 7.9.

{\bf Answer:} Assuming $X_0 = 1$, the two sequences are
\[
1, 6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1, \ldots, \mbox{ and}
\]

\[
1, 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1, \ldots.
\]
They are both deterministic sequences with full period and both appear
equally random.

{\bf 5. (8 points) Error-correcting codes} \hs 

An early code used in radio transmission involved codewords that
consist of binary bits and contain the same number of 1s.  Thus, the
two-out-of-five code only transmits blocks of five bits in which two
bits are 1 and the others 0.
\begin{itemize}
\item[{\bf (a)}] 
List the valid codewords.

{\bf Answer:} They are 

{\noindent 11000}\\
10100\\
10010\\
10001\\
01100\\
01010\\
01001\\
00110\\
00101\\
00011

\item[{\bf (b)}]
Suppose the code is used to transmit blocks of binary bits.  How many
bits can be transmitted per codeword?

{\bf Answer:} There are 10 possible codewords.  Three bits per
codeword can be transmitted if eight codewords are used.

\item[{\bf (c)}]
What pattern does the receiver check to detect errors?

{\bf Answer:} Each received codeword should have exactly two bits that
are 1s and three bits that are 0s to be a valid codeword.

\item[{\bf (d)}]
What is the minimum number of bit errors that cause a detection
failure?

{\bf Answer:} A valid codeword can be changed into another invalid
codeword by changing a 1 to a 0 and a 0 to a 1 in the first codeword.
Therefore, two bit errors can cause a detection failure.
\end{itemize}

{\bf 6. (10 points) Convolutional encoding}

Problem 8.20.

\begin{figure}[h]
\begin{center}
%\epsfig{file=convolution.eps,width=0.5\textwidth}
\centerline{\epsfxsize = 4in \epsffile{convolution.eps}}
%\includegraphics[width=0.5\textwidth]{convolution}
\end{center}
\end{figure}

{\bf 7. (6 points) CRC}

Prove that the CRC coding technique can detect any burst errors for
which the length of the burst is less than or equal to the length of
the frame check sequence (number of redundant bits), as long as the
most significant and least significant bits of the CRC code are both
1.

{\bf Answer:} We are given a degree-$k$ data polynomial $D(X)$
and a degree $n-k$ CRC polynomial $P(X)$.  Let the encoded data be
represented by the polynomial $Z(X)$.  Thus, $Z(X)$ is a multiple of
$P(X)$.  Suppose, we encounter an error given by $E(X)$, which is
represented by $X^i + X^{i+1} + \ldots + X^{i+\ell}$, where $\ell$ is
at most $n-k-1$.  Thus, we have 
\[
E(X) = X^i (1 + X + X^2 + \ldots + X^{\ell}).
\]
An $n-k$ degree polynomial $P(K)$ with the highest and lowest
coefficient being 1 cannot divide $E(X)$ since it is not possible for
the highest order and lowest order terms of any multiple of $P(X)$ to
be $X^i$ and $X^{i+\ell}$.

\end{document}

