Алгоритм для генерации размера k Код исправления ошибок на N Bits

Question

Я хочу создать код на N Bits для K разных входов, которые я хочу классифицировать. Основным требованием этого кода является критерии корректировки ошибок: максимально используемое расстояние между любыми двумя кодировками различных входов. Мне не нужно, чтобы это было точным - приблизительным будет делать, а простота использования и скорость вычислительной реализации тоже является приоритетом.

В общем, N будет в сотнях, К в десятках.

Кроме того, есть ли достаточно плотная граница на минимальном расстоянии хэмминга между K различными N-битными двоичными кодировками?

Answer 1

Проблема нахождения точного наилучшего кода исправления ошибок для заданных параметров очень сложно, даже приблизительно лучшие коды сложно. Кроме того, некоторые коды не имеют никаких приличных алгоритмов декодирования, а для других проблем декодирования довольно сложно.

Тем не менее, вы спрашиваете о конкретном диапазоне параметров, где N »k, где, если я правильно понимаю, вы хотите, чтобы K-мерный код длины n. (Так что k биты кодируются в n битах.) В этом диапазоне, во-первых, случайный код, вероятно, имеет очень хорошее минимальное расстояние. Единственная проблема заключается в том, что декодирование - это где-нибудь из непрактично для нецелесообразного и фактически вычисления минимального расстояния не так просто.

Во-вторых, если вы хотите явный код для случая n »k, то вы можете сделать достаточно хорошо с Код БХ с q = 2. Как объясняет страницу Википедии, существует хороший алгоритм декодирования для кодов BCH.

Что касается верхних границ для минимального расстояния Hamming, в диапазоне n »k вы должны начать с Гермпин, также известный как граница громкости или сфера, связанная с сферой. Идея границы проста и красивая: если минимальное расстояние t, то код может исправить ошибки до расстояния до полок ((T-1) / 2). Если вы можете исправить ошибки к некоторому радиусу, это означает, что шарики хэмминга этого радиуса не перекрываются. С другой стороны, общее количество возможных слов составляет 2^N., Поэтому, если вы разделите, что по количеству точек в одном шарике хэмминга (который в двоичном корпусе представляет собой сумму биномиальных коэффициентов), вы получаете верхнюю границу по количеству ошибок кодовых слов. Можно победить эту границу, но для большого минимального расстояния это не легко. В этом режиме это очень хорошая граница.