单纠错问题汉明码冗余比特公式的证明

网络工程 网络 网络理论
2022-02-23 15:26:46
  1. m --->一帧的数据位数
  2. r --->冗余位数
  3. n=m+r ----> 码字的长度(数据+冗余位)

想象一下,我们想要设计一个包含m个消息位和r个校验位的代码,它允许纠正所有单个错误。

在计算冗余比特数的公式的证明中(m + r + 1) ≤ 2^r

我已经理解了以下声明:

2^m 个合法消息中的每一个在距离(汉明距离)为 1 处都有 n 个非法代码字。这些是通过系统地反转由它形成的 n 位代码字中的每个 n 位而形成的。

但我目前坚持以下声明:

因此,2^m 个合法消息中的每一个都需要 n + 1 个专用于它的位模式。

特别是在第二个陈述中,我不明白这一点为什么第二个陈述是第一个陈述的结果

在此处输入图像描述

塔南鲍姆的证明:

在此处输入图像描述

2个回答

因此,2^m 个合法消息中的每一个都需要 n + 1 个专用于它的位模式。

m个数据位允许 2^ m个不同的消息。这些是使用m+r通道位重现的,因此合法通道消息之间的汉明距离允许您重现(单个)位错误并纠正它们。

我终于明白为什么上面的第二个陈述是第一个陈述的结果。

上述四个消息中的每一个都与一个合法代码字加上n 个非法代码字相关联。

  • 合法码字:由偶数个1组成

  • 非法码字:由一个奇数组成

例如,第一条消息00有 4 个与之关联的码字,其中 3 个是非法的(每个码字通过反转与第一条消息00关联的合法码字000的每个单个位获得 ):

  1. 001
  2. 010
  3. 100

加上合法的:

  1. 000

所以第二个说法。