L'algorithme de génération d'une taille k du code de correction d'erreur sur n bits

Question

Je veux générer un code sur n bits pour k différentes entrées que je veux classer. La principale exigence de ce code est les critères de correction d'erreur: que la distance par paires minimum entre deux encodages de différentes entrées est maximisée. Je ne ai pas besoin pour être exact -. Approximative fera, et la facilité d'utilisation et la rapidité de mise en œuvre de calcul est une priorité aussi

En général, n sera dans les centaines, k dans les dizaines.

En outre, il est une limite raisonnable serré sur la distance de Hamming minimum entre k différents codages binaires de n bits?

Answer 1

Le problème de trouver le meilleur code correcteur d'erreurs exacte des paramètres donnés est très difficile, même approximativement meilleurs codes sont difficiles. En plus de cela, certains codes n'ont pas des algorithmes de décodage décent, alors que pour d'autres le problème de décodage est assez délicat.

Cependant, vous poser des questions sur une gamme particulière de paramètres n »k, si je comprends bien, vous voulez un code k dimensions de longueur n. (Alors que les k bits sont codés en bits n.) Dans cette gamme, tout d'abord, un code aléatoire est susceptible d'avoir une très bonne distance minimale. Le seul problème est que le décodage est partout de pratique à intractible, et le calcul fait la distance minimale est pas facile non plus.

En second lieu, si vous voulez un code explicite pour le cas n »k, alors vous pouvez le faire assez bien avec Hamming lié , également connu comme le volume lié ou l'emballage de la sphère liée. L'idée de la limite est simple et belle: Si la distance minimale est t, le code peut corriger les erreurs jusqu'à rez-de-distance ((t-1) / 2). Si vous pouvez corriger des erreurs dans une certaine rayon, cela signifie que les boules de Hamming de ce rayon ne se chevauchent pas. D'autre part, le nombre total de mots possibles est 2 ⁿ , donc si vous divisez par le nombre de points dans une boule Hamming (qui, dans le cas binaire est une somme de coefficients binomiaux), vous obtenez une limite supérieure du nombre de mots de code sans erreur. Il est possible de battre cette limite, mais pour une grande distance minimale, il est pas facile. Dans ce régime, il est une très bonne limite.