Let us assume that the probability of transmission error is small. That is certainly true with our technology today. By small we mean that the probability of a single bit being wrong in a message is some small fraction of a percent (as small as possible). In particular, we ignore catastrophic errors such as scratches or breaks in media, which produce large bursts of errors.
Parity is about evenness or oddness, in the numerical sense. To find out the parity of a message, we add up the bits in the message; if the number of 1's is even, then we say that the message has even parity (or parity zero). If the number of 1's is odd, then we say that the message has odd parity, (or parity 1). Another way of saying this is that the parity of a message is
Parity = Sum_of_bits mod 2
The idea of a parity check is to make an extremely primitive message digest. We use one bit in a bit-string to signal the parity of that string. The sender calculates the parity and appends a parity bit to the data (e.g. 1 bit in every byte). The receiver then checks that the parity is consistent with the received message. If it is not consistent, then an error must have occurred. There are two problems with this:
We can only detect an odd number of errors. (If errors are few this should not be a problem in practice)
There could be an error in the parity bit itself
Errors must be corrected by retransmission.
A single error in a binary code can be detected without much loss of efficiency. For a given codeword, we count the number of times the digit 1 appears in the string, then append an extra check digit to the string which would make this number even. If the number of 1's is even we append a else a 1. For example the codeword 0010 is in the binary code C over . The number of 1's is odd so the check digit should be 1, changing the codeword to 00101 which is in a (5,4) parity check code. For the codeword 0011 in the same code the check digit will be , making it 00110.
Now, a...