/ Informatik

Informationstheorie

Shannon-Entropie, Informationsgehalt, Redundanz, Kodierungseffizienz, Huffman, Kanalkapazität, Bitfehlerrate, Hamming-Distanz und -Prüfbits, Parität sowie CRC.

13 Rechner in dieser Kategorie, jeweils mit automatischer Variablen-Umstellung.

I01

Shannon-Entropie

Mittlerer Informationsgehalt einer diskreten Quelle: H = −Σ pᵢ · log₂(pᵢ). Formel hier für drei Symbole mit Wahrscheinlichkeiten p1, p2, p3.

I02

Informationsgehalt

Informationsgehalt eines Einzelereignisses: I = −log₂(p) = log₂(1/p). Seltene Ereignisse tragen mehr Information.

I03

Redundanz

Relative Redundanz einer Quelle: R = 1 − H / Hmax. Hmax = log₂(Symbolanzahl) ist die maximale Entropie bei Gleichverteilung.

I04

Kodierungseffizienz

Verhältnis aus Entropie und mittlerer Codewortlänge: Effizienz = H / L. Werte nahe 1 stehen für nahezu optimale Kodierung.

I05

Huffman min. Codewortlänge

Untere Schranke der Codewortlänge bei festen Binärcodes: MinLaenge = ⌈log₂(Symbolanzahl)⌉. Huffman erreicht diesen Wert bei Gleichverteilung.

I06

Mittlere Codewortlänge

Gewichtete mittlere Codewortlänge eines Präfixcodes: L = Σ pᵢ · lᵢ. Formel hier für drei Symbole mit Wahrscheinlichkeiten und Codewortlängen.

I07

Kanalkapazität (Shannon)

Shannon-Hartley-Theorem: C = B · log₂(1 + S/N). Obere Schranke für fehlerfreie Datenrate auf einem analogen Kanal mit Gauß-Rauschen.

I08

Bitfehlerrate (BER)

Bitfehlerrate als Quotient fehlerhafter Bits zu übertragenen Bits: BER = FehlerBits / GesamtBits. Typische Werte 10⁻³ bis 10⁻¹².

I09

Hamming-Distanz

Aus der minimalen Hamming-Distanz d eines Blockcodes folgen Erkennbar = d − 1 Fehler und Korrigierbar = ⌊(d − 1) / 2⌋ Fehler.

I10

Hamming-Code Prüfbits

Anzahl Prüfbits r für m Datenbits im (m+r,m)-Hamming-Code: kleinstes r mit 2^r ≥ m + r + 1.

I11

Parität (gerade)

Paritätsbit für gerade Parität: Paritaetsbit = Einsen mod 2. Das Bit wird so gesetzt, dass die Gesamtzahl der Einsen gerade ist.

I12

Parität (ungerade)

Paritätsbit für ungerade Parität: Paritaetsbit = (Einsen + 1) mod 2. Die Gesamtzahl der Einsen inklusive Prüfbit ist anschließend ungerade.

I13

CRC-Prüfbits

Gesamtlänge einer Nachricht mit CRC-Prüfsumme: Gesamtlaenge = Datenbits + Grad. Der Grad des Generatorpolynoms entspricht der Anzahl angehängter CRC-Bits.