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

задан 22 Фев '17 16:40

Постановка задачи непонятна. Не указано, какое число информационных бит мы хотим переслать. Ясно, что если все 9 бит информационные, то нельзя исправить ни одной ошибки. Обычно вводят два параметра типа k, m, где k+m равно длине кода, k бит считаются информационными (то есть они любые), а остальные m бит вспомогательные (это функции от k бит). В зависимости от значений параметров, можно построить коды с исправлением какого-то числа ошибок, которое зависит от k и m.

(22 Фев '17 19:20) falcao
10|600 символов нужно символов осталось
1

Данная постановка задачи, действительно, не без изъяна. Но и в текущей постановке может быть предложено решение.

Рассмотрим двоичный код длины $%9$%, состоящий только из одного кодового слова. Такой код обладает чудесным свойством исправления $%9$%-и ошибок, однако обладает "небольшим" недостатком — не передает информации. Таким образом, если закрыть глаза на указанный недостаток, то максимальное количество исправляемых ошибок равно $%9$%.

ссылка

отвечен 11 Июл 23:42

@PerfectCode, Вы ранее писали "Вообще говоря, код с кодовым расстоянием $%d$% исправляет $%\lfloor\frac{d-1}{2}\rfloor $%⌋ ошибок, а обнаруживает $%d−1$%". С учетом этого у обучающегося может возникнуть вопрос, откуда появился такой код, для чего он нужен и по каким формулам все-таки рассчитывать его "чудесные" исправляющие свойства.

(15 Июл 19:39) Urt

К данной задаче мной был приведен пример тривиального кода, состоящего из одного кодового слова. Такой код не имеет практического смысла по указанной ранее причине — он не передает информации. Действительно, количество исправляемых кодом ошибок зависит от его кодового расстояния, которое определяется как минимальное расстояние Хэмминга между парой различных кодовых слов. Получается, что для приведенного тривиального кода кодовое расстояние не определено. Тогда остается рассмотреть механику исправления ошибок, которая до крайности примитивная.

(16 Июл 0:40) PerfectCode

Исправление ошибок подчиняется принципу максимального правдоподобия, который заключается в том, что наименьшее количество ошибок наиболее вероятно. Этот принцип является следствием предположения о том, что вероятность искажения символа в канале связи с шумами менее $%1/2$%. Иначе приведенный принцип можно сформулировать так: декодирование следует осуществлять в ближайшее кодовое слово.

(16 Июл 0:40) PerfectCode

Теперь механику исправления ошибок можно представить следующим образом: строятся непересекающиеся шары максимального радиуса с центрами в кодовых словах, для кода с кодовым расстоянием $%d$% такие шары будут иметь радиус $%\lfloor\frac{d-1}{2}\rfloor$%. Далее если полученный из канала связи вектор с ошибками попадает в некоторый шар указанного радиуса с центром в кодовом слове, то полагается, что отправлено было именно такое кодовое слово, то есть ошибки исправляются до получения кодового слова из центра соответствующего шара.

(16 Июл 0:41) PerfectCode

Наконец, обращаемся к коду из одного кодового слова, приведенному в решении к данной задаче. Шар с центром в кодовом слове будет только один и его радиус можно взять максимально возможным, то есть $%9$%. Таким образом, в этот шар попадет все двоичное $%9$%-и мерное пространство и какой бы вектор мы не получили, следует считать, что отправлено было то единственное кодовое слово из центра нашего шара.

Строго говоря, предложенное решение из серии абсурдных, и возможно оно только вследствие некорректной постановки задачи.

(16 Июл 0:41) PerfectCode
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×40

задан
22 Фев '17 16:40

показан
447 раз

обновлен
16 Июл 0:42

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

по почте:

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

по RSS:

Ответы

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

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