Algorithmus für eine Größe k Fehlerkorrekturcode auf n Bits zu erzeugen

Question

Ich möchte für k verschiedene Eingänge, einen Code auf n Bits erzeugen, dass ich klassifizieren wollen. Die Hauptanforderung dieses Codes ist die Fehlerkorrekturkriterien: dass der minimalen Abstand zwischen paarweise zwei beliebigen Codierungen verschiedenen Eingänge maximiert wird. Ich brauche es nicht genau zu sein -. Annäherndes tun und Benutzerfreundlichkeit und Geschwindigkeit der Rechen Implementierung ist eine Priorität zu

In der Regel n wird in den Hunderten, k in den Dutzenden sein.

Außerdem ist es eine ziemlich eng gebunden an der minimalen Hamming-Distanz zwischen k verschiedenen n-Bit-Codierungen?

Answer 1

Das Problem des genauen besten Fehlerkorrektur der Suche nach bestimmten Parametern Code ist sehr schwer, auch nur annähernd beste Codes hart sind. Hinzu kommt, dass, haben einige Codes keine anständigen Dekodierungsalgorithmen haben, während für andere das Dekodieren Problem ziemlich schwierig ist.

Allerdings Sie über einen bestimmten Bereich von Parametern zu fragen, wo n »k, wo, wenn ich das richtig verstehen Sie einen k-dimensionalen Code der Länge n will. (So ??dass k Bits wird in n Bits codiert.) In diesem Bereich, wird zuerst ein Zufallscode wahrscheinlich sehr gut Mindestabstand haben. Das einzige Problem ist, dass Decodierung überall von unpraktisch effizient lösbar ist, und tatsächlich den Mindestabstand der Berechnung ist nicht so einfach, auch nicht.

Zweitens, wenn Sie einen expliziten Code für den Fall n »k wollen, dann können Sie einigermaßen gut tun mit einem Hamming beginnen sollen gebundener , auch als das Volumen gebunden oder gebunden Kugelpackung bekannt. Die Idee der gebundenen ist einfach und schön: Wenn der Mindestabstand t ist, dann kann der Codefehler auf Abstand Boden korrigiert bis ((t-1) / 2). Wenn Sie Fehler aus bis zu einem gewissen Radius korrigieren, bedeutet das, dass die Hamming Kugeln dieses Radius nicht überlappen. Auf der anderen Seite ist die Gesamtzahl der möglichen Worte 2 ⁿ , also wenn Sie teilen, dass durch die Anzahl der Punkte in einem Hamming-Ball (die im binären Fall eine Summe von Binomialkoeffizienten ist), Sie erhalten eine obere von der Anzahl der fehlerfreie Codewörter gebunden. Es ist möglich, diese Schranke zu schlagen, aber für großen Mindestabstand ist es nicht einfach. In diesem Bereich ist es eine sehr gut gebunden.