QOJ.ac

QOJ

حد الوقت: 1 s حد الذاكرة: 512 MB مجموع النقاط: 100

#3348. 通信信道

الإحصائيات

经典信息论基于通信信道的概念。

信息论通常被认为是由 Claude Shannon 在 1948 年的开创性著作《通信的数学理论》中创立的。经典信息论的核心范式是噪声信道下的信息传输工程问题。

在本题中,我们将专门考虑最简单的噪声信道之一,即二进制对称信道(BSC)。BSC 传输比特序列,但每个传输的比特都有概率 $p$ 被翻转为错误的比特。这被称为交叉概率,如图所示。我们假设不同比特的行为是独立的,因此传输 $l$ 个比特时,正确传输的概率为 $(1 - p)^l$。注意,我们可以始终假设 $p < 1/2$,因为 $p = 1/2$ 的信道是完全无用的,而 $p > 1/2$ 的信道可以通过翻转输出的所有比特,轻松转换为交叉概率为 $1 - p$ 的新信道。

当然,在噪声信道上进行通信仍然是可能的。(事实上,你一直在这样做!)为了做到这一点,必须添加额外的比特,以便接收方检测甚至纠正错误。这种特性的示例实现包括奇偶校验位、循环冗余校验(CRC)和 Golay 码。然而,这些与本题无关,因此在此不做讨论。

在本题中,你必须研究二进制对称信道的行为。

输入格式

输入的第一行包含一个整数 $T$,表示传输次数。 接下来有 $T$ 行,每行包含一次传输的输入和输出,均为二进制字符串,中间由一个空格分隔。

输出格式

对于每次传输,如果通信传输正确,输出 OK,否则输出 ERROR

数据范围

  • $0 < T \leq 100$
  • 所有输入和输出的长度均小于 $120$。
  • $T$ 以十进制编码。

样例

输入格式 1

2
10 10
10 11

输出格式 1

OK
ERROR

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.