Please enable JavaScript.
Coggle requires JavaScript to display documents.
ERROR DETECTION chapter 8 - Coggle Diagram
ERROR DETECTION chapter 8
TYPES OF ERROR
SINGLE BIT ERROR
only one bit given data unit is changed from 1 to 0 or 0 to 1
occur in parallel transmission(between CPU and memory)
BURST ERROR
2 or more bits the data unit have changed from 1 to 0 or 0 to1
length of burst measured by the first corrupted bit to the last corrupted bit
occur in serial transmission
REDUNDANCY CONCEPT
DEFINITION
adding extra bits for detecting errors at
the destination. allow the receiver to detect and
correct corrupted bits
ERROR DETECTION
to see if any error has occurred
ERROR CORRECTION
to know the exact number of bits
corrupted and their location
ERROR DETECTION AND CORRECTION METHODS
BLOCK CODING
message will be divided into
blocks, each of k bits, called datawords
redundant bits, r, is added to each block to
make the length n = k + r.
result n-bit blocks = codewords
error detection process
two conditions that helps receriver detect a change in the original codeword
receiver has a list of valid codeword
original codeword has changed to an invalid one
LINEAR BLOCK CODING
exclusive OR of two valid codewords creates another valid codeword
SIMPLE PARITY CHECK
redundant bit( parity bit) added to every data unit so the total number of 1s become even (or odd)
PARITY CHECK
organized in a table
parity bit calculated for each data unit
CYCLIC CODING
codeword is cylically shifted (rotated), the result is another codeword
Example, if 1011000 is a codeword and we cyclically
left-shift, then 0110001 is also a codeword
CYCLIC REDUNDANCY CHECK(CRC)
based on binary division
sequence of redundant bits, called CRC or CRC
remainder, is appended to the end of data unit
derived by dividing the data
unit by a predetermined divisor
POLYNOMIALS
pattern of 0s and 1s can be represented as a
polynomial with coefficients of 0 and 1
coefficient shows the value of the bit
CHEKSUM
used by the higher-layer protocols
sender
The message is divided into n bits (usually 16 bits)
All words are added using one’s complement addition
The sum is complemented and becomes the checksum
The checksum is sent with the data
Receiver
The message (including checksum) is divided into n bit (16 bits)
All words are added using one’s complement addition
The sum is complemented and becomes the new checksum f the value of checksum is 0, he message is accepted;otherwise, it is rejected
ONE'S COMPLEMENT
Present the unsigned numbers between 0 and 2n – 1 using only n bits
If the number has more than n bits, the extra leftmost bits need to be added to the rightmost bit (wrapping)
A negative number can be represented by inverting all bits (changing 0 to 1 and 1 to 0)
MODULAR ARITHMETIC
limited range of integers is used
used in error detection and correction is modulo-2 arithmetic – only integer 0 and
1 are used
Used operation XOR (exclusive OR) for addition and
subtraction
– the result is 0 if two bits are the same;
the result is 1 if two bits are different
