Не по Delphi (поиск алгорима)

← →
JohnKorsh (2014-01-21 11:14) [0]

Добрый день!
Мне нужно найти кодовые слова с расстоянием Хемминга не менее заданного. Не подскажет ли кто алгоритм поиска? (Прямой перебор занимает чересчур много времени при большом количестве слов).

← →
Jeer © (2014-01-21 11:54) [1]

Это к экстрасенсам.

← →
MBo © (2014-01-21 11:58) [2]

Найти где - в списке? Тогда надо загнать список в подходящую структуру данных:
http://stackoverflow.com/questions/6389841/efficiently-find-binary-strings-with-low-hamming-distance-in-large-set

← →
JohnKorsh (2014-01-27 09:14) [3]

Добрый день! Нет, не в списке. Пользователь задаёт длину кода и требуемое Хеммингово расстояние. Я должен выдать таблмцу со ВСЕМИ допустимыми кодовыми словами. Простой перебор хорошо работает до патаметров 25, 11. Дальше поиск очень сильно замедляется. Думаю, что есть формула, может, рекурентная для выбора слов без перебора. Может, кто встречал?

← →
MBo © (2014-01-27 09:27) [4]

Почему тогда речь идет о поиске? Генерация всех вариантов в любом случае не будет быстрой, ведь их количество экспоненциально растет (грубо - 2^n)

Вот пример генерации всех битовых последовательностей длины N, содержащих не более M установленных битов (инвертировать - будет не менее N-M установленных битов).

procedure GenComb(N, M, K, BitPos, Value: Integer); var i: Integer; begin Memo1.Lines.Add(Copy(IntToBin(Value), 25, 8)); if K < M then for i := BitPos + 1 to N - 1 do GenComb(N, M, K + 1, i, Value or (1 shl i)); end; begin GenComb(5, 3, 0, -1, 0);

← →
JohnKorsh (2014-01-28 22:48) [5]

Да, конечное, не быстрая. Испытываю на себе. Пользователь вводит длину кода (до 2048 бит) и желаемое Хеммингово (в среднем, где - то 0,01 от длины кода) расстояние. Я должен сгенерировать все возможные слова. Ну или попытаться, если Хеммингово расстояние мало. Я делаю тупым перебором - инкрементирую счётчик сверхбольших целых и, на каждом шаге сравниваю со всеми элементами динамического массива на предмет отличий. Если не менее заданного, то пополняю массив. Вывел для себя на график - по x - целые числа, по y - найденные слова. растёт кусочно-линейно. Думаю, что есть алгоритм, может рекуррентный, поиска слов длиной N с расстоянием не менее заданного. Не встречал ли кто?

← →
MBo © (2014-01-29 09:26) [6]

← →
MBo © (2014-01-29 09:42) [7]

>Я должен сгенерировать все возможные слова
На всякий случай - кодов длиной 2048 с расстоянием до 20 включительно будет примерно 6*10^47 штук.

← →
MBo © (2014-01-29 10:23) [8]

>Не встречал ли кто?
Встречал в [4]

← →
JohnKorsh (2014-01-29 16:10) [9]

Спасибо. С первого раза просмотрел.

← →
JohnKorsh (2014-01-30 21:47) [10]

Добрый день! Нет, всё-таки не пойму. Насчёт [4]. Проверил - получаются числа, согласно указанному Вами алгоритму, по примеру - 26 штук. 5 разрядов, не более 3 установленных битов. Но расстояние Хемминга между ними - колеблется от 1 до 4 (имеется ввиду xor каждого с каждым числом с подсчётом количества 1). Ведь имеет значение и позиция, в которой установлен бит. Или я не понимаю Вашу идею? Или я плохо объяснил, свою задачу. Из ряда натуральных чисел надо составить наиболее плотно упакованный массив чисел с расстоянием Хемминга не менее заданного.

← →
ТНЕ картман (2014-01-30 21:57) [11]

> JohnKorsh (30.01.14 21:47) [10]

[4] + [2]?

← →
MBo © (2014-01-30 22:47) [12]

Расстояние Хемминга обычно используют при сравнении с образцом. Поэтому я и предложил алгоритм для генерации всех масок, xor-я образец с которыми, можно получить слова с нужным отличием от образца.

Фраза, что нужно расстояние между ними -т.е. между словами в наборе - прозвучала впервые. А как понимать наиболее плотно упакованный массив?

← →
JohnKorsh (2014-01-31 18:46) [13]

Именно так мы и используем. При проектировании систем радиосвязи с ограниченным алфавитом проще сравнить принятую бинарную последовательность с имеющимися образцами и выбрать самый близкий из них. Это требует меньше энергозатрат, чем реализвция алгоримов Рида-Соломона или Виттерби. Следовательно, нужно набрать кодовые слова заданной длины с расстоянием Хемминга не менее заданного между всеми словами. Железа мы выпускаем много и все железки должны работать независимо - это к тому, что Хеммингово расстояние между всвсеми найденными элементами не менее заданного. Ничего более умного, чем тупой перебор я не придумал. Думаю, эта задача давно решена в теории кодирования - алгоритм выработки слов с заданным расстоянием Хемминга и сколько таких слов содержится в кодовом слове заданной длины. Но поиск в Интернет не дал результатов и изучение учёных книжек тоже. Вот и обратился к народу.

← →
JohnKorsh (2014-01-31 18:49) [14]

Да, забыл - наиболее плотно упакован - ну, если мы досчитали до какого то числа в переборе, то, если упаковка плотная, мы даём гарантию, что не пропустили ни одного подходящего слова. Если не стоит такого требования, то задача проста, но и длина кодов быстро возрастает.

← →
MBo © (2014-01-31 19:10) [15]

Для расстояний n/2 есть матрицы Адамара.
Что до маленьких расстояний - это инженеры по связи и корр. кодам должны знать...

← →
JohnKorsh (2014-02-03 09:45) [16]

Спасибо

← →
JohnKorsh (2014-02-08 13:39) [17]

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

← →
картман © (2014-02-08 15:03) [18]

а скока есть памяти и что такое в данном контексте алфавит - кол-во символов или слов?

← →
JohnKorsh (2014-02-09 11:50) [19]

Если сигнал идёт по эфиру от датчика, на, например, с 12-разрядного АЦП, то значений 2^12, а после кодирования их станет ещё больше - добавятся биты, ответственные за обнаружение и исправление ошибок. В этом случае отлично работает кодирование и декодирование Рида-Соломон и другие вычислительные алгоритмы, так как сравнивать так много значений с образцами неимоверно долго. У меня же команд немного - десяток - это и имеется в виду под ограниченным алфавитом. Их проще сравнить с принятым образцом и выбрать с наименьшим Хемминговым расстоянием.

← →
JohnKorsh (2014-02-09 11:56) [20]

Да, ещё, если знать алгоритм нахождения слов с заданным расстоянием Хемминга, то и памяти надо не особо много - например, в 11-битном коде с расстоянием 7 всего 4 слова. У меня около трёхсот бит и расстояние порядка 30, то есть числа сравнимы. Прямой перебор 2^300 - это лет сто, а то и поболее. Слова расположены на оси действительных чисел неравномерно - это и понятно - старшие разряды при переборе меняются всё медленнее и медленнее - поэтому, подходящие слова ищутся всё медленнее.

ничего не понял

Когда расстояние = 2^n, и количество разрядов = 2^(N+1)-1? то есть простой алгоритм генерации 2^(N+1) таких слов ;)

← →
ничего не понял (2014-02-10 14:55) [23]

> JohnKorsh (30.01.14 21:47) [10]
> Нет, всё-таки не пойму. Насчёт [4]...
> ...Но расстояние Хемминга между ними - колеблется от 1 до 4 (имеется ввиду xor каждого с каждым числом с подсчётом количества 1)

вот это непонятно - зачем вы искали расстояние Хемминга между всеми числами внутри списка чисел с меньшим или равным заданному расстоянием Хемминга ОТ НУЛЯ
(то есть от числа с заданным количеством бит, в котором все биты сброшены)

для ясности: рХ(a, c) <= pX(a,b)+pX(b,c) (рХ - расстояние Хемминга)

для получения из этого списка нужного вам списка чисел, отличающихся от ЗАДАННОГО ЧИСЛА на расстояние Хемминга, меньшее или равное заданному, нужно каждый член исходного списка проXORить с этим заданным числом - это вроде очевидно, но возникают сомнение, что вы это поняли - извините, если что)

и, видимо, стоит отсортировать исходный список по количеству единичек (это в случае, если алгоритм в [4] не выдает сразу отсортированный список - тут не разобрался)

Человеку нужно вот ЭТО
http://www.ee.unb.ca/cgi-bin/tervo/hamming.pl?X=+Generate+&L=11&D=7&T=0000000
Только на числах, которые там допустимы, вполне можно обойтись полным перебором

← →
ШАША (2014-02-11 02:40) [25]

Удалено модератором

← →
ШАША (2014-02-11 02:46) [26]

Удалено модератором

← →
ШАША (2014-02-11 12:52) [27]

Удалено модератором

← →
JohnKorsh (2014-02-12 21:32) [28]

Спасибо, icWasya. Мир Delphi тесен.

Не по Delphi (поиск алгорима) Найти похожие ветки