Date: Jan 7, 2014 2:40 AM
Author: acd
Subject: Equivalence relation on Boolean vectors

I have recently completed some work on 
configurable circuits for rotationally symmetric Boolean functions.

That means functions, such that
if x is equivalent with y
f(x) = f(y).

x and y are equivalent if x can be cyclically shifted into y:
x=(x_1,x_2,...x_n)
y = (x_k,...x_n,x_1,..x_k-1)

This has the consequence that the input space {0,...,2^n-1}
is divided into classes of roughly n elements (the necklace problem
has the details).

To test my circuit generation approach further I would like
to use a different equivalence relation, that is neither based on
"arithmetic" nor on bit permutations, and which has larger equivalence classes,
something like 2^(n/2).

With "arithmetic" I mean something like
x mod h
where h = 2^(n/2).

Any ideas?

Andreas