Information Technology Reference
In-Depth Information
I
of synthesis scheme, where
L
max
denotes
maximum permissible length
of the
attractor cycle.
1 1 1 0
1 1 1 0
1 1 0 1
0 1 1 1
1 1 0 1
0 1 1 1
1 0 1 1
1 0 1 1
1 1 1 1
1 1 1 1
Cycle Length =
1
Cycle Length =
2
Present State
1 1 1 0
Next State
Present State
1 1 1 0
Next State
1 0 1 1
1 0 1 1
1 0 1 1
1 0 1 1
1 1 0 1
0 1 1 1
1 0 1 1
1 1 1 1
1 1 0 1
0 1 1 1
1 0 1 1
1 1 1 1
1 0 1 1
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 0 1 1
Neighborhood:
Next State
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
Neighborhood:
Next State
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
*
0 / 1
0
1
*
0
*
*
*
0
0
1
*
0
*
*
'Collision'
'No Collision'
Fig. 6.
Example of Cycle Length Increment of a Directed Graph
Scheme 1 : Reduction of the cycle length of a given graph
In this
case, we reduce the attractor cycle length of a given graph. The
Fig.5
illustrates
an example of this technique along with the state transition table and next state
function. In
Fig.5
, when the cycle length of the graph is 4, there is a 'collision'
between state '0' and '1' for '111' configuration of 3
rd
cell; whereas when the
cycle length is reduced from 4 to 3, there is no 'collision' for same configuration.
Scheme 2 : Increment of the cycle length of a given graph
In this
case, we increase the cycle length of a given graph. The
Fig.6
illustrates an
example of this technique. When cycle length of the given graph is 1, there is
a 'collision' between state '0' and '1' for '111' configuration of 2
nd
cell; whereas
when the cycle length is incremented from 1 to 2, the 'collision' disappears.
In
Schemes 1
and
2
, we change the state transition table by changing the
cycle length of the given graphs. As a result, the collision between state '0' and
'1' of a particular configurations of a cell is changed. Consequently, the
cost
function
is also changed.
The cost value is evaluated from
Equation -2
. There are two types of solution
based on cost value - Best Solution(
BS
) and Current Solution(
CS
). A New
Solution(
NS
) at immediate next
Temp
point
compares its cost value with
CS
.If
NS
has better cost value than
CS
, then
NS
becomes
CS
. The new solution(
NS
)
is also compared with
BS
and if
NS
is better, then
NS
becomes
BS
.Evenif
NS
is not as good as
CS
,
NS
is accepted with a probability. This step is done
typically to avoid any local minima. The complete algorithm is presented below:
