Добрый день! Помогите мне товарищи специалисты, самой никак не разобраться, кучу всего предначертала но все равно не могу понять как решать подобные задачи. Подскажите ход решения или подкиньте ссылки на ваш взгляд полезный материал по этой теме.
Сама задача:
Из канала связи, качество которого исключает появление более одной ошибки замещения разряда на сообщение, получено сообщение, закодированное стандартным кодом Хемминга:
1 1 0 0 1 1 1 1 1 0 1 1
Определите, имеется ли ошибка в принятом сообщении, какой разряд искажен при передаче; восстановите переданное сообщение, выделите в нем информационную часть, определите, какое десятичное число было закодировано для передачи стандартным двоичным кодом.
AVKor: Конечно, 11+4. А 12-битный - с каким распределением на информационные и контрольные биты? И с какими масками для контрольных битов? Вообще, где описан стандарт на эти коды?
AVKor: А что можно посчитать? Понятно, что можно сделать 4 контрольных бита и 8 информационных (объявив три оставшихся бита нулями). С тем же успехом можно взять 4 информационных бита и 8 контрольных - в любом случае, "совершенного" кода мы не получим, так что это будет уже не код Хэмминга.
А в книжке действительно описан "стандартный" код? Или просто одна из возможных реализаций?
Про какие "оставшиеся биты" говорите? Там нет никаких "оставшихся". Все контрольные биты используются, это минимальное количество для исправления одной ошибки замещения. Считайте сами: 2^k >= n+1=8+1=9. Отсюда k=4; 8+4=12.
Что такое "стандартный" код Хэмминга, я не знаю. Не встречал такого именования ни в одном источнике. Оригинальной работы не читал. Но везде, где видел изложение, все различия сводились только к порядку нумерации битов (справа налево или наоборот).
Вообще, есть целые книжки по кодам, исправляющим ошибки, но так глубоко я их не копал. Можете поискать и заглянуть туда сами, если есть интерес.
AVKor: "Что такое "стандартный" код Хэмминга, я не знаю. Не встречал такого именования ни в одном источнике." - я говорю именно об этом. В вопросе фигурирует "сообщение, закодированное стандартным кодом Хемминга" - я пытаюсь выяснить, что это значит. Даже если предположить, что это код, построенный по алгоритму, описанному в русской и английской Вики - с контрольными битами 1,2,4,8 - то неизвестно, какой бит имеет номер 1 - первый или последний.
Что касается "оставшихся битов" - я смотрел на это определение:
For each integer r ≥ 2 there is a code with block length n = 2^r−1 and message length k = 2^r−r−1. Hence the rate of Hamming codes is R = k/n = 1 − r/(2^r−1), which is the highest possible for codes with minimum distance 3 (i.e., the minimal number of bit changes needed to go from any code word to any other code word is 3) and block length 2^r−1.
И примечание, что это "perfect code".
При r=4 получаем k=11 и длину блока 15 - и только. Никаких 12 бит не будет. В коде 8+4 обязательно окажутся "невозможные" сочетания, которые нельзя получить из правильных внесением одной ошибки.
В вопросе фигурирует "сообщение, закодированное стандартным кодом Хемминга" - я пытаюсь выяснить, что это значит.
Это вопрос к автору задачи. Я не знаю, откуда он это брал и что имеет в виду.
Даже если предположить, что это код, построенный по алгоритму, описанному в русской и английской Вики - с контрольными битами 1,2,4,8 - то неизвестно, какой бит имеет номер 1 - первый или последний.
Ну так я и писал выше, что все различия сводятся только к порядку нумерации битов Да и какая разница - результат будет один и тот же.
При r=4 получаем k=11 и длину блока 15 - и только.
Вы "не стой стороны" считаете. Нужно идти не от числа контрольных бит, а от числа информационных, их 8. Отсюда получаем число контрольных - 4. Всего 12.
В коде 8+4 обязательно окажутся "невозможные" сочетания, которые нельзя получить из правильных внесением одной ошибки.
Нет, не окажутся. Картинку нарисуйте для решения задачи ТС, и всё поймёте.
AVKor: да, в этом примере неправильный бит при обоих порядках окажется одним и тем же. Но вот набор информационных битов будет разным.
А насчёт невозможного сочетания - возьмите такую последовательность:
1 0 0 1 0 0 0 1 0 0 0 0
(контрольные биты - 1,2,4,8, бит 1 - самый левый). В каком бите ошибка?
Сумма информационных битов в маске должна быть равна контрольному, которому эта маска соответствует. Или, что то же самое, сумма контрольного и информационных битов должна быть равна нулю. То есть, b1+b3+b5+b7+b9+b11=0 или b1=b3+b5+b7+b9+b11 (b1 - контрольный). А если у вас b1=b1+b3+b5+b7+b9+b11 (и так же для остальных контрольных битов), то это будет выполняться только когда все информационные биты равны нулю. Вряд ли от такого кода будет много пользы.
AVKor: Проблема - как исправить одну ошибку, чтобы все четыре контрольные суммы стали нулевыми? Ведь вы утверждаете, что невозможных пакетов нет. И в "совершенных кодах", к которым относится код Хэмминга, их действительно не должно быть.
Ого... прямо научный спор у вас тут разгорелся ) Вообщем всем спасибо, более менее разобралась. Единственное, буду очень благодарна, если посоветуйте каким образом удобнее производить вычисления на бумаге? Ато у меня ощущение что я как-то примитивно это делаю. Да и ошибок многовато.
Открываете методику или справочник на разделе, где описан стандартный код Хемминга, и пробуете декодировать свое сообщение этим кодом. По результатам декодирования решаете остальные задачи.
Я примерно так и пыталась, кодировать сообщение и разбирать древо с горем пополам поняла как, а вот определять какой разряд искажен при передаче научится не могу и даже принципа этого действия не понимаю( Объясните как это сделать, если это, конечно не отнимет у вас много времени)
Татьяна Свитлицкая: Для начала надо понять, сколько в сообщении контрольных битов, какие они, и за какие информационные биты отвечает каждый из них. После этого должно быть просто.
Средний
Простой
Средний
