Is there a binary representation where the encoding distance grows with the arithmetic distance? I need to binarily encode/decode small integers (around 10 bits), in such a way that the hamming distance of the encoded number grows monotonically with the (absolute value) arithmetic distance of the numbers.
Edit: the monotonicity doesn't needs to be absolute. There is probably a cost to pay breaking it, but the cost should be as low as possible. Is preferable to reduce the hamming distance at short scales, and if unavoidable, break it at larger scales.
For example:
The question is: Is there already such an encoding (better if it has error correction)?
I need to use it in python, so if there is already a python library to do the encode/decode, it would be perfect.
The &quot;monotonically growing&quot; requirement is a loose requirement. It is not strictly necessary. It just is convenient that the hamming distance reflects the arithmetic distance in some way.
The hamming distance can be replaced wit some other measure of encoding distance, like Jaccard distance.
The requirement is that close integers share most of their binary encoding, and still there is error correction.
You can get some kind of tradeoff between unary and binary.
Start by choosing some integer $k$ and set $w=2^k-1$.
Then write $x$ as $x=r+w+w+\ldots+w$, where $r$ is the remainder of $x$ when divided by $w$. Let $\bar{a}$ denote the binary encoding of $a$. You can encode $x$ as $e(x) = \bar{r}\bar{w}\bar{w}\ldots\bar{w}$.
This encoding is of length $k\times x/w$ and you have $d_{hamming}(x,y)$ which should be in the range from $\frac{1}{w}(|x-y|-1)$ to $\frac{k}{w}(|x-y|+1)$ (give or take some rounding errors on my part).
The smaller $k$ you choose, the better correspondence between Hamming distance and absolute difference, but the longer the encoding.
You can also use Gray code instead of binary to squeeze a bit more out of it.