Le problème de trouver le meilleur code de correction d'erreur exact pour des paramètres donnés est très difficile, même si les meilleurs codes sont difficiles. En plus de cela, certains codes n'ont pas d'algorithmes de décodage décents, tandis que pour d'autres, le problème du décodage est assez délicat.
Cependant, vous posez des questions sur une plage particulière de paramètres où n »k, où si je comprends bien, vous voulez un code k de longueur n. (De sorte que k bits sont codés en n bits.) Dans cette gamme, 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 peu pratique ou intractible, et calculer la distance minimale n'est pas si simple non plus. Deuxièmement, si vous voulez un code explicite pour le cas n »k, alors vous pouvez raisonnablement bien faire avec BCH code avec q = 2. Comme l'explique la page Wikipédia, il existe un bon algorithme de décodage pour les codes BCH. En ce qui concerne les bornes supérieures pour la distance minimale de Hamming, dans la plage n »k, vous devriez commencer par le Hamming bound, également connu sous le nom de la limite de volume ou de la densité de la sphère. L'idée de la borne est simple et belle: Si la distance minimale est t, alors le code peut corriger les erreurs jusqu'au plancher de distance ((t-1)/2). Si vous pouvez corriger des erreurs à un certain 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 n, donc si vous divisez cela par le nombre de points dans une boule de Hamming (qui dans le cas binaire est une somme de coefficients binomiaux), vous obtenez une limite supérieure sur le nombre de mots de code sans erreur. Il est possible de battre cette limite, mais pour une distance minimale importante, ce n'est pas facile. Dans ce régime, c'est une très bonne limite.