Berechnung der Parität

Zuerst ein bisschen Theorie.

• Die Parität eines Bitsatzes ist selbst wenn die Anzahl der 1-Bits gerade ist, ist ungerade, wenn die Anzahl der 1-Bits ist ungerade.

• Wir kodieren die Paritätsinformation als:

  • 1 - & gt; Parität der Menge ist ungerade
  • 0 - & gt; Parität des Satzes ist gerade

• Die Parität eines Satzes von zwei Bits kann einfach berechnet werden mit 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
  

• Die Parität einer Menge von Bits S kann aus den Paritäten von zwei disjunkten Untermengen berechnet werden S1 , S2 , so dass S = S1 UNION S2 unter Verwendung von XOR: P(S) = P(S1) ^ P(S2) . Eigentlich:
  • Wenn S1 und S2 die gleiche Parität haben, d. h. beide eine gerade Anzahl von Bits oder eine ungerade Anzahl von Bits haben, wird ihre Vereinigung S eine gerade Anzahl von Bits haben.
  • Wenn S1 und S2 unterschiedliche Paritäten haben, hat S eine ungerade Anzahl von Bits.

Nun können wir den Trick verstehen, vorausgesetzt ein unsigned int hat 32 Bits: Er berechnet die Parität "rekursiv", indem er die Bits in Teilmengen von zwei Bits (zwei benachbarte Bits) gruppiert, dann führt er die Paritätsprüfung durch auf diesen Teilmengen. Dann prüft er die Parität der nächstgrößeren Sätze von 4 Bits, indem er die Parität der gerade berechneten 2-Bit-Untersätze verwendet. Dann geht es weiter mit 8-Bit- und 16-Bit-Teilmengen.

Sehen wir es uns graphisch an (an den am wenigsten signifikanten Stellen für Klarheit):

y = x ^ (x >> 1)

Wo ich die Notation Pn-m verwendet habe, um die Parität der Menge von Bits mit der Position von m bis n zu bezeichnen. Da wir die Parität mit disjunkten Teilmengen berechnen müssen, verwenden wir nur einen von zwei dieser Paritätswerte. Ich werde die anderen mit ? kennzeichnen, um zu bedeuten, dass sie nicht sinnvoll sind. So haben wir:

y = y ^ (y >> 2) (unter Berücksichtigung von Bits höherer Ordnung)

Da wir nur die Parität der disjunkten Teilmenge benötigen, vernachlässigen wir einige Bits des Ergebnisses, um überlappende Mengen zu vermeiden, d. h. P5-2 , P9-6 usw., wodurch:

y = y ^ (y >> 4) (unter Berücksichtigung von Bits höherer Ordnung)

Erneute Überlappung der Sätze (und Gruppierung von ? s für Lesbarkeit):

y = y ^ (y >> 8) (unter Berücksichtigung aller 32 Bits):

Auch hier werden überlappende Mengen vernachlässigt:

y = y ^ (y >> 16)

return y & 1

Sie können also sehen, dass der zurückgegebene Wert nur das Paritätsbit P31-0 für die Bits des Arguments x ist, was wir wollten.