If you receive some information, how do you know if it’s intact or has been changed?
Let me make this point clear from the beginning. Error detection only lets you detect errors. It doesn’t correct them. You have to provide other means to fix any errors. Usually this just means trying again.
Parity works by including an extra bit for a small fixed number of data bits. You might want to include a parity bit for every byte or eight bits. This means that if you want to send a parity bit for every eight data bits, then you’ll really be sending and receiving nine bits instead of eight.
The other option is to take a data bit away. Maybe you need to send information through a connection that can only support a fixed number of bits. You can’t just add an extra bit. So instead, what you do is devote one of the bits as the parity bit. This leaves you with one fewer bits to use for your actual data.
Okay, so how does parity actually work? It sets or clears the parity bit in order to make the total number of bits with the value of 1 be either even or odd. Setting a bit just means to make its value one. And clearing a bit just means to make its value zero.
Listen to the full episode or read the full transcript below for more details on parity.
Transcript
When I was little, my school teacher asked the class to form a line and relay a message from one kid to the next. Everybody thought it was funny that the message at the end was nothing like how it started. Some kids would forget parts, some would leave parts out because they thought it wasn’t important, and some would add new things based on what they thought they heard.
It’s amazing how closely programming resembles real life. I know I say that a lot. But it’s true!
You might think a computer won’t forget things, or choose to leave things out. And how could a computer make up it’s own story? Well, these things do happen. And we need a way to detect them.
Let me make this point clear from the beginning. Error detection only lets you detect errors. It doesn’t correct them. You have to provide other means to fix any errors. Usually this just means trying again.
Where can errors enter your application? It’s easy to understand where the errors come from in a line of kids. How about computers? Computers are a lot more reliable today than they used to be and they’re getting better.
I remember when hard drives had a sticker that listed all the bad sectors. Those were places on the disk known to have defects. The worst part was the label had empty spots. Room to add your own bad sectors. I would run utilities every few months that would scan the entire disk. It would write data and make sure the same data could be read back again. Sometimes a value would be written and a different value read back. That was a bad sector and would have to be avoided because it was unreliable. Over time as I found new spots on the disk that were bad, I would write down the locations on the sticker.
Even though we don’t have to go through this anymore, there can still be errors when reading or writing data. Usually, once data is loaded into a computer, it’ll stay there. But nothing is absolute. It’s possible for data in memory to fail to be written properly or even to change. Not likely, but possible.
You’re much more likely to get errors when sending information from one computer to another. I’ve been talking about this a lot since episode 159. And we have protocols designed to deal with errors. But so far, I haven’t described how to actually detect when an error occurs.
Let’s start with a simple example. You want to send two binary bits and they’re both zeros. What possible results can you expect?
Well, first of all, you might actually get what was sent. But how do you know that it’s correct? What if you receive 01 instead? Was that what was sent?
What if you only receive a single 0? Or maybe you get 001? Or maybe you get four zeros? There’s lots of possibilities. I’m going to ignore cases where you receive a different number of bits than what was sent. These cases will usually be detected just because you should know ahead of time how many bits to expect.
What I’m going to describe here is not perfect. But it’s simple and fast. It’s called parity.
There’s actually two ways you can calculate parity. One’s called even parity and the other is called odd parity. These names come from even and odd numbers.
Parity works by including an extra bit for a small fixed number of data bits. You probably won’t include a parity bit for every two data bits like I started the example with. Instead, you might want to include a parity bit for every byte or eight bits. I’ll explain what this parity bit is in just a moment. For now, just understand that if you want to send a parity bit for every eight data bits, then that means you’ll be sending and receiving nine bits instead of eight.
The other option is to take a data bit away. Maybe you need to send information through a connection that can only support a fixed number of bits. You can’t just add an extra bit. So instead, what you do is devote one of the bits as the parity bit. This leaves you with one fewer bits to use for your actual data.
You’ll also find parity used in hardware. I mentioned earlier that you can usually rely on your computer’s memory. Some memory includes parity bits. Even though the computer isn’t sending or receiving data, it still has to write data to memory which means it leaves the confines of the processor. There’s always a small chance that when that data is needed again, it will be a different value when it makes its way back into the processor. Parity can be used here too in order to detect this.
Okay, so how does parity actually work? I’ve put this off to the very end because it’s really simple. It sets or clears the parity bit in order to make the total number of bits with the value of 1 be either even or odd. Setting a bit just means to make its value one. And clearing a bit just means to make its value zero.
Let’s say that you’re using even parity. This means the total number of one’s should be an even number. Back to the earlier example of sending a couple zeros. How many one’s are in that value? Zero. And zero is already an even number. So in this case the parity bit should also be zero. If instead you wanted to send the value 10, then the parity bit needs to be a one in order to bring the total number of ones to two which is an even number.
The information that gets sent includes the parity bit. To send 00 with even parity means that what actually gets sent is 000. To send 10 with even parity means that what actually gets sent is 110.
This is all good, but how does it actually help you detect errors? Well, let’s say that you received 000 and are expecting even parity. Yes, the sender and receiver must agree on the type of parity being used otherwise the whole system falls apart. Okay, so you get 000. The first thing to do is count the number of bits set to one. There are zero bits set to one. Zero is an even number. So the data passes.
If instead you received 001, then the test for even parity fails. As long as only a single bit error occurs, then parity will help you detect it. But there’s some cases that escape detection using just parity. What if you send the value 000 with even parity but there are two bit errors so what you receive is 101? This passes the even parity check but does not match the data sent.
Parity also doesn’t help if bits get swapped.
I’ll explain other methods that can help detect these types of errors next week. Parity may not be perfect but it’s so simple that it can be implemented in hardware. Many times, you won’t notice it until it detects an error.