Arithmetic stream coding using fixed precision registers

Algorithms are presented for encoding and decoding strings of characters as real binary fractions, using registers of fixed precision. The encoding is left to right and does not require blocking. The algorithms have storage requirements <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(N)</tex> and computation time <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(n log₂N)</tex> for string length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</tex> and alphabet size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</tex> .