Проблема поиска точного наилучшего кода с исправлением ошибок для заданных параметров очень сложна, даже приблизительно наилучшие коды трудны. Кроме того, в некоторых кодах нет приличных алгоритмов декодирования, в то время как для других проблема декодирования довольно сложная.
Однако вы спрашиваете об определенном диапазоне параметров, где n ≫ k, где, если я правильно понимаю, вы хотите k-мерный код длины n. (Так что k битов кодируются в n битах.) Во-первых, в этом диапазоне случайный код, вероятно, будет иметь очень хорошее минимальное расстояние. Единственная проблема заключается в том, что декодирование может быть практически непрактичным, а фактически вычисляемым минимальным расстоянием тоже не так просто.
Во-вторых, если вам нужен явный код для случая n ≫ k, то вы можете достаточно хорошо справиться с кодом BCH с q = 2. Как объясняется на странице Википедии, есть хороший алгоритм декодирования для кодов МПБ.
Что касается верхних границ для минимального расстояния Хэмминга, в диапазоне n ≫ k следует начинать с границы Хэмминга , также известной как граница объема или границы упаковки сферы. Идея ограничения проста и прекрасна: если минимальное расстояние равно t, тогда код может исправлять ошибки вплоть до расстояния до пола ((t-1) / 2). Если вы можете исправить ошибки до некоторого радиуса, это означает, что шары Хэмминга этого радиуса не перекрываются. С другой стороны, общее количество возможных слов составляет 2 n , поэтому, если вы поделите это на количество точек в одном шаре Хэмминга (которое в двоичном случае представляет собой сумму биномиальных коэффициентов), вы получить верхнюю границу количества безошибочных кодовых слов. Можно преодолеть этот предел, но для большого минимального расстояния это не легко. В этом режиме это очень хорошая оценка.