통신 채널

고전 정보 이론은 통신 채널이라는 개념을 바탕으로 한다. 클로드 섀넌이 1948년 논문 "A Mathematical Theory of Communication"에서 세운 이 이론의 중심 문제는 잡음이 있는 채널로 정보를 보내는 공학 문제다.

이 문제에서는 가장 단순한 잡음 채널인 이진 대칭 채널(BSC)만 다룬다. BSC는 비트열을 전송하는데, 전송되는 각 비트는 확률 $p$로 반대 비트로 뒤집힌다. 이 $p$를 교차 확률이라고 한다. 비트마다 뒤집히는 사건은 서로 독립이므로, 길이가 $l$인 통신이 정확히 전달될 확률은 $(1-p)^l$이다. $p = 1/2$인 채널은 아무 쓸모가 없고 $p > 1/2$인 채널은 출력의 모든 비트를 뒤집어 교차 확률이 $1-p$인 채널로 바꿀 수 있으므로, 항상 $p < 1/2$라고 가정해도 된다.

잡음이 있는 채널로도 통신은 가능하다. 지금 이 순간에도 하고 있다. 그러려면 수신 측이 오류를 검출하거나 정정하도록 여분의 비트를 덧붙여야 한다. 패리티 비트, 순환 중복 검사(CRC), 골레이 부호가 그런 장치다. 이 문제에서는 그런 부호를 다루지 않는다.

이진 대칭 채널을 지나간 전송 기록이 주어진다. 각 전송이 제대로 전달되었는지 판정하라.

첫 줄에 전송 횟수 $T$가 주어진다. 다음 $T$개의 줄에는 전송 하나의 입력과 출력이 공백 하나로 구분된 이진 문자열 두 개로 주어진다.

• $0 < T \le 100$
• 모든 입력과 출력의 길이는 $120$보다 작다.
• 한 전송의 입력과 출력은 길이가 같다. 채널은 비트를 뒤집기만 하고 비트를 넣거나 빼지 않는다.
• $T$는 십진수로 주어진다.

각 전송마다 한 줄씩, 통신이 정확히 전달되었으면 OK를, 잘못 전달되었으면 ERROR를 출력한다.