Context-Adaptive Binary Arithmetic Coding | Hacker News Reader

Context-Adaptive Binary Arithmetic Coding

bertolami.com

36 pointswholenote6 comments

As exposition, I think this piece falls into the trap of explaining the specifics of CABAC as if it was a concrete object like an internal combustion engine. Arithmetic coding is not difficult to visualize, as the well-known Dasher applet shows, and there's no problem with giving a very general and abstract explanation rather than working through a specific implementation. The question of the size of the alphabet is orthogonal to the topic of context adaptation, and I think CA could be clearly introduced in a generic setting before picking an alphabet size. Dasher uses the actual alphabet (well, a character set) which makes the predictive aspect of context adaptation obvious to anyone who has played with Markov chains.

Actually the Wikipedia page for CABAC seems a bit confused and fanboyish on some points. Maybe I am missing something, but "It encodes binary symbols, which keeps the complexity low and allows probability modelling for more frequently used bits of any symbol" sounds like garbage to me...

In case anyone isn't aware of Dasher:

http://www.inference.phy.cam.ac.uk/dasher/

As a keyboard on your Android device:

https://play.google.com/store/apps/details?id=dasher.android

Are there any known patent issues with CABAC?

Yes, CABAC and techniques surrounding it are heavily patented. For this reason, both Opus and Daala use (different) range coding schemes instead, which can also deliver higher performance.

One problem with CABAC is that it is highly serial, and ends up being directly clock rate limited in a lot of hardware engines.

https://www.google.com/patents/US20050074176

The general concept of arithmetic coding isn't patented. CABAC has some notable performance issues when done in software; IIRC they messed up benchmarking different algorithms, so instead of a multiply in one stage there's an array lookup. Unnecessary memory accesses will kill you.

There are many patents around. Some of them are already expired though.

For instance the arithmetic coding patents needed for jpeg are expired, yet almost no browser supports it: https://bugzilla.mozilla.org/show_bug.cgi?id=680385

Reply on news.ycombinator.com