CYCLIC REDUNDANCY CHECK (CRC)
In synchronous communications, CRC is used
to verify the integrity of the entire packet or block of data. Integrity
of the packet means whether the complete packet of data received
in its correct form as it was sent from the sending end. In synchronous
communications, parity checking is sufficient to ensure data integrity.
In high-speed asynchronous communications, single bit corrections are not
enough. As each packet is created, a CRC check is placed somewhere in
the packet and is verified at the receiving end.
CRC is a calculation method used to check the accuracy of a digital
transmission over a communication link. The sending computer uses one of several
formulas to calculate a value from the information contained in the data, and
this value is appended to the message block before it is sent. The receiving
computer performs the same calculation on the same data and should drive the
same number. If the two CRCs do not
match, indicating that a transmission error has occurred, the receiving
computer asks the sending computer to retransmit the data.
This procedure is known as redundancy
check because each transmission includes extra or redundant error-checking
values as well as the data itself. A CRC is generated by dividing the total
number of bits in the block of data being sent by a predetermined binary
number. The reminder is then added to the packet and the packet
is transmitted. On the receiving end, the reverse mathematical operation is
performed to verify the packet contents. If the computation is
successful, the packet is passed to the next step. If it fails, the
issuing node is notified and the entire packet is re-transmitted.
Common CRC patterns are 12-bit
(CRC 12), 16-bit (CRC 16), and 32-bit (CRC 32).
One of the most common and widely used
error detection methods for synchronous data transmission is Cyclic
Redundancy Check (CRC), developed by IBM. IBM uses CRC-16 as the specific
application of the CRC method. This process uses a constant "divisor"
which is in binary form as ::
1000 1000 0001 0000 1
The steps are follows :
(a) Add 16 zeros (1 less bit than the
number of bits in the "divisor") after the Least Significant Bit of
the message to be sent. The message is then written down as it would be
transmitted, with the extra bits sent first ( i.e. most significant bits).
(b) The divisor is exclusive ORed with the
16 most significant bits of the message are appended to the result of this to
from another 16 bits of data headed by a 1.
(c) The exclusive ORing is repeated along
with the rest of the process until all bits in the message are exhausted.
(d) The final exclusive OR result is the
CRC characters. Enough leading zeros are appended to the CRC character to from
a total of 16 bits.
We shall try to understand the CRC character calculation using the
following CRC-4 method with the modified divisor constant of 10011:
Let the message be 1100 0110 1011 01 (The LSB is on the right)
There is one less zero than the total number of bits in the divisor
which is 10011. To use the shortened CRC-4 divisor, four zeros are
first appended to the message. The extended
message becomes:
110001101011010000
Now we set up the problem:
10011)110001101011010000
Exclusive OR the first five bits with the "divisor" we have:
10011)110001101011010000
10011
-----------
1011
By bringing down the next bit from the
message and repeating the process until all the bits in the appended message
are used.
We do this as shown below:
10011)110001101011010000
10011
----------
10111
10011
----------
10010
10011
----------
11011
10011
----------
10000
10011
----------
11100
10011
----------
11110
10011
----------
11010
10011
----------
1001 = CRC
The original message followed by the CRC-16
bytes is sent to a receiving station. At the receiving station, the data are
shifted in and a CRC is computed using the entire message plus the CRC bytes.
If the same constant "divisor" is used, the result of the receiver's
CRC computation is all zeros when there are no errors.
To detect the correct communication errors, a sender must provide a
receiver with information that enables the receiver to verify proper receipt of
information or data. The sender could simply send an entire set of information
twice and let the receiver compare the two sets of information for error
detection, but because of the time and computer resources, it takes to perform
this type of comparison. It is more popular to detect the error based on
mathematical calculations that are hardware or software execute at high speed.
The sender must use a
mathematical technique to calculate error-checking data. The sender generates
this redundancy data from the bit stream of information data from the bit
stream of information data it sends and then appends the redundancy data to the
end of the bit stream. The receiver must generate its own redundancy data from
the information data it receives and compare the results with the redundancy
data it receives from the sender. A favourable comparison indicates the absence
of errors. An unfavourable comparison indicates the presence of errors.
No comments:
Post a Comment