Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

How to describe Transition Function of ...

Status
Not open for further replies.

khorram

Full Member level 4
Joined
Oct 27, 2004
Messages
212
Helped
13
Reputation
26
Reaction score
1
Trophy points
1,298
Activity points
1,892
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

Full Member level 5
Joined
Jun 17, 2006
Messages
296
Helped
44
Reputation
88
Reaction score
10
Trophy points
1,298
Location
Middle Earth
Activity points
3,295
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

Full Member level 4
Joined
Oct 27, 2004
Messages
212
Helped
13
Reputation
26
Reaction score
1
Trophy points
1,298
Activity points
1,892
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

Member level 3
Joined
May 21, 2007
Messages
63
Helped
10
Reputation
20
Reaction score
0
Trophy points
1,286
Location
Sophia-Antipolis,France
Activity points
1,819
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

Full Member level 4
Joined
Oct 27, 2004
Messages
212
Helped
13
Reputation
26
Reaction score
1
Trophy points
1,298
Activity points
1,892
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
 

Status
Not open for further replies.

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top