📂Lemmas

Hamming Distance

Definition

For a natural number $n \in \mathbb{N}$, the Hamming distance is defined in the set $\left\{ 0, 1 \right\}^{n}$ of code points of length $n$ as the distance function $H$ given below¹.

$$ H \left( \mathbf{x} , \mathbf{y} \right) = \operatorname{card} \left\{ k : x_{k} \ne y_{k} \right\} $$ Here, code points are represented by $\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right)$ and $\mathbf{y} = \left( y_{1} , \cdots , y_{n} \right)$, and $\operatorname{card}$ is the cardinality of the set. Simply put, it’s the number of coordinates that differ when comparing two code points coordinate-wise.

Explanation

Hamming distance is one of the simplest distance functions aside from discrete distances. It can be seen as broadcasting a comparison operation from an exotic distance to each coordinate. Naturally, it can be used wherever there is a need to compare ‘difference’ or ‘disparity’ since it only requires the elements to be the same or different, making it a primary candidate in all fields that involve comparison.

Generalization

There’s no reason why Hamming distance cannot be generalized to finite sets other than binary numbers, like alphabets. Moreover, as long as the order is strictly maintained and comparisons can be made accordingly, it can be readily applied to various data types, including matrices and even more complex structures like tensors.