
7. ADDITIVE DECOMPOSITION
Assume that we are given a Mealy type automaton and the partition. To illustrate each step of decomposition with an example, we will use some defined automaton A, and partition
Let put network N with
n component automata in accordance to pair.
The number of component automata is equal to the number of blocks in the partition .
So, in our example there will be two
component automata A^{1 }and A^{2}, since there
are two blocks (B^{1} and B^{2}) in the partition .
7.2. Definition of States in Component Automata
First, define set of states in component automata as:
Let define states of component automata
in our example:
C^{1} = (s_{1}, s_{2},
s_{3}, c_{1}}
C^{2} = {s_{4}, s_{5},
s_{6}, c_{2}}
7.3. Set of Input and Output Variables
To define inputs and outputs of component automaton let put sets X(B^{m}), Y(B^{m}), G^{m}, T^{m}, Q^{m} in accordance to each block of the partition :
Now we can define the set of input vaiables X^{m}:
In our example:
{w_{1}}
{w_{5}, w_{6}}
Similarly, we define the set of output variables Y^{m}:
Here is the set of additional output variables which connect the automaton Am with other component automata. To define let put the additional output variable w_{i }in accordance to each state in set T^{m}. So, the number of elements in is equal to the number of states in T^{m}:
In our example:
{w_{5},
w_{6}}
{w_{1}}
In other words states Q^{m}
and T^{m} define the sets of additional input ()
and output ():
if
then and
if
then
7.4. Definition of Transition and Output Functions
Let
be transition in the automaton A. Now we will define transition and output functions in the component automata.
a) If (s_{i} and s_{j} are states of the same component automaton A^{m}), then
is the transition in component automaton A^{m}b) If (s_{i} and s_{j} are states of two different component automata A^{m} and A^{p }). Then, the component automaton A^{m }transits from state s_{i }to the additional state c_{m} with the output Y_{t} and additional output w_{j} :
How transitions in automaton A are defined in component automata showed on the figure below:
7.5. Reduced Procedure of Decomposition
The procedure of decomposition can be reduced to:
a) copiying row s_{i}, s_{j} , X(s_{i}, s_{j}), Y(s_{i}, s_{j}) from the table of the automaton A to the table of component automaton A^{m} , if s_{i} and s_{j} are the states of A^{m}.7.6. Result of Decomposition
b) the replacement of the row s_{i}, s_{j},X(s_{i}, s_{j}), Y(s_{i}, s_{j}) in the table of automaton A by the row s_{i}, c_{m} X(s_{i}, s_{j}) Y(s_{i}, s_{j})w_{i} in the table of component automaton A^{m} and the row c_{p }, a_{j} , w_{j} in the table of component automaton A^{p}, s_{i} is the state of A^{m} and s_{j} is the state of A^{p}; mp.
c) adding row c_{m}, c_{m} to the transition table of component automaton A^{m}.
As result of decomposition of our sample automaton A we obtain the network N with two component automata A^{1} and A^{2} :
Also we can build transition tables of each component automaton:
Note: If there three or more signals in additional input (output) signals, then it is reasonable to code them by binary values. For example, to variables u_{1} and u_{2} are sufficient for coding four inputs w_{i}, w_{j}, w_{k} and . Also zeronumber state (s_{0}) may be used to represent additional states (c_{i}) in each of component automata.
Last update: 3 August, 2004