【ARM 安全系列介绍 1 -- 奇偶校验与海明码校验详细介绍】

奇偶校验介绍

奇偶校验是一种错误检测方法，广泛应用于计算机内部以及数据通信领域。其基本原理是为了使得一组数据（通常是一字节8位）中的“1”的个数为偶数或奇数。
奇偶校验分为两种：

• 偶校验：确保数据中“1”的个数为偶数。如果“1”的个数是奇数，则添加一个“1”进行校验；如果“1”的个数已经是偶数，则添加一个“0”进行校验。
• 奇校验：确保数据中“1”的个数为奇数。如果“1”的个数是偶数，则添加一个“1”进行校验；如果“1”的个数已经是奇数，则添加一个“0”进行校验。

举个例子：
比如我们有一个字节的数据，二进制表示为1001 1100（十六进制为9C）。这个字节中“1”的个数为4，是偶数。

• 如果我们要进行偶校验，由于“1”的个数已经是偶数，所以我们添加一个“0”，得到的校验字节为1001 1100 0（十六进制为138）。
• 如果我们要进行奇校验，由于“1”的个数是偶数，所以我们添加一个“1”，得到的校验字节为1001 1100 1（十六进制为139）。

当接收方收到校验字节后，就可以通过计算“1”的个数来判断数据是否出现错误。如果接收到的字节中“1”的个数与预期（偶数或奇数）不符，就可以认为数据在传输过程中可能出现了错误。
需要注意的是，奇偶校验只能检测出单个位的错误，如果多个位同时出错，可能会导致错误无法被检测出来。

奇偶校验 python 实现

在串行通信中，奇偶校验被用于错误检测。但是值得注意的是，Linux系统并没有直接可以进行奇偶校验的命令。你可能需要使用其他工具或语言（如awk，perl，python等）来实现奇偶校验操作。这些操作通常涉及到二进制数的处理和位操作。

例如，下面的 Python 脚本可以计算一个文件的奇偶校验：

def parity_of(int_type): 
	parity = 0 
	while (int_type): 
		parity = ~parity 
		int_type = int_type & (int_type - 1) 
	return(parity) 

filename = 'yourfile' 
with open(filename, 'rb') as f: 
	c = f.read(1) 
	while c: 
		print(parity_of(ord(c))) 
		c = f.read(1)
1
2
3
4
5
6
7
8
9
10
11
12
13

这个脚本会读取文件 ‘yourfile’，然后逐字节计算奇偶校验，并输出结果。如果结果为0，表示该字节中有偶数个1；如果结果为-1，表示该字节中有奇数个1。

奇偶校验C代码实现

#include  

unsigned int parity(unsigned int n) 
{ 
	unsigned int parity = 0; 
	
	while (n) { 
		parity = !parity; 
		n = n & (n - 1); 
	} 
	
	return parity; 
} 

int main(void) 
{ 
	unsigned int n; 

	printf("Enter a number: "); 
	scanf("%u", &n); 
	printf("Parity of number %u is %s\n", n, (parity(n)? "odd": "even")); 

	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

上述代码首先会询问用户输入一个数字，然后计算该数字的偶校验。如果该数字的二进制表示中 ‘1’ 的个数是奇数，则它的偶校验就是奇数，反之则为偶数。

对于奇校验，只需稍微修改一下上述代码即可：

#include  

unsigned int parity(unsigned int n) 
{ 
	unsigned int parity = 1; // 修改这里 

	while (n) { 
		parity = !parity; 
		n = n & (n - 1); 
	} return parity; 
} 

int main(void) 
{ 
	unsigned int n; 
	
	printf("Enter a number: "); 
	scanf("%u", &n); 
	printf("Parity of number %u is %s\n", n, (parity(n)? "odd": "even")); 

	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

现在，如果输入的数字的二进制表示中 ‘1’ 的个数是奇数，则其奇校验就是偶数，反之则为奇数。

海明码详细介绍

海明码（Hamming code）是一种错误检测和纠正的编码方式，由美国数学家理查德·海明于1950年代早期提出。
海明码的核心思想是在数据位中插入多个校验位，这些校验位覆盖的数据位范围有所重叠，使得任何一个位的错误都能被至少两个校验位所发现。通过这种方式，如果某一位发生错误，可以通过查看所有的校验位来确定出错的是哪一位，从而达到纠错的目的。
具体来说，对于长度为 m 的信息位，我们需要添加r个校验位，其中 r 是满足: 2^rr >= m + r + 1 的最小整数。例如，对于长度为4位的信息位，我们需要添加3位校验位，因为 2³ = 8 >= 4 + 3 + 1。

在确定了校验位数量后，我们需要确定每个校验位的位置以及它们应该覆盖的数据位。这个过程有一定的规则可循：首先，把校验位放在2的整数幂的位置（1，2，4，8…等等）；然后，每个校验位覆盖的数据位是从该校验位的位置开始，覆盖相应的位数，然后跳过相同的位数，再覆盖相同的位数，以此类推。比如，位置在 2 的 n 次方的校验位，会覆盖从位置 n 开始的每隔 n个位。

生成了校验位之后，接收端可以通过检查每个校验位来确定是否有错误，以及错误在哪一位。如果所有的校验位都是正确的，那么数据没有错误；如果某些校验位错误，那么错误的位置就是这些错误校验位的位置之和。例如，如果位置2和位置4的校验位错误，那么错误的数据位就是位置 2+4=6。
海明码虽然只能纠正单个位的错误，但它的优点是实现简单，计算量小，适用于需要实时纠错的场景。