Compressions Notes

• Shannon's Entropy: H = - sum( p_i log p_i )
  • his 1948 paper
  • Summary of Shannon's ideas
  • jim's Perl Entropy Code

• lossless compression - the basics
  • summary of Huffman and LZ coding, with animations of each algorithm
  • another huffman tutorial
  • another LZ tutorial
  • One more LZW tutorial, from Dr. Dobbs Journal, with C code
  • Ross William's LZRW Crypt
    - history, patent issues, and code for LZW-like stuff, by the author of several interesting versions
  • arimetic coding description and tar.gz source code

• JPEG - a lossy image compression algorithm
  • Steps:
    1. break into 8x8 pixel blocks
    2. convert RGB to YUV color (with fewer bits in UV; some loss here)
    3. discrete cosine transform (DCT, like FFT)
    4. round off fourier components (most of loss is here)
    5. compress with Huffman (or arithmetic) coding
    6. write to file in SPIFF format
  • paper describing the details

• MP3
  • not yet

• See google directory compression

• this directory