On Boolean Techniques for Non Touching Loops of Signal Flow Graphs
- PDF / 348,525 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 45 Downloads / 141 Views
On Boolean Techniques for Non Touching Loops of Signal Flow Graphs V.C. Prasad
Received: 13 February 2012 / Revised: 30 August 2012 / Published online: 12 September 2012 © Springer Science+Business Media, LLC 2012
Abstract Vertex disjoint (non touching) loops have to be processed to form all combinations of disjoint loops for Mason’s graph. Similarly Coates’ graph-based method needs all spanning disjoint loop sets. This is required to obtain the transfer function/solve equations of a system represented by Mason’s/Coates’ signal flow graph. A Boolean formula is presented in this note to obtain them. A Boolean function is formed comprising product of sums of pairs of touching loops for each connected component. It is then simplified using some rules of Boolean algebra. The resulting terms are “complemented” to derive all combinations of non touching loops for a Mason’s graph. Using an additional Boolean rule, the same formula gives all spanning disjoint loop sets of a Coates’ graph. The graph need not be connected. Keywords Signal flow graphs · Boolean algebra · Disjoint loops · Mason’s graph · Coates’ graph 1 Introduction A signal flow graph is a popular representation of a system [1–6, 8, 9]. Symbolic analyses of electronic circuits for transfer functions, control systems and signal processing are some of the innumerable areas of applications of signal flow graphs in electrical engineering alone. Other branches of engineering and science also use these graphs extensively. Two types of graph called Mason’s graph and Coates’ graph are widely known. They are used to represent linear algebraic equations in the form of V.C. Prasad is retired from Indian Institute of Technology, New Delhi, India. V.C. Prasad () Faculty of Engineering, Dayalbagh Educational Institute, Dayalbagh, Agra 282005, India e-mail: [email protected] V.C. Prasad e-mail: [email protected]
1444
Circuits Syst Signal Process (2013) 32:1443–1453
a graph. A variable xj is represented by a node. A node x2 is connected to a node x1 by a directed edge of weight w from x2 to x1 if x1 depends linearly on wx2 . In Mason’s graph, the equation x1 = w1 x1 + w2 x2 + · · · + wn xn is represented by a self loop of w1 at x1 and an edge from xj to x1 with weight wj . If wj = 0, there is no edge. This is done for all j = 2 . . . n. In Coates’ graph, the self loop at x1 will have weight (w1 − 1). It is the same as in Mason’s graph for other nodes. The graph at node x1 represents the equation (w1 − 1)x1 + w2 x2 + · · · + wn xn = 0. Figure 1 is an example of a Mason’s graph. C = a6 x5 + a16 x10 , x5 = a5 x4 + a14 x9 + a15 x14 are two of its equations. Figure 3 is an example of a Coates’ graph. Its equations are given in Example 2. Mason and Coates [1, 2, 8] derived topological formulas to solve these equations. Their formulas use directed circuits of the respective graphs. This paper also deals with these directed circuits. Mason’s formula is widely used to derive the transfer function of a system. It states that the transfer function of a system represen
Data Loading...
