Sets with maximum hamming index

Abstract

The Hamming distance between two equal lengthed bit strings is the number of positions at which those strings differ. Let the Hamming index of a set S of equal lengthed bit strings be the number of pairs of strings in S that are at unit Hamming distance from each other. The lower the Hamming index of S, the more suitable 5 is as a set of binary codes that may be transmitted over data networks. We show a nontrivial result that the Hamming index of the set of equal lengthed binary representations of the numbers 0, n-1 is never less than the Hamming index of any set of n equal lengthed binary strings. In addition to being of interest in coding theory, our result has applications in graph embeddings and parallel computer architectures

Keywords:

• Binary number system
• Hamming distance