2
$\begingroup$

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:
rough description

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 "monotonically growing" 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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Represent the number $n$ with the value $\sum_{i=0}^{n} 2^i$. By doing this, you will get that the hamming distance is exactly the arithmetic distance. However I don't recommend encoding integers in any other way except the usual encoding that the computer does, since its the most efficient one. $\endgroup$
    – nir shahar
    Mar 4, 2021 at 21:56
  • $\begingroup$ @nir shahar The usual encoding creates large differences in encoding between neighbor numbers, so is not efficient by that criteria. $\endgroup$
    – Lewec
    Mar 4, 2021 at 22:31
  • $\begingroup$ Thats right. However any other way to encode numbers will be either inefficient in terms of storage, or inefficient in computational time for operators. What are you trying to use this for? $\endgroup$
    – nir shahar
    Mar 4, 2021 at 23:31
  • $\begingroup$ My last claim can actually be proven: for numbers with $n$ bits in their representation, we start with the encoding of $0$ and to reach any $x$ we need to do at most $n$ flips. If we assume that the hamming distance relates linearly with the arithmetic distance, then since the hammin distance is at most $n$, the value of any $x$ would not exceed $cn$, meaning that our representation is really inefficient. $\endgroup$
    – nir shahar
    Mar 4, 2021 at 23:37
  • 1
    $\begingroup$ Sounds like an XY problem. What is the problem that you actually want to solve? $\endgroup$
    – gnasher729
    Mar 5, 2021 at 7:45

4 Answers 4

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You mean pasting binary or gray code to an unary? (You forgot to explain how many w are there). I marked your post as the answer, because it is the closer answer to what I asked. $\endgroup$
    – Lewec
    Mar 6, 2021 at 18:54
  • $\begingroup$ No I mean what I wrote, that is, "chuncks" of binary code arranged in a unary-type way (their sum represents the number, similarly to unary). The number of $w$'s is $\lfloor x/w \rfloor$. $\endgroup$
    – Tassle
    Mar 6, 2021 at 19:11
1
$\begingroup$

Unary encoding meets all of your stated requirements, with $c=1$. This will work poorly for large integers, because the encoding grows very long, but for small integers, it is probably fine.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That's the trivial solution, but the point of encoding is to economize some bits. Unfortunately, I don't know a metric to decide between economy and hamming distances. That's why I only ask about hamming distance. $\endgroup$
    – Lewec
    Mar 5, 2021 at 18:34
  • $\begingroup$ @Lewec, like I wrote in my answer, it meets all of the requirements stated in the question. The question doesn't state any requirement to economize some bits. If this answer is not satisfactory, I encourage you to edit the question to clarify what you are asking and to be explicit about all of your requirements. $\endgroup$
    – D.W. ♦
    Mar 5, 2021 at 18:36
1
$\begingroup$

Here’s what you can try: Start with 0 encoded as all bits zero. To encode k+1, determine which is the highest bit you would set to change from k to k+1 in pure binary, and change only that bit. So the number of bits changing when you add 1 is at most 1.

Numbers 0 to 15 are 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That's like gray code, which is an improvement over binary, for small changes, but still has large local extremes for certain $|x-y|$. Ideally, it would be preferable to rarify those jumps, to smooth the hamming distance at different arithmetic distrances, and to distance large jumps as much as possible. $\endgroup$
    – Lewec
    Mar 5, 2021 at 18:25
1
$\begingroup$

Try gray code encoding. It is basically used already in many places and fits your needs.

A link to some python module to start with: link

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.