Dense coding-a fast alternative to arithmetic coding

With dense coding a new method for minimum redundancy coding is introduced. An analysis of arithmetic coding shows, that it is essentially identical to an encoding of discrete intervals. Interval coding is introduced, which encodes symbols directly by encoding the corresponding discrete intervals. Dense coding is an enhanced variant of interval coding, where redundancies are mostly removed with a new technique called conditional coding. Conditional coding is at most 0.086071... bits per encoding step (0.057304... bits in average) longer than optimal encoding. Dense coding uses conditional coding twice and is therefore 0.114608... bits per encoding step worse than the theoretical limit (unlimited precision arithmetic coding). Dense coding is a lot faster than arithmetic coding or Huffman coding and achieves nearly the same compact code as arithmetic coding.