Коммуникационные каналы
Классическая теория информации основана на понятии коммуникационного канала.
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.
В этой задаче мы досконально рассмотрим один из простейших возможных шумовых каналов, а именно бинарный симметричный канал (БСК). БСК передает последовательность бит, но вероятность искажения каждого переданного бита равна p. Это называется переходной вероятностью, как показано на картинке. Считаем, что разные биты ведут себя независимо, поэтому l бит будет передано правильно с вероятностью (1-p)^l. Мы всегда можем считать что p < 1/2, иначе канал с p = 1/2 является бесполезным, а канал с p > 1/2 может легко быть преобразован в новый канал с переходной вероятностью 1 - p в результате простого переворота выходных бит.
Конечно, передавать информацию по шумовому каналу все еще возможно (фактически Вы это делаете постоянно)! Для этого Вам следует присоединить несколько дополнительных бит к сообщению, с помощью которых получатель сможет обнаружить или даже исправить ошибки. Примером реализации таких свойств являются свойство четности бит, контроль циклическим избыточным кодом (CRC) и коды Голея. Но это не относится к задаче, и поэтому здесь не будет обсуждаться.
Вам необходимо исследовать поведение бинарного симметрического канала.
Входные данные
Первая строка содержит количество передач T (0 < T ≤ 100). Каждая из следующих T строк содержит входные и выходные данные передачи данных по каналу в виде бинарных строк, разделенных пробелом.
Длины входной и выходной строки меньше 120. T представлено в десятичной системе счисления.
Выходные данные
Для каждой передачи вывести OK если она прошла корректно или ERROR если произошла ошибка.