Top Qs
Timeline
Chat
Perspective

Hamming ball

Set of strings with few differences From Wikipedia, the free encyclopedia

Hamming ball
Remove ads

In combinatorics, a Hamming ball is a metric ball for Hamming distance. The Hamming ball of radius centered at a string over some alphabet (often the alphabet {0,1}) is the set of all strings of the same length that differ from in at most positions. This may be denoted using the standard notation for metric balls, . For an alphabet and a string , the Hamming ball is a subset of the Hamming space of strings of the same length as , and it is a proper subset whenever . The name Hamming ball comes from coding theory, where error correction codes can be defined as having disjoint Hamming balls around their codewords,[1] and covering codes can be defined as having Hamming balls around the codeword whose union is the whole Hamming space.[2]

Thumb
Hamming balls centered at the string "cab" with radius 1 (orange vertices and center), 2 (previous ball plus yellow vertices) and 3 (previous plus gray vertices).

Some local search algorithms for SAT solvers such as WalkSAT operate by using random guessing or covering codes to find a Hamming ball that contains a desired solution, and then searching within this Hamming ball to find the solution.[2]

A version of Helly's theorem for Hamming balls is known: For Hamming balls of radius (in Hamming spaces of dimension greater than ), if a family of balls has the property that every subfamily of at most balls has a common intersection, then the whole family has a common intersection.[3]

Remove ads

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads