College of Computer & Information Science Spring 2010 Northeastern University Handout 5 CS 6710: Wireless Networks 12 March 2010

Sample Solution to Problem Set 2

1. (6 points) Number of quantization levels in PCM

Consider an audio signal with frequency components in the range 300 to 3000 Hz. Suppose we generate a PCM signal with 6000 samples per second.

(a) What is the number of uniform quantization levels needed to achieve an SNR of 30 dB?

SNRdB equals 6.02n + 1.76 dB. So we obtain n ≥ (30 − 1.76)/6.02 ≥ 4.69. That is we need n ≥ 5, implying 32 quantization levels.

(b) What data rate is required?

With 6000 samples per second and 5 bits per sample, we obtain a data rate of 30000 bps.

2. (12 points) FHSS Consider an MFSK scheme with carrier frequency f_{c} equal to 250 kHz, difference frequency f_{d} equal to 25KHz, and M equal to 8 (L equal to 3 bits).

(a) Make a frequency assignment for each of the eight possible 3-bit data combinations.

Here is one possible frequency assignment:

String Frequency (kHz)
000  75
001  125
010  175
011  225
100  275
101  325
110  375
111  425

We wish to apply FHSS to this MFSK scheme with k = 2; that is, the system will hop among four different carrier frequencies. Suppose the data rate is R bps, so the duration of a bit is T = 1/R seconds.

(b) Consider a slow FHSS with T_{c} (the period at which the MFSK carrier frequency changes) being 2T_{s}, where T_{s} is the duration of a signal element. Show the sequence of frequencies used, and the times the frequency changes occur, for transmitting the bit string 011110001.

Let f_{ij} denote the frequency associated with the jth string of the ith carrier frequency, where 0 ≤ i < 4, and 0 ≤ j < 8. Thus, for example, if the ith carrier frequency is F kHz, then f_{ij} equals F + (j − 4) · 50 + 25 kHz.

Under slow FHSS with T_{c} = 2T_{s}, frequency hops occur every 2 signal elements, so 6 bits.

Suppose PN sequence for generating the frequency hops starts with the sequence 0011. Then, the frequencies used would be the following:

f_{03}, f_{06}, f_{31},

where frequency changes occur every T_{s} time units.

(c) Consider a fast FHSS with T_{s} being 4T_{c}. Show the sequence of frequencies used, and the times the frequency changes occur, for transmitting the bit string 011110001.

As above, let f_{ij} denote the frequency associated with the jth string of the ith carrier frequency, where 0 ≤ i < 4, and 0 ≤ j < 8.

Under fast FHSS with T_{s} = 4T_{c}, frequency hops occur every T_{s}/4 time units.

Suppose the PN sequence is 001101110010110100011111. Then, the frequencies used would be the following:

f_{03}, f_{33}, f_{13}, f_{33}, f_{01}, f_{21}, f_{31}, f_{11}, f_{06}, f_{16}, f_{36}, f_{36},

frequency changes occur every T_{s}/4 time units.

3. (8 points) DSSS

Sketch the transmitted DSSS signal s(t)c(t) over the time interval [0, 2T_{b}] (two bit times) asssuming that s(t) is BPSK modulated with carrier frequency 100 MHz and T_{s} is 1 μs. Assume the first data bit is a 0 and the second is a 1. Assume that there are ten chips per bit and the chips alternate between +1 and −1 with the first chip equal to +1.

Answer: The signal has 100 time periods in 1 μs. So each chip should have 10 time periods of the signal, and we would have phase shifts every 10 time periods of the signal; at the 1μs point, however, when we move from a 1 bit to a 0 bit, there will not be any phase shift since the chip change and bit change cancel each other. In the given figure, all times are in μs.

4. (12 points) Balance, run-length, and shifts

Consider a random binary sequence of N = 2^{n} − 1 bits, where each bit is generated independently and uniformly at random.

(a) What is the expected number of 0s and 1s in this sequence?

For a bit uniformly chosen at random, the expected number of 0s (resp., 1s) is 1/2. By linearity of expectation, the expected number of 0s (resp., 1s) in a random binary sequence of N bits is N/2.

(b) If we slide a window of length n along the sequence for 2^{n−1} shifts, what is expected number of occurrences of a given n-bit string.

The probability that a given n-bit string occurs in a particular shift equals 1/2^{n} since there are 2^{n} different n-bit strings, each equally likely. So the expected number of occurrences of a given n-bit string in 2^{n−1} shifts is 2^{n−1}/2^{n} = 1/2.

(c) What is the expected number of runs of length k, for a given k?

In a string of length N, there are N − k + 1 starting positions for the run. The probability that the run exists at the beginning of the string is 1/2^{k+1} (k 1s followed by a 0). The same holds for the end. For the remaining N −k +3 positions, the probability is 1/2^{k+2} (0 followed by k 1s followed by a 0). Thus, the expected number of runs of length k equals

(N − k + 3)/2^{k+2} + 2/2^{k+1} = 2^{n−k−2} − k/2^{k+2} + 3/2^{k+1}.

(d) For each of the above answers, compare with the equivalent counts in an m-sequence, and comment.

An m-sequence of length N has 2^{n−1} 1s, 1/2 more than expected number of 1s in the random binary sequence (see part (a)). The m-sequence has 2^{n−1} − 1 0s, 1/2 less than the expected number of 0s in the random binary sequence (see part (a)). So these two counts almost match.

Each n-bit string (other than all 0s) appears exactly once in the m-sequence. The expected number of occurrences of an n-bit string is 2^{n−1} shifts – covering roughly half of the N-bit string – is 1/2. Thus, again, the number of occurrences in m-sequences almost matches the expectation in a random binary sequence.

The number of runs of length k in an m-sequence equals 2^{n−k−2}, k < n. This again is very close to the expectation computed in part (c).

Thus, the counts for these occurrences in a (deterministic) m-sequence is very close to the expectations of the same counts in a random binary sequence.

5. (6 points) A simple block code

Consider a simple block code in which each codeword consists of 4 data bits and one parity bit. List all the codewords of this code. What is the minimum distance between two codewords of this code?

Each codeword has 5 bits. Let the first 4 bits be the data bits, and the last bit the parity bit. The 16 codewords are

00000, 00011, 00101, 00110, 01001, 01010, 01100, 01111, 10001, 10010, 10100, 10111, 11000, 11011, 11101, 11110.

The minimum distance between two codewords is 2.

6. (6 points) Codes and generator polynomials

Consider a Hamming code with the generator polynomial g(X) = 1 + X + X^{4}. Determine if the codewords described by the polynomials c_{1}(X) = 1 + X + X^{3} + X^{7} and c_{2}(X) = 1 + X^{3} + X^{5} + X^{6} are valid codewords for this generator polynomial.

We divide c_{1}(X) by g(X) to obtain that c_{1}(X) = g(X) · (1 + X^{3}), so c_{1}(X) is a valid codeword. We divide c_{2}(X) by g(X) to obtain a remainder of X + 1, so c_{2}(X) is not a valid codeword.