[flac-dev] flac-dev Digest, Vol 149, Issue 5

[Federico Miyara]

Marcus,

The code used in flac is a Golomb-Rice code. As flac codes residuals 
(errors) after estimating the signal with a suitable model obtained 
during coding, the code is chosen because it requires less bits for 
smaller residuals and more bits for larger residuals.

This works because smaller residuals are far more frequent, so even if 
large residuals require many bits, they are so infrequent that this is 
not a problem.

How does Golomb-rice work?

The residuals are divided by a suitable power of two (generally small, 
like 8 or so). The integer quotient is represented in unary code, this 
is, a number of zeros equal to the number to be represented followed bya 
a 1 as separator, and the remainder in ordinary binary code.

For instance, if you have to represent decimal 7 you would do this:

integer quotient 7/8 = 0
remainder = 7

So the GR code would be 1111. The first 1 is the separator (in this case 
there are zero 0's) and the remaining bits are 111 (decimal 7)

If you have to represent 45, a much more infrequent residual,

integer quotient 45/7 = 6
remaider = 3

So the GR code would be 0000001011. The first six 0's represent 6, the 
following 1 is the separator and 011 represents decimal 3

The idea is that most residuals will be very small if the model is 
accurate, so they will bhe representable with only 4 bits (in this 
example). Of course, now and then you may have a residual as large as 
32767 (full scale for 16 bit), wich would require 8191 zeros (integer 
quotient of 32767/4), one 1 (separator) and three additional bits. This 
is very inefficient, but the odds that this happens are extremely low 
(the statistical distribution is Laplatian or absolute value 
exponential, so large values are very unlñikely.

Regards,

Federico Miyara


On 23/05/2017 10:40, Marcus Johnson wrote:
> ​Can you guys clarify that by Rice you don't mean unary coding, but 
> exponential golomb coding?
>
> that issue has confused me before, and probably others.​
>
>
>
> _______________________________________________
> flac-dev mailing list
> flac-dev at xiph.org
> http://lists.xiph.org/mailman/listinfo/flac-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.xiph.org/pipermail/flac-dev/attachments/20170523/75869ccc/attachment.html>