Author: Gerd Isenberg
Date: 14:14:41 06/23/04
Hi all,
first, congrats to Netherlands and Czechia!
Condolences to Germany ;-( and the very unlucky Italy.
I played a bit with parity words and for some reason thought about a inverse
function. The solution was new to me and surprisingly simple. Imagine following
mod2 or bitwise matrix operation to build a 32-bit parity word (or is there any
other term for that?):
x0 = x0
x1 = x1 ^ x0
x2 = x2 ^ x1 ^ x0
x3 = x3 ^ x2 ^ x1 ^ x0
......
x31 = x31 ^ x30 ^...^ x3 ^ x2 ^ x1 ^ x0
It may be computed parallel prefix wise with five "xor" and "shift"
instructions:
x ^= x<<1;
x ^= x<<2;
x ^= x<<4;
x ^= x<<8;
x ^= x<<16;
Some bit(i) of the parity word indicates whether there is an odd or even number
of ones from bit i (including) until the least significant bit, zero.
"Surprisingly" one additional
x ^= x<<1;
is the inverse function of the above instruction sequence and restores the
initial x. A circle - 64-bit words require one additional x ^= x<<32.
One application of parity words is building de Bruijn sequences N from N-1, eg.
64 from 32:
deBruijn32: 0x04653adf
parity: 0x03dce9b5
~parity: 0xfc23164a
insert[1]: 0x03dce9b4 1
1f8462c94
deBruijn64: 0x03dce9b5f8462c95 (for that special case)
A 32-bit de Bruijn sequence with 5 leading binary zeros and 16 ones, resets bit
32-6 due to the even parity, but sets bit 32-7 due to odd parity because 32-6
was set before. The set bit 0 leaves unchanged.
Now a 64 bit de Bruijn sequence may be build by inserting the inverted (and
rotated) bits of the parity word somehow in the "middle" (1..27) of the parity
word, leaving six leading zeros as seen in the above example.
Other applications?
Cheers,
Gerd
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.