Hamming1

Hamming1 is a term used in coding theory to denote the one-bit flip neighborhood around a binary string. It describes the set of strings that differ from a given string in exactly one position, and is named for the concept of single-bit errors studied by Richard Hamming.

Formally, for a binary string x of length n, the Hamming1 neighborhood, denoted N1(x), consists of all strings y in {0,1}^n such that the Hamming distance dH(x,y) equals 1. There are exactly n such strings, corresponding to flipping each bit position once. This neighborhood is symmetric: every y in N1(x) is at distance 1 from x, and x is at distance 1 from each y in N1(x).

In coding theory, Hamming1 neighborhoods are used to reason about error detection and correction. When a binary code C is transmitted over a noisy channel, a received word r may lie in the Hamming1 neighborhood of a transmitted codeword c if a single-bit error occurred. A code with minimum distance dmin can detect up to dmin−1 bit errors and can correct up to ⌊(dmin−1)/2⌋ errors. In particular, ensuring that no two codewords are at distance 1 (i.e., dmin ≥ 2) prevents confusion between codewords due to single-bit errors, while dmin ≥ 3 enables single-error correction.

Example: for a 4-bit string x = 0101, the Hamming1 neighborhood N1(x) includes 1101, 0001, 0111, and 0100.

See also: Hamming distance, Hamming code, error detection and correction.