BE Computer Engineering (IOE, TU) Data Communication (IOE, CT 604 / ENCT 253) Question Paper 2078 Nepal

(a) Nyquist's theorem and Shannon's capacity formula

Nyquist (noiseless channel) bit-rate formula:

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

• $C$ = maximum bit rate (channel capacity) in bits per second
• $B$ = bandwidth of the channel in Hz
• $L$ = number of discrete signal (amplitude/phase) levels used to encode data

Nyquist applies to an ideal, noiseless channel: it tells the maximum rate at which signal levels can be reliably distinguished given the bandwidth.

Shannon's capacity formula (noisy channel):

$$C = B \log_2\!\left(1 + \frac{S}{N}\right) \ \ \text{(bps)}$$

• $C$ = theoretical maximum channel capacity in bps
• $B$ = bandwidth in Hz
• $S/N$ = signal-to-noise power ratio (a plain ratio, not in dB)

Shannon gives the upper bound imposed by noise, independent of the number of levels used. If $\text{SNR}_{dB}$ is given, convert: $S/N = 10^{(\text{SNR}_{dB}/10)}$.

(b) Numerical computation

Given: $B = 3300 - 300 = 3000$ Hz, $S/N = 3162$ (i.e. 35 dB).

Shannon capacity:

$$C = 3000 \times \log_2(1 + 3162) = 3000 \times \log_2(3163)$$ $$\log_2(3163) = \frac{\ln 3163}{\ln 2} \approx \frac{8.059}{0.693} \approx 11.63$$ $$C \approx 3000 \times 11.63 \approx 34{,}881 \ \text{bps} \approx 35 \ \text{kbps}$$

Nyquist — number of levels to (just under) reach this rate:

$$C = 2B \log_2 L \Rightarrow 34{,}881 = 2(3000)\log_2 L = 6000 \log_2 L$$ $$\log_2 L = \frac{34{,}881}{6000} \approx 5.81 \Rightarrow L = 2^{5.81} \approx 56$$

Since $L$ must be a usable power of two, choose $L = 2^5 = 32$ levels, giving a practical, achievable rate below capacity:

$$C_{prac} = 6000 \times \log_2 32 = 6000 \times 5 = 30{,}000 \ \text{bps} = 30 \ \text{kbps}$$

(Using $L=64$ would give 36 kbps, which exceeds the Shannon limit and is therefore unattainable in practice.)

Why the two results differ: Shannon gives the absolute upper bound set by noise and is independent of $L$ — you can never beat it. Nyquist gives the rate for a chosen number of levels on an ideal (noiseless) channel and places no limit on $L$. In a real noisy channel, increasing $L$ packs levels closer together until noise makes them indistinguishable, so the practical Nyquist rate must stay at or below the Shannon ceiling. Thus Shannon tells us how fast we can go; Nyquist tells us how to engineer the levels to get there without exceeding it.

(a) ASK, FSK, PSK (digital-to-analog modulation)

In digital-to-analog conversion a binary stream alters one parameter of a carrier $s(t)=A\cos(2\pi f_c t + \phi)$.

ASK (Amplitude Shift Keying): the amplitude changes with the bit; binary 1 = carrier present (amplitude $A$), binary 0 = no/low carrier (amplitude 0). The carrier waveform is a burst of full-amplitude sinusoid for 1 and a flat line (or reduced amplitude) for 0.

FSK (Frequency Shift Keying): the frequency changes; bit 1 = higher frequency $f_1$, bit 0 = lower frequency $f_2$, amplitude constant. The waveform shows closely-packed cycles for one bit value and widely-spaced cycles for the other.

PSK (Phase Shift Keying): the phase changes; bit 1 = phase $0\degree$, bit 0 = phase $180\degree$ (a phase reversal at each bit transition), amplitude and frequency constant. At every 0→1 or 1→0 change the sinusoid flips, appearing to "jump" by half a cycle.

Comparison:

(b) 8-QAM constellation and how QAM raises bit rate

8-QAM combines several amplitudes and several phases. A common 8-QAM constellation has two amplitude rings with four phase points each (or 4 phases × 2 amplitudes), giving 8 distinct points. Because $\log_2 8 = 3$, each signal element carries 3 bits, so for a given baud rate the bit rate is tripled compared with a 2-point scheme.

Constellation (described): 8 points plotted on the I (in-phase, x) vs Q (quadrature, y) plane — e.g. four points on an inner circle at $45\degree,135\degree,225\degree,315\degree$ and four on an outer circle at $0\degree,90\degree,180\degree,270\degree$. Each point = a unique combination of amplitude (distance from origin) and phase (angle).

QAM combines amplitude and phase modulation: by varying both $A$ and $\phi$ together, many more distinguishable symbols fit in the same bandwidth than amplitude-only or phase-only schemes, so $C = 2B\log_2 L$ rises with larger $L$.

(c) Constellation diagram; QPSK vs 4-QAM

A constellation diagram plots each signal element as a point whose horizontal coordinate is the in-phase (I) component and vertical coordinate is the quadrature (Q) component. The distance from the origin = amplitude and the angle = phase. It compactly shows how many bits/symbol a scheme carries and how far apart symbols are (noise margin).

4-PSK (QPSK): all 4 points lie on a single circle (constant amplitude), differing only in phase — typically at $45\degree,135\degree,225\degree,315\degree$.

4-QAM: also has 4 points and, in its simplest form, is identical to QPSK — 4 points of equal amplitude at four phases. In general QAM allows multiple amplitude rings, but for $L=4$ the standard 4-QAM constellation coincides with QPSK (same 4 phase-only points). The key conceptual difference: PSK is defined by phase only, whereas QAM permits amplitude variation as well, which becomes visible only at higher orders (8-QAM, 16-QAM).

(a) Pulse Code Modulation (PCM)

PCM converts an analog signal to a digital bit stream in three stages.

Block diagram (described):

Analog input → [Sampler (PAM)] → [Quantizer] → [Encoder] → Digital (PCM) output

1. Sampling: The continuous analog signal is sampled at regular intervals (rate $f_s$), producing a sequence of PAM (pulse-amplitude-modulated) samples. By the sampling theorem, $f_s \ge 2 f_{max}$ to avoid aliasing.

2. Quantization: Each sample's continuous amplitude is approximated to the nearest of $L = 2^n$ discrete levels. This introduces quantization error/noise; more levels ($n$ bits) reduce the error.

3. Encoding: Each quantized level is represented by an $n$-bit binary code word, producing the final PCM bit stream. The bit rate is $\text{bit rate} = f_s \times n$.

(b) Numerical

Bit rate: With 4 bits per signal element and 1000 signal elements/s:

$$\text{Bit rate} = \text{signal rate} \times \text{bits per element} = 1000 \times 4 = 4000 \ \text{bps} = 4 \ \text{kbps}$$

Minimum sampling rate (Nyquist): highest frequency $f_{max}=4$ kHz, so

$$f_s \ge 2 f_{max} = 2 \times 4\,\text{kHz} = 8\,\text{kHz} \ (8000 \ \text{samples/s})$$

Consequence of under-sampling: If $f_s < 2 f_{max}$, aliasing occurs — high-frequency components fold back and masquerade as lower frequencies, so the original signal cannot be faithfully reconstructed and the recovered signal is permanently distorted.

(a) Sliding Window flow control; Go-Back-N vs Selective-Repeat ARQ

Sliding Window: Instead of stop-and-wait, the sender may transmit up to a window of $W$ unacknowledged frames before pausing. As ACKs arrive, the window slides forward, allowing continuous transmission and far better link utilization. Sequence numbers (modulo $2^m$ for an $m$-bit field) label frames.

Go-Back-N ARQ:

• Sender window size up to $2^m - 1$; receiver window = 1 (frames must arrive in order).
• On a damaged/lost frame, the receiver discards that frame and all subsequent frames, sending no ACK (or a NAK).
• On timeout the sender retransmits the lost frame and every frame after it ("goes back N").
• Timing diagram (described): frames 0,1,2,3 sent; frame 2 corrupted; receiver discards 2,3; sender, on timeout, resends 2,3,4… Simpler receiver, but wasteful on noisy links.

Selective-Repeat ARQ:

• Sender and receiver windows each up to $2^{m-1}$.
• Receiver buffers correctly received out-of-order frames and ACKs them individually; it requests retransmission (NAK) only of the specific damaged frame.
• Sender retransmits only the lost frame; the buffered frames are then delivered in order.
• Timing diagram (described): frames 0,1,2,3 sent; frame 2 lost; receiver buffers 3 and NAKs 2; sender resends only 2; receiver then delivers 2,3. More efficient bandwidth use, but needs receiver buffering and more complex logic.

Window-size restriction: Go-Back-N: $W_s \le 2^m - 1$. Selective-Repeat: $W_s + W_r \le 2^m$, typically $W_s = W_r = 2^{m-1}$, to avoid ambiguity between old and new frames having the same sequence number.

(b) Go-Back-N with 3-bit sequence number

A 3-bit sequence number gives $2^3 = 8$ numbers (0–7). For Go-Back-N the maximum sender window size is:

$$W_{max} = 2^m - 1 = 2^3 - 1 = 7$$

Justification: If the window were the full $2^m = 8$, a situation arises where all 8 ACKs are lost; the receiver, expecting the next frame, cannot tell a retransmitted old frame 0 from a new frame 0 (same sequence number). Limiting the window to 7 leaves at least one sequence number unused at any time, removing the ambiguity.

Transmission impairment is any imperfection of the medium that causes the received signal to differ from the transmitted signal, degrading communication quality.

Three causes:

• Attenuation: loss of signal energy (amplitude) as it travels through the medium, due to medium resistance; signal must be amplified/repeated. Measured in decibels.
• Distortion: change in the shape of the signal because different frequency components travel at different speeds (delay) and arrive with different phases, so a composite signal is reshaped.
• Noise: unwanted random energy added to the signal from external or internal sources.

Two types of noise:

• Thermal noise: random motion of electrons in a conductor, present in all media at temperatures above absolute zero; uniformly distributed across frequencies (white noise) and cannot be eliminated.
• Crosstalk: unwanted coupling of a signal from one wire/channel into an adjacent one (the effect of one wire acting as antenna for another), e.g. hearing another conversation faintly on a telephone line.

Guided vs unguided media: Guided (wired) media confine and direct signals along a physical conductor — twisted pair, coaxial, optical fibre. Unguided (wireless) media propagate signals through free space (air/vacuum) as electromagnetic waves — radio, microwave, infrared — with no physical conductor and the path determined by antennas and the environment.

Twisted-pair cable: two insulated copper conductors twisted together (twisting reduces crosstalk and external interference); comes as UTP/STP. Applications: telephone local loop, LAN cabling (Cat 5/6 Ethernet). Cheap and easy to install; limited bandwidth and distance.

Coaxial cable: a central copper conductor surrounded by an insulating layer, a braided metallic shield, and an outer jacket. The shield gives higher bandwidth and better noise immunity than twisted pair. Applications: cable TV distribution, older Ethernet (10Base2/5), broadband.

Optical fibre: a thin glass/plastic core surrounded by cladding of lower refractive index; light is guided by total internal reflection, carrying data as light pulses. Applications: high-speed/long-haul backbones, undersea cables, FTTH. Offers enormous bandwidth, very low attenuation, and immunity to electromagnetic interference, but is costlier and harder to splice.

(a) CRC computation

Data word: 1101011011 Generator: 10011 (degree 4 → append 4 zero bits).

Dividend = 1101011011 0000. Perform modulo-2 (XOR) division by 10011:

1101011011 0000 ÷ 10011

Step-by-step XOR long division yields a 4-bit remainder:

$$\textbf{CRC remainder} = 1110$$

Transmitted frame = data + CRC:

$$\boxed{1101011011\,1110}$$

(Check: dividing 11010110111110 by 10011 gives remainder 0000, confirming the codeword.)

(b) Hamming distance for error detection/correction

The Hamming distance $d(x,y)$ between two code words is the number of bit positions in which they differ. The minimum Hamming distance $d_{min}$ of a code is the smallest distance over all pairs of valid code words. A received word is checked against valid code words; errors are detected if it is not a valid code word and corrected by mapping it to the nearest valid code word.

Capabilities (for $d_{min} = d$):

• Error detection: up to $d - 1$ bit errors.
• Error correction: up to $\left\lfloor \dfrac{d-1}{2} \right\rfloor$ bit errors.

For $d_{min} = 4$:

$$\text{Detect} = 4 - 1 = 3 \ \text{errors}, \qquad \text{Correct} = \left\lfloor \tfrac{4-1}{2} \right\rfloor = 1 \ \text{error}.$$

FDM vs TDM:

FDM diagram (described): the channel bandwidth is divided into parallel sub-bands stacked in frequency; each input signal modulates a different carrier and all travel simultaneously. Guard bands (unused frequency gaps) are placed between adjacent channels to prevent overlap/interference between signals whose spectra would otherwise spill into one another.

TDM diagram (described): inputs are interleaved in time — a multiplexer takes a slot (or byte) from input 1, then 2, then 3, …, repeating; each input owns the full bandwidth during its slot. Framing bits are extra bits added at the start of each frame (one bit per frame, following a known pattern) so the receiver can identify slot boundaries and stay synchronized, correctly assigning each slot to the right output channel.

Need for guard bands: to keep FDM channels from interfering. Role of framing bits: to maintain synchronization between multiplexer and demultiplexer in synchronous TDM.

Three switching techniques (block diagram concept: source — network of switches/nodes — destination):

Summary: Circuit switching guarantees QoS but wastes idle capacity. Datagram switching is flexible and robust (no setup) but offers no ordering/QoS guarantee. Virtual-circuit switching is a hybrid: one setup, then efficient packet forwarding along a fixed path with in-order delivery and small headers (VCI instead of full address).

Bit pattern: 0 1 0 1 1 1 0

Waveform conventions (described per bit; high = positive level, low = negative level):

NRZ-L (Non-Return-to-Zero Level): level = value. 0 → high, 1 → low (one common convention). For 0101110: H, L, H, L, L, L, H. The level holds for the whole bit; no transitions unless the value changes.

NRZ-I (NRZ-Invert): 1 = transition at the start of the bit, 0 = no transition. Starting low: bit0(0)=no change→low; bit1(1)=invert→high; bit2(0)=hold→high; bit3(1)=invert→low; bit4(1)=invert→high; bit5(1)=invert→low; bit6(0)=hold→low.

Manchester: each bit has a mid-bit transition; 0 = high→low transition, 1 = low→high transition (IEEE convention). So 0=↓, 1=↑, giving guaranteed transition in every bit period.

Differential Manchester: always a mid-bit transition (for clocking); the bit value is set by the presence/absence of a transition at the start of the bit — 0 = transition at start, 1 = no transition at start. For 0101110 the start-of-bit transitions occur for each 0, are absent for each 1, while every bit still has its mid-bit transition.

(A full pen-and-paper answer draws these four waveforms aligned under the bit pattern with the mid-bit and boundary transitions marked.)

Advantage of biphase (self-synchronizing) schemes: Manchester and Differential Manchester guarantee at least one transition per bit, so the receiver can recover the clock and stay synchronized even during long runs of identical bits — something NRZ schemes fail to do (a long string of 0s or 1s in NRZ gives no transitions and causes loss of synchronization / baseline wander).

Bit stuffing: a framing technique for bit-oriented protocols (e.g. HDLC) where the flag 01111110 marks frame boundaries. To prevent the data from accidentally containing the flag, the sender inserts (stuffs) a 0 after every five consecutive 1s in the data. The receiver removes any 0 that follows five 1s, recovering the original data.

Byte (character) stuffing: used in byte-oriented protocols where a special FLAG byte delimits frames and an ESC byte is defined. Whenever a FLAG or ESC byte appears inside the data, the sender prefixes it with an ESC byte; the receiver strips the ESC to recover the original byte. This keeps data bytes from being mistaken for control bytes.

Bit-stuffing the given data: Data = 01111110 01111100, i.e. 0111111001111100.

Scan for five consecutive 1s and insert a 0 after each such run:

• 01111 1... → after the first five 1s, stuff a 0: 011111 0 then continue 10...
• The original bits 0 1 1 1 1 1 1 0 become 0 1 1 1 1 1 0 1 0.
• Next group 0 1 1 1 1 1 0 0: after its five 1s stuff a 0 → 0 1 1 1 1 1 0 0 0.

Stuffed bit stream:

$$\texttt{0\,1\,1\,1\,1\,1\,0\,1\,0\,0\,1\,1\,1\,1\,1\,0\,0\,0}$$

i.e. 011111010 011111000 — the two inserted 0s (after each run of five 1s) ensure the flag pattern 01111110 never appears in the data field. Actual flags 01111110 are then added at the frame's start and end.

Definitions:

• Bandwidth: the capacity of a link — either the range of frequencies it passes (Hz) or, in computing, the maximum bits it can carry per second (bps).
• Throughput: the actual measured rate of successful data delivery over the link (bps); always ≤ bandwidth because of overhead, congestion, and errors.
• Latency (delay): the total time for a message to travel from source to destination = propagation + transmission + queuing + processing delay.
• Bandwidth-delay product (BDP): $\text{bandwidth} \times \text{delay}$ — the number of bits that can be "in flight" (filling the pipe) at one time.

Calculation: bandwidth = 1 Mbps = $10^6$ bps; round-trip delay (RTT) = 20 ms = $0.02$ s.

$$\text{BDP} = 1\times10^6 \ \text{bps} \times 0.02 \ \text{s} = 20{,}000 \ \text{bits} = 2500 \ \text{bytes} = 2.5 \ \text{KB}$$

Significance for window size: The BDP is the amount of data that can be unacknowledged "in the pipe" at once. To keep the link fully utilized, the sender window must be at least one BDP (here ≈ 20,000 bits). If the window is smaller, the sender stalls waiting for ACKs and bandwidth is wasted; sizing the window to the BDP lets the sender transmit continuously and achieve throughput close to the full bandwidth.