问题标签 [error-correction]

这种纠错方法的正确名称是什么？它与汉明码非常相似，但要简单得多。我在文献中也找不到了。我现在能找到的唯一描述该方法的互联网资源是：

http://www.mathcs.emory.edu/~cheung/Courses/455/Syllabus/2-physical/errors-Hamming.html

还有德语维基百科。

http://de.wikipedia.org/w/index.php?title=Fehlerkorrekturverfahren

在 Wikipedia 文章中，该方法称为 Hamming-ECC 方法。但我不是 100% 肯定，这是正确的。

这是一个示例，它描述了该方法的工作方式。

第 1 步：确定奇偶校验位位置。位是 2 的幂（1、2、4、8、16 等）是奇偶校验位：

第 2 步：计算奇偶校验位值。传输中的每个位位置都分配有一个位置编号。在此示例中，位置编号是 4 位数字，因为我们有 4 个奇偶校验位。计算这些位置的值的异或（4 位格式），其中有效载荷是传输中的 1 位：

第 3 步：在传输中插入奇偶校验位值：

验证非常简单，如果接收到的消息被正确传输并且可以纠正单位错误。这是一个例子。接收器计算计算的和接收的有效载荷位的异或，其中值为 1 位。如果结果为0，则传输无误。否则结果包含具有错误值的位的位置。

我希望，这里的任何人都知道该方法的正确名称。

谢谢你的帮助。

我正在使用 C 进行单比特纠错双比特错误检测的项目，我得到了实现汉明码 (7, 4) 的答案，但是我在生成缩短的汉明码或扩展的汉明码时遇到了困难。任何人都可以建议如何为不同的输入长度生成缩短的汉明码的逻辑吗？谢谢...

几年前的一些具有里程碑意义的研究现在表明，大型数据集中的无声损坏比以前预期的要广泛得多（今天我猜你会说它比普遍意识到的要多）。

假设应用程序和操作系统编写了一个扇区并且有时间让所有内容刷新，没有崩溃或异常关闭，也没有会命令保存错误数据的软件错误。

稍后，一个扇区被读回，并且没有从 HDD 读取错误。但它包含错误的数据。

由于 HDD 数据编码包含纠错码，我认为任何神秘的状态更改通常都会被检查注意到。即使检查不是很严格，因此会出现一些错误，但仍然会检测到更多的错误，这些错误会告诉您驱动器有问题。但这并没有发生：显然，数据被发现是错误的，没有任何症状。

怎么会这样？

我在台式机上的经验是，有时曾经好的文件后来发现是坏的，但这可能是由于在写入过程中没有注意到的问题，无论是移动扇区还是文件系统跟踪数据。关键是，在写入时可能会引入错误，其中数据在 HDD（或 RAID 硬件）内部被损坏，因此错误的数据被写入与其纠错码匹配。如果这是（唯一的）原因，那么一次验证应该足以表明它确实写得很好。

或者，数据在磁盘上显示正常后是否会变坏？即验证一次，一切正常；稍后验证并发现错误，此时该扇区尚未在中间写入。我认为这就是意思，因为通过改进的刷新检查可以很容易地处理写入时错误。

那么，如何在不触发数据附带的纠错码的情况下发生这种情况呢？

我真的不知道要寻找什么，因为我得到的所有“纠错码”都是与您不知道错误位置的情况相关的东西。因此，这些代码比我需要的要复杂得多且效率低下。

在下文中，请注意位等于数据包（因为只能丢失整个数据包，因此位类比非常适合）。

是否有 ECC 考虑到您已经知道丢失了哪些k位，并且只为您提供了一种在这些k位置重建数据流的方法？另外，ECC添加的位应该是独立的（最好是）。这样，如果数据的ECC部分内部发生丢包，它仍然可以重建一些原始数据（并不总是会有k个错误，大多数不会有。所以ECC对自己的容错很重要添加了 ECC 位）。

这是一个很大的区别IMO。对于一个丢失的位很简单，我可以只使用一个 XOR 位。但我不够聪明，无法将其推广到 n 位。

再说一次，我有一个n位流，并且我知道最多丢失了k位（我真的知道哪些是确切的并且它们丢失了，不可能发生损坏）。现在我需要一个编解码器，它可以在向数据流中添加尽可能少的开销的情况下重建它们。我梦想有(n+k)位来纠正n位流中的k个随机位错误:)。最重要的是，理想情况下，如果添加到n位数据流的k ECC 位中的任何一个被损坏，例如k位中的c位被损坏，那么它应该仍然能够重建(kc)位错误中的n比特流。

请注意，尽管 xD 我事先并不知道错误位置。

例子：

我能想到的一种算法是这样的。要防止错误的 n 位数据流。

设 p 是 n 的最小相对素数。然后用 i = (p * j) mod n 迭代数据流，通过递增 j，对通过选择每个偶数 j 的位获得的子流进行异或。该子流有 n/2 个元素。迭代后，我们获得了 n/2 个元素的奇偶校验。我们可以以相同的方式获得另一半的另一个奇偶校验（取奇数 j）。

对于 2 位丢失，这会产生 50% 的错误减少。

好的一面是我们现在可以任意变得更好。只需取下一个较高的相对质数，然后再做同样的事情。现在我们有 25% 的错误机会。基本上，每次我们添加两个额外的奇偶校验位时，我们可以将错误机会减少一半。

您好，我有一个带有四个标记的图像，如下图所示，图像没有正确对齐。

我使用图像中两个左侧标记的质心画了一条线，这条线没有对齐，图像需要一些旋转来固定。

我怎样才能执行这个旋转，我怎么知道我应该旋转图像多少度？

我有每个标记中心的两个点（我的标记）。

我搜索但没有找到任何东西，有人告诉我使用霍夫变换进行偏斜校正，我该如何执行？

有人可以指出我正确的方向吗？

也许使用这两个点得到线方程（极坐标系）然后得到角度，这可能吗？那么我只需要旋转（180º - 结果角度），对吗？[数学题]

非常感谢您提前

我正在尝试在 Python 中实现一个 Reed-Solomon 编码器-解码器，支持对擦除和错误的解码，这让我发疯。

该实现目前支持仅解码错误或仅擦除，但不能同时解码两者（即使它低于 2*errors+erasures <= (nk) 的理论界限）。

从 Blahut 的论文（这里和这里）看来，我们只需要用擦除定位多项式初始化错误定位多项式，就可以隐式计算 Berlekamp-Massey 内的勘误定位多项式。

这种方法部分适用于我：当我有 2*errors+erasures < (nk)/2 时它可以工作，但实际上在调试之后它才有效，因为 BM 计算了一个错误定位器多项式，它得到与擦除定位器多项式完全相同的值（因为我们低于仅错误校正的限制），因此它通过 galois 域被截断，我们最终得到了擦除定位多项式的正确值（至少我是这样理解的，我可能是错的）。

但是，当我们超过 (nk)/2 时，例如如果 n = 20 且 k = 11，则我们可以纠正 (nk)=9 个擦除符号，如果我们输入 5 个擦除，那么 BM 就会出错。如果我们输入 4 个擦除 + 1 个错误（我们仍然远低于界限，因为我们有 2*errors+erasures = 2+4 = 6 < 9），BM 仍然会出错。

我实现的 Berlekamp-Massey 的确切算法可以在这个演示文稿中找到（第 15-17 页），但是可以在此处和此处找到非常相似的描述，在这里我附上数学描述的副本：

现在，我将这个数学算法几乎完全复制到了 Python 代码中。我想要扩展它以支持擦除，我尝试使用擦除定位器初始化错误定位器 sigma：

多项式和 GF256int 分别是 2^8 上的多项式和伽罗瓦域的通用实现。这些类是单元测试的，并且它们通常是错误证明的。Reed-Solomon 的其他编码/解码方法也是如此，例如 Forney 和 Chien 搜索。我在这里谈论的问题的快速测试用例的完整代码可以在这里找到：http ://codepad.org/l2Qi0y8o

这是一个示例输出：

在这里，擦除解码总是正确的，因为它根本不使用 BM 来计算擦除定位器。通常，其他两个测试用例应该输出相同的 sigma，但它们根本不会。

当您比较前两个测试用例时，问题来自 BM 的事实在这里是公然的：校正子和擦除定位器是相同的，但得到的 sigma 完全不同（在第二个测试中，使用了 BM，而在不调用仅擦除 BM 的第一个测试用例）。

非常感谢您对我如何调试它的任何帮助或任何想法。请注意，您的答案可以是数学或代码，但请解释我的方法出了什么问题。

/EDIT：仍然没有找到如何正确实现勘误表BM解码器（请参阅下面的答案）。赏金提供给任何可以解决问题（或至少引导我找到解决方案）的人。

/ EDIT2：愚蠢的我，对不起，我刚刚重新阅读了架构，发现我错过了作业中的更改L = r - L - erasures_count......我已经更新了代码来解决这个问题并重新接受了我的答案。

我最近创建了这个简单的程序来查找平均速度。

平均速度 = Δx / Δt

我选择 x 作为 t 的函数，因为x =t^2

因此v =2t

此外，平均 v =(x2 - x1) / (t2 - t1)

我选择区间为t =1s to 4s。暗示x 来自1 to 16

因此平均 v = (16 - 1) / (4 - 1)= 5

现在程序：

我使用非常小的时间增量来计算很多时刻的速度。现在，如果t的增量为 0.001，则计算出的 avg v 为 4.99998。
现在，如果我将t的增量设为 0.0001，则 avg v 变为5.00007！

进一步减少增量到 0.00001 产生 avg v = 5.00001

为什么呢？

谢谢你。

这是在零件选择交易中出现的。一些 ARM 单片机具有缓存级 ECC，但没有 RAM 级 ECC。似乎任何受 ECC 保护的系统都与其最薄弱的环节一样强大。我只缺少缓存级 ECC 是否有理由？

关于 Shor 的量子 9 位纠错码，该代码是否可以纠正任何单个 qbit 上的任何错误？还是它只纠正一个相位或一点翻转？我该如何验证？

我一直在尝试解决 java 中的 3n+1 问题。但是我的输出似乎非常随机。问题是考虑以下算法：

给定输入 22，将打印以下数字序列 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

据推测，对于任何整数输入值，上述算法将终止（当打印 1 时）。尽管算法很简单，但这个猜想是否正确尚不清楚。然而，已经验证了对于所有整数 n，使得 0 < n < 1,000,000（事实上，对于比这更多的数字。）

给定输入 n，可以确定打印的数字数量（包括 1）。对于给定的 n，这称为 n 的周期长度。在上面的例子中，循环长度 22 是 16。

对于任何两个数字 i 和 j，你要确定 i 和 j 之间所有数字的最大循环长度。

输入

输入将由一系列整数对 i 和 j 组成，每行一对整数。所有整数都将小于 1,000,000 且大于 0。

您应该处理所有整数对，并为每对确定 i 和 j 之间（包括 i 和 j）之间所有整数的最大循环长度。

您可以假设没有任何操作会溢出 32 位整数。

输出

对于每对输入整数 i 和 j，您应该输出 i、j 以及介于 i 和 j 之间且包括 i 和 j 的整数的最大循环长度。这三个数字应至少用一个空格隔开，所有三个数字都在一行，每行输入对应一行输出。整数 i 和 j 必须按照它们在输入中出现的顺序出现在输出中，并且后面应该是最大循环长度（在同一行上）。我的代码如下

现在我的输入是

预期输出为

但是我的输出是

请帮我找出错误