Information Technology Reference
In-Depth Information
instance, in the chromosome (4.25) above, the arguments to the UDF are by
definition a and b , and by replacing “U” in the expression tree above by this
user defined XOR, we obtain:
A
O
O
O
d
A
N
c
A
A
d
O
c
O
N
A
A
A
a
c
b
A
A
O
d
O
N
a
a
c
b
b
A
O
N
d
a
a
b
b
A
a
b
Compare this solution with the following solution to the odd-4-parity func-
tion discovered using a normal XOR instead of a rigid, user defined XOR:
0123456
XXXbcad (4.26)
Nevertheless, UDFs are extremely useful, especially if they are carefully
crafted to the problem at hand, for they can help us in the discovery of pat-
terns in modular functions. The two problems we will be analyzing next
clearly illustrate this point.
Odd-parity Functions
When expressed in binary form, a number is said to have odd parity if it has
an odd number of 1's. And there is a class of so called odd-parity functions
which return “1” or “true” if an n -bit number is odd, “0” or “false” other-
wise. So, the simplest odd-parity function is the identity function of one
argument or the odd-1-parity function. Another simple and familiar odd-parity
Search WWH ::




Custom Search