CS计算机代考程序代写 scheme algorithm CEG3185 Winter 2021 Tutorial 1

CEG3185 Winter 2021 Tutorial 1
Problem 1
CEG 3185-Winter 2021 TUTORIAL 1
1) Express the following in the simplest form you can: 1. sin(2ft-)+ sin(2ft+)
2. sin(2ft)+sin(2ft-) Solution
1) sin (2ft – ) + sin (2ft + ) = 2 sin (2ft +) or 2 sin (2ft – ) or –2 sin (2ft) 2) sin (2ft) + sin (2ft – ) = 0.
Problem 2
Consider the periodic functions f1(t) and f2(t), with periods T1 and T2 respectively. Is it always the case that the function f(t) = f1(t) + f2(t) is periodic? If so, demonstrate this fact. If not, under what conditions is f(t) periodic?
Solution
If f1(t) is periodic with period X, then f1(t) = f1(t+X) = f1(t+nX) where n is an integer and X is the smallest value such that f1(t) = f1(t+X). Similarly, f2(t) = f2(t+X) = f2(t+mX) with m being an integer. We have f(t) = f1(t) + f2(t). If f(t) is periodic with period Z, then f(t) = f(t + Z). Therefore f1(t) + f2(t) = f1(t + Z) + f2(t + Z). This last equation is satisfied if f1(t) = f1(t + Z)) and f2(t) = f2(t + Z). This leads to the condition Z = nX = mY for some integers n and m. We can rewrite this last as (n/m) = (Y/X). We can therefore conclude that if the ratio (Y/X) is a rational number, then f(t) is periodic.
different codes can be defined. The actual number is less, since some codes, such as space, are “don’t-cares” with respect to shift locks.
Problem 3
Given an amplifier with an effective noise temperature of 10,000 K and a 10 MHz bandwidth, what thermal noise level, in dBw, may we expect at its output?
Solution
N = 10 log K + 10 log T + 10 log B = –228.6 dBw + 10 log 104 + 10 log 107 = –228.6 + 40 + 70 = –118.6 dBw
Problem 4
[Type the company name] 1

CEG3185 Winter 2021 Tutorial 1
What is the thermal noise level of a channel with a bandwidth of 10 KHz carrying 1000 watts of power and operating at 50o C?
Solution
N = 1.38 10–23 (50 + 273) 10,000 = 4.5 10–17 watts
Problem 5
If the received signal level for a particular digital system is -151 dBw and the receiver’s effective noise temperature is 1500 K, what is the Eb/No for a link transmitting 2400 bps?
Solution
Eb/No
Eb = Pr*Tb=Pr/rT
N0 kT
N0 = noise power density
k = Boltzmann’ s constant = 1.3803 x E-23 J/oK T = temperature (oK)
(Eb/No) = –151 dBw – 10 log 2400 – 10 log 1500 + 228.6 dBw = 12 dBW
Problem 6
The communication path connecting a sending and a receiving computing device, consists of five links of equal size. In addition to attenuation, the signals passing through these links are impaired by additive noise of zero mean value. The links have identical attenuation and additive noise characteristics. The additive noise process of each link is independent for the noise processes of the other links. The input of each link is equipped with an amplifier. The gain of the amplifier is such that, after amplification, the power of the information signal is restored to its original value (the value the signal had when it left the transmitter of the sending computer). The power of the information signal at the output of the first link is 100 mW, whereas the power of the additive noise is 10 mW. Calculate the Signal-to-Noise (SNR) ratio at the input of the receiving computer.
Solution
Since the input of each link is equipped with an adapted amplifier (the amplifier gain is such that the original signal is restored), the output signal is just the sum of the original signal and the
[Type the company name] 2

CEG3185 Winter 2021 Tutorial 1
additive noise. So, at the output the kth (k=1,2,..,5) link the power of the signal is given by:
P  P  kN , where P is the power of the information signal at the input of the first link, N
out,k in in
is the power of the noise process of each link (the powers of the noise of the different links add
up because their noise processes are assumed independent,; which means that they are not correlated).
in The SNR is given by: SNR 10log P
in
10log P , where N
is the power of the noise at the output of the fifth link. We have Pin  100mW and N = 10mW. Then,
SNR  10 log 100  10 log 2  3dB . 50
Problem 7
Deduce the maximum theoretical information rates associated with the following transmission channels:
a) Telex network with a bandwidth of 500 Hz and a signal-to-noise ratio of 5dB.
b) Switched telephone with a bandwidth of 3100 Hz and a signal-to-noise ratio of 20 dB.
Solution
C  W log 2 (1  S / N ) where S / N  10
Place the values of SNR (dB) (5 dB and 20 dB for (a) and (b) respectively, you get the answer.
Nt
5N
t
SNR(dB) 10
[Type the company name] 3

CEG3185 Winter 2021 Tutorial 1
Problem 8
A CRC is constructed to generate a 4-bit FCS for an 11-bit message. The generator polynomial G(X)=X4+ X3+1
a. Draw the shift register circuit that would perform the task.
b. Encode the binary data sequence 10011011100, where the rightmost bit is the most
significant. Use the generator polynomial and give the codeword.
c. Assume that bit 5, counting from the most significant bit, of the received codeword is in
error. Show that the detection algorithm detects the error.
Solution
PARITY BITS OUTPUT
INPUT
NOTE: after passing all information bits through the shift register, the content of the 4 storing elements contain the parity bits, which have to be read out.
1) Information sequence: 10011011100 M(X)=1+X3+X4+X6+X7+X8.
x4M(x)=X12+X11+X10+X8+X7+X4.
x4M(x)/G(x)=[X12+X11+X10+X8+X7+X4/ X4 + X3 + 1]= X8+ X6 + X5 + X4 + X2 + [X2 / X4 + X3 +
1]R(x)=X2. T(x)=X4M(x)+R(X)=X12+X11+X10+X8+X7+X4+X2. Code=0010 10011011100.
3) code=001010001011100
T(X)/G(X) yields a remainder R(X)= X3+X. Since it is not null, the decoder will “output” the received codeword is not correct.
C3
C2
C1
C0
[Type the company name] 4

Problem Solving Tutorial 2
CEG3185 University of Ottawa
Navid Khalili

Problem 1
Problem Statement:
–RAB = 1 Mbps
– RBC = R
– Prop. Delay = 5 𝜇𝑠/𝑘𝑚 for both lines
– There are full-duplex lines between the nodes
– All data frames are 10,000 bits long
– The size of the Ack packets is assumed negligible (≈ 0) – A → B: sliding-window, size = N
– B → C: stop-and-wait
CEG3185 – Problem Solving Tutorial 2 Winter 2021 2 of 25

Problem 1 – Cont.
Question (a):
The minimum value of R and corresponding maximum value of N that maximize the throughput of the A → B → C connection, without overflowing the buffer at node B.
CEG3185 – Problem Solving Tutorial 2 Winter 2021 3 of 25

Problem 1 – Cont.
Answer (a):
A→B: (Sliding-window)
Prop. time: 𝜏(A→B)= 4,000 km × 5 𝜇𝑠 = 20 msec Trans. time/frame: TF(A→B)=10,000/106 = 10 msec
B→C: (Stop-and-wait)
Prop. time 𝜏(B→C)= 1,000 km × 5 𝜇𝑠 = 5 msec
CEG3185 – Problem Solving Tutorial 2 Winter 2021 4 of 25

Problem 1 – Cont.
Answer (a) – Cont.:
A → B: Transmission time per frame N= 5
CEG3185 – Problem Solving Tutorial 2 Winter 2021 5 of 25

Problem 1 – Cont.
Answer (a) – Cont.:
B→C Assumption:
– L frames passed from A to B Circle duration for the A→B: 50ms
LTF(B→C) + L10ms ≤ 50ms CEG3185 – Problem Solving Tutorial 2
Winter 2021
6 of 25

Problem 1 – Cont.
Answer (a) – Cont.:
B→C
Eq.(1):0<𝐿𝑇 𝐵 𝐶 +𝐿10𝑚𝑠𝑒𝑐 ≤50𝑚𝑠𝑒𝑐 0<𝑇 L = 5  L = 4 ✓ ∴ 50𝑚𝑠𝑒𝑐 − 10𝑚𝑠𝑒𝑐 = 𝟐. 𝟓 𝒎𝒔𝒆𝒄 𝐿 For the transmission of 10,000 bits in 2.5 msec: 𝑅 𝐵 𝐶 ≥10,000𝑏𝑖𝑡𝑠=𝟒𝑴𝒃𝒑𝒔 2.5 𝑚𝑠𝑒𝑐 𝐹𝐹 𝐵 𝐶 ≤50𝑚𝑠𝑒𝑐 −10𝑚𝑠𝑒𝑐 𝐿 CEG3185 - Problem Solving Tutorial 2 Winter 2021 7 of 25 Problem 1 – Cont. Question (b): Determine the minimum size at B, that ensures no packets coming from A are been lost because of buffer overflow at B. Assume that initially, the packet is collected in the buffer of the NIC terminating the A → B connection, and is moved the NIC to the B’s buffer, only after the entire packet has been absorbed. CEG3185 - Problem Solving Tutorial 2 Winter 2021 8 of 25 Problem 1 – Cont. Answer (b): Input buffer of node B ≥ 2 CEG3185 - Problem Solving Tutorial 2 Winter 2021 9 of 25 Problem 2 Question: Assume a system transmits characters. Each character consists of n information bits (n is even number) and 1 parity bit. We are assuming that bit errors are occurring randomly and are uncorrelated with each other. Determine the probability a character might be damaged (one or more bits are in error) and it goes undetected that errors have occurred. The parity check used per character is even. CEG3185 - Problem Solving Tutorial 2 Winter 2021 10 of 25 Problem 2 – Cont. Answer: - Assumption: - Total number of bits in a character = n plus parity bit = n + 1 - The probability a character contains even number of errors: 𝑷𝑬 - The probability of a bit is in error: 𝑝𝑏 For n even: 𝑛 + 1 𝑛 + 1 𝑬2𝑏𝑏4𝑏𝑏𝑛𝒃𝑏𝑖 = 𝑛+1 𝑝2 1−𝑝 𝑛+1−2+ 𝑛+1 𝑝4 1−𝑝 𝑛+1−4+⋯+ 𝑛+1 𝑝𝑛 1−𝑝 ֞𝑃 2𝑏𝑏 4𝑏𝑏 𝑛𝑏𝑏𝑖 𝑷 = 𝑝2(1−𝑝 )𝑛+1−2+ 𝑛 + 1 𝑝4(1−𝑝 )𝑛+1−4+⋯+ 𝑝𝑛 1−𝑝 𝑛+1−𝑛 ֞𝑃 𝑛 𝑛 2 = ෍ 𝑛+1 𝑝𝑗 1−𝑝𝑏 𝑛+1−𝑗 =෍ 𝑛+1 𝑝2𝑘 1−𝑝𝑏 𝑛+1−2𝑘 𝑗 𝑏 2𝑘 𝑏 𝑗=2,4,6... 𝑘=1 CEG3185 - Problem Solving Tutorial 2 Winter 2021 11 of 25 Problem 3 Question (a): In a CRC error detecting scheme, we choose generator polynomial G(X)=X4+X+1. Encode the information bits 10010011011. Answer (a): X10 +X7 +X4 +X3 +X+1 X4 + X + 1 G(X)=X4+X+1 = 10011 = 5 – 1= 4 bits = X3 + X2 CEG3185 - Problem Solving Tutorial 2 Winter 2021 12 of 25 Problem 3 – Cont. Answer (a) – Cont.: X10 + X6 + X4 + X2 X4+X+1)X14+X11+X8+X7+X5+X4 X14+X11+X10 X10+X8+X7+X5+X4 X10+X7+X6 X8+X6+X5+X4 X8+X5+X4 X6 X6+X3+X2 X3+X2 CRC bits = 1100 The string is sent = 100100110111100 CEG3185 - Problem Solving Tutorial 2 Winter 2021 13 of 25 Problem 3 – Cont. Question (b): The channel introduces an error pattern 100010000000000 (flip from 1 to 0 or from 0 to 1 in positions 1 and 5). What is received? Can the error be detected? Answer (b): The string is received = 000110110111100 = X11 + X10 + X8 + X7 + X5 + X4 + X3 + X2 X11 +X10 +X8 +X7 +X5 +X4 +X3 +X2 =X3 +X2 +X (Errordetected) X4 + X + 1 CEG3185 - Problem Solving Tutorial 2 Winter 2021 14 of 25 Problem 3 – Cont. Question (c): Repeat part (b) with error pattern 100110000000000. Answer (c): The string is received = 000010110111100 = X10 + X8 + X7 + X5 + X4 + X3 + X2 X10 +X8 +X7+X5+X4+X3+X2 =0 (Noerrordetected) X4 + X + 1 CEG3185 - Problem Solving Tutorial 2 Winter 2021 15 of 25 Problem 4 Problem Statement: Suppose you are tuning up window protocols for a 1 Mbps point-to-point full duplex errorless link to the moon. The distance between the earth and the moon is approximately 360,000 kilometers, and the data travels over the link at the speed of light, i.e., 300,000 kilometers per sec. A camera on the moon takes pictures of the earth and saves them in digital format to a disk. Suppose Mission Control on earth wishes to download the most current image, which is 25 MB. Assume that the data frame carries 1,000 Bytes of data and that the only control information appended to the data is the frame sequence number (See Frame figure below). header data CEG3185 - Problem Solving Tutorial 2 Winter 2021 16 of 25 Problem 4 – Cont. Question (a): Calculate the earth-to-moon propagation delay. Answer (a): 𝜏𝑝 =360,000 km / 300,000 (km/sec)=1.2 sec CEG3185 - Problem Solving Tutorial 2 Winter 2021 17 of 25 Problem 4 – Cont. Question (b): Assume the use of a go-back N protocol. Determine the minimum window size that would allow the sender to keep transmitting continuously. In this case, how many bits are required to represent the packet sequence number? CEG3185 - Problem Solving Tutorial 2 Winter 2021 18 of 25 Problem 4 – Cont. Answer (b): - Each frame generates 25,000,000 bytes/1,000 bytes= 25,000 payloads - The transmission time of one frame: TF = 1,000 bytes x 8 bits/106 bps = 0.008 sec - Assumption: frame payload = 1Kb - First frame ack receives after 2𝜏𝑝 + TF = 2.408 sec - Number of frames transmitted during this time: NF=(2.408 sec / 0.008 sec) = 301 frames - Assumption: the transmission remains continuous CEG3185 - Problem Solving Tutorial 2 Winter 2021 19 of 25 Problem 4 – Cont. Answer (b) – Cont.: - 256 < 301 < 512 ∴ we need 9 bits - We need 2 bytes to form the header - The transmission time of one frame (recalculate) : TF = (1,002 bytes x 8 bits/106 bps) = 0.008016 sec - NF=(2.408016 sec / 0.008016 sec) =300.4 ≈ 301 frames CEG3185 - Problem Solving Tutorial 2 Winter 2021 20 of 25 Problem 4 – Cont. Question (c): Calculate the time Mission Control has to wait for the image to be transferred, i.e., the time elapsed between the instant the request for the image is sent until the image is completely received at Mission Control. Assume that the transmission time of the request command is equal to 10ms and that processing times are negligible. CEG3185 - Problem Solving Tutorial 2 Winter 2021 21 of 25 Problem 4 – Cont. Answer (c): - Transmission time of the image: 10 msec + 1.2 sec = 1.21 sec - Window size ≥ 301 - Camera must send (payloads): 25,000 frames - Total time for the image to reach the earth: - 25,000 x TF + 𝜏𝑝 = 25,000 x 0.008016 sec = 200.4 sec + 1.2 sec = 201.6 sec - 201.6 sec + 1.21 sec = 202.81 sec CEG3185 - Problem Solving Tutorial 2 Winter 2021 22 of 25 Problem 4 – Cont. Question (d): This time assume use of a selective repeat protocol. Determine the minimum window size that would allow the sender to keep transmitting continuously. In this case, how many bits are required to represent the packet sequence number? CEG3185 - Problem Solving Tutorial 2 Winter 2021 23 of 25 Problem 4 – Cont. Answer (d): - The “go-back N” and “selective repeat” protocols differ only on the way they handle the retransmission of lost frames. The sending process is the same, thus, the answer is identical with part c. CEG3185 - Problem Solving Tutorial 2 Winter 2021 24 of 25 Suggested Reading • William Stallings , Data and Computer Communications, Pearson Prentice Hall CEG3185 - Problem Solving Tutorial 2 Winter 2021 25 of 25