Abschnitt 28

Lineare Codes und Fehlerkorrektur

> Algebraische Anwendung von Vektorräumen und endlichen Körpern. In diesem Abschnitt wird der mathematische Kern linearer Codes vorgestellt, ohne den Kurs in einen vollständigen Kurs zur Codetheorie umzuwandeln.

Linearer Code auf einem endlichen Feld

fortgeschrittenviz

Ein linearer Code $C$ der Länge $n$ über $F_{q}$ ist ein Vektorunterraum

C \leq F_{q}^{n} .

Äquivalente Form

dim (C) = k,

Eine Menge geschlossener Codewörter unter Addition und Multiplikation mit Skalaren des endlichen Körpers.

Details ansehen →

Es heißt linearer Code $[n, k]_{q}$ .

Generierende Matrix

fortgeschrittenviz

G \in F_{q}^{k \times n} .

Äquivalente Form

c = m G .

Konvertiert eine Nachricht mit $k$ -Symbolen in ein Codewort mit $n$ -Symbolen.

Details ansehen →

Eine $m \in F_{q}^{k}$ -Nachricht wird mit codiert

Paritätsprüfmatrix

fortgeschrittenviz

Eine Prüfmatrix $H$ erfüllt für jedes Codewort $c$

H c^{T} = 0 .

Äquivalente Form

H \in F_{q}^{(n - k) \times n} .

Zusätzlich mit unterstützten Konventionen für $G$ und $H$

G H^{T} = 0.

Es definiert lineare Einschränkungen, die jedes gültige Codewort erfüllen muss.

Details ansehen →

Syndrom

fortgeschrittenviz

s = H r^{T} .

Wenn $r$ ein gültiges Codewort ist

s = 0 .

Äquivalente Form

s = H e^{T} .

Fasst zusammen, gegen welche Paritätsbeschränkungen ein empfangenes Wort verstößt.

Details ansehen →

Wenn $r = c + e$ , dann

Hamming-Distanz und Gewicht

fortgeschrittenviz

d_{H} (x, y) = ∣ {i : x_{i} \neq = y_{i}} ∣.

Äquivalente Form

w_{H} (x) = d_{H} (x, 0) .

Zählen Sie, wie viele Positionen sich zwischen zwei Wörtern unterscheiden.

Details ansehen →

Das Hamming-Gewicht ist

Mindestabstand, Erkennung und Korrektur

fortgeschrittenviz

d_{m i n} = c_{1} \neq = c_{2} min d_{H} (c_{1}, c_{2}) .

Äquivalente Form

d_{m i n} - 1

Äquivalente Form

t = ⌊ \frac{d _{m i n} - 1}{2} ⌋

Für einen linearen Code

d_{m i n} = c \neq = 0 min w_{H} (c) .

Die Trennung zwischen Codewörtern bestimmt die theoretische Erkennungs- und Korrekturkapazität.

Details ansehen →

Ein Code mit Mindestabstand $d_{m i n}$ kann bis zu erkennen

Fehler erkennen und korrigieren

Fehler im klassischen Symbolfehlermodell.

Rate eines linearen Codes

fortgeschrittenviz

R = \frac{k}{n} .

Bruchteil der Symbole im Codewort, die unabhängige Informationen darstellen.

Details ansehen →

Abschnitt 28

Lineare Codes und Fehlerkorrektur

Linearer Code auf einem endlichen Feld

fortgeschrittenviz

Ein linearer Code $C$ der Länge $n$ über $F_{q}$ ist ein Vektorunterraum

C \leq F_{q}^{n} .

Äquivalente Form

dim (C) = k,

Eine Menge geschlossener Codewörter unter Addition und Multiplikation mit Skalaren des endlichen Körpers.

Details ansehen →

Es heißt linearer Code $[n, k]_{q}$ .

Generierende Matrix

fortgeschrittenviz

G \in F_{q}^{k \times n} .

Äquivalente Form

c = m G .

Konvertiert eine Nachricht mit $k$ -Symbolen in ein Codewort mit $n$ -Symbolen.

Details ansehen →

Eine $m \in F_{q}^{k}$ -Nachricht wird mit codiert

Paritätsprüfmatrix

fortgeschrittenviz

Eine Prüfmatrix $H$ erfüllt für jedes Codewort $c$

H c^{T} = 0 .

Äquivalente Form

H \in F_{q}^{(n - k) \times n} .

Zusätzlich mit unterstützten Konventionen für $G$ und $H$

G H^{T} = 0.

Es definiert lineare Einschränkungen, die jedes gültige Codewort erfüllen muss.

Details ansehen →

Syndrom

fortgeschrittenviz

s = H r^{T} .

Wenn $r$ ein gültiges Codewort ist

s = 0 .

Äquivalente Form

s = H e^{T} .

Fasst zusammen, gegen welche Paritätsbeschränkungen ein empfangenes Wort verstößt.

Details ansehen →

Wenn $r = c + e$ , dann

Hamming-Distanz und Gewicht

fortgeschrittenviz

d_{H} (x, y) = ∣ {i : x_{i} \neq = y_{i}} ∣.

Äquivalente Form

w_{H} (x) = d_{H} (x, 0) .

Zählen Sie, wie viele Positionen sich zwischen zwei Wörtern unterscheiden.

Details ansehen →

Das Hamming-Gewicht ist

Mindestabstand, Erkennung und Korrektur

fortgeschrittenviz

d_{m i n} = c_{1} \neq = c_{2} min d_{H} (c_{1}, c_{2}) .

Äquivalente Form

d_{m i n} - 1

Äquivalente Form

t = ⌊ \frac{d _{m i n} - 1}{2} ⌋

Für einen linearen Code

d_{m i n} = c \neq = 0 min w_{H} (c) .

Die Trennung zwischen Codewörtern bestimmt die theoretische Erkennungs- und Korrekturkapazität.

Details ansehen →

Ein Code mit Mindestabstand $d_{m i n}$ kann bis zu erkennen

Fehler erkennen und korrigieren

Fehler im klassischen Symbolfehlermodell.

Rate eines linearen Codes

fortgeschrittenviz

R = \frac{k}{n} .

Bruchteil der Symbole im Codewort, die unabhängige Informationen darstellen.

Details ansehen →