Section A — 1 Mark Questions
1. Define framing in the data link layer. [1 Mark]
Answer: Framing is the process of dividing a stream of bits into manageable units called frames to ensure data is transmitted correctly between nodes.
2. What is the primary purpose of error detection? [1 Mark]
Answer: It is used to identify whether any bits have been corrupted or changed during transmission from the sender to the receiver.
3. Name a simple method for error detection using parity bits. [1 Mark]
Answer: Parity check, specifically one-dimensional parity method.
4. What is bit stuffing? [1 Mark]
Answer: Bit stuffing is the insertion of an extra 0 in the data stream when a specific flag pattern is detected to prevent false frame boundaries.
5. What does CRC stand for? [1 Mark]
Answer: Cyclic Redundancy Check.
6. In one-dimensional parity, what does an even parity scheme ensure? [1 Mark]
Answer: It ensures that the total number of 1s in the data unit, including the parity bit, is an even number.
7. What is character stuffing? [1 Mark]
Answer: Character stuffing is the process of adding a special escape character before a flag byte if that byte appears within the data payload.
8. Can a simple parity check detect two-bit errors? [1 Mark]
Answer: No, simple parity check cannot detect an even number of bit errors.
9. What is the main disadvantage of one-dimensional parity? [1 Mark]
Answer: It cannot detect errors if the number of flipped bits is even.
10. How many redundant bits are used in Hamming code to correct a single-bit error for a 4-bit data word? [1 Mark]
Answer: 3 redundant bits.
11. What is the purpose of the frame delimiter or flag? [1 Mark]
12. Answer: It marks the beginning and the end of a frame to allow the receiver to identify where a frame starts and ends.
13. Which error detection method uses polynomial division? [1 Mark]
Answer: Cyclic Redundancy Check (CRC).
14. If the parity bit is set for odd parity, what is the count of 1s? [1 Mark]
Answer: The total number of 1s must be odd.
15. What is the size of a standard frame flag often used in HDLC? [1 Mark]
Answer: 8 bits (01111110).
16. Does Hamming code provide both detection and correction? [1 Mark]
Answer: Yes, it provides both error detection and single-bit error correction.
17. What is the main strength of two-dimensional parity over one-dimensional? [1 Mark]
Answer: It can detect multiple bit errors and identify the specific location of a single-bit error.
18. What happens if the CRC remainder is non-zero at the receiver? [1 Mark]
Answer: The receiver detects an error and discards or requests retransmission of the frame.
19. Define a data frame. [1 Mark]
Answer: A frame is a data-link layer transmission unit that consists of header, payload, and trailer information.
20. Why is bit stuffing necessary in bit-oriented framing? [1 Mark]
Answer: To prevent the data payload from containing the flag sequence, which would cause premature frame termination.
Section B — 2/3 Mark Questions
1. Explain the concept of one-dimensional parity check. [2 Marks]
Answer: In one-dimensional parity, an extra bit is added to each data block. If even parity is chosen, the bit is set to make the total number of 1s even. It is simple but only detects single-bit errors.
2. Compare character stuffing and bit stuffing. [3 Marks]
Answer: Character stuffing is used in byte-oriented framing, inserting an ESC character when the flag appears in data. Bit stuffing is used in bit-oriented framing, inserting a 0 after five consecutive 1s to ensure the flag sequence (01111110) does not occur in the payload.
3. Why is a two-dimensional parity check more reliable than one-dimensional? [2 Marks]
Answer: Two-dimensional parity organizes data in a grid and creates a parity bit for each row and column. This structure allows for the detection of many multiple-bit errors and enables the correction of single-bit errors.
4. What are the primary responsibilities of framing? [3 Marks]
Answer: Framing is responsible for dividing bit streams into frames, adding header information (like source/destination addresses), and adding trailer information for error detection to delineate the start and end of frames.
5. Describe the role of the Generator Polynomial in CRC. [2 Marks]
Answer: The generator polynomial acts as a divisor. Both the sender and receiver agree on this polynomial. The sender divides the message by it to find the remainder, which is then sent as the CRC checksum.
6. How does the Hamming code correct errors? [3 Marks]
Answer: Hamming code uses redundant bits placed at positions corresponding to powers of two. By calculating the parity of specific subsets of bits (syndrome calculation), the receiver can pinpoint the exact position of a corrupted bit and flip it back to its original state.
7. What is the main goal of using error detection methods? [2 Marks]
Answer: The goal is to ensure data integrity. It allows the receiver to determine if a received frame is error-free, preventing the processing of corrupted data in higher network layers.
8. Describe the structure of a generic frame. [3 Marks]
Answer: A frame typically consists of a Header (containing source and destination addresses), a Data field (the actual payload), and a Trailer (containing error detection bits like a CRC checksum).
9. How is the CRC remainder calculated at the sender side? [2 Marks]
Answer: The sender appends n-1 zeros to the message (where n is the number of bits in the divisor). This augmented message is divided by the generator polynomial using modulo-2 division, and the resulting remainder is the CRC.
10. Explain why we need to detect errors in the data link layer. [3 Marks]
Answer: Physical layer transmissions are susceptible to interference, noise, and signal degradation, causing bit flips. The data link layer must detect these errors to either request retransmission or discard invalid data, ensuring reliable hop-to-hop delivery.
Section C — 5 Mark Questions
1. Explain the process of Cyclic Redundancy Check (CRC) in detail. [5 Marks]
Answer:
Introduction
CRC is a powerful error-detection method based on binary division. It treats bit strings as representations of polynomials.
Process Steps
- Agreement: The sender and receiver agree on a fixed generator polynomial of degree n.
- Appending Zeros: The sender appends n zeros to the data payload.
- Modulo-2 Division: The sender performs binary division of the augmented payload by the generator polynomial. The remainder is the CRC checksum.
- Transmission: The sender replaces the appended zeros with the CRC remainder and sends the frame.
- Verification: The receiver divides the entire received frame by the same generator polynomial. If the remainder is zero, the frame is assumed correct; otherwise, it is corrupted.
CRC is highly effective at detecting burst errors, making it superior to simple parity checks for most data communication applications.
2. Discuss framing and the mechanisms used to ensure clear separation of frames. [5 Marks]
Answer:
Introduction
Framing is the physical grouping of bits into a format for transmission. Without proper framing, a receiver cannot identify where one frame ends and the next begins.
Mechanisms
- Character Stuffing: Used in byte-oriented protocols. When a flag byte (like DLE STX) appears in the data, the sender inserts an extra 'escape' (ESC) byte before it. The receiver removes the ESC and treats the next byte as data.
- Bit Stuffing: Used in bit-oriented protocols like HDLC. If the sender finds five consecutive 1s in the data, it automatically inserts a 0 bit. This ensures the reserved flag sequence '01111110' never occurs naturally in the data payload.
These techniques allow for reliable synchronization between sender and receiver by clearly delineating the boundaries of each frame, even if the user data contains patterns similar to frame delimiters.
3. Elaborate on the two-dimensional parity method for error detection and correction. [5 Marks]
Answer:
Explanation
Two-dimensional parity improves upon the one-dimensional method by arranging data bits into a table format consisting of rows and columns. This adds a redundant parity bit for every row and every column.
Working Mechanism
- Row Parity: Each row is checked for parity to create a parity bit.
- Column Parity: Each column is checked for parity to create a column parity word.
- Error Detection: If a bit flips, both the specific row and specific column parity will fail to match.
- Error Correction: The intersection of the failed row and the failed column precisely identifies the location of the flipped bit. The receiver simply flips that bit back to its correct state.
This method can detect multiple errors in a frame and is uniquely capable of performing single-bit error correction, which simple parity methods cannot do. However, it requires higher overhead compared to simple one-dimensional parity.
4. Compare one-dimensional and two-dimensional parity methods. [5 Marks]
Answer:
| Feature | One-Dimensional Parity | Two-Dimensional Parity |
|---|---|---|
| Structure | Single bit added to data | Grid-based row/column parity |
| Overhead | Low (1 bit per block) | Higher (requires row/col bits) |
| Detection | Detects odd number of errors | Detects most multiple-bit errors |
| Correction | Cannot correct errors | Can correct single-bit errors |
| Complexity | Very low | Moderate |
Conclusion
While one-dimensional parity provides a basic and efficient way to detect simple errors, it is insufficient for applications requiring high reliability. Two-dimensional parity, despite its increased bit overhead, provides essential error-correction capabilities that make it more suitable for communication links with higher noise levels.
5. Describe the role of Hamming code in error correction. [5 Marks]
Answer:
Introduction
Hamming code is a block code that is capable of detecting and correcting single-bit errors. It uses redundant bits inserted at specific positions within the data.
Mechanism
- Placement of Parity Bits: Redundant bits (p1, p2, p4, etc.) are placed at positions corresponding to powers of 2 (1, 2, 4, 8...).
- Parity Calculation: Each parity bit covers specific data bit positions. For instance, p1 covers positions 1, 3, 5, 7, and so on.
- Syndrome Calculation: At the receiver, the parity check is repeated. If an error occurred, the results of the parity checks form a 'syndrome' that equals the position of the incorrect bit.
- Correction: If the syndrome is non-zero, the receiver identifies the specific bit at that numerical position and flips it, effectively correcting the single-bit error.
Hamming code is efficient because it requires relatively few redundant bits to correct a single-bit error, making it a standard technique for memory systems and short-distance data links.