Для передачи данных используются слова длины $%13$% в алфавите $%\{0, 1\}$%. Какое максимальное число кодовых слов может содержать код, позволяющий исправлять $%5$% ошибок?

Я рассуждаю так: пусть $%d$% - расстоянием Хемминга между двумя кодовыми словами. Код исправляет $%\frac{d-1}{2}$% ошибок, значит отсюда $%d=11$%, т.е. нужно найти все слова длины $%13$%, расстояние между которыми $%= 11$%. Количество слов = $%C^{11}_{13} \cdot 2^2$%. Правильно ли я рассуждаю?

задан 17 Мар '17 22:56

10|600 символов нужно символов осталось
0

Начало верное, а дальше задача неправильно поставлена чисто словесно. Нужно найти максимально возможное число слов длины 13, которые расположены далеко друг от друга, то есть попарные расстояния между словами не меньше 11. Это значит, что у двух разных кодовых слов могут совпадать максимум две позиции.

Одно кодовое слово без ограничения общности можно считать нулевым. Тогда любое другое к.с. содержит как минимум 11 единиц. Два таких слова будут иметь общую единицу не менее чем в 9 позициях. Такого быть не должно, поэтому кроме нулевого может быть только одно к.с. Такой пример есть: вектор из одних единиц.

Поэтому тут всего два кодовых слова получается.

ссылка

отвечен 17 Мар '17 23:27

Не до конца понятно, что же все таки требуется найти в задании. И немного не понятно на счет нулевого вектора и вектора из всех единиц. Расстояние между ними будет 13, тогда по формуле код будет исправлять 6 ошибок.

(17 Мар '17 23:42) PaCman

@PaCman: вопрос задания сформулирован понятно, и Вы дали описание. Сколько можно предъявить слов длины 13, попарные расстояния между которыми не меньше 11? Я показал, что два слова можно предъявить, а три уже нельзя. То, что построенный код будет исправлять 6 ошибок, верно. Но при этом он автоматически будет исправлять 5, то есть удовлетворяет условию.

Нужно иметь в виду, что слова здесь не слишком длинные, а 5 ошибок -- это много. Поэтому код получается совсем примитивный.

(18 Мар '17 0:33) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×40

задан
17 Мар '17 22:56

показан
423 раза

обновлен
18 Мар '17 0:33

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru