1.5 Lineare Codes

Nachdem wir in den letzten drei Kapiteln einen Code rein als Untermenge $C \subseteq {0, 1}^{n}$ betrachtet haben und die Fragen der Codierung und Fehlererkennung hinangestellt haben, kehren wir nun zu der ursprünglichen Sichtweise zurück, dass nämlich der Code durch die Codierungsfunktion

\begin{array}{r} E : {0, 1}^{k} \to {0, 1}^{n} \end{array}

gegeben ist. Wir werden nun die Menge ${0, 1}$ als Köper mit zwei Elementen $F_{2}$ auffassen, mit Multiplikation $\cdot$ und Addition modulo 2. Dann sind $F^{k}$ und $F^{n}$ Vektorräume über $F$ , d.h. wir können Vektoren addieren, z.B.

\begin{array}{r} [\begin{array}{c} 0 \\ 1 \\ 1 \\ 1 \end{array}] + [\begin{array}{c} 1 \\ 0 \\ 1 \\ 0 \end{array}] = [\begin{array}{c} 1 \\ 1 \\ 0 \\ 1 \end{array}] \end{array}

Wir können nun den Fall untersuchen, dass die Codierungsfunktion $E$ linear ist.

Definition 1.5.1 (Linearer Code). Ein linearer Code ist gegeben durch eine lineare Abbildung $E : F_{2}^{k} \to F_{2}^{n}$ . Dies ist ein Code der Blocklänge $n$ . Die Dimension des Codes ist $k$ . Die Rate des Codes ist $k / n$ . Wir können die Abbildung $E$ durch eine Matrix $G \in F_{2}^{n \times k}$ mit $n$ Zeilen und $k$ Spalten darstellen, die Generatormatrix des Codes. Wir nennen $E$ einen $[n, k]$ -Code.

Erinnern wir uns an einen ganz einfachen Parity-Check-Code $E : {0, 1}^{k} \to {0, 1}^{n}$ mit $k = n - 1$ : wir hängen dem Urwort $x$ die seine Parität an, also $(x_{1} \dots x_{k}) \mapsto (x_{1}, \dots, x_{k}, x_{1} \oplus \dots \oplus x_{k})$ . Dies ist ein linearer Code mit der Generatormatrix

\begin{array}{r} [\begin{array}{c} 1 \\ 1 \\ ⋱ \\ 1 \\ 1 & 1 & \dots & 1 \end{array}] \end{array}

Dieser Code ist ein $[n, n - 1]$ -Code mit Abstand 2.

Übungsaufgabe 1.5.1 Zeigen Sie: wenn $E : F_{2}^{k} \to F_{2}^{n}$ ein linearer Code ist, dann ist der Abstand $Δ (E)$ gleich

\begin{array}{r} min_{x \in F_{2}^{k} ∖ {0}} | E (x) |, \end{array}

wobei $| y |$ die Anzahl der Stellen in $y$ ist, die nicht $0$ sind.

Generatormatrix in systematischer Form

Der obige Parity-Check-Code, also der $[n, n - 1]$ -Code mit Abstand 2, hatte die schöne Eigenschaft, dass jedes Codeword $E (x)$ aus dem Urwort $x$ besteht, gefolgt von Parity-Check-Bits. Das ist nicht immer so. Betrachten wir beispielsweise den $[7, 4]$ -Code mit der Generatormatrix

\begin{array}{r} G := [\begin{array}{c} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \end{array}] \end{array}

Sie werden das Urwort $x \in F_{2}^{4}$ in seinem Bild $G x$ nicht unmittelbar wiedererkennen:

\begin{aligned} [\begin{array}{c} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \end{array}] \cdot [\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{array}] & = [\begin{array}{c} x_{1} + x_{2} + x_{3} \\ x_{1} + x_{2} \\ x_{2} + x_{3} \\ x_{4} \\ x_{3} + x_{4} \\ x_{2} \\ x_{1} + x_{3} + x_{4} \end{array}] \end{aligned}

Wenn Sie allerdings mit dem Gaussschen Eliminierungsverfahren vertraut sind, wird es Sie nicht wundern, dass man die Generatormatrix immer so umformen kann, dass das Urwort ein Präfix des Codewortes ist. Wir demonstrieren dies am Beispiel der obigen Matrix. Konkret wollen wir erreichen, dass die obersten vier Zeilen die Identitätsmatrix bilden. Die Gausssche Eliminierung lässt sich über dem Körper $F_{2}$ viel besser demonstrieren als über $Q$ , da man nicht mit unhandlichen Brüchen hantieren muss.

Bezeichnen wir die vier Spalten der obigen Matrix mit $c_{1}$ , $c_{2}$ , $c_{3}$ und $c_{4}$ . Die Matrix $G$ können wir also als $[c_{1} | c_{2} | c_{3} | c_{4}]$ schreiben. In dieser Notation wird aus dem Urwort $x = [x_{1}, x_{2}, x_{3}, x_{4}]^{T}$ das Codewort $x_{1} c_{1} + x_{2} c_{2} + x_{3} c_{3} + x_{4} c_{4}$ , also

\begin{array}{r} E : [\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{array}] \mapsto x_{1} c_{1} + x_{2} c_{2} + x_{3} c_{3} + x_{4} c_{4} \end{array}

Ich möchte nun $G$ so umformen, dass die obersten vier Zeilen der Matrix die Identitätsmatrix $I_{4}$ bilden. Als erstes arbeite ich an der ersten Zeile und möchte sie von derzeit $[1, 1, 1, 0]$ nach $[1, 0, 0, 0]$ umbauen. Dafür addieren wir die erste Spalte zur zweiten, ersetzen also $G = [c_{1} | c_{2} | c_{3} | c_{4}]$ durch $G_{1} := [c_{1} | c_{1} + c_{2} | c_{3} | c_{4}]$ . Aber Moment: jetzt haben wir eine neue Generatormatrix. Haben wir auch einen neuen Code? Nun ja, wenn wir die Codierungsfunktion betrachten, dann ist $x \mapsto G_{1} x$ natürlich eine andere Funktion als $x \mapsto G x$ . Wenn wir allerdings den Code als Untermenge $C = img (G) \subseteq F_{2}^{7}$ betrachten, dann ändert dieser sich nicht:

Behauptung. 1.5.2 $img (G) = img (G_{1})$ .

Ich könnte natürlich sagen "das ist grundlegende lineare Algebra", aber vielleicht ist es nicht schlecht, es sich noch einmal ins Gedächtnis zu rufen, warum das so ist.

Beweis. Als erstes zeigen wir $img (G) \subseteq img (G_{1})$ . Sei $y \in img (G)$ , also $y = G x$ für ein $x \in F_{2}^{4}$ . Setzen wir $u := [x_{1} - x_{2}, x_{2}, x_{3}, x_{4}]^{T}$ . Dann gilt

\begin{aligned} G_{1} u = G_{1} [\begin{array}{c} x_{1} - x_{2} \\ x_{2} \\ x_{3} \\ x_{4} \end{array}] & = (x_{1} - x_{2}) c_{1} + x_{2} (c_{1} + c_{2}) + x_{3} c_{3} + x_{4} c_{4} \\ = x_{1} c_{1} + x_{2} c_{2} + x_{3} c_{3} + x_{4} c_{4} \\ = G x, \end{aligned}

und somit ist $y = G x = G_{1} u$ auch in $img (G_{1})$ . Für die Inklusion $img (G_{1}) \subseteq img (G)$ nehmen wir $y = G_{1} x$ und rechnen das einfach aus:

\begin{array}{r} y = G_{1} x = [c_{1} | c_{1} + c_{2} | c_{3} | c_{4}] [\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{array}] = x_{1} c_{1} + x_{2} c_{1} + x_{2} c_{2} + x_{3} c_{3} + x_{4} c_{4} = [c_{1} | c_{2} | c_{3} | c_{4}] \cdot [\begin{array}{c} x_{1} + x_{2} \\ x_{2} \\ x_{3} \\ x_{4} \end{array}] \end{array}

und somit gilt

y \in img (G)

. Dies zeigt also, dass

img (G) = img (G_{1})

ist.

◻

Obwohl wir so getan haben, am konkreten Beispiel von $G \in F_{2}^{7 \times 4}$ zu arbeiten, wird der Leser bestimmt bestätigen können, dass diese Methode ganz allgemein funktioniert: wenn wir $G_{1}$ aus $G$ bilden, indem wir eine Spalte zu einer anderen addieren, dann gilt $img (G) = img (G_{1})$ .

\begin{array}{r} G = [\begin{array}{c} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \end{array}] ⟶ [\begin{array}{c} 1 & 1 + 1 & 1 & 0 \\ 1 & 1 + 1 & 0 & 0 \\ 0 & 0 + 1 & 1 & 0 \\ 0 & 0 + 0 & 0 & 1 \\ 0 & 0 + 0 & 1 & 1 \\ 0 & 0 + 1 & 0 & 0 \\ 1 & 1 + 0 & 1 & 1 \end{array}] = [\begin{array}{c} 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \end{array}] =: G_{1} \end{array}

Wir entfernen nun die 1 an der dritten Stelle der ersten Zeile, indem wir die erste Spalte auf zur dritten addieren.

\begin{array}{r} G_{1} = [\begin{array}{c} 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \end{array}] \to [\begin{array}{c} 1 & 0 & 1 + 1 & 0 \\ 1 & 0 & 1 + 0 & 0 \\ 0 & 1 & 0 + 1 & 0 \\ 0 & 0 & 0 + 0 & 1 \\ 0 & 0 & 0 + 1 & 1 \\ 0 & 1 & 0 + 0 & 0 \\ 1 & 1 & 1 + 1 & 1 \end{array}] = [\begin{array}{c} 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \end{array}] =: G_{2} \end{array}

Wir haben also die erste Zeile erfolgreich in $[1, 0, 0, 0]$ umgeformt. Als nächstes wollen wir die zweite Zeile in $[0, 1, 0, 0]$ umformen. Hier haben wir allerdings ein Problem: die ersten beiden Zeilen haben an der zweiten Stelle eine 0. Wir kriegen da also keine 1 hin. Wir könnten nun unser Ziel ändern und die dritte Zeile zu $[0, 1, 0, 0]$ machen. Dann würden wir oben zwar nicht die Identitätsmatrix hinkriegen, aber so etwas ähnliches (eine Permutationsmatrix). Übersichtlicher wird es allerdings, wenn wir für Position $(2, 2)$ eine 1 "beschaffen", in dem wir zum Beispiel Zeile 2 und 3 vertauschen.

\begin{array}{r} G_{2} = [\begin{array}{c} 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \end{array}] \mapsto [\begin{array}{c} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \end{array}] =: G_{3} \end{array}

Jetzt haben wir an Position (2,2) eine 1 und können fortfahren. Aber halt: ändert dieser Schritt, also das Vertauschen zweier Zeilen, unseren Code? In der Tat ja, allerdings nicht wesentlich. Definieren wir $π_{(23)} : F_{2}^{7} \to F_{2}^{7}$ als

\begin{array}{r} π_{(23)} : [\begin{array}{c} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ y_{5} \\ y_{6} \\ y_{7} \end{array}] \mapsto [\begin{array}{c} y_{1} \\ y_{3} \\ y_{2} \\ y_{4} \\ y_{5} \\ y_{6} \\ y_{7} \end{array}], \end{array}

also die Abbildung, die die zweite und die dritte Koordinate vertauscht, und definieren wir für eine Menge $U \subseteq F_{2}^{7}$ die Menge $π_{(23)} (U) := {π_{(23)} (u) | u \in U}$ , dann gilt

\begin{array}{r} img (G_{2}) = π_{(23)} (img (G_{3})) . \end{array}

Wir erhalten als Bild $img (G_{3})$ also einen neuen Code $C^{'}$ , der im allgemeinen nicht identisch zu $C = img (G) = img (G_{1}) = img (G_{2})$ ist, sondern aus diesem durch Vertauschen zweier Koordinaten hervorgeht. Es sollte offensichtlich sein, dass $| C^{'} | = | C |$ und $Δ (C) = Δ (C^{'})$ gilt und ganz allgemein alle interessanten kombinatorischen Eigenschaften erhalten bleiben. Machen wir weiter:

\begin{array}{r} G_{3} = [\begin{array}{c} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \end{array}] \overset{zweite auf dritte addieren}{\to} [\begin{array}{c} 1 & 0 & 0 + 0 & 0 \\ 0 & 1 & 1 + 1 & 0 \\ 1 & 0 & 0 + 1 & 0 \\ 0 & 0 & 0 + 0 & 1 \\ 0 & 0 & 0 + 1 & 1 \\ 0 & 1 & 1 + 0 & 0 \\ 1 & 1 & 1 + 0 & 1 \end{array}] = [\begin{array}{c} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{array}] =: G_{4} \end{array}

Indem wir die zweite Spalte auf die dritte addieren, haben wir die 1 un der zweiten Zeile an dritter Stelle eliminiert. Oberhalb davon, also in der ersten Zeile, geschieht nichts, weil diese Einträge ja bereits 0 geworden sind. Wir haben also die Sicherheit, dass getane Arbeit in den oberen Zeilen nicht wieder zerstört wird. Mit der dritten Zeile nun haben wir Glück: sie hat eine 1 an der dritten Stelle. Wir müssen also keine Koordinaten vertauschen. Wir eliminieren die 1 an Stelle 1 der dritten Zeile, indem wir die dritte Spalte auf die erste addieren:

\begin{array}{r} G_{4} = [\begin{array}{c} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{array}] \to [\begin{array}{c} 1 + 0 & 0 & 0 & 0 \\ 0 + 0 & 1 & 0 & 0 \\ 1 + 1 & 0 & 1 & 0 \\ 0 + 0 & 0 & 0 & 1 \\ 0 + 1 & 0 & 1 & 1 \\ 0 + 1 & 1 & 1 & 0 \\ 1 + 1 & 1 & 1 & 1 \end{array}] = [\begin{array}{c} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \end{array}] =: G_{5} \end{array}

Durch reines Glück ist die vierte Zeile bereits $[0, 0, 0, 1]$ und wir sind nun fertig. Unsere Matrix hat die Form $[\begin{matrix} I_{4} \\ P \end{matrix}]$ wie gewünscht.

Gausssche Umformungsschritte. Rekapitulieren wir kurz, welche Umformungsschritte wir angewandt haben:

Spaltenaddition. Wir addieren eine Spalte zu einer anderen. Dadurch ändert sich $img (G)$ nicht.
Zeilen vertauschen. Wir vertauschen Zeile $i$ mit Zeile $j$ . Dadurch ändert sich $img (G)$ , es wird nämlich zu $π_{(i j)} (img (G))$ , aber alle interessanten kombinatorischen Eigenschaften (insbesondere Mindestabstand $Δ$ ) bleiben erhalten.

Im allgemeinen Fall werden wir nicht unbedingt über $F_{2}$ arbeiten, sondern über einem allgemeinen Körper $K$ , meist einem endlichen. Für diesen Fall brauchen wir noch eine dritte Umformungsoperation:

Skalarmultiplikation. Wir ersetzen eine Spalte $c$ durch $λ c$ für ein $λ \in K ∖ {0}$ .

Für $F_{2}$ ist der dritte Schritt trivial, weil es neben $0$ nur ein Körperelement gibt, die 1.

Können wir steckenbleiben? Wie allgemein ist obiges Verfahren? Kann man steckenbleiben? Wir beschränken uns hier wieder auf den Fall $F_{2}$ , da der von der Notation her einfacher ist aber alle essentiellen Argumente enthält.

Im allgemeinen haben wir bereits durch die Umformungsschritte erreicht, dass Zeilen $1$ bis $i - 1$ die Einheitszeilenvektoren $e_{1}, \dots, e_{i - 1}$ sind. Wenn es nun eine weitere Zeile $u$ gibt, die an der $i$ -ten Stelle eine $1$ hat, also $u_{i} = 1$ , dann können wir in einem ersten Schritt per Vertauschung sicherstellen, dass dies Zeile $i$ ist. In einem zweiten Schritt entfernen wir alle anderen Einser von Zeile $i$ : für jedes $j \neq i$ mit $u_{j} = 1$ ersetzen wir Spalte $c_{j}$ durch $c_{i} + c_{j}$ . Dadurch wird Stelle $j$ von $u$ zu 0.

Nun ist also die $i$ -te Zeile von $u$ zu $e_{i}$ , dem Zeileneinheitsvektor, geworden. Was ist oberhalb von Zeile $i$ geschehen? Wir haben Spalte $c_{i}$ auf viele andere Spalten addiert. Da aber Zeilen 1 bis $i - 1$ die Einheitszeilenvektoren $e_{1}, \dots, e_{i - 1}$ sind, sind die oberen $i - 1$ Einträge von $c_{i}$ alle $0$ . Die Additionsschritte haben also in den ersten $i - 1$ Zeilen keinen Effekt.

Wir sehen: wir können nur steckenbleiben, wenn es keine Zeile $u$ gibt mit $u_{i} = 1$ . Das heißt aber, dass $c_{i} = 0$ . In Fachsprache: die Spalten von $G$ sind nicht linear unabhängig; $G$ hat nicht vollen Spaltenrang. Konkret heißt das, dass

\begin{aligned} G \cdot x & = G \cdot [\begin{array}{c} x_{1} \\ ⋮ \\ x_{i} \\ ⋮ \\ x_{n} \end{array}] = x_{1} c_{1} + \dots + x_{i} c_{i} + \dots + x_{n} c_{n} \\ (weil c_{i} = 0) & = x_{1} c_{1} + \dots + (x_{i} + 1) c_{i} + \dots + x_{n} c_{n} \\ = G \cdot z, \end{aligned}

wobei sich $x$ und $z$ nur an Stelle $i$ unterscheiden. Die Abbildung $x \mapsto G \cdot x$ ist also nicht einmal injektiv, insbesondere ist der Minimalabstand des Codes $0$ ! Wir sehen: solange $G \in F_{2}^{n \times k}$ vollen Spaltenrang $k$ hat, kommt das Umformungsverfahren zu einem Ende und liefert uns eine neue Generatormatrix in der Form $[\begin{matrix} I_{k} \\ M \end{matrix}]$ .

Wir können also jede Generatormatrix $G \in F_{2}^{n \times k}$ umformen in eine Matrix $G^{'} = [\begin{matrix} I_{k} \\ M \end{matrix}]$ , so dass sich $img (G)$ und $img (G^{'})$ nur in der Anordnung ihrer Koordinaten unterscheiden.

Theorem 1.5.3 (Generatormatrix in systematischer Form). Sei $G \in F_{2}^{n \times k}$ einer Generatormatrix mit Spaltenrang $k$ . Dann gibt es $G^{'} = [\begin{matrix} I_{k} \\ M \end{matrix}]$ und eine Permutation $π : [n] \to [n]$ mit

\begin{array}{r} img (G^{'}) = π (img (G)), \end{array}

wobei $A \subseteq F_{2}^{n}$ die Notation $π (A) := {(a_{π (1)} a_{π (2)} \dots a_{π (n)}) | a \in A}$ verwenden.

Insbesondere gilt $Δ (G^{'}) = Δ (G)$ und $R (G) = R (G^{'})$ , das heißt, in allen Parametern, die uns im Moment interessieren, sind $G$ und $G^{'}$ gleichwertig.

Fehlererkennung: die Parity-Check-Matrix

Wenn nun $G$ in systematischer Form vorliegt, können wir für ein gegebenes $x \in F_{2}$ auch direkt überprüfen, ob $x \in img (G)$ liegt, ob also $x$ ein Codewort ist:

def checkLinearCodeWord

(x = [x_{1} \dots x_{n}]^{T}, G = [\begin{matrix} I_{k} \\ M \end{matrix}])

: // prüft, ob

x

ein Codewort ist

$u := [x_{1}, \dots, x_{k}]$ , $v = [x_{k + 1}, \dots, x_{n}]$
if $M \cdot u = v$ return true else return false

Wenn $x$ ein gültiges Codewort ist, dann sind die ersten $k$ Koordinaten das Urwort $u$ (da $G$ in systematischer Form vorliegt). Wir erhalten die "richtigen" weiteren $n - k$ Koordinaten durch $M \cdot u$ . Der Algorithmus muss also nur prüfen, ob diese identisch mit den tatsächlich vorliegenden Koordinaten $x_{k + 1} \dots x_{n}$ sind. Der Algorithmus prüft also, ob $M \cdot u - v = 0$ ist. Da $x = [\begin{matrix} u \\ v \end{matrix}]$ gilt, können wir das kompakt wie folgt schreiben:

\begin{array}{r} [M | - I_{(n - k) \times (n - k)}] x = 0 \end{array}

Die Matrix $P := [M | - I_{(n - k) \times (n - k)}] \in F_{2}^{(n - k) \times n}$ ist die Parity-Check-Matrix des Codes.

Theorem 1.5.4 Sei $G \in F_{2}^{n \times k}$ die Generatormatrix eines Codes und habe $G$ vollen Rang $k$ . Dann gibt es eine Matrix $P \in F_{2}^{(n - k) \times n}$ , die Parity-Check-Matrix mit der Eigenschaft

\begin{array}{r} x \in img (G) ⟺ P \cdot x = 0 \in F_{2}^{n - k} \end{array}

für alle $x \in F_{2}^{n}$ .

Wir erhalten die Parity-Check-Matrix, indem wir $G$ in systematische Form $G^{'} = [\begin{matrix} I_{k} \\ M \end{matrix}]$ bringen. Die Parity-Check-Matrix ist dann $P^{'} = [M | - I_{(n - k) \times (n - k)}]$ . Eine Parity-Check-Matrix $P$ für den Code $img (G)$ erhalten wir dann, indem wir Spalten von $P^{'}$ entsprechend permutieren, die Vertauschungen also rückgängig machen.