ExtendedSource checked

Rice Coding

Encodes nonnegative integers using quotient-remainder codes with a power-of-two divisor.

Quick Facts

Compact metadata for implementation and discovery.

Rice coding is a Golomb coding variant that is fast to encode and decode when values follow a geometric-like distribution.

quotient-remainder splitunary quotientfixed-width remaindergeometric distribution

Quick facts

Runtime and memory behavior at a glance.

Best

O(log n)

Average

O(log n)

Worst

O(log n)

Space

O(1)

Avoid when the data is already compressed or the format overhead exceeds the savings.
Avoid when a simpler algorithm gives the required result with less setup.

Encodes nonnegative integers using quotient-remainder codes with a power-of-two divisor
Uses quotient-remainder split and unary quotient to guide the work.
Produces encoded stream.

q = ⌊n / 2^k⌋, r = n mod 2^k

q = floor(n / 2^k), r = n mod 2^k

Splits an integer into a unary quotient and k-bit remainder.

1.Prepare the inputs and state needed for Rice Coding.
2.Apply the quotient-remainder split step while the stopping condition has not been met.
3.Update intermediate state and discard invalid candidates.
4.Return encoded stream.

Input: Rice Coding input with a small representative case
Output: Encoded stream
Explanation: Rice Coding applies quotient-remainder split to produce encoded stream.

Define bit packing and stream termination rules before optimizing compression ratio.
Keep the quotient-remainder split step separate enough to test independently.

Encoder and decoder state must evolve in exactly the same order.
Forgetting to check edge cases can make Rice Coding look correct on only ideal inputs.