📡 Data Link Layer Study Guide

ECE 422 - Data Communication & Computer Networks - Department of Electrical & Communication Engineering

OSI Model Layer 2 | Error Control | Flow Control | Framing

⚙️ (a) Functions of Data Link Layer

Introduction

The Data Link Layer (DLL) is the second layer of the OSI model, responsible for node-to-node data transfer. It takes packets from the Network Layer and encapsulates them into frames for transmission over the physical link.

OSI Model Context
Application
Layer 7
Presentation
Layer 6
Session
Layer 5
Transport
Layer 4
Network
Layer 3
Data Link
Layer 2
Physical
Layer 1

Primary Functions

1. Framing

Divides the stream of bits from the network layer into manageable data units called frames. Each frame contains a header, payload, and trailer.

| Header | Data (Payload) | Trailer | | Flag | IP Packet | FCS | | (8 bits)| (Variable) | (16 bits)|

2. Physical Addressing (MAC Addressing)

Adds physical addresses (MAC addresses) to the frame header to identify sender and receiver on the local network. MAC addresses are 48-bit hardware addresses burned into NICs.

Frame Header = Destination MAC (6 bytes) + Source MAC (6 bytes) + Type/Length (2 bytes)

3. Error Control

Detects and sometimes corrects errors that occur during transmission. Uses techniques like CRC (Cyclic Redundancy Check), Checksum, and ARQ (Automatic Repeat Request).

4. Flow Control

Regulates data transmission rate between sender and receiver to prevent buffer overflow. Techniques include Stop-and-Wait and Sliding Window protocols.

5. Access Control

Determines which device has control over the link at any given time when multiple devices share the same link (Multi-access protocols).

6. Synchronization

Ensures sender and receiver are synchronized regarding bit timing and frame boundaries.

Sublayers of Data Link Layer

LLC and MAC Sublayers
LLC (Logical Link Control)
• Handles error control & flow control
• Provides interface to Network Layer
• Supports multiple network protocols
MAC (Media Access Control)
• Controls physical media access
• MAC addressing & framing
• CSMA/CD, Token Passing protocols
Key Point: The Data Link Layer provides hop-to-hop (node-to-node) delivery, while the Network Layer provides end-to-end delivery.
⚠️ (b) Types of Errors

Understanding Transmission Errors

Errors occur when bits are corrupted during transmission due to noise, interference, or attenuation. Understanding error types is crucial for designing appropriate detection and correction mechanisms.

Classification of Errors

🔴 Single-Bit Error

Only one bit in the data unit (frame) is changed from 0 to 1 or from 1 to 0.

Original:
1
0
1
1
0
1

Received:
1
0
1
0
0
1

Least likely type in serial data transmission

🟡 Burst Error

Two or more bits in the data unit are changed. Burst errors are more common and measured from first to last error bit.

Original:
1
0
1
1
0
0
1

Received:
1
0
0
0
1
0
1

Most common in wireless and noisy channels

🔵 Random Errors

Errors occur randomly and independently across the data stream, often modeled using Binary Symmetric Channel (BSC) where:

P(0→1) = P(1→0) = p (crossover probability)

Common in satellite and deep space communications

Causes of Errors

Source Description Impact
Thermal Noise Random electron motion in conductors (White Gaussian Noise) Low SNR, random bit errors
Interference EMI from nearby equipment, crosstalk between cables Burst errors
Attenuation Signal strength loss over distance Detection errors
Multipath Fading Signal reflections in wireless channels Intersymbol interference
Jitter Timing variations in signal transitions Synchronization errors

Error Metrics

Bit Error Rate (BER)

BER = (Number of bit errors) / (Total number of bits transmitted)

Typical values: Wired: 10⁻⁹ to 10⁻¹², Wireless: 10⁻³ to 10⁻⁶

Packet Error Rate (PER)

PER = Number of Incorrect Packets/Number of Packets Received
🔍 (c) Introduction to Error Detection and Correction

Error Control Mechanisms

Error control techniques ensure reliable data transmission by detecting corrupted bits and either correcting them or requesting retransmission.

Fundamental Concepts

Error Control Taxonomy
Error Control
├── Forward Error Correction (FEC)
│ └── Receiver corrects errors without retransmission
│ └── Used in: Satellite, Deep space, Real-time video
│
└── Automatic Repeat Request (ARQ)
└── Receiver detects errors and requests retransmission
└── Used in: Wired networks, File transfers

Redundancy and Coding

All error control schemes add redundant bits to the original data. The ratio of data bits to total bits is called Code Rate:

Code Rate (R) = k / n
where k = message bits, n = codeword bits (n > k)

Error Detection Techniques

1. Parity Check

Simplest form of error detection. Adds one parity bit to make total number of 1s either even (even parity) or odd (odd parity).

Interactive Parity Check

Limitation: Can detect only odd number of bit errors. Cannot correct errors.

2. Checksum

Used in Internet protocols (IP, TCP, UDP). Data is divided into segments, summed using 1's complement arithmetic, and complement of sum is appended.

Checksum = ~(Sum of all 16-bit words) [1's complement]

3. Cyclic Redundancy Check (CRC)

Most powerful error detection method. Treats data as polynomial and performs binary division using a generator polynomial G(x).

Algorithm: 1. Append (n-k) zeros to data (n=degree of G(x)) 2. Divide by G(x) using modulo-2 arithmetic 3. Remainder = CRC (n-k bits) 4. Transmit: Data + CRC

Common CRC Standards:

  • CRC-8: G(x) = x⁸ + x² + x + 1 (Bluetooth)
  • CRC-16: G(x) = x¹⁶ + x¹⁵ + x² + 1 (HDLC)
  • CRC-32: G(x) = x³² + x²⁶ + x²³ + ... + x² + x + 1 (Ethernet)

Error Correction Techniques

Hamming Distance

The number of bit positions in which two codewords differ. Minimum Hamming distance (dmin) determines error capability:

To detect s errors: dmin ≥ s + 1
To correct t errors: dmin ≥ 2t + 1
To correct t and detect s (s>t): dmin ≥ t + s + 1

Hamming Codes

Perfect single-error correcting codes that can detect double errors. Places parity bits at positions that are powers of 2 (1, 2, 4, 8...).

For m data bits, r parity bits needed where: 2ʳ ≥ m + r + 1

Hamming Code Position Calculator

Method Redundancy Detect Correct Application
Single Parity 1 bit Odd errors No Simple serial comm
2D Parity n+m+1 bits Up to 3 errors 1 error Early computer memory
Checksum 16/32 bits Random errors No TCP/IP, Internet
CRC 8-32 bits Burst errors No Ethernet, WiFi, Storage
Hamming log₂(m)+1 2 errors 1 error ECC Memory
🧱 (d) Block Coding

Block Coding Fundamentals

Block Coding is a coding technique where a block of k message bits is mapped to a block of n code bits (n > k), adding (n-k) redundant bits for error control.

Block Coding Process
Message
k bits
→
Encoder
Adds r=(n-k) bits
→
Codeword
n bits

Key Parameters

Code Rate: R = k/n (Efficiency measure)
Hamming Weight: Number of 1s in a codeword
Hamming Distance: Number of positions where two codewords differ
Minimum Distance (dmin): Smallest distance between any two codewords

Types of Block Codes

1. Linear Block Codes

A code is linear if the modulo-2 sum of any two valid codewords produces another valid codeword. All-zero codeword must be valid.

Generator Matrix (G)

Used to generate codewords from message bits: C = D × G

Where D is message vector, C is codeword vector (modulo-2 arithmetic)

Example: (7,4) Hamming Code G = [I₄ | P] = [1 0 0 0 | 1 1 0] [0 1 0 0 | 1 0 1] [0 0 1 0 | 0 1 1] [0 0 0 1 | 1 1 1]

Parity-Check Matrix (H)

Used for error detection: H × Cᵀ = 0 (if no errors)

Syndrome S = H × Rᵀ (R = received vector). Non-zero syndrome indicates errors.

2. Cyclic Codes

Special class of linear block codes where any cyclic shift of a codeword produces another valid codeword. Implemented efficiently using shift registers.

Property: If C = (c₀, c₁, ..., cₙ₋₁) is a codeword, then (cₙ₋₁, c₀, c₁, ..., cₙ₋₂) is also a codeword.

3. Important Block Codes

Code Parameters dmin Capability Application
Hamming (2ʳ-1, 2ʳ-1-r) 3 SEC DRAM ECC
Reed-Muller (2ᵐ, ΣC(m,i)) 2ᵐ⁻ʳ MED Space comm
Reed-Solomon (n, k) over GF(2ᵐ) n-k+1 t=(n-k)/2 CD/DVD, QR codes
BCH (2ᵐ-1, k) 2t+1 t-error SSD, Satellite
LDPC (n, k) sparse Variable Near Shannon 5G, WiFi 6

Decoding Methods

Maximum Likelihood Decoding (MLD)

Selects the codeword that is closest (minimum Hamming distance) to the received vector. Optimal but computationally complex for large codes.

Syndrome Decoding

Uses parity-check matrix to compute syndrome. Lookup table maps syndrome to error pattern. More efficient than MLD for linear codes.

Syndrome S = H × Rᵀ = H × Eᵀ (where E is error pattern)
If S = 0: No error detected
If S ≠ 0: Error detected, correct if possible

Interactive Block Code Example

(7,4) Hamming Code Encoder

Parity Bit Calculation:
p1 = d1 ⊕ d2 ⊕ d4 (covers positions 1,3,5,7)
p2 = d1 ⊕ d3 ⊕ d4 (covers positions 2,3,6,7)
p3 = d2 ⊕ d3 ⊕ d4 (covers positions 4,5,6,7)

Summary: Block Coding Advantages

  • Fixed processing delay (block size independent of data stream)
  • Easy synchronization (frame boundaries known)
  • Efficient hardware implementation using shift registers
  • Strong mathematical structure enables efficient decoding
  • Widely used in storage (SSD, HDD) and wireless systems
📚 Study Summary

Key Takeaways

Data Link Layer Functions

  • Framing & Synchronization
  • Physical Addressing (MAC)
  • Error Control (Detection/Correction)
  • Flow Control
  • Access Control

Error Types

  • Single-bit errors (rare)
  • Burst errors (common)
  • Random errors (BSC model)
  • BER and PER metrics

Error Control

  • Detection: Parity, Checksum, CRC
  • Correction: Hamming, Block codes
  • ARQ vs FEC strategies
  • Hamming distance concepts

Block Coding

  • Linear block codes (G and H matrices)
  • Cyclic codes (shift register impl.)
  • Hamming, BCH, Reed-Solomon
  • Syndrome decoding
Exam Tip: Focus on understanding the relationship between minimum Hamming distance (dmin) and error control capabilities. Be prepared to calculate parity bits, encode messages using generator matrices, and analyze simple block codes.