计算奇偶校验 [英] Computing the Parity
问题描述
我不完全理解这种算法计算奇偶校验位。
可有人请详细解释一下？
以下code是从'黑客的喜悦'书采取：
内部奇偶校验（无符号X）{
无符号ÿ;
Y = X ^（X GT;大于1）;
Y = Y ^（γ＆GT;＆→2）;
Y = Y ^（γ＆GT;→4）;
Y = Y ^（Y＆GT;＆GT; 8）;
Y = Y ^（Y＆GT;＆GT; 16）;
返回Y'放大器; 1;
}
首先一点理论。
-
一组位的奇偶性
即使1位的数目是偶数，是奇数，如果
1位的个数为奇数。 -
我们EN code中的奇偶校验信息如下：
- 1 - >设定的奇偶校验为奇数
- 0 - >设置的平价甚至是
- 一组两个位中的奇偶校验可以简单地被计算
使用XOR：
B0 B1 - > P1-0
＆ndash的; -------------------------
0 ^ 0 - > 0 - >偶校验
0 ^ 1 - > 1 - >奇偶奇
1 ^ 0 - > 1 - >奇偶奇
1 ^ 1 - > 0 - >偶校验 - 一组位S能够从两个不相交的子集的奇偶
S1，S2来计算的奇偶这样取值＆NBSP;=＆NBSP;S1 UNION S2使用XOR：P（S）= P（S1）^ P（S2）。事实上：- 如果
S1和S2具有相同的奇偶性，即它们都具有偶数位或奇数比特数，他们的工会取值将有偶数个位数。 - 如果
S1和S2有不同的校验，S将有奇数个。
- 如果
现在我们能够理解的伎俩，假设一个 unsigned int类型有32位：它计算奇偶校验递归由两位的子集分组位开始（两个相邻的比特），然后它执行对这些子集的奇偶校验。然后，它通过使用刚刚计算出的2比特的子集的奇偶检查的4位下一更大集合的奇偶校验。然后它与8位和16位的子集
让我们看看它以图形（上为清晰起见，至少有意义位）：
Y = X ^（X GT;＆GT; 1）
X：B7 B6 B5 B4 B3 B2 B1 B0
点¯x>> 1：B8 B7 B6 B5 B4 B3 B2 B1
Y =：P8-7 P7-6 P6-5 P5-4 P4-3 P3-2 P2-1 P1-0
当我用符号的Pn-M 来表示组具有位置位，从 M 奇偶到 N 。因为我们必须用不相交的子集计算奇偶校验，我们只使用二分之一的奇偶校验值，我将标志着他人以？来表示他们是没有意义的。因此，我们有：
Y：？ P7-6？ P5-4？ P3-2？ P1-0
Y = Y ^（Y＆GT;＆GT; 2） （考虑到更高阶位）
Y：P15-14？ P13-12？ P11-10？ P9-8？ P7-6？ P5-4？ P3-2？ P1-0
Ÿ>> 2：P17-16？ P15-14？ P13-12？ P11-10？ P9-8？ P7-6？ P5-4？ P3-2
Y =：P17-14？ P15-12？ P13-10？ P11-8？ P9-6？ P7-4？ P5-2？ P3-0
同样，因为我们只需要脱节的子集的奇偶性，我们忽略结果的一些位，以避免重复设置，即 P5-2 ， P9-6 等，从而获得：
Y：?? P15-12？ P11-8？ P7-4？ P3-0
Y = Y ^（Y＆GT;＆GT; 4） （考虑到更高阶位）
Y：P23-20？ P19-16？ P15-12？ P11-8？ P7-4？ P3-0
Ÿ>> 4：P27-24？ P23-20？ P19-16？ P15-12？ P11-8？ P7-4
Y =：P27-20？ P23-16？ P19-12？ P15-8？ P11-4？ P7-0
再次忽略重叠集（和分组 S表示可读性）：
Y：???? P23-16？ ???? P15-8？ ???? P7-0
Y = Y ^（Y＆GT;＆GT; 8） （考虑到所有32位）：
Y：P31-24？ ???? P23-16？ ???? P15-8？ ???? P7-0
Ÿ>> 8：0 000 0000 P31-24？ ???? P23-16？ ???? P15-8
Y =：P31-24？ ???? P31-16？ ???? P23-8？ ???? P15-0
再次忽略重叠集：
Y：???? ???? P31-16？ ???? ???? ???? P15-0
Y = Y ^（Y＆GT;＆GT; 16）
Y：???? ???? P31-16？ ???? ???? ???? P15-0
Ÿ>> 16：0000 0000 0 000 0000 ???? ???? P31-16
Y =：???? ???? P31-16？ ???? ???? ???? P31-0
返回Y'放大器; 1
Y：???? ???? P31-16？ ???? ???? ???? P31-0
1：0000 0000 0 000 0000 0000 0000 1
Y'1：0000 0000 0 000 0000 0000 0000 P31-0
所以，你可以看到，返回的值就是校验位 P31-0 为参数的位 X ，这正是我们想要的。
I don't fully understand this algorithm of calculating the parity bit. Can someone please explain in detail?
The following code is taken from the 'Hacker's Delight' book:
int parity(unsigned x) {
unsigned y;
y = x ^ (x >> 1);
y = y ^ (y >> 2);
y = y ^ (y >> 4);
y = y ^ (y >> 8);
y = y ^ (y >>16);
return y & 1;
}
First a bit of theory.
The parity of a set of bits is even if the number of 1-bits is even, is odd if the number of 1-bits is odd.
We encode the parity information as:
- 1 --> parity of the set is odd
- 0 --> parity of the set is even
- The parity of a set of two bits can simply be computed
using XOR:
b0 b1 --> P1-0 –------------------------- 0 ^ 0 --> 0 --> parity even 0 ^ 1 --> 1 --> parity odd 1 ^ 0 --> 1 --> parity odd 1 ^ 1 --> 0 --> parity even
- The parity of a set of bits S can be computed from the parities of two disjoint subsets
S1,S2such thatS=S1 UNION S2using XOR:P(S) = P(S1) ^ P(S2). In fact:- if
S1andS2have the same parity, i.e. they both have an even number of bits or an odd number of bits, their unionSwill have an even number of bits. - if
S1andS2have different parity, S will have an odd number of bits.
- if
Now we are able to understand the trick, assuming an unsigned int has 32 bits: it computes the parity "recursively" starting by grouping the bits in subsets of two bits (two adjacent bits), then it performs the parity check on those subsets. Then it checks the parity of the next-bigger sets of 4 bits by using the parity of the 2-bits subsets just computed. Then it goes on with 8-bits and 16-bits subsets.
Let's see it graphically (on the least significative bits for clarity):
y = x ^ (x >> 1)
x: b7 b6 b5 b4 b3 b2 b1 b0 x>>1: b8 b7 b6 b5 b4 b3 b2 b1 y=: P8-7 P7-6 P6-5 P5-4 P4-3 P3-2 P2-1 P1-0
Where I used the notation Pn-m to denote the parity of the set of bits having position from m to n. Since we must compute the parity using disjoint subsets, we use only one out of two of those parity values, I'll mark the others with ? to mean they are not meaningful. So we have:
y: ? P7-6 ? P5-4 ? P3-2 ? P1-0
y = y ^ (y >> 2) (taking into account more higher order bits)
y: P15-14 ? P13-12 ? P11-10 ? P9-8 ? P7-6 ? P5-4 ? P3-2 ? P1-0 y>>2: P17-16 ? P15-14 ? P13-12 ? P11-10 ? P9-8 ? P7-6 ? P5-4 ? P3-2 y=: P17-14 ? P15-12 ? P13-10 ? P11-8 ? P9-6 ? P7-4 ? P5-2 ? P3-0
Again, since we need only the parity of disjoint subset, we neglect some bits of the result to avoid overlapping sets, i.e. P5-2, P9-6, etc., thus obtaining:
y: ?? P15-12 ??? P11-8 ??? P7-4 ??? P3-0
y = y ^ (y >> 4) (taking into account more higher order bits)
y: P23-20 ??? P19-16 ??? P15-12 ??? P11-8 ??? P7-4 ??? P3-0 y>>4: P27-24 ??? P23-20 ??? P19-16 ??? P15-12 ??? P11-8 ??? P7-4 y=: P27-20 ??? P23-16 ??? P19-12 ??? P15-8 ??? P11-4 ??? P7-0
Again, neglecting overlapping sets (and grouping ?s for readability):
y: ???? P23-16 ??? ???? P15-8 ??? ???? P7-0
y = y ^ (y >> 8) (taking into account all 32 bits):
y: P31-24 ??? ???? P23-16 ??? ???? P15-8 ??? ???? P7-0 y>>8: 0 000 0000 P31-24 ??? ???? P23-16 ??? ???? P15-8 y=: P31-24 ??? ???? P31-16 ??? ???? P23-8 ??? ???? P15-0
Again, neglecting overlapping sets:
y: ???? ???? P31-16 ??? ???? ???? ???? P15-0
y = y ^ (y >> 16)
y: ???? ???? P31-16 ??? ???? ???? ???? P15-0
y>>16: 0000 0000 0 000 0000 ???? ???? P31-16
y=: ???? ???? P31-16 ??? ???? ???? ???? P31-0
return y & 1
y: ???? ???? P31-16 ??? ???? ???? ???? P31-0
1: 0000 0000 0 000 0000 0000 0000 1
y&1: 0000 0000 0 000 0000 0000 0000 P31-0
So you can see that the returned value is just the parity bit P31-0 for the bits of the argument x, which is what we wanted.
这篇关于计算奇偶校验的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
