How to describe Transition Function of ...

[khorram]

Hi all,

I am looking for a technique that explains how I can describe the Transition Function of a system which has the following property:
A transition from present state to next state exists if hamming distance between two states is 1.

Best Regards,
KH

 

[kishore2k4]

I remember very little but there is way to split the function into states and then transform it, later which can be cobined using some producedure I can't remember. For example:

Say Y is the output of your transfer function which is dependent on x, hamming distance.

Therefore,

Y= f(x); when x = 1,
Y= 0; when x != 1;

I know its not much help but thats all that is left in my head related to your question.

 

[khorram]

Hi my friend,

Thanks for your reply.

Let me explain the problem in a more detail.
Problem Definition: Suppose you have an FSM so that there will be a transition from current state to the next state if hamming distance between those states is 1.

Goal: How I can describe such a FSM in word level (not Boolean expressions) for example in C.

Let N indicates the number of bits. The first state is 0...00, where all bits are 0. we call it LEVEL=0. In LEVEL=1, we list all states that only one of their bits is 1 (00...01; 00...10; etc). Similarly LEVEL=2 presents all states that have two 1's and LEVEL=N indicates 11...11 (all bits are 1). The problem is how we can describe the transition between LEVEL=i and LEVEL=i+1, while at each node we have to know what bits are 1.

I was wondering if someone could help me to figure out a suitable algorithm. The main problem is to keep what bits are 1 at each state of a given LEVEL.

Regards,
KH

 

[tzushky]

I was just thinking, and it might be wrong...but the difference of just 1 bit between two states is actually 2 to the power of the position which is different.

The thing I haven't proven is that the sum of the other positions that are different in case there's more than one, is never a perfect power of 2... now is that true? don't know for sure yet....

The thing is that it would mean calculating the decimal equivalent of the word bits, don't know if that works for you either.... And also it would mean calculating all differences between 2^N words... looong algorithm

Otherwise, a very basic soloution is simply looking at them as arrays and comparing, but it's some imbricated "for"'s u need...

I'll be thinking some more

Regards,

Tzushky

Added after 5 minutes:

I'm wrong... forget that ( if you have N=3 and look between level 2 and 1, 011 and 100 you get decimal difference 1 and Hamming distance 3, what I said is completely dumb, should have never wrote it....)

I don't see anything except treating them as arrays..., couting the elements that are different, when larger than one transition is 0, when equal to 1 transition is 1... It's just a lot of comparing..

and how do you generate the levels? The binary words?

 

[khorram]

Hi,

Thanks for your replay.

As I said before, the maon problem is how we can keep a trace of bits have been 1. If we can keep them (as you mentioned, if we consider an array we have to decalre an array that has 2^N elements!! which is actually impossible) in a linear form (that doesn't grow exponentially) we have already done it.

The algorithm is simple, we subtract StateNumber from 2^j (for j=0 to N-1). If the new StateNumber has not generated yet, we define a new state. otherwise we do nothing.

I am looking forward to hearing from you all, who are expert in ALGORITHM as well as MATHEMATICS

Best Regards,
KH