Orientation of rotationally invariant bit vectors

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

.

Relevant Pages

  • Re: combinatorics problem
    ... >> equivalence classes by an equivalence relation ~. ... > Suppose that C is one of the equivalence classes, ... > as a sum of squares has exactly _one_ such representation. ... >> Snis Pilbor ...
    (sci.math)
  • Re: Orientation of rotationally invariant bit vectors
    ... The equivalence classes are defined such that each class contains all ... I now apply also reflection, ... we reach the same equivalence class. ... Since applying a rotation and a reflection in sequence is equivalend ...
    (comp.theory)
  • Re: Analysis with nonmeasurable set..
    ... There exists a nonmeasurable set in the interval [0,1). ... We define an equivalence relation '~' in the set I = [0,1) ... while those of the different classes differ by an irrational number. ... Suppose that is disjoint equivalence classes. ...
    (sci.math)
  • Re: Testing for the equivalence relation
    ... >> Here there are 4 equivalence classes and two distinct equivalence ... > There are just two equivalence classes. ... Abiteboul, Hull, and Vianu mention active domains in the context of query ...
    (comp.databases.theory)
  • Re: Generalized Equivalence Relations?
    ... > equivalence relation consists of a set of ordered pairs, is there ... product such as abc represents the composite of a reflection in a, ... Anyway, we say is in a certain ternary relation iff abc ... II "Geometry," Chapter 5. ...
    (sci.math)