差错检测与纠正：奇偶校验与二维奇偶校验

差错检测的基本思路

发送方在要保护的数据$D$后面附加差错检测和纠正比特（EDC, Error-Detection and -Correction），一起发送给接收方。接收方收到的可能是被改变了的$D'$和$EDC'$，它根据二者判断数据是否出错。差错检测技术并不能保证发现所有差错：总有一些差错模式恰好能“骗过”检测。一般来说，EDC越长，漏检的概率就越小，但开销也越大。

奇偶校验（Parity Check）

差错检测最简单的方式就是使用单个奇偶校验位（parity bit）。假设待发送的信息为0111000110101011，当使用偶校验时，发送方只需再附加一个比特1，使得全部比特中1的数量为偶数。

如果采用偶校验的方式，作为接收方只需数一数接收信息中1的个数是否为偶数即可。如果出现了奇数个1，说明信息中出现了奇数个比特差错。然而，如果出现了偶数个比特差错，将会导致差错无法被检测出来。

奇校验的规则与之相反：附加的校验位使全部比特中1的数量为奇数。在上例中，奇校验位应为0。实际信道中的差错往往成串出现（突发差错），一次影响多个相邻比特，单个奇偶校验位漏检的可能性并不小。

二维奇偶校验

利用二维奇偶校验不仅可以检测到出现单个比特差错的问题，还能根据行和列的索引找到差错的比特并纠正。

把数据排成若干行、若干列，为每一行和每一列各计算一个奇偶校验位，右下角的比特再对这些校验位进行校验。下面是采用偶校验的例子：

如果第2行第2列的比特在传输中由1变成了0，第2行和第2列的校验都会失败，二者的交点就是出错的比特，接收方把它取反即可纠正：

二维奇偶校验能够检测出任意两个比特的差错，但不能纠正它们：两个差错在同一行时，只有两列的校验失败，无法确定在哪一行。如果四个差错恰好位于一个矩形的四个角上，每一行、每一列的1都成对变化，差错就完全检测不到。接收方不需要重传、直接纠正差错的能力称为前向纠错（FEC, Forward Error Correction），它在重传代价很高的场合（例如卫星链路和实时音视频）尤其有用。