Perfect error correction is impossible.  You can spend four
years in grad school learning to prove this rigorously, or you can
accept the following explanation:

        The minimum number of different messages that a transmitter
may possibly be transmitting is two.  In practice, of course, it's
always a lot more than that, but it must be at least two.  If the
transmitter could only send one message, then there would be no cause
for the receiver to bother decoding the message -- it could just
assume that it was *the* message and act accordingly.  The "act" of
not transmitting the message is not relevant here, since one possible
kind of error is the apparent transmission of a ghost message that was
never actually sent by the transmitter.  In other words, the
transmitter-receiver model is only applicable where there are more
than one possible message that can be sent.  Given that, an error so
nasty that it changes the bit-pattern of message number 1 to that of
number 2 (including any error-correction data, which see) is
undetectable.  Sorry.  You lose.  Nothing you can do.

        In practice, of course, error-correction techniques are
available that make the chances of this happening so small as to be
not worth consideration.  Here are a few, starting from the basics --
read them from the beginning, as later ones may depend on terminology
introduced in earlier ones:



Parity bit:
        The "parity" of a block of bits is "even" ("parity 0") if the
number of 1's in the block is even, "odd" ("parity 1") if the number
of 1's is odd.  Thus, the single bit 1 has odd parity, or parity 1,
and 0 has parity 0.  A block of k bits can always be made into a block
of k + 1 bits with parity 0, by attaching a bit to the end whose
parity is equal to the parity of the original block.  Example:

        1001011    (k = 7, the parity of this block is 0)

        10010110   (k + 1 = 8, parity of added bit is 0, total block
                    is parity 0)



        The receiver knows that all valid blocks (i.e.: blocks equal
to the ones transmitted) have parity 0.  If a just one bit in a block
is changed in the channel, then the received block will have parity 1.
So we have the ability to detect the existence of a 1 bit error.  This
doesn't imply the power to correct the error -- that would require
knowing which bit was changed, so we could change it back.  Nor are we
insured against errors in two different bits, which would preserve the
parity that is our only clue.  In fact, we can only detect the
existence of an odd number of errors, and we won't even know how many
there were.


Hamming:

        The "Hamming weight" of a binary block is the number of 1's in
it.  The "Hamming distance" between two two binary blocks (assumed to
be of the same length) is the number of places in which they differ.
Just XOR blocks A and B together, and you'll get a block E of the same
length that contains 1's where A and B differ.  E is the error pattern
block, and its Hamming weight is equal to the Hamming distance between
A and B.  Neat, huh?