<p>I'm investigating a possible self-synchronizing, or it seems &quot;prefix-free&quot; is the term I really mean, binary encoding for use in a variable length exponent in a floating point number format like Posits.</p>
<p>Posits use something like Elias Gamma encoding <a href="https://en.wikipedia.org/wiki/Elias_gamma_coding" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Elias_gamma_coding</a>, prefixing the value by consecutive <em>regime</em> bits whose count determine the length of the exponent value that follows in normal binary encoding.</p>
<p>Imagining there to be something more space-efficient, I've come across Fibonacci coding <a href="https://en.wikipedia.org/wiki/Fibonacci_coding" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Fibonacci_coding</a>. These bit patterns are terminated by the bit pattern &quot;11&quot; and it looks more space-efficient than what Posits use.</p>
<p>I'm wondering if this is likely to be true.</p>
<p>The range that need to be encoded are exponents of floating point values that are likely to be used in software. This may be different for different bit width of floating point types.</p>
<p>More details about what I'm talking about:</p>
<p><a href="https://posithub.org/docs/posit_standard-2.pdf" rel="nofollow noreferrer">Posits</a> are an alternate encoding to the IEEE binary floating point number format. That IEEE stardard is like <code>|s|eeeee|ffffffffff|</code> where the number of exponent bits &quot;e&quot; is fixed and encoded as a normal binary integer. Posit format uses, effectively <code>|s|gggggg|fffffffff|</code> where g bits are variable length and like an Elias gamma encoding.</p>
<p>Diving in further (and forgetting about the sign bit here), those <code>g</code> bits are made up of some count of 0's, then a sentinel 1, then that count of subsequent bits as normal binary integer giving the overall value of the exponent. This is as described in <a href="https://en.wikipedia.org/wiki/Elias_gamma_coding" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Elias_gamma_coding</a>.</p>
<p>The clever trick is that <code>g</code> bits like <code>0001|100</code> is in fact exponent -4, and like <code>1110|100</code> where 3 1's are counted instead of 3 0's is exponent +4. Indicating sign by counting 1's vs 0's isn't the only clever part: Taking the bit patterns of the entire encoded floating point value F(bits) and reinterpreting as a binary integer B(bits), when F(x) &gt; F(y), B(x) &gt; B(y).</p>
<p>(I was originally asking if there was an alternative to Fibonacci coding but retained Posits current ordering feature, though I was set straight that this didn't make sense. The ordering is entirely down to leading 0's or 1's doing double (triple?) duty to ensure this ordering. I see now that no other variable-length encoding I can imagine for these exponent bits that also self-describe their length would also have this property)</p>
<p>So I'm hoping to verify my suspicions that an alternate form of Posits that used Fibonacci encoded exponents instead will, to any significance, represent more values accurately for various bit lengths (of the overall floating point value).</p>
<p>Ways I can think of that I may be wrong:</p>
<p>a) My proposed alternate form would target use cases where quickly calculating the order of two values wasn't important, but perhaps there aren't many such problem domains.</p>
<p>b) It seems unavoidable that an extra bit would be needed for the sign of the exponent, this makes it not completely a normal comparison of Fibonacci encoding efficiency vs. Elias gamma encoding. And I'm of no illusions that I didn't miss another detail that makes it even less of a simple comparison.</p>
<p><a href="https://cstheory.stackexchange.com/users/6959/emil-je%c5%99%c3%a1bek">Emil Jeřábek</a> noted in a comment (to the previous iteration of this question) &quot;the Elias coding of an -bit number takes about 2 bits, whereas the Fibonacci coding about /log2 bits, which is smaller (for large enough )&quot;. This issue doesn't deal with &quot;large enough &quot; though but most often small  up to, well, still relatively small .</p>
<p>I may experiment with the <a href="https://gitlab.com/cerlane/SoftPosit" rel="nofollow noreferrer">SoftPosit library</a> and maybe some tests it might have, hack it to use my scheme and try to answer my own question.</p>
<p>(Thanks for all the help to refine this question into something that might end up being interesting)</p>

CC BY-SA 4.0
2024-06-19T10:01:45.263Z
Well, that's because the Fibonacci "digits" in the coding described on Wikipedia are increasing rather than decreasing left-to-right. So just reverse the encoding string (except the final 11). This will make increasing bit patterns of the same length; it's not clear to me how you want to compare them if they have different lengths.
Emil Jeřábek
CC BY-SA 4.0
2024-06-19T10:09:08.667Z
It's actually not clear to me how is any version of this encoding "self-synchronizing". Did you just mean "prefix-free"?
Emil Jeřábek
CC BY-SA 4.0
2024-06-19T12:15:02.900Z
@EmilJeřábek: In this coding, whenever you come across two 1's in a row, you know this is the end of an encoded integer, so the decoding procedure will synchronize at this point.
Peter Shor 
CC BY-SA 4.0
2024-06-19T12:38:09.010Z
As far as I can see, the Elias coding of an $n$-bit number takes about $2n$ bits, whereas the Fibonacci coding about $n/\log_2\phi$ bits, which is smaller (for large enough $n$).
Emil Jeřábek
CC BY-SA 4.0
2024-06-19T12:45:55.300Z
Re [the previous comment](https://cstheory.stackexchange.com/questions/54417/is-there-a-self-synchronizing-binary-coding-like-fibonacci-coding-but-ordered-we#comment121305_54417): all right, though this is not the definition of "self-synchronising" as given on Wikipedia (a portion of one code word, or an overlapped portion of any two adjacent code words, is not a valid code word). Clearly, there are valid Fibonacci codewords that are proper substrings of other Fibonacci codewords.
Emil Jeřábek
CC BY-SA 4.0
2024-06-20T13:18:36.307Z
Also, the Elias gamma coding is not self-synchronizing under *either* of the two definitions.
Emil Jeřábek
CC BY-SA 4.0
2024-06-26T04:11:26.090Z
Maybe I do mean prefix-free, I'm not too familiar with all the nomenclature. With Fibonacci encodings only ending in double 1-bits, one cannot be a substring of another. I'll edit the Q to further explain the problem. @EmilJeřábek yes, I see how this doesn't make sense now, of course 6 compared to 8 encoded (plus whatever followed the encoded prefix) would not be comparing  "010011.." to "100011" but  "10011..." to "100011..."
Pierre Houston
CC BY-SA 4.0
2024-06-27T06:34:17.603Z
Please don't use "EDIT:", include multiple versions of the question/title, or list meta-comments about what has changed.  Instead, just revise the question to what it should be, and so it is self-contained, so it reads well for someone who encounters it for the first time.  We are looking to build an archive of knowledge for posterity, that will be useful to others in the future.  We have revision history which keeps a copy of all older versions that anyone can refer to if they wish.  See https://cs.meta.stackexchange.com/q/657/755.
D.W.
CC BY-SA 4.0
2024-06-27T06:35:17.133Z
What exactly is your question?  I'm having a hard time finding the question.  I see that there is a question in the previous version, but apparently that is no longer relevant.  After that, there is no question, merely a lot of declarative sentences.  Can you make this more concise and get to the point and state the question explicitly, and remove all the material that is now redundant/moot/no longer needed?
D.W.
<encoding>
Can Elias Gamma encoded (ish) exponents used in Posit format binary floating point numbers be improved with Fibonacci encoded exponents instead?
Pierre Houston
# Can Elias Gamma encoded (ish) exponents used in Posit format binary floating point numbers be improved with Fibonacci encoded exponents instead?

(Asked by: username_0 on 2024-06-19)

I'm investigating a possible self-synchronizing, or it seems "prefix-free" is the term I really mean, binary encoding for use in a variable length exponent in a floating point number format like Posits.

Posits use something like Elias Gamma encoding <https://en.wikipedia.org/wiki/Elias_gamma_coding>, prefixing the value by consecutive *regime* bits whose count determine the length of the exponent value that follows in normal binary encoding.

Imagining there to be something more space-efficient, I've come across Fibonacci coding <https://en.wikipedia.org/wiki/Fibonacci_coding>. These bit patterns are terminated by the bit pattern "11" and it looks more space-efficient than what Posits use.

I'm wondering if this is likely to be true.

The range that need to be encoded are exponents of floating point values that are likely to be used in software. This may be different for different bit width of floating point types.

More details about what I'm talking about:

[Posits](https://posithub.org/docs/posit_standard-2.pdf) are an alternate encoding to the IEEE binary floating point number format. That IEEE stardard is like `|s|eeeee|ffffffffff|` where the number of exponent bits "e" is fixed and encoded as a normal binary integer. Posit format uses, effectively `|s|gggggg|fffffffff|` where g bits are variable length and like an Elias gamma encoding.

Diving in further (and forgetting about the sign bit here), those `g` bits are made up of some count of 0's, then a sentinel 1, then that count of subsequent bits as normal binary integer giving the overall value of the exponent. This is as described in <https://en.wikipedia.org/wiki/Elias_gamma_coding>.

The clever trick is that `g` bits like `0001|100` is in fact exponent -4, and like `1110|100` where 3 1's are counted instead of 3 0's is exponent +4. Indicating sign by counting 1's vs 0's isn't the only clever part: Taking the bit patterns of the entire encoded floating point value F(bits) and reinterpreting as a binary integer B(bits), when F(x) > F(y), B(x) > B(y).

(I was originally asking if there was an alternative to Fibonacci coding but retained Posits current ordering feature, though I was set straight that this didn't make sense. The ordering is entirely down to leading 0's or 1's doing double (triple?) duty to ensure this ordering. I see now that no other variable-length encoding I can imagine for these exponent bits that also self-describe their length would also have this property)

So I'm hoping to verify my suspicions that an alternate form of Posits that used Fibonacci encoded exponents instead will, to any significance, represent more values accurately for various bit lengths (of the overall floating point value).

Ways I can think of that I may be wrong:

a) My proposed alternate form would target use cases where quickly calculating the order of two values wasn't important, but perhaps there aren't many such problem domains.

b) It seems unavoidable that an extra bit would be needed for the sign of the exponent, this makes it not completely a normal comparison of Fibonacci encoding efficiency vs. Elias gamma encoding. And I'm of no illusions that I didn't miss another detail that makes it even less of a simple comparison.

[username_1](https://cstheory.stackexchange.com/users/6959/emil-je%c5%99%c3%a1bek) noted in a comment (to the previous iteration of this question) "the Elias coding of an -bit number takes about 2 bits, whereas the Fibonacci coding about /log2 bits, which is smaller (for large enough )". This issue doesn't deal with "large enough " though but most often small up to, well, still relatively small .

I may experiment with the [SoftPosit library](https://gitlab.com/cerlane/SoftPosit) and maybe some tests it might have, hack it to use my scheme and try to answer my own question.

(Thanks for all the help to refine this question into something that might end up being interesting)

**Tags:** encoding

> **Comments:**
> **username_1**: Well, that's because the Fibonacci "digits" in the coding described on Wikipedia are increasing rather than decreasing left-to-right. So just reverse the encoding string (except the final 11). This will make increasing bit patterns of the same length; it's not clear to me how you want to compare them if they have different lengths.  
> **username_1**: It's actually not clear to me how is any version of this encoding "self-synchronizing". Did you just mean "prefix-free"?  
> **username_2**: @EmilJeřábek: In this coding, whenever you come across two 1's in a row, you know this is the end of an encoded integer, so the decoding procedure will synchronize at this point.  
> **username_1**: As far as I can see, the Elias coding of an $n$-bit number takes about $2n$ bits, whereas the Fibonacci coding about $n/\log_2\phi$ bits, which is smaller (for large enough $n$).  
> **username_1**: Re [the previous comment](https://cstheory.stackexchange.com/questions/54417/is-there-a-self-synchronizing-binary-coding-like-fibonacci-coding-but-ordered-we#comment121305_54417): all right, though this is not the definition of "self-synchronising" as given on Wikipedia (a portion of one code word, or an overlapped portion of any two adjacent code words, is not a valid code word). Clearly, there are valid Fibonacci codewords that are proper substrings of other Fibonacci codewords.  
> **username_1**: Also, the Elias gamma coding is not self-synchronizing under *either* of the two definitions.  
> **username_0**: Maybe I do mean prefix-free, I'm not too familiar with all the nomenclature. With Fibonacci encodings only ending in double 1-bits, one cannot be a substring of another. I'll edit the Q to further explain the problem. @EmilJeřábek yes, I see how this doesn't make sense now, of course 6 compared to 8 encoded (plus whatever followed the encoded prefix) would not be comparing  "010011.." to "100011" but  "10011..." to "100011..."  
> **username_3**: Please don't use "EDIT:", include multiple versions of the question/title, or list meta-comments about what has changed.  Instead, just revise the question to what it should be, and so it is self-contained, so it reads well for someone who encounters it for the first time.  We are looking to build an archive of knowledge for posterity, that will be useful to others in the future.  We have revision history which keeps a copy of all older versions that anyone can refer to if they wish.  See https://cs.meta.stackexchange.com/q/657/755.  
> **username_3**: What exactly is your question?  I'm having a hard time finding the question.  I see that there is a question in the previous version, but apparently that is no longer relevant.  After that, there is no question, merely a lot of declarative sentences.  Can you make this more concise and get to the point and state the question explicitly, and remove all the material that is now redundant/moot/no longer needed?  

---

## 0 answers

