Червяку нужно отправить Письмо Мира птицам, которое состоит из 4 бит данных. Червячиная передача и связь очень ненадежны и любой бит информации (лишь один) может испортиться. Зато размер посылаемого пакета равен 7ми битам.
Как лучше Червяку следует послать данные в пакете, чтобы птицы, зная алгоритм, гарантированно смогли прочитать данные. Хотя возможно один бит (любой) будет поврежден.
3 ноября 2009 в 23:01
Код Хэмиминга, кажися, для этого есть
2 ноября 2009 в 0:03
Да, решение необычное, но, по-моему, верное =) Супер!
2 ноября 2009 в 0:01
муторно как-то но можно сделать так(надо книжку почитать конечно, слишком криво)
вобщем идея такая (плюсы все по модулю два)
п1=д1+д2
п2=д2+д3
п3=д3+д4
п4=д4+д1
лемма п1+п2+п3+п4=0 (почти очевидно это xor числа со своим циклическим сдвигом)
так что если ошибка в первой четвёрке, факт ошибки там или её отсутствия в этой части пакета мы установим сразу
прообраз данных восстанавливается имея, один первый бит данных
п5=д1;
п6=п1+п2+п5
п7=п1+п3+п5
пусть в первой четвёрке
- чётное число единичных битов (ошибки нет)
т.е. п1 п2 п3 п4 – известны достоверно
— тогда из условия для п6 восстонавливаем п5
— из условия для п7 восстанавливаем п5
— берём сам п5, по два из трёх однозначно получаем п5
—– можно писать ответ
в первой четвёрке нечётное число единичных битов- ошибка именно здесь
- достоверно известны п5 п6 п7
— в уравнения п6 и п7 подставляем данныи и получаем 4 варианта
—– либо и п6 т п7 верны, тогда ошибка в п4 его инвертируем и пишем ответ
—– п6 верен п7 нет – ошибка в п3 инвертируем восстанавливаем ответ
—– п6 неверен п7 верно – ошибка в п2
—– оба условия для п6 и п7 не выполняются ошибка в п1.
31 октября 2009 в 1:01
Надо удалять правильные ответы, чтобы новым было интереснее =)
30 октября 2009 в 22:05
"Пацаны, я вас ненавижу" ©
=)
30 октября 2009 в 19:02
Правильно
30 октября 2009 в 18:02
А вообще, вникать в ваши решения – штука сложная. Давайте договоримся о таких обозначениях:
П1 П2 П3 П4 П5 П6 П7 – это биты пакета.
Д1 Д2 Д3 Д4 – это биты данных.
Соответственно решение #34 (неверное) выглядит примерно так:
П1 Д1
П2 Сумма П1 и П3 по модулю 2
П3 Д2
П4 Сумма П3 и П5 по модулю 2
П5 Д3
П6 Сумма П5 и П7 по модулю 2
П7 Д4
Имхо так понятнее получается, нет?
30 октября 2009 в 18:02
например, слово: 1011011
ошибка в 6 бите, то есть: 1011001
если в 6, значит неверна сумма 3 и 4 битов исходного сообщения.
так как сумма 2 и 3 верна (поскольку ошибка возможна только в одном бите), значит 3 бит исходного сообщения (7 в слове) верен, значит ошибка в 6 бите
30 октября 2009 в 18:02
Александр, а как правильно? Только не заглядывая в книжку =)
30 октября 2009 в 18:02
всё, понял свою ошибку )))
30 октября 2009 в 18:01
запись в строчку: 1 2 3 4 5 6 7
1, 3, 5, 7 – биты информации
2, 4, 6 – суммы соседних битов по модулю 2.
например, имеем сообщение1001
получаем слово 1100011
допустим, во время передачи испортился 5 бит: 1100111.
тогда выписываем сообщение 1 0 1 1,
считаем суммы по модулю 2 соседних элементов 1 1 0 – они не сходятся с сообщением – определяеи, что ошибка во 2 и 3 сумме, значит ошибочен 3 бит.
30 октября 2009 в 18:01
Если ошибка в 6м бите, то как ты определишь, где ошибка, в 6м или в 7м?
30 октября 2009 в 17:00
Всё, всем спокойной ночи, надеюсь что когда я вернусь решения тут всё ещё не будет
30 октября 2009 в 16:05
Всё хорошо, люди, думаем дальше. Если ошибка в бите 2 или 3, то система не работает
30 октября 2009 в 16:02
ну что, есть у кого-нть идеи?
30 октября 2009 в 16:02
(решение неверно)
Иеееес!!! Если я не гоню, то я её решил! Короче заливаю решение:
Кароче запишем биты в сточку: 1 2 3 4 5 6 7. Первые 4 бита это само слово, а биты 5, 6, 7 – контрольные.
Изменим бит 5 таким образом, чтобы биты 1, 2, 3, 5 вместе содержали чётное колличество еденичек.
Изменим бит 6 таким образом, чтобы биты 2, 3, 4, 6 вместе содержали чётное колличество еденичек.
Изменим бит 7 таким образом, чтобы биты 2, 3, 5, 6, 7 вместе содержали чётное колличество еденичек.
Всё, теперь допустим это было слово 1001. Соответственно изменяем биты 5, 6, 7 и получаем 1001110. Это слово червячок несёт птицам. Допустим по дороге бит 5 изменился, т.е. он принёс число 1001010. Обратим внимание, что биты 1, 2, 3, 5 содержат нечётное колличество еденичек. Значит один из них ошибочен. Но биты 2, 3, 4, 6 правильны, значит это либо 1 либо 5, ну и 2, 3, 5, 6, 7 также содержат ошибку, значит это 5. Ну и это работает для любой комбинации… походу.
ЧТД
30 октября 2009 в 15:03
Чёрт! А раньше сказать не мог?!
30 октября 2009 в 15:03
Борис, а какое третье значение ты представлял у бита?
)))
30 октября 2009 в 15:03
Денис GooDWiN Гублин, но ведь отправитель не знает, какой номер будет ошибочным. Ошибочным, кстати, может быть как раз один из трех битов для суммы.
А вообще – алгоритм в студию.
30 октября 2009 в 15:03
ну… как обычно нолик либо единичка, но только синенький.
30 октября 2009 в 15:03
Ну вот бит и может быть или нулем, или единицей
30 октября 2009 в 15:02
если он испорчен то он обязательно содержит информацию обратную той которую содержал в начале.
30 октября 2009 в 15:02
1) Только 2 значения у бита =)
2) Всегда приходит 7 бит. Но один из битов может быть неправильным.
3) Если бит содержит ту информацию, что он содержал в начале, то он уже по факту этого – не испорчен
30 октября 2009 в 15:01
суммировать номер ошибочного бита, как раз трех битов хватит
30 октября 2009 в 15:01
кажется придумал решение )
30 октября 2009 в 15:01
у бита ведь только два значения?
30 октября 2009 в 15:01
вопрос по условию задачи: если бит испорчен, он содержит информацию или нет?
30 октября 2009 в 14:05
про код хемминга в первую очередь думается, когда дублировать каждый бит не получается)))
зы тоже держусь
30 октября 2009 в 14:04
а как проверить правильность решения кто-нибудь знает?
30 октября 2009 в 14:04
Конечно. Когда ты додумался до решения, это значит, что в случае, если отсутствует любой бит из передаваемых, ты можешь назвать алгоритм, как восстановить этот бит.
Если на какой-то поломанный бит такого алгоритма не существует – решение неправильное.
На все существует – правильное
30 октября 2009 в 14:03
пойду кофе попью. Кому нибудь сделать кофе?
30 октября 2009 в 14:03
Сергей, и ты тут
Честно говоря, я не помню код хемминга) до этого дела можно додуматься самому
30 октября 2009 в 14:03
Конечно можно. Хеминг же додумался как то
30 октября 2009 в 14:02
да, это именно оно. Но глядеть не честно. Я вон уже минут 40 держусь
30 октября 2009 в 14:01
че-та мне подсказывает, что мне надо 1-3 балла решать))
30 октября 2009 в 14:01
вроде код Хеминга нужно использовать.
Шахнов нам это рассказывал. Там как раз на 4 бита полезной информации 3 бита – минимальная контрольная сумма будет для востановления 1 ошибки
точно алгоритм не помню, но глянуть не проблема
угадал? )))
30 октября 2009 в 14:00
Да я вообще в шоке! …Короче если я долго ничего не напишу щитайте, что я пошёл спать
30 октября 2009 в 14:00
Ну она на 4ре балла из 5 по мнению braingames. А задача "от Intel 2", по-моему, на 1 или 2 балла. Т.ч. эта чуть посложнее. Но всё равно решаема. И решение красивое
30 октября 2009 в 13:05
Не сдавайтесь
30 октября 2009 в 13:04
И я чтото туплю. Удалось вспомнить только, что это возможно, а как именно возможно никаких идей
30 октября 2009 в 13:03
хватит. мне работать надо
30 октября 2009 в 13:03
напал тупняк) тоже пойду работать. ща отчет доделаю и подумаю еще
30 октября 2009 в 13:02
Это проходят на курсе по булевской алгебре
Поэтому буду сохранять гордое молчание.
30 октября 2009 в 13:02
Постарался изменить текст задачи так, чтобы он совсем не гуглился =) вроде получилось)