Lukket

The Hamming distance dist(u, v) between two binary vectors

The Hamming distance dist(u, v) between two binary vectors v = (v1, . . . , vn) and w = (w1, . . . , wn) is the number of indices k such that vk 6= wk. A fundamental question in coding theory is to determine the

number A(n, d) = max |{S ⊂ {0, 1} n | dist(u, v) ≥ d for all distinct u, v ∈ S}|,

the maximal number of binary vectors of length n that one can find such that any

two distinct vectors have a Hamming distance ≥ d. For example, A(5, 4) = 2.

The Hamming graph H(n, d) = (V, E) is the graph with 2n vertices V given by

binary strings of length n. We have (u, v) ∈ E if and only if dist(u, v) ≥ d.

The number A(n, d) coincides with the size of a maximal clique in H(n, d).

Find an implement “efficient” algorithms to compute the maximal clique in the

Hamming graph (but note that the problem to compute maximal cliques is NP

hard).

Evner: Python, Algoritme

Projekt ID: #23949524