# Détection des erreurs de parité

### Durée estimée: 45 minutes

## Introduction

As you learned in the previous lesson, the card "trick" is really not a magic trick at all. It is a very precise algorithm of error checking based on the concept of*.*

**parity**
In mathematics, *parity* refers to the evenness or oddness of a number. In
the card trick, a *parity bit* was added to each row and column such that the
additional bit would make the row or column have an even number of 1 bits. This is
known as * even parity*. The "trick" would also work if the parity bits
were set so as to make each row and column have an odd number of 1 bits. That would
be known as

*.*

**odd parity**
It's important to realize that the parity bit is not part of the data. It is * redundant*, an extra bit, added to the data to allow us to detect if one of the data bits has been flippedfrom its original value.

## Parity Bit Error Detection

Suppose you are sending a stream of data to a server. By adding a*parity bit*, you enable the server to detect some basic transmission errors. For example, if the server expects that every byte will contain an

**even number of 1s**and it detects a byte such as 0001 0101 with an odd number of 1s, it can tell that an error occured. Perhaps the user meant to send 0000 0101 but one of the bits was flipped from 0 to 1 during transmission.

A **parity bit** is a bit that is added as the leftmost bit of
a bit string to ensure that the number of bits that are 1 in the bit string
are *even* or *odd*.

To see how this works, suppose our data are stored in strings containing 7 bits. (You might remember that the ASCII scheme, when it was initially introduced, was a 7-bit code. In practice, a parity bit would be added to the ASCII code so that 1-bit errors could be detected in the resulting 8-bit byte.)

In an **even parity scheme** the eighth bit, the **parity
bit**, is set to 1 if the number of 1s in the 7 data bits is odd,
thereby making the number of 1s in the 8-bit byte an even number. It
is set to 0 if the number of 1s in the data is even.

In an **odd parity scheme** the eighth bit, the **parity
bit**, is set to 1 if the number of 1s in the 7 data bits is even,
thereby making the number of 1s in the 8-bit byte an odd number. It
is set to 0 if the number of 1s in the data is odd.

The following table summarize this approach.

Data Bits (7) Add a parity bit to get 8 bits Even Parity

Total number 1s is evenOdd Parity

Total number of 1s is odd000 0000 (0 1s) 0000 0000 1000 0000 011 0010 (3 1s) 1011 0010 0011 0010 011 0011 (4 1s) 0011 0011 1011 0011 011 0111 (5 1s) 1011 0111 0011 0111

## Exercice sur la parité

## Auto-contrôle

Here is a table of the technical terms introduced in this lesson. Hover over the terms to review the definitions.
parité
parité paire parité impaire bit de parité |

### Questions sur la parité

## En savoir plus ?

As you learned in this lesson, with 1 redundant parity bit you can detect 1-bit errors in a stream of bits. Actually, you could detect that an error occurred if 1, 3, 5, or any odd number of bits were flipped, but not 2, 4, 6. or any even number of bits.Detecting an error in a bit stream means that the bit stream would have to be retransmitted. Or, if writing the bit stream to the disk, it would have to be rewritten.

#### Error Correction Codes

Is it possible to *correct* errors as well as detect them? The
answer is 'yes' but it will require more, redundant bits. Actually, you saw this
with the card trick. In that case, each data bit had 2 parity bits, 1 at the end
of its row and 1 at the end of its column. That's what enabled us to identify
the exact bit that was flipped (in the case of a single bit). And the intersection
of the row and column that had the wrong parity, is how we identified the bit. If
you can identify the bit that was flipped, then you can correct it by flipping it back.

A more general way of correcting errors such as this is known as *Hamming Code* and
the following video shows how this very interesting approach works.

## Pour votre Portfolio

Create a page named * Parity Error Checking* under the

*Reflections*category of your portfolio and answer the following questions:

- Explain how the error card trick from Lesson 3.6 uses a parity scheme. Was it an even or odd parity scheme?
- What are some of the limitations of using parity bits for error detection?
- Another type of error detection is a check sum. Research what a check sum is and then describe it in your own words. Can a check sum identify where an error occurs?
- (Optional) Explain in your own words the difference between error detection and error correction. Describe how the error correction process used in the video above allows the computer to fix errors.