CS70Disc 05A

Berlekamp-Welch 纠错编码

背景知识： Berlekamp-Welch 算法是一种用于纠正数据传输中错误的编码技术，尤其适用于多项式编码。该算法能够通过对收到的数据进行分析，恢复出原始的消息。

题目描述：

设 $ P(i) $ 为在输入 $ i $ 上应用的多项式，表示在发送之前的原始编码多项式，$ r_i $ 为接收到的与输入 $ i $ 相关的信息，可能会受到干扰。

(a) 发送长度为 n 的消息，P(x) 的次数应是多少？

答案： $ P $ 的次数应为 $ n - 1 $，因为 $ n $ 个点可以确定一个次数为 $ n - 1 $ 的多项式。

(b) $ r_i = P(i) $ 什么时候成立？什么时候不成立？

答案：
- $ r_i = P(i) $ 当接收到的包是正确的。
- $ r_i P(i) $ 当接收到的包受到干扰时。

(c) 当最多有 k 个擦除错误时，我们应该发送多少个数据包？当最多有 k 个一般错误时，又应该发送多少个数据包？

答案：
- 对于最多有 k 个擦除错误，我们发送 $ n + k $ 个数据包。
- 对于最多有 k 个一般错误，我们发送 $ n + 2k $ 个数据包。

(d) 错误多项式 $ E(x) $ 的根代表什么？接收方知道 $ E(x) $ 的根吗？如果最多有 k 个错误，$ E(x) $ 的最大次数是多少？根据 $ P(x) $ 和 $ E(x) $ 的次数，$ Q(x) = P(x)E(x) $ 的次数是多少？

答案：
- $ E(x) $ 的根代表损坏包的位置。
- 接收方不知道 $ E(x) $ 的根。
- 如果最多有 k 个错误，$ E(x) $ 的最大次数为 $ k $。
- $ Q(x) $ 的最大次数为 $ (n - 1) + k = n + k - 1 $（因为 $ P $ 的次数为 $ n - 1 $，而 $ E $ 的最大次数为 $ k $）。

(e) 为什么方程 $ Q(i) = P(i)E(i) = r_iE(i) $ 总是成立？（考虑 $ P(i) = r_i $ 和 $ P(i) r_i $ 的情况）

答案：
- 如果在点 $ i $ 没有错误，则 $ P(i) = r_i $，因此有：$ Q(i) = P(i)E(i) = r_iE(i) $
- 如果在点 $ i $ 存在错误，则 $ E(i) = 0 $，因此有：$ Q(i) = P(i)E(i) = r_iE(i) = 0 $

(f) 在多项式 $ Q(x) $ 和 $ E(x) $ 中，总共有多少个未知系数？（这些是你必须求解的变量。）当你接收到数据包时，你有多少个方程？是否有足够的方程来求解所有未知数？

答案：
- $ Q(x) $ 的最大次数为 $ n + k - 1 $，所以未知数为 $ n + k $。
- $ E(x) $ 的最大次数为 $ k $，这意味着有 $ k + 1 $ 个未知数。
- 由于我们知道 $ E(x) $ 中 $ x^k $ 的系数为 1，因此未知数的数量为 $ k $。
- 总的未知数为 $ (n + k) + k = n + 2k $。
- 收到 $ n + 2k $ 个方程，这是足够求解所有未知数的。

(g) 如果你有 $ Q(x) $ 和 $ E(x) $，如何恢复 $ P(x) $？如果你知道 $ P(x) $，又如何恢复原始消息？

答案：
- 可以通过以下方程计算 $ P(x) $：$ P(x) = $
- 为了恢复消息，我们计算： $ P(i) i n $

Berlekamp-Welch 算法与较少的错误

问题背景

Alice 希望向 Bob 发送消息，并利用 Berlekamp-Welch 算法来防止潜在的错误。她将消息编码为多项式 $ P(x) $ 在 $ (7) $ 中，并发送该多项式的三个评估值。

问题详情

消息: 发送的消息由多项式 $ P(x) = 4 $ 表示，使得 $ P(0) = 4 $。
发送的消息: Alice 发送点 $ (P(0), P(1), P(2)) = (4, 4, 4) $。
接收到的消息: Bob 收到的消息是 $ (4, 5, 4) $。

解决方案

(a) 寻找 $ E(x) $ 和 $ Q(x) $

错误定位多项式:
- Bob 注意到第二个值发生了错误，即 $ r_1 = 5 $ 而不是 $ P(1) = 4 $。因此，我们设 $ E(x) = x - 1 $，这表示在 $ x = 1 $ 处发生了错误。
**计算 $ Q(x) $**: - 通过定义，$ Q(x) = P(x) E(x) $。 - 因此，$ Q(x) = 4(x - 1) = 4x - 4 $。

总结：

所以，错误定位多项式 $ E(x) = x - 1 $ 和 $ Q(x) = 4x - 4 $。

(b) 验证 $ Q(x) $ 和 $ E(x) $

如果 Bob 收到的消息是原始消息 $ (4, 4, 4) $，我们需要验证在这种情况下 $ Q(x) $ 和 $ E(x) $ 是否仍然满足 $ Q(i) = r_i E(i) $ 对于所有 $ i = 0, 1, 2 $。

对于 $ i = 0 $:$ Q(0) = 4(0) - 4 = -4 ( 7), E(0) = 0 - 1 = -1 ( 7) $ $ r_0 E(0) = 4 = 24 ( 7) $
对于 $ i = 1 $:$ Q(1) = 4(1) - 4 = 0, E(1) = 1 - 1 = 0 $ $ r_1 E(1) = 4 = 0 $
对于 $ i = 2 $:$ Q(2) = 4(2) - 4 = 4, E(2) = 2 - 1 = 1 $ $ r_2 E(2) = 4 = 4 $

因此，$ Q(i) = r_i E(i) $ 对于所有 $ i = 0, 1, 2 $ 都成立。

(c) 另一组解的验证

我们还可以验证 $ E(x) = x $ 和 $ Q(x) = 4x $ 是否满足 $ Q(i) = r_i E(i) $ 对于所有 $ i = 0, 1, 2 $。

对于 $ i = 0 $:$ Q(0) = 4 = 0, E(0) = 0 $ $ r_0 E(0) = 4 = 0 $
对于 $ i = 1 $:$ Q(1) = 4 = 4, E(1) = 1 $ $ r_1 E(1) = 4 = 4 $
对于 $ i = 2 $:$ Q(2) = 4 = 8 ( 7), E(2) = 2 $ $ r_2 E(2) = 4 = 8 ( 7) $

所以，$ E(x) = x $ 和 $ Q(x) = 4x $ 也是一个满足条件的解。

(d) 行简化时的结果

当我们尝试解码接收到的消息 $ (4, 4, 4) $ 时，根据前面的讨论，我们有多组可能的解。由于我们有多个解，行简化过程中会出现多个解决方案，这意味着我们可能无法确定唯一的 $ Q(x) $ 和 $ E(x) $。

(e) 证明恢复的 $ P(x) $ 始终相同

假设我们得到了两组解 $ Q'(x), E'(x) $ 和 $ Q(x), E(x) $。由于它们都是解，因此根据定义我们有：$ Q'(i) = r_i E'(i) Q(i) = r_i E(i) 1 i n + 2k $ 这意味着： $ Q'(i) E(i) = Q(i) E'(i) = r_i E(i) E'(i) $ 由于 $ Q'(x)E(x) - Q(x)E'(x) $ 是一个最高度为 $ n + 2k - 1 $ 的多项式，并且在 $ n + 2k $ 个点上都为零，所以有： $ Q'(x) E(x) = Q(x) E'(x) x $ 这证明了最终恢复的 $ P(x) $ 始终相同。