I have a (seemingly) simple question about coding theory. I feel like the answer to this should be very obvious, but I'm having some troubles with it.
I'm trying to create binary code which is $N$ bits in length and consists of $M < 2^N$ codewords, $\{m_1, m_2, … , m_M\}$.
For a given $N$ and $M$, is there a general algorithm/approach to generate $\{m_1, m_2, … , m_M\}$ such that the minimum Hamming distance between any two codewords in the code is maximized?
It's pretty obvious that there isn't necessarily a unique solution for a given $N$ and $M$ (if $N=4$ and $M=2$, both $\{0000, 1111\}$ and $\{0101, 1010\}$ have $d_{min} = 4$), but I'm interested to know if there's a way to generate an "ideal" code based on Hamming distance (or the full set of codes) for an arbitrary $N$ and $M$. I could imagine brute-forcing this easily enough, but it feels like there should be a simple way to express this mathematically. Any help would be appreciated.
Best Answer
The coding-theoretic function $A(n,d)$ is the maximal size of a binary code of a length $n$ with minimum distance $d$. There is no known way to find its value easily, so in other words, it is not easy to determine whether, given $n$, $M$ and $d$, an $(n,M,d)$ binary code exists. In your case, there is no easy way even to find the maximal Hamming distance, let alone construct a code with the maximal Hamming distance. Some of the known values of $A$ are tabulated e.g. here.