[JohnKorsh 1]

Добрый день! Не подскажет ли кто алгоритм поиска кодовых слов с расстоянием Хемминга не менее заданного?

Прямой перебор (счётчик от 0 и до бесконечности) работает, но занимает много времени - с ростом числа слов время поиска возрастает по экспоненте.

И ещё. Есть ли формула, определяющее максимально возможное количество слов кода с заданным расстоянием Хемминга по расстоянию Хемминга [бит] и максимально допустимой длине кода [бит]?

[FatRobot 0]

А почему по экспоненте?

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

 

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

 

[JohnKorsh 1]

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

[JohnKorsh 1]

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

[bbg 0]

конечно... это обычное "цэ из эн по ка" где "эн" - длина слова в битах, "ка" - ваше "расстояние хэмминга" или число несовпадающих бит, число таких наборов (формула числа сочетаний) это n!/k!/(n-k)!

 

Есть ли формула, определяющее максимально возможное количество слов кода с заданным расстоянием Хемминга по расстоянию Хемминга [бит] и максимально допустимой длине кода [бит]?

 

[JohnKorsh 1]

Спасибо, но, к сожалению, комбинаторная формула не подходит - ведь результат зависит не только от числа перестановок но и от положения значащих 1, от того какое расстояние между уже найденными словами. Так, для кода длиной 11 бит и с Хемминговым расстоянием 7 комбинаторная формула даёт более 300 комбинаций. А прямой перебор выявляет только 4 комбинации. Ещё раз - подходят не любые перестановки - для каждой перестановки надо вычислять Хеммингово расстояние между уже найденными словами.

[bbg 0]

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

 

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

[thermit 1]

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

 

Вы, похоже, пытаетесь решить задачу, которая давно решена.

Поиск на множестве 2^n кодовых слов отстоящих на расстояние не менее заданного (dmin) эквивалентно построению кода исправляющего ошибки с корректирующей способностью t = floor( (dmin-1)/2 ). Максимальное число кодовых слов кода определяется границей хэмминга.

Существует большое количество кодов, которые вам подойдут. Например БЧХ код (127,43) имеет dmin=29. Не хватит 43-х бит для алфавита и адресации устройств - можно взять код круче. Короче говоря, ваша проблема не совсем понятна.

 

 

[JohnKorsh 1]

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

 

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