Codierung und Datenkompression

analoganalog

wertdiskretewertdiskrete

zeitdiskretezeitdiskrete tt

Y(t)Y(t)

tt

Y(t)Y(t)

Y(t)Y(t)

DigitalisierungAbb.1.1

tt

Qelle Qellen-encodierung

Kanal-codierung Modulation

Kanalubertragung, Speicherung

DemodulationFehlerkorrekturEmpfänger Qellen-decodierung

Datenkompression

Codierung DatenreduktionDekorrelation

132

Ein Zeichen, Symbol oder Ereignis sei mit Si bezeichnet. Dann umfasst das Alphabet

Z = {si} mit i = 1,2,...,K die Menge aller vorkommenden (unterschiedlichen) Symbole.

Signale werden mit x[n] beschrieben, wobei die eckigen Klammern symbolisieren, daß das Signal zeitdiskret ist. x[n] ist gleichzeitig als endliche Folge von Symbolen aus Z zu betrachten.

• Jedes Ereignis si besitzt eine Auftretenswahrscheinlichkeit pi

• In Abhängigkeit von pi ermittelt man den Informationsgehalt des Symbols I(si) mit:

i 2i

1I s =log

P2.1

Die Einheit des Informationsgehaltswird in l bit (analog zu l Volt) angegeben.

Aus Gleichung (2.1) kann abgelesen werden, dass der

Informationsgehalt eines Ereignisses umso kleiner ist, je Informationsgehalt eines Ereignisses umso kleiner ist, je häufiger das Ereignis auftritt.häufiger das Ereignis auftritt.

Oder anders gesagt: je überraschender das Auftreten eines Symbols, desto größer die damit verbundene Information.

Am Beispiel der Wettervorhersage soll die Verwendung des Informationsgehalts demonstriert werden.

I[bit] I[bit]

Tabelle 2.1: Wetterinformation, links: gleichverteiltes Wetter, rechts: Ergebnis einer Langzeit-Observation

?

Wir befinden uns in einem sehr frühen Stadium der Wetterforschung und unterscheiden lediglich vier Zustände: Sonne, Wolken, Regen und Schnee

I[bit] I[bit]

?

Beobachtungen über einen längeren Zeitraum ergeben allerdings eine andere Verteilung des Wetters (Tab. 2.1 rechts).

• Hier stellt sich die Frage, welche Codewörter den Symbolen Sonne bis Schnee zugewiesen werden müssen, um eine optimale Codierung zu erreichen.

• An dieser Stelle lässt sich aber bereits vermuten, dass der neue Code variable Längen aufweist, während die der neue Code variable Längen aufweist, während die alten Codewörter eine feste Länge von 2 Bits habenalten Codewörter eine feste Länge von 2 Bits haben.

• Jedes Codewort kann durch einen Codewert und eine Codelänge definiert werden. Die Länge gibt die Anzahl der zusammenhängenden Bits an.

• Der Codewert ist derjenige Zahlenwert, der sich bei Interpretation des Codewortes als binäre Zahl ergibt. Das Codewort „00011" zum Beispiel hat eine Codelänge von 5 Bits und einen Codewert von 3.

• Die Gesamtheit aller Codewörter eines Die Gesamtheit aller Codewörter eines Alphabets wird als Code bezeichnet.Alphabets wird als Code bezeichnet.

Die Frage ist, wie viel bit erforderlich sind, um die Information einer n- stelligen Zahl eines b- wertigen Zahlensystems zu beschreiben. Die größte, mit n Ziffern darstellbare Zahl jedes Zahlensystems beträgt

Löst man die Gleichung nach der Anzahl der binären Stellen k auf, erhält man

1nb

1 2 1n kb

2

log bk=n. =n.log b

log 2

Daraus ergibt sich zum Beispiel, dass eine Ziffer des dezimalsystems einer Information von log2(10) 3.32 bit entspricht.

2

3

4

10 1 99

10 1 999

2 1 15

• Für die Berechnung des mittleren Informationsgehalts einer Folge von statistisch unabhängigen Symbolen verwendet man

die Entropie H. Sie berechnet sich aus der Summe der gewichteten Einzelinformationen

k

i 2i=1 i

1H= p .log

p[bit/Symbol]

[2.2]

Die Einheit ist 1 bit pro Symbol. Der Wertebereich der Entropie ist durch die Anzahl verschiedener Symbole K definiert

20<H<log k

• Die Entropie hat ihren höchsten Wert, wenn alle Symbole gleichverteilt sind (pi = 1/K)

k

max 2 2i=1

1H = .log log

KK K

Je ungleichmäßiger die Symbole verteilt sind, desto geringer ist der Informationsgehalt des Signals.

Der Extremfall H = 0 ist erreicht, wenn nur ein einziges Symbol des Alphabets im Signal vorkommt K=1

i

1.0 i=jH=0 wenn p =

0.0 i j

Entropie eines binären Signals als Funktion der Symbolwahrscheinlichkeit pi

0 0.2 0.4 0.6 0.8 1.0

1.0

0.8

0.6

0.4

0.2

0

H=f(Pi)

Pi

Kommen wir nun noch einmal zur Übermittlung von Wetterdaten zurück. Wie groß ist der mittlere Informationsgehalt der Nachrichten an die Zentrale bei ungleichmäßiger Verteilung des Wetters entsprechend Tabelle 2.1 rechts?

Die Entropie beträgt nach Gleichung (2.2)

Hsrc =0.5.1 bit + 0.25 • 2 bit + 0.125 • 3 bit + 0.125 • 3 bit = =1.75 bit/Symbol .

Für die Datenkompression bedeutet dies, es muss einen Weg geben, die vier Wetterlage im Durchschnitt mit weniger als 2 Bits pro Nachrichtzu unterscheiden.

Redundanz

4 0.3p 0 1 2 0.2p p p 3 0.1p

Als Codierungsredundanz wird die Differenz zwischen der durchschnittlichen Datenmenge pro Symbol und der Entropie des Signals Hsrc bezeichnet

Ein Signal bestehe aus fünf verschiedenen Symbolen mit

codR

cod src srcR S H

Die Entropie des Signals beträgt nach Gl. (2.2) somit rundHsrc 2.246. Der Speicheraufwand beträgt bei Verwendung von festen Codelängen mindestens Ssrc = log2 K = 3 Bits pro Symbol. Die Codierungsredundanz beträgt demzufolge

3 2.246 0.754 bit/SymbolcodR

Beurteilung von Kompressionsalgorithmen.

• Ziel der Bewertung ist der Vergleich zwischen verschiedenen Codierungsstrategien.

Kompressionsrate

Die Kompressionsrate ergibt sich aus dem Verhältnis von Datenmenge des ursprünglichen Signals und der Datenmenge des codierten Signals

Kriterien zur Kompressionsbewertung

( )( S )R

Datenmenge OriginalsignalCDatenmenge codiertes ignal

• Oft wird die Kompressionsleistung die Kompressionsleistung mit Hilfe der Bitrate angegeben. Die Bitrate entspricht der Datenmenge NB (in Bits) des codierten Signals bezogen auf die Anzahl NA der Symbole

[bit/Symbol]BR

A

NN

Für Bilddaten wird die Bitrate meist in bit pro Bildpunkt (engl.: bit per pixel [bpp]) angegeben.

Signalqualität

Die Bewertung der Signalqualität ist für die Einschätzung von verlustbehafteten Kompressionsverfahren von Interesse. Grundsätzlich wird zwischen objektiver und subjektiver Beurteilung der Qualität unterschieden.

Objektiv bedeutet, dass ein Computerprogramm das Original mit dem veränderten, auf der Empfängerseite rekonstruierten Bild vergleicht und die Unterschiede der Helligkeits und Farbwerte in einer Zahl zusammenfasst. Subjektive Qualitätsbewertung setzt im Gegensatz dazu mehrere Testpersonen voraus, die ihr Urteil zur Qualität abgeben.

Verzerrungsmaße• Mittlerer quadratischer Fehler (engl.: mean square error)

2

1

1 NMSE i i

ix x

N

Große Differenzen zwischen den Signalwerten werden durch das Quadrieren stärker gewichtet als kleinere Differenzen.

1

1.

N

i ii

MAD x xN

Mittlerer absoluter Fehler (engl.: mean absolute difference)

Dieses Maß verzichtet auf das Quadrieren und wird eingesetzt, wenn es auf eine schnellere Berechnung ankommt.

Summe der absoluten Fehler (engl.: sum of absolute difference/distortions)

1

N

i ii

SAD x x

Der SAD-Wert unterscheidet sich vom MAD lediglich durch die fehlende Division durch N. Für ausschließlich vergleichende Zwecke ist diese Normierung nicht erforderlich und die Berechnung wird dadurch beschleunigt.

Qualitätsmaße

Signal-Rausch-Verhältnis (engl.: signal-to-noise ratio)Das Signal-Rausch-Verhältnis ist ein Qualitätsmaß und hat im Gegensatz zu der vorangegangenen Verzerrungsmaßen einen steigenden Wert mit steigender Qualitäl des rekonstruierten Signals. Es wird in Dezibel angegeben

2

10 210.log x

e

SNR dB

ist die Varianz des Originalsignals und berechnet sich nach2x

N 22

i ii=1 1

1 1. x - x mit x . x

N

xiN N

ist entsprechend die Varianz des Rekonstruktionsfehlers e[n] = x[n] — x[n]. Falls der Rekonstruktionsfehler mittelwertfrei ist, sind Fehlervarianz und MSE identisch

N N 222

ii i ii=1 i=1

1 1. e - 0 . x - x mit e 0e N N

2e

Ziel ist die Zuordnung von Codewörtern (Bitfolgen) derart, dass die mittlere Bitrate minimiert.

Es wird versucht, jedem Symbol nur so viele Bits zuzuordnen, wiees aufgrund des Informationsgehalts des Symbols erforderlich ist. Symbolen mit hoher Auftretenswahrscheinlichkeit werden kurze Codewörter zugewiesen, während seltene Symbole längere Codewörter erhalten.

Die Theorie der Codierung, wie wir sie heute verwenden, geht auf Claude E. Shannon zurück

Codierungstheorie

k sei die Länge jenes Codewortes ci, das dem Symbol si

mit der Auftretenswahrscheinlichkeit pi zugeordnet wird. Die mittlere Codelänge einer Symbolfolge kann dann mit

1

. Bits/SymbolK

i i ii

l p l

angegeben werden, wenn die Signalquelle K verschiedene Zeichen produziert.

4.1

Die niedrigste Bitrate wird erreicht, wenn ein Code den kleinsten Wert für li liefert. Die entscheidende Frage ist nun, ob

es eine untere Grenze für die mittlere Codelänge gibt und wenn ja, wie groß sie ist.

Shannon hat 1948 bewiesen, dass li stets größer oder mindestens gleich der Quellenentropie Hsrc ist.

Darüber hinaus hat er gezeigt, dass immer ein Code gefunden werden kann, der eine Übertragung mit weniger als Hsrc + l bit pro Abtastwert ermöglicht.

1src i srcH l H

In Tabelle 4.1 ist ein Beispiel für ein Symbolalphabet mit K = 4 Zeichen angegeben. Auf Basis der Wahrscheinlichkeiten ergibt sich für jedes Symbol nach Gleichung (2.1)

i 1 2 3 4

si a b c d

pi 0.4 0.2 0.1 0.3

Ii[bit] 1.32 2.32 3.32 1.74

Ci 00 01 10 11

k 2 2 2 2

Tabelle 4.1

Die Entropie beträgt somit laut Gleichung (2.2) Hsrc = 0.4 • 1.32 + 0.2 • 2.32 + 0.1 • 3.32 + 0.3 • 1.74 = 1.846 bit/Symbol.

Den Symbolen wurden Codewörter mit einer festen Länge von li= l = log2(4)= 2 Bits zugeordnet.

Die durchschnittliche Codelänge beträgt entsprechend Gl. (4.1)k = 0.4 • 2 + 0 . 2 • 2 + 0.1 • 2 + 0.3 • 2 = 2 Bits/Symbol.

• Es ist zu erkennen, dass dieser Code die durch die Entropie vorgegebene untere Grenze nicht unterschreitet (li > Hsrc). Der Code ist aber auch schon so gut, dass er innerhalb der in Gleichung (4.2) angegebenen Grenzen liegt.

• Eine übliche Darstellungsform für Codes sind sogenannte Codebäume.

• Abbildung 4.1 zeigt den Codebaum für das Beispiel aus Tabelle 4.1. Die Symbole bilden die Blätter des Baumes und die Beschriftung der Zweige von der Wurzel bis zum Blatt entspricht dem jeweiligen Codewort.

Abbildung 4.1: Codewortbaum mit Codewörtern gleicher Länge

a b c d

0 1 1

1

0

0

i 1 4 2 3

Si a d b c

Pi 0.4 0.3 0.2 0.1

Ii[bit] 1.32 1.74 2.32 3.32

  1   0  

  - 1 0  

  - - 1 0

Ci 1 01 001 000

k 1 2 3 3

i 1 2 3 4 5 6 7

Pi 0.4 0.1 0.1 0.1 0.1 0.1 0.1

  1       0    

  1 0   1   0  

  - - 1   0 0 0

  - - 1 0 - - -

Ci 11 10 0111 0110 010 001 000

Si Piab

cd

0.40.20.1

0.3

1

11.0

00

1

0.3

0 0.6

i 1 2 3 4

Si a b c d

Pi 0.4 0.2 0.1 0.3

Ci 1 011 010 00

k 1 3 3 2

i Ci li

1 1 1

2 011 3

3 010 3

4 0011 4

5 0010 4

6 0001 4

7 0000 4

i Pi

1

2

3

4

5

6

7

0.4

0.1

0.1

0.1

0.1

0.1

0.1

1

11

0.2

0.2

0.2

11

1

0

0

0

0

0.6

0.4

0

0

1.0

i Ci li

1 11 2

2 010 3

3 100 3

4 011 3

5 010 3

6 001 3

7 000 3

i Pi

1

2

3

4

5

6

7

0.4

0.1

0.1

0.1

0.1

0.1

0.1

1

11

0.2

0.2

0.2

11

1

0

0

0

0

0.6

0.4

0

0

1.0