A minimization problem in systems characterized by acyclic signal flow graphs
Clarence Earl Endy, Pen-Min Lin · IEEE Transactions on Circuits and Systems · 1981
It is well known that some stochastic systems (e.g., semiMarkov systems) can be modeled by signal flow graphs. For such systems time-domain, transform, and simulation methods are available for analysis. The time-domain method has not been popular because of the requirement for numerous convolutions and deconvolutions, which are very timeconsuming and subject to error propagation. In this paper a method of minimizing the number of multiplications required to evaluate the symbolic gain expression for an acyclic signal flow graph is presented. For stochastic systems these multiplications correspond to time-domain convolutions. The method requires an N! search, where N is the number of internal nodes of the signal flow graph. To avoid this N! search a heuristic algorithm is implemented in a computer program (Symbolic Analysis-Minimal Multiplications (SAMM)) and examples of its application to semi-Markov systems are discussed.