eolymp
bolt
Try our new interface for solving problems
Məsələlər

Коммуникационные каналы

Коммуникационные каналы

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Классическая теория информации основана на понятии коммуникационного канала.

Information theory is generally considered to have been founded in 1948 by Claude Shannon in his seminal work, "A Mathematical Theory of Communication." The central paradigm of classical information theory is the engineering problem of the transmission of information over a noisy channel.

http://en.wikipedia.org/wiki/Information theory

В этой задаче мы досконально рассмотрим один из простейших возможных шумовых каналов, а именно бинарный симметричный канал (БСК). БСК передает последовательность бит, но вероятность искажения каждого переданного бита равна p. Это называется переходной вероятностью, как показано на картинке. Считаем, что разные биты ведут себя независимо, поэтому l бит будет передано правильно с вероятностью (1-p)^l. Мы всегда можем считать что p < 1/2, иначе канал с p = 1/2 является бесполезным, а канал с p > 1/2 может легко быть преобразован в новый канал с переходной вероятностью 1 - p в результате простого переворота выходных бит.

Конечно, передавать информацию по шумовому каналу все еще возможно (фактически Вы это делаете постоянно)! Для этого Вам следует присоединить несколько дополнительных бит к сообщению, с помощью которых получатель сможет обнаружить или даже исправить ошибки. Примером реализации таких свойств являются свойство четности бит, контроль циклическим избыточным кодом (CRC) и коды Голея. Но это не относится к задаче, и поэтому здесь не будет обсуждаться.

Вам необходимо исследовать поведение бинарного симметрического канала.

Giriş verilənləri

Первая строка содержит количество передач T (0 < T100). Каждая из следующих T строк содержит входные и выходные данные передачи данных по каналу в виде бинарных строк, разделенных пробелом.

Длины входной и выходной строки меньше 120. T представлено в десятичной системе счисления.

Çıxış verilənləri

Для каждой передачи вывести OK если она прошла корректно или ERROR если произошла ошибка.

Nümunə

Giriş verilənləri #1
2
10 10
10 11
Çıxış verilənləri #1
OK
ERROR