Einige Grundlagen der Algebra

Aus LNTwww
< Kanalcodierung
Version vom 10. Januar 2017, 19:03 Uhr von Ayush (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „ {{Header |Untermenü=Reed–Solomon–Codes und deren Decodierung |Vorherige Seite=Informationstheoretische Grenzen der Kanalcodierung |Nächste Seite=Erweit…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Wechseln zu:Navigation, Suche

Definition eines Galoisfeldes


Bevor wir uns der Beschreibung der Reed–Solomon–Codes zuwenden können, benötigen wir einige algebraische Grundbegriffe. Beginnen wir mit den Eigenschaften eines Galoisfeldes GF(q), benannt nach dem Franzosen Évariste Galois, dessen Biografie für einen Mathematiker eher ungewöhnlich ist.

: Ein Galoisfeld GF(q) ist ein endlicher Körper mit q Elementen z0, z1, ... , zq–1, wenn alle acht nachfolgend aufgeführten Aussagen hinsichtlich der Addition („+”) und der Multiplikation („·”) zutreffen. Addition und Multiplikation sind hierbei modulo q zu verstehen.

(A)  GF(q) ist in sich abgeschlossen  ⇒  Closure:

\[\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} z_j \in {\rm GF}(q): \hspace{0.25cm}(z_i + z_j)\in {\rm GF}(q),\hspace{0.15cm}(z_i \cdot z_j)\in {\rm GF}(q) \hspace{0.05cm}. \]

(B)  Es gibt ein hinsichtlich der Addition neutrales Element NA, das man oft auch als das Nullelement bezeichnet  ⇒  Identity for „+”:

\[\exists \hspace{0.15cm} z_j \in {\rm GF}(q) : \hspace{0.25cm}z_i + z_j = z_i \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_j = N_{\rm A} = {\rm "0"} \hspace{0.25cm}{\rm (Nullelement)} \hspace{0.05cm}.\]

(C)  Es gibt ein hinsichtlich der Multiplikation neutrales Element NM, das oft auch als das Einselement bezeichnet wird  ⇒  Identity for „·”:

\[\exists \hspace{0.15cm} z_j \in {\rm GF}(q) : \hspace{0.25cm}z_i \cdot z_j = z_i \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_j = N_{\rm M} = {\rm "1"} \hspace{0.25cm}{\rm (Einselement)} \hspace{0.05cm}. \]

(D)  Für jedes zi existiert eine additive Inverse  ⇒  Inverse for „+”:

\[\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_A}(z_i) \in {\rm GF}(q): \hspace{0.25cm}z_i + {\rm Inv_A}(z_i) = N_{\rm A} = {\rm "0"} \]

\[ \Rightarrow \hspace{0.25cm}{\rm kurz:}\hspace{0.15cm} {\rm Inv_A}(z_i) = - z_i \hspace{0.05cm}. \]

(E)  Für jedes zi mit Ausnahme des Nullelements existiert die multiplikative Inverse ⇒ Inverse for „·”:

\[\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} z_i \ne N_{\rm A}, \hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_M}(z_i) \in {\rm GF}(q): \hspace{0.25cm}z_i \cdot {\rm Inv_M}(z_i) = N_{\rm M} = {\rm "1"}\]

\[\Rightarrow \hspace{0.25cm}{\rm kurz:}\hspace{0.15cm} {\rm Inv_M}(z_i) = z_i^{-1} \hspace{0.05cm}. \]

(F)  Für Addition und Multiplikation gilt jeweils das Kommutativgesetz  ⇒  Commutative Law:

\[\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} z_j \in {\rm GF}(q): \hspace{0.25cm}z_i + z_j = z_j + z_i ,\hspace{0.15cm}z_i \cdot z_j = z_j \cdot z_i \hspace{0.05cm}.\]

(G)  Für Addition und Multiplikation gilt jeweils das Assoziativgesetz  ⇒  Associative Law:

\[\forall \hspace{0.15cm} z_i,\hspace{0.1cm} z_j ,\hspace{0.1cm} z_k \in {\rm GF}(q): \hspace{0.25cm}(z_i + z_j) + z_k = z_i + (z_j + z_k ),\hspace{0.15cm}(z_i \cdot z_j) \cdot z_k = z_i \cdot (z_j \cdot z_k ) \hspace{0.05cm}.\]

(H)  Für die Kombination „Addition – Multiplikation” gilt das Distributivgesetz  ⇒  Distributive Law:

\[\forall \hspace{0.15cm} z_i,\hspace{0.15cm} z_j ,\hspace{0.15cm} z_k \in {\rm GF}(q): \hspace{0.25cm}(z_i + z_j) \cdot z_k = z_i \cdot z_k + z_j \cdot z_k \hspace{0.05cm}.\]


Es sei nochmals darauf hingewiesen, dass Addition („+”) und Multiplikation („·”) modulo q zu verstehen sind. Hierbei bezeichnet die Ordnung q die Anzahl der Elemente des Galoisfeldes.