MODULE 2 Flashcards
(16 cards)
block coding? Explain the process of error detection in block coding.
Block coding is a method used in error detection and correction, where data is divided into fixed-size blocks. Each block consists of k bits, called datawords. To ensure that the data is transmitted correctly, extra redundant bits (referred to as r bits) are added to the data. This process results in a codeword of n bits, where
𝑛
=
𝑘
+
𝑟
n=k+r.
Key Concepts:
Dataword: The original set of data bits, typically consisting of k bits.
Codeword: The result of combining the dataword with the additional r redundant bits, making the total size n bits.
This coding process allows for detecting or correcting errors that occur during transmission. Block coding schemes typically ensure that 2^k datawords are mapped to a larger set of 2^n codewords. Some of these codewords are valid and others are invalid, helping in detecting errors.
Process of Error Detection in Block Coding:
Error detection with block coding involves the following steps:
Encoding:
The sender takes the k-bit dataword and adds r redundant bits, creating a n-bit codeword.
This mapping is done such that only a subset of 2^n codewords are valid, while the others are invalid.
Transmission:
The encoded codeword is sent through a noisy channel, which could introduce errors.
Reception and Detection:
The receiver receives an n-bit word, which may or may not match the sent codeword.
The receiver checks whether the received word is a valid codeword by comparing it to the list of known valid codewords.
If the received codeword matches a valid codeword, the data is accepted.
If the received codeword does not match any valid codeword, it indicates that an error occurred, and the codeword is rejected.
Example (from the text):
In the example where k = 2 and n = 3, we have the following mapping:
Dataword Codeword
00 000
01 011
10 101
11 110
Suppose the dataword “01” is encoded as the codeword “011” and transmitted.
The receiver may receive either “011” (valid) or an erroneous codeword like “111”.
“011” is valid, so the dataword “01” is extracted.
“111” is invalid, so the error is detected and the codeword is discarded.
Block coding ensures that when an invalid codeword is received, the error is detected, but there may be cases where certain types of errors (like multiple bit errors) could go undetected if the corrupted codeword matches another valid codeword.
Hamming Distance:
The Hamming distance between two codewords is the number of bit positions in which they differ. The minimum Hamming distance in block coding determines the error detection and correction capability. For example, if the minimum Hamming distance between all codewords is dmin, the system can detect up to dmin - 1 errors.
cyclic redundancy check shows an example of a CRC code
Cyclic Redundancy Check (CRC)
Cyclic Redundancy Check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data. CRC is based on cyclic codes, a type of linear block code that has a property where if a codeword is cyclically shifted, the result is another codeword.
In CRC, both the sender and receiver agree on a generator polynomial, which is used to compute a remainder when the data is divided by this polynomial. The remainder (or checksum) is appended to the original data to form the transmitted codeword. Upon reception, the receiver checks the integrity of the data by performing the same division. If the remainder matches the expected value, the data is considered intact.
CRC Process:
Dataword: The original data that needs to be transmitted.
Augmentation: The dataword is augmented by appending n - k zeros (where
𝑛
n is the length of the codeword, and
𝑘
k is the length of the dataword).
Division: The augmented dataword is divided by a predefined generator polynomial using modulo-2 division. This division process is similar to long division, but instead of normal arithmetic, XOR is used for subtraction.
Remainder: The remainder from the division (called the CRC checksum) is appended to the dataword to form the final codeword.
Transmission: The codeword (which includes the original data and the CRC checksum) is transmitted.
Error Checking: The receiver receives the codeword and performs the same division by the generator polynomial. If the remainder is zero, the data is considered valid; otherwise, an error is detected.
Example of CRC Code:
Let’s walk through an example where:
The dataword is: 1001 (4 bits)
The generator polynomial is:
𝐺
(
𝑥
)
=
𝑥
3
+
𝑥
+
1
G(x)=x
3
+x+1, which corresponds to the binary value 1011.
EX CRC
Step-by-Step CRC Example:
Dataword: 1001
Augment the Dataword:
Append n - k zeros to the dataword. In this case, the generator polynomial has a degree of 3, so we append 3 zeros to the dataword:
Augmented Dataword: 1001000
Division:
Divide the augmented dataword by the generator polynomial using XOR for division (modulo-2 arithmetic).
The generator polynomial is 1011, and we perform binary division.Append the Remainder (Checksum):
The original dataword is 1001, and the CRC checksum is 100. The final codeword is the dataword with the remainder appended:
Final Codeword: 1001100
Transmission:
The codeword 1001100 is sent to the receiver.
Error Detection at Receiver:
The receiver performs the same division on the received codeword 1001100 by the generator polynomial 1011. If the remainder is zero, the data is considered valid.
CRC Properties:
Cyclic Property: A cyclic shift of a valid codeword results in another valid codeword.
Detection of Errors: CRC can detect:
All single-bit errors.
Double-bit errors.
Odd numbers of errors.
Burst errors (up to the length of the generator polynomial).
Benefits of CRC:
It can detect a wide range of common errors in transmission.
It is simple to implement in both hardware and software, making it efficient for real-time systems.
type of errors?
rrors in digital communication occur when bits are altered during transmission. The main types of errors are:
Single-bit Error:
Definition: Only one bit in the data unit is altered (i.e., a 0 becomes a 1 or vice versa).
Example: Sent data: 10001001, Received data: 10000001 (The second bit from the right has changed).
Burst Error:
Definition: Two or more bits in a sequence are altered. A burst error affects a sequence of bits but not necessarily contiguous ones.
Example: Sent data: 10001001, Received data: 11101001 (A burst error affected four bits starting from the left).
Cause: Burst errors are more likely to occur due to longer interference, as noise or signal disruptions typically last longer than a single bit duration.
Simple Parity-Check Code
Simple Parity-Check Code
The Simple Parity-Check Code is an error-detection code that adds an extra parity bit to the dataword. This bit is set in such a way that the total number of 1’s in the codeword (including the parity bit) is even (for even parity) or odd (for odd parity).
Parity Bit: A single bit added to the dataword to ensure that the total number of 1s in the dataword (including the parity bit) is even (even parity) or odd (odd parity).
Steps for Simple Parity Check:
Encoding:
The sender computes the parity bit and appends it to the dataword to create a codeword.
The parity bit is calculated to make the total number of 1’s in the codeword even (for even parity).
Transmission:
The sender transmits the codeword (dataword + parity bit).
Decoding and Error Detection:
The receiver checks the number of 1’s in the received codeword.
If the number of 1’s is even (for even parity), the codeword is accepted. If the number of 1’s is odd, it indicates that an error has occurred during transmission.
Example of Simple Parity-Check Code:
1. Encoder Process:
Dataword: 1010 (4 bits)
Even Parity: The total number of 1’s in 1010 is 2 (even). Therefore, the parity bit will be 0.
Codeword: The parity bit is appended to the dataword, resulting in 10100.
2. Transmission:
The codeword 10100 is sent over the network.
3. Decoder Process:
Received Codeword: Suppose the receiver gets 10100.
Check for Even Parity:
The total number of 1’s is 2 (even), so the receiver accepts the data as valid.
However, if a single-bit error occurred, such as receiving 11100, the decoder would find that the number of 1’s is 3 (odd), and an error would be detected.
Error Detection with Parity Check:
The simple parity-check code can only detect errors where an odd number of bits are corrupted (e.g., 1, 3, 5 bits, etc.). It cannot detect errors if an even number of bits are altered, as the parity would still appear correct.
Example 1: No Error Detected
Sent Codeword: 10100
Received Codeword: 10100 (no error)
Check: Number of 1’s = 2 (even parity holds).
Example 2: Single-bit Error Detected
Sent Codeword: 10100
Received Codeword: 11100 (error in second bit)
Check: Number of 1’s = 3 (odd parity, error detected).
Example 3: Undetectable Error (Even number of errors)
Sent Codeword: 10100
Received Codeword: 11101 (error in second and last bits)
Check: Number of 1’s = 2 (even parity holds, no error detected, but data is corrupted).
Conclusion:
Simple parity-check is useful for detecting single-bit errors but cannot detect errors when an even number of bits are altered.
It is a simple and efficient method for error detection in systems where single-bit errors are more likely.
Framing in Data Communication
Framing refers to the method of packaging data for transmission over a network. It is the process of dividing data into manageable units, called frames, for reliable and efficient communication between two devices on a network. A frame typically consists of:
A header: Contains control information such as the sender’s and receiver’s addresses.
The data or payload: The actual message or data to be transmitted.
A trailer: Contains error-detection codes or other information to help the receiver verify data integrity.
Purpose of Framing:
Synchronization: To distinguish where one frame ends and another begins.
Error Detection: To help detect errors in data transmission.
Flow Control: To manage the flow of data between sender and receiver to prevent overwhelming the receiver.
TYPE FARM
Types of Framing:
There are two primary types of framing:
Fixed-size Framing
Variable-size Framing
1. Fixed-size Framing:
In fixed-size framing, all frames are of a constant, predetermined size, and thus, there is no need for any extra data to mark the boundaries between frames.
Example:
The ATM (Asynchronous Transfer Mode) protocol uses fixed-size cells of 53 bytes, where 48 bytes are allocated for the payload (data) and 5 bytes for the header.
Because the frame size is known and fixed, the receiver doesn’t require any special indicators to detect the beginning or end of a frame. It simply reads the data in blocks of 53 bytes.
Advantages:
No Need for Boundary Markers: Since the size is fixed, boundary markers like flags or length fields are unnecessary.
Efficient Processing: The predictable size allows for simpler and faster processing.
Disadvantages:
Wasted Space: If the data to be transmitted is smaller than the frame size, the remaining space in the frame is wasted, reducing efficiency.
2. Variable-size Framing:
In variable-size framing, frames can have different lengths. To distinguish between frames, special indicators are required to mark the boundaries between frames.
There are two main approaches to variable-size framing:
Character-oriented framing (Byte-oriented framing)
Bit-oriented framing
EX FARM
Examples of Framing in Network Protocols:
Ethernet (Variable-size framing):
Ethernet uses a variable-size framing scheme. An Ethernet frame can vary between 64 bytes and 1518 bytes in length.
Each frame contains a header, payload, and trailer (CRC for error detection).
ATM (Fixed-size framing):
Asynchronous Transfer Mode (ATM) frames are fixed at 53 bytes, consisting of a 5-byte header and 48-byte payload.
Conclusion:
Framing is crucial for reliable communication, ensuring that data is sent and received correctly.
Fixed-size framing is simpler but can be less efficient due to wasted space. Variable-size framing, while more complex, is more adaptable to different data sizes.
Protocols like HDLC, PPP, and Ethernet use variable-size framing with methods like bit or byte stuffing to manage frame boundaries and ensure data integrity.
Flow and Error Control in Data Link Layer
In the Data Link Layer, flow control and error control mechanisms ensure reliable transmission of data between two adjacent nodes in a network.
Flow Control:
Flow control is a technique used to prevent the sender from overwhelming the receiver with too much data at once. It ensures that the sender transmits data at a rate that the receiver can handle, avoiding buffer overflow at the receiver’s end.
Two common flow control methods are:
Stop-and-Wait Flow Control:
Process: The sender transmits a frame and waits for an acknowledgment from the receiver before sending the next frame.
Advantages: Simple to implement and prevents the receiver from being overwhelmed.
Disadvantages: Inefficient for long-distance communication because the sender must wait for an acknowledgment for each frame, leading to idle time.
Sliding Window Flow Control:
Process: The sender can transmit multiple frames (up to a window size) before waiting for an acknowledgment. Each frame has a sequence number, and the receiver acknowledges the frames as they are received.
Advantages: More efficient than Stop-and-Wait as it allows the sender to transmit multiple frames before waiting for acknowledgment, maximizing throughput.
Disadvantages: More complex to implement but well-suited for high-speed, long-distance networks.
Error Control:
Error control is the mechanism used to detect and correct errors in transmitted data. In the data link layer, error control ensures that frames are delivered to the receiver without errors and in the correct sequence.
There are two types of errors:
Single-bit errors: Only one bit in the data is altered during transmission.
Burst errors: A group of consecutive bits are altered.
Common error control techniques include:
Error Detection:
The goal of error detection is to identify whether errors have occurred during transmission. Some common methods include:
Parity Check: A single parity bit is added to the data to make the number of 1s either even (even parity) or odd (odd parity). It detects single-bit errors.
Cyclic Redundancy Check (CRC): A more powerful error-detection method, where a polynomial code is used to detect burst errors.
Checksum: A checksum is calculated by summing the data segments and sending the sum with the data. The receiver recalculates the checksum to verify the integrity of the received data.
Error Correction:
Once an error is detected, it can be corrected using techniques like:
Automatic Repeat reQuest (ARQ): This is a feedback-based system where the receiver detects errors and requests the sender to retransmit the erroneous data.
Stop-and-Wait ARQ: The sender waits for an acknowledgment after each frame and retransmits if an error is detected.
Go-Back-N ARQ: The sender sends multiple frames and retransmits all frames from the erroneous one onward if an error is detected.
Selective Repeat ARQ: Only the erroneous frames are retransmitted, making it more efficient than Go-Back-N.
Forward Error Correction (FEC): Instead of retransmitting the data, FEC corrects errors by including enough redundant bits in the data, allowing the receiver to detect and correct the errors without retransmission.
Stop-and-Wait Protocol
The Stop-and-Wait Protocol is a simple flow control method used in data communication. In this protocol, the sender sends one data frame at a time and waits for an acknowledgment (ACK) from the receiver before sending the next frame. If the acknowledgment is not received within a specific time (due to a lost frame or acknowledgment), the sender retransmits the same frame. This ensures reliable data transfer but can lead to inefficiency, especially over long distances, due to the idle waiting time.
Key Features:
Frame Transmission: The sender sends one frame and waits for an acknowledgment.
Acknowledgment: The receiver sends an acknowledgment after successfully receiving a frame.
Timeout: If the sender does not receive an acknowledgment within a certain period, it assumes the frame is lost and retransmits it.
Error Detection: Errors in transmission are handled through retransmissions triggered by the timeout mechanism.
Steps in Stop-and-Wait Protocol:
Sender Side:
The sender transmits a frame and starts a timer.
It waits for an acknowledgment (ACK) from the receiver.
If the ACK is received within the timeout period, the sender sends the next frame.
If no ACK is received within the timeout period, the sender retransmits the previous frame.
Receiver Side:
The receiver receives the frame.
If the frame is error-free (validated by error detection mechanisms like CRC), the receiver sends an ACK to the sender.
If the frame is corrupted or a duplicate, the receiver discards the frame and does not send an acknowledgment. Example:
Suppose the sender is transmitting data frames, and each data frame must be acknowledged by the receiver.
Sender sends Frame 1 → Waits for ACK1.
Upon receiving ACK1 → Sends Frame 2.
If no ACK1 is received within the timeout, Frame 1 is retransmitted.
This process repeats for each frame, ensuring that every frame is delivered and acknowledged before proceeding to the next one.
Finite State Machine (FSM) for Stop-and-Wait Protocol
Finite State Machine (FSM) for Stop-and-Wait Protocol
The FSM for the Stop-and-Wait protocol represents the states and transitions for both the sender and the receiver during the communication process.
- FSM for the Sender:
States:
Idle State: The sender is ready to send the next frame.
Waiting for ACK: The sender is waiting for an acknowledgment for the sent frame.
Transitions:
From Idle State to Waiting for ACK:
When the sender sends a frame, it transitions to the “Waiting for ACK” state and starts the timer.
From Waiting for ACK to Idle State:
If an acknowledgment is received before the timer expires, the sender moves back to the “Idle State” to send the next frame.
From Waiting for ACK to Waiting for ACK (Retransmission):
If the timer expires before receiving an acknowledgment, the sender retransmits the frame and remains in the “Waiting for ACK” state. Idle: The sender sends a frame and moves to the “Waiting for ACK” state.
Waiting for ACK: If the ACK is received, it transitions back to “Idle” to send the next frame. If a timeout occurs, it resends the frame and remains in “Waiting for ACK”.
2. FSM for the Receiver:
States:
Waiting for Frame: The receiver is waiting for a new frame from the sender.
Transitions:
From Waiting for Frame to Waiting for Frame:
When a frame is received:
If the frame is error-free and new (not a duplicate), the receiver sends an acknowledgment and remains in the same state, waiting for the next frame.
If the frame is corrupted or a duplicate, the receiver discards the frame and stays in the same state, waiting for the next correct frame.Waiting for Frame: The receiver waits for a frame. If the frame is correct, it sends an acknowledgment and waits for the next frame. If there is an error or duplicate, it discards the frame and continues waiting for the correct frame.
Explanation of FSM:
Sender:
The sender starts in the Idle state. It sends a frame, transitions to the Waiting for ACK state, and starts the timer.
If it receives an acknowledgment (ACK) within the timer period, it transitions back to the Idle state to send the next frame.
If no acknowledgment is received and the timer expires, the sender retransmits the frame and stays in the Waiting for ACK state until the ACK is received.
Receiver:
The receiver starts in the Waiting for Frame state. When a frame is received:
If the frame is correct (i.e., no errors and not a duplicate), the receiver sends an ACK and remains in the same state, waiting for the next frame.
If the frame is corrupted or a duplicate, it discards the frame and continues waiting for the correct frame.
Advantages and Disadvantages of Stop-and-Wait Protocol
Advantages:
Simplicity: Easy to implement due to its straightforward logic.
Reliable Delivery: Ensures that data frames are received correctly before the next one is sent.
Disadvantages:
Inefficiency: Due to waiting for an acknowledgment after each frame, the protocol wastes time, especially for long-distance communications, where propagation delays are high.
Low Throughput: The protocol can lead to underutilization of the communication channel because only one frame is sent at a time.
Checksum: Definition and Overview
A checksum is an error-detection technique used to ensure the integrity of data during transmission over a network or in data storage. The checksum process involves calculating a value based on the sum of the data being transmitted and appending it to the message. At the receiver’s end, the checksum is recalculated and compared to the transmitted checksum. If the two match, the data is considered valid; otherwise, an error is detected.
How Checksum Works:
Sender: The sender divides the message into fixed-size units (e.g., 16-bit words) and adds them up using a specific algorithm. The result (the checksum) is then appended to the message.
Receiver: The receiver calculates the checksum by summing the same fixed-size units of the received message (including the transmitted checksum). If the result is zero (or a predefined value such as all bits set to zero), the data is assumed to be intact.
Traditional Checksum Calculation Algorithm:
The traditional checksum process typically uses one’s complement arithmetic to add the data units. The following steps outline the traditional checksum calculation method.
