Сообщение через шум
Передатчик посылает сообщение из битов через канал, который иногда переворачивает бит. Чтобы ошибки можно было исправить, сообщение кодируют свёрточным кодом. В кодере регистр из K битов, сначала нулевой. Очередной бит сообщения вдвигается в регистр старшим битом, младший выпадает, и в канал уходят два бита: чётности битов регистра, отмеченных единицами в двоичной записи образующих g1 и g2. Например, образующая 171 = 11110012 при K = 7 берёт новый бит и биты, вдвинутые на 1, 2, 3 и 6 шагов раньше. После сообщения в регистр вдвигают ещё K − 1 нулей, и на каждый из них тоже уходят два бита — так регистр возвращается в ноль.
Пришли 2(n + K − 1) битов, часть из них перевёрнута. Найдите сообщение из n битов, код которого отличается от пришедшего в наименьшем числе мест.
В тестах сообщения — отрывки из «Войны и мира» в UTF-8, а канал переворачивает разную долю битов, от нуля до половины. Код с K = 7 и образующими 171 и 133 (восьмеричные) — тот, что в статье.
Вход
В первой строке — K, g1, g2 и n: 2 ≤ K ≤ 7, образующие записаны восьмеричными числами от 1 до 2K − 1, 1 ≤ n ≤ 104. Во второй — пришедшие биты: строка из 2(n + K − 1) нулей и единиц.
Выход
В первой строке — наименьшее число мест, в которых код сообщения отличается от пришедших битов. Во второй — само сообщение: n нулей и единиц. Если подходящих сообщений несколько, выведите любое.
Примеры
Пример 1
3 7 5 4 111000010111
0 1011
Пример 2
3 7 5 4 101000110111
2 1011
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сообщений 2n — перебрать их нельзя. Но код каждого шага зависит не от всего сообщения, а только от содержимого регистра. Сколько различных состояний у кодера между шагами?
2Подсказка 2
Состояние — последние K − 1 битов сообщения, их 2K−1, не больше 64. Два разных начала сообщения, приводящих в одно состояние, дальше ведут себя одинаково. Какое из них стоит помнить?
3Идея
Пусть Dt(s) — наименьшее число расхождений с пришедшими битами среди начал сообщения длины t, после которых кодер в состоянии s. Из состояния s бит b ведёт в состояние, где b стал старшим битом, а младший бит s выпал, и выдаёт два бита, которые сравниваются с пришедшей парой:
Dt+1(s′) = min по s, b, ведущим в s′, от Dt(s) + расхождения пары.
Расхождения дальше шага t зависят только от состояния и будущих битов, поэтому из двух начал с одним состоянием худшее можно забыть. Это алгоритм Витерби — тот, ради которого его и придумали: на решётке из 2K−1 состояний ищется путь с наименьшей суммой расхождений. На хвостовых шагах разрешён только бит 0, ответ — D в нулевом состоянии в конце.
4Разбор
Для каждого шага и состояния храним, из какого состояния пришли; хватает одного бита — того, что выпал из регистра. Обратный ход от нулевого состояния восстанавливает биты: бит сообщения на шаге — старший бит состояния после шага.
Во втором примере код сообщения 1011 — двенадцать битов, из них перевёрнуты второй и седьмой. Ближайшее сообщение — снова 1011, расстояние 2. На отрывке из романа длиной почти две тысячи битов, коде с K = 7 и 5 % перевёрнутых битов ближайшее сообщение совпадает с отправленным; на отрывке подлиннее при 10 % — расходится с ним примерно в каждом десятом бите. При такой доле ошибок код не справляется, но ближайшее сообщение всё равно определено, и его нужно найти.
4+Решение
5Сложность
O((n + K) · 2K) времени: на каждом шаге из каждого из 2K−1 состояний два перехода. Это миллион с небольшим действий при n = 104 и K = 7. Память на обратный ход — (n + K) · 2K−1 битов. В настоящих декодерах её ограничивают: решение о бите выносят через фиксированное число шагов — обычно несколько K, — когда пути из всех состояний почти наверняка уже сошлись.
6Типичные ошибки
- Бит за битом. Выбирать на каждом шаге бит, чья пара ближе к пришедшей, и не оглядываться — одна перевёрнутая пара уводит на чужую ветку, и ошибки идут дальше. Второй пример ловит это.
- Забыть хвост. Последние 2(K − 1) битов — код нулей, вдвинутых после сообщения; их тоже сравнивают, и путь обязан кончиться в нулевом состоянии.
- Порядок битов регистра. Новый бит — старший; образующую 171 = 1111001 накладывают на регистр как есть. Если вдвигать новый бит снизу, получится зеркальный код — у него те же свойства, но другие биты на выходе.
- Восьмеричная запись. «171» — это 121 в десятичной записи, а не 171.