Datenkompression: Allgemeine Einführung

Wiki Bookwizard - ThePacker

Clear page cache

Edit current page

Create or Edit page TOC
include TOC with

{{:Datenkompression: Allgemeine Einführung:_TOC}}

zurück

2 Allgemeine Einführung

2.1 Fundamentalprinzipien der Datenkompression

2.1.1 Redundanzreduktion

2.1.2 Irrelevanzreduktion

2.1.3 Kombination aus beidem

2.2 Gründe für eine Datenreduktion

2.3 Informationstheorie und Datenkompression

2.3.1 Technologien bis 1948

2.3.2 Informationstheorie und verlustfreie Datenkompression

2.3.3 Informationstheorie und fehlerfreie Kommunikation

2.3.4 Informationstheorie und verlustbehaftete Datenkompression

2.3.5 Informationstheorie ist mehr

2.4 Anwendungsbereiche der Datenreduktion

2.5 Objektive und Subjektive Qualitätskriterien

2.5.1 Codiergewinn

2.5.2 Codiergeschwindigkeit

2.5.3 Decodiergeschwindigkeit

2.5.4 Temporärer Speicherbedarf

2.5.5 Objektive Qualitätskriterien

2.5.6 Subjektive Qualitätskriterien

2.6 Text- und Datenkompression

2.7 Audio-, Sprach-, Video- und Bildkompression

2.7.1 Audiokompression

2.7.2 Sprachkompression

2.7.3 Bildkompression

2.7.4 Videokompression

Allgemeine Einführung

Bei der Datenkompression ist man primär an einem sog. Codiergewinn interessiert, der sich als Differenz aus der Darstellung der Information gegenüber einer alternativen Darstellung der gleichen Information ergibt. Man spricht von einem Codiergewinn, wenn sich die alternative Darstellung als effizienter (kürzer) erweist, als die ursprüngliche Darstellung der Information. Das klingt zwar kompliziert, trifft aber den Kern der Datenkompression meiner Meinung nach sehr genau.

Fundamentalprinzipien der Datenkompression

	"Only wimps use tape backup: real men just upload their important stuff on ftp, and let the rest of the world mirror it."
Linus Torvalds

Die Datenkompression bzw. Datenreduktion ist nur aufgrund zweier fundamentaler Prinzipien möglich. Das Erste ist die Entfernung von Redundanz (Kompression) i.e.S. und das Zweite ist die Entfernung von Irrelevanz (Reduktion) aus einer beliebigen Informationsquelle. Der Unterschied zwischen Kompression und Reduktion liegt bei näherer Betrachtung auf der Hand: Bei der Kompression (i.e.S) bleiben die Originaldaten nach der Abbildung (Kompressionsvorgang) vollständig rekonstruierbar und im Sinne einer Rückabbildung erhalten. Mathematisch formuliert spricht man von einer bijektiven Abbildung. Bei der Datenreduktion hingegen sind die Originaldaten nach dem Abbildungsvorgang nicht immer fehlerfrei rekonstruierbar. Das bedeutet, es kommt zu einem Fehler zwischen den Originaldaten und den rekonstruierbaren Daten. Eine Rückabbildungsvorschrift ist zwar vorhanden, diese ist jedoch nicht in der Lage, sämtliche Originaldaten einwandfrei wieder herzustellen.

Redundanzreduktion

Als redundant bezeichnet man umgangssprachlich Informationen oder Daten, die sich aufgrund bereits überlieferter/übertragener Informationen durch Deduktion ableiten lassen. Es ist demnach nicht notwendig diese sog. redundanten Daten gesondert, zusätzlich oder überhaupt zu übertragen. Redundanz beschreibt den Grad der Vorhersagbarkeit von Teilen einer Nachricht, um es etwas weniger mathematisch auszudrücken.

Die Redundanz innerhalb einer Nachricht/Information lässt sich mathematisch exakt bestimmen. Es ist trotzdem weder mit beliebigem technischem oder mathematischem Aufwand möglich eine größere Menge an Redundanz aus einer Nachricht zu entfernen, als die Nachricht enthält. Es sei denn man verfälscht die ursprüngliche Nachricht oder nimmt bewusst Fehler in der rekonstruierten Nachricht in Kauf.

Das Grundprinzip der Entfernung von Redundanz findet überall dort
Verwendung, wo es darum geht, Informationen unverfälscht zu über-
tragen. Beispiele hierfür sind: verschlüsselte Daten, Text, oder
Kontoinformationen. Bei denen offensichtlich ist, dass diese nicht
verfälscht wiedergegeben werden dürfen.

Die Vermeidung von Redundanz erfolgt mit den Methoden zur verlustfreien Datenkompression. Alles in Allem geht es bei der verlustfreien Datenkompression darum, die zu übertragende Nachricht durch eine kürzere aber äquivalente Nachricht zu ersetzen, sie anschließend zu übertragen und auf der Seite des Empfängers fehlerfrei zu rekonstruieren. Sie werden im Verlauf des Buches erkennen, dass die Möglichkeiten zur Codierung sehr vielfältig sind. Dabei unterscheidet man statistische, Wörterbuch-basierende und kombinierte Ansätze. Sie werden erfahren wie verschieden diese Ideen sind und welche Möglichkeiten der Kombinationen sich eröffnen.

Irrelevanzreduktion

Als irrelevant bezeichnet man Informationen oder Daten, die vom Beobachter bzw. Empfänger nicht wahrgenommen werden können oder deren Genauigkeit nicht hinreichend wahrnehmbar ist. Als schlechtes Beispiel könnte man einen Rot/Grün-Blinden wählen, der bekanntlich schwer zwischen Rot und Grün unterscheiden kann. Durch die fehlende Unterscheidbarkeit beim Empfänger würde es bspw. ausreichen, wahlweise den Rot oder den Grün-Anteil zu übertragen. Das heißt man benutzt physiologische Grundlagen, Gegebenheiten und Modelle um zu entscheiden, ob eine Information eine Übertragung wert ist oder nicht.

Bei der Irrelevanz ist es mittels technischer oder mathematischer Modelle möglich, relevante Informationen von irrelevanten Informationen zu trennen. Meist müssen dazu komplexe Modelle, Messmethoden oder empirische Werte gefunden werden, anhand derer die Entscheidung vorgenommen werden kann, ob eine Information relevant oder irrelevant ist. Dabei spielen insbesondere objektive und subjektive Kriterien eine Rolle.

Das Grundprinzip der Irrelevanz-Reduktion findet überall dort Verwendung, wo
es nicht um die Exaktheit der Wiedergabe einer Information geht, sondern wo
selbst leichte, mittlere oder starke Verfälschungen der ursprünglichen
Informationen akzeptabel sind. Beispiele hierfür sind Audio-, Video- oder
Bild-Daten.

Darüber hinaus ist es möglich, nicht nur nicht hinreichend wahrnehmbare Informationen zu unterschlagen, sondern bewusst auch wahrnehmbare Fehler in Kauf zu nehmen, um so die zu übertragende Information an die Art der Codierung anzupassen. Der Vorteil der Anpassung an die Art der Codierung besteht darin, dass der Codierer entscheiden kann, welche Modifikation während der Codierung zu einer besseren Kompressionsleistung führen. Der Codierer erzeugt durch die Modifikation sog. Kompressionsartefakte, die es dem Codierer möglich machen eine vorgegebene Kompressionsrate zu erreichen oder zu unterschreiten. Die Verfahren mit denen diese Art der Codierung erreicht werden kann, werden im Kapitel Verlustbehaftete Kompression behandelt.

Kombination aus beidem

Nachdem die Einleitung bereits andeutete, dass es sich bei der Datenkompression um eine Transformation bzw. Abbildung der Daten handelt, kann man auf den Gedanken kommen, verschiedene Transformationen nacheinander anzuwenden. Bei einer Redundanz-Reduktion spielt es jedoch keine Rolle, wie oft eine Transformation statt findet oder wie komplex diese Transformationsvorschriften sind, es ist nicht möglich einen höheren Codiergewinn zu erzielen, als die sog. Redundanz zulässt. Was man prinzipiell tun kann, ist Verfahren der Irrelevanzreduktion mit denen der Redundanzreduktion zu kombinieren. Hierbei ist es wichtig, sich an die folgende Reihenfolge zu halten:

In den ersten Schritten sollte stets die Irrelevanz aus den zu codierenden Daten entfernt werden.
- Dazu werden zunächst relevante und irrelevante Informationen getrennt oder in eine passende Darstellung überführt.
- Zur Trennung der relevanten Informationen können vollkommen verschiedene Darstellungen der Information sinnvoll sein.
Die nachfolgenden Schritte versuchen anschließend die verbliebenen redundanten Anteile aus der zu codierenden Nachricht zu entfernen.

Diese Vorgehensweise ist überall dort möglich und sinnvoll, wo Veränderungen an den zu codierenden Informationen akzeptabel sind. Es gelten die gleichen Bedingungen, wie bei den Verfahren, die zur Irrelevanz-Reduktion eingesetzt werden. Es gibt im Grunde keine Verfahren, die ausschließlich Irrelevanz entfernen, sondern solche Verfahren werden stets mit Verfahren zur Redundanz-Reduktion kombiniert. Ansonsten gäbe es keinen großen Codiervorteil. Die kombinierten Verfahren werden im Kapitel verlustbehaftete Kompression behandelt.

Um sich näher mit den Verfahren zur Irrelevanzreduktion zu befassen, ist es optimal, wenn Sie sich mit dem Kapitel zur verlustfreien Codierung befasst haben. Denn nur die abschließende verlustfreie Codierung macht eine verlustbehaftete Codierung erst richtig effizient.

Gründe für eine Datenkompression

Es gibt eine Vielzahl von Beispielen, anhand derer gezeigt werden kann, dass die verlustfreie oder verlustbehaftete Datenkompression sinnvoll sind. Die Datenkompression ist eng mit der Informationstheorie, wie sie von Claude Shannon im Jahr 1948 formuliert wurde, verbunden. Die Informationstheorie und die Informationstheoretischen Ansätze haben nach über 50 Jahren der Existenz derart viele Bereiche berührt, dass die moderne Informatik und Informationstechnik nicht ohne diese theoretische Abhandlung denkbar wären. Heute geht es mehr denn je, um die Speicherung und Verarbeitung digitaler Daten und es ist völlig egal in welche Richtung man blickt. Die moderne Medizin kommt heute nicht ohne bildverarbeitende Methoden aus. Nachdem die Information digital wurden, suchte man nach Möglichkeiten sie auch digital zu übertragen, digital zu speichern und digital zu verarbeiten. Erst dadurch gelang es Informationen digital und somit verlustfrei zu verarbeiten oder zu kopieren.

Nachdem die Information digital aufgezeichnet werden konnte, wollte man erfahren, wie viel Information tatsächlich in einer Nachricht steckt. Diese Frage ist sowohl von philosophischem, als auch von ingenieurstechnischem Interesse. Die ingenieurstechnischen Fragen beantwortete Claude Elwood Shannon (Vater der Informationstheorie) mit seiner berühmt gewordenen Arbeit A Mathematical Theory of Communication [1]. Sie wurde 1949 unter dem Titel The Mathematical Theory of Communication leicht erweitert und erneut veröffentlicht.

Nach über 50 Jahren der Informationstheorie gibt es keinen Bereich, der nicht von der Informationstheorie berührt worden ist und es gibt keinen Bereich, der sich früher oder später nicht mit der Codierung und Kompression von Daten bzw. Informationen beschäftigen muss.

Die Datenkompression wird häufig dann eingesetzt, wenn bspw. eine bestimmte Datenmenge pro Zeiteinheit übertragen werden muss, oder die absolute Datenmenge entscheidend ist. Eine bestimmte übertragbare Datenmenge pro Zeiteinheit heißt Kanalkapazität und diese Kapazität ist endlich. Das bedeutet, dass endlich viele Informationen pro Zeiteinheit übertragen werden können und das wiederum bedeutet, dass keine Information unendlich genau übertragen werden kann. Damit jedoch der Kern der Information erhalten bleibt, wird sie codiert, wenn bspw:

keine ausreichende Kanalkapazität zur Verfügung steht, bspw. bei:
- Funk-Übertragungsstrecken (BOS, Tetra, Richtfunk),
- DVB-C (digitales Kabel-Fernsehen),
- DVB-S (digitales Satelliten-Fernsehen),
- DVB-T (digitales terrestrisches Fernsehen),
- DAB (digitaler Hörfunk),
- Mobilfunk (digitale terrestrische und satellitengestützte Telefonie),
- Internettelefonie
die verbesserte Wirtschaftlichkeit (Senkung von Kosten) bzgl. Speicherung oder Übertragung von Daten im Vordergrund steht oder
konkurrierende Daten auf einem Kanal (Sprach und Videodaten) sich eine gemeinsame Bandbreite teilen.

Von einer nicht ausreichenden Kanalkapazität spricht man häufig dann, wenn man darauf angewiesen ist, eine bestimmte Menge von Daten pro Zeiteinheit über einen begrenzten Kanal zu übertragen bzw. der Kanal schmalbandig ist. So kann es passieren, dass nur ein Teil der Informationen übertragen werden kann. Der Funkstandard GSM ist ein solches Beispiel. Ein GSM-Kanal bietet inklusive Fehlerschutz etwa 9.6 Kilobit/Sekunde. Die Datenrate einer Audio-CD (Stereo) beträgt etwa 1500 Kilobit/Sekunde. Das bedeutet, dass eine Audio-CD nicht in "Echtzeit" mit Hilfe eines GSM-Kanals transferiert werden kann. Für jede Sekunde CD-Datenmaterial wären etwa 2 Minuten und 30 Sekunden Übertragungszeit auf einem GSM Kanal notwendig. Die einzige Möglichkeit der Echtzeitübertragung besteht darin, das CD-Datenmaterial so zu verarbeiten, dass der Empfänger einen Eindruck vom Inhalt der CD bekommen kann. Das bedeutet, man versucht den wichtigsten Teil der Information zu übertragen.

Eine verbesserte Wirtschaftlichkeit erreicht man, wenn man die Datenmenge durch Datenkompression und Datenreduktion reduzieren kann, bevor man sie auf den Datenträger/Datenspeicher überträgt. So kann mehr vom ursprünglichen Datenmaterial gespeichert werden. Der Datenspeicher kann eine bestimmte Menge an Daten speichern (Kapazität) und es ist egal, ob der Datenspeicher redundante Daten speichert oder nichtredundante. Bevorzugt speichert man nicht redundante Informationen auf der Festplatte bzw. dem Datenspeicher. Somit müssen weniger Datenträger/Datenspeicher gekauft/gemietet werden. Im Normalfall fallen für die Datenspeicherung und Datenvorhaltung weitere Kosten in Form von Strom für die Computer und insbesondere für die Klimatechnik an. Das betrifft auch Daten die auf magnetischen Bändern gespeichert worden sind. Diese müssen vor allem dort gelagert werden, wo sie nicht wechselnden Umweltbedingungen ausgesetzt sind.

Der Nachteil der optimalen Darstellung der Daten liegt insbesondere dann vor, wenn die Daten aufwändig verarbeitet werden müssen, um die codierte oder uncodierte Form der Daten zu erhalten. Die meisten heute bekannten komplexen Verfahren der Audio, Video und Bild-Codierung benötigen komplexe mathematische Transformationen und Modelle, um sie zu codieren oder sie für den Menschen wieder nutzbar zu machen. Andere Verfahren kommen mit geringerem mathematischen Aufwand aus und können dafür nicht optimal oder nicht effizient genug codieren. Das bedeutet, dass man einen Kompromiss zwischen Rechen/Verarbeitungs-Zeit und Codiereffizienz der Daten finden muss. Je mehr Abhängigkeiten man zwischen den einzelnen zu codierenden Daten identifizieren kann, desto effizienter können diese Daten codiert werden.

Informationstheorie und Datenkompression

Die Grundlagen für die Datenkompression und die Datenübertragung wurden durch Claude Shannons Artbeit A mathematical theory of communication bereits im Jahr 1948 gelegt. Diese Arbeit markiert den Beginn er der Informationstheorie. Dieser Abschnitt beschreibt den Zusammenhang zwischen der Informationstheorie und der Datenkompression, sowie der Informationstheorie mit anderen Gebieten, die im Laufe der Zeit mit ihr verknüpft wurden. Ein Artikel, der sich ausführlich mit den letzten 50 Jahren der Informationstheorie beschäftigt, ist Fifty Years od Shannon Theory von Sergio Verdú (IEEE Transactions on Information Theory, Vol. 44, No. 6, October 1998, Pages 2057-2078, Author: Sergio Verdú). [2], [3], [4]. Gefunden mit der wissenschaftlichen Suchmaschine scholar.google.com.

Technologien bis 1948

Lassen Sie uns einen Blick auf die 1948 verfügbaren Technologien werfen, denn nur so kann beurteilt werden, was Claude Elwood Shannon geschaffen hat. Seine Arbeit "A mathematical theory of communication" wird heute bereits als die "Magna Charta" des Informationszeitalters bezeichnet. Lassen Sie uns zunächst die Kommunikationssysteme und die technischen Errungenschaften betrachten, die 1948 verfügbar waren:

Telegraf
Telefon
Amplitudenmodulation
Radio
Funk
Fernsehen
Fernschreiber
Frequenzmodulation
Pulscodemodulation
Vocoder
Frequenzspreizung (Spreizband-Modulation)

Informationstheorie und verlustfreie Datenkompression

Die Informationstheorie überschneidet sich thematisch mit den Bereichen über die Wahrscheinlichkeit, Statistik, Informatik und trug zur Entwicklung der Kommunikation, Datenspeicherung, und Datenverarbeitung und anderen Informationstechologien bei.

Shannon begriff als erster, dass eine Nachrichtenquelle bzw. Informationsquelle als ein Zufallsprozess verstanden werden kann. Diese Informationsquelle erzeugt Nachrichten, indem sie sie Zeichen für Zeichen ausgibt. Sie wählt diese Zeichen anhand einer bestimmten Wahrscheinlichkeit. Ein mathematisches System, das ein Zufallselement aus einer endlichen Menge generiert, ist der sog. stochastische Prozess und als solcher kann eine diskrete Quelle verstanden werden.

Huffman
Shannon
Codes mit Variabler Länge
Codes mit fester Länge
universelle Codierung

Das bekannteste universelle Quellencodier-Verfahren wurde von Abraham Lempel und Jacob Ziv vorgestellt. Die von Lempel und Ziv vorgestellte Methode kümmert sich nicht um die Wahrscheinlichkeiten, mit denen die Symbole an einer Quelle auftreten, sondern codiert stets die kürzeste noch unbekannte Phrase. Allgemein konnte das von Lempel und Ziv vorgestellte und später noch verbesserte Verfahren beliebige stationäre ergodische Quellen nahe ihrem Informationsgehalt codieren.

Bedingte Entropie
Blockentropie
Entropie natürlicher Sprache
Codierung mit abzählbar unendlich großem Alphabet
Kolmogoroff-Komplexität

Informationstheorie und fehlerfreie Kommunikation

Kanal
Kanalkapazität
Kanalcodierung

Informationstheorie und verlustbehaftete Datenkompression

Rate / Distortion-Theorie
Rate / Distortion-Funktion

Informationstheorie ist mehr

In den letzten 50 Jahren wurden einige hundert wissenschaftliche Abhandlungen verfasst, die einen direkten Bezug zur Informationstheorie von Shannon herstellen. Darunter zählen Abhandlungen aus den folgenden Bereichen:

Biologie
Chemie
Informatik
Mathematik
Physik
Statistik
Wahrscheinlichkeitstheorie
Wirtschaft

Anwendungsbereiche der Datenreduktion

Neben den bereits angesprochenen Bereichen, also Rundfunk, Fernsehen und Mobilfunk ist die Datenkompression insbesondere für die Archivierung von Informationen bzw. Daten sehr nützlich. In nahezu jedem Lebensbereich fallen heute ungeheure Datenmengen an. Das betrifft beispielsweise Kreditkartenabrechnungen, bei Banken oder Händlern, öffentlichen und privaten Institutionen insbesondere zu Abrechnungszwecken, Steuereintreibung, Leistungsnachweisen, Telefonaten, Urlaubs- und Gehaltsabrechnungen, Kartei und Katalogsystemen, Rechnungen, Mahnungen, bei der Arbeit mit und am Computer, Rentenversicherung, Sozialversicherung und beispielsweise in der Verwaltung. Um nur einige wenige Bereiche zu nennen, in denen die Daten teilweise über Jahre und Jahrzehnte hinweg archiviert werden müssen.

Spätestens jetzt bekommt man eine Vorstellung, wie sehr man selbst von Daten und Informationen abhängt. Nicht nur die kurzzeitige Archivierung von Daten spielt eine Rolle, sondern auch die sogenannte Langzeitarchivierung. Ein solcher Bereich ist die Langzeitarchivierung medizinischer Daten, die immer häufiger in digitaler Form vorliegen (Stichwort: elektronische Patientenakte). So können korrekte oder falsch gestellte Diagnosen, selbst nach vielen Jahren geprüft oder belegt werden. Weil zum Beispiel die ursprünglichen Daten (Originaldaten ohne jede Alterung) in unveränderter Form zur Begutachtung herangezogen werden können. In der Krankenhausverwaltung werden Informationssysteme benötigt (sog. Krankenhaus-Informationssysteme), mit denen die Patienten und deren Daten verwaltet werden. Das hört sich vielleicht etwas merkwürdig an, aber diese Daten sind für den Patienten lebenswichtig, denn in einem HIS (engl. Hospital-Information-System) wird gespeichert, welche Medikamente der Patient in welcher Dosierung bekommt, welche er bereits erhalten hat, wann er für eine Operation mit welcher Dosis narkotisiert wird und vieles andere mehr. Die Resultate von radiologischen Untersuchungen werden in einem RIS gespeichert, einem Radiologie-Informationssystem. Die Geräte sammeln die Daten und archivieren sie mittels ACR-NEMA/DICOM, damit der Arzt diese Daten einsehen kann, sobald sie das Arztzimmer betreten.

Weitere Daten, die langzeitarchiviert werden sind meteorologische und weitere statistische Informationen. Denn erst über lange Zeiträume hinweg können derartige Daten analysiert und Regelmäßigkeiten bzw. Regeln bei bestimmten Wetterlagen, oder andere statistische Abhängigkeiten erkannt werden. Insbesondere, wenn diese Daten über Generationen hinweg gesammelt werden müssen. Die Regeln werden umso präziser, je mehr aussagekräftige Daten vorliegen. Die Schätzung für das Wetter der nächsten Tage, beruht im wesentlichen darauf, dass eine bestimmte Wetter Konstellation mit einer früheren bzw. ähnlichen Konstellation verglichen wird. Abhängig davon wird für die damaligen Folgetage überprüft, ob es geregnet hat oder nicht. Eine 70 Prozentige Regenwahrscheinlichkeit bedeutet, dass die früheren bzw. vergleichbaren Daten zeigen, dass in 70 Prozent ähnlicher Fälle am Folgetag Regen fiel. Das sagt nur aus, dass man mit einem Regenschauer mit einer Wahrscheinlichkeit von 70 Prozent rechnen muss. Wie lange dieser Regenschauer dauert, wie heftig er ist oder ob er überhaupt eintritt ist schwer vorherzusagen. Diese Daten müssen jederzeit verfügbar, durchsuchbar und vergleichbar sein. Das bedeutet, man benötigt ein Archiv derartiger Daten. Wenn anhand dieser Daten Modelle ermittelt wurden, kann eine Schätzung nicht nur für den Folgetag abgegeben werden, sondern für die weiteren Folgetage. Diese Modelle wären durch flächendeckende Aufzeichnungen von Temperatur, Luftdruck, Windgeschwindigkeit, Windrichtung, Sonneneinstrahlung und diverser anderer Parameter nicht möglich gewesen.

Der analoge und der digitale Rundfunk kommen heute nicht mehr ohne eine Datenreduktion aus. Das beginnt im Studio, wo die Daten nicht mehr mittels analoger magnetischer Aufzeichnungen (MAZ) auf Bändern, sondern auf Festplatten-Arrays liegen, von denen sie in Echtzeit abrufbar sind. Die Musik, Sprache, Videos sind um den Faktor 5..100:1 codiert. Andernfalls würden riesige Archive bzw. Lagerhallen gebraucht, um das Originalmaterial zu lagern. Die Filmindustrie setzt immer mehr auf die digitale Übertragung von Filmen, da die Erstellung von Kopien auf Zelluloid sehr aufwändig und teuer ist. Es ist einfach billiger die Daten digital an mehrere Kinos gleichzeitig auszuliefern. Das erspart die Produktion und Vernichtung von tonnenweise Chemikalien, was dem Umweltschutz zu Gute kommt.

Wenn Sie heute im Geschäft eine Film-DVD erstehen, so befinden sich die Daten in komprimierter Form auf dem Datenträger, da eine DVD nicht annähernd in der Lage wäre, einen vollständigen Film unkomprimiert zu speichern. Das für die DVD eingesetzte Verfahren zur Video-Kompression ist MPEG 2 und für die Audio-Codierung wurde ursprünglich Audio MPEG 2 (5.1) vorgesehen. Das Audio-Codierverfahren wurde allgemeinen durch Dolby-Digital 5.1 (ATSC A.52) ersetzt. Der Vorgänger der DVD, die VCD, arbeitete noch mit dem MPEG I Verfahren. Das heißt die Unterhaltungsindustrie setzte schon seit Jahren auf allgemein verfügbare Standards zur Audio und Videokompression. Heute wird fast überall Kompression eingesetzt, sei es in Bildformaten bei Digitalkameras (JPEG, PNG, GIF, TIFF), in Videos (MPEG 1,2,4), in Audiodaten (MPEG 1 Audio, Layer I/II/III, MPEG 2 Audio, AC-3, ATRAC, MPEG4-AAC) oder in der Videokommunikation (H.261, H.262, H.263, H.264, G.711, G.723, G.726, G.728, G.729, H.323). Auch in Zukunft werden multimediale Inhalte komprimiert werden, nur werden sie durch sog. DRM (Digitales Rechtekontrollmanagement), ausschließlich mit zertifizierter Hardware(TPM), sowie nur mit zertifizierten und signierten Treibern in voller Auflösung(HDCP) zu genießen sein.

Ohne eine Entschlüsselung, die durch eine Lizenz aktiviert wird, wird es in Zukunft nicht mehr möglich sein, diese Daten zu entschlüsseln und anschließend zu dekomprimieren. In den meisten heute verfügbaren DRM-geschützten Inhalten, stecken die Techniken der letzten 30 Jahre der Datenkompression, wobei von den Herstellern der DRM-Verfahren alt bewährte Kompressionsverfahren wie bspw. MPEG 1 Audio Layer II/III eingesetzt werden. Die meisten der in den neuen Medienformaten verwendeten Techniken sind nicht neu, sondern nur in Crypto-Containern verpackt und verschlüsselt.

Auch Office-Pakete wie OpenOffice (SWX-Dateien) setzen bei der Speicherung der Dokumente auf Datenkompression. Das bedeutet die Dokumente werden in redundanzarmer Form auf der Festplatte gespeichert.

Objektive und Subjektive Qualitätskriterien

Welche Möglichkeiten gibt es, verschiedene Kompressionsverfahren resp. Codierverfahren miteinander zu vergleichen? Wir kennen mindestens zwei mögliche Strategien, zwei Dinge miteinander zu vergleichen. Die eine ist die Möglichkeit, zwei Dinge objektiv miteinander zu vergleichen. Die andere besteht darin, zwei Dinge subjektiv miteinander zu vergleichen.

Ein Beispiel für einen Vergleich ist, wer mehr oder weniger Weizenmehl besitzt. Es kann bspw. durch eine Zahl (und Ordnung) und ein definiertes Kriterium (bspw. die Masse) ausgedrückt werden. Auch anderen Beobachtern ist es möglich zu entscheiden, ob Dinge größer, kleiner, oder ob mehr oder weniger vorhanden ist, oder auch gleich sind. Vergleicht man, ob etwas qualitativ besser oder schlechter ist, so definiert man zunächst was denn besser überhaupt bedeutet in diesem Kontext. Dadurch hat man ein objektives Qualitätskriterium geschaffen.
Ein weiteres Beispiel ist der Vergleich, dass eine Sache vom eigenen Standpunkt gesehen aus schöner oder besser ist. Das bedeutet, dass man selbst für sich entscheidet, dass etwas schöner ist, als etwas anderes. Eine Katze ist schöner als ein Hund. Man vergleicht oder beurteilt also zwei unterschiedliche Dinge mit Hilfe eines persönlichen Maßstabs. Beschränkt man sich bspw. nur auf die Farbe oder Form der Katze bzw. des Hundes, hat man man ein subjektives Qualitätskriterium geschaffen.

Bei der Datenkompression unterscheidet man zwischen objektiven und subjektiven Qualitätskriterien und nutzt diese gezielt, um ein oder mehrere Codierverfahren oder Kompressionsverfahren untereinander bzw. miteinander zu vergleichen. Beide Arten der Qualitätskriterien (obj. u sub.) können für ein Kompressionsverfahren angewandt werden, um ein Codierverfahren zu evaluieren.

Ein Vergleich eines Algorithmus mit sich selbst kommt immer dann in Frage, wenn es unterschiedliche Parametrierungen eines Algorithmus gibt und man die beste aller Parametrierungen ermitteln möchte. Man vergleicht einen Algorithmus mit einem anderen, um sie direkt miteinander zu vergleichen, bspw. welcher Algorithmus von beiden besser ist als ein anderer.

Um zwei Algorithmen direkt miteinander zu vergleichen, brauchen beide Algorithmen die gleiche Testumgebung. Es haben sich insgesamt zwei verschiedene Testumgebungen etabliert, die ältere der beiden Testumgebungen ist der sog. Calgary Corpus (der Klassiker), und die jüngere von beiden ist der Canterbury Corpus.

Der Calgary Corpus (wenig umfangreich) dient vor allem der Evaluierung verlustfreier Verfahren, wohingegen der Canterbury Corpus sehr umfangreich ist und auch für die Evaluierung verlustbehafteter Verfahren verwendet werden kann. Man meint, der Calgary Corpus sei heute nicht mehr standesgemäß, weil sich die Art der Daten in den letzten zwei Dekaden verändert habe. Aber es gibt sowohl kurze als auch längere Daten, und Kompressionsalgorithmen sollten bezüglich verschiedener Testsuiten gute Resultate liefern.

Der Calgary Corpus ist die Testsuite der Universität Calgary (Kanada) und ist auf der Seite (http://www.data-compression.info/Corpora/CalgaryCorpus/) zu finden.

Der Canterbury Copus ist auf der Seite (http://corpus.canterbury.ac.nz/index.html) zu finden. Der Canterbury Corpus ist etwa zehn Jahre jünger (1990) als der Calgary Corpus. Speziell heute geht es darum, große Dateien bzw. große Datenmengen zu codieren. Hier dient bspw. das Resultat der Sequenzierung des E.Coli-Bakteriums als eines der Testobjekte.

Es gibt unter anderem einen Corpus, mit dem Bildkompresionsalgorithmen / Bild-Codier-Verfahren getestet werden können. Dieser ist bspw. hier zu finden (http://links.uwaterloo.ca/bragzone.base.html). Daneben gibt es eine Reihe weiterer Testsuiten, um beispielsweise die Bild- und Videokompression zu testen. Alle in diesem Rahmen vollständig aufzuzählen wäre allerdings sehr aufwendig.

Codiergewinn

Der Codiergewinn ist abhängig von der sog. Kompressionsrate. Die Kompressionsrate ist das Verhältnis der Datenmenge, die ursprünglich für eine Nachricht benötigt wurde, zu der, die nach einer Codierung benötigt wird. Ist das Ergebnis dieses Verhältnisses größer als 1, ist also die Datenmenge nach einer Codierung weniger umfangreich als vor der Codierung, so erzielt man einen Codiergewinn. Ist dieses Verhältnis kleiner als 1, so ist die Datenmenge zur Darstellung der codierten Nachricht größer als die uncodierte Darstellung. In diesem Fall ist es effizienter, die Nachricht nicht zu codieren.

Kompressionsrate = Datenmenge(Original) / Datenmenge(Codiert)

$R={\frac {n_{original}}{n_{codiert}}}$

Zwei verschiedene Kompressions- oder Codier-Verfahren lassen sich dadurch miteinander vergleichen, indem man von beiden die Kompressionsrate bestimmt und miteinander vergleicht. Das Verfahren mit der höheren Kompressionsrate ist im allgemeinen das bessere Codierverfahren. Das bessere Codierverfahren erzeugt also eine kürzere Repräsentation der Originalnachricht als das schlechtere von beiden.

Der Codiergewinn lässt sich sowohl auf Codierverfahren anwenden, die verlustfrei arbeiten, als auch auf jene, die verlustbehaftet arbeiten. Im Falle eines verlustbehafteten Verfahrens werden zumeist weitere Qualitätskriterien herangezogen, um ein ausgewogeneres Bild zu erhalten. Denn nicht jeder Algorithmus der eine besonders hohe Kompressionsrate erzielt, erzielt auch visuell oder hörbar die beste Qualität.

Codiergeschwindigkeit

Ein weiterer wichtiger Parameter ist u.a. die Codiergeschwindigkeit, die sowohl von der zu codierenden Datenmenge abhängt, als auch vom verwendeten Codierverfahren. Jedes Codierverfahren besitzt eine eigene Strategie, mit Hilfe derer eine Eingabe codiert wird. Als Faustregel gilt: je komplexer ein Codier-Algorithmus ist, desto mehr Rechenzeit wird benötigt, um eine Nachricht in eine codierte Form zu überführen.

Eine hohe Codiergeschwindigkeit bedeutet zumeist eine geringe Latenzzeit. Dass das aber nicht immer so sein muss, soll an diesem Beispiel verdeutlicht werden: Stellen sie sich einen Algorithmus vor, dessen codierte Zeichen vom Decodierer partiell kurz nach dem Empfang der Daten decodiert werden können. Dann spricht man von einer sehr geringen Latenzzeit, da die Daten kontinuierlich auf der Seite des Senders und des Empfängers verarbeitet werden. Mit wenigen codierten Zeichen kann anschließend eine Decodierung begonnen werden. Die Latenzzeit besteht somit aus den folgenden Zeiten:

Zeit des Codiervorgang, bis das erste Zeichen sicher decodiert werden kann
Zeit für das Übertragen der dafür notwendigen Datenmenge und die
Zeit für den Decodiervorgang für dieses erste Zeichen.

Als Gegenstück zu diesem Algorithmus stellen Sie sich ein Verfahren vor, bei dem zunächst das vollständige codierte Datenpaket empfangen und gespeichert werden muss, ehe es vollständig decodiert werden kann. Ein derartiges Verfahren ist die sog. fraktale Bildkompression. Es muss zunächst die komplette Decodiervorschrift empfangen werden, bevor einzelne Pixel decodiert werden können. Das Verfahren zur Codierung kann noch so schnell sein, die Gesamtlatenzzeit besteht aus der Zeit, die für den

Codiervorgang,
die für die Übertragung aller codierten Daten und den
Decodiervorgang selbst benötigt wird.

Unter Umständen ist die Codiergeschwindigkeit nicht wichtig, wenn sie nur ein einziges Mal durchgeführt zu werden braucht. Dazu zählt bspw. die Kompression eines ISO-Images, das anschließend verbreitet wird. Dort ist es akzeptabel, wenn ein Verfahren zwei Stunden oder länger benötigen würde, um eine möglichst kompakte Darstellung zu erreichen. Der einmalige Zeiteinsatz mag ärgerlich sein, das Ergebnis ist dass die Daten schneller beim Empfänger ankommen (Zeit für den Prozess des Herunterladens).

Bei Verfahren der Online-Kompression, Codierung z.B. während eines Nachrichtenaustausches, dürfen derartig lange Latenzzeiten nicht auftreteten. Dort sollte das Verfahren möglichst wenig Komplexität besitzen, um eine ungestörte bzw. transparent Kommunikation zu erreichen. Das bedeutet, man codiert die Nachricht mit einem nicht optimalen Verfahren, das aber weitaus schneller arbeitet und eine geringe Latenzzeit hat, als andere und ebenso in der Lage ist, partiell empfangene Daten zu decodieren.

Decodiergeschwindigkeit

Weitaus weniger häufig wird auf die Decodiergeschwindigkeit Wert gelegt. Diese geht oft mit der Komplexität des Verfahrens einher, mit der die Decodierung vorgenommen wird. Das spielt insbesondere bei der mobilen Kommunikation eine Rolle. Je aufwendiger es ist, eine Nachricht zu decodieren, desto mehr Rechenzeit und vor allem Energie muss aufgewendet werden, um an die uncodierte Informationen zu gelangen. Das beeinträchtigt vor allem die Betriebsdauer, während der das mobile Gerät betrieben werden kann. Es ist zwar meist einfacher, die codierten Informationen zu decodieren, als sie zu codieren, doch sollte man trotzdem immer berücksichtigen dass sich die Nutzung eines Verfahrens immer nur dann als sinnvoll erweist, wenn man es für einen bestimmten Einsatzzweck hin optimiert bzw. auswählt. Man sollte also nicht immer das Verfahren mit der größten Kompressionsrate wählen, sondern eventuell eines, welches mit möglichst wenigen Rechenoperationen auskommt, um Nachricht zu decodieren, und trotzdem eine vergleichsweise hohe Kompression erreicht.

Spielt die Energieeffizienz keine Rolle, da sie praktisch in ausreichender Form vorhanden ist, so treten meist andere Parameter in den Vordergrund, anhand derer die Wirtschaftlichkeit eines Verfahrens gemessen wird. Dann sind dann es meist das Datenvolumen oder die Übertragungszeit, die als wirtschaftliche Parameter entscheidend sind. Manchmal sind es aber banalerweise auch die einfachen Stückkosten. (Es ist billiger, eine DVD oder CD im Handel auszuliefern, als zwei davon.)

Temporärer Speicherbedarf

Nahezu jeder heute erhältliche Computer ist mit ausreichend RAM ausgestattet, und es scheint etwas sinnlos darüber zu philosophieren, wie hoch der Speicherbedarf eines bestimmten Algorithmus sei. Für Computer i.e.S. mag diese Ansicht zutreffen, aber spätestens bei netzunabhängigen Geräten bedeutet zusätzlicher RAM automatisch einen zusätzlichen Energiebedarf.

Bereits heute gibt es Kompressionsverfahren, die sehr gute Werte beim Codiergewinn erzielen, meist jedoch auf Kosten eines immensen temporären Speicherbedarfs. Damit ist ein temporärer Speicherbedarf von bspw. mehr als 768 Megabyte gemeint, um eine für heutige Verhältnisse mittelgroße Datei zu kodieren. Ein Datenkompressionsverfahren hat demnach auch das Problem, dass es unterschiedliche Gütekriterien erfüllen muss. Stellen sie sich vor, sie würden eine sehr effizient codierte Datei erhalten, könnten sie weder lesen noch verarbeiten, weil sie nicht genügend temporären Speicher besitzen, um diese Datei zu decodieren. Aus diesem Grund ist es notwendig, auch die vermeintlich „antiquierten“ Verfahren der Datenkompression nicht zu vergessen. Denn vor allem die älteren Verfahren wurden zu Zeiten entwickelt, in denen der temporäre Speicherbedarf und die Berechnungskomplexität ebenso wichtig waren, wie der Codiergewinn.

Hat man jedoch ausreichend Speicher und Rechenzeit zur Verfügung, so kann man Daten, Bilder, Musik und Videos sehr effizient codieren. Der Speicher wird heute meist nicht durch die zu komprimierenden Daten selbst benötigt, sondern für die sog. Kontext-Modelle, mit denen die Folgesymbole vorausgesagt werden. Heute gilt, je exakter sich das verwendete Modell an die zu codierenden Daten anpassen kann, desto besser sind die Voraussagen des Modells, und desto besser sind anschließend die Kompressionsergebnisse. Mit der Komplexität der Modelle steigt zumeist der Bedarf an Rechenbedarf für die jeweiligen komplexen Modelle, was dazu führt, dass nicht jedes Verfahren gleichermaßen gut geeignet ist. Eine nicht zu vergessene Regel ist: Keep it simple.

Auch sollte man unterscheiden, zwischen dem temporären Speicherbedarf, der für den Codiervorgang benötigt wird, und dem, der für die Decodierung benötigt wird. Viele dieser Verfahren benötigen für die Decodierung der Daten weitaus weniger Speicher, als für die Codierung der Daten. Also frei nach dem Prinzip, es ist aufwändiger eine Null oder Eins zu berechnen, als sie mittels Decodierung weiter zu verarbeiten.

Objektive Qualitätskriterien

Wie in der kurzen Einführung beschrieben wurde, ist ein objektives Qualitätskriterium eines, dass sich exakt messen lässt. Messen lassen sich unter Anderem der Codiergewinn, die Codiergeschwindigkeit und die Decodiergeschwindigkeit. Wie diese zu messen sind liegt klar auf der Hand und braucht nicht weiter erläutert zu werden. Man kann die bereits vorgestellten Kriterien für die verlustfreie Datenkompression ganz hervorragend verwenden. Doch wir wissen bereits, dass der Codiergewinn bei verlustbehafteten Verfahren etwas zwiespältig ist. Nicht jedes Verfahren, das Bilder, Audio- und Videodaten mit hohen Gewinnen codieren kann, ist auch qualitativ die beste Wahl.

Was bedeutet diese Aussage? Im Grunde genommen nur eines: Es fehlt ein zuverlässiges Maß (quasi ein Qualitätskriterium) in Bezug auf die verlustbehaftete Kompression. Genau diesem Problem ist sowohl dieser Abschnitt, als auch der folgende Abschnitt gewidmet.

Um Ihnen einen kurzen Überblick zu verschaffen, wie diese objektiven Kriterien zustande kommen, sollen Ihnen einige der Kriterien in Form kurzer Erläuterungen vorgestellt werden. Die bekanntesten sind:

Signal-Rausch-Verhältnis

Das SNR (Signal Noise Ratio) - Signal-Rausch-Verhältnis ist im Grunde genommen das erste Qualitätskriterium was einem in Bezug auf die Güte einfallen kann. Besitzt man das originale Signal und das rekonstruierte Signal in Form einzelner abgetasteter Werte, so kann man direkt die Differenz dieser beiden Signale bestimmen. Man spricht dabei vom Fehlersignal. Das Fehlersignal kann man grundsätzlich als eine Art Rauschen verstehen, welches auf Original-Signal einwirkt und zum fehlerhaften rekonstruierten Signal führt. Betrachtet man das Rauschsignal im Verhältnis zur Gesamtamplitude des Signals, so spricht man vom Signal-Rausch-Verhältnis. Das soll als kurze Erklärung zunächst ausreichen, da das Signal-Rausch-Verhältnis an anderer Stelle wesentlich detaillierter erläutert werden wird.

Spektrale Distanz

Unter der spektralen Distanz versteht man die Differenz zweier Kurzzeitspektren. Dabei wird das originale Signal einer Kurzzeit-Spektralanalyse unterzogen und mit dem Kurzzeit-Spektrum des rekonstruierten Signals verglichen und die Differenz ermittelt. Damit beide Signale miteinander vergleichbar bleiben, werden die gleichen Ausschnitte gewählt. Man hat die Möglichkeit, die einzelnen Differenzen abhängig von der Frequenz zu gewichten, und erhält einen objektiven Wert, der mit dem subjektiven Empfinden im großen und ganzen korreliert ist. Je größer die Distanz zwischen zwei Signalen ist, desto weniger ähneln sie sich, und desto größer ist der Rekonstruktionsfehler.

Wahrnehmungsangepasste Kriterien

Manchmal reicht eine einfache lineare Differenz zwischen Kurzzeitspektren nicht aus, und es werden weitere Zahlenwerte in Form von Tabellen benutzt, nach denen die Rekonstruktionsfehler bewertet werden. Das Resultat ist eine genauere Beurteilung, als sie mit der Spektralen Distanz möglich ist. Dazu beurteilt man bspw. ein einzelnes Kurzzeitspektrum nicht mehr allein, sondern bewertet zusätzlich die Veränderungen des Kurzzeitspektrums in Hinblick auf die physiologische Wahrnehmbarkeit. Das bedeutet, dass ein sehr komplexes Modell entscheidet, welche Qualität ein rekonstruiertes Signal erreicht. Wie derartige Modelle funktionieren, soll in den Kapiteln und Abschnitten zur verlustbehafteten Codierung besprochen werden.

Subjektive Qualitätskriterien

Subjektive Qualitätskriterien ergeben sich in der Regel aus statistischen Messungen. Dazu wird einem Kreis von potentiellen Nutzern oder besonders geschulten Personen eine Reihe parametrierter Daten zur subjektiven Qualitätsbeurteilung überlassen. Diese Daten werden mittels Fragebögen oder in anderer Form abgefragt und anschließend evaluiert. Daraus können die gemittelten subjektiven Kriterien mit der Parametrierung des Modells oder des Kompressionsverfahrens in Zusammenhang gebracht werden.

Subjektive Verfahren werden ausschließlich dort eingesetzt, bei denen eine Irrelevanzreduktion erfolgt. Denn wenn Originaldaten und Wiedergabedaten objektiv nicht unterscheidbar sind, kann objektiv gesehen, kein subjektiver Unterschied festgestellt werden.

Allein die digitale Repräsentation von ursprünglich analogen Signalen, sorgt für eine Verzerrung. Das Grundproblem eines Codierers besteht zunächst darin, diese Verzerrung des Analogsignals nach Möglichkeit zu minimieren. Da ein Codierer dieses Signal aufgrund der Kompression zusätzlich verzerrt. Das macht eine Evaluation eines sog. Codecs (Kunstwort:Codierer-Decodierer) mit einem subjektiven Testverfahren nötig.

Eines dieser subjektiven Qualitätskriterien ist der MOS: ausgeschrieben Mean Opinion Score, manchmal wird er auch als Mean Opinion Scale bezeichnet. Es ist die populärste Methode der Evaluation von Sprach und Audiodaten und nach ITU-T P.800 spezifiziert. Mit dieser Skala klassifiziert man die Qualität eines codierten Signals mit Hilfe einer fünfstufigen Skala. Das Resultat ist eine Fließkommazahl und eine gemittelte Größe der angegebenen Beurteilungen. Diese Beurteilung erfolgt durch geübte oder ungeübte Menschen, was dazu führt, dass die Resultate der Beurteilung nicht immer einfach zu wiederholen sind, weil es sich um eine statistische Erhebung handelt. Diese statistische Erhebung ist sowohl von der Tagesform derjenigen die Beurteilen, als auch von der des verwendeten Testmaterials abhängig und können von Test zu Test variieren. Besonders bei Audiodaten hängen die Ergebnisse es sehr stark von den verwendeten Testdaten ab, ob ein codiertes Signal mit einer 5 (Bestnote) oder einer 1 (schlechteste Note) bewertet wird oder natürlich irgendwo dazwischen.

MOS - Score	Qualität	Wahrnehmbarkeit
5	Exzellent - (excellent)	Fehler sind nicht wahrnehmbar bzw.
4	Gut - (good)	Fehler sind wahrnehmbar, aber nicht störend.
3	Ordentlich - (fair)	Fehler sind nur leicht störend. (Es bedarf einer leichten Anstrengug, um die Sprache zu verstehen.)
2	Mäßig - (poor)	Die Fehler sind störend. (Es bedarf einer großen Konzentration, um die Kommunikation sicherzustellen.)
1	Mangelhaft - (bad)	Die Fehler sind extrem störend. (Trotzt großer Anstrenung ist keine Kommunikation möglich.)

Ein Beispiel für die notwendige Evaluation der verschiedenen bekannten Codecs, ist die Möglichkeit Sprache über IP-Datenverbindungen (sog. Voice over IP - VoIP) zu übertragen. Ein Telekommunikations-Dienste-Anbieter kann auf die Idee kommen, Sprachinformationen innerhalb seines Netzes codiert zu übertragen und am Ein- und Ausgang des Netzes zu wandeln, um die internen Kosten zu senken. Das Resultat ist, dass die Sprachverständlichkeit sinkt. Wird diese Art der Übertragung der Daten im Netz durch durch mehrere Anbieter vorgenommen, so leidet das ursprüngliche Sprachsignal erheblich. Diesen Vorgang nennt man Tandem-Codierung und wird natürlich ebenso evaluiert. Also die zwei- oder dreimalige Codierung und Decodierung nacheinander.

Die Tabelle ist nach absteigender Bitrate codiert.
Standard	Codierverfahren	Bitrate	MOSwert	Verzögerung in ms	Anwendungsbereich
G.711	PCM - (Puls Code Modulation - µ-Law-Codierung)	64kbit	4.1	0.75	Audio und Sprachkompression
G.726	ADPCM - (Adaptive Differenz Puls Code Modulation)	32kbit	3.85	1.0	Audiokompression
G.728	LD-CELP - (LowDelay-Code Excited Linear Predicton)	16kbit	3.61	3-5ms	Sprachkompression
G.729	CS-ACELP - (Konjugierte Struktur - ACELP)	8kbit	3.92	10	Sprachkompression
G.729	Tandem 2fach	8kbit	3.27	20	Sprachkompression
G.729	Tandem 3fach	8kbit	2.68	30	Sprachkompression
G.729a	CS-ACELP	8kbit	3.70	10	Sprachkompression
G.723.1	MP-MLQ - (Multipuls-Maximum Likelihood Quantisierung)	6.3kbit	3.9	30	Sprachkompression
G.723.1	ACELP - (Algebraic Code Excited Linear Prediction)	5.6kbit	3.65	30	Sprachkompression

Text- und Datenkompression

Wie oben ausgeführt unterscheidet man zwischen Redundanz und Irrelevanz, bei der Text oder Datenkompression benutzt man ausschließlich Verfahren zur Redundanzvermeidung. Denn die Originalinformation muss eineindeutig aus den komprimierten Daten rekonstruierbar sein. Man spricht hierbei von einer verlustfreien Codierung. Die Möglichkeiten zur Redundanzvermeidung sind jedoch begrenzt. Das heißt es gibt eine untere Grenze. Nicht jede Art von Daten kann weiter komprimiert werden. Näheres zu dieser Problematik finden sie im Kapitel das den informationstheoretischen Grundlagen gewidmet ist.

Die untere Grenze gibt an, wie viel (Speicher)/Kanal-Kapazität mindestens bereitgestellt werden muss, um eine gewünschte Information fehlerfrei auf einem Kanal zu übermitteln. Es gibt kein mathematisches Verfahren mit dem diese Grenze weiter nach unten verschoben werden kann. Gleichwohl man heute den Eindruck bekommt, dass die Kompressionsverfahren immer besser werden. Das werden sie auch, jedoch nähern sie sich immer mehr an die geschätzte Informationsdichte von 1.7 bit/Symbol bei deutschen und englischen Texten an.

Die Verfahren zur Text- und Datenkompression werden auch für die Verfahren der Bild-, Audio-, Sprach und Videocodierung verwendet, weswegen die Verfahren zur Text- und Datenkompression als erste besprochen werden. Sie stellen quasi die Vorstufe zur verlustbehafteten Codierverfahren dar.

Die Text- und Datenkompression vermindert die sog. Redundanz, indem es häufig vorkommende Wortpassagen, Wortgruppen, Buchstabengruppen, Buchstaben besonders codiert. Es wird zumeist eine sog. Phrase codiert. Das ist eine Gruppe von Buchstaben, die aufgrund ihrer Umgebung zu erwarten waren und deswegen eigentlich nicht übertragen werden müssten. Diese Beschreibung scheint auf den ersten Blick sehr dürftig, ist aber das, was diese Verfahren gemeinsam haben. Sie codieren die Phrasen direkt oder versuchen vorherzusagen, welches Symbol als nächstes im zu codierenden Symbolstrom zu erwarten ist. Neben der Phrasencodierung findet man Verfahren, die eine Schätzung für das nächste Symbol der Nachricht abgeben. Aber eine echte Trennung zwischen Phrasencodierung und Symbolwahrscheinlichkeit kann man heute nicht mehr vornehmen. Ich trenne zwar zwischen Statistischen Verfahren und Verfahren zur Phrasencodierung, aber die Trennung wird mit jedem neuen Verfahren, dass die eine Gruppe mit der anderen kombiniert immer schwieriger.

Der Algorithmus der für die Kompression allgemeiner Daten verwendet wird, muss in der Lage sein, sich an beliebige Daten anpassen zu können, damit ein akzeptables Verhältnis zwischen Aufwand und Kompressionsleistung erreicht wird. Es wird also ein universeller Codiermechanismus gefordert. Die Daten die der Algorithmus bekommt, haben für den Algorithmus keinerlei Bedeutung. Nachteilig dieser Universalität ist die Kompressionsleistung.

Bei der Textkompression ist das schon etwas Anders. Dem Codierer werden ausschließlich textuelle Daten präsentiert. Wenn der Codierer darauf hin optimiert wurde, mit textuellen Daten umzugehen, so wird sich mit einem derartigen Codierer, ein besseres Ergebnis erzielen lassen, in Vergleich zu einem universellen Datenkompressionsalgorithmus. Das Wissen, um welche Art von Daten es sich handelt, verbessert in den meisten Fällen die Codiereffizienz erheblich. Man nutzt dabei die sog. a priori Wahrscheinlichkeit aus.

Audio-, Sprach-, Video- und Bildkompression

Hat man die Möglichkeit, Verfahren zur Irrelevanzreduktion einzusetzen, so kann man die Datenmenge ganz erheblich reduzieren und somit die mathematische Grenze, die den Verfahren mit verlustfreier Codierung gesetzt sind, nahezu problemlos unterschreiten. Der Nachteil ist, dass die Information zwar eindeutig decodierbar ist, aber die decodierte Information nicht mit der Originalinformation übereinzustimmen braucht. Das zeigt sich in Form von Fehlern, wenn man die originalen und die rekonstruierten Daten miteinander vergleicht. Dieser Fehler wird als Kompressionsverlust bezeichnet.

Audiokompression

Wenn man a priori weiß, es handelt sich um Daten, die speziell dafür verwendet werden, sie mit einem Lautsprecher wiederzugeben, so kann man den zu codierenden Daten einen bestimmten Sinn zuordnen. Man kann anhand der Daten herausfinden, ob

sie laut oder leise sind,
sie tonal oder nichttonal sind oder ob
sich gewisse Parameter zeitlich verändern.

Wenn man zusätzlich ein besonderes Wissen über das menschliche Gehör hat und aus Erfahrung weiß, an welchen Stellen die Wahrnehmung des Menschen begrenzt ist, so kann man die nicht benötigten Daten vor der Übertragung weglassen und reduziert somit die zu codierende Datenmenge. Um die Daten jedoch weglassen zu können, müssen sie zumeist transformiert werden, damit man die relevanten und nicht relevanten Anteile überhaupt voneinander trennen kann. Der Codierer berechnet beispielsweise, dass es einen sehr lauten Ton gibt, welcher einen leisen Ton vollständig überdeckt, d.h. vom menschlichen Zuhörer nicht wahrnehmbar ist. Also überträgt man zum Empfänger nur die Informationen über den lauten Ton und verschweigt ihm, dass es diesen einen leisen Ton überhaupt gegeben hat. Der Decodierer übernimmt anschließend die Aufgabe ein Signal nach der Vorgabe des Codierers zu erzeugen. Dieses vom Decodierer synthetisierte Signal enthält diesen leisen Ton aber nicht mehr.

Der Codierer interpretiert die zu codierenden Daten völlig anders, als es ein universeller Datenkompressionsalgorithmus tun würde. Die einzelnen zu übertragenden Parameter werden anschließend mit den klassischen Verfahren der Datenkompression verarbeitet und anschließend übertragen. Diese Vorgehensweise macht die Codierung von Audiodaten erst richtig effizient. Mit der Entscheidung des Codierers, welche Informationen übertragen werden oder nicht, kann dieser sogar dafür sorgen, dass eine vorher bestimmte maximale Datenmenge den Codierer verlässt. Das äußert sich darin, dass man entweder eine konstante oder variable Bitrate festlegt, oder man versucht eine bestimmte Gesamtdatenmenge zu unterschreiten.

Der Decodierer übernimmt die Synthese des transformierten Signals und sorgt damit anschließend dafür, dass das übertragende Audiosignal wiedergegeben werden kann. Es ist dabei unerheblich, ob es sich um ein Mono-Signal handelt, ob es sich um ein Stereo-Signal handelt oder ob es sich um ein Mehrkanal-Signal handelt. Das interessante an der Codierung mehrerer Kanäle ist, dass man diese Informationen noch besser miteinander verknüpfen kann und somit eine noch bessere Kompression erreicht. Weil die Informationen auf dem rechten bzw. linken Kanal ähnlich, bzw. korreliert sind.

Sprachkompression

Bei der Sprachkompression verhält es sich ähnlich wie bei der Audiokompression, nur ist das entscheidende Kriterium bei der Sprachkompression nicht das Wissen darüber, wie ein Mensch hört, sondern, wie die menschliche Sprache entsteht. Wir besitzen die Stimmbänder und die Mundhöhle, um unsere Sprache zu synthetisieren bzw. zu modulieren. Dazu verändern wir zeitlich abhängig mit den Muskeln die Stellung und die Form des lautbildenden Systems. Außerdem spielt bei der Sprachübertragung eine Rolle, dass der größte Teil der Sprachinformation im Frequenzbereich von 400 Hz bis 3400 Hz liegt. Also reicht es aus, sich bei der Sprachkompression auf diesen Frequenzbereich zu beschränken. In diesem Fall wird ein Großteil des menschlichen Hörvermögens ignoriert.

Gelingt es, nun auf der Empfangsseite eine Sprachsynthese vorzunehmen, die genau so klingt wie der Sender der Information, so muss man nur die Parameter übertragen, die diese Synthese ermöglichen. Derartige Parameter sind weitaus effizienter codierbar als das eigentlich gesprochene (modulierte) Signal. Damit sind anschließend Datenraten möglich, die nur ein Hundertstel dessen umfassen, was eine CD für nur einen Kanal benötigt. Wenn man sich vor Augen führt, dass man den Anrufer (Sender) am „anderen Ende“ der Telefonleitung immer noch versteht, ist das schon sehr erstaunlich. Versuchen Sie mal ein Buch zu lesen und zu verstehen, indem nur jeder hundertste Buchstabe gedruckt ist und der Rest frei gelassen wird. Es wird schon extrem schwierig, wenn nur jeder zehnte Buchstabe gedruckt worden wäre.

Wie man am Beispiel der Sprachkompression gut sehen kann, ist eine Codierung um so besser möglich, je mehr man über die zu codierenden Daten weiß. Aus diesem Grund gibt es unter anderem verlustfreie Audiokompressionsalgorithmen, die sich speziell um die Audiodaten kümmern und so Audiodaten besser verlustfrei komprimieren können als ein universelles Datenkompressionsverfahren.

Bildkompression

Die moderne Bildkompression macht sich die Beschränkungen des menschlichen Sehapparates zunutze. Es soll damit nicht gesagt werden, dass er nicht hochwertig ist, sondern vielmehr soll verdeutlicht werden, welche Komplexität er hat. Nahezu alle Tiere sind nicht in der Lage, farbig zu sehen. Wir können das. Was wir auch können, ist helle und dunkle Flächen besser voneinander unterscheiden, als zwischen den verschiedenen Farben zu differenzieren. Somit werden die Daten von fast allen Bildkompressionsalgorithmen zunächst einer Farbraumtransformation unterzogen, die Farbe (Chrominanz) und Helligkeiten (Luminanz) separiert. Anschließend können die Informationen entsprechend dem menschlichen Sehvermögen verarbeitet und komprimiert werden. Auch hier werden beispielsweise Informationen einfach weggelassen, die wir nicht erfassen würden.

Videokompression

Die moderne Videokompression geht noch einige Schritte weiter und komprimiert nicht mehr jedes Standbild einzeln, sondern übernimmt Informationen aus den letzten Bildern, da sich diese im Bruchteil einer Sekunde nicht grundlegend verändern. Zumindest nicht dann, wenn es eine längere Szene gibt. Man stelle sich dazu einen Nachrichtensprecher vor, der vor dem immer gleichen Hintergrund präsentiert wird. Diese konstante Information braucht nicht jedes mal aufs neue übertragen zu werden. Es reicht, in diesem Fall nur Veränderungen zu übertragen, die sich seit der letzten Standbildaufnahme ereignet haben. Es gibt kein modernes Videokompressionsverfahren mehr, welches ohne diese Art der Modellbildung auskommt. Es ist zu erwarten, dass moderne Verfahren dazu führen werden, dass Videos in DVD-Qualität bald wieder auf eine CD passen werden. Doch statt den Weg zu kleineren Medien zu gehen, wird man die Farbtreue, die Auflösung und die Audioqualität so verbessern, dass dieser Vorteil wieder kompensiert wird. Diesen Codiervorteil erreicht man auch in der Videokompression fast ausschließlich durch Modellbildung, und diese hat einen entscheidenden Nachteil: Der Codierer und der Decodierer werden mit jedem neuen Modell komplexer und algorithmisch immer aufwendiger.

Es gibt eine Vielzahl von Modellen und Algorithmen, mit denen der Codierer visuelle Redundanzen entfernt. Das könnte er nicht, wenn er nicht auf diese Art von Daten spezialisiert wäre und die Daten entsprechend ihrer vorgesehenen Nutzung interpretieren würde. Aus diesem Grund trennt man die universelle Datenkompression von den anderen Datenkompressionsalgorithmen, die auf bestimmte Daten spezialisiert sind. Spezialisierte Kompressionstechniken sind auf speziellen Daten immer im Vorteil. Aber nochmal, jedes dieser spezialisierten Verfahren, setzt auf eines dieser universellen Verfahren auf.