Golomb coding: Difference between revisions

Revision as of 16:45, 11 July 2021

Revision as of 23:04, 11 July 2021

Line 26:

:<math>r = x - qM</math>.

[[File:GolombCodeRedundancy.svg|thumb|upright 1.5|This image shows the redundancy, in bits, of the Golomb code, when {{mvar|M}} is chosen optimally for {{math| (1 − ''p''(0) &ge; 0.5}}]]

Both {{mvar|q}} and {{mvar|r}} will be encoded using variable numbers of bits – {{mvar|q}} by a unary code, and {{mvar|r}} by {{mvar|b}} bits for Rice code, or a choice between {{mvar|b}} and {{mvar|b}}+1 bits for Golomb code (i.e. {{mvar|M}} is not a power of 2). Let <math>b = \lfloor\log_2(M)\rfloor</math>. If <math>r < 2^{b+1} - M</math>, then use {{mvar|b}} bits to encode {{mvar|r}}; otherwise, use {{mvar|b}}+1 bits to encode {{mvar|r}}. Clearly, <math>b=\log_2(M)</math> if {{mvar|M}} is a power of 2 and we can encode all values of {{mvar|r}} with {{mvar|b}} bits.