Error control coding

Error Control Coding
 Purpose – to enable receiver to detect, or even
correct errors in transmitted data
 The idea is to introduce some redundancies into
the data to be transmitted
 Data communications errors:
 Single bit
 Only one bit in data stream is in error
 Multiple bit
 Two or more non-consecutive bits in data stream are in error
 Burst
 Two or more consecutive bits in data stream are in error

 Probability of error, P[e] = the theoretical
expectation of the rate at which errors will occur
 Bit error rate (BER) = actual historical record of a
system’s error performance
 Two general categories of error control:
 Error detection
 Error correction

Example 1
 Given P[e] = 10-5. If 1 Mbits of data are transmitted,
how many bits may be in error?

Error Detection
 Error detection = determine when errors have occur
 Error detection indicates only when an error has
occur. It does not prevent the error
 Most common technique is redundancy checking,
which includes:
 Vertical redundancy checking
 Checksum
 Longitudinal redundancy checking
 Cyclic redundancy checking

Redundancy Checking
 Redundancy is a form of error detection in which each
data unit is duplicated
 Effective but costly (complex) especially with long
messages
 Redundancy checking = adding redundant bits for
error detection

Vertical redundancy checking (VRC)
 VRC is also referred to as parity
 Each character has its own error-detection bit, called
the parity bit
 Single parity bit is added to each character so that the
total no. of logic 1’s in the character plus the parity bit,
will be an odd number (for odd parity) or even number
(for even parity)

Example 2
 Determine the odd and even parity bits for the ASCII
character R

 Advantage of VRC:
 Simple
 Disadvantage of VRC:
 If an even no. of bits are in error, the parity checker will
not detect them because the parity of the character
remains the same
 Parity will theoretically detect only 50% of transmission
errors

Checksum
 Each character has a numerical value (known as
‘checksum’) assigned to it
 Receiver’s checksum is compared to the checksum
appended to the message, and if they are same, no
errors. If different, there are errors

Longitudinal redundancy checking
(LRC)
 Uses parity to determine whether a message has an
error
 LRC is sometimes called message parity
 Each bit position has a parity bit
 LRC bits are calculated in the transmitter and
appended at the end of message as redundant
character
 At receiver, LRC is recomputed from the data. If the
two LRC values are the same, no error. If not, there is
error

 Bit sequence for LRC is often called block check
sequence (BCS)
 Using LRC, all messages (regardless of their length)
have the same no. of error-detection characters

Example 3
 Determine VRC and LRC for the following ASCII-encoded
message: THE CAT. Use odd parity for VRCs
and even parity for LRC

Cyclic redundancy checking (CRC)
 Is a convolutional coding scheme
 In CRC generation, modulo-2 division is used;
remainder is derived from an exclusive OR (XOR)
operation
 At receiver, the data stream, including the CRC code, is
divided using the same generating function. If
remainder is zero, means no error

 CRC can be expressed as:
G x
( )
P x
( )
Q x R x
 
G(x) = message polynomial
P(x) = generator polynomial
Q(x) = quotient
R(x) = remainder
( ) ( )
 No. of bits in CRC character is always twice the no. of
bits in a data character

Error Correction
 Two basic types of error messages:
 Lost message
 Never arrives
 Damaged message
 Arrives but contains errors
 Error-correcting codes include extra information so
that receiver will know if there is an error, and where
 Two methods of error correction:
 Retransmission
 Forward-error correction

Retransmission
 Retransmission:
 If received message is in error, the receiver asks
transmitter to resend the message
 Forward error correction (FEC):
 Errors are detected and corrected
 Redundant bits are used to determine which bit is in
error, and to correct it, simply complement the
redundant bits
 No. of redundant bits must be much greater than the no.
of bits needed to only detect errors
 Is generally limited to one-, two- or three-bit errors

Hamming Code
 Is an error-correcting code
 Can only correct one-bit errors
 Hamming bits are inserted into a character at random
locations

Error control coding

Recommended

More Related Content

What's hot (20)

Viewers also liked (6)

Similar to Error control coding (20)

More from Mohammad Bappy (16)

Recently uploaded (20)

Error control coding