Direkt zum Inhalt

Lexikon der Mathematik: Majoritätscode

besonders einfache Art der Codierung, die Fehler durch Vergleich mit Schwellwerten korrigiert. Ihre Codierer und Decodierer zeichnen sich durch hohe Geschwindigkeit bei großen Bitraten aus, allerdings sind ihre Korrekturraten selten optimal.

Einfache Vertreter einer solchen Codierung sind die mehrmalige Wiederholung, deren Informationsrate niedrig ist, und die Paritätsprüfung, die aber nur einen Einzelfehler bemerkt. Für beliebige n = 2m und r existiert ein binärer linearer (n, k)-Blockcode \(\left(k=1+\left(\begin{array}{c}m\\ 1\end{array}\right)+\ldots +\left(\begin{array}{c}m\\ r\end{array}\right)\right)\), dessen minimaler Hamming-Abstand 2m−r beträgt (Reed-Muller-Codes). Die Generatormatrix G des Codes besteht aus r+1 Untermatrizen Gi mit jeweils n Zeilen G = [G0G1Gr]. Dabei besteht G0 aus einer Spalte, deren Komponenten alle 1 sind, G1 aus m Spalten, die alle verschiedenen m-Zeilenvektoren darstellen, \begin{eqnarray}{G}_{1}=\left(\begin{array}{cccc}0 & 0 & \cdots & 0\\ 0 & 0 & \cdots & 1\\ \cdots & \cdots & \cdots & \cdots \\ 1 & 1 & \cdots & 1\end{array}\right),\end{eqnarray} und Gi aus allen verschiedenen komponentenweisen Produkten aus i Spaltenvektoren der Matrix G1. Für m = 3, n = 8 und r = 2 erhält man G = {(1)(a1)(a2)(a3)(a1a2)(a1a3)(a2a3)), \begin{eqnarray}{G}=\left(\begin{array}{ccccccc}1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 1 & 0 & 0 & 1\\ 1 & 1 & 0 & 0 & 0 & 0 & 0\\ 1 & 1 & 0 & 1 & 0 & 1 & 0\\ 1 & 1 & 1 & 0 & 1 & 0 & 0\\ 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right).\end{eqnarray}

Durch Aufstellung von „Abstimmungsgleichungen“ kann man rekursiv durch Mehrheitsbeschluß die Fehler in den zu den jeweiligen Untermatrizen Gi gehörigen Informationsbits korrigieren.

Majoritätscodes werden wegen der einfachen Decodierregeln gern verwendet. Sie können auch oft erfolgreich mehr Fehler korrigieren, als es der minimale Hamming-Abstand des Codes garantiert.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte