Was ist ein perfekter Code?

Question

Es geht um Codes in der diskreten Mathematik.

Was ein linearer fehlerkorrigierender bzw. fehlererkennender Code ist weiß ich. Dann gibt es aber noch den perfekten Code mit der folgenden Definition:

C⊆IF₂ⁿ ist ein Code, r∈ℕ

C ist r-perfekt, falls IF₂ⁿ = Disjunkte Vereinigung von B_r(v), v∈C

Kann man sich das so vorstellen, dass der Code perfekt ist, wenn er kein Korrigierbedarf hat? Also quasi richtig ist? Oder wie kann man sich so ein Code vorstellen. Habe schon mehrere Definitionen durchgelesen, leider habe ich keine Vorstellung bekommen. Ich danke jedem im Voraus.

Answer 1

Hallo,

wenn die Kugeln \(B_r(v)\) diskjunkt sind, kann man r Fehler korrigieren. Denn ein Wort mit höchstens r Fehlern liegt dann eindeutig in genau einer solchen Kugel.

Wenn man jetzt einen Code C entwickelt, der r Fehler korrigieren soll, und hat ein bestimmtes v Wort für C ausgewählt, dann kann für ein weiteres Wort keines aus \(B_r(v)\) mehr genommen werden.

Allgemein: Wenn schon \(v_1,v_2, \ldots v_k\) für C bestimmt sind, kann kein weiteres aus der Vereinigung der \(B_r(v_j),j=1 \ldots k,\) wählen.

Wenn der Code C nun so viele Elemente enthält, dass die Vereinigung dieser Kugeln den ganzen Raum ausmacht, dann hat man den größtmöglichen Code gefunden - und den nennt man eben perfekt.

Gruß

Comments

Vielen Dank für die ausführliche Antwort!!

Fällt Dir eventuell zur Verdeutlichung ein Beispiel ein? Das würde sehr helfen. Vielen Dank im Voraus!

---

Hallo,

ein einfaches "didaktisches" Beispiel habe ich nicht zur Hand. Aber in der Literatur findest Du natürlich einige perfekte Codes.

Gruß