F23_SYSC4602_Assignment2_Solution

pdf

School

Carleton University *

*We aren’t endorsed by this school

Course

4602

Subject

Electrical Engineering

Date

Jan 9, 2024

Type

pdf

Pages

Uploaded by ChefOyster3965

1/4 SYSC 4602 Fall 2023 Assignment 2 Solution 1. Consider an information source generating one sample at a time. Each sample may take one of the two random outcomes x = 0 or 1 with probabilities of 1 - p or p respectively. What is the average amount of information (also called entropy) each sample will carry? Show that when ࠵? = ! " , the entropy achieves its maximum. Solution: By the definition of information, the information carried by each sample will be −log " (1 − ࠵?) or −log " (࠵?) for x = 0 or 1 respectively. Therefore, the average amount of information (i.e., entropy) will be ࠵?(࠵?) = −࠵?log " (࠵?) − (1 − ࠵?)log " (1 − ࠵?) . To get the ࠵? that maximizes the entropy, we set its gradient to 0 as #$(&) #( = −log " (࠵?) − ࠵? ! ()* " + log " (1 − ࠵?) + (1 − ࠵?) ! (!,() )* " = −log " (࠵?) + log " (1 − ࠵?) = 0 , 1 − ࠵? = ࠵? , ࠵? = ! " . ( The following part is optional. ) It’s easy to see that, when ࠵? < 1/2 , log " (1 − ࠵?) > log " (࠵?), #$(&) #( > 0 . When ࠵? > 1/2 , log " (1 − ࠵?) < log " (࠵?) , #$(&) #( < 0 . Therefore, when ࠵? = 1/2 , ࠵?(࠵?) achieves its maximum value 1. 2. Suppose a TDM multiplexer has two input streams, each at a nominal rate of 1Mbps. To accommodate deviations from the nominal rate, the multiplexer transmits at a rate of 2.2 Mbps as follows. Each group of 22 bits in the output of the multiplexer contains 18 positions that always carry information bits, nine from each input. The remaining four positions consist of two flag bits and two data bits. Each flag bit indicates whether the corresponding data bit carries user information or a stuff bit because of user information was not available at the input. a. Suppose that the two input lines operate at exactly 1 Mbps. How frequently are the stuff bits used? b. How much does this multiplexer allow the input lines to deviate from their nominal rate? Solution: a. In this case, the stuff bits are always used because the information bits alone only provide an aggregate bit rate of 1.8 Mbps. b. This multiplexer provides either 9 or 10 bits for each stream per 22-bit frame. Thus it allows either of the two input streams to transmit as low as 0.9 Mbps and as high as 1.0 Mbps.

2/4 3. A CDMA receiver gets the following chips: (-1 +1 -3 +1 -1 -3 +1 +1). Assuming the following chip sequences used by four sending stations, which stations transmitted, and which bits did each one send? Solution: Clearly, stations A, B, and D transmitted bits 1, 0, 1 respectively while station C did not transmit. 4. Consider a noiseless 4-kHz channel. What is the maximum data rate? How does the maximum data rate change if the channel is noisy, with a signal-to-noise ratio of 30 dB? How many symbols (or levels) do you need to achieve this data rate? Solution: A noiseless channel can carry an arbitrarily large amount of information, no matter how often it is sampled. Just use as many symbols (or levels) as you need per sample. For the 4-kHz channel, the Nyquist sampling rate will be 8000 samples/sec. If each sample is 16 bits, the channel can send 128 kbps. If each sample is 1024 bits, the channel can send 8.2 Mbps. The key word here is ‘‘noiseless.’’ With a normal 4 kHz noisy channel, the Shannon limit would not allow this. A signal-to-noise ratio of 30 dB means S/N = 1000. Using Shannon theorem with B = 4000, we get a maximum data rate of about 39.86 kbps. With 8000 samples/sec, each sample will carry around 4.98 bits. So, we need around 2 -./0 ≈ 32 symbols. 5. One way of detecting errors is to transmit data as a block of n rows of k bits per row and add parity bit to each row and each column. The bit in the lower-right corner is a parity bit that checks its row and its column. Will this scheme detect all single errors? Double errors? Triple errors? Show that this scheme cannot detect some four-bit errors. Solution: A single error will cause both the horizontal and vertical parity checks to be wrong. Two errors will also be easily detected. If they are in different rows, the row parity will catch them. If they are in the same row, the column parity will catch them. Three errors will also be detected. If they are in the same row or column, that row’s or column’s parity will catch them. If two errors are in the same row, the column parity of at least one of them will catch the error. If two errors are in the same column, the row parity of at least one of them will catch the error. If they are at different row, the row parity of each of them will detect the error. A 4-bit error in

3/4 which the four error bits lie on the four corners of a rectangle cannot be caught since there are two errors in each row and column. 6. Suppose that a packet 1001 1100 1010 0011 is transmitted using Internet checksum (4-bit word). What is the value of the checksum? Solution: To obtain the checksum, we need to calculate the ones complement of the ones complement sum of the words. The ones complement sum is the same as sum modulo 2 4 -1 and adding any overflow of high order bits back into low-order bits: 0011 + 1010 = 1101 1101 + 1100 = 1001 + 1 = 1010 1010 + 1001 = 0011 + 1 = 0100 So, the Internet checksum is the ones complement of 0100, or 1011. 7. Suppose a node has a CPU with 1GHz clock and a one’s complement addition of two 16-bit numbers can be done in one clock cycle. Consider all packets have the size of 1500 bytes that include all overhead. How much time does it take for the CPU to process a packet for error detection with Internet checksum over the whole packet? Now we also assume that the node has an outgoing link with the capacity of 100Gbps. How much is the transmission time for a packet? Which part is the bottleneck of the node? Solution: The packet processing time for error detection will be !122/" !×!2 ! = 7.5 × 10 ,5 (࠵?) . The transmission time for a packet will be !122∗0 !22×!2 ! = 1.2 × 10 ,5 (࠵?). From the above results, processing time is clearly the bottleneck of the link. 8. A bit stream 1001 is transmitted using the standard CRC method. The generator code is 1011. Show the actual bit string transmitted. Suppose that the first bit sent is inverted during transmission error. Show that this error is detected at the receiver’s end. Give an example of bit errors in the bit string transmitted that will not be detected by the receiver. Solution: The message is 1001 and the generator is 1011. The message after appending three zeros is 1001000. The remainder on dividing 1001000 by 1011 is 110. So, the actual bits transmitted are 1001110. The received bit stream with an error in the first bit is 0001110. Dividing this by 1011 produces a remainder of 101, which is different from 0. Thus, the receiver detects an error. If the transmitted bit stream is converted to any multiple of 1011110, the error will not be detected. A trivial example is if all ones in the bit stream are inverted to 0. 9. A large population of slotted ALOHA users manages to generate 50 requests/sec, including both originals and retransmissions. Time is slotted in units of 40 msec.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

4/4 a. What is the chance of success on the first attempt? b. What is the probability of exactly k collisions and then a success? c. What is the expected number of transmission attempts needed? Solution: With 25 slots/second and an average or 50 requests/second, we have G = 2. Then use the slotted Aloha formulas in Sec. 4.2.1. a. With G =2 Poisson’s Law gives a probability of e - 2 . b. (1 - e - G ) k e - G =0. 135 ´ 0. 865 k . c. The expected number of transmissions is e G = 7. 4. 10. What is the length of a contention slot in CSMA/CD for a 2-km twin-lead cable (signal propagation speed is 82% of the signal propagation speed in vacuum)? Solution: Signal propagation speed in twin lead is 2.46 ´ 10 8 m/sec. Signal propagation time for 2 km is 8.13 ࠵? sec. So, the length of contention slot is 16.26 ࠵? sec.