为了检测比特长度n_errors代码中的许多错误n_total，我们必须牺牲一定数量n_check的比特来进行某种校验和。
我的问题是：方法是什么，我必须牺牲最少的位数来检测位长度代码中n_check给定数量的错误。n_errorsn_total
如果对这个问题没有一般性的答案，我将非常感谢有关以下条件的方法的一些提示：
n_total=32，n_errors>1并且显然n_check应该尽可能小。
谢谢你。
问问题
162 次
1 回答
0
CRC动物园笔记链接：
http://users.ece.cmu.edu/~koopman/crc/notes.html
如果您查看 3 位 crc 的表格：
http://users.ece.cmu.edu/~koopman/crc/crc3.html
您可以看到第二个条目 0xb => x^3 + x + 1 具有 4 个数据位的 HD（汉明距离）3，总大小为 7 位。这可以检测到所有 2 位错误模式（共 7 位），但一些 3 位模式会失败，所有位都应该为零的明显情况是
0 0 0 1 0 1 1 (when it should be 0 0 0 0 0 0)
这是一个简单的示例，其中多项式中 1 的位数决定了最大误码数。为了验证 HD = 3（检测到 2 位错误），检查了总共 7 位、2 位坏的所有 21 种情况。
如果您检查 32 位 CRC，您会看到 0x04c11db7（以太网 802.3，在 263 个数据位 => 263+32 = 295 个总位时具有 HD=6（5 位错误检测），而 0x1f4acfb13 在 0x1f4acfb13 处具有 HD=6 32736 个数据位 => 32736+32 = 32768 个总位。
这是一篇关于搜索良好 CRC 的 pdf 文章：
https://users.ece.cmu.edu/~koopman/networks/dsn02/dsn02_koopman.pdf
为特定的汉明距离寻找“好”的 CRC 需要一些有关该过程的知识。例如，在 HD=6（5 个坏位检测）的 0x1f4acfb13 的情况下，在 32768 位中，有 314,728,365,660,920,250,368 种可能的 5 位坏位组合。但是，0x1f4acfb13 = 0x1f4acfb13 = 0xc85f*0x8011*0x3*0x3，并且 0x3 (x+1) 项中的任何一个都将检测到任何奇数个错误位，这将搜索减少到 4 个坏位情况。对于使用此多项式失败的消息的最小大小，第一位和最后一位将是错误的。这将搜索减少到仅 5 位中的 2 位，从而将案例数量减少到约 5.36 亿。不是为每个位组合计算 CRC，而是可以为其他全 0 位消息中的每个 1 位创建一个 CRC 表，然后可以对特定位对应的表条目进行异或运算以加快处理速度。对于不是第一位和最后一位的多项式，可以为所有 2 位错误生成一个 CRC 表（假设这样的表适合内存），然后排序，然后检查重复值（使用排序的数据，这只需要排序表的一个顺序传递）。重复值将对应于 4 位故障。其他情况需要不同的方法，在某些情况下，这仍然很耗时。这只需要排序表的一个顺序传递）。重复值将对应于 4 位故障。其他情况需要不同的方法，在某些情况下，这仍然很耗时。这只需要排序表的一个顺序传递）。重复值将对应于 4 位故障。其他情况需要不同的方法，在某些情况下，这仍然很耗时。
于 2020-02-05T15:04:13.193 回答