Parity

Objectives

1. Understand even and odd parity
2. Understand how a parity bit can be calculated
3. Understand how a parity bit can be checked
4. Understand how errors can be detected with a parity bit
5. Understand the errors that can't be detected with a parity bit.
6. Understand how RAID uses parity

Notes

• Parity is a method to detect errors in an encoding.
• To compute the parity of a code, add the number of 1s
• For even parity this should be an even number.
• For odd parity this should be an odd number.
• Parity is achieved by adding a bit, the parity bit, to a code.
  • Assume we are sending a 5 bit code with even parity.
  • We add a single bit for a total of six bits.
  • We must agree where we will add that bit.
  • In this case, let's make it the last bit.
  • If we wish to transmit 11010
    • We note that there are three ones, so we need to add a 1
    • So we will transmit 110101
  • If we wish to transmit 10100
    • We note that there are 2 ones, which is even so we add a 0
    • We will transmit 101000
• We check the parity of a transmission the same way
  • Assume that we are dealing with 4 bit odd parity.
  • We add a parity bit to the end.
  • We receive 01110 is this correct
    • Adding counting the 1 bits we get 3
    • 3 is odd so the message is possibly correct, and is 0111
  • We receive 10100 is this correct?
    • Counting the bits we find that the parity is 2 or even.
    • But this should be odd, so there is an error.
    • We don't know what the error is, but we know there is an error
• This is called error detection.
• But it can only detect a single bit permutation
  • Assume we send the message 10111000 in 8 bit (including parity) even parity.
  • We receive the message 10110100. Is this message correct?
    • No, it is not the same pattern.
    • But can we detect this with parity? No
    • We are in even parity and the bits sum to 4,
• Data communications and storage are examples of where parity is used.
  • A first stage of memory error detection is to use a parity bit.
    • Add 1 bit per word.
    • If the parity is incorrect the memory is corrupt.
    • This adds expense due to:
      • Extra hardware needed to do parity checks (very low, but some)
      • Extra memory needed to store parity bit (probably much higher)
    • And it slows down memory access just a little bit.
  • One type of RAID (Redundant array of independent disks) uses parity
    • Data is split between three drives.
    • Drive 1 and 2 store data
    • Drive 3 stores the parity of that data.
      • This is based on a boolean operation xor or exlusive or.
        • xor is ⊕
        • it takes to values and returns a third >

          a	b	a⊕b
          0	0	0
          0	1	1
          1	0	1
          1	1	0

      • We will examine further boolen expression in the near future.

    • Same space on 
      Drive 1          10110011
      Drive 2      xor 01101001
                       --------
      Drive 3          11011010  (the even parity bit)
      
      If we lose drive 2
      Drive 1 xor drive 3 = data on drive 2
                       10110011
                   xor 11011010
                       --------
                       01101001