Java Applet on Multiplicative Decomposition

Start the applet

INTRODUCTION

Applet is devoted to general method of decomposition of FSM and enables synthesis of the network of interacting sub-FSMs corresponding to a complete set of partitions on the set of states of source FSM. We call this method of decomposition as multiplicative decomposition, because the graph of the prototype FSM is embedded into a product of smaller graphs. The brief list of other features provided by applet includes: partitions search by specified criteria, random generation of set of partitions, import and export of FSM/Network (various formats are supported), built-in libraries of FSMs, steady-state probabilities computation. The applet could be considered not only as educational system but also as a research tool that we are able to use to carry out experiments guided to further development of decomposition synthesis.

SHORT THEORETICAL BASICS

It is not an overstatement to tell that the decomposition task is one of the most intricate and actual problems at complex discrete devices synthesis. Commonly, the FSM decomposition task is representing of prototype FSM as its network realization. It means that, we construct such network of interconnecting and interacting component automata that it must realizes the work of source FSM.

Let p_i be the state partition inducting state decomposition on machine A. For each p_i, there is an associated FSM, A_i=<S_i, X_i, Y_i, d_i, l_i> where d_i and l_i is the partitioned next state and output functions consequently.  The primary inputs are shared by the A_i’s and the communication among A_i’ is through state variables. The set (A_i | iÎI=(1, …, n)) of all the sub-FSM’s A_i’s represents the decomposed network of FSM’s obtained from the original machine A when its set of states is decomposed according of p_i.

As mentioned above, on the set of states S of the source original FSM A we choose a set of state partitions p_i. Next we define some information partitions which are induced on A by a network that defines A. These “associated” partitions on A may be thought of as a global characterization (on A) of the information used and computed in a component machine of network. It is natural correspondence between local and global properties that allows us to approach the structure of machines with partition pair algebra.

The main condition of general FSM’s decomposition is equality to zero of product of all selected partitions on the set of the states of the FSM. These partitions are called complete set of partitions. From informational point of view, while a partition on the set of states of source FSM is some measure of information about corresponding component sub-FSM, the zero partition on the set of states of decomposed FSM contains complete information about it. 

The procedure of decomposition described in this section is based on the general form of decomposition without the restriction on their interconnection. Each sub-machine corresponds to a partition on the set of state. The procedure is illustrated on example of decomposition of the machine described by Table 1. Next we illustrate general description of main steps of the procedure.

Present state (sp­)	Input condition αpq	Next state sq	Output signal βpq
1	x1^x2	1	y1y2
	^x1^x2	3	y2
	^x1x2	5	y5
	x1x2	6	y1
2	x2	2	y2y6
	^x2	7	y5
3	x4	1	y3
	^x4^x5	4	y3y4
	^x4x5	7	y4
4	x3	3	y2y5y6
	^x3	5	y5
5	x6	5	y7
	^x6	9	y7
6	x1x3	7	y5y6
	^x1x3	8	y5
	^x3	9	y6
7	x2	8	y2
	^x2	9	y1y6
8	x5	3	y3y4
	^x5	8	y4
9	x6	1	y7
	^x6	7	y3y4y7

Table 1.State Transition Table of example FSM

Choosing a system of partitions on the set of states of FS

On this step of the decomposition procedure we select a complete set of partitions on the set of states. In our example the set of partitions will be the following:

Let us label the blocks of partition p₁ by a₁, a₂, a₃ and the blocks of partition p₂ by b₁, b₂, b₃, b₄ correspondingly.

Coding of the network

The coding of the network (global states of the net) gives us a set of internal binary variables of the network Z. Consider a set of states S and an encoding function e: S{0, 1}^c, for a given c (encoding length), that to each symbol sS a code, i.e., a binary vector of length c. A necessary requirement is that different symbols are mapped to different binary vectors. Given a set of symbols S, a face constraint is a block BS in the partition specifying that the symbols in B are to be assigned to one face (or sub-cube) of a binary c-dimensional cube, without any other symbol sharing the same face. So, face constraints are generated by step of partition search, c is the number of internal binary variables of the net, |Z|. Every variable zZ corresponds to some two-block partition on S. Let the binary internal state variable zⁱ_j be produced by the sub-machine A_i. Then zⁱ_j is a state variable of sub-machine A_i and corresponds to the two-block partition hⁱ_j. One of the blocks of hⁱ_j is coded by 0, the other one by 1. In this step we decide an combinatorial problem called face hypercube embedding [3], to find the minimum c and related e: S{0, 1}^c such that face constraints are satisfied i.e., h_ijp_i.

The internal binary variables for FSM’s network are:

;   h¹₁ ~ z₁

;   h¹₂ ~ z₂

;   h²₁ ~ z₃

;   h²₂ ~ z₄

We suppose that the first block of two-block partition corresponds to the value of internal binary variable equal to 1 and the second block corresponds to 0. For instance, if z₁=1, than it means that global state s_p the network contains in the first block of partition h¹₁, i.e., s_pÎ{1,3,5,6}. In this example two-blocks hⁱ_j partitions were constructing by trivial combining of blocks of corresponded p_i partitions, since the optimal algorithm of search for optimal solution of coding problem is beyond of the bounds of this work.

Determining of the structure of the network

To determine the structure of the network the M(p_i) partitions should be found for each of p_i partitions. In our example:

So M(p₁) h¹₁×h²₁×h²₂. It means that z₁ is the state variables and z₃, z₄ are the input variables of the first sub-FSM

Bp	apq(Bp, Bq)	Bq	βpq
a1	z3 z4	a1	-
	^z3 z4 x4	a1	y3
	^z3 z4 ^x4 ^x5	a3	y3 y4
	^z3 z4 ^x4 x5	a2	y4
a2	^z3 ^z4 x6	a1	y7
	^z3 ^z4 ^x6	a2	y7
a3	z3 ^z4	a2	-
	z3	a2	-
	^z3 z4 x5	a1	y3 y4
a4	^z3 z4 ^x5	a2	y4
	^z3 ^z4 x6	a1	y7
	^z3 ^z4 ^x6	a2	y3 y4 y7
	1	a1	-

Table 2. State Transition Table of constructed component FSM A

The second component sub-FSM can be constructed in the similar way.

Defining of the basis of the network

This step characterizes the basis of realization of the network. The set of states of component FSM Aⁱ is equal to the set of blocks of partition p_i. The internal inputs of component machines are defined at the previous step of procedure. The schematic representation of the constructed network is presented in Figure 1.

Figure 1. Schematic representation of the constructed network

APPLET MANUAL

LIST OF PUBLICATIONS:

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. S. Devadze, A. Jutman, M. Kruus, A. Sudnitson, and R. Ubar, “Web Based Tools for Synthesis and Testing of Digital Devices”, in Proc. International Conference on Computer Systems and Technologies (CompSysTech’2002), Sofia, Bulgaria, 2002, v.1, pp. 91-96. (ISBN: 954-9641-28-7)
2. E. Fomina, A. Keevallik, M. Kruus, and A. Sudnitson, “Web-based Tools for Finite State Machine Decomposition with Analysis of Information Flows”, in Proc. 8th International Baltic Electronics Conference ( BEC’2002), Tallinn, Estonia, 2002, pp. 165-168. (ISBN: 9985-59-292-1)
3. E. Fomina, A. Keevallik, M. Kruus, and A. Sudnitson, “A Decomposition Procedure for Register-Transfer Level Power Management”, in Proc. International Conference on Computer Systems and Technologies (CompSysTech’2003), Sofia, Bulgaria, 2003, v.1, pp.21-26. (ISBN: 954-9641-33-3)
4. A. Jutman, A. Sudnitson, R. Ubar, and H.-D. Wuttke, “Java Applets Support for an Asynchronous-Mode Learning of Digital Design and Test”, in Proc. 4th International Conference on Information Technology Based Higher Education and Training (ITHET 2003), Marrakech, Morocco, 2003, pp.397-401. (ISBN: 9954-8352-0-2)
5. A. Jutman, A. Sudnitson, and R. Ubar, “Digital Design Learning System Based on Java Applets”, in Proc. 4th Annual Conference of the LTSN Centre for Information and Computer Sciences, NUI Galway, Ireland, 2003, pp.183-187. (ISBN: 0-9541927-4-5)
6. 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)

---

Last update: 3 August, 2004