CRC多项式的原始性

问题描述 投票:1回答:2

我在网上发现了以下有关CRC性能的信息:

原始多项式。这具有HD = 3的最佳长度,并且在该长度之上具有良好的HD = 2性能。

我不明白。 HD = 3的最佳长度是可以理解的;但是好的HD = 2表现意味着什么呢? AFAIK所有CRC在HD = 2时具有无限数据长度。

那么对于原始多项式来说,“良好的HD = 2超过该长度的性能”意味着什么?

crc
2个回答
1
投票

...具有HD = 3的最佳长度,并且具有高于该长度的良好HD = 2性能。

该声明措辞不力。我在“Notation:”下的网页底部找到它

https://users.ece.cmu.edu/~koopman/crc

在我发现的这篇文章和其他文章中,缩写“HD”表示CRC的最小汉明距离:对于HD = k + 1,则CRC可以检测到消息中任何长度达到一定长度的k位错误(如图所示)在表中)。正如您所说,“所有CRC在HD = 2时都具有无限数据长度”。

使用短语“好HD = 2表现超过该长度”令人困惑。上面的网站链接到下面的网站,其中包括声明“HD = 2长度总是无限的,因此总是不在此列表之外。”

https://users.ece.cmu.edu/~koopman/crc/notes.html


Wiki hamming distance解释了位错误检测和汉明距离之间的关系:“代码C被认为是k错误检测,如果且仅当其任何两个代码字之间的最小汉明距离至少为k + 1时”正如您所述, “所有CRC在HD = 2时都具有无限数据长度”,这意味着无论消息长度如何,所有CRC都可以检测到任何单个位错误。

至于“HD = 3的最佳长度”,这意味着能够检测到2位错误,请考虑基于CRC多项式的linear feedback shift register,使用任何非零值初始化,如果循环寄存器足够多次,它将结束回到初始值。对于基于n + 1位本原多项式的n位CRC,寄存器将在重复之前循环通过所有2 ^ n-1个非零值。消息的最大长度(数据的长度加上CRC的长度),其中没有检测到2位错误的失败是2 ^ n - 1.对于长度为2 ^ n或更大的消息,则为任何“i”,如果位[0 + i]和位[(2 ^ n)-1 + i]出错,则原语CRC将无法检测到2位错误。如果CRC多项式不是原始的,则防故障2错误位检测的最大长度将减小,而不是“最佳”。

对于基于任何CRC多项式的线性反馈移位寄存器,初始化为任何非零值,无论它循环多少次,它都不会包含零值。这是解释为什么“所有CRC在HD = 2时具有无限数据长度”(能够检测单个位错误)的一种方法。


0
投票

作者说:“与许多其他多项式相比,原始多项式通常在HD = 2时具有相当好(即低)的权重。从我看起来已经有一段时间了,但我认为在所有情况下都高于HD = 2断点最低权重多项式总是原始的。“

对于一些算法实现,低权重可以提供更快的计算。

© www.soinside.com 2019 - 2024. All rights reserved.