|
CIPR / RPI Homepage of Amir Said |
|---|
|
|
|
|
This page provides the links to the source code and documentation of a new
implementation of arithmetic coding called FastAC, which was designed with the
following objectives:
|
- Many students and researchers are still using my very first implementation of
arithmetic coding, which is now hopelessly obsolete. The new version is much faster
and convenient (see this graph with speed comparisons).
While it represents the state-of-the-art of arithmetic coding in terms of speed
and efficiency, it also uses C++ features to enable an easy and seamless integration
into compression applications.
- The code can be used as a companion to my Introduction to Arithmetic Coding
[1,2], enabling students to understand how arithmetic coding
works, and some of its implementation problems and solutions. While this may seem
a contradiction with the first objective (truly efficient vs. simple), it
happens that the new AC implementations can actually be both, thanks to the
fact that they basically use… arithmetic, which is supported with great
efficiency and low cost in most current processor (including those for embedded
systems, DSP, etc.) [1,2,3].
- It can be used (I hope) to eliminate some misconceptions
about the computational complexity of arithmetic coding. It is basically the
code used for the experiments in ref. [3], in which we compare the speed of
different types of implementations, and stress the need to consider the
encoder/decoder information throughput as a measure of efficiency and speed.
|
|
|
|
References [2] and [3] are downloadable from the
HP Labs Technical Reports site.
The PDF files are, respectively,
HPL-2004-76 and
HPL-2004-75.
|
- [1] Amir Said,
- "Arithmetic Coding," in Lossless Compression Handbook, (K. Sayood, Ed.),
Academic Press, San Diego, CA, 2003.
- [2] Amir Said,
- Introduction to Arithmetic Coding Theory and Practice,
Hewlett-Packard Laboratories Report,
HPL-2004-76,
Palo Alto, CA, April 2004.
- [3] Amir Said,
- Comparative Analysis of Arithmetic Coding Computational Complexity,
Hewlett-Packard Laboratories Report,
HPL-2004-75,
Palo Alto, CA, April 2004.
|
|
|
|
|
We decided to also make the source code of our C++ implementation of Huffman coding
publicly available for education. Its design objectives and interface (and documentation)
are very similar to FastAC. Thus, except for the lack of binary coders, porting from one
to the other should be quite easy. In addition, they are completely independent, i.e.,
both can be used in the same compression program.
|
|
|
|
 Bio Page- Journal Page
- Compound Images and Video
- Structured Scalable Metaformats
- Virtual Environment Design Automation
- Set Partitioning in Hierarchical Trees
- SPIE/IS&T Conf. on Image and Video Communications and Processing
- Other Links
|
|
 |
|