BE Computer Engineering (Pokhara University) Data Communication (PU, CMM 220) Question Paper 2078 Nepal

(a) Guided vs. Unguided Media

Guided (wired) media carry signals along a solid physical conductor; the signal is directed and contained by the medium.

• Examples: twisted-pair cable, coaxial cable, optical fiber.

Unguided (wireless) media transmit signals as electromagnetic waves through free space (air/vacuum) without a physical conductor.

• Examples: radio waves, microwave, infrared, satellite links.

Comparison of guided media

Optical fiber gives the best performance (huge bandwidth, lowest attenuation, full EMI immunity) but at the highest cost; twisted pair is cheapest but weakest.

(b) Attenuation and Gain Calculations

Attenuation when power falls to one-half ($P_2 = P_1/2$):

$$A = 10\log_{10}\frac{P_2}{P_1} = 10\log_{10}(0.5) = 10 \times (-0.301) = -3.01\ \text{dB}$$

The loss is about 3 dB (negative sign indicates attenuation).

Gain when amplified by a factor of 10 ($P_3 = 10 P_2$):

$$G = 10\log_{10}(10) = +10\ \text{dB}$$

Overall gain (decibels add along a path):

$$G_{total} = -3.01 + 10 = +6.99 \approx +7\ \text{dB}$$

The overall result is a net gain of about 7 dB.

(a) Digital-to-Analog Modulation Schemes

In digital modulation a carrier $A\cos(2\pi f_c t)$ is varied according to the binary data.

Amplitude Shift Keying (ASK): the amplitude of the carrier is switched between two levels while frequency and phase stay constant. Binary 1 = carrier present (high amplitude), binary 0 = no/low carrier.

• Waveform: full-amplitude carrier bursts for 1s, flat/zero line for 0s.
• Application: low-cost optical fiber and infrared (LED on/off) links.

Frequency Shift Keying (FSK): the carrier frequency is switched between two values ($f_1$ for 1, $f_2$ for 0); amplitude constant.

• Waveform: tightly spaced cycles (high $f$) for one bit, widely spaced cycles (low $f$) for the other.
• Application: low-speed modems, caller-ID, RFID.

Phase Shift Keying (PSK): the carrier phase is shifted (e.g. $0°$ for 1 and $180°$ for 0 in BPSK); amplitude and frequency constant.

• Waveform: identical sinusoids with an abrupt 180° phase reversal at each 1→0 / 0→1 transition.
• Application: Wi-Fi, satellite and digital cellular systems (more noise-immune than ASK).

(b) Constellation Diagrams and Bit Rate

QPSK has 4 points spaced 90° apart on a circle (e.g. at 45°, 135°, 225°, 315°); each point carries 2 bits.

8-PSK has 8 points spaced 45° apart around the circle; each point carries 3 bits ($2^3 = 8$).

Bit rate for 8-PSK: each signal element (baud) carries $r = \log_2 8 = 3$ bits.

$$\text{Bit rate} = \text{Baud rate} \times r = 2000 \times 3 = 6000\ \text{bps} = 6\ \text{kbps}$$

(a) Comparison of Switching Techniques

Datagram switching best suits bursty data; circuit switching best suits constant-rate (voice) traffic.

(b) Three Phases of a Circuit-Switched Connection

[Caller]---(1 Setup: reserve path)--->[Switches]--->[Callee]
[Caller]<==(2 Data transfer: dedicated circuit)==>[Callee]
[Caller]---(3 Teardown: release path)--------->[Callee]

1. Circuit establishment (setup): a dedicated end-to-end path through the switches is reserved before any data flows.
2. Data transfer: data flows continuously over the reserved circuit with low, constant delay.
3. Circuit disconnect (teardown): the path is released and resources freed for other connections.

Why inefficient for data: data traffic is bursty, but the reserved circuit is held for the whole session even during idle gaps, so the guaranteed bandwidth sits unused and cannot be shared — leading to poor link utilization.

(a) CRC Computation

• Message: $M = 1101011011$ (10 bits)
• Generator: $G(x)=x^4+x+1 \Rightarrow$ divisor $= 10011$ (5 bits, so append $4$ zeros)
• Dividend: append 4 zeros → $1101011011\,0000$

Perform modulo-2 (XOR) division:

1101011011 0000 ÷ 10011

11010  XOR 10011 = 01001
 -> 10010 (bring down) XOR 10011 = 00001
 -> 00011 ... 000111 ... 0001110 XOR 10011

Working it out step by step (modulo-2):

  11010110110000
  10011
  -----
  01001110110000
   10011
   -----
  00000010110000
        10011
        -----
  00000000101000
          10011
          -----
  00000000001110  -> remainder (last 4 bits) = 1110

CRC (remainder) = 1110.

Transmitted codeword = message + CRC =

$$\mathbf{1101011011\,1110}$$

Receiver verification

The receiver divides the received 14-bit codeword $11010110111110$ by $10011$. Since the CRC bits were chosen to make the codeword exactly divisible by $G(x)$, the remainder is $0000$ → no error detected, frame accepted.

(b) Error Detection by CRC

• Single-bit error: a single error corresponds to an error polynomial $E(x)=x^i$. If $G(x)$ has at least two non-zero terms (more than one '1'), it cannot divide $x^i$ exactly, so a non-zero remainder appears and the error is detected.
• Burst error: a burst of length $L$ gives $E(x)=x^i(x^{L-1}+\dots+1)$. If the burst length $L \le r$ (the degree of $G(x)$, i.e. number of CRC bits), $G(x)$ cannot divide $E(x)$, so all such bursts are detected.

Condition to detect all single-bit errors: the generator polynomial must have more than one non-zero term (at least two 1s, i.e. it must not be a single power of $x$). A factor of $(x+1)$ additionally guarantees detection of all odd-numbered bit errors.

Multiplexing Techniques

• FDM: each channel occupies a different frequency sub-band of the link; all transmit simultaneously, separated by frequency.
• TDM: the full bandwidth is given to each channel in turn for short time slots.
• WDM: conceptually FDM applied to light — different wavelengths (colors) carried together on one fiber, combined and split by prisms/gratings.

Synchronous vs. Statistical TDM

Synchronous TDM: each input is pre-assigned a fixed time slot in every frame, whether or not it has data → empty slots waste bandwidth.

Statistical (asynchronous) TDM: slots are allocated dynamically only to inputs that actually have data, so slots carry an address; this raises utilization for bursty traffic.

Synchronous TDM frame:  | A | B | C | D |  (A & C idle => empty slots sent)
Statistical TDM frame:  | B:data | D:data |  (only active inputs; addr attached)

Causes of Transmission Impairment

1. Attenuation: loss of signal energy (power) as it travels through the medium, due to the resistance of the medium. The signal weakens with distance and is restored by amplifiers/repeaters. Measured in decibels.

2. Distortion: change in the shape of the signal. A composite signal contains components of different frequencies that travel at different speeds (different propagation delays), so they arrive with different phases, altering the received waveform.

3. Noise: unwanted random signals added to the data signal, corrupting it.

Types of Noise

• Thermal (Johnson) noise: random motion of electrons in the conductor; present in all media.
• Induced noise: from external sources such as motors and appliances acting as antennas.
• Crosstalk: signal of one wire/channel coupling into an adjacent one.
• Impulse noise: sudden high-energy spikes from lightning, power lines or switching.
• Intermodulation noise: new frequencies generated when signals of different frequencies share a non-linear medium.

Nyquist and Shannon

Nyquist theorem (noiseless channel): the maximum bit rate for a noiseless channel of bandwidth $B$ with $L$ signal levels is

$$C = 2B\log_2 L \ \text{bps}$$

Shannon capacity formula (noisy channel): the theoretical maximum capacity of a channel with bandwidth $B$ and signal-to-noise ratio $SNR$ is

$$C = B\log_2(1 + SNR) \ \text{bps}$$

Calculation

Given $B = 3000\ \text{Hz}$, $SNR_{dB} = 30\ \text{dB}$.

Convert SNR from dB to ratio:

$$SNR = 10^{30/10} = 10^3 = 1000$$

Apply Shannon's formula:

$$C = 3000 \times \log_2(1 + 1000) = 3000 \times \log_2(1001)$$ $$\log_2(1001) \approx 9.967$$ $$C \approx 3000 \times 9.967 \approx 29{,}901\ \text{bps} \approx 29.9\ \text{kbps}$$

Maximum theoretical channel capacity ≈ 30 kbps.

Pulse Code Modulation (PCM)

PCM converts an analog signal into a digital bit stream in three main steps.

Analog in --> [Sampling (S/H)] --> [Quantization] --> [Encoding] --> PCM bit stream

1. Sampling: the continuous analog signal is measured (sampled) at regular time intervals to produce a discrete-time PAM signal. By the Nyquist sampling theorem, the sampling rate must be at least twice the highest signal frequency, $f_s \ge 2 f_{max}$.

2. Quantization: each sample's amplitude is rounded to the nearest of a finite set of levels ($2^n$ levels for $n$-bit PCM). The rounding introduces quantization error/noise.

3. Encoding: each quantized level is represented as an $n$-bit binary code word, giving the digital output stream.

Required Sampling Rate

For a signal band-limited to $f_{max} = 4\ \text{kHz}$:

$$f_s \ge 2 \times 4\ \text{kHz} = 8\ \text{kHz} = 8000\ \text{samples/s}$$

So the minimum (Nyquist) sampling rate is 8000 samples per second — the basis of the 8 kHz rate used in digital telephony.

Comparison of ARQ Protocols

Summary: utilization order is Selective-Repeat > Go-Back-N > Stop-and-Wait, at the cost of increasing complexity and receiver buffering.

Hamming Distance

The Hamming distance $d(x, y)$ between two equal-length code words is the number of bit positions in which they differ (found by XOR-ing them and counting the 1s).

The minimum Hamming distance $d_{min}$ of a code is the smallest Hamming distance between any pair of valid code words. It determines the code's error-handling power.

Relation to Error Detection and Correction

• To detect up to $s$ errors: $\;d_{min} \ge s + 1$
• To correct up to $t$ errors: $\;d_{min} \ge 2t + 1$

For $d_{min} = 5$

Detection:

$$s = d_{min} - 1 = 5 - 1 = 4 \text{ errors detectable}$$

Correction:

$$t = \left\lfloor \frac{d_{min}-1}{2} \right\rfloor = \left\lfloor \frac{4}{2} \right\rfloor = 2 \text{ errors correctable}$$

The code can detect up to 4 errors and correct up to 2 errors.

Line Coding Schemes

(Waveforms described for the bit pattern; voltage levels noted.)

NRZ-L (Non-Return-to-Zero Level): the voltage level represents the bit — e.g. positive voltage = 0, negative = 1. The level stays constant for the whole bit; no transition unless the bit changes.

NRZ-I (Non-Return-to-Zero Inverted): the bit is encoded by transition: a 1 causes an inversion of level at the start of the bit, a 0 causes no change. This is differential, so it survives polarity reversal.

Manchester: each bit has a transition in the middle of the bit period. Convention: high→low transition = 0, low→high = 1 (or vice versa). The mid-bit transition both encodes data and provides clocking.

Differential Manchester: always has a mid-bit transition for synchronization; the data is encoded at the start of the bit — a 0 causes a transition at the start, a 1 causes no start transition.

Data:            1   0   1   1   0
NRZ-L:          ‾‾| __ |‾‾ |‾‾ | __     (level per bit)
NRZ-I:          (invert on 1, hold on 0)
Manchester:     each bit has a mid-bit edge
Diff-Manch.:    mid-bit edge always + start edge on 0

Advantage of Manchester over NRZ

Manchester encoding is self-clocking: the guaranteed mid-bit transition lets the receiver recover the clock and stay synchronized even during long runs of identical bits — whereas NRZ has no transitions during such runs, causing the receiver to lose synchronization.

Data Link Layer Functions

Framing: the data link layer packages the bit stream from the network layer into discrete frames, adding header and trailer (address, control, flag/delimiter, error-check) so the receiver can recognize where each frame starts and ends.

Flow control: a set of procedures that prevents a fast sender from overwhelming a slow receiver by limiting how much data can be sent before an acknowledgement (e.g. stop-and-wait or sliding-window).

Byte Stuffing (character stuffing)

Used in byte-oriented framing. A special flag byte marks frame boundaries. If the flag byte (or the escape byte) appears inside the data, an escape (ESC) byte is inserted before it so it is not mistaken for a real flag; the receiver removes the ESC.

Data:  ...  FLAG  ...
Sent:  ...  ESC FLAG  ...   (ESC inserted; ESC ESC for a real ESC)

Bit Stuffing

Used in bit-oriented framing (e.g. HDLC) where the flag is 01111110 (six consecutive 1s). To stop the data from accidentally containing the flag, the sender inserts a 0 after every five consecutive 1s in the data.

Flag delimiter:        0 1 1 1 1 1 1 0
Data containing 11111: 0 1 1 1 1 1 0 1   (after five 1s, insert 0)
                                 ^ stuffed 0

The receiver, on finding five 1s followed by a 0, removes that stuffed 0; a 0111111 0 sequence is recognized as the genuine flag. This guarantees the flag pattern never appears in the payload.