Top Qs
Timeline
Chat
Perspective
Hamming ball
Set of strings with few differences From Wikipedia, the free encyclopedia
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]

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
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads