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

[JohnKorsh]

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

[Fat Robot]

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

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

[JohnKorsh]

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

[JohnKorsh]

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

[thermit]

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

Вы, похоже, пытаетесь решить задачу, которая давно решена.
Поиск на множестве 2^n кодовых слов отстоящих на расстояние не менее заданного (dmin) эквивалентно построению кода исправляющего ошибки с корректирующей способностью t = floor( (dmin-1)/2 ). Максимальное число кодовых слов кода определяется границей хэмминга.
Существует большое количество кодов, которые вам подойдут. Например БЧХ код (127,43) имеет dmin=29. Не хватит 43-х бит для алфавита и адресации устройств - можно взять код круче. Короче говоря, ваша проблема не совсем понятна.

[JohnKorsh]

Добрый день! bbq, спасибо за идею. Просто и изящно. Серьёзные алгоритмы, конечное использовать можно, но железо - микроконтроллер, питание надо очень сильно экономить, а серьёзный алгоритм требует много вычислений, то есть потребляет. Поэтому использую сравнение, благо, алфавит ограничен.

thermit, спасибо за границу Хемминга. Чувствовал, что это давным-давно найдено и снова забыто такими, как я.