Форум программистов, компьютерный форум, киберфорум
Наши страницы

Дискретная математика

Войти
Регистрация
Восстановить пароль
 
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
#1

Доказать, что кодовые слова веса 4 расширенного совершенного кода образуют систему четверок Штейнера - Дискретная математика

24.04.2017, 16:11. Просмотров 297. Ответов 0
Метки нет (Все метки)

1) Доказать, что совокупность кодовых слов веса 4 расширенного совершенного кода, содержащего нулевой вектор, образуют систему четверок Штейнера.
Решение: я нашла только пример относительно расширенного кода Хэмминга [8,4,4]. Тогда числа Ai получаются такими - A0=A8=1 и A4=14. Два кодовых слова веса 4 имеют расстояние как минимум 4, у них как минимум две 1-цы общие и получается, что ни одно слово веса 3 не может появиться как подслово в более чем одном слове. С другой стороны получается, что всего http://www.cyberforum.ru/cgi-bin/latex.cgi?{C}^{8}_{3}=56 кодовых слов веса 3 и каждое слово веса 4 имеет 4 подслова веса 3. Следовательно, каждое слово веса 3 является подсловом единственного слова веса 4. Поэтому supp 14-ти кодовых слова веса 4 образуют 3-(8,4,1)-дизайн, т.е. SQS(8).
Можно ли как-то его расширить на общий случай, когда у нас множество из {1...N}?
Также я посчитала, что всего http://www.cyberforum.ru/cgi-bin/latex.cgi?|SQS(n)|= \frac{n(n-1)(n-2)}{24} четверок. Но при этом http://www.cyberforum.ru/cgi-bin/latex.cgi?{C}^{n}_{3}=\frac{n(n-1)(n-2)}{6}. Получается, что даже их количество изначально не совпадает.

2) Доказать, что SQS(10) уникальна
Всего должно получиться 30 четверок. Построение данных четверок было таким образом:сначала выписывались все столбцы, строки, диагонали матрицы
http://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix}<br />
1 & 2 & 3\\ <br />
4 & 5 & 6\\ <br />
7 & 8 & 9<br />
\end{pmatrix}
Т.е. получилось
{123 10},{456 10},{789 10},
{147 10},{258 10},{369 10},
{159 10},{357 10},{267 10},
{483 10},{249 10},{168 10}.
Это 12 четверок.
Далее рассматривались все подматрицы размера 2х2. Это дало еще 9 четверок.
И затем еще 9 четверок дали какие-то странные махинации со строками и столбцами, т.е., например, получилась четверка {2,3,5,7}. Собственно весь вопрос уникальности сводился к вопросу "все ли пути выбора подматриц эквивалентны?". И здесь как бы получается, что мы ведь можем вычеркнуть любой столбец из трех и независимо любую строку из трех и получить подматрицу. Отсюда и получается 3х3=9 возможностей. Но это объяснение мне кажется каким-то странно простым (или неправильным).

Добавлено через 10 минут
1) Может нужно опираться на факт, что мы знаем, что слова веса 3 у кода длины n образуют STS(n). Значит, если мы расширим этот код, то это все равно, что добавление нового элемента http://www.cyberforum.ru/cgi-bin/latex.cgi?\infty в каждое подмножество кода нечетной мощности. Но отсюда ведь не будет следовать напрямую, что каждое слово веса 4 (минимального) образует систему четверок Штейнера?

Добавлено через 44 минуты
1) Объяснение было найдено в книге Мак-Вильямс, Слоэн "Теория кодов, исправляющих ошибки"
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.04.2017, 16:11
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Доказать, что кодовые слова веса 4 расширенного совершенного кода образуют систему четверок Штейнера (Дискретная математика):

Доказать что векторы а1,а2,а3,а4 образуют базис четырехмерного пространства - Математика
Помогите пожалуйста! Доказать что векторы а1,а2,а3,а4 образуют базис четырехмерного пространства. Найти координаты вектора b в этом...

Доказать что векторы образуют базис. Найти его размерность - Математика
Здравствуйте. Наведите на мысли по поводу решения данной задачи. Спасибо. :senor: Правила форума :rtfm: Правила, 5.18....

Доказать что векторы образуют базис - Геометрия
Доказать что векторы a,b,c образуют базис и найти координаты вектора d в этом базисе,если a=(5,4,1),b=(-3,5,2),c=(2,-1,3),d=(7,23,4)

Доказать, что векторы образуют базис - Геометрия
Помогите,пожалуйста, решить. Доказать,что векторы a, b, c, образуют базис, и найти координаты вектора d в этом базисе: a = (1,2,3), b =...

Доказать, что векторы a, d, c образуют базис - Алгебра
Доказать,что векторы a,b,c образуют базис,и найти координаты вектора d в этом базисе. a(2,-1,4),b(-3,0,-2),c(4,5,-3),d(0,11,-14)

Доказать, что векторы a, b, c образуют базис, и - Геометрия
Доказать, что векторы a, b, c образуют базис, и разложить вектор d по этому базису.

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.04.2017, 16:11
Привет! Вот еще темы с ответами:

Напишите фрагмент кода для определения кода нажатой клавиши (расширенного кода в том числе) - Turbo Pascal
Напишите фрагмент кода для определения кода нажатой клавиши (расширенного кода в том числе). Найдите коды клавиш Esc, Enter, BackSpace,...

Доказать, что многочлены образуют векторное пространство - Алгебра
Доказать, что все многочлены степени &lt;= n от одного неизвестного с вещественными коэффициентами (или с коэффициентами из любого поля P)...

Доказать, что значения функции образуют геометрическую прогрессию - Математический анализ
Доказать, что если для линейной функции f(x)=a^x (a&gt;0) значения аргумента x=xn, x=1, 2,... образуют арифметическую прогрессию, то...

Доказать, что многочлены образуют базис в пространстве многочленов - Алгебра
Доказать, что многочлены 2t+{t}^{5}, {t}^{3}-{t}^{5}, t+{t}^{3} образуют базис в пространстве нечётных многочленов степени не выше 5, и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.