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.

.



Relevant Pages

  • Re: Orientation of rotationally invariant bit vectors
    ... Since applying a rotation and a reflection in sequence is equivalend ... the two equivalence classes are different. ... reflectas a side effect while computing h1, ...
    (comp.theory)
  • 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. ... it is a n-bit to 1-bit function. ...
    (comp.theory)
  • 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: 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)