Decomposition of a parallel automaton into a net of sequential automata and low power state assignment of them at asynchronous implementation

Abstract

Objectives. The problems of decomposition of a parallel automaton into a net of sequential automata at synchronous realization and low power race free state assignment of them are considered. The objective of the paper is to investigate the possibilities of applying decomposition in state assignment of partial states in order to decrease the problem dimension taking into account the peculiar properties of the asynchronous realization.Methods. The given parallel automaton is decomposed into a net of sequential asynchronous automata whose states are assigned then with ternary vectors. The power consumption lowering of the designed device is achieved by lowering the intensity of its memory elements switching that is appreciated by probabilities of transitions between the states of the automaton. The state assignment is reduced to the problem of minimal weighted cover. The probabilities of transitions between sets are calculated by means of solving a system of linear equations according to the Chapmann – Kolmogorov method.Results. A method to construct a net of sequential asynchronous automata that realizes the given parallel automaton is described. The paper touches upon the problem of minimization of interconnections in the net.Conclusion. Applying parallel automaton decomposition allows decreasing the dimension of the laborious problem of state assignment. The proposed method is intended for application in computer aided systems for design of discrete devices.

Keywords

• parallel automaton
• partial state
• decomposition of automata
• state assignment of automata
• probability of transition between states
• weighted cover