Пусть 11010011 и 11001111-искаженные слова расширенного кода Хемминга длины 8.Какое из этих слов содержит одиночную,а какое-двойную ошибку?В случае одиночной ошибки определить ее положение.

Верно ли мое решение?Если что не так,просьба поправить меня)
Обозначения :$%a_1$%,$%a_2$%...-разряды кода
$%S_1$%={$%а_4$%+$%а_5$%+$%а_6$%+$%а_7$%=0}
$%S_2$%={$%а_2$%+$%а_3$%+$%а_6$%+$%а_7$%=0}
$%S_3$%={$%а_1$%+$%а_3$%+$%а_5$%+$%а_7$%=0}
$%S_0$%={$%а_0$%+$%а_1$%+$%а_2$%+$%а_3$%+$%а_4$%+$%а_5$%+$%а_6$%+$%а_7$%=0}
1) 11010011 суммы разрядов кода $%S_1$%=0 и $%S_2$%=0 и $%S_3$%=0,а $%S_0$%=1 то этот код содержит двойную ошибку. 2)11001111 суммы разрядов кода $%S_1$%=1 и $%S_2$%=1 и $%S_3$%=1, а $%S_0$%=0 то это код содержит одиночную ошибку. Позиция этой ошибки будет $%S_1$%$%S_2$%$%S_3$%, т.е $%111_2$% = 7. Начальное слово без ошибки-11001101

задан 6 Окт '13 16:43

изменен 6 Окт '13 16:46

@Viktoria111, ваше заключение ошибочно. Это видно из того, что проверка на четность всех разрядов (S0) равна нулю только для конфигураций ошибок четной кратности (в вашем случае для двойной ошибки) и равна 1 для ошибок нечетной кратности (в вашем случае однократной ошибки). Чтобы найти позицию ошибки (кроме того, лучше понять структуру кода и потренироваться) перепишите все кодовые слова (их 16) и найдите ближайшее слово к первому из проверяемых. Найти конфигурацию ошибки можно по ее синдрому. В вашем случае вес синдрома = 1, след-но, ошибка в соответствующей проверочной позиции.

(6 Окт '13 19:35) Urt
10|600 символов нужно символов осталось
0

Здесь всё немножко "хитрее". Прежде всего, будем исходить из того, что сначала строится обычный код Хэмминга для обнаружения и исправления одной ошибки как слово длины 7, и затем добавляется 8-й контрольный бит, чтобы обеспечить паритет чётности.

В первом примере ошибка точно есть, так как паритет чётности не соблюдён. Возможны два логических варианта: в последнем бите ошибка либо есть, либо её там нет. Допустим, что ошибка есть, и тогда на последнем месте должен был стоять 0. Тогда, поскольку всего ошибок может быть не более двух, то в первых семи разрядах допущено не более одной ошибки. С учётом того, что первые три суммы равны нулю, оказывается, что ошибки там нет, то есть могло быть передано слово 11010010 с одной ошибкой в последнем бите.

Теперь надо рассмотреть второй случай, когда ошибки в последнем бите нет. Это значит, что на первые 7 бит приходится одна или две ошибки. Случай, когда ошибка ровно одна, отметается по уже указанной причине. Могло ли быть ровно две ошибки? Если да, то паритет чётности остался бы прежним. Но тогда 8-й бит должен быть равен нулю.

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

Во втором примере хотя бы одна ошибка также есть. Допустим, что она ровно одна. Тогда она не может быть в 8-м бите из-за паритета чётности. Если она в первых семи разрядах, то анализ при помощи сумм приводит к указанному Вами случаю ошибки в 7-м бите. Но тогда, если мы её исправим, то паритет чётности нарушится! То есть то слово, которое Вы указали, передано быть не могло. Значит, здесь ошибок имеется по крайней мере две.

Интересно исследовать эту ситуацию до конца. Какие тут могли быть варианты? Если ошибка есть в 8-м бите, то всё ясно: есть ещё одна ошибка в 7-м бите, и было передано сообщение 11001100. Единственный ли это вариант? Если нет, то надо рассмотреть случай, когда в последнем бите ошибки нет. Тогда две ошибки есть среди семи разрядов. И здесь видно, что могли быть другие случаи. Например, слово могло состоять из одних единиц, а ошибки при передаче были допущены в 3-м и 4-м бите. Поэтому во втором примере ничего декодировать не удаётся.

ссылка

отвечен 6 Окт '13 21:01

@Falcao, в задаче не требуется найти позицию ошибки во втором примере, по S0=0 однозначно устанавливается факт четного числа ошибок (конфигурация не единственная - это очевидно). В первом случае по S0=1 однозначно устанавливается факт нечетного числа ошибок в принятой комбинации. С учетом условия Nош. =1 - такая конфигурация единственная. Если говорить о единственности без условия Nош=1, то безусловно нет, найдутся конфигурации ошибки кратности 3, 5 и т.д., но при условии одной ошибки вариант безусловно единственный. Аз есмь.

(6 Окт '13 21:46) Urt

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

(6 Окт '13 22:06) falcao

@Falcao, одна "тонкость" которую я не отметил, это то, что элемент a0 может быть принят за проверочный. При этом, если вес синдрома не превышает t (макс. кратность исправляемых ошибок), то все ошибки (при стандартном декодировании) полагаются в тех проверочных разрядах с номерами i, для которых Si=1

(6 Окт '13 22:23) Urt

@Urt: к сожалению, я пока не уловил Вашу мысль. Что означает первая фраза о рассмотрении последнего бита как проверочного элемента?

(6 Окт '13 22:34) falcao

@Falcao, дело в том, что в совокупности проверочных уравнений проверочные элементы в явном виде не выделены, но по "счастливой случайности" элемент a0 участвует только в одной проверке (он принимается за проверочный) и именно в этой позиции произошла ошибка. Этот же код можно было представить более завуалированной матрицей проверок, для которой информационную совокупность (и соответственно проверочные элементы) нужно было поискать. Могло случиться, что ошибка попала бы в информационную совокупность и простое декодирование (инвертировать проверочную позицию) для данной ошибки было невозможно.

(6 Окт '13 23:00) Urt
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×30

задан
6 Окт '13 16:43

показан
2486 раз

обновлен
6 Окт '13 23:00

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

по почте:

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

по RSS:

Ответы

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

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