Integrity checks may be applied for each byte or on the groups of bytes forming a link-level transmisison frame.
Character or byte parity is an error detection technique that is typically used with asynchronous links. It is used to verify the integrity of each individual received byte. When used, each character (byte) is protected at the sender by one additional single parity bit, which is the logical exclusive or of all the bits in each byte.
A frame integrity check protects all the bytes in a frame. It seeks to verify if the whole farme is correct (i.e. can not identify in which byte an error occurs, but instead just tells if there have been any detected errors within the entire frame).
The simplest form of frame integrity check is the longitudinal paritry checksum. This consists of an additional byte added at the end of each transmisison frame by the sender. The receiver performs the same opeartion as the sender and compares the calculated value with the received checksum. If both match the frame, then the frame is judged to be valid. If not, it is invalid (and will usually be discarded by the receiver).
One way to see this is:
For each bit position (i := 0 to 7) calculate the XOR sum of all the bits and palce this in the longitudinal parity position i.
This provides an independent check for each bit position. The accumulated checksum is an 8-bit value. The example below shows calculation of the logitudinal parity for a 3 byte frame. Ecah column shows one 8-bit byte. The final column shows the accumulated parity values for the frame.
Byte0 Byte1 Byte2 Parity
0 0 0 0
1 1 1 1
1 0 1 0
1 1 0 0
0 0 1 1
1 1 0 0
1 1 1 1
1 0 1 0
However, this process is costly to implemkent in a computer algorithm In fact, computers are very efficient at performing byte-wise logica operations and henc can easily accumulate the byte-wise exclusive OR (XOR) or all bytes within a frame. Implementation of longitudinal parity is very easy using a microcontroller or computer, requiring only a register to accumulate the checksum and one XOR operation per byte.
[Note: The checksum value accumulatd for an ASCII string is not necessarily an ASCII printable character. When displaying an NMEA GPS sentence, there needs to be a way to display the checksum to a user, in this case it is dispalyed as two hexadecimal digits.]
Sample code to generate a longitudinal parity checksum:
var checksum = 0;
for(var i = 0; i < stringToCalculateTheChecksumOver.length; i++) {
+checksum = checksum ^ stringToCalculateTheChecksumOver.charCodeAt(i);
}
The longitudinal checksum can indicate if there is corruption of the data, but has a number of weaknesses:
For each bit position in every byte, this checksum can detect any odd number of bit inversions (errors). Since errors often occur in bursts, this can provide more detection than expected, but can not correct errors, hence corrupted frames need to be discarded.
The method is also known as a Longitudinal Redundancy Check (LRC), Bit-Interleaved Parity (BIP-8) and ISO 1155.
A longitudinal arithmetic checksum is more powerful. That is, it is able to detect more patterns of error than a parity checksum. The checksum achieves this by replacing the XOR operation used to accumulate the checksum value with an ADD operation. In itself this makes the sum sensitive to repeated values the same i.e. byte 0x01 followed by byte 0x01 and then byte 0x01 accumulates a sum of 0x03, whereas the longitudinal parity would have the value 0x01 (identical to the value had the sequence been 0x01, 0x00, 0x00). The accumulated checksum mnay be one or more bytes per frame.
There is however a flaw in this basic method, in the ADD operation may generate a carry. This would lead to less ability to detect errors in the most significant bit. To overcome this, most arithmetic checksum algorithms not only add the values, they also add any accumulated carry into the least significant bit of the accumulated sum. This provides equal protection for every bit position in the bytes.
Protocols at the network layer and higher (e.g. IP, UDP, TCP) often use this checksum to verify that the data being transported has not been corrupted by the processing performed by the nodes in the network.
A CRC is a powerful method for detecting errors in the received data is by grouping the bytes of data into a block and performing an integrity check. This is usually done by the link protocol and the calculated CRC is then appended to the end of each link frame.
Examples of systems using integrity check methods include:
Prof. Gorry Fairhurst, School of Engineering, University of Aberdeen, Scotland. (2014)