Arithmetic coding

related topics
{math, number, function}
{system, computer, user}
{rate, high, increase}
{language, word, form}
{law, state, case}

Arithmetic coding is a form of variable-length entropy encoding used in lossless data compression. Normally, a string of characters such as the words "hello there" is represented using a fixed number of bits per character, as in the ASCII code. When a string is converted to arithmetic encoding, frequently used characters will be stored with fewer bits and not-so-frequently occurring characters will be stored with more bits, resulting in fewer bits used in total. Arithmetic coding differs from other forms of entropy encoding such as Huffman coding in that rather than separating the input into component symbols and replacing each with a code, arithmetic coding encodes the entire message into a single number, a fraction n where (0.0 ≤ n < 1.0).

Contents

Implementation details and examples

Equal probabilities

In the simplest case, the probability of each symbol occurring is equal. For example, consider a sequence taken from a set of three symbols, A, B, and C, each equally likely to occur. Simple block encoding would use 2 bits per symbol, which is wasteful: one of the bit variations is never used.

Full article ▸

related documents
SHA hash functions
COBOL
Advanced Encryption Standard
Cyclic redundancy check
Uniform Resource Identifier
Objective Caml
White noise
Database normalization
Exclusive or
Key size
IEEE 754-1985
Aspect-oriented programming
Countable set
Complex analysis
Filter (mathematics)
Modular arithmetic
Ultrafilter
Partition (number theory)
Absolute convergence
Semigroup
Galois theory
XPath 1.0
Natural transformation
Gaussian quadrature
Homological algebra
J (programming language)
Sequence
Elliptic curve
Scope (programming)
Ideal class group