标签: error-detection

MurmurHash3和 xxHash等非加密哈希几乎专为哈希表设计，但它们的功能似乎与CRC-32、Adler-32和Fletcher-32相当（甚至更有利）。非加密哈希通常比 CRC-32 更快，并产生更多类似于慢速加密哈希（MD5、SHA）的“随机”输出。尽管如此，我只看到 CRC-32 或 MD5 被推荐用于数据完整性/校验和目的。

在下表中，我测试了 32 位校验和/CRC/哈希函数，以确定它们检测数据中微小差异的能力：

每个单元格中的结果意味着：A) 发现的冲突次数，以及 B) 32 个输出位中的任何一个设置为 1 的最小和最大概率。要通过测试 B，最大值和最小值应尽可能接近 50 . 任何低于 45 或高于 55 的东西都表明存在偏见。

查看表格，MurmurHash3 和Jenkins lookup2与 CRC-32（实际上未通过一项测试）相比要好得多。它们也分布良好。DJB2 和 FNV1a 通过了碰撞测试，但分布不佳。Fletcher32 和 Adler32 在 NullBytes 和 8RandBytes 测试中挣扎。

那么我的问题是，与其他校验和相比，“非加密哈希”有多适合检测文件中的错误或差异？CRC-32/Adler-32/CRC-64 是否有任何理由可能胜过任何体面的 32 位/64 位哈希？

我有一个发送数据单元的假设情况,每个数据单元都有一千个字节.故障率很少,但是当发生错误时,它不太可能是单个位错误,并且更可能是连续几位中的错误.

起初我想过使用校验和,但显然可能会错过大于一位的位错误.奇偶校验也不起作用,因此CRC可能是最佳选择.

使用循环冗余校验是否有效千字节？或者还有其他方法可以更好地运作吗？

我有一个奇怪的通信通道,我需要检测错误并消除通道中的某些序列.

每条消息长12位,分成3个半字节(每个4位).我需要提取至少450个不同的代码,所以我的汉明距离可以达到3.

但是,我不能将两个半字节序列相同,因此以下序列无效:

0xf 0xf 0xf - Three of the same nibbles in sequence
0x8 0x8 0x0 - Two of the same nibbles in sequence
0xf 0x3 0x3 - Two of the same nibbles in sequence

此外,消息可以相互跟随而不会中断,因此一个序列的开头不能与最后一个序列的末尾具有相同的第一个半字节:

0x327 0x743 - Even though they are not in the same message, two sequential nibbles are the same in the message stream

但是以下序列很好:

0x1 0x2 0x1 - Two nibbles same, but separated by another nibble
0x0 0x1 0x2 - All nibbles different
0xf …

错别字发生了,有时候用JavaScript跟踪它们真的很难.以此为例(想象一下在更多代码之间):

// no error. I would like a warning
document.getElementById('out').innerHtml = "foo";

对于未声明的变量,严格模式有助于:

"use strict";
var myHTML = "foo";
myHtml = "bar"; // -> error

但它不适用于上面的例子.是否有可以捕获这些错误的程序或模式？我尝试过JSLint和JavaScript Lint,但他们没有抓住它.

理想情况下,我希望这仍然可以工作(没有警告):

// should work (without warning)
function MyClass(arg) {
  this.myField = arg;
}

我试图找出如何计算任意 CRC 多项式的错误检测能力。

我知道有各种错误检测功能可能（或可能不）适用于任意多项式：

1. 检测单个位错误：所有 CRC 都可以执行此操作，因为这仅需要 CRC 宽度 >= 1。

2. 突发错误检测：所有 CRC 都可以检测大小等于其宽度的突发错误。

3. 检测奇数位错误：CRC 与多项式的偶数项（这意味着完整二进制多项式中 1 位的偶数）可以做到这一点。

4. 检测随机位错误（取决于帧大小）：我有一个现成的 C 算法，可以计算给定 HD 和多项式的最大帧大小。我没有完全理解它，但它有效。

让我们假设一个 16 位 CRC 多项式 x¹?+x¹²+x?+1 = 0x11021。该多项式可以：

• 检测所有单位错误（与数据大小无关）。
• 检测所有高达 16 位宽度的突发错误（与数据大小无关）。
• 检测所有奇数个误码（因为它有 4 个多项式；与数据大小无关）。
• 检测高达 32571 位数据大小的 3 位错误 (HD4)。

以上正确吗？

是否有额外的 CRC 错误检测功能？如果是，我如何检查（没有深入的数学知识）任意 CRC 多项式是否支持它们？

什么是CRC？它如何帮助进行错误检测？

据说CRC（循环冗余校验和）可以检测到小于r +1位的突发错误，其中r是多项式的次数。此外，以1 – 2 ^-r的概率检测到长度大于r + 1位的突发。

有人可以指导我提供相同的证明吗？

您能否建议一种错误检测方案,用于检测33字节消息的前32个字节中的一个可能的位翻转,使用不超过8位的附加数据？

Pearson哈希能成为解决方案吗？

我们是否将奇偶校验位添加到位集的前面或后面？作为对一组二进制值的检查的一个位,以这样的方式计算:集合中的1的数量加上奇偶校验位应该总是偶数(或者偶尔应该总是奇数).

Dart编辑器版本1.2.0.release(STABLE).Dart SDK 1.2.0版.

此源代码生成运行时异常.

void main() {
  test(new Base());
}

void test(Child child) {
}

class Base {
}

class Child extends Base {
}

我假设分析仪生成这样的东西.

The argument type 'Base' cannot be assigned to the parameter type 'Child'

但是我只能在发生此异常(post factum)时在运行时检测到此错误.

Unhandled exception:
type 'Base' is not a subtype of type 'Child' of 'child'.