Diskussion:Perfekter Code

Fehlerhafte Definition ganz oben auf der Seite

Die Definition "Blockcode C \subset A^n, bei dem jedes Wort x\in A^n nur zu genau einem Codewort c \in C eine minimale Hamming-Distanz hat." ist falsch: der binaere Code mit den Codewoertern (0, 0) und (1, 0) erfuellt diese Definition, jedoch hat man bei der Hamming-Schranke eine echte Abweichung. --77.58.84.36 13:11, 4. Jan. 2013 (CET)

Häääääääää? Die einzelnen Begriffe zu erklären, ggfs. auf eigenen Seiten, wäre gut. -- 217.255.79.131 12:51, 21. Feb 2005 (CET)

Unverständlich

Für nicht-Informatiker nicht zu verstehen. --Gunter Krebs Δ 12:55, 21. Feb 2005 (CET)

Es gab zwar einige Änderungen, aber als Otto-Normal-Wikipedia-User weiß ich immer noch nicht was das ist. Warum kann niemand einen allgemeinverständlichen Einleitungssatz formulieren, der beschreibt um was es geht, für was man es braucht und was es möglicherweise für praktische Auswirkungen hat? --EMU 23:06, 16. Feb. 2008 (CET)

Unvollständige Definition

Die Definition ist hier eindeutig unvollständig und damit nicht aussagekräftig genug. Umgangssprachlich fehlt hier noch eine Aussage über die Wirtschaftlichkeit. Ein Perfekter Code "verschwendet" nämlich keine Wörter indem er sie ungenutzt läßt. Die Summe der Anzahlen aller Worte, die innerhalb eines definierten Hamming-Abstandes d von einem benachbarten Codewort stehen ist gleich der Anzahl aller möglichen Worte (kein Wort wird also verschwendet). Ich habe die Definition aus dem Buch "Introduction to Coding and Information Theory" (Steven Roman Springer Verlag) vorliegen. Sie ist nur wegen der Mengenoperationssymbole etwas schwer einzutippen. Bei Bedarf bitte melden, dann erfasse ich sie in TEX. --Jbulling 17:00, 23. Sep 2006 (CEST)

Überarbeitung

• Fehlerhafte Definition korrigiert vgl. Benutzer_Diskussion:Wdwd#Perfekter_Code
• Die mathematische Beschreibung neu verfasst, da der Zusammenhang mit den perfekten Codes nicht ersichtlich war.
• Abschnitt Perfekte Codes: Gilt in obiger Gleichung die Gleichheit, so nennt man C einen t-perfekten Code. Ein t-perfekter Code hat in jeder Nebenklasse genau ein Codewort vom Gewicht \leq t , was hilfreich bei der Syndrom-Decodierung ist. ist inhaltlich problematisch, da diese Argumentation nur für lineare Codes funktioniert und ein Perfekter Code a priori nicht linear sein muss (auch wenn die bekannten perfekten Codes linear sind), deshalb gelöscht.
• Abschnitt Perfekte Codes: Anschaulich wird um jedes Codewort eine Kugel vom Radius t gelegt. Bei einem Code mit Minimalabstand mindestens d=2*t+1 sind dabei alle Kugeln disjunkt. Falls nun die Vereinigung dieses Kugeln den ganzen Raum ausmachen, so ist C ein t-perfekter Code.: ist in der Mathematischen Beschreibung gelandet (Wenn auch nicht wörtlich). --62.180.24.37 11:38, 16. Feb. 2008 (CET)

Danke für die Überarbeitung bzw. Richtigstellungen.--wdwd 12:05, 16. Feb. 2008 (CET)

Kritische Formulierung

"Um perfekt zu sein muss ein Code also eine ungerade Hammingsdistanz haben..." Diese Formulierung sehe ich kritisch. Ich schlage folgende Umformulierung vor: "Um perfekt zu sein muss ein Code also ein ungerades minimales Hamminggewicht haben..." oder "Um perfekt zu sein muss die minimale Hammingdistanz zwischen zwei Wörtern eins Codes ungerade sein..."

Bitte prüfen und ggf. ändern. Es ist zwar klar was gemeint ist, jedoch ist der Anspruch auf Präzision meiner Meinung nach nicht erfüllt. Was haltet ihr davon? --Georg 27. Jun 2008 12:20

Ja, ist eine bessere Formulierung. --wdwd 15:35, 27. Jun. 2008 (CEST)

Gleich mehrere Fehler in Abschnitt "Bekannte Perfekte Codes"

In dem Abschnitt findet sich die irreführende Aussage "Es gibt - bis auf Isomorphie - lediglich die folgenden perfekten Codes: [...]". Es wurden nicht die perfekten Codes klassifiziert, sondern nur die Parameter perfekter Codes, und das auch nur für Alphabetgrößen, die Primpotenzen sind. Selbst wenn wir das alles hinnehmen, ist die Liste noch unvollständig: es fehlen die nicht binären Hammingcodes.

In der zitierten Referenz MacWilliams/Sloane steht etwas vollkommen anderes; die andere Referenz (Werner Lütkebohmert: Codierungstheorie, Braunschweig/Wiesbaden, Vieweg, 2003) ist mir nicht bekannt, aber ich kann mir nicht vorstellen, dass es dort falsch drinsteht.

Bekannt ist das folgende für Alphabetgrößen, die Primpotenzen sind: Ist C ein perfekter Code mit Parametern [n,M,d], so gibt es einen Code D mit denselben Parametern aus der folgenden Liste:

• Ein trivialer Code. Ein Code heißt hier trivial, falls er entweder nur ein einziges Codewort enthält, oder falls er sämtliche q^n möglichen Wörter der gegebenen Blocklänge enthält, oder falls er ein Wiederholungs-Code der Länge n ist.
• Ein q-ärer Hammingcode
• Ein Golay-Code

Hierbei bezeichnet n die Blocklänge,M die Anzahl der Codewörter, und d den minimalen Hammingabstand des Codes C.

Man beachte, dass diese Klassifikation nur die möglichen Parameter betrifft, und Klassifikation der Codes selbst noch nicht vollständig bekannt ist. Insbesondere weiss man, dass es nichtlineare Codes gibt, die dieselben Parameter haben wie binäre Hammingcodes. Ausserdem ist offen, für welche Parameter es perfekte Codes gibt, falls die Alphabetgröße keine Primpotenz ist.

All dies findet sich in einer verlässlichen Quelle auf deutsch, die noch dazu ohne Bibliotheksausweis zugreifbar ist:

Wolfgang Willems: Mathematische Aspekte der Codierungstheorie, Jahresbericht der DMV 109 (2007), 71-97

Mag sich jemand von den regulären Wikindianern die Mühe machen, den Artikel gründlich zu lesen, und das entsprechend zu korrigieren? Danke. (Ich selbst habe, offenbar im Gegensatz zu derjenigen Person, der diesen falsch zitierten Unsinn reingeschrieben hat, noch kein Sichtungsrecht. Angesichts der Unregelmäßigkeit meiner Beiträge wird das wohl auch noch die nächsten 10 Jahre so bleiben.) --Hermel 23:41, 17. Sep. 2009 (CEST)

Ok habe die fehlerhaften Stellen bereinigt und den Begriff Isomorphie genauer erläutert, die Liste entsprechend korrigiert und den Codes die entsprechenden Parameter zugeordnet. Folgendes aus dem Vorschlag wurde nicht übernommen, da falsch:

• Die Wiederholungscodes sind nicht trivial und nur dann perfekt, wenn 1. die Blocklänge ungerade ist und 2. Das Alphabet nur aus 2 Elementen besteht. Gegenbeispiele zu 1. Binärer Wiederholungcode der Länge 2: das Wort (1,0) ist nicht eindeutig decodierbar 2. Ternärer Wiederholungscode z.B. der Länge 3: (0,1,2) ist auch nicht eindeutig zu decodieren.
• Der (23,11,5) Golay Code gelöscht, da mir nicht bekannt und wegen der Parameter nicht perfekt (war anscheinend noch aus einer ganz frühen Fassung erhalten und nie korrigiert...)

Die genannte Quelle gibt zu dem Thema im großen und Ganzen die gleiche Information wie die erwähnten Fachbücher, allerdings sind 2 Lösungen der "Hamminggleichung" in dieser Quelle falsch: $(n,2,n)_{2}$ und $(24,2^{12},7)_{2}$ die erste entspricht den Wiederholungscodes, und löst die Gleichung für gerades n nicht, da $(d-1)/2$ abgerundet wird (alternativ: der minimale Hammingabstand wäre dann gerade). Das zweite geht nicht auf: 2325 teilt keine Zweierpotenz; allerdings ist $(23,2^{11},7)_{2}$ eine entsprechende Lösung, die zum Golay-Code ${\mathcal {G}}_{23}$ führt. In dem Buch von Lütkebohmert stehen die Lösungen richtig drin. -- Mestor 18:31, 19. Sep. 2009 (CEST)

Danke für das schnelle und umsichtige Eingreifen. Aber ich bezweifle, dass der Begriff "isomorph" an dieser Stelle in richtiger Art und Weise verwendet wird. --Hermel 10:38, 21. Sep. 2009 (CEST)

Update: zwei Mengen von Codewörtern C und D heissen isomorph genau dann wenn es eine Permutation $\pi :\{1,2,\ldots ,n\}\to \{1,2,\ldots ,n\}$ gibt, so dass $D=\{\,\pi (c)\mid c\in C\,\}$. Siehe: Tuvi Etzion, Nonequivalent q-ary perfect codes, SIAM J. Discrete Math., 1996. Ich habe im Moment keines der beiden im Artikel zitierten Lehrbücher zur Hand, aber ich wage zu bezweiflen, dass diese Lehrbücher den Begriff der Isomorphie in anderer Weise definieren als Etzion. Falls sich dieser Zweifel erhärtet, ist die Aussage also, in der Form wie sie momentan im Artikel steht, immer noch nicht richtig.--Hermel 11:08, 21. Sep. 2009 (CEST)

Doch, die Begriffe werden zumindest teilweise anderst verwendet. Wenn ich das richtig verstehe verwendet der eben erwähnte Artikel den Begriff isomorph dafür, dass man bei einen Code $C_{1}$ bei allen Codewörtern die Koordinaten permutiert und den Code $C_{2}$ erhält. Ich kenne diese Konstruktion unter äquivalent, was bei dem erwähnten Artikel wiederum eine andere Bedeutung hat. Man hat zwei gleich große endliche Mengen C und D und kann sich also ohne weiteres eine bijektive Abbildung konstruieren, meiner Meinung nach kann man dann schon von „isomorph“ sprechen. Um weitere Verwirrungen zu vermeiden ist es aber wahrscheinlich doch besser den Begriff zu vermeiden. --Mestor 14:57, 21. Sep. 2009 (CEST)