分组码纠正单比特错误所需校验位数的下界是什么？请证明。

分组码纠正单比特错误所需校验位数的下界是 $r+1$，其中 $r$ 是数据位数。

证明：

假设有一个 $(n,k)$ 分组码，其中 $n=k+m$，其中 $m$ 是校验位数。

考虑纠正单比特错误的情况，即只有一个比特出现错误。不失一般性，假设错误出现在第 $i$ 个比特上。

观察第 $i$ 位的校验位。由于每个校验位的作用是检测某些数据位的奇偶性，因此第 $i$ 位的校验位必定检测第 $i$ 个数据位。而且，由于只有一个比特出现错误，因此其他数据位的奇偶性都是正确的。因此，第 $i$ 位的校验位可以被用来检测第 $i$ 个数据位是否出错。

接下来考虑如何纠正错误。为了纠正错误，我们需要找到一个校验位，它检测的数据位包含第 $i$ 个数据位。假设第 $i$ 个数据位被 $r_1,r_2,\dots,r_p$ 个校验位检测，其中 $p\geq 1$。

现在考虑所有可能的错误位置。如果错误出现在第 $i$ 个数据位上，那么符合条件的校验位就是 $r_1,r_2,\dots,r_p$ 中的任意一个。如果错误出现在某个校验位上，那么符合条件的校验位就是被该校验位检测的所有数据位。

因此，如果要能够纠正单比特错误，那么必须满足以下条件：

1. 每个数据位必须被至少一个校验位检测。

2. 每个校验位必须检测至少两个数据位。

对于条件 1，由于每个数据位可以被 $r$ 个校验位检测，因此必须满足 $r\geq 1$。

对于条件 2，由于每个校验位只能检测奇偶性，因此必须至少检测两个数据位才能确定这两个数据位是否相同。因此，每个校验位必须检测至少两个数据位。由于有 $m$ 个校验位，因此必须满足 $2m\leq n$，即 $m\leq \frac{n}{2}$。

综上所述，必须满足 $r\geq 1$ 和 $m\leq \frac{n}{2}$ 才能纠正单比特错误。因此，必须满足 $m+r\leq n+1$，即 $m\geq n-r+1$。因为 $n=k+m$，所以 $k=n-m$，从而 $k\geq r+1$。因此，分组码纠正单比特错误所需校验位数的下界是 $r+1$。