Hamming distance

Hamming distance is the number of positions at which two equal-length strings differ. It measures substitutions without accounting for insertions or deletions.

Hamming weight: The number of nonzero symbols in a vector or the number of 1s in a binary string. Comparing a binary string with another amounts to counting 1s in their bitwise difference.
Error-correcting code: A method of encoding data with redundancy so that errors can be detected or corrected. Codewords are designed to remain far apart under Hamming distance.
Binary string: A finite sequence whose symbols are drawn from the alphabet 0 and 1. Bit strings are the standard setting for Hamming-distance examples and applications.
Richard Hamming: An American mathematician and computer scientist whose work helped establish error-correcting codes. His 1950 paper introduced codes that correct errors using symbol differences.
Exclusive OR: A logical operation that is true when its two inputs differ. For binary strings, exclusive OR marks exactly the positions counted by the distance.
Minimum distance decoding: A decoding rule that selects the codeword nearest to a received word under a chosen distance. Hamming distance makes this rule a direct way to decode substitution errors.
Finite alphabet: A finite set of symbols from which sequences or messages can be formed. Hamming distance applies to equal-length strings over any finite alphabet.
Error detection and correction: Methods for identifying and recovering from errors in stored or transmitted data. Hamming’s distance formalized how many substitutions separate valid messages.
Metric space: A set equipped with a distance function satisfying nonnegativity, identity, symmetry, and the triangle inequality. Hamming distance satisfies the metric axioms on strings of a fixed length.
Hamming code: A family of binary linear error-correcting codes introduced by Richard Hamming. Its codewords have a minimum Hamming distance that enables single-error correction.

Linked from 17 pages