# Re: Orientation of rotationally invariant bit vectors

*From*: Gene <gene.ressler@xxxxxxxxx>*Date*: Tue, 16 Oct 2007 02:49:51 -0000

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.

.

**Follow-Ups**:

**References**:

- Prev by Date:
**Re: Orientation of rotationally invariant bit vectors** - Next by Date:
**Re: Orientation of rotationally invariant bit vectors** - Previous by thread:
**Re: Orientation of rotationally invariant bit vectors** - Next by thread:
**Re: Orientation of rotationally invariant bit vectors** - Index(es):