Алгоритм поиска кодовых слов., Кодовые слова с заданным расстоянием Хемминга. Опции

[JohnKorsh]

Добрый день! Не подскажет ли кто алгоритм поиска кодовых слов с расстоянием Хемминга не менее заданного?
Прямой перебор (счётчик от 0 и до бесконечности) работает, но занимает много времени - с ростом числа слов время поиска возрастает по экспоненте.
И ещё. Есть ли формула, определяющее максимально возможное количество слов кода с заданным расстоянием Хемминга по расстоянию Хемминга [бит] и максимально допустимой длине кода [бит]?

[Fat Robot]

А почему по экспоненте?
(n*n-n), по-моему, сложность простого перебора (n - размер ансамбля).

время поиска возрастает по экспоненте.

[JohnKorsh]

Добрый день! Наверное, Вы правы. Я написал чисто по ощущениям. Приходится, к тому же сравнивать на допустимое расстояние Хемминга текущее значение счётчика с постоянно растущим количеством найденных слов. А по сути ничего не посоветуете?

[JohnKorsh]

Добрый день! По прежнему ищу. Перерыл Интернет - форумы по теории кодирования - студенческие, им бы самим помочь. Может кто посоветует ссылку? Ещё раз чего я ищу. Система связи с ограниченным алфавитом. Использование алгоритмов исправления ошибок типа Рида-Соломона в данном случае не очень удобно - много вычислений, микроконтроллеру "тяжело". Проще сравнивать принятые слова со списком и смотреть, какое слово "ближе". Для этого эти слова нужно подобрать. Железок много, поэтому, в каждой - свой набор слов. Длина кода - порядка сотен бит. Используемое по допустимой вероятности ошибки Хеммингово расстояние порядка 25 и более бит. Прямой перебор неимоверно долг. Сейчас на сервере круглосуточно "трудится" программа - по три-четыре слова в день. Уверен, что существует алгоритм поиска слов длиной N с заранее заданным Хеминговым расстоянием d. Изучение найденных слов привело к таким выводам - если их записывать в двоичном коде, то все слова одинаковой длины (имеется ввиду, что впереди идут 0, дополняющий до заданной длины N) образуют группу. То есть, получив первое слово следующее получается добавлением d, затем, сложением двух получившихся слов и так до того, как исчерпаются все слова этой длины. (Под сложением я имею ввиду порязрядную операцию XOR). А дальше требуется добавить старший разряд. Не могу понять из списка слов как это происходит. Иногда добавляется d двоичных разрядов, иногда меньше, иногда больше. А найти решение надо - сразу резко упадёт потребление системы - не надо вычислять локатор ошибок и прочие ресурсоёмкие вещи. Даже на кафедры математики разных вузов писал, ну, понятно, что вежливо послали.

[bbg]

Меня терзают смутные сомнения, что Вы как-то излишне усложнили себе задачу. Вот несколько более конструктивный подход - нужно нагенерить для некоторого алфавита набор кодов с большим хэмминговым. Допустим, у нас есть генератор случайных чисел, генерим кодовые слова длины N "бит за битом", тогда примерно половина битов будет 1, другая 0, генерим еще одно такое слово (пятое, десятое) - всюду можно ожидать, что хэммингово расстояние между кодовыми словами будет с большой вероятностью близко к N/2, если размер алфавита много меньше мощности множества кодовых слов. Проверяем.. Алфавит - 256 символов, в качестве рэндомгенератора, не мудрствуя насчет генерации бита за битом, используем хороший криптоалгоритм, например, AES (хороший криптоалгоритм должен обеспечивать аваланш - то есть изменение одного бита на входе приводит к изменению примерно половины бит на выходе) Параметры - 128бит кодовое слово, 8 бит - символ алфавита, ключ для AES - просто нолики, на входе в AES массив из слова алфавита (байт) плюс 15 байт ноликов - результат 256 128-битных слов, у них минимальный между собой хэмминг 40, максимальный 89, в среднем 64 (только что набросал прогу и проверил). Так годится? (AES для народа сейчас есть даже в некоторых кристаллах приемопередатчиков, например, SPIRIT1)

Длина кода - порядка сотен бит. Используемое по допустимой вероятности ошибки Хеммингово расстояние порядка 25 и более бит. Прямой перебор неимоверно долг. Сейчас на сервере круглосуточно "трудится" программа - по три-четыре слова в день. Уверен, что существует алгоритм поиска слов длиной N с заранее заданным Хеминговым расстоянием d.