Linearer Code - Versionsgeschichte

Bildungskind: Umbenennung nach Diskussion in Portal:Mathematik

2024-03-21T01:31:37Z

Umbenennung nach Diskussion in Portal:Mathematik

← Nächstältere Version		Version vom 21. März 2024, 03:31 Uhr
Zeile 13:		Zeile 13:
	\end{pmatrix}		\end{pmatrix}
	</math>		</math>
	zusammen, erhält man eine ''[[Generatormatrix\|Erzeugermatrix]]''. Des Weiteren besitzt der Code eine ''[[Kontrollmatrix]]'' <math>H</math>. Für sie gilt <math>H c^T=0</math> genau dann, wenn <math>c</math> ein Codewort ist. Der [[Rang (~~Mathematik~~)\|Rang]] von <math>G</math> ist <math>k</math>, der von <math>H</math> ist <math>n-k</math>. Der [[Hamming-Abstand#Hamming-Abstand eines Codes\|Hamming-Abstand]] von <math>C</math> ist die minimale Anzahl linear abhängiger Spalten der Kontrollmatrix.		zusammen, erhält man eine ''[[Generatormatrix\|Erzeugermatrix]]''. Des Weiteren besitzt der Code eine ''[[Kontrollmatrix]]'' <math>H</math>. Für sie gilt <math>H c^T=0</math> genau dann, wenn <math>c</math> ein Codewort ist. Der [[Rang (Lineare Algebra)\|Rang]] von <math>G</math> ist <math>k</math>, der von <math>H</math> ist <math>n-k</math>. Der [[Hamming-Abstand#Hamming-Abstand eines Codes\|Hamming-Abstand]] von <math>C</math> ist die minimale Anzahl linear abhängiger Spalten der Kontrollmatrix.

	Das [[Hamming-Gewicht]] eines Codewortes <math>c=(c_1,\dots,c_n)</math> ist gleich der Anzahl der <math>c_i</math>, die von Null verschieden sind. Beispielsweise hat das Codewort <math>(4 3 0 5 4 0)</math> über <math>\mathbb{F}_7^6</math> das Hamming-Gewicht 4. Der [[Hamming-Abstand]] des Codes ist gleich dem kleinsten Hamming-Gewicht aller Codewörter außer dem Nullwort.		Das [[Hamming-Gewicht]] eines Codewortes <math>c=(c_1,\dots,c_n)</math> ist gleich der Anzahl der <math>c_i</math>, die von Null verschieden sind. Beispielsweise hat das Codewort <math>(4 3 0 5 4 0)</math> über <math>\mathbb{F}_7^6</math> das Hamming-Gewicht 4. Der [[Hamming-Abstand]] des Codes ist gleich dem kleinsten Hamming-Gewicht aller Codewörter außer dem Nullwort.

Maximum 2520: /* Eigenschaften */ ergänzt

2022-11-24T21:44:43Z

Eigenschaften: ergänzt

← Nächstältere Version		Version vom 24. November 2022, 23:44 Uhr
Zeile 6:		Zeile 6:

	== Eigenschaften ==		== Eigenschaften ==
	Da <math>C</math> ein Untervektorraum von <math>V</math> ist, existiert eine Basis <math>g_1, \dots, g_k</math> von <math>C</math>. Fasst man diese Basis in einer [[Matrix (Mathematik)\|Matrix]]		Da <math>C</math> ein [[Untervektorraum]] von <math>V</math> ist, existiert eine [[Basis (Vektorraum)\|Basis]] <math>g_1, \dots, g_k</math> von <math>C</math>. Fasst man diese Basis in einer [[Matrix (Mathematik)\|Matrix]]
	: <math> G=\begin{pmatrix}		: <math> G=\begin{pmatrix}
	g_1 \\		g_1 \\
Zeile 13:		Zeile 13:
	\end{pmatrix}		\end{pmatrix}
	</math>		</math>
	zusammen, erhält man eine ''[[Generatormatrix\|Erzeugermatrix]]''. Des Weiteren besitzt der Code eine ''Kontrollmatrix'' <math>H</math>. Für sie gilt <math>H c^T=0</math> genau dann, wenn <math>c</math> ein Codewort ist. Der [[Rang (Mathematik)\|Rang]] von <math>G</math> ist <math>k</math>, der von <math>H</math> ist <math>n-k</math>. Der [[Hamming-Abstand#Hamming-Abstand eines Codes\|Hamming-Abstand]] von <math>C</math> ist die minimale Anzahl linear abhängiger Spalten der Kontrollmatrix.		zusammen, erhält man eine ''[[Generatormatrix\|Erzeugermatrix]]''. Des Weiteren besitzt der Code eine ''[[Kontrollmatrix]]'' <math>H</math>. Für sie gilt <math>H c^T=0</math> genau dann, wenn <math>c</math> ein Codewort ist. Der [[Rang (Mathematik)\|Rang]] von <math>G</math> ist <math>k</math>, der von <math>H</math> ist <math>n-k</math>. Der [[Hamming-Abstand#Hamming-Abstand eines Codes\|Hamming-Abstand]] von <math>C</math> ist die minimale Anzahl linear abhängiger Spalten der Kontrollmatrix.

	Das [[Hamming-Gewicht]] eines Codewortes <math>c=(c_1,\dots,c_n)</math> ist gleich der Anzahl der <math>c_i</math>, die von Null verschieden sind. Beispielsweise hat das Codewort <math>(4 3 0 5 4 0)</math> über <math>\mathbb{F}_7^6</math> das Hamming-Gewicht 4. Der Hamming-Abstand des Codes ist gleich dem kleinsten Hamming-Gewicht aller Codewörter außer dem Nullwort.		Das [[Hamming-Gewicht]] eines Codewortes <math>c=(c_1,\dots,c_n)</math> ist gleich der Anzahl der <math>c_i</math>, die von Null verschieden sind. Beispielsweise hat das Codewort <math>(4 3 0 5 4 0)</math> über <math>\mathbb{F}_7^6</math> das Hamming-Gewicht 4. Der [[Hamming-Abstand]] des Codes ist gleich dem kleinsten Hamming-Gewicht aller Codewörter außer dem Nullwort.

	Permutiert man die einzelnen Koordinaten der Codewörter, erhält man einen sogenannten ''äquivalenten Code''. Damit und mittels [[Lineare Algebra\|linearer Algebra]] kann man zu jedem linearen Code einen äquivalenten finden, der eine Erzeugermatrix der Form <math>G=(\mathbb{E}_k\|P)</math> hat. Dabei ist <math>\mathbb{E}_k</math> die <math>(k \times k)</math>-[[Einheitsmatrix]], und <math>P</math> ist eine <math>(k \times (n-k))</math>-Matrix. Dann heißt <math>G</math> Erzeugermatrix in reduzierter Form. Die ersten <math>k</math> Koordinaten können als Informationssymbole und die letzten <math>n-k</math> als Kontrollsymbole interpretiert werden. Ist <math>G</math> eine Erzeugermatrix in reduzierter Form, kann eine Kontrollmatrix <math>H</math> sofort gefunden werden: <math>H=(-P^T\|\mathbb{E}_{n-k})</math>. Ein linearer Code ist bereits durch seine Erzeugermatrix oder seine Kontrollmatrix bestimmt.		Permutiert man die einzelnen [[Koordinatensystem\|Koordinaten]] der Codewörter, erhält man einen sogenannten ''äquivalenten Code''. Damit und mittels [[Lineare Algebra\|linearer Algebra]] kann man zu jedem linearen Code einen äquivalenten finden, der eine [[Erzeugermatrix]] der Form <math>G=(\mathbb{E}_k\|P)</math> hat. Dabei ist <math>\mathbb{E}_k</math> die <math>(k \times k)</math>-[[Einheitsmatrix]], und <math>P</math> ist eine <math>(k \times (n-k))</math>-Matrix. Dann heißt <math>G</math> Erzeugermatrix in reduzierter Form. Die ersten <math>k</math> Koordinaten können als Informationssymbole und die letzten <math>n-k</math> als Kontrollsymbole interpretiert werden. Ist <math>G</math> eine Erzeugermatrix in reduzierter Form, kann eine Kontrollmatrix <math>H</math> sofort gefunden werden: <math>H=(-P^T\|\mathbb{E}_{n-k})</math>. Ein linearer Code ist bereits durch seine Erzeugermatrix oder seine Kontrollmatrix bestimmt.

			Weil der lineare Code ein <math>k</math>-[[Dimension (Mathematik)\|dimensionaler]] [[Untervektorraum]] von <math>\mathbb{F}_q^n</math> ist, ist er der [[Kern (Algebra)\|Kern]] einer [[Lineare Abbildung\|linearen Abbildung]] <math>f \colon \mathbb{F}_q^n \to \mathbb{F}_q^{n - k}</math>. Die [[Matrix (Mathematik)\|Matrix]] einer solchen linearen Abbildung heißt ''Paritätsprüfungsmatrix'' und wird notiert als <math>H^T</math> mit <math>H \in \mathbb{F}_q^{(n - k)\times{n}}</math>. Der lineare Code ist definiert als [[Kern (Algebra)\|Kern]] dieser linearen Abbildung: <math>C := \mathrm{ker}(f) = \{c \in \mathbb{F}_q^n \mid cH^T = 0\}</math>.

			Die [[Informationsrate]] des linearen Codes <math>C</math> ist <math>R = \tfrac{k}{n} \cdot \log_2(q)</math>.<ref>Technische Universität Berlin: [https://www.commit.tu-berlin.de/fileadmin/fg302/CC-linear-codes.pdf Linear Codes]</ref>

	=== Beispiel ===		=== Beispiel ===

Anthroporraistes: /* Dualer Code */

2022-06-12T13:32:00Z

Dualer Code

← Nächstältere Version		Version vom 12. Juni 2022, 15:32 Uhr
Zeile 200:		Zeile 200:
	== Dualer Code ==		== Dualer Code ==

	Zu jedem (linearen) Code <math>C</math> gibt es einen dualen Code (oder auch Dualcode) <math>C^\perp</math>, der selbst ein linearer Code ist. Die Codewörter des dualen Codes sind alle Wörter aus <math>\mathbb{F}_q^n</math>, die zu den ~~Codewörter~~ aus <math>C</math> dual sind:		Zu jedem (linearen) Code <math>C</math> gibt es einen dualen Code (oder auch Dualcode) <math>C^\perp</math>, der selbst ein linearer Code ist. Die Codewörter des dualen Codes sind alle Wörter aus <math>\mathbb{F}_q^n</math>, die zu den Codewörtern aus <math>C</math> dual sind:

	Man definiert hierzu ein inneres Produkt:		Man definiert hierzu ein inneres Produkt:

A.kotlorz: Einheitliche Schreibweise für "kodieren" ist in einem Artikel besser :-)

2019-08-13T15:49:52Z

Einheitliche Schreibweise für "kodieren" ist in einem Artikel besser :-)

← Nächstältere Version		Version vom 13. August 2019, 17:49 Uhr
Zeile 1:		Zeile 1:
	Ein '''linearer Code''' ist in der [[Kodierungstheorie]] ein spezieller [[Blockcode]], bei dem die Codewörter Elemente eines endlichdimensionalen [[Vektorraum\|Vektorraums]] <math>\mathbb{F}_q^n</math> über einem [[Endlicher Körper\|endlichen Körper]] <math>\mathbb{F}_q</math> sind. Ein [[Code]] ist genau dann linear, wenn er ein [[Untervektorraum]] von <math>\mathbb{F}_q^n</math> ist.		Ein '''linearer Code''' ist in der [[Kodierungstheorie]] ein spezieller [[Blockcode]], bei dem die Codewörter Elemente eines endlichdimensionalen [[Vektorraum\|Vektorraums]] <math>\mathbb{F}_q^n</math> über einem [[Endlicher Körper\|endlichen Körper]] <math>\mathbb{F}_q</math> sind. Ein [[Code]] ist genau dann linear, wenn er ein [[Untervektorraum]] von <math>\mathbb{F}_q^n</math> ist.

	Lineare Codes haben den Vorteil, dass Methoden der [[Lineare Algebra\|Linearen Algebra]] verwendet werden können. Sie sind somit einfach zu ~~codieren~~ und dekodieren. Die meisten wichtigen Codes sind linear: [[Hamming-Code]], [[Low-Density-Parity-Check-Code]], [[Reed-Muller-Code]], [[Hadamard-Code]], alle [[Zyklischer Code\|zyklischen Codes]] (damit auch [[BCH-Code\|BCH]], [[Reed-Solomon-Code]]s, [[Golay-Code]]s und [[Goppa-Code]]s).		Lineare Codes haben den Vorteil, dass Methoden der [[Lineare Algebra\|Linearen Algebra]] verwendet werden können. Sie sind somit einfach zu kodieren und dekodieren. Die meisten wichtigen Codes sind linear: [[Hamming-Code]], [[Low-Density-Parity-Check-Code]], [[Reed-Muller-Code]], [[Hadamard-Code]], alle [[Zyklischer Code\|zyklischen Codes]] (damit auch [[BCH-Code\|BCH]], [[Reed-Solomon-Code]]s, [[Golay-Code]]s und [[Goppa-Code]]s).

	Ist die Vektorraumdimension des linearen Codes <math>C</math> gleich <math>k</math>, so nennt man <math>C</math> einen ''<math>[n,k]</math>-Code'' oder bei einem [[Hamming-Abstand]] von <math>d</math> auch ''<math>[n,k,d]</math>-Code''.		Ist die Vektorraumdimension des linearen Codes <math>C</math> gleich <math>k</math>, so nennt man <math>C</math> einen ''<math>[n,k]</math>-Code'' oder bei einem [[Hamming-Abstand]] von <math>d</math> auch ''<math>[n,k,d]</math>-Code''.
Zeile 196:		Zeile 196:

	== Anwendung ==		== Anwendung ==
	Die Kodierung und Dekodierung ist, so wie sie oben beschrieben ist, relativ aufwendig. Bei der ~~Codierung~~ muss die Erzeugermatrix im Speicher gehalten werden, was bei Systemen mit begrenzten Ressourcen (zum Beispiel mobile Endgeräte oder Weltraumsonden) problematisch ist. Bei der Dekodierung wird eine – je nach Korrekturrate – große Tabelle benötigt; der Speicherverbrauch ist dementsprechend groß. Aus diesem Grund werden in der Regel zusätzliche Eigenschaften der Codes benutzt, um diese effizient zu kodieren und dekodieren. Binäre [[Zyklischer Code\|zyklische Codes]] lassen sich beispielsweise sehr einfach mittels [[Schieberegister]] und [[Exklusiv-Oder-Gatter]] realisieren.		Die Kodierung und Dekodierung ist, so wie sie oben beschrieben ist, relativ aufwendig. Bei der Kodierung muss die Erzeugermatrix im Speicher gehalten werden, was bei Systemen mit begrenzten Ressourcen (zum Beispiel mobile Endgeräte oder Weltraumsonden) problematisch ist. Bei der Dekodierung wird eine – je nach Korrekturrate – große Tabelle benötigt; der Speicherverbrauch ist dementsprechend groß. Aus diesem Grund werden in der Regel zusätzliche Eigenschaften der Codes benutzt, um diese effizient zu kodieren und dekodieren. Binäre [[Zyklischer Code\|zyklische Codes]] lassen sich beispielsweise sehr einfach mittels [[Schieberegister]] und [[Exklusiv-Oder-Gatter]] realisieren.

	== Dualer Code ==		== Dualer Code ==

Wdwd: rev, bitte um Kommentar warum - Ggf. auf Disk.

2019-06-07T09:19:12Z

rev, bitte um Kommentar warum - Ggf. auf Disk.

← Nächstältere Version		Version vom 7. Juni 2019, 11:19 Uhr
Zeile 21:		Zeile 21:
	=== Beispiel ===		=== Beispiel ===

	Der binäre <math>[7,4,3]</math>-[[Hamming-Code]] besitzt folgende Erzeugermatrix in reduzierter Form:		Der binäre <math>[7,4,3]</math>-[[Hamming-Code]] besitzt folgende Erzeugermatrix in reduzierter Form sowie die dazugehörige Kontrollmatrix:
	{\| style="margin-left:2em"		{\| style="margin-left:2em"
	\|-		\|-

2A00:8A60:C000:1:89D1:94F0:496A:7C49: /* Beispiel */Fehler korrigiert, die im folgenden angegebene Matrix ist keine Kontrollmatrix des [7, 4, 3] -Hamming-Code

2019-06-07T06:43:26Z

Beispiel: Fehler korrigiert, die im folgenden angegebene Matrix ist keine Kontrollmatrix des [7, 4, 3] -Hamming-Code

← Nächstältere Version		Version vom 7. Juni 2019, 08:43 Uhr
Zeile 21:		Zeile 21:
	=== Beispiel ===		=== Beispiel ===

	Der binäre <math>[7,4,3]</math>-[[Hamming-Code]] besitzt folgende Erzeugermatrix in reduzierter Form ~~sowie die dazugehörige Kontrollmatrix~~:		Der binäre <math>[7,4,3]</math>-[[Hamming-Code]] besitzt folgende Erzeugermatrix in reduzierter Form:
	{\| style="margin-left:2em"		{\| style="margin-left:2em"
	\|-		\|-

A.kotlorz: Rang der Matrix ist gleich k (und nicht n).

2019-05-27T08:17:02Z

Rang der Matrix ist gleich k (und nicht n).

← Nächstältere Version		Version vom 27. Mai 2019, 10:17 Uhr
Zeile 13:		Zeile 13:
	\end{pmatrix}		\end{pmatrix}
	</math>		</math>
	zusammen, erhält man eine ''[[Generatormatrix\|Erzeugermatrix]]''. Des Weiteren besitzt der Code eine ''Kontrollmatrix'' <math>H</math>. Für sie gilt <math>H c^T=0</math> genau dann, wenn <math>c</math> ein Codewort ist. Der [[Rang (Mathematik)\|Rang]] von <math>G</math> ist <math>n</math>, der von <math>H</math> ist <math>n-k</math>. Der [[Hamming-Abstand#Hamming-Abstand eines Codes\|Hamming-Abstand]] von <math>C</math> ist die minimale Anzahl linear abhängiger Spalten der Kontrollmatrix.		zusammen, erhält man eine ''[[Generatormatrix\|Erzeugermatrix]]''. Des Weiteren besitzt der Code eine ''Kontrollmatrix'' <math>H</math>. Für sie gilt <math>H c^T=0</math> genau dann, wenn <math>c</math> ein Codewort ist. Der [[Rang (Mathematik)\|Rang]] von <math>G</math> ist <math>k</math>, der von <math>H</math> ist <math>n-k</math>. Der [[Hamming-Abstand#Hamming-Abstand eines Codes\|Hamming-Abstand]] von <math>C</math> ist die minimale Anzahl linear abhängiger Spalten der Kontrollmatrix.

	Das [[Hamming-Gewicht]] eines Codewortes <math>c=(c_1,\dots,c_n)</math> ist gleich der Anzahl der <math>c_i</math>, die von Null verschieden sind. Beispielsweise hat das Codewort <math>(4 3 0 5 4 0)</math> über <math>\mathbb{F}_7^6</math> das Hamming-Gewicht 4. Der Hamming-Abstand des Codes ist gleich dem kleinsten Hamming-Gewicht aller Codewörter außer dem Nullwort.		Das [[Hamming-Gewicht]] eines Codewortes <math>c=(c_1,\dots,c_n)</math> ist gleich der Anzahl der <math>c_i</math>, die von Null verschieden sind. Beispielsweise hat das Codewort <math>(4 3 0 5 4 0)</math> über <math>\mathbb{F}_7^6</math> das Hamming-Gewicht 4. Der Hamming-Abstand des Codes ist gleich dem kleinsten Hamming-Gewicht aller Codewörter außer dem Nullwort.

143.93.17.16: Falsche Angaben. Auch im Beispiel ist zu sehen, dass der Rang von G n ist und nicht k

2019-02-06T11:26:38Z

Falsche Angaben. Auch im Beispiel ist zu sehen, dass der Rang von G n ist und nicht k

← Nächstältere Version		Version vom 6. Februar 2019, 13:26 Uhr
Zeile 13:		Zeile 13:
	\end{pmatrix}		\end{pmatrix}
	</math>		</math>
	zusammen, erhält man eine ''[[Generatormatrix\|Erzeugermatrix]]''. Des Weiteren besitzt der Code eine ''Kontrollmatrix'' <math>H</math>. Für sie gilt <math>H c^T=0</math> genau dann, wenn <math>c</math> ein Codewort ist. Der [[Rang (Mathematik)\|Rang]] von <math>G</math> ist <math>k</math>, der von <math>H</math> ist <math>n-k</math>. Der [[Hamming-Abstand#Hamming-Abstand eines Codes\|Hamming-Abstand]] von <math>C</math> ist die minimale Anzahl linear abhängiger Spalten der Kontrollmatrix.		zusammen, erhält man eine ''[[Generatormatrix\|Erzeugermatrix]]''. Des Weiteren besitzt der Code eine ''Kontrollmatrix'' <math>H</math>. Für sie gilt <math>H c^T=0</math> genau dann, wenn <math>c</math> ein Codewort ist. Der [[Rang (Mathematik)\|Rang]] von <math>G</math> ist <math>n</math>, der von <math>H</math> ist <math>n-k</math>. Der [[Hamming-Abstand#Hamming-Abstand eines Codes\|Hamming-Abstand]] von <math>C</math> ist die minimale Anzahl linear abhängiger Spalten der Kontrollmatrix.

	Das [[Hamming-Gewicht]] eines Codewortes <math>c=(c_1,\dots,c_n)</math> ist gleich der Anzahl der <math>c_i</math>, die von Null verschieden sind. Beispielsweise hat das Codewort <math>(4 3 0 5 4 0)</math> über <math>\mathbb{F}_7^6</math> das Hamming-Gewicht 4. Der Hamming-Abstand des Codes ist gleich dem kleinsten Hamming-Gewicht aller Codewörter außer dem Nullwort.		Das [[Hamming-Gewicht]] eines Codewortes <math>c=(c_1,\dots,c_n)</math> ist gleich der Anzahl der <math>c_i</math>, die von Null verschieden sind. Beispielsweise hat das Codewort <math>(4 3 0 5 4 0)</math> über <math>\mathbb{F}_7^6</math> das Hamming-Gewicht 4. Der Hamming-Abstand des Codes ist gleich dem kleinsten Hamming-Gewicht aller Codewörter außer dem Nullwort.

Pemu am 19. April 2018 um 22:38 Uhr

2018-04-19T22:38:13Z

← Nächstältere Version		Version vom 20. April 2018, 00:38 Uhr
Zeile 196:		Zeile 196:

	== Anwendung ==		== Anwendung ==
	Die Kodierung und Dekodierung ist, so wie sie oben beschrieben ist, relativ aufwendig. Bei der Codierung muss die Erzeugermatrix im Speicher gehalten werden, was bei Systemen mit begrenzten Ressourcen (zum Beispiel mobile Endgeräte oder Weltraumsonden) problematisch ist. Bei der Dekodierung wird eine – je nach Korrekturrate – große Tabelle benötigt; der Speicherverbrauch ist dementsprechend groß. Aus diesem Grund werden in der Regel zusätzliche Eigenschaften der Codes benutzt, um diese effizient zu kodieren und dekodieren. Binäre [[Zyklischer Code\|zyklische Codes]] lassen sich beispielsweise sehr einfach mittels [[Schieberegister]] und [[~~XOR~~-Gatter]] realisieren.		Die Kodierung und Dekodierung ist, so wie sie oben beschrieben ist, relativ aufwendig. Bei der Codierung muss die Erzeugermatrix im Speicher gehalten werden, was bei Systemen mit begrenzten Ressourcen (zum Beispiel mobile Endgeräte oder Weltraumsonden) problematisch ist. Bei der Dekodierung wird eine – je nach Korrekturrate – große Tabelle benötigt; der Speicherverbrauch ist dementsprechend groß. Aus diesem Grund werden in der Regel zusätzliche Eigenschaften der Codes benutzt, um diese effizient zu kodieren und dekodieren. Binäre [[Zyklischer Code\|zyklische Codes]] lassen sich beispielsweise sehr einfach mittels [[Schieberegister]] und [[Exklusiv-Oder-Gatter]] realisieren.

	== Dualer Code ==		== Dualer Code ==

Ziegenberg: wikilink, Namenskonvention

2017-02-23T01:09:15Z

wikilink, Namenskonvention

← Nächstältere Version		Version vom 23. Februar 2017, 03:09 Uhr
Zeile 13:		Zeile 13:
	\end{pmatrix}		\end{pmatrix}
	</math>		</math>
	zusammen, erhält man eine ''[[Generatormatrix\|Erzeugermatrix]]''. Des Weiteren besitzt der Code eine ''Kontrollmatrix'' <math>H</math>. Für sie gilt <math>H c^T=0</math> genau dann, wenn <math>c</math> ein Codewort ist. Der [[Rang (Mathematik)\|Rang]] von <math>G</math> ist <math>k</math>, der von <math>H</math> ist <math>n-k</math>. Der [[Hamming-Abstand#Hamming-Abstand eines Codes\|~~Hammingabstand~~]] von <math>C</math> ist die minimale Anzahl linear abhängiger Spalten der Kontrollmatrix.		zusammen, erhält man eine ''[[Generatormatrix\|Erzeugermatrix]]''. Des Weiteren besitzt der Code eine ''Kontrollmatrix'' <math>H</math>. Für sie gilt <math>H c^T=0</math> genau dann, wenn <math>c</math> ein Codewort ist. Der [[Rang (Mathematik)\|Rang]] von <math>G</math> ist <math>k</math>, der von <math>H</math> ist <math>n-k</math>. Der [[Hamming-Abstand#Hamming-Abstand eines Codes\|Hamming-Abstand]] von <math>C</math> ist die minimale Anzahl linear abhängiger Spalten der Kontrollmatrix.

	Das [[~~Hamming-Abstand#~~Hamming-Gewicht~~\|Hamminggewicht~~]] eines Codewortes <math>c=(c_1,\dots,c_n)</math> ist gleich der Anzahl der <math>c_i</math>, die von Null verschieden sind. Beispielsweise hat das Codewort <math>(4 3 0 5 4 0)</math> über <math>\mathbb{F}_7^6</math> das ~~Hamminggewicht~~ 4. Der ~~Hammingabstand~~ des Codes ist gleich dem kleinsten ~~Hamminggewicht~~ aller Codewörter außer dem Nullwort.		Das [[Hamming-Gewicht]] eines Codewortes <math>c=(c_1,\dots,c_n)</math> ist gleich der Anzahl der <math>c_i</math>, die von Null verschieden sind. Beispielsweise hat das Codewort <math>(4 3 0 5 4 0)</math> über <math>\mathbb{F}_7^6</math> das Hamming-Gewicht 4. Der Hamming-Abstand des Codes ist gleich dem kleinsten Hamming-Gewicht aller Codewörter außer dem Nullwort.

	Permutiert man die einzelnen Koordinaten der Codewörter, erhält man einen sogenannten ''äquivalenten Code''. Damit und mittels [[Lineare Algebra\|linearer Algebra]] kann man zu jedem linearen Code einen äquivalenten finden, der eine Erzeugermatrix der Form <math>G=(\mathbb{E}_k\|P)</math> hat. Dabei ist <math>\mathbb{E}_k</math> die <math>(k \times k)</math>-[[Einheitsmatrix]], und <math>P</math> ist eine <math>(k \times (n-k))</math>-Matrix. Dann heißt <math>G</math> Erzeugermatrix in reduzierter Form. Die ersten <math>k</math> Koordinaten können als Informationssymbole und die letzten <math>n-k</math> als Kontrollsymbole interpretiert werden. Ist <math>G</math> eine Erzeugermatrix in reduzierter Form, kann eine Kontrollmatrix <math>H</math> sofort gefunden werden: <math>H=(-P^T\|\mathbb{E}_{n-k})</math>. Ein linearer Code ist bereits durch seine Erzeugermatrix oder seine Kontrollmatrix bestimmt.		Permutiert man die einzelnen Koordinaten der Codewörter, erhält man einen sogenannten ''äquivalenten Code''. Damit und mittels [[Lineare Algebra\|linearer Algebra]] kann man zu jedem linearen Code einen äquivalenten finden, der eine Erzeugermatrix der Form <math>G=(\mathbb{E}_k\|P)</math> hat. Dabei ist <math>\mathbb{E}_k</math> die <math>(k \times k)</math>-[[Einheitsmatrix]], und <math>P</math> ist eine <math>(k \times (n-k))</math>-Matrix. Dann heißt <math>G</math> Erzeugermatrix in reduzierter Form. Die ersten <math>k</math> Koordinaten können als Informationssymbole und die letzten <math>n-k</math> als Kontrollsymbole interpretiert werden. Ist <math>G</math> eine Erzeugermatrix in reduzierter Form, kann eine Kontrollmatrix <math>H</math> sofort gefunden werden: <math>H=(-P^T\|\mathbb{E}_{n-k})</math>. Ein linearer Code ist bereits durch seine Erzeugermatrix oder seine Kontrollmatrix bestimmt.
Zeile 67:		Zeile 67:
	Mit ''Dekodierung'' bezeichnet man das Zuordnen eines empfangenen, möglicherweise fehlerhaften Eingabevektors <math>x</math> zu einem Codevektor <math>c'</math>. Die Dekodierung ist ''nicht'' die [[Umkehrfunktion]] der Kodierung, die einem Codevektor wieder einen Vektor aus <math>\mathbb{F}_q^k</math> zuordnet.		Mit ''Dekodierung'' bezeichnet man das Zuordnen eines empfangenen, möglicherweise fehlerhaften Eingabevektors <math>x</math> zu einem Codevektor <math>c'</math>. Die Dekodierung ist ''nicht'' die [[Umkehrfunktion]] der Kodierung, die einem Codevektor wieder einen Vektor aus <math>\mathbb{F}_q^k</math> zuordnet.

	Als Dekodierungsmethode wird in der Kodierungstheorie meistens die ''Methode der größten Wahrscheinlichkeit'' (englisch: ''maximum likelihood decoding'') verwendet. Dabei wird ein empfangener Vektor <math>x</math> zu dem Codevektor <math>c'</math> dekodiert, der mit der größten Wahrscheinlichkeit zum tatsächlich versandten Codevektor <math>c</math> identisch ist. Häufig wird der Vektor, bei dem die wenigsten Stellen (Fehler) korrigiert werden müssen, als der Wahrscheinlichste angenommen. Mathematisch gesprochen heißt das, man sucht den Codevektor <math>c'</math> mit dem geringsten ~~Hammingabstand~~ zum empfangenen Vektor <math>x</math>. Dieser Fall wird auch als ''Methode des nächstgelegenen Nachbarn'' (englisch: ''nearest neighbor decoding'') bezeichnet. Durch Kenntnis der Art der gesendeten Daten oder des verwendeten [[Kanal (Informationstheorie)\|Kanals]] können gegebenenfalls andere Informationen verwendet werden, um die Wahrscheinlichkeit für bestimmte Codevektoren zu bestimmen.		Als Dekodierungsmethode wird in der Kodierungstheorie meistens die ''Methode der größten Wahrscheinlichkeit'' (englisch: ''maximum likelihood decoding'') verwendet. Dabei wird ein empfangener Vektor <math>x</math> zu dem Codevektor <math>c'</math> dekodiert, der mit der größten Wahrscheinlichkeit zum tatsächlich versandten Codevektor <math>c</math> identisch ist. Häufig wird der Vektor, bei dem die wenigsten Stellen (Fehler) korrigiert werden müssen, als der Wahrscheinlichste angenommen. Mathematisch gesprochen heißt das, man sucht den Codevektor <math>c'</math> mit dem geringsten Hamming-Abstand zum empfangenen Vektor <math>x</math>. Dieser Fall wird auch als ''Methode des nächstgelegenen Nachbarn'' (englisch: ''nearest neighbor decoding'') bezeichnet. Durch Kenntnis der Art der gesendeten Daten oder des verwendeten [[Kanal (Informationstheorie)\|Kanals]] können gegebenenfalls andere Informationen verwendet werden, um die Wahrscheinlichkeit für bestimmte Codevektoren zu bestimmen.

	Es sei <math>c</math> der tatsächlich versendete (Code-)Vektor und <math>x</math> der empfangene Vektor. Die Dekodierung sucht aus allen <math>q^n</math> Codevektoren den oder die Codevektoren <math>c'</math>, die mit der größten Wahrscheinlichkeit versendet wurden.		Es sei <math>c</math> der tatsächlich versendete (Code-)Vektor und <math>x</math> der empfangene Vektor. Die Dekodierung sucht aus allen <math>q^n</math> Codevektoren den oder die Codevektoren <math>c'</math>, die mit der größten Wahrscheinlichkeit versendet wurden.
Zeile 91:		Zeile 91:
	Alle Vektoren, die aus einem beliebigen, festen Vektor durch Subtraktion eines beliebigen Codevektors hervorgegangen sind, bilden eine [[Nebenklasse (Mathematik)\|Nebenklasse]] der [[Untergruppe]] <math>C</math> von <math>\mathbb{F}_q^n</math>. Der Vektor mit minimalem Gewicht in dieser Klasse heißt ''Führer der Nebenklasse'' (englisch: ''coset leader''). Daher ist auch der Begriff „coset leader decoding“ verbreitet.		Alle Vektoren, die aus einem beliebigen, festen Vektor durch Subtraktion eines beliebigen Codevektors hervorgegangen sind, bilden eine [[Nebenklasse (Mathematik)\|Nebenklasse]] der [[Untergruppe]] <math>C</math> von <math>\mathbb{F}_q^n</math>. Der Vektor mit minimalem Gewicht in dieser Klasse heißt ''Führer der Nebenklasse'' (englisch: ''coset leader''). Daher ist auch der Begriff „coset leader decoding“ verbreitet.

	Um <math>x</math> zu <math>c'</math> zu dekodieren, sucht man also den Fehlervektor <math>e'</math>, dessen Syndrom identisch zum Syndrom von <math>x</math> ist und dessen [[Hamming-~~Abstand\|Hamminggewicht~~]] minimal ist. Mit diesem Fehlervektor berechnet man <math>c' = x - e'</math> den nächstgelegenen Codevektor <math>c'</math>.		Um <math>x</math> zu <math>c'</math> zu dekodieren, sucht man also den Fehlervektor <math>e'</math>, dessen Syndrom identisch zum Syndrom von <math>x</math> ist und dessen [[Hamming-Gewicht]] minimal ist. Mit diesem Fehlervektor berechnet man <math>c' = x - e'</math> den nächstgelegenen Codevektor <math>c'</math>.
	Man kann also eine Tabelle mit bis zu <math>q^{n-k}</math> Zeilen aufstellen, die für jedes Syndrom eines empfangenen Vektors den entsprechenden Fehlervektor mit minimalem ~~Hamminggewicht~~ beinhaltet. Ist das Syndrom gleich 0, dann muss nichts korrigiert werden ansonsten beschränkt sich Dekodierung auf das Nachschlagen des Fehlervektors in dieser Tabelle und Korrigieren der so detektierten Fehler.		Man kann also eine Tabelle mit bis zu <math>q^{n-k}</math> Zeilen aufstellen, die für jedes Syndrom eines empfangenen Vektors den entsprechenden Fehlervektor mit minimalem Hamming-Gewicht beinhaltet. Ist das Syndrom gleich 0, dann muss nichts korrigiert werden ansonsten beschränkt sich Dekodierung auf das Nachschlagen des Fehlervektors in dieser Tabelle und Korrigieren der so detektierten Fehler.

	Anders interpretiert sind die Nebenklassen gerade die [[Äquivalenzklasse]]n der [[Äquivalenzrelation]] <math>x\equiv y \Leftrightarrow s_x^T = s_y^T</math> Die Führer sind gerade Vertreter der Äquivalenzklassen, man wählt einen mit minimalem ~~Hamminggewicht~~. [[Perfekter Code\|Perfekte Codes]] zeichnen sich dadurch aus, dass die Führer eindeutig festgelegt sind.		Anders interpretiert sind die Nebenklassen gerade die [[Äquivalenzklasse]]n der [[Äquivalenzrelation]] <math>x\equiv y \Leftrightarrow s_x^T = s_y^T</math> Die Führer sind gerade Vertreter der Äquivalenzklassen, man wählt einen mit minimalem Hamming-Gewicht. [[Perfekter Code\|Perfekte Codes]] zeichnen sich dadurch aus, dass die Führer eindeutig festgelegt sind.

	Die Dekodierung von linearen Codes ist im Allgemeinen [[NP-Vollständigkeit\|NP-vollständig]], das heißt, es sind keine Algorithmen mit polynomieller Laufzeit bekannt.<ref>{{Literatur\|Autor=E. R. Berlekamp, R. J. McEliece, H. C. A. von Tilburg\|Titel=On the inherent intractability of certain coding problems\|Sammelwerk=IEEE Transactions on Information Theory 24\|Hrsg=\|Datum=1978}}</ref>		Die Dekodierung von linearen Codes ist im Allgemeinen [[NP-Vollständigkeit\|NP-vollständig]], das heißt, es sind keine Algorithmen mit polynomieller Laufzeit bekannt.<ref>{{Literatur\|Autor=E. R. Berlekamp, R. J. McEliece, H. C. A. von Tilburg\|Titel=On the inherent intractability of certain coding problems\|Sammelwerk=IEEE Transactions on Information Theory 24\|Hrsg=\|Datum=1978}}</ref>
Zeile 165:		Zeile 165:
	\|}		\|}

	Jeweils zwei Spalten von <math>H</math> sind linear unabhängig, alle drei dagegen linear abhängig. Der minimale ~~Hammingabstand~~ des Codes berechnet sich als minimale Anzahl linear abhängiger Spalten in <math>H</math> also zu 3. Es kann damit höchstens ein Zeichenfehler korrigiert werden. Die Syndromtabelle sieht folgendermaßen aus:		Jeweils zwei Spalten von <math>H</math> sind linear unabhängig, alle drei dagegen linear abhängig. Der minimale Hamming-Abstand des Codes berechnet sich als minimale Anzahl linear abhängiger Spalten in <math>H</math> also zu 3. Es kann damit höchstens ein Zeichenfehler korrigiert werden. Die Syndromtabelle sieht folgendermaßen aus:

	{\| class="wikitable"		{\| class="wikitable"