College of Computer & Information Science Spring 2007 Northeastern University Handout 4 CSG250: Wireless Networks 13 February 2007

Sample Solutions to Problem Set 2

1. (10 points) Frequency-hopping spread spectrum

Problem 7.5.

Answer:

a. 15.

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 → f_{0}, 01 → f_{1}, 10 → f_{2}, 11 → f_{3}

c. log_{2} M = 2.

d. M = 4.

e. 3 bits per hop.

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.

g. 2^{3} = 8.

h. When we consider the dehopped frequencies, we can replace f_{i} by f_{j} where j = i mod 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}.

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?

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

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.

(a) Give the signal-to-interference ratio as a function of the distances between the two terminals and the base station.

(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.

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

Noise: Assume that there is no other background noise.

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 = ∫_{√\overline{2E_{b}/N_{0}}}^{∞} \frac{1}{\sqrt{2π}} 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.)

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 = ∫_{√\overline{400r^{3}}}^{∞} \frac{1}{\sqrt{2π}} e^{− \frac{u^{2}}{2}} du.

The plots are given in the Figures 1 and 2. In each case, the x-axis is the ration r and the y-axis is the BER (in log-scale, in the second figure).

4. (6 points) Pseudo-random number generation

Problem 7.9.

Answer: Assuming X_{0} = 1, the two sequences are

1, 6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1, …, and

1, 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1, ….

They are both deterministic sequences with full period and both appear equally random.

5. (8 points) Error-correcting codes

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.

Figure 1:

(a) List the valid codewords.

Answer: They are

11000 10100 10010 10001 01100 01010 01001 00110 00101 00011

(b) Suppose the code is used to transmit blocks of binary bits. How many bits can be transmitted per codeword?

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

(c) What pattern does the receiver check to detect errors?

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

(d) What is the minimum number of bit errors that cause a detection failure?

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.

Figure 2:

6. (10 points) Convolutional encoding

Problem 8.20.

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.

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} + … + X^{i+ℓ}, where ℓ is at most n − k − 1. Thus, we have

E(X) = X^{i}(1 + X + X^{2} + … + X^{ℓ}).

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+ℓ}.

5