Parity Check
The parity check is done by adding an extra bit, called parity bit to the data to make a number of 1s either even in case of even parity or odd in case of odd parity.While creating a frame, the sender counts the number of 1s in it and adds the parity bit in the following way
In case of even parity: If a number of 1s is even then parity bit value is 0. If the number of 1s is odd then parity bit value is 1.
In case of odd parity: If a number of 1s is odd then parity bit value is 0. If a number of 1s is even then parity bit value is 1.
On receiving a frame, the receiver counts the number of 1s in it. In case of even parity check, if the count of 1s is even, the frame is accepted, otherwise, it is rejected. A similar rule is adopted for odd parity check.
The parity check is suitable for single bit error detection only.
Cyclic Redundancy Check (CRC)
Cyclic Redundancy Check (CRC) involves binary division of the data bits being sent by a predetermined divisor agreed upon by the communicating system. The divisor is generated using polynomials.
Here, the sender performs binary division of the data segment by the divisor. It then appends the remainder called CRC bits to the end of the data segment. This makes the resulting data unit exactly divisible by the divisor.
The receiver divides the incoming data unit by the divisor. If there is no remainder, the data unit is assumed to be correct and is accepted. Otherwise, it is understood that the data is corrupted and is therefore rejected.
Transmitted Data:
2.Example - The data bit to be sent is [100100], and the polynomial equation is [x3+x2+1].
Divisor (k) - 1101 (Using the given polynomial)
Appending Zeros - (k-1) > (4-1) > 3
Dividend - 100100000
Error Correction Techniques
Error correction techniques find out the exact number of bits that have been corrupted and as well as their locations. There are two principle ways
Forward Error Correction − If the receiver detects some error in the incoming frame, it executes error-correcting code that generates the actual frame. This saves bandwidth required for retransmission. It is inevitable in real-time systems. However, if there are too many errors, the frames need to be retransmitted.
The four main error correction codes are
Hamming Codes
Binary Convolution Code
Reed – Solomon Code
Low-Density Parity-Check Code
Hamming Codes: In Computer Networks, Hamming code is used for the set of error-correction codes which may occur when the data is moved from the sender to the receiver.
The hamming method corrects the error by finding the state at which the error has occurred.
Redundant bits are extra binary bits that are generated and added to the information-carrying bits of data transfer to ensure that no bits were lost during the data transfer. The redundancy bits are placed at certain calculated positions to eliminate the errors and the distance between the two redundancy bits is called "Hamming Distance".
The following formula is used to find the number of redundant bits.
Number of single-bit errors = M + R
Number of states for no error = 1
So, the number of redundant bits (R) that represent all states (M+R+1) must satisfy −
2^𝑅 ≥ 𝑀 + 𝑅 + 1
where R = Redundant bit, and M = data bit.
The hamming method uses the extra parity bits to allow the identification of a single-bit error.
Step 1 − First write the bit positions starting from 1 in a binary form (1, 10, 11,100, etc.)
Step 2 − Mark all the bit positions that are powers of two as parity bits (1, 2, 4, 8, 16, 32, 64, etc.)
Step 3 − All other bit positions are for the data to be encoded using (3, 5, 6, 7, 9, 10 and 11, etc.)
Each parity bit calculates the parity for some of the bits in the code word. The position of the parity determines the sequence of bits that it alternatively checks and skips.
Position 1 − Check 1 bit, then skip 1 bit, check 1 bit and then skip 1 bit and so on (Ex − 1,3,5,7,11, etc.)
Position 2 − Check 2 bit, then skip 2 bit, check 2 bit, then skip 2 bit (Ex − 2,3,6,7,10,11,14,15, etc.)
Position 4 − Check 4 bit, then skip 4 bit, check 4 bit, then skip 4 bit (Ex − 4, 5, 6, 7, 12, 13, 14, 15, etc.)
Position 8 − Check 8 bit, then skip 8 bit, check 8 bit, then skip 8 bit (Ex − 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31).
Note − Set the parity bit 1 if the total number of 1s in the positions it checks odd or set the parity bit 0 if the total number of 1's in the positions it checks even.
Example
Construct the even parity Hamming code word for a data byte 10001101.
The number (D7 - DO 10001101 ) of bits is 8.
The value of r is calculated as −
⇒ 2^4 ≥ 8 + 4 + 1
⇒ 16 ≥ 8 + 4 + 1 (True)
No comments:
Post a Comment