当前位置：文江博客话题详情

所需奇偶校验位的数量

发布于 2024-09-24 18:34:40 字数 226 浏览 4 评论 0原文

我正在阅读有关错误检测的内容，偶然发现了一个我不太理解的声明。该声明说“对于 ak 位字符串，我们需要 lg k 奇偶校验位来检测 2 位错误”。其中 lg 是以 2 为底的对数，

我不太明白为什么这是真的，是否有任何正式的推导可以证实这一点。

这本书的名字是 Gallahager 的《数据网络》。

我并不怀疑这本书所说的内容，但我只是好奇地想看看它的推导。

谢谢，钱德

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

失去的东西太少 2024-10-01 18:34:40

查看维基百科页面的循环冗余检查。严格来说，奇偶校验位是 1 位检查，因此谈论多于 1 个奇偶校验位可能是等效 CRC 的简写。文章“CRC 数学” 提供了有关推导的更多信息。

回复收藏 0 原文

水波映月 2024-10-01 18:34:40

术语

对于“线性”码（CRC、汉明码等），每个数据位总是影响固定的一组（但不是全部）奇偶校验位。例如，如果（仅）数据的第 7 位在传输过程中被翻转，并且翻转奇偶校验位 2 和 4，但不翻转奇偶校验位 5（在重新计算的奇偶校验位中，与接收到的奇偶校验位相比），则翻转对于每个可能的有效负载数据位帧，数据的第 7 位将翻转奇偶校验位 2 和 4，但不会翻转奇偶校验位 5。
有效负载中影响特定奇偶校验位（例如奇偶校验位 5）的所有位以及该奇偶校验位本身都被称为被该奇偶校验位“覆盖”或“保护”。
当接收器重新计算奇偶校验位，并将重新计算的奇偶校验位与接收到的奇偶校验位进行比较时，其差异称为校正子。当没有错误时，综合症为零。
换句话说，syndrome = recalculated_parity XOR receive_parity。

证明

证明需要 n 个奇偶校验位才能检测 2^n 位有效负载数据位帧中的 2 位错误：

当在有效负载数据位中仅存在 1 个错误时整个框架，
当接收器重新计算奇偶校验位时，
有两种情况：

每个重新计算的未覆盖错误位的奇偶校验位与相应的接收到的奇偶校验位相同。（校正子中的对应位为“0”）。
覆盖错误位的每个重新计算的奇偶校验位与对应的接收到的奇偶校验位不同，并且检测到错误。（校正子中对应的位是“1”）。

当整个帧恰好有2个错误时，
得到的综合症是由每个孤立错误引起的综合症的异或。
当接收器重新计算奇偶校验位时，有3种情况：

(a)未覆盖任一错误位的每个重新计算的奇偶校验位与相应的接收到的奇偶校验位相同。（校正子中的对应位为“0”）。
(b) 覆盖两个错误位的每个重新计算的奇偶校验位与相应的接收到的奇偶校验位相同。（每个错误都会翻转该位一次，并且两次翻转合并后会将该位返回到原始状态，因此校正子中的相应位为“0”）。
(c)覆盖一个错误位且不覆盖另一错误位的每个重新计算的奇偶校验位与对应的接收到的奇偶校验位不同，并且检测到错误。（校正子中对应的位是“1”）。

假设，如果存在一些有效负载位，使得翻转它会产生一些综合症 S，
并且还有任何其他有效负载位可以产生完全相同的综合症 S，
那么同时命中这两个位的双位错误将无法检测到。
换句话说，该两位错误将给出S xor S == 0 的综合症。
换句话说，每个奇偶校验要么是情况(a)，要么是情况(b)，这两种情况都不能检测到这样的错误。
那会很糟糕。

因此，为了检测帧中每一个可能的两位错误，
我们必须设计错误检测代码，使得
每个单位错误都必须产生不同的综合症。
换句话说，对于帧中两个错误位的每种可能情况，必须至少有 1 个类型 (c) 的奇偶校验位。

使用 n 个奇偶校验位给出 n 个校正子位。
对于 n 个校正子位，最多有 2^n 种可能的不同校正子。
因此，为了确保帧中的每个位（当它是唯一的错误时）给出不同的综合症，
帧中最多必须有 2^n 位。

我敢打赌，如果您在 https://math.stackexchange.com/ 上发布这个问题，您会得到一个更短、更优雅的证明:-)。

terminology

For "linear" codes (CRC, Hamming codes, etc.), each data bit always affects a fixed set of some (but not all) of the parity bits. For example, if (only) bit 7 of the data is flipped in transit, and that flips parity bits 2 and 4 but not parity bit 5 -- in the recalculated parity bits, compared to the as-received parity bits -- then flipping bit 7 of the data will flip parity bits 2 and 4 but not parity bit 5 for every possible frame of payload data bits.
All the bits in the payload that affect a particular parity bit (such as parity bit 5), and that parity bit itself, are said to be "covered" or "protected" by that parity bit.
When the receiver re-calculates the parity bits, and compares the re-calculated parity bits with the received parity bits, the difference is called the syndrome. When there were no errors, the syndrome is zero.
In other words, syndrome = recalculated_parity XOR recieved_parity.

Proof

A proof that n parity bits are required to detect 2 bit errors in a 2^n bit frame of payload data bits:

When there is only 1 error in the entire frame,
when the receiver re-calculates the parity bits,
there are two cases:

Each recalculated parity bit that does not cover the erroneous bit is the same as the corresponding received parity bit. (The corresponding bit in the syndrome is "0").
Each recalculated parity bit that covers the erroneous bit is different from the corresponding received parity bit, and the error is detected. (The corresponding bit in the syndrome is "1").

When there is exactly 2 errors in the entire frame,
the resulting syndrome is the XOR of the syndrome caused by each error in isolation.
When the receiver re-calculates the parity bits, there are 3 cases:

(a) Each recalculated parity bit that does not cover either erroneous bit is the same as the corresponding received parity bit. (The corresponding bit in the syndrome is "0").
(b) Each recalculated parity bit that covers both erroneous bit is the same as the corresponding received parity bit. (Each error flips such a bit once, and both flips combined return that bit to the original state, so the corresponding bit in the syndrome is "0").
(c) Each recalculated parity bit that covers one erroneous bit, and does not cover the other erroneous bit, is different from the corresponding received parity bit, and the error is detected. (The corresponding bit in the syndrome is "1").

If, hypothetically, there existed some payload bit such that flipping it produces some syndrome S,
and there is any other payload bit that produces exactly the same syndrome S,
then a two-bit error that hit both of those bits would be undetectable.
In other words, that two-bit error would give syndrome of S xor S == zero.
In other words, each parity is either case (a) or case (b), neither of which can detect such an error.
That would be bad.

So in order to detect every possible two-bit error in the frame,
we must design the error-detection code such that
each single-bit error must produce a different syndrome.
In other words, there must be at least 1 parity bit of type (c) for every possible case of two erroneous bits in the frame.

Using n parity bits gives n syndrome bits.
With n syndrome bits, there are at most 2^n possible different syndromes.
So to make sure that each bit in the frame (when it is the only error) gives a different syndrome,
we must have at most 2^n bits in the frame.

I bet if you posted this question on https://math.stackexchange.com/ you'd get a much shorter and more elegant proof :-).

回复收藏 0 原文

~没有更多了~