Golomb-Rice (from flac-dev)

[privatezero]

Posted on 2017-06-06 in [flac-dev]:

Andrew,

I think it is neither Rice Coding nor Exponential Golomb Coding. The one used in FLAC is Golomb-Rice coding, which is almost optimal for the Laplace (exponential) statistical distribution of residuals after modelling.

Best regards,

Federico

[privatezero]

I must confess I don't know enough about the encoding specifics confirm this myself. Is anyone who is more familiar with the guts of the spec able to chime in on this?

[dericed]

ping @bumblebritches57

[retokromer]

I can review the information about the used codings, but only after Bangkok and after Bologna.

[MarcusJohnson91]

There's a whole family of Rice codes, there's regular Rice (aka Unary), modified regular Rice (Truncated Rice), Exponential-Golomb. (that I'm familiar with anyway, there's probably a bunch more)

So, it's called Exponential-Golomb in AVC/H.264 documentation, I thought this was the universal term, but I guess not?

Anyway, regular Rice (Unary) coding works by writing X number of bits (0 or 1, I don't remember which is more common, not that it really matters), then writing a stop bit (the opposite, if the regular bits are 0, this is 1, or vice versa).

Truncated Rice aka Truncated Unary coding, works by doing the same, except there is no stop bit (EDIT the stop bit is still there, it's just also counted as part of the code length, unlike in Rice; and as a result, you subtract 1 from the number you're trying to write)

Exponential-Rice coding uses regular Rice (aka Unary, and not the truncated variant) to write how many bits there are in the number.

So if you want to write the number 7, it'll write 3 binary digits as length codes (because the number 7 takes up 3 bits), then it'll write a "stop bit" (except here it's used to separate the sections of the code), then the regular binary digits of the number, in this case, 111.

For a total code of 0001111. (in this case, they (being Rice vs Exp-Golomb) take up the same number of bits, but for a larger number, say 12 bits, it's a fuck ton more efficient than writing 4096 + 1 + 12 bits)

As for what "Golomb-Rice coding" is, It sounds incredibly generic so I'm worried I'll stumble upon the wrong variant, but I'll look into it.

Is this the variant they're talking about, or is it just ddg getting confused because the name is too vague?

https://en.wikipedia.org/wiki/Golomb_coding

[retokromer]

Thank you very much, @bumblebritches57! I don’t longer need to re-delve into my 1990s teachings!

[MarcusJohnson91]

Does anyone have a link to the thread? not sure if I'm subbed to the flac mailing list anymore.

Either way "Golomb-Rice" is just too generic to be of use, it's just the names of the inventors, David A. Rice, and Solomon W. Golomb.

That's like saying "What OS do you use?" "I use the "Jobs-Gates" OS!"

Edit: I emailed him from the thread on the mailing list with a link to this thread.

[retokromer]

Federico’s post is at: http://lists.xiph.org/pipermail/flac-dev/2017-June/006286.html

[fweimer]

I'm not familiar with these encodings, but when writing a decoder, I found the specification has the following gaps:

• The numbers are signed (the default in the specification is unsigned numbers).
• A signed-magnitude encoding is used. The sign bit is in the LSB of the decoded unsigned value (not the MSB, not two's complement as in the rest of the specification).
• The separator bit is 1, that is, the unary prefix uses 0 bits.

[ktmf01]

I see that quite some time ago, the name of the residual coding methods was changed from rice to exponential Golomb. I looked into what exponential Golomb is, and it is not what FLAC is using. Also the explanation currently in the spec is not what FLAC is using.

FLAC uses a coding method in which the residual is first split up into partitions. Each of these partitions get a parameter from 0 to 14 for the first coding method or 0 to 30 for the second method. Each (signed) residual sample is then 'folded' into an unsigned representation: if the residual sample is positive, it is doubled, if the sample is negative, it is doubled and has 1 subtracted from it. This folded residual is then divided by 2^parameter. The floored result of this division is coded unary, the remainder follows in parameter number of bits.

So, if a partition has a parameter of 3, the residuals are coded as follows

residual	folded residual	quotient	remainder	coded residual
0	0	0	0	0b1000
-1	1	0	1	0b1001
1	2	0	2	0b1010
2	4	0	4	0b1100
-2	3	0	5	0b1011
-4	7	0	7	0b1111
4	8	1	0	0b01000
-8	15	1	7	0b01111
8	16	2	0	0b001000
34	68	8	4	0b000000001100

Wikipedia calls this simply Rice coding or Rice-Golomb coding, as does libFLAC. It is pretty much the 'simple algorithm' described on the Wikipedia page on Golomb coding. Also, see this bit of code. As can be seen, the total number of bits is 0 + parameter + residual << parameter. In other words, the remainder is stored directly (in parameter bits), while the quotient (residual << parameter) is stored unary.

If this name is not appropriate, perhaps one should come up with a better name, but as I understand it, this is not Exponential Golomb coding.

[JeromeMartinez]

Thanks. So I think it is safer to go back to the old naming.
Would you mind to send a PR with the change as well as more details about how to decode (the spec is about decoding, so it should describe how to decode these bits)?

[ktmf01]

Yes, I will expand that part. Still, if 'rice code' is too general, I haven't been able to come up with a better name yet.

[wader]

Hi, when implemented https://github.com/wader/flac.tcl i was confused by the unsigned "folding" for a while. I think it is essentially https://en.wikipedia.org/wiki/Variable-length_quantity#Zigzag_encoding or?

[ktmf01]

Thanks for the tip @wader, I didn't know there was a name for this representation. I've just added it to PR #96 and #101. As you have first hand experience, would you mind looking at these PRs to see whether something is still missing?

[wader]

👍 Sure no problem

[ktmf01]

As both #122 and #101 have been merged, I'm closing this issue.