Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- se:informationstheorie [2009-02-24 16:01]
stefan
+++ se:informationstheorie [2014-04-05 11:42] (aktuell)
@@ Zeile 185: / Zeile 185: @@
     * die Spektralwerte können durch einen globalen Verstärkungsfaktor und Skalierungsfaktoren für bestimmte Bereiche des Spektrums abgeschwächt werden
     * Funktionsweise: der globale Verstärkungsfaktor wird variiert und nach einer erneuten Quantisierung und Codierung überprüft, ob das Ergebnis der Ausgangsbitrate entspricht und die Maskierungsschwelle eingehalten wird (evtl. Korrektur durch Anpassung der Skalierungsfaktoren)
+===== Kanalcodierung =====
+  * die Grundidee der Kanalcodierung ist die Vermeidung von Übertragungsfehlern oder die Erkennung der solchen durch gezieltes Hinzufügen von Redundanz
+  * FEC (Forward Error Control) und ARQ (Automatic Repeat Request)
+    * FEC wird verwendet, wenn es keinen Rückkanal gibt oder die Übertragungszeit für den Request und die Antwort zu lang wäre (z.B. Mobilfunk)
+    * bei PC-Netzen wird meist ARQ verwendet, da der Overhead hier keine große Rolle spielt und ARQ weniger aufwändig ist als FEC (bei gleicher Restfehlerwahrscheinlichkeit)
+  * Auswahl eines Kanalcodes abhängig von Fehlerverhalten, Bandbreite, Sendeleistung, Delay und Art der Daten (wichtige Daten brauchen bessere Absicherung)
+  * werden Nachrichten in geichgroße Blöcke aufgeteilt, handelt es sich um **Blockcodes**
+    * gibt es hierbei jedoch ein blockübergreifendes Gedächtnis, spricht man von **Faltungscodes**
+  * **Coderate**: Verhältnis von Infosymbolen zu Codesymbolen
+    * {{:se:coderatekanalcodes.jpg|}}
+  * **Hamminggewicht**: Anzahl der von Null verschiedenen Symbole eines Codewortes
+    * {{:se:hamminggewicht.jpg|}}
+    * die **Gewichtsverteilung** sind die Anzahlen der Codewörter mit Hamminggewicht 0...m
+  * **Hammingdistanz**: Anzahl der verschiedenen Symbole zweier Codewörter
+    * {{:se:hammingdistanz.jpg|}}
+    * die minimale Hammingdistanz ist die kleinste Hammingdistanz zwischen zwei unterschiedlichen Codewörtern eines Codes
+  * Kurzbezeichnung für Blockcodes: (m, n, d<sub>min</sub>)<sub>q</sub>
+  * der **Coderaum** umfasst alle m-stelligen Codewörter und dient u.a. der Darstellung von Distanzen zwischen den Codewörtern
+    * {{:se:coderaum.jpg|}}
+    * das Beispiel hat eine minimale Hammingdistanz von 2 und kann damit 1 Bitfehler bei der Übertragung erkennen
+  * mögliche Fehlererkennung: e<sub>det</sub> = d<sub>min</sub> - 1
+  * mögliche Fehlerkorrektur: e<sub>kor</sub> = (d<sub>min</sub> - 1) / 2 (abrunden)
+  * **perfekter Code** (dicht gepackter Code): alle Codeworte des Codes liegen in Korrigierkugeln mit einem Radius von e<sub>kor</sub>
+  * Decodierung: Hard-Decision (Empfangsworte stammen aus dem Codealphabet), Soft-Decision (Empfangsworte stammen aus einem größeren Alphabet)
+    * bei der Decodierung soll anhand des Empfangswortes das Wort gefunden werden, das mit der größten Wahrscheinlichkeit gesendet wurde
+      * Maximierung der A-posteriori-Wahrscheinlichkeit (MAP): p(c|r) bzw. p(u|r)
+      * wird auch Minimum Error Probability Decoding (MED) genannt, da die geringste Wortfehlerwahrscheinlichkeit erzielt wird
+    * Hard-Decision: das Codewort, das dem Empfangswort zugewiesen wird, ist dasjenige, welches die geringste Hammingdistanz zum Empfangswort aufweist
+    * Soft-Decision: Entscheidung aufgrund des Abstandsmaßes zwischen Codewort und Empfangswort (quadrierte euklidische Distanz im Coderaum)
+      * {{:se:softdecisionml.jpg|}}
+      * die feinere Quantisierung der Symbole des Empfangswortes führt zu einer geringeren quantisierungsbedingten Verfälschung und sorgt für eine Berücksichtigung der in den Symbolen enthaltenen Zuverlässigkeitsinformation
+    * um mittels Hard-Decision die gleiche Fehlerwahrscheinlichkeit zu erreichen wie mit Soft-Decision müsste man eine verdoppelte Sendeleistung aufwenden
+  * **Interleaving**: Methode zum Umgang mit Bündelfehlern (mehrere Fehler gleichzeitig: Fehlerbursts)
+    * die Codeworte werden ineinander verschachtelt, wodurch Bündelfehler sich zwar auf mehrere Worte, aber auf jedes einzeln nicht so stark auswirken
+    * Folge ist ein erhöhter Speicherbedarf und eine Übertragungsverzögerung
+==== Lineare Blockcodes ====
+  * häufig verwendet: Modulo-2-Rechnung
+    * die Ergebnisse der Modulo-2-Addition und Modulo-2-Subtraktion entsprechen sich und dem Ergebnis einer XOR-Verknüpfung
+  * Definition: ein binärer (m,n)-Code ist ein **linearer Blockcode**, wenn er ein n-dimensionalen Unterraum des Coderaums {0,1}<sup>m</sup> im Sinn der Modulo-2-Rechnung ist
+    * jede beliebige Linearkombination aus Codewörtern ergibt wieder ein Codewort
+    * damit muss in jedem linearen Blockcode auch das Nullwort enthalten sein
+    * d(c,c') = w(c-c'), damit ergibt sich die minimale Hammingdistanz aus der Suche nach dem Codewort mit dem geringsten Hamminggewicht (außer dem Nullwort)
+  * als **Restfehler** wird bei Fehlerkorrektur mittels Kanalcodes die Falschkorrektur (das ermittelte Codewort entspricht nicht dem übermittelten) bezeichnet
+    * das empfangene Codewort wurde durch Verfälschung zu einem anderen gültigen Codewort
+    * {{:se:wortfehlerwahrscheinlichkeit.jpg|}}
+    * bei linearen Blockcodes treten Restfehler genau dann auf, wenn der Fehlervektor ein vom Nullwort verschiedenes Codewort ist
+      * {{:se:wortfehlerwahrscheinlichkeit2.jpg|}}
+      * {{:se:wortfehlerwahrscheinlichkeit3.jpg|}}
+  * Schranken für die erforderliche Redundanz
+    * Singleton-Schranke: m - n >= d<sub>min</sub> - 1
+      * Codes, die dies mit Gleichheit erfüllen, heißen MDS-Codes (Maximum Distance Seperable)
+      * Beispiele: (m,1,m)<sub>2</sub>-Wiederholungscodes, (n+1,n,2)<sub>2</sub>-Paritätscodes
+    * Hamming-Schranke / Kugelpackungsschranke (Sphere-Packing Bound)
+      * {{:se:hammingschranke.jpg|}}
+      * Codes, die dies mit Gleichheit erfüllen, heißen perfekte Codes oder dicht gepackte Codes (alle Worte liegen innerhalb von Korrigierkugeln)
+      * Beispiele für perfekte Codes: (m,1,m)-Wiederholungscodes mit ungeradem m
+    * Plotkin-Schranke
+      * {{:se:plotkinschranke.jpg|}}
+      * Codes, die dies mit Gleichheit erfüllen, heißen äquidistante Codes (alle Worte haben paarweise gleiche Abstände)
+    * Gilbert-Varshamov-Schranke
+      * {{:se:gilbertvarshamovschranke.jpg|}}
+      * bei Erfüllung dieser Schranke kann auf die Existenz eines solchen Codes geschlossen werden (ohne jedoch eine Konstruktionsvorschrift anzugeben)
+  * arithmetische Beschreibung linearer Blockcodes
+    * bei der Codierung werden aus den Infowörtern durch Multiplikation mit einer **Generatormatrix** Codewörter erzeugt
+    * die Generatormatrix besteht aus n Codewörtern der Länge m
+    * ein Vertauschen der Spalten der Generatormatrix erzeugt einen äquivalenten Code mit den gleichen Parametern (aber anderen Codewörtern)
+    * ein Vertauschen der Zeilen oder das Ersetzen einer Zeile durch ihre Summe mit einer anderen Zeile ändert nicht den Code, sondern nur die Zuordnung von Codewörtern zu Infowörtern
+  * **systematische Codes** sind solche, bei denen die Infobits in allen Codeworten an der gleichen Stelle stehen (ergänzt um die Schutzbits), sie lassen sich also ohne Berechnung aus dem Codewort ablesen
+    * die Generatormatrix G hat dabei n Spalten mit jeweils nur einer 1
+    * Codewörter **klar-systematischer Codes** bestehen aus dem Infowort mit angehängten Schutzbits, d.h. die Infobits in Infowort und Codewort stehen an der gleichen Stelle
+      * die Generatormatrix weist hierbei die Zeilennormalform [E<sub>n</sub>|P] auf (n x n Einheitsmatrix + n x (m - n) Matrix für die Prüfstellen)
+    * aus jedem linearen Blockcode kann durch Anwendung der Zeilenoperationen ein systematischer Blockcode gemacht werden
+      * einen klar-systematischen (äquivalenten) Code erhält man dann ggfs. durch Spaltenvertauschung
+  * Decodierung mittels Prüfmatrix H = [P<sup>T</sup>|E<sub>m - n</sub>]
+    * das **Syndrom** eines Empfangswortes ist s = r * H<sup>T</sup> und muss für alle Codeworte 0 sein
+      * ist es ungleich 0 kann auf einen Übertragungsfehler geschlossen werden und das wahrscheinlichste Codewort ermittelt werden
+      * hierzu wird aus der **Nebenklasse** der Fehlermuster mit gleichem Syndrom dasjenige mit dem kleinsten Hamminggewicht ausgewählt und zum Empfangswort addiert
+  * Modifikation linearer Codes
+    * Expandieren: m' > m, n' = n, R' < R, d'<sub>min</sub> >= d<sub>min</sub>
+    * Punktieren: m' < m, n' = n, R' > R, d'<sub>min</sub> <= d<sub>min</sub>
+    * Verlängern: m' > m, n' > n, m' - n' = m - n, R' > R, d'<sub>min</sub> <= d<sub>min</sub>
+    * Verkürzen: m' < m, n' < n, m' - n' = m - n, R' < R, d'<sub>min</sub> >= d<sub>min</sub>
+  * wenn Codes durch Vertauschen der Generator- und Prüfmatrix ineinander übergehen (z.B. Paritäts- und Wiederholungscode), nennt man diese Codes **dual** oder **orthogonal**
+  * **Hamming-Codes** sind Einzelfehler-korrigierende Blockcodes, deren Coderate mit wachsender Blocklänge gegen 1 geht
+    * Hamming-Codes können erstellt werden, indem die 2<sup>m - n</sup> - 1 von 0 verschiedenen Paritätsbit-Kombinationen in Spaltenform angeordnet und dann so sortiert werden, dass rechts eine m-n x m-n Einheitsmatrix entsteht. Aus dieser Prüfmatrix kann nun die Generatormatrix des Hamming-Codes abgeleitet werden.
+  * bei **zyklische Blockcodes**, die eine Untermenge der linearen Blockcodes sind, entstehen auch durch zyklische Verschiebung der Codeworte (z.B. um 1 nach links: 010001 -> 100010) andere Codeworte
+    * Vorteil: können einfach mittels rückgekoppelten Schieberegistern (LFSR = Linear Feedback Shift Register) realisiert werden
+    * fehlererkennende zyklische Blockcodes (CRC = Cyclic Redundancy Check) erkennen gut Bündelfehler
+    * {{:se:generatormatrixzyklischerblockcodes.jpg|}}
+    * {{:se:generatormatrixzyklischerblockcodespolynom.jpg|}}
+    * wenn ein Generatorpolynom bekannt ist, kann damit durch c(x) = u(x) * g(x) der (meist nicht-systematische) Code erzeugt werden
+      * Codeworte sind daher immer Vielfache des Generatorpolynoms
+    * die Syndrome bei zyklischen Blockcodes entspechen s(x) = r(x) mod g(x)
+      * ein Fehler ist aufgetreten, wenn der Rest dieser Division nicht 0 ist
+    * ein zyklischer Code ist durch die Angabe seines Generatorpolynoms und der Codewortlänge vollständig definiert
+      * ein zyklischer Code entsteht, wenn zu einem gegebenen Generatorpolynom eine Codewortlänge gewählt wird, die der Zykluslänge entspricht
+      * größere Zykluslängen führen zu einer höheren Coderate
+      * wenn die Zykluslänge eines Polynoms den maximalen Wert 2<sup>k</sup> - 1 annimmt, handelt es sich um ein **primitives Polynom** (es ist dann auch irreduzibel)
+  * (Bündel-)Fehlererkennung durch zyklische Blockcodes
+    * von einem Bündelfehler der Länge t spricht man, wenn innerhalb eines Codeabschnitts der Länge t maximal t Fehler auftreten
+      * Bündelfehler können sich auch zyklisch vom Wortende zum Anfang erstrecken, dann werden sie zyklische Bündelfehler genannt
+    * zyklische Blockcodes erkennen mindestens Einzelfehler, Doppelfehler und Bündelfehler bis zur Länge k = m - n
+  * spezielle zyklische Codes
+    * zyklische Hamming-Codes: werden aus primitiven Generatorpolynomen erzeugt
+    * Fire-Codes: verwenden ein Produkt g(x) = g<sub>1</sub>(x) * (x<sup>k<sub>2</sub></sup> + 1) aus zwei irreduziblen Polynomen als Generatorpolynom
+    * BCH-Codes (Bose-Chaudhuri-Hocquenghem) erlauben die Korrektur von zufällig verteilten Fehlern
+    * RS-Codes (Reed-Solomon) bilden eine Klasse von nichtbinären BCH-Codes
+      * gehören zu den besten bekannten Bündelfehler-korrigierenden Codes (z.B. Audio-CD)
+==== Faltungscodes ====
+  * Faltungscodes haben ein Blockübergreifendes Gedächtnis und können mit sehr kleinen Blöcken (oft n = 1) arbeiten
+    * werden z.B. beim Mobilfunk eingesetzt
+    * man kann recht einfach auch den ungleichmäßigen Schutz der Nachrichtenbits erreichen (wichtige Bereiche werden besser geschützt)
+    * der Entwurf erfolgt nicht algebraisch, sondern durch rechnergestützte Suche
+    * Unterscheidung in rekursiv/nicht-rekursiv und systematisch/nicht-systematisch
+      * häufig: Nonrecursive nonsystematic Convolution (NSC)
+  * {{:se:schaltbildfaltungscodierer.jpg|}}
+    * das Beispiel macht aus einem Eingangsbit drei Ausgangsbit, die der Reihe nach gesendet werden
+    * die Länge der Verzögerungskette (3 Bits gehen in die Berechnung ein) nennt man Einflusslänge (Constraint Length)
+    * das Gedächtnis ist die die Anzahl der vorangehenden Bits in der Verzögerungskette (Anzahl - 1)
+    * {{:se:schaltbildfaltungscodiererallgemein.jpg|}}
+  * Darstellungsformen
+    * grafisch (s.o.)
+    * Koeffizientenmatrix, in der die Einsen dafür stehen, dass das entsprechende Eingangsbit in die Modulo-2-Operation zur Ermittlung des Ausgangsbits eingeht
+      * die Matrixzeilen (Generatoren) werden häufig in Oktalschreibweise angegeben
+    * Baumdiagramme
+      * {{:se:baumdiagrammfaltungscodierer.jpg|}}
+    * Zustandsdiagramme
+      * {{:se:zustandsdiagrammfaltungscodierer.jpg|}}
+    * Trellisdiagramme: Zustanddiagramme, in denen die neuen Zustände immer nach rechts weiter abgetragen werden
+      * {{:se:trellisdiagramm.jpg|}}
+      * erst nach 2 Schritten können alle Zustände erreicht werden (eingeschwungener Zustand)
+  * Decodierung
+    * die Decodierung erfolgt mittels des Viterbi-Algorithmus, also der Suche nach dem am besten übereinstimmenden Pfad des Trellisdiagramms
+      - Zweigdistanz/Zweigmetrik für jeden Zweig ermitteln (unterschiedliche Bits zur Eingangsfolge bei Hard-Decision, euklidische Distanz bei Soft-Decision)
+      - die Zweigdistanz wird zur Survivormetrik des Ursprungsknotens des Zweiges addiert -> neue Summenzweigmetrik/Summenmetrik
+      - die neue Survivormetrik des Zielknotens ergibt sich als Minimum aller Summenzweigmetriken der in den Knoten mündenden Zweige. Diese Survivormetriken werden für alle Knoten berechnet.
+      - die Survivorpfade ergeben sich durch Rückverfolgen (Backtracing) des Pfades, der den Zweig mit der minimalen Summenzweigmetrik enthält
+    * {{:se:viterbi1.jpg|}}
+    * {{:se:viterbi2.jpg|}}
+    * {{:se:viterbi3.jpg|}}
+  * analog zur Hammingdistanz kann man bei Faltungscodes eine Minimaldistanz d<sub>free</sub> (freie Distanz) als kleinstes Gewicht der Pfade vom Nullzustand in den Nullzustand (ohne reinen Nullpfad)
+===== Klausur =====
+==== Wichtige Feststellungen und Definitionen ====
+  * Entropie: mittlerer Informationsgehalt der Zeichen des Quellalphabets
+    * Gleichverteilung der Symbolwahrscheinlichkeiten => **maximale Entropie** (Entscheidungsgehalt) H<sub>0</sub> = ld(q)
+  * bedingte Entropie: mittlere Entropie aller Zustände
+    * H(x|s) &le; H(x)
+  * Verbundentropie: mittlerer Informationsgehalt von Ausgangsfolgen einer Quelle
+  * Wahrscheinlichkeiten
+    * A-posteriori  p(x|y)
+    * A-priori p(x)
+  * Äquivokation/Rückschlussentropie/Verlust H(x|y)
+  * Irrelevanz/Streuentropie/Rauschen H(y|x)
+  * Transinformation: mittlere im Ausgangszeichen eines Kanals enthaltene Information
+  * Kanalkapazität: Maximum der Transinformation
+    * bei symmetrischen Kanälen führt eine Gleichverteilung der Wahrscheinlichkeiten der Eingangszeichen zur maximalen Transinformation
+  * Zusammenfassen von Eingangssymbolen zu Eingangsfolgen erhöht die Codeeffizienz (1. Fundamentalsatz der Quellencodierung)
+  * arithmetische Codierung geht nur für stationäre gedächtnislose Quellen
+  * Ausnutzen von bedingten Wahrscheinlichkeiten bei Markov-Quellen erhöht die Effizienz
+  * Codeumschaltung: bei zustandsabhängiger Codierung wird je nach Zustand eine andere Codetabelle verwendet
+  * Lauflängencodierung ist nur sinnvoll, wenn genügend Zeichenfolgen auftreten, die in der Darstellung (Code, Lauflänge) kürzer sind als normal
+  * Verfahren mit adaptiven Wörterbüchern eignen sich auch für nicht-stationäre Quellen
+  * Blockcodes teilen die Nachrichten in gleichgroße Blöcke auf
+  * um bei einem Gausskanal mittels Hard-Decision die gleiche Wortfehlerwahrscheinlichkeit erreichen wie mit Soft-Decision braucht man die doppelte Sendeleistung
+  * lineare Blockcodes: n < m, 2<sup>n</sup> Codeworte
+  * Wortfehler/Restfehler: aus dem Empfangswort wird auf das falsche Codewort geschlossen oder beim Korrigieren eines Fehlers wird das falsche Codewort erzeugt
+    * für kleine Bitfehlerwahrscheinlichkeiten resultiert ein Wortfehler meist aus der Verfälschung zu einem Codewort mit der zum korrekten Codewort minimalen Hammingdistanz
+  * Modifikationen (Expandieren, Punktieren, Verlängern, Verkürzen) führen systematische Codes wieder in systematische Codes über
+  * CRC-Codes sind fehlererkennende zyklische Blockcodes
+  * mit größeren Zykluslängen sind höhere Coderaten möglich
+  * primitives Polynom: die Zykluslänge entspricht dem maximalem Wert 2<sup>k</sup> - 1 und ist irreduzibel
+    * primitive Generatorpolynome erzeugen Codes mit d<sub>min</sub> = 3
+    * meist werden CRC-Codes aus Generatorpolynomen der Form g<sub>prim</sub>(x) * (x + 1)
+      * dann: d<sub>min</sub> = 4, z = 2<sup>k - 1</sup> - 1
+  * jeder lineare Blockcode (auch zyklische Codes) enthält das Nullwort
+==== Berechnungen ====
+  * Redundanz: &rho; =  H<sub>0</sub> - H(x)
+  * Coderedundanz/Weitschweifigkeit p<sub>Code</sub> = L - H(x) (mit L = mittlere Wortlänge in Bit)
+  * relative Coderedundanz: p<sub>Code<sub>rel</sub></sub> = p<sub>Code</sub> / L
+  * Codeeffizienz &eta; = H(x) / L
+  * Coderate R = m / n
+  * Entropie einer Markov-Quelle ohne Berücksichtigung der statistischen Bindung
+    * "normale" Entropie mit p(x<sub>i</sub>) berechnen
+  * bedingte Entropie bei gegebener Markov-Quelle
+    - p(x<sub>i</sub>|s) sind gegeben durch Zustandsdiagramm
+    - p(s) für alle Zustände ermitteln (lineares Gleichungssystem)
+    - H(x|s) für jeden Zustand ermitteln und mit p(s) multiplizieren und aufaddieren
+  * Verbundentropie
+    * bei Markov-Quellen
+      * Formel mit p(x,s) = p(x|s) * p(s)
+      * H(x,s) für n Zeichen = (n - 1) * H(x|s) + H(x)
+    * bei statistisch unabhängigen Ausgangszeichen: n * H(x)
+  * zyklische Blockcodes
+    * Generieren
+      * vollständig definiert durch Generatorpolynom und Codewortlänge (n = Rang des Generatorpolynoms)
+      * g(x) und  n gegeben (oder aus m ermittelt) -> alle Permutationen von Wörtern der Länge n mit g(x) multiplizieren
+      * systematische Codes: Permutationen der Länge n erzeugen, d(x) = u(x) * x<sup>k</sup> mod g(x) addieren
+    * Generatormatrix erzeugen
+      * Koeffizienten eintragen und n Mal verschieben -> Streifenform
+  * zyklische Hamming-Codes: Erzeugen durch primitive Generatorpolynome
+  * Fire-Codes: Erzeugen durch Produkt zweier irreduzibler Polynome
+  * minimale Hammingdistanz durch Prüfmatrix ermitteln: jede Auswahl von d<sub>min</sub> - 1 Spalten ist linear unabhängig und es gibt mindestens eine Auswahl von d<sub>min</sub> linear abhängigen Spalten
+==== Eigenschaften ====
+  * Code
+    * optimal/kompakt: größtmögliche Effizienz bei gegebener Quelle -> kleinste mittlere Wortlänge
+    * ideal: eindeutig decodierbarer Effizienz &eta; = 1
+    * eindeutig decodierbar: Erfüllen der Kraft-McMillan-Ungleichung
+    * perfekt/dicht gepackt: alle Worte eines Coderaums liegen in Korrigierkugeln mit Radius e<sub>kor</sub>, Hamming-Schranke wird mit Gleichheit erfüllt
+    * äquivalent: Codes mit gleichen Parametern m, n, d<sub>min</sub> und w
+      * Code und Leistungsfähigkeit können abweichen, aber Distanzeigenschaften bleiben gleich
+      * Erzeugen durch Vertauschen von Spalten in der Generatormatrix
+    * systematisch: alle Eingangsbits stehen in allen Codeworten an der gleichen Stelle
+      * klar-systematisch: die Eingangsbits stehen der Reihe nach am Anfang der Codeworte
+    * Hamming-Codes: Coderate geht mit wachsender Blocklänge gegen 1
+      * Erzeugung: alle Permutationen von m - n Schutzbits als Spalten einer Prüfmatrix eintragen
+      * Hamming-Schranke mit Gleichheit erfüllt
+      * sind perfekt
+    * äquidistant: Codeworte haben paarweise jeweils gleiche Abstände d<sub>min</sub>, Plotkin-Schranke mit Gleichheit erfüllt
+    * identisch: Codes bestehen aus denselben Codeworten (nicht unbedingt in derselben Zuordnung zu Eingangsworten)
+    * zyklisch: Codeworte gehen durch Verschiebung ineinander über
+  * Quelle
+    * stationär: Wahrscheinlichkeiten der Ausgabezeichen sind unabhängig von der Zeit
+    * gedächtnislos: Wahrscheinlichkeiten der Ausgabezeichen sind unabhängig von Zeichen davor/danach
+  * Kanal
+    * diskret: zeit- und wertdiskret
+    * symmetrisch: Anzahl Eingänge = Anzahl Ausgänge, Fehlerwahrscheinlichkeit p
+    * verlustfrei/ungestört: nur ein von 0 verschiedener Eintrag je Spalte in der Kanalmatrix, aus Ausgangszeichen kann sicher auf das Eingangszeichen geschlossen werden
+    * rauschfrei: Kanalmatrix ist quadratische Einheitmatrix, in jeder Zeile nur ein von 0 verschiedener Eintrag, 1 Eingangszeichen -> 1 Ausgangszeichen
+    * total gestört: Ein- und Ausgangszeichen sind statistisch unabhängig, Transinformation = 0
+  * zyklische Blockcodes
+    * Codewortlänge muss gleich der Zykluslänge sein
+    * Zykluslänge z = kleinstes i, für das gilt: x<sup>i</sup> + 1 mod g(x) = 0
+    * Fehlererkennung: Einzel-, Doppel- und Bündelfehler bis zum Grad von g(x) sicher, darüber hinaus mit hoher Wahrscheinlichkeit
+    * Fehlerkorrektur
+      * primitives g(x): d<sub>min</sub> = 3 -> e<sub>kor</sub> = 1
+      * g(x) = g<sub>prim</sub>(x) * (x + 1): d<sub>min</sub> = 4 -> e<sub>kor</sub> = 1
+      * g(x) = g<sub>1</sub>(x) * (x<sup>k<sub>2</sub></sup> + 1) (Fire-Codes): d<sub>min</sub> = 4, sie können aber Bündelfehler korrigieren: t<sub>max</sub> &le; k<sub>1</sub>, t<sub>max</sub> < k<sub>2</sub> / 2 + 1
+==== ToDo ====
+  * Shannon-Grenze
+  * Wann welche Codierung? arithmetisch bei gedächtnisbehaftet?
+  * Gleichförmige Quantisierung
+  * Beispiele machen
+    * Huffman Code
+    * Arithmetische Codierung
+    * Lempel Ziv
+  * Kanalkapazität berechnen
+  * Kraft-McMillan
+  * Gewichtsverteilung berechnen
+  * Syndrome berechnen
+  * Decodierung der verschiedenen Codes
+    * zyklisch
+  * Polynomdivision
+  * Zykluslänge bestimmen

Stefans Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Unterschiede

Seiten-Werkzeuge