# Binary coding of Numbers with Minimum Hamming Distance

I am looking for binary encoding of a set of integers that satisfy the following two properties:

1. The number of 1s in the larger numbers is larger.

2. The hamming distance between the encoding of two consecutive numbers is minimized.

Is there any number coding scheme to do this?

The objective is to find a better encoding for ordinal values as a binary vectors. The common idea for encoding of ordinal values in machine learning is to consider them categorical and encode them as one-hot binary vector. But a one-hot vector is quite wasteful.

Suppose you encode two ordinal values $$o_1 < o_2$$ as $$d$$-dimensional binary vectors $$\mathbf{v}_1, \mathbf{v}_2 \in \{0, 1\}^{d}$$. For this encoding to be efficient, there should exist an embedding vector $$\mathbf{w} \in \mathbb{R}^{d}$$ such that $$\mathbf{w}^{\top}\mathbf{v}_1 < \mathbf{w}^{\top}\mathbf{v}_2$$.

• Could you be more specific about the first property, please? Taken literally, you want the encoding of "two" to have more 1s than that of "one", that of "three" more still et cetera, forcing you to adopt the silly $1\mapsto 1, 2\mapsto 11, 3\mapsto 111, 4\mapsto 1111$ etc. I rather suspect that your reason for including item 1 is to avoid the use of Gray codes and the like. Why is that? You need to also be more specific about ties. Commented Oct 6, 2018 at 9:45
• @JyrkiLahtonen: I added the context and clarification for the problem definition. Please make changes if my presentation is confusing.
– Taha
Commented Oct 6, 2018 at 19:07
• Hmm. Won't the usual base two presentation of integers work if we use $w=(1,2,4,8,\ldots,2^{d-1})$? Commented Oct 6, 2018 at 19:12
• The problem happens with $3 = [0, 1, 1]$ and $4 = [1, 0, 0]$. When we learn $\mathbf{w}$, the algorithm needs to understand the relationship between coordinates (the leftmost position should have twice the value of the position to its right). Your previous solution is a better one though.
– Taha
Commented Oct 6, 2018 at 19:18
• Also, $\mathbf{w}$ should be learned from the data. We do not know the true numerical value of the ordinal numbers in the dataset and the prediction task.
– Taha
Commented Oct 6, 2018 at 21:00