奇偶校验位

奇偶校验位是一种简单的错误检测码。

分为偶检验位和奇校验位两种。对于偶校验位来说,如果 01 序列中的 1 的个数是奇数,那么校验位是 1,使得添加校验位后的 1 的个数是偶数,否则校验位是 0;奇校验位刚好相反。

从定义来说,可以看到,奇偶校验仅能检测奇数个位数发生反转的错误,不能检测偶数个位发生反转的情况,也不能确定哪些位发生了反转,故不能纠错。

校验位的生成

对于 01 序列 AnAn-1…A1,其偶检验位是 (An + An-1 + … + A1) mod 2,奇校验位是 (An + An-1 + … + A1 + 1) mod 2。

01 序列的求和模 2 可以用异或来实现。

把 01 序列重新排列成 m 个连续的 1 和 n 个连续的 0。记 m 个 1 的异或为 p,n 个 0 的异或为 q。其中 q 不乱 n 是奇偶都会是 0,而 m 是奇数时,p 将是 1,m 是偶数时,p 将是 0。

有以下表格:

m n m mod 2 p q p^q
1 1 0 1
1 1 0 1
0 0 0 0
0 0 0 0

可见,各位求和后模 2 即是各位做异或。

异或(XOR)

符号是 ⊕,下面用编程语言中的 ^ 来表示

异或满足交换率、结合律。

  • a^a = 0
  • a^0 = a
  • a^b = b^a
  • a^b^c = a^(b^c) = (a^b)^c
  • c = a^b => a = b^c => c = b^a
  • a^b^a = b

发表评论

电子邮件地址不会被公开。 必填项已用*标注