Света и Костя обсуждают новую образовательную программу в переписке. Формулировки важны, а интернет иногда «шалит»: при передаче сообщения один бит может исказиться. Чтобы восстанавливать смысл, они решили кодировать каждый фрагмент сообщения кодом Хэмминга (7,4), который умеет исправлять ровно одну ошибку.
Каждый фрагмент состоит из 4 информационных битов d1 d2 d3 d4. Они кодируются в 7-битное слово, где позиции нумеруются слева направо от 1 до 7:
- позиции 1, 2, 4 — проверочные биты
p1, p2, p4;
- позиции 3, 5, 6, 7 — данные
d1, d2, d3, d4.
То есть буква имеет вид (индексация с 1):
| Позиция | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|
| Бит | p1 | p2 | d1 | p4 | d2 | d3 | d4 |
|---|
Проверка. Для проверки сначала вычисляются s1, s2, s4 с помощью XOR (Исключающее ИЛИ, обозначается как ⊕):
- s1 = p1 ⊕ d1 ⊕ d2 ⊕ d4 (позиции 1, 3, 5, 7)
- s2 = p2 ⊕ d1 ⊕ d3 ⊕ d4 (позиции 2, 3, 6, 7)
- s4 = p4 ⊕ d2 ⊕ d3 ⊕ d4 (позиции 4, 5, 6, 7)
Далее рассчитывается синдром ошибки S: S = s1·1 + s2·2 + s4·4.
- если S = 0, ошибки нет;
- иначе ошибочен бит в позиции S (его нужно инвертировать: 0→1 или 1→0).
Гарантируется, что в каждом принятом фрагменте либо нет ошибок, либо ровно одна ошибка на фрагмент.
Вам дано закодированное слово (состоит из нескольких фрагментов):
1010101 0111110 1100000 0011001 0110101
В ответ запишите пару чисел «номер фрагмента с ошибкой» и «номер бита с ошибкой в этом фрагменте» (без пробела между этими двумя числами); если таких пар несколько, то запишите эти пары через пробел в том же порядке, в котором фрагменты даны в условии (индексация с 1 как для бита, так и для номера фрагмента).
Пример записи ответа: 11 27
Примечание. Таблица истинности для XOR (Исключающего ИЛИ):
| a | b | a XOR b |
|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |