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