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

\head{CSG250}{Wireless Networks}{Fall 2008}{6 October 2008}{1}

\begin{center}
\Large{\bf Problem Set 2 (due Wednesday, October 15)}
\end{center}

{\bf 1. Codes}
\begin{itemize}
\item[{\bf (a)}]
Hamming codes are \emph{perfect} linear codes of distance $3$. \emph{Perfect}
means that every word is at Hamming distance at most $1$ from a unique codeword.
Prove that it must be the case for any perfect $(n,k,3)$-code that $n = 2^t-1$
and $k=2^t-t-1$. [3]
\item[{\bf (b)}] 
Consider the $2^t-1 x t$ matrix whose $i$th row is the $t$-bit binary representation 
of $i, 1 \leq i \leq 2^t-1$. Prove that such a matrix is the parity check matrix of
a Hamming code. [3] 
\item[{\bf (c)}] 
Consider the set of codes generated by the $t x 2^t$ matrix whose $i$th column is 
the $t$-bit binary representation of $i, 0 \leq i \leq 2^t-1$. Prove that this linear
code has a distance of at least $2^(t-1)$. (Such codes are known as Hadamard codes.) [4]
\end{itemize}

{\bf 2. Hat problem}
Consider the hat problem presented in class where the professor tosses a coin and picks 
each student's hat. Students can see all hats except their own. If a nonzero subset 
speak up and  each person (who speaks up) correctly reports the color of their 
own hat then the professor gives everybody an A grade. If no students speak up or if
some student speaks up and says the wrong color of their hat then all the students fail. 
\begin{itemize}
\item[{\bf (a)}]
Prove that in the case of $3$ students it is possible for them to succeed with probability
at least $\frac{3}{4}$. [3]
\item[{\bf (b)}] 
Prove that in the case of $2^t-1$ students it is possible for them to succeed with 
probability at least $1-\frac{1}{2^t}$. [3]
\item[{\bf (c)}] 
Prove that it is not possible for $n$ students to fail with probability less 
than $\frac{1}{n+1}$. [4]
\end{itemize}

{\bf 3. Spread Spectrum}

\begin{itemize}
\item[{\bf (a)}]
What is spread spectrum? Describe the two main flavors of spread spectrum. [4]
\item[{\bf (b)}] 
What are the advantages and disadvantages of spread spectrum? [2]
\item[{\bf (c)}] 
Consider an MFSK scheme with carrier frequency $f_c = 250$ kHz, difference frequency 
$f_d = 25 kHz$, and number of different signal elements $M = 8$. Give a frequency assignment
for each of the possible $3$-bit data combinations. Now apply slow FHSS to this MFSK scheme 
with a pseudo-noise of $2$ bits or $4$ different channels and show the set of all frequency
assignments. [4]

\end{itemize}

\pagebreak

{\bf 4. Shannon's theorem}
\begin{itemize}
\item[{\bf (a)}]
What is the noise model for the discrete version of Shannon's theorem? What is the expected
number of errors given block length of $n$ and bit flip probability of $p$? [2]
\item[{\bf (b)}]
How many $0-1$ strings of length $n$ have exactly $pn$ $1$'s? Prove that this number
is asymptotically equal to $2^(nH(p))$ where $H(p) = -plg(p) - (1-p)\lg(1-p)$. [4]
\item[{\bf (c)}]
Prove the converse of Shannon's theorem in the discrete case, i.e. all 
encoding/decoding schemes that achieve a rate in excess of the channel capacity do so
with a success probability that is exponentially small. [4] 
\end{itemize}

{\bf 5. Fading and Modulation}
\begin{itemize}
\item[{\bf (a)}]
What is fading? Briefly explain the different causes of fading. What are three techniques
for dealing with fading? [3]
\item[{\bf (b)}]
Explain how Amplitude Modulation works. How is the signal encoded and what filters 
are used in the demodulation process to extract the signal at the receiver. [4]
\item[{\bf (c)}]
Describe how QAM works with an example. How is the signal encoded and how is it
decoded by filtering at the receiver's end? [3]
\end{itemize}
 
\end{document}