That Gurjot

Witness the normal



PARITY TIME! Let’s Drill Holes in CDs

27 Mar 2013

I have a course on digital electronics this semester.

Digital electronics is pretty interesting; the fact that everything inside my laptop or my smartphone is based on a tiny little thing called a flip flop, blows my mind. Flip flops were just open-toed sandals (that’s what Wiki calls them) or chappals (that’s what we call them in India) till December last year. Now they are much, much more than that. They are the Higgs Bosons to nearly all of electronics.

If you think I am exaggerating, here’s something for you to chew on - everything electronic today has a very basic entity attached to it: data. Data is generated, stored, used, flown, mined and everything else. Flip flops are the tiniest devices which can store data. A single flip flop stores a single bit of data.

Flip flops are awesome. Admit it.

So let’s get to the par(i)ty now. Par(i)ty? Oh, I meant party. Wait. Parity. Yeah, Parity.

Parity

Parity in mathematics is just whether a number is even or odd. That’s it.

In electronics, however, it is much more. Parity is used in transmission of data. I hope you’re familiar with ASCII code. Originally ASCII code had 7 bits. The 8th bit was a parity bit. There’s even parity and odd parity but I don’t need to go into deeper details about that. In broad generalization an even parity checker works like this - on generation of code it checks whether the number of bits that are logic high (1) is even, if it isn’t it adds 1 as the parity bit, if it is even, it adds 0. When the code is transmitted to the end receiver, the parity checker there checks again. If a code with an even parity is received it accepts it, if the number of 1’s in the code is odd, it rejects it because the data has been transmitted incorrectly then. Flip the evens and odds for an odd parity checker. Wait. An instance will do more than a volume of generalities to make the meaning clear. Suppose wants to transmit the code to . The even parity checker sees that there’s 4 1’s in the code, so it adds the last parity bit as 0. So the code that is transmitted to is actually . Upon receiving the code, B checks the number of 1’s in it, the number is still even and so knows that the data that has been transmitted is correct and thus it accepts the input. In case the code is transmitted incorrectly and B actually receives a code with one bit flipped - something like . It’ll see that the number of 1’s is odd when instead it should have been even, so it rejects the input.

A very obvious flaw to this system is if the number of errors is even, that is, if instead of one, two or maybe even four bits were flipped during transmission, will still accept the code. But it works in most cases. I am not sure if this method is still used but it sounded pretty cool to me.

Bonus! (or the drilling holes reference you came here for)

Parity checkers are used in some pretty amazing ways. Here’s two of them:

  1. RAID devices : In RAID levels the data is stored in various drives. We use parity in order to protect data from being lost. How? Here’s how: suppose drive 1 has the data stored in it and drive 2 has in it. We XOR the data in both the drives and store it in a drive 3. In this case our drive 3 packs the code . If any of our drives crashes and loses all data, the data can be regenerated by XOR-ing the other two drives! Something similar occurs in CDs and DVDs. If you drill a tiny hole in a CD and then play it, it’ll still play as if nothing happened. How? It reconstructed the lost data from the rest of it! If the hole is big enough, say 2-3mm in diameter, well then your data is a goner.

  2. ISBN codes : Quick, pick nearest the book up! Flip to the back cover and look at the barcode, you’ll see something like this -
    ISBN
    The number on the top is the International Standard Book Number. This is how we keep track of all the books in the world. There’s two kinds of ISBN codes, one with 10 digits and the other with 13 digits. I’ll talk about the former first.

Till 1970 ISBN codes were of 9 digits only. Then the ISO added a tenth digit called the “check bit” or “parity bit” which helps make sure that the code is correct or not. Pick up any 10 digit ISBN code, say 0-306-40615-2. The magic here is that if you multiply each integer by its integer weight, that is, if you multiply 0 by 11, 3 by 9, 0 by 8 and so on till 2 by 1, and then add all those numbers the sum will always be a multiple of 11! This is how we make sure whether the ISBN is correct or not. If the sum isn’t a multiple of 11, the code is invalid. In case of a 13 digit ISBN the integers are multiplied by 1 and 3 alternatively and their sum is always a multiple of 10. So for we have something like 9 * 1 + 7 * 3 + 8 * 1 + 0 * 3 and so on.


Sources : ISBN Check digits.