Форум мехмата МГУ по высшей математике
| Пользователям: | Аксиома — это истина, на которую не хватило доказательств. |
Форумы > Математика > Высшая математика > Тема |
Объявления | Последний пост | |
---|---|---|
Запущен новый раздел «Задачки и головоломки» | 29.08.2019 00:42 | |
Открыта свободная публикация вакансий для математиков | 26.09.2019 16:34 | |
Книги по математике и экономике в добрые руки! | 10.08.2023 09:45 |
29.10.2012 00:01 Дата регистрации: 12 лет назад Посты: 19 | пространство Хемминга Скажу сразу я не математик! Так что не ругайтесь если что не правильно сформулировал. Может есть у кого нибуть варианты покрытия для 4из7 для троичного алфавита.Предполагается что таких вариантов 9 ,но меньше чем 12 сформировать не удается |
29.10.2012 01:56 Дата регистрации: 12 лет назад Посты: 176 | Просьба уточнить Поскольку я знаком с вашими задачами по предыдущим вопросам, то хотелось бы уточнить постановку. Действительно ли эта задача состоит в минимальном покрытии пространства Хемминга E(7) над троичным алфавитом шарами радиуса 3? При таком покрытии код A, состоящий из центров шаров обладает следующим свойством: - Для любой последовательности x из E(7) найдется кодовое слово a из A, совпадающее с x не менее, чем в 4-х позициях. Если это так, то, мне представляется, что ваш результат с |A|=12 очень хорош. Если нетрудно, то приведите этот код. Правда, сомневаюсь, что его удастся улучшить. |
29.10.2012 04:31 Дата регистрации: 12 лет назад Посты: 58 | Кто такой Хеминг? Кто такое Хэминг? |
30.10.2012 04:09 Дата регистрации: 12 лет назад Посты: 176 | И все-таки ... ??? 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 Дата регистрации: 12 лет назад Посты: 19 | уточнение
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 Дата регистрации: 12 лет назад Посты: 58 | ответ
|
30.10.2012 09:15 Дата регистрации: 12 лет назад Посты: 19 | И все-таки ... ???
свои 243 варианта я получил так: набор покрытия из 81 варианта (6из8) помножил на 3 варианта (3из7) |
30.10.2012 11:04 Дата регистрации: 12 лет назад Посты: 176 | Замечательный код! Ваш код, Serega126, работает и удивительно хорош !!! Спасибо! При наличии времени еще подумаю. Эти задачи сильно увлекают и отвлекают... |
30.10.2012 11:14 Дата регистрации: 12 лет назад Посты: 176 | В добавление.. На всякий случай привожу код с параметрами $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 Дата регистрации: 12 лет назад Посты: 19 | В добавление..
переложил в такой вид: 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 Дата регистрации: 12 лет назад Посты: 19 | вопрос Yog-urt, а можно ли покрытие 9из15 двоичного алфавита (8 вариантов) превратить в минимальное покрытие 9из15 троичного алфавита? |
02.11.2012 02:27 Дата регистрации: 12 лет назад Посты: 176 | "Кабы ведать о том, кабы знать ..." Еще раз просмотрел ваши коды и убедился, что они тщательно продуманы и оптимизированы - мои попытки улучшить оказались безуспешными. Использованы методы каскадирования, причем составляющие коды выбраны очень удачно. Так, код $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 Дата регистрации: 12 лет назад Посты: 19 | уточнение... если взять код K(4,3,9) , то глядя на него видно что это самостаятельная группа полученная не перемножением каких- то составляющих. Так у меня вопрос в следующем ....если задатся целью построить покрытие 9из15 такой же самостоятельной группой то это невозможно,точные способы такого построения не известны или это очень трудоемкая работа ? Когда то на просторах сети кто то хвалился что у него есть такое покрытие состоящее из 34-40 вариатов...точно не помню |
02.11.2012 15:46 Дата регистрации: 12 лет назад Посты: 176 | Уточнения... Код $ 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=?). $ Нужно как-то искать. Пути улучшения есть. Наверное, это был не я – не думаю, что меня так могло переклинить. Нижняя оценка числа 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 Дата регистрации: 12 лет назад Посты: 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 Дата регистрации: 12 лет назад Посты: 176 | "Еще не известно" 1. Обращу это вопрос ко всем участникам форума. 2. Пояснение к коду: - Если записанные последовательности переписать в остатках от деления на 3, то получится код над алфавитом {0,1,2}., содержащий 51 слово - Полученный код обладает тем свойством, что для любой последовательности длины 10 над этим алфавитом найдется кодовое слово, совпадающее с этой последовательностью не менее, чем в 6 позициях (проверено). Можно ли построить код с меньшим числом слов? Возможно, у кого-нибудь появятся идеи. Я сейчас ничего определенного сказать не могу. Известные грубые оценки не позволяют сделать однозначный вывод. До понедельника не будет времени даже посмотреть, потом отвечу. Редактировалось 1 раз(а). Последний 08.11.2012 19:04. |
13.11.2012 01:19 Дата регистрации: 12 лет назад Посты: 176 | О конструировании кодов покрытий над 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 Дата регистрации: 12 лет назад Посты: 176 | О состоянии вопроса (от K. Knop'a) |
16.08.2015 08:44 Дата регистрации: 9 лет назад Посты: 4 | Перемножение покрытий Добрый день yog-urt! А каким образом умножаются покрытия допустим из 81 варианта (6из8) на 3 варианта (3из7)? |
16.08.2015 21:31 Дата регистрации: 12 лет назад Посты: 176 | Произведение кодов Приветствую! Коды покрытия – это множества. Прямое произведение множеств $ 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. $ |
Copyright © 2000−2023 MathForum.Ru & MMOnline.Ru Разработка, поддержка и дизайн — MMForce.Net |