Re: Orientation of rotationally invariant bit vectors



On Oct 15, 8:13 am, acd <acd4use...@xxxxxxxx> wrote:
I am searching for two functions when characterizing equvalence
classes of n-bit bit vectors.

The equivalence classes are defined such that each class contains all
copies of a bit vector obtained by
rotation (cyclic shif).

For example, for n=6, we would have a class containing
010111, 101011, 110101, 111010, 011101, and 101110

I now apply also reflection, e.g.
010111 turns into 111010 (swap highest with lowest digit, second
highest with second lowest digit, ...)

For the example before, we reach the same equivalence class.

But for the class containing
010011 and its rotational equivalences, the reflection leads to a
different class.

I am investigating now two functions, one is unambiguous,
which tells for a given bit vector, whether the two equivalence
classes are equivalent.
Since applying a rotation and a reflection in sequence is equivalend
to a different reflection,
we can just check all reflections.
These are just the involutions of the dihedral group on n points,.

The second function will give an orientation bit in those cases where
the two equivalence classes are different.
In case they are equal the result does not matter.
So the function has the following properties:

it is a n-bit to 1-bit function.

It is rotationally invariant, i.e. for all k: f(v) = f(rot(v,k))
(rot(v,k) denotes the cyclic shift of v by k digits).

(f(v) = not f(reflect(v)) if there is no k, such that reflect(v) =
rot(v,k)

As a simple software implementation, I
calculated
h1 = min(v,rot(v,1),rot(v,2), ...) and
h2 = min(reflect(v),reflect(rot(v,1)),...)
the minimum was taken by interpreting the n-bit string as binary
encoded natural number.
However, this is quite expensive as a cicuit and I am wondering,
whether there are
cheaper ways to implement a function which gives the "orientation".

The problem is related to the "Necklace Problem", interpreted as the
action of a cyclic or dihedral group on words of length n.
It can be understood as considering regular polygons of n points,
where the points are colored,
and I want to know from which side I am looking at it.

I am interested in moderatly sizes of n, say up to 20.

Andreas

You said "circuit," so you are designing hardware? I guess this is
obvious: For n=20, both functions fit in a 256KB ROM.

.