NAME

Data::BitStream::Code::Golomb - A Role implementing Golomb codes

VERSION

version 0.08

DESCRIPTION

A role written for Data::BitStream that provides get and set methods for Golomb codes. The role applies to a stream object.

Beware that with the default unary coding for the quotient, these codes can become extraordinarily long for values much larger than m.

METHODS

Provided Object Methods

put_golomb($m, $value)

put_golomb($m, @values)

Insert one or more values as Golomb codes with parameter m. Returns 1.

put_golomb(sub { ... }, $m, @values)

Insert one or more values as Golomb codes using the user provided subroutine instead of the traditional Unary code for the base. For example, the common Gamma-Golomb encoding can be performed using the sub:

  sub { shift->put_gamma(@_); }

get_golomb($m)

get_golomb($m, $count)

Decode one or more Golomb codes from the stream. If count is omitted, one value will be read. If count is negative, values will be read until the end of the stream is reached. In scalar context it returns the last code read; in array context it returns an array of all codes read.

get_golomb(sub { ... }, $m)

Similar to the regular get method except using the user provided subroutine instead of unary encoding the base. For example:

  sub { shift->get_gamma(@_); }

Parameters

The parameter m must be an integer greater than or equal to 1.

The quotient of value / m is encoded using unary (or via the user supplied subroutine), followed by the remainder in truncated binary form.

Note: if m == 1 then the result will be coded purely using unary (or the supplied sub) coding.

Note: if m is a power of 2 (m = 2^k for some non-negative integer k), then the result is equal to the simpler Rice(k) code, where the operations devolve into a shift and mask.

For a general array of integers, the value of m leading to the smallest sum of codes is approximately 0.69 * the average of the values. (citation needed)

Golomb coding is often preceeded by a step that adapts the parameter to the data seen so far.

Required Methods

read

write

get_unary

put_unary

These methods are required for the role.

SEE ALSO

Data::BitStream::Code::Rice

Data::BitStream::Code::GammaGolomb

Data::BitStream::Code::ExponentialGolomb

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

S.W. Golomb, "Run-length encodings", IEEE Transactions on Information Theory, vol 12, no 3, pp 399-401, 1966.

R.F. Rice and R. Plaunt, "Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data", IEEE Transactions on Communications, vol 16, no 9, pp 889-897, Dec. 1971.

AUTHORS

Dana Jacobsen <dana@acm.org>

COPYRIGHT

Copyright 2011-2012 by Dana Jacobsen <dana@acm.org>

This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.