"Datenkompression 002.ps.gz" - читать интересную книгу автора

Datenkompression Maciej Li'skiewicz, Henning Fernau Wilhelm-Schickard-Institut f"ur Informatik, Universit"at T"ubingen,

Sand 13, D-72076 T"ubingen liskiewi,fernau@informatik.uni-tuebingen.de

1

INHALTSVERZEICHNIS 2 Inhaltsverzeichnis 1 Einleitung 6

1.1 Ein bisschen Informationstheorie . . . . . . . . . . . . . . . . . 6 1.2 Benchmarks f"ur die englische Sprache . . . . . . . . . . . . . 8

2 Grundlegende Codes 10

2.1 Huffman-Algorithmus . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Shannon-Fano Codierung . . . . . . . . . . . . . . . . . . . . 12 2.3 Erweiterte Huffman-Codierung . . . . . . . . . . . . . . . . . 13

3 Arithmetische Codes 15

3.1 Die numerische Repr"asentation . . . . . . . . . . . . . . . . . 15 3.2 Bin"arer Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 W"orterbuch-Techniken 20

4.1 Statisches Verfahren . . . . . . . . . . . . . . . . . . . . . . . 20 4.2 Dynamisches W"orterbuch . . . . . . . . . . . . . . . . . . . . 20

5 Verlustfreie Komprimierung von Bildern 28

5.1 Die bedingte Entropie und das Markov Modell . . . . . . . . 28 5.2 Facsimile Codierung (Faxen) . . . . . . . . . . . . . . . . . . 30 5.3 Fortschreitende Bild"ubertragung . . . . . . . . . . . . . . . . 32

6 Grundlagen der verlustbehafteten Komprimierung 37 7 Skalar- und Vektorquantisierung 40

7.1 Quantisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 7.2 Gleichquantisierer . . . . . . . . . . . . . . . . . . . . . . . . 44 7.3 Adaptive Quantisierung . . . . . . . . . . . . . . . . . . . . . 46

INHALTSVERZEICHNIS 3

7.3.1 Voradaptierung . . . . . . . . . . . . . . . . . . . . . . 47 7.3.2 R"uckadaptierung . . . . . . . . . . . . . . . . . . . . . 47 7.4 Allgemeine Quantisierer . . . . . . . . . . . . . . . . . . . . . 49 7.5 Skalare Quantisierung versus Vektorquantisierung . . . . . . . 52 7.6 Der Entwurf guter Codeb"ucher . . . . . . . . . . . . . . . . . 55

8 Weitere verlustbehaftete Komprimierverfahren 65

8.1 Differentialcodierung . . . . . . . . . . . . . . . . . . . . . . . 65 8.2 Pr"adikative Differentialcodierung . . . . . . . . . . . . . . . . 66 8.3 Adaptive Differentialcodierung . . . . . . . . . . . . . . . . . 69 8.4 Delta-Modulierung . . . . . . . . . . . . . . . . . . . . . . . . 71 8.5 Teilbandcodierung . . . . . . . . . . . . . . . . . . . . . . . . 72