Java Applet on Additive Decomposition

Start the applet


Applet demonstrates additive decomposition, wherein the graph of the FSM is partitioned into node disjoint subsets. The network of interacting sub-FSMs corresponds to a given partition on the set of states of source FSM. The network of FSMs consists of components working alternatively in time, i.e. all components except one are suspended in one of extra state (the “wait” state). This property gives opportunity to apply sleep mode operation (dynamic power management) for saving power consumption.


Prototype FSM model

Formally, FSM is a quintuple < S, X, Y, , > where

Example Prototype FSM

  • S= { s1 , s2 , … , s8 }
  • X= { x1, x2 , … , x8 }
  • Y= { y1 , y2 , … , y14 }

FSM description

Decomposition procedures


The set of states of (component) sub-FSM

Define set of states in component automata as:

Bm- is the block of the partition ,
am - is the additional state that exists in each component automata.

Let define states of component automata in our example:

S={ s1 , s2 , … , s8 }
={ { s1, s4, s7 }, { s2 , s3, s6 }, { s5 , s8 } }

S1 = { s1, s4, s7, a1 }
S2 = { s2, s3, s6, a2 }
S3 = { s5, s8, a3 }

Set of external input variables

X(Bm) is the set of external input variables at all transitions from the states of block Bm in the transition table of the prototype FSM A:

In our example:
X(B1) = { x1, x2, x3 }
X(B2) = { x5, x7, x8 }
X(B3) = { x4, x6 }

={ { s1, s4, s7 }, { s2 , s3, s6 }, { s5 , s8 } }

Set of external output variables

Y(Bm) is the set of external output variables at all transitions from the states of block Bm in the transition table of the FSM A:

In our example:
Y(B1) = { y3, y4, y7 }
Y(B2) = { y2, y5, y10, y11, y12 }
Y(B3) = { y6, y8, y9, y13, y14 }


Example FSM parameters

Component FSMs B2 and B3

FSM Network

Additional theory is available here or here



WARNING: This page contains links to PDF files of articles that may be covered by copyright. You may browse the articles at your convenience. (in the same spirit as you may read a journal or a proceeding article in a public library). Retrieving, copying, or distributing these files, however, may violate the copyright protection law. We recommend that the user abides international law in accessing this directory.

  1. M. Kruus, H. Lensen, and A. Sudnitson, “Web-Based Tools for Decomposition-Oriented Digital Design”, in Proc. 1st International Congress on Mechanical and Electrical Engineering and Technology (MEET/MARIND’2002), Varna, Bulgaria, 2002, v.1, pp. 261-266. (ISBN: 954-20-0211-4)
  2. S. Devadze, M. Kruus, and A. Sudnitson, “Web-Based Software Implementation of Finite State Machine Decomposition for Design and Education”, in Proc. International Conference on Computer Systems and Technologies (CompSysTech’2001), Sofia, Bulgaria, 2001, v.4, pp. 1-7. (ISBN: 954-9641-25-2)
  3. A. Jutman, M. Kruus, A. Sudnitson, and R. Ubar “Distance-Learning Tools for Digital Design and Test Issues”, in Proc. 29th International Conference on Information Technologies in Science, Education, Telecommunication, Business (IT+SE’ 2002), Gurzuf, Ukraine, 2002, pp.269-272.
  4. S. Devadze, E. Fomina, M. Kruus, and A. Sudnitson, “Web-Based System for Sequential Machines Decomposition”, in Proc. IEEE EUROCON 2003 International Conference on Computer as a Tool, Ljubljana, Slovenia, 2003, V. 1, pp. 57-61. (ISBN: 0-7803-7763-X, IEEE Catalog No.: 03EX665)

Back to List

Last update: 3 August, 2004