пространство Хемминга

Автор темы serega126 
ОбъявленияПоследний пост
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
ОбъявлениеКниги по математике и экономике в добрые руки!10.08.2023 09:45
29.10.2012 00:01
пространство Хемминга
Скажу сразу я не математик! Так что не ругайтесь если что не правильно сформулировал. Может есть у кого нибуть варианты покрытия для 4из7 для троичного алфавита.Предполагается что таких вариантов 9 ,но меньше чем 12 сформировать не удается
29.10.2012 01:56
Просьба уточнить
Поскольку я знаком с вашими задачами по предыдущим вопросам, то хотелось бы уточнить постановку. Действительно ли эта задача состоит в минимальном покрытии пространства Хемминга E(7) над троичным алфавитом шарами радиуса 3? При таком покрытии код A, состоящий из центров шаров обладает следующим свойством:
- Для любой последовательности x из E(7) найдется кодовое слово a из A, совпадающее с x не менее, чем в 4-х позициях.
Если это так, то, мне представляется, что ваш результат с |A|=12 очень хорош.
Если нетрудно, то приведите этот код. Правда, сомневаюсь, что его удастся улучшить.
29.10.2012 04:31
Кто такой Хеминг?
Кто такое Хэминг?
30.10.2012 04:09
И все-таки ... ???
1. Положительное трактование вашей молчаливой реакции на сообщение несколько затруднительно.
Вопрос сводился лишь к правильному пониманию вашей задачи. Действительно ли нужно обеспечить совпадение произвольной 7-миэлементной последовательности с подходящим словом кода в 4-х позициях (при этом радиус покрытия 3) или совпадение в 3-х позициях (т. е. радиус покрытия $r=4$)? Для первого варианта постановки код, о котором вы говорите, представляется весьма хорошим. Хотелось бы убедиться, что он тот, который соответствует моему пониманию постановки задачи.
2. По поводу вашего вопроса по e-mail (не удивляйтесь - я сменил nickname, почту на sadcamel просматриваю крайне редко). Этот вопрос перевожу на язык покрытий. Задача состоит в построении минимального покрытия $E^{15}$ шарами радиуса $ 6. $ При этом код обеспечит в вашей терминологии «ловлю» любой троичной последовательности длины $n=15 $ по $m=9 $ позициям. Здесь также хотелось бы удостовериться в правильном понимании вашей задачи.
Если задача понята правильно, то ваш результат$ (M=|A|=243) $выглядит слабым. Даже прикидочные оценки дают $M<220. $Кроме того, я проверил такую элементарную (и заведомо неэффективную) конструкцию:
• вспомнил про код $A_1(6,4,17), $ который построил в вашей теме «Тотализатор» $ (n_1=6, M_1=17, r_1=2, $ «ловит» $m_1=4 $ символа из $ 6$);
• записал по наитию $11 $кодовых слов длины $9, $которыми образовал код $A_2(9,5,11) $ («ловит» $ 5 $ символов из $9$);
• подумал о том, что код $ A= A_1\times A_2, $ полученный в виде прямого произведения кодов $A_1 $ и $A_2$ (т. е. $M=17*11=187 $с конкатенацией последовательностей), имеет параметры $n=n_1+n_2=15, m=m_1+m_2=9, $ т. е. должен «ловить» $9 $символов из $15. $
Если в моих рассуждениях нет ошибки (нужно проверить!), то даже такая простая прикидка дает результат, намного лучше вашего.
3. Может быть, кто-нибудь из общающихся здесь математиков подскажет информацию по верхним границам для мощности покрывающего кода в пространствах Хемминга? Нижняя граница может быть получена на основе элементарных соотношений объемов пространства и шара (как двойственный аналог верхней границы Хемминга для упаковки шаров). Методики покрытий, основанные на «раздутии» упаковок дают очень плохие результаты.
30.10.2012 06:32
уточнение
Цитата
yog-urt
Поскольку я знаком с вашими задачами по предыдущим вопросам, то хотелось бы уточнить постановку. Действительно ли эта задача состоит в минимальном покрытии пространства Хемминга E(7) над троичным алфавитом шарами радиуса 3? При таком покрытии код A, состоящий из центров шаров обладает следующим свойством:
- Для любой последовательности x из E(7) найдется кодовое слово a из A, совпадающее с x не менее, чем в 4-х позициях.
Если это так, то, мне представляется, что ваш результат с |A|=12 очень хорош.
Если нетрудно, то приведите этот код. Правда, сомневаюсь, что его удастся улучшить.


1 4 7 10 14 16 20
1 4 7 10 14 18 21
1 4 7 10 13 16 21
1 4 7 10 15 17 19
2 5 8 11 14 16 21
2 5 8 11 13 18 19
2 5 8 11 13 17 20
2 5 8 11 15 18 20
3 6 9 12 14 17 19
3 6 9 12 13 18 20
3 6 9 12 15 16 19
3 6 9 12 15 17 21
30.10.2012 07:31
ответ
Цитата
yog-urt
Поскольку я знаком с вашими задачами по предыдущим вопросам, то хотелось бы уточнить постановку. Действительно ли эта задача состоит в минимальном покрытии пространства Хемминга E(7) над троичным алфавитом шарами радиуса 3? При таком покрытии код A, состоящий из центров шаров обладает следующим свойством:
- Для любой последовательности x из E(7) найдется кодовое слово a из A, совпадающее с x не менее, чем в 4-х позициях.
Если это так, то, мне представляется, что ваш результат с |A|=12 очень хорош.
Если нетрудно, то приведите этот код. Правда, сомневаюсь, что его удастся улучшить.

Цитата

20101
2010201
2010202
201021
2012
202
21
102012
10202
12012
120102
120101
12021
12020
12102
1210121
1210120
121010
1212
30.10.2012 09:15
И все-таки ... ???
Цитата
yog-urt
1. Положительное трактование вашей молчаливой реакции на сообщение несколько затруднительно.
Вопрос сводился лишь к правильному пониманию вашей задачи. Действительно ли нужно обеспечить совпадение произвольной 7-миэлементной последовательности с подходящим словом кода в 4-х позициях (при этом радиус покрытия 3) или совпадение в 3-х позициях (т. е. радиус покрытия $r=4$)? Для первого варианта постановки код, о котором вы говорите, представляется весьма хорошим. Хотелось бы убедиться, что он тот, который соответствует моему пониманию постановки задачи.
2. По поводу вашего вопроса по e-mail (не удивляйтесь - я сменил nickname, почту на sadcamel просматриваю крайне редко). Этот вопрос перевожу на язык покрытий. Задача состоит в построении минимального покрытия $E^{15}$ шарами радиуса $ 6. $ При этом код обеспечит в вашей терминологии «ловлю» любой троичной последовательности длины $n=15 $ по $m=9 $ позициям. Здесь также хотелось бы удостовериться в правильном понимании вашей задачи.
Если задача понята правильно, то ваш результат$ (M=|A|=243) $выглядит слабым. Даже прикидочные оценки дают $M<220. $Кроме того, я проверил такую элементарную (и заведомо неэффективную) конструкцию:
• вспомнил про код $A_1(6,4,17), $ который построил в вашей теме «Тотализатор» $ (n_1=6, M_1=17, r_1=2, $ «ловит» $m_1=4 $ символа из $ 6$);
• записал по наитию $11 $кодовых слов длины $9, $которыми образовал код $A_2(9,5,11) $ («ловит» $ 5 $ символов из $9$);
• подумал о том, что код $ A= A_1\times A_2, $ полученный в виде прямого произведения кодов $A_1 $ и $A_2$ (т. е. $M=17*11=187 $с конкатенацией последовательностей), имеет параметры $n=n_1+n_2=15, m=m_1+m_2=9, $ т. е. должен «ловить» $9 $символов из $15. $
Если в моих рассуждениях нет ошибки (нужно проверить!), то даже такая простая прикидка дает результат, намного лучше вашего.
3. Может быть, кто-нибудь из общающихся здесь математиков подскажет информацию по верхним границам для мощности покрывающего кода в пространствах Хемминга? Нижняя граница может быть получена на основе элементарных соотношений объемов пространства и шара (как двойственный аналог верхней границы Хемминга для упаковки шаров). Методики покрытий, основанные на «раздутии» упаковок дают очень плохие результаты.




свои 243 варианта я получил так: набор покрытия из 81 варианта (6из8) помножил на 3 варианта (3из7)
30.10.2012 11:04
Замечательный код!
Цитата
serega126
1 4 7 10 14 16 20
1 4 7 10 14 18 21
1 4 7 10 13 16 21
.........................
Ваш код, Serega126, работает и удивительно хорош !!! Спасибо!
При наличии времени еще подумаю. Эти задачи сильно увлекают и отвлекают...
30.10.2012 11:14
В добавление..
На всякий случай привожу код с параметрами $n=9,m=5,r=4,M=11$
$0 0 0 0 0 0 0 0 0$
$1 2 0 2 0 0 2 2 0$
$2 1 2 1 2 0 1 2 1$
$0 2 1 1 1 1 2 2 2$
$2 1 2 0 1 2 2 0 1$
$0 2 2 2 2 1 0 1 1$
$0 0 2 0 2 2 1 1 0$
$1 1 1 2 0 2 1 1 2$
$1 0 0 1 2 1 1 0 2$
$2 1 0 1 1 1 0 1 0$
$2 2 0 0 2 2 0 2 2$
Нужно проверить.
Редактирование:
Проверка показала, что параметры этого кода не $(9,5,11), r=4,$ а $](9,4,11), r=5$. Придется что-нибудь придумывать...



Редактировалось 1 раз(а). Последний 30.10.2012 12:38.
30.10.2012 12:39
В добавление..
Цитата
yog-urt
На всякий случай привожу код с параметрами $n=9,m=5,r=4,M=11$
$0 0 0 0 0 0 0 0 0$
$1 2 0 2 0 0 2 2 0$
$2 1 2 1 2 0 1 2 1$
$0 2 1 1 1 1 2 2 2$
$2 1 2 0 1 2 2 0 1$
$0 2 2 2 2 1 0 1 1$
$0 0 2 0 2 2 1 1 0$
$1 1 1 2 0 2 1 1 2$
$1 0 0 1 2 1 1 0 2$
$2 1 0 1 1 1 0 1 0$
$2 2 0 0 2 2 0 2 2$
Нужно проверить.


переложил в такой вид:

1 4 7 10 13 16 19 22 25
2 6 7 12 13 16 21 24 25
3 5 9 11 15 16 20 24 26
1 6 8 11 14 17 21 24 27
3 5 9 10 14 18 21 22 26
1 6 9 12 15 17 19 23 26
1 6 9 10 15 18 20 23 25
2 5 8 12 13 18 20 23 27
2 4 7 11 15 17 20 22 27
3 5 7 11 14 17 19 23 25
3 6 7 10 15 18 19 24 27

где1,4,7,10,13,16,19,22,25 это 0 ...2,5,8,11,14,17,20,23,26 это 1....и 3,6,9,13,15,18,21,24,27 это 2

прогнал по полному массиву....в остатке осталось 1758вар.
01.11.2012 18:07
вопрос
Yog-urt, а можно ли покрытие 9из15 двоичного алфавита (8 вариантов) превратить в минимальное покрытие 9из15 троичного алфавита?
02.11.2012 02:27
"Кабы ведать о том, кабы знать ..."
Еще раз просмотрел ваши коды и убедился, что они тщательно продуманы и оптимизированы - мои попытки улучшить оказались безуспешными. Использованы методы каскадирования, причем составляющие коды выбраны очень удачно. Так, код $K(4,3,9) $ (здесь параметры $ (n,m,M) $ соответствуют в вашей терминологии $ «m$ из $n» $) – это, с одной стороны, совершенный код Хемминга, упаковывающий в $E^4$ шары радиуса $r=1 $ «без просвета» и, следовательно, покрывающий этими шарами все пространство $E^4$ (без пересечения), и, с другой, - конечная аффинная плоскость порядка 3 (уникальная для данной задачи). Удачными оказались конструкции $K(15,9,3^5)=K(4,3,9) \times K(4,3,9) \times K(7,3,3) $ и $K(7,4,12). $
Здесь я для взаимопонимания еще раз поясню связь радиуса покрытия r с числом m гарантированных совпадений произвольной последовательности из $E^n $ с подходящим кодовым словом. А именно, если шары радиуса r покрывают пространство $E^n, $то любая последовательность из$ E^n $ попадет в некоторый шар, центром которого является кодовое слово. Следовательно, расстояние от этой последовательности до кодового слова (число несовпадающих позиций) не более $r, $ и значит, число совпадающих позиций не менее $n-r, $ т. е. гарантируется $m= n-r.$
По существу вопроса. Отрицательный ответ дать нельзя, потому что теоретически такое преобразование (двух двоичных кодов в троичный) существует. Но, понятно, что вопрос касается каскадирования, например, поэлементного. Если допустим, из пары двоичных кодов $К1(15,9,M1) $ и $К2(15,9,M2) $ над разными алфавитами путем объединения алфавитов построить четверичный код с $К3(15,9,M3), $ а затем, объединив два элемента алфавита (из четырех) перейти к троичному коду), то тогда он будет иметь нужные параметры $n=15, m=9. $ Но…
Четверичный код будет иметь нужные параметры $ (n=15, m=9), $ если, например, $К1(15,9,M1) $ – обычный код покрытия, а $К2(15,9,M2) $ обладает дополнительным свойством – он не просто содержит слово, совпадающее в каких-то 9-ти позициях с любой последовательностью из $E^{15}(2), $ а для любой последовательности из $E^{15}(2) $ и любых 9-ти позиций содержит слово, совпадающее с данной последовательностью в этих позициях. Скорее всего, для такой конструкции потребуется слишком большая мощность кода $K2. $
Каскадирование упрощает построения, но ведет к потере эффективности. Кроме того, переход от четверичного кода к троичному также влечет существенные потери.
Оценка. Параметры кодов Хемминга над $GF(2^2): n=(4^i-1)/3, r=1, m=n-1. $ Например, при $i=2$ имеем код $K(5,4,64) $ – очень плохо. Параметры кодов Хемминга над $ GF(3): n=(3^i-1)/2, r=1, m=n-1. $ При $i=2$ – вами использован. При $i=3, M=3^{10}$ – вам не интересен. Уникальный совершенный код Голея над $GF(3) $ имеет параметры $n=11, r=2, m=9, M=3^6. $
Придумывать более тонкие методы построения кодов покрытия интересно, тем более, что они увязаны с комбинаторными проблемами высокого уровня, но сейчас я на это «пойтить не могу» (другие задачи).
Может быть, вы имели в виду другие конструкции и варианты каскадирования? Предлагайте. При возможности посмотрю, а пока перерыв - нужно переключиться на дела.



Редактировалось 1 раз(а). Последний 02.11.2012 10:22.
02.11.2012 12:33
уточнение...
если взять код K(4,3,9) , то глядя на него видно что это самостаятельная группа полученная не перемножением каких- то составляющих. Так у меня вопрос в следующем ....если задатся целью построить покрытие 9из15 такой же самостоятельной группой то это невозможно,точные способы такого построения не известны или это очень трудоемкая работа ? Когда то на просторах сети кто то хвалился что у него есть такое покрытие состоящее из 34-40 вариатов...точно не помню
02.11.2012 15:46
Уточнения...
Код $ K(4,3,9) ] $ строился как код упаковки, при этом он оказался совершенным.
Поясню. Он содержит $ M=9 $ слов, каждое из которых удалено друг от друга на расстояние не менее 3, т. е. шары радиуса $ r=1 $ не пересекаются. Каждый шар содержит само кодовое слово ( 1 шт,) + 4*2 последовательностей, находящихся от центра на расстоянии 1, т. е. всего $S(r=1)=9$ последовательностей. Все шары содержат $ S(1)*M=9*9= 81 $ последовательность, т. е. все последовательности $ E^4. $ Таким образом, оказалось, что этот код упаковки является и кодом покрытия.
Для построения кодов покрытия есть инструменты: 1) использовать совершенные коды упаковки, 2) использовать подобранные эвристическими или вычислительными методами коды для малых размерностей задач, 3) как-то комбинировать 1 и 2.
По коду $ K(15,9,M=?). $ Нужно как-то искать. Пути улучшения есть.
Цитата
serega126
Когда то на просторах сети кто то хвалился что у него есть такое покрытие состоящее из 34-40 вариатов...точно не помню
Наверное, это был не я – не думаю, что меня так могло переклинить.
Нижняя оценка числа M: Для $ K(15,9,M) $ радиус покрытия $ r=6. $ Объем шара $ S(6)= \sum^6_{i=0} C^i_{15}2^i= 442347, $ число шаров $ M \ge 3^{15}/S(6) \Rightarrow M \ge 33. $
Оценка грубая, но что-либо бездоказательно утверждать весьма опасно.
И еще – вопросы об оптимизации стратегий «угадывания» не обсуждаем. Мы просто решаем задачи покрытия.



Редактировалось 1 раз(а). Последний 02.11.2012 16:55.
08.11.2012 00:19
вопрос
Yog-Urt ,как по вашему мнению можно ли код 6из10 (51вариант) уменьшить до 36 вариантов ?

1 5 7 12 15 16 21 24 27 29
1 5 9 10 13 16 21 24 27 29
1 5 9 11 14 17 21 24 27 29
1 4 8 10 14 17 21 24 27 29
1 6 7 11 15 18 21 24 27 29
1 6 9 12 13 18 21 24 27 29
3 5 7 12 14 18 21 24 27 29
3 5 9 10 15 18 21 24 27 29
3 4 8 11 13 16 21 24 27 29
3 6 7 10 13 16 21 24 27 29
3 6 7 11 14 17 21 24 27 29
3 6 9 12 15 17 21 24 27 29
2 5 8 11 13 17 21 24 27 29
2 4 8 12 15 17 21 24 27 29
2 4 7 10 13 17 21 24 27 29
2 4 9 11 14 16 21 24 27 29
2 6 8 10 14 16 21 24 27 29
1 5 7 12 15 16 20 23 26 28
1 5 9 10 13 16 20 23 26 28
1 5 9 11 14 17 20 23 26 28
1 4 8 10 14 17 20 23 26 28
1 6 7 11 15 18 20 23 26 28
1 6 9 12 13 18 20 23 26 28
3 5 7 12 14 18 20 23 26 28
3 5 9 10 15 18 20 23 26 28
3 4 8 11 13 16 20 23 26 28
3 6 7 10 13 16 20 23 26 28
3 6 7 11 14 17 20 23 26 28
3 6 9 12 15 17 20 23 26 28
2 5 8 11 13 17 20 23 26 28
2 4 8 12 15 17 20 23 26 28
2 4 7 10 13 17 20 23 26 28
2 4 9 11 14 16 20 23 26 28
2 6 8 10 14 16 20 23 26 28
1 5 7 12 15 16 19 22 25 30
1 5 9 10 13 16 19 22 25 30
1 5 9 11 14 17 19 22 25 30
1 4 8 10 14 17 19 22 25 30
1 6 7 11 15 18 19 22 25 30
1 6 9 12 13 18 19 22 25 30
3 5 7 12 14 18 19 22 25 30
3 5 9 10 15 18 19 22 25 30
3 4 8 11 13 16 19 22 25 30
3 6 7 10 13 16 19 22 25 30
3 6 7 11 14 17 19 22 25 30
3 6 9 12 15 17 19 22 25 30
2 5 8 11 13 17 19 22 25 30
2 4 8 12 15 17 19 22 25 30
2 4 7 10 13 17 19 22 25 30
2 4 9 11 14 16 19 22 25 30
2 6 8 10 14 16 19 22 25 30
08.11.2012 19:03
"Еще не известно"
Цитата
serega126
...как по вашему мнению можно ли код 6из10 (51вариант) уменьшить до 36 вариантов ?
1. Обращу это вопрос ко всем участникам форума.
2. Пояснение к коду:
- Если записанные последовательности переписать в остатках от деления на 3, то получится код над алфавитом {0,1,2}., содержащий 51 слово
- Полученный код обладает тем свойством, что для любой последовательности длины 10 над этим алфавитом найдется кодовое слово, совпадающее с этой последовательностью не менее, чем в 6 позициях (проверено).
Можно ли построить код с меньшим числом слов? Возможно, у кого-нибудь появятся идеи.
Я сейчас ничего определенного сказать не могу. Известные грубые оценки не позволяют сделать однозначный вывод. До понедельника не будет времени даже посмотреть, потом отвечу.



Редактировалось 1 раз(а). Последний 08.11.2012 19:04.
13.11.2012 01:19
О конструировании кодов покрытий над GF(3)
1. Все ваши построения используют обычные конструкции покрытий, причем удачно. В том числе упомянутый в вашем предыдущем посте код $K(10,6,51)=K(6,4,17) \times K(4,2,3).$
2. Спрашивать о существовании кодов, удовлетворяющих известным границам, бессмыслено. Это то же самое, что спросить, существует ли 5 попарно ортогональных латинских квадратов порядка 10. Код с M<51 предположительно существует, а с M=36 – большой вопрос.
3. Методы конструирования ранее обозначены. Естественно, что композиции ведут к потерям эффективности. Наглядный пример – код K(6,4,17), не представимый в виде композиции.
4. Код с параметрами K(15,9, M<243) определенно нужно искать. Наиболее просто было бы его построить на базе кода K(11,7,M<81), который, в свою очередь, попытаться получить усечением совершенного кода Голея над GF(3)) . Один из известных приемов усечения - сохранение в коде лишь слов, удовлетворяющих проверке на четность (этого не достаточно), При этом, очевидно, изменяется радиус покрытия, но усеченный код, как известно, сохраняет хорошие свойства (регулярность). Придумайте и проверьте другие варианты усечения – это интересно. Укорочение кода путем отбрасывания части информационных элементов также дает код с хорошими свойствами покрытия, но приводит к уменьшению длины последовательности, т. е. таким образом вы можете получать коды с n<11. Поработайте с совершенными кодами, посмотрите на их метрические свойства и спектры, покомбинируйте...
5. В этой области много работ (например, наши замечательные математики Л.А.Бассалыго, В.А.Зиновьев), см. также библиографию к их работам. Как правило, ищутся регулярные конструкции, в частности, на базе совершенных кодов. В вашем случае для решения конкретных задач небольшой размерности можно поискать более эффективные коды на основе направленных вычислительных процедур.
05.06.2015 18:41
О состоянии вопроса (от K. Knop'a)
Достаточно полно этот вопрос раскрыт здесь

PS. Пояснение: Эта тема на нашем форуме была начата этим вопросом.



Редактировалось 1 раз(а). Последний 05.06.2015 18:52.
16.08.2015 08:44
Перемножение покрытий
Добрый день yog-urt! А каким образом умножаются покрытия допустим из 81 варианта (6из8) на 3 варианта (3из7)?
16.08.2015 21:31
Произведение кодов
Приветствую!
Коды покрытия – это множества. Прямое произведение множеств $ A $ и $ B $ (обозначение $ A \times B ) $ – это множество пар $ (a, b), $ таких что $ a \in A, b \in B. $ С учетом этого произведение указанных кодов покрытия $ K_1, K_2 $ представляет собой код, содержащий все 243 последовательности длины 15, у которых первые 8 символов принадлежат коду $ K_1, $ а последние 7 символов – коду $ K_2. $ Параметры $ n, r, M $ (соответственно длина кодового слова, радиус покрытия, мощность кода) произведения кодов покрытия удовлетворяют условиям: $ n= n_1+n_2, r= r_1+r_2, M=M_1M_2. $ В этой теме параметр v кода в обозначении $ K(n, v, M) $ имеет смысл $ v=n-r. $ Как нетрудно видеть, для произведения кодов $ v= v_1+v_2. $ Таким образом, код $ K(n, v, M), $ образованный умножением кодов $ К(8, 6, 81) $ и $ К(7, 3, 3), $ имеет параметры $ n=15, v= 9, r= 6, M=243. $
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти