Was ist der Entscheidungsgehalt H0 einer diskreten Quelle?
Er ist der maximal mögliche mittlere Informationsgehalt;
(H0 = ld(M) [bit], wobei M die Anzahl der Quellenzeichen ist (ld = Logarithmus zur Basis 2), bei Gleichverteilung gilt H(Q) = H0.)
Wie ist der Informationsgehalt I(q_i) eines Zeichens definiert?
I(q_i) = ld(1/p(q_i)) = −ld(p(q_i)) [bit]. — Seltene Zeichen (kleines p) tragen viel Information; ein Zeichen mit p=1/2 trägt 1 bit.
Was ist die Entropie H(Q) einer Quelle?
Der mittlere Informationsgehalt: H(Q) = −Σ p(q_i)·ld(p(q_i)) [bit/Zeichen]. — Es gilt stets 0 ≤ H(Q) ≤ H0; maximal bei Gleichverteilung.
Was bedeutet Gleichverteilung informationstheoretisch?
Alle M Zeichen treten mit p = 1/M auf; jedes hat denselben (maximalen) Informationsgehalt, und H(Q) = H0 = ld(M). — Beispiel: 10 gleichverteilte Ziffern → I = H0 = ld(10) ≈ 3,32 bit.
Was ist Redundanz einer Quelle?
R_Quelle = H0 − H(Q) ≥ 0 [bit]: der „überflüssige“, aus anderen Anteilen herleitbare Teil der Nachricht. — Beispiel: in natürlicher Sprache kann man fehlende/verstümmelte Buchstaben oft rekonstruieren.
Was ist Irrelevanz?
Anteile einer Nachricht, die für den Empfänger keine Bedeutung haben, weil er sie nicht wahrnehmen kann (physiologische/technische Grenzen).
Beispiel: Audiofrequenzen > 20 kHz, sehr hohe Bildwiederholraten; Basis verlustbehafteter Kompression (JPEG, MP3).
Unterschied Redundanzreduktion vs. Irrelevanzreduktion?
Redundanzreduktion: entfernt vorhersagbare Anteile → reversibel/verlustlos (Datenkompression,
z. B. ZIP). Irrelevanzreduktion: entfernt nicht wahrnehmbare Anteile → irreversibel/verlustbehaftet (Datenreduktion, z. B. MP3, JPEG). — Knackpunkt: verlustlos ↔ verlustbehaftet.
Wann ist eine Codierung effizient, und was ist die mittlere Codewortlänge?
Effizient, wenn die mittlere Codewortlänge minimal ist. n̄ = Σ p(q_i)·n(q_i) [bit/Zeichen], wobei n(q_i) die Codewortlänge von q_i ist. — Coderedundanz R_Code = n̄ − H(Q).
Was ist ein präfixfreier Code (Präfixcode)?
Ein Code, bei dem KEIN Codewort der Anfang eines anderen Codeworts ist.
Vorteil: kein Trennzeichen nötig, eindeutige Decodierung über den Codebaum (Codewörter sitzen nur an Blättern).
Was ist ein Huffman-Code?
Ein präfixfreier Binärcode mit der kürzest möglichen mittleren Codewortlänge für ein gegebenes Quellenalphabet → Optimalcode.
Häufige Zeichen erhalten kurze, seltene lange Codewörter; Konstruktion über einen binären Baum.
Verfahren: Konstruktion eines Huffman-Codes?
1) Zeichen nach fallender Wahrscheinlichkeit sortieren.
2) Die zwei kleinsten Wahrscheinlichkeiten zu einem Knoten p_i+p_j zusammenfassen.
3) Knoten neu einsortieren.
4) Schritte wiederholen, bis nur die Wurzel (1,0) bleibt.
5) Zweigen 0/1 zuordnen;
Codewort = Folge von der Wurzel zum Blatt.
Aufgabe (Huffman): Q={a,b,c,d} mit p=0,4/0,3/0,2/0,1 – Codewörter und mittlere Länge?
Zusammenfassen:
c+d=0,3; dann b+[cd]=0,6; dann a+0,6=1,0.
Codewörter z. B. a=0, b=10, c=110, d=111.
Mittlere Länge n̄ = 0,4·1+0,3·2+0,2·3+0,1·3 = 1,9 bit/Zeichen
Wie prüft man, ob ein Huffman-Code präfixfrei ist?
Prüfen, dass kein Codewort Anfang eines anderen ist; bei Huffman ist das automatisch erfüllt, da alle Zeichen auf BLÄTTERN des Codebaums liegen.
Damit ist eindeutige Decodierung ohne Trennzeichen garantiert.
Was ist die Lauflängencodierung (Run Length Encoding, RLE)?
Verlustlose Redundanzreduktion:
Läufe (wiederholte Zeichen) werden durch (Lauflänge, Zeichen) ersetzt.
Beispiel: aaaaabbb → 5a3b.
Problem:
wenig Gewinn bei kurzen Läufen;
bei Ziffern im Text feste Stellenzahl m für die Lauflänge nötig.
Was ist die Substitutionscodierung (Wörterbuchverfahren)?
Verlustfreie Codierung:
wiederholt auftretende Zeichenketten werden durch Verweise auf ein dynamisch aufgebautes Wörterbuch ersetzt.
Grundlage der Lempel-Ziv-Familie (LZ77/LZ78); hoher Kompressionsgrad bei strukturierten Daten.
Verfahren: LZ77-Algorithmus?
Mit Such-Fenster S (Wörterbuch) und Vorschaufenster L:
suche im S die längste Übereinstimmung mit dem Anfang von L;
gib Token <Offset, Länge, nächstes Symbol> aus und schiebe das Fenster weiter.
Knackpunkt: Offset = Abstand zurück zum Match-Beginn, Länge = Anzahl übereinstimmender Zeichen; bei keinem Treffer „Nullphrase“ <0,0,Zeichen>.
Aufgabe (LZ77): Token <6,2,I> – wie liest man das?
Gehe 6 Zeichen zurück im bereits übertragenen Text, übernimm 2 Zeichen von dort und hänge dann das neue Zeichen 'I' an.
Decoder baut so sein Wörterbuch beim Empfang Stück für Stück selbst auf (sehr einfach).
Warum ist LZ77 verlustfrei?
Es werden nur Verweise auf bereits gesendete identische Zeichenketten plus das jeweils nächste Originalzeichen übertragen – keine Information geht verloren.
Eignet sich daher für Texte, Programmcode, DNS-Sequenzen usw. (z. B. ZIP, PNG-Deflate).
Worauf basieren Redundanzreduktion-Verfahren grundsätzlich?
Im Wesentlichen auf der Statistik der Quellensymbole (Häufigkeiten, Wiederholungen).
Huffman nutzt Auftrittswahrscheinlichkeiten, RLE/LZ nutzen Wiederholungen/Muster.
Wie groß ist die Codewortlänge eines Blockcodes im Vergleich zu Huffman?
Blockcode: feste Länge n = ld(M) aufgerundet, alle gleich lang.
Huffman: variable Länge, mittlere Länge ≤ Blockcode-Länge, näher an der Entropie.
Was ist die modifizierte Huffman-Codierung beim Telefax (CCITT)?
Kombination aus Lauflängencodierung (weiße/schwarze Pixelläufe) und fester Huffman-Codetabelle für die Lauflängen.
Was unterscheidet LZ77 von einem reinen Huffman-Code?
Huffman nutzt die Auftrittshäufigkeit einzelner Zeichen (statistisch).
LZ77 nutzt Wiederholungen von Zeichenketten (Wörterbuch/Verweise).
Zuletzt geändertvor 9 Tagen