Information Theory and Coding - Cheatsheet

Definition von Information und Entropie

Definition:

Information: Maß für den Informationsgehalt einer Nachricht. Entropie: Durchschnittlicher Informationsgehalt einer Quelle.

Details:

• Shannon-Entropie: \[H(X) = - \sum_{i} p(x_i) \log_2 p(x_i)\]
• Maximale Entropie, wenn alle Ereignisse gleich wahrscheinlich: \[H_{max} = \log_2 n\]
• Geringste Entropie, wenn ein Ereignis sicher: \[H = 0\]

Shannon'sche Kommunikationsmodelle

Definition:

Modell, das Kommunikationsprozesse beschreibt und mathematisch analysiert; zentrale Bestandteile sind Informationsquelle, Sender, Kanal, Empfänger und Informationsziel.

Details:

• Informationsquelle: Ursprung der Nachricht
• Sender: wandelt Nachricht in Signal um
• Kanal: Übertragungspfad, kann Störungen enthalten
• Empfänger: wandelt das empfangene Signal zurück in die Nachricht
• Informationsziel: Enddestination der Nachricht
• Mathematische Beschreibung: \(C = B \cdot \log_2(1 + \frac{S}{N})\) wobei C die Kanalkapazität, B die Bandbreite und \(\frac{S}{N}\) das Signal-Rausch-Verhältnis ist

Lineare Block-Codes

Definition:

Lineare Block-Codes sind Fehlerkorrektur-Codes, die eine feste Anzahl von Datenbits in eine größere Anzahl von Codebits transformieren, durch lineare Kombinationen der Datenbits.

Details:

• Jeder Code ist ein Vektorraum über dem endlichen Körper \(\text{GF}(q)\).
• Codes erzeugt durch eine Generator-Matrix \(G\).
• Codewort \(c = uG\), wobei \(u\) Informationsvektor ist.
• Hamming-Abstand bestimmt Fehlerkorrekturfähigkeit:
• Minimalabstand \(d_{\text{min}}\): Anzahl der Fehler, die korrigiert werden können: \(t = \frac{d_{\text{min}} - 1}{2}\).
• Empfänger überprüft Gültigkeit durch Multiplikation mit Kontrollmatrix \(H\): \(Hc^T = 0\).
• Kontrollmatrix \(H\) erfüllt \(HG^T = 0\).

Unterschiedliche Kanäle: AWGN, BSC, und erweiterte Modelle

Definition:

Unterschiedliche Modelle zur Beschreibung von Kommunikationskanälen, die verschiedene Störungsarten und Verhaltensweisen darstellen.

Details:

• AWGN-Kanal: Additive White Gaussian Noise, Rauschen mit konstanter Leistungsdichte.
• • SNR (Signal-to-Noise Ratio): Verhältnis von Signalleistung zu Rauschleistung.
• BSC (Binary Symmetric Channel): Bitübertragungskanal mit fester Fehlerwahrscheinlichkeit.
• • Übergangswahrscheinlichkeit: Wahrscheinlichkeit, dass ein Bit falsch übertragen wird, bezeichnet als \(p\).
• Erweiterte Modelle: Realistischere Abbildungen von Übertragungskanälen, z. B. Markov-Modelle.
• • Kanalmodelle mit Gedächtnis: Abhängigkeit gegenwärtiger Zustände von vorherigen Zuständen.
  • Mehrwegeausbreitung, Fading: Realistische Störungen in drahtlosen Kommunikationskanälen.

Kapazität von diskreten und kontinuierlichen Kanälen

Definition:

Kanal-Kapazität misst die maximale Informationsrate, die fehlerfrei über einen Kanal übertragen werden kann.

Details:

• Diskrete Kanäle: Kapazität C gegeben durch \[ C = \text{max}_p(X) I(X;Y) \]
• Kontinuierliche Kanäle: Kapazität hängt von Bandbreite und Signal-Rausch-Verhältnis (SNR) ab, z.B. für AWGN-Kanal: \[ C = B \log_2(1 + \text{SNR}) \]
• Shannons Theorem: Beschreibt die theoretische Grenze der fehlerfreien Übertragung.
• Wichtige Begriffe: Entropie, Mutual Information, Signal-Rausch-Verhältnis (SNR), Bandbreite.

Hamming-Codes und deren Anwendungen

Definition:

Fehlerkorrigierender Code, der einzelne Bitfehler erkennen und korrigieren kann.

Details:

• Grundlage: Hamming-Abstand
• Codewortlänge (n):
• Informationsbits (k):
• Redundanzbits (r):
• Fehlererkennung: Bis zu Bitfehler
• Fehlerkorrektur: Einzelbitfehler
• Hamming-Bedingung:
• Um Anwendung: Datenspeicherung, Kommunikation, Telekommunikation

Huffman-Codierung und arithmetische Kodierung

Definition:

Huffman-Codierung und arithmetische Kodierung sind Algorithmen zur verlustfreien Datenkompression. Während Huffman-Codierung feste Codewörter verwendet, basiert die arithmetische Kodierung auf Intervallpartitionierung.

Details:

• Huffman-Codierung:
• Bildung binärer Bäume mit minimaler Pfadlänge
• Wörter häufiger Zeichen kürzer
• Entropiebasiert optimal bei bekannten Symbolhäufigkeiten
• Algorithmus: Frequenzen ermitteln, Baum erstellen, Codes zuweisen
• Arithmetische Kodierung:
• Verwendet Intervalle zur Darstellung von Zeichenfolgen
• Je häufiger ein Zeichen, desto kleiner das zugewiesene Intervall
• Ermöglicht feinkörnigere Kompression als Huffman
• Benötigt genaue Wahrscheinlichkeiten der Zeichen
• Algorithmus: Intervall definieren, Zeichen sukzessive in Intervall einfügen, binärer String kodieren

Faltungs- und Turbo-Codes

Definition:

Faltungs- und Turbo-Codes sind Fehlerkorrekturcodes, die in der digitalen Kommunikation verwendet werden, um die Zuverlässigkeit von Datenübertragungen zu erhöhen.

Details:

• Faltungscodes: Verwenden Speicher, um Eingabedaten sequentiell zu verarbeiten.
• Turbo-Codes: Bestehen aus parallelen, rekursiven systematischen Faltungscodes.
• Konvolutionsencoder: Zustandsmaschine mit k-Eingangs- und n-Ausgangsbit, Zustände durch Shift-Register dargestellt.
• Turbo-Decoding: Iterativer Algorithmus basierend auf MAP-Decoder.
• Gewinn (in dB) von Turbo-Codes nah an Shannon-Grenze.
• Faltungs- und Turbo-Codes effizient in Anwendungen wie Mobilfunk und Satellitenkommunikation.