Calculating the Parity Bit of a Bit Sequence | Baeldung on Computer Science

1. Introduction

In this tutorial, we’ll study a simple technique for checking errors in the transmission of a binary string: parity checking.

Despite its simplicity and vulnerability, we can use this method in many applications for error prevention such as reading data from magnetic tapes and storing information in main memory.

2. Parity Control and Parity Bit

Let’s consider a message $M$ we codify as a binary string of 1 byte (8 bits) that is sent from sender $A$ to a receiver $B$ :

$M\equiv b_{1}b_{2}b_{3}b_{4}b_{5}b_{6}b_{7}b_{8}$

The transmission of $M$ involves the encoding, transport, and decoding of the message, operations potentially subject to errors. To be sure that $B$ receives a message that’s identical to the transmitted one, we need a check.

Of course, any potential control involves the transmission of a certain amount of information in addition to the original message. It is this extra information that allows the analysis of the information present in the message we receive.

One of the simplest methods of verification is the parity check. Parity is a control code we can use to prevent errors in data reception or reading on mass memories, adding redundant information.

This technique adds to each byte an additional bit $p$ , the parity bit. When writing data (bit sequence), we add a control bit set to 0 or 1 after each byte.

If within a byte, the bits at 1 are even in number, the additional bit will be set at 0. If the bits at 1 are odd, we add a bit at 1.

The sent message, $M_ {s}$ , is therefore different from the original message, $M$ . Assuming that $p$ is at the end of each byte, we have:

$M_ {s} = Mp \equiv b_ {1} b_ {2} b_ {3} b_ {4} b_ {5} b_ {6} b_ {7} b_ {8} p$

3. Detection of Errors Through Parity Check

When receiver $B$ groups the bits received, it performs the check by simply counting the number of 1. If the case of error (a 0 becoming 1 or vice versa), $B$ will send a retransmission request.

A limitation of the parity check concerns the case in which an error occurs involving two bits of the word (or in general an even number of bits). In this case, the error would go unnoticed, as the parity would be maintained.

4. Calculation of the Parity Bit

4.1. Message Without Errors

For each byte, $A$ calculates the parity bit by performing an XOR between all the bits of the message $M$ :

$p = b_ {1} \oplus b_ {2} \oplus b_ {3} \oplus b_ {4} \oplus b_ {5} \oplus b_ {6} \oplus b_ {7} \oplus b_ {8}$

Suppose $M \equiv00110110$ . $p$ is:

$p = 0 \oplus0 \oplus1 \oplus1 \oplus0 \oplus1 \oplus1 \oplus0 = 0$

The sent message becomes:

$M_ {s} \equiv Mp = 00110110 \mathbf {0}$

Now $B$ receives the message and, to detect its accuracy, XORs all the bits of $M_ {s}$ . The result can only be 0 or 1. If it were 0 it would indicate that $M_ {s}$ has arrived correctly, otherwise, it would detect an error.

4.2. Message with Errors

Instead, suppose the message arrives incorrectly. If, for example, $b_ {7}$ changed its state from 1 to 0, we would have a situation like this:

$M_ {s} \equiv001101 \mathrm {\mathbf {0}} 00$

and the operation carried out by $B$ would be:

$p = 0 \oplus0 \oplus1 \oplus1 \oplus0 \oplus1 \oplus0 \oplus0 = 1$

which shows that there was an error.

4.3. Parity Check Failure

Let us consider the case in which the parity check fails when the number of errors in the transmission is even. Let:

$M_ {s} \equiv11010110 \mathbf {1}$

Suppose that the values of two bits change and precisely $b_ {1}$ and $b_ {2}$ which invert their state from 1 to 0. We get:

$M_ {s} \equiv \mathbf {00} 0101101$

The control operation carried out by $B$ is therefore:

$p = 0 \oplus0 \oplus0 \oplus1 \oplus0 \oplus1 \oplus1 \oplus0 = 1$

from which $B$ deduce, erroneously, that there was no error in the transmission.

In these examples, $B$ calculates the parity bit, located at position 9, using the first 8 bits of the message. From an implementation point of view, it is sufficient to apply the XOR operator on all the bits of $M_ {s}$ , including the parity bit. If there are no errors, the result is always 0. It is only necessary for $A$ and $B$ to know the position of $p$ in the sent message.

5. Conclusion

Parity checking is a method of checking for errors, not correcting them. There are techniques, such as the Hamming code, which serve both detection and correction.

Each error checking system in a message involves the transmission of information in addition to the original message.

Despite its simplicity, parity checking is a widely used technique in computer science. However, it is not without limitations, such as when the number of errors is even.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex