Publ. I.R.M.A. Strasbourg, 1984, 229/S–08 Actes 8^{e} Séminaire Lotharingien, p. 71–74

DIE KONSTRUKTION ALLER MAXIMALEN CODE

MIT HILFE VON MDS-CODEN

VON

Ulrich OBERST UND Arne DÜR

Einführung (vergl. [1]) und Motivation. — Ein linearer Code der Länge n über einem endlichen Körper F ist ein Unterraum C von F^{n}. Das für die Anwendungen wichtigste Beispiel eines solchen F ist das binäre “Alphabet” F = {0, 1}. Bezeichne dim(_{F} C) die Dimension von C. Auf F^{n} betrachtet man die Hamming-“Norm”

∥x∥ = Anzahl der von Null verschiedenen Komponenten eines Vektors x = (x_{1}, …, x_{n}) ∈ F^{n}.

Die normerhaltenden linearen Automorphismen von F^{n} heißen Isometrien. Man kann die algebraische Codierungstheorie als Geometrie bezüglich der Hammingmetrik oder als Invariantentheorie der Isometriegruppe betrachten.

Die Zahl

d(C) = min{∥x∥ ; x ∈ D, x ≠ 0}

heißt die Distanz des Codes C. Es gilt

(1)  dim(C) + d(C) ≤ n + 1.

Der Code C heißt MDS-Code, falls in (1) die Gleichheit gilt. Der Code C heißt maximal, falls er unter allen Coden C̃ ⊆ F^{n} mit d(C̃) ≥ d(C) maximal (bezüglich der Inklusion) ist.

Das Ziel der algebraischen Codierungstheorie ist es, “gute” (z.B. maximale) Code zu finden, für welche sowohl die Dimension als auch die Distanz möglichst groß sind. Informationstheoretisch bedeutet dies, daß man mit Hilfe dieser Code Nachrichten sowohl schnell wie möglichst fehlerfrei über einen gestörten symmetrischen Kanal übertragen kann. Eine bedeutende Klasse von “guten” Coden ist die der alternanten, insbesondere der Goppa Code : Seien k und n natürliche Zahlen mit 2 ≤ k ≤ n − 2. Seien K ein endlicher Erweiterungskörper von F mit wenigstens n Elementen und a_{1}, …, a_{n} n paarweise verschiedene Elemente von K. Die Vektoren

(a_{1}^{i}, …, a_{n}^{i}), i = 0, …, k − 1

U. OBERST AND A. DÜR

sind die Basis eines MDS-Codes der Dimension k und Distanz d = n+1−k über K. Jeder zu einem solchen isometrische Code Z ⊆ K^{n} heißt alternanter MDS-Code. Der Code

C := F^{n} ∩ Z

hat dann ebenfalls wenigstens die Distanz d, kann aber sehr klein sein. Bei geeigneter Wahl von Z erhält man aber “gute” Code. Die so erhaltenen Code heißen alternant.

Die folgenden Sätze zeigen, daß man in der Form C = Z ∩ F_{n} alle maximalen Code erhält, wenn man von geeigneten MDS-Coden Z ausgeht, und daß die Klasse der alternanten Code “sehr klein” ist.

Ergebnisse.

Satz 1. — Seien C ⊆ F^{n} ein Code der Dimension l und Distanz d und K ein endlicher Oberkörper von F mit wenigtens \binom{n−1}{d−1} + \binom{n−l−2}{d−1} + 1 Elementen. Dann gibt es einen MDS-Code Z ⊆ K^{n} der gleichen Distanz d mit

C ⊆ Z ∩ F^{n}.

Ist speziell C maximal, so ist C = Z ∩ F^{n}.

Die im vorigen Satz benötigten MDS-Code Z erhält man auf folgende Weise : Sei weiter 2 ≤ k ≤ n − 2. Ist

B = (B(i, j) ; i = 1, …, k, j = k + 1, …, n), B(i, j) ∈ K,

eine k × (n − k)-Matrix mit Koeffizienten in K, so sei

Z(B) = {x = (x_{1}, …, x_{n}) ∈ K_{n} ; (x_{1}, …, x_{k})B = (x_{k+1}, …, x_{n})}.

Satz 2. — Bezeichnungen wie oben. Die Abbildung B → Z(B) induziert eine Bijektion der Menge V(K) aller k × (n − k)-Matrizen mit Koeffizienten in K, deren quadratische Unterdeterminanten ungleich 0 sind, auf die Menge C(K) aller MDS-Code der Dimension k in K^{n}.

Wie uns die Kollegen HEISE (München) und HERGERT (Darmstadt) mitteilten, ist eine Version dieses Satzes bekannt und insbesondere enthalten in dem Buch [2]. Dieses war uns bis jetzt nicht zugänglich. Von Interesse ist nach SATZ 1 die Dimension von F_{n} ∩ Z(B).

Satz 3. — Sei F ⊂ K eine Erweiterung der Dimension m und habe F q Elemente. Seien Z = S(B) ⊆ K^{n} wie in SATZ 2 und C := Z ∩ F^{n} wie in SATZ 1 definiert. Dann ist

(2)  dim(_{F} C) = k − Rang(B^{(1)} − B, …, B^{(m−1)} − B).

MAXIMALE CODE

Dabei ist

B^{(l)} = (B(i, j)^{q(l)}; i = 1, …, k, j = k + 1, …, n), q(l) = q^{l}.

Die Matrix auf der rechten Seite von (2) hat die Gestalt k×(m−1)(n−k).

Die Menge V(K) in SATZ 2 ist auf offensichtliche Weise die Menge der K-rationalen Punkte der k(n−k)-dimensionalen affinen algebraischen Mannigfaltigkeit V(F̃), wobei F̃ ⊇ K der algebraische Abschluß von F ist. Durch Strukturtransport bildet dann auch die Menge C(F̃) der MDS-Code der Dimension k in F̃^{n} eine solche Mannigfaltigkeit und C(K) ist deren Menge der K-rationalen Punkte. Bezeichne Alt(K) die Menge der alternanten MDS-Code der Dimension k in K^{n}. Der nächste Satz zeigt, daß eine “kleine” Untermannigfaltigkeit von C ist. Sei

Z = Z(B) ⊆ K^{n}, B ∈ V(K),

ein MDS-Code der Dimension k in K^{n}. Betrachte die zugehörige normalisierte Matrix

A = (A(i, j) ; i = 2, …, k, j = k + 2, …, n),

A(i, j) := \frac{B(i, j) B(1, k + 1)}{B(i, k + 1) B(1, j)}

und die (k − 2)(n − k − 2) Relationen

(3) \frac{A(i, j) − 1}{A(i, j)A(2, j)^{−1} − 1} = \frac{A(i, j + 1) − 1}{A(i, j + 1)A(2, j + 1)^{−1} − 1},

i = 3, …, k, j = k + 2, …, n.

Satz 4. — Voraussetzungen und Bezeichnungen wie oben. Der Code Z(B) is genau dann ein alternanter MDS-Code, wenn die Gleichungen (3) erfüllt sind. Die Menge Alt(F̃) ist eine (2n − 4)-dimensionale abgeschlossene Untermannigfaltigkeit von C(F̃). Insbesondere ist

Alt(F̃) {⊂ \atop ≠} C(F̃) für 3 ≤ k ≤ n − 3.

Dies bedeutet, daß es für 3 ≤ k ≤ n − 3 sehr wenige alternante Code gibt oder, anders, daß die Alternanz keine generische Eigenschaft von Coden ist.

Die Sätze 1 und 4 machen die Suche nach neuen Klassen von MDS-Coden auf neue Weise interessant.

LITERATUR

[1] VAN LINT (J.H.). — Introduction to coding theory. — Berlin, Springer-Verlag, 1982.

[2] MAC WILLIAMS (F.J.) and SLOANE (N.J.A.). — The theory of error-correcting codes. — North-Holland, 1977.

Ulrich Oberst u. Arne Dür, Institut für Mathematik der Universität, Innrain 52, A-6020 Innsbruck.