COMP 3203 Lecture Notes - Lecture 5: Hamming Distance, Error Detection And Correction, Parity Bit
26 Oct 2018
School
Department
Course
Professor
Document Summary
Error correction: error correction like error detection, uses the idea of redundancy (redundancy needed, error correction is more difficult than error detection! Not only you must detect that an error occurred, you have to correct it, as well: to correct a bit-error it is enough to locate it. Its significance is that if two codewords are a hamming distance d apart, it will require d single-bit errors to convert one into the other: the hamming distance of 10001001 and 10110001 is 3. With odd parity 1011010 becomes 10110101: a code with a single parity bit has a distance 2, since any single-bit error produces a codeword with the wrong parity. It can be used to detect single errors: example error correction, consider a code with only four valid codewords: 1111111111: this code has a distance 5, which means that it can correct double errors. If the codeword 0000000111 arrives, the receiver knows that the original must have been 0000011111.
