What makes Rice coding a special case?

Its parameter m equals 2 to an integer power, so the remainder has a fixed binary width.

Can Golomb coding represent zero?

Yes. Zero has quotient and remainder zero under the chosen parameter.

Is one parameter best for every dataset?

No. It should reflect the magnitude distribution or follow a compatible adaptive rule.

AI Glossary / MLOps and deployment / Intermediate

Golomb coding

Definition

Golomb coding is a family of lossless variable-length codes for nonnegative integers. It divides each integer by a chosen positive parameter, codes the quotient in unary and codes the remainder in a compact binary form. With an appropriate parameter, it is especially useful for distributions that favor small values and decrease approximately geometrically.

What it means

The parameter controls how much information goes into the unary quotient and how much goes into the remainder. A small parameter gives short codes to very small numbers but makes large quotients expensive. A larger parameter reduces those quotients while increasing the remainder's width. The best choice depends on the data distribution. Rice coding is the special case where the parameter is a power of two, making the division and remainder operations particularly simple.

How it works

For nonnegative n and parameter m, calculate q = floor(n/m) and r = n mod m. Using the unary convention here, q is represented by q ones followed by a zero. If m is a power of two, the remainder uses a fixed number of bits. Otherwise a truncated-binary code assigns shorter representations to some remainders and longer ones to others. The decoder reads the quotient, decodes the remainder with the same m and returns n = qm + r. A format must communicate or reproducibly derive m.

Three practical examples

A lossless image coder represents small prediction-related distances using a parameter adapted to local statistics.
A signal compressor maps signed residuals to nonnegative integers, then uses Golomb or Rice codes for the mapped values.
A search-index experiment compares Golomb-coded positive gaps with other integer representations using the observed gap distribution.

Think of it this way

Think of describing an amount as several full boxes plus the items left over. The box size is m, the number of full boxes is q and the remainder is r. The analogy explains division, but it does not by itself explain compression: savings come from choosing a box size and bit codes that match the frequency of the amounts.

Worked example

Encode n = 13 with m = 5. Division gives q = 2 and r = 3. The unary quotient is 110. For the truncated-binary remainder, let b = ceil(log2(5)) = 3 and t = 2³ − 5 = 3. Remainders below 3 use two bits; other remainders encode r + t in three bits. Since r = 3, encode 6 as 110. The complete code is 110110. To decode, the initial 110 gives q = 2. The remainder begins with two bits 11, whose value 3 is not below t, so read one more bit to obtain 6 and subtract t to recover r = 3. Then 2×5 + 3 = 13.

Illustrative case study

Fictional case: Beech Sensors compresses small prediction residuals from a monitoring stream. A parameter selected during quiet operation performs poorly during startup, when larger residuals are common. The team compares a fixed parameter with a documented adaptive rule and checks that decoder updates match encoder updates exactly. It reports size across both conditions and includes the cost of any parameter signaling. This fictional case illustrates distribution sensitivity rather than claiming a particular operational saving.

Common misconceptions and mistakes

Do not assume the code chooses its own parameter automatically. Parameter selection is an additional design decision. Do not interchange unary conventions without updating the decoder. Signed values need a specified mapping, and a mapping that favors small magnitudes changes the distribution seen by the coder. Golomb coding is also distinct from Exp-Golomb coding, despite the shared name. For values far larger than m, a unary quotient can become very long, so bounded implementations must handle extremes deliberately.

Business use

Businesses encounter Golomb codes inside specialist media, telemetry and storage systems. Their appeal is a compact representation with relatively simple operations when values follow a suitable distribution. Compare encoded size, decoding speed and worst-case behavior on representative data. Include the cost of parameter updates and any restart points. For AI input pipelines, verify exact residual reconstruction and the inverse signed mapping so compression does not silently alter measurements.

Check your understanding

With m = 4 and n = 9, what quotient and remainder are coded?

Answer: q = 2 and r = 1. Under the stated unary convention and a two-bit remainder, the code is 110 followed by 01, or 11001. This is also a Rice code because 4 is a power of two.

Related terms

Unary code
Entropy coding
Rice coding
truncated binary code
geometric distribution
prediction residual
Exp-Golomb coding

Learn next

Encode values 0 through 15 with m = 3, 4 and 5, recording code lengths under one stated convention. Weight those lengths by a small observed histogram. The resulting average makes the parameter trade-off concrete and avoids choosing m from a single convenient example.

Sources

Primary implementation research reference: Howard and Vitter, Fast and Efficient Lossless Image Compression, including its Golomb and Rice coding discussion, https://www.ittc.ku.edu/~jsv/Papers/HoV93.fitech.pdf . Primary PDF opened and coding section consulted; full convention-specific and editorial review remain pending. The worked remainder uses explicitly specified truncated-binary ordering.

Previous: Goldfeld - Quandt test Next: Gomory-Hu Tree