Чем отличается алгоритм расширенного кода Хемминга от обычного?
Я закодировала сообщение, у меня получилась такая последовательность:01110010101 Сейчас четность единиц всех групп, контролируемые проверочными разрядами равно 0. допустим мы сделали 2 ошибки, и что нужно сделать дальше, чтобы их обнаружить.

задан 6 Июн '14 21:12

изменен 7 Июн '14 0:59

Deleted's gravatar image


126

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

(6 Июн '14 21:55) falcao

а расширенный код хэмминга одновременно может исправить и обнаружить 2 ошибки?

(6 Июн '14 22:26) Dashka64

Этого описания вполне достаточно -- теперь всё стало понятно. Прежде чем ставить вопрос, нужно указывать параметры кода, потому что без этого информации недостаточно. Я так понимаю, Вы составили обычный код Хэмминга с исправлением одной ошибки для исходного 7-битного сообщения, и получился 10-битный код. К нему добавили 11-й бит, равный сумме всех имеющихся, и получился расширенный код. Он пригоден для обнаружения случая двух ошибок, но исправить их в этом случае нельзя. Из соображений количества информации, для самоисправляющегося кода с двумя ошибками нужно не меньше 5 вспомогательных бит.

(6 Июн '14 23:17) falcao

Можете обьяснить, почему код хэмминга исправляет 1 ошибку. На какие теоремы можно сослаться чтобы это обьяснить?

(7 Июн '14 16:07) Dashka64

Так это основное свойство кода Хэмминга, и оно доказывается в учебниках вместе с его построением. Там основная идея в том, что вводится семейство множеств типа $%M_1=\{1,3,5,..\}$%, $%M_2=\{2,3,6,7,...\}$% и так далее по принципу наличия единицы в двоичной записи, считая с конца. Потом биты с номерами 1, 2, 4, 8, .. заполняются так, чтобы обеспечить паритет чётности по каждому из множеств. Если один бит искажается, то получатель смотрит, по каким из множеств нарушен паритет, и этим однозначно определяет код ошибки. А более подробно это всё описано в учебной литературе.

(7 Июн '14 17:06) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
1

О формулировке задачи и размышлениях @falcao

Если речь идет о двоичном коде Хэмминга, то ни длиной $%10$%, ни длиной $%11$% он быть не может. Для длины $%n$% двоичного кода Хэмминга выполняется равенство $%n=2^m-1$%, где $%m$% — количество проверочных символов, произвольное целое число больше 1.

По вопросам

Можете обьяснить, почему код хэмминга исправляет 1 ошибку. На какие теоремы можно сослаться чтобы это обьяснить?

Код Хэмминга по определению является совершенным линейным кодом с кодовым расстоянием 3, то есть такой код по определению исправляет одну ошибку, а обнаруживает две.

а расширенный код хэмминга одновременно может исправить и обнаружить 2 ошибки?

Расширенный код Хэмминга имеет кодовое расстояние 4, и, следовательно, гарантированно исправляет по-прежнему одну ошибку, а обнаруживает гарантированно не более трех. Вообще говоря, произвольный код с кодовым расстоянием $%d$% гарантированно исправляет не более $%\lfloor\frac{d-1}{2}\rfloor$% ошибок, а обнаруживает гарантированно не более $%d-1$%.

допустим мы сделали 2 ошибки, и что нужно сделать дальше, чтобы их обнаружить?

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

Обнаружение ошибок — это установление факта наличия какого-то количества ошибок в полученном из канала связи слове. Факт наличия ошибок устанавливается очень просто: если полученное слово не является кодовым, то ошибки были.

Исправление же ошибок для кода Хэмминга и расширенного кода Хэмминга осуществляется посредством проверочной матрицы, например, с помощью метода синдромов.

ссылка

отвечен 12 Июл 3:08

изменен 16 Июл 2:08

2

@PerfectCode: всё зависит от постановки задачи. Изначально нам может быть дана константа L, про которую из опыта известно, что при передаче L бит возможно не более одной ошибки. При этом L может быть равна 10 или 11. Тогда нам потребуется 4 вспомогательных бит, и хотя при таком количестве имеются 15-битные коды Хэмминга, но пересылать их уже рискованно из-за возможности возникновения более одной ошибки. Поэтому здесь имеет смысл рассматривать более общую ситуацию.

(13 Июл 18:20) falcao
1

@PerfectCode, здесь Вы предложением с "Вообще говоря...", по сути дела утверждаете, что код не исправляет других ошибок. Т. е. из Вашего ответа можно усмотреть, что код Хемминга (да и любой другой двоичный) с проверкой на четность гарантированно не обнаружит любое нечетное число ошибок, что, очевидно, неверно. Понятия "исправляет", "обнаруживает" целесообразно увязывать с режимом декодирования, который может быть организован при условии $%2t+s+1\le d$%, где $% s$% - кратность гарантированно обнаруживаемых (дополнительно к $%t$% исправляемым) кодом ошибок.

(15 Июл 20:37) Urt

@Urt, извините, я не понимаю что это значит:

код не исправляет других ошибок

Вы верно подметили, что после слов "Вообще говоря" следует также использовать слова "гарантированно" и "для произвольного кода". Исправляюсь!

(16 Июл 1:57) PerfectCode

@Urt, а вот рассматривать для расширенного двоичного кода возможности обнаружения любого нечетного количества ошибок не имеет смысла, поскольку в таком канале связи, где возможны столь многократные ошибки с большей вероятностью произойдет меньшее количество ошибок, обнаружить которые код уже не позволит. То есть правильным будет писать: "исправляет (обнаруживает) гарантированно не более некоторого количества ошибок".

(16 Июл 2:16) PerfectCode

@PerfectCode, в первом случае у меня должно быть "гарантировано не обнаруживает" (погрешность, которую заметил, но исправлять было поздно). Во втором случае я отметил, что любой двоичный код (в том числе, нелинейный) с проверкой на четность может гарантировано обнаруживать все ошибки нечетной кратности, а из Вашего текста следует, что он обнаруживает лишь d-1 ошибку. Желательно более строго использовать терминологию и не отождествлять параметры кода с режимом его использования. В других ответах и комментариях у Вас аналогично (как у Гоголя: "да так, брат,...так как-то всё" (Пушкин) :).

(16 Июл 2:38) Urt

@PerfectCode, у Вас: "для расширенного двоичного кода возможности обнаружения любого нечетного количества ошибок не имеет смысла, поскольку..." - добавить уже нечего (типа сдаюсь).

(16 Июл 2:49) Urt

@falcao, Ваш комментарий мне не понятен. В математике в мирное время принято различать слова "нам может быть дана" и "нам дана". А так я с Вами почти согласен: из чего угодно может следовать что угодно. Вы пишите о необходимости рассматривать некую общую ситуацию, тогда обратите, пожалуйста, внимание на описанную мной в ответе процедуру обнаружения ошибок — что может быть более общим?

(16 Июл 15:56) PerfectCode

@PerfectCode: фраза "нам может быть дана" означает то, что возможно такое изложение теории. Однако обязательности здесь нет, поскольку для простоты можно рассматривать (2^m-1)-битовые кодовые сообщения с числом m вспомогательных бит. Лично мне больше нравится первый вариант как чуть более общий.

(16 Июл 16:04) falcao

@falcao, я согласен с Вами, такой общий взгляд более целостный, что ли. Однако, в таком случае формулировка задачи должна содержать параметры или описание канала связи.

(16 Июл 18:30) PerfectCode

@PerfectCode: это довольно типичное явление, когда задачи формулируются не полностью. Ведь как обычно бывает: читается некий теоретический материал, а нём сообщается разная информация. Типа, например, той, на какие места требуется записывать вспомогательные биты. А формулировки даются без учёта этого, то есть "урезанные". То же касается почти любых задач, где речь идёт об алгоритмах. Контекст очень мало кто при этом приводит. Постоянно приходится уточнять, просить ссылки и т.п.

(16 Июл 23:23) falcao
показано 5 из 10 показать еще 5
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×40

задан
6 Июн '14 21:12

показан
2312 раз

обновлен
16 Июл 23:23

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

по почте:

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

по RSS:

Ответы

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

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