© The Institution of Engineering and Technology
A switch, mechanical or electrical, is a fundamental building element of digital systems. The theory of switching networks, or simply circuits, dates back to Shannon's thesis (1937), where he employed Boolean algebra for reasoning about the functionality of switching networks, and graph theory for describing and manipulating their structure. Following this classic approach, one can deduce functionality from a given structure via analysis, and create a structure implementing a specified functionality via synthesis. The use of two mathematical languages leads to a 'language barrier' – whenever a circuit description is changed in one language, it is necessary to translate the change into the other one to keep both descriptions synchronised. This work presents a unified algebra of switching networks. Its elements are circuits rather than just Boolean functions (as in Boolean algebra) or vertices/edges (as in graph theory). This approach allows one to express both the functionality and structure of switching networks in the same mathematical language and brings new methods of circuit composition for greater reuse of components and interfaces. In this paper we demonstrate how to use the algebra to formally transform circuits, reason about their properties, and even solve equations whose 'unknowns' are circuits.
References
-
-
1)
-
14. Liu, T.J.K., Jeon, J., Nathanael, R., Kam, H., Pott, V., Alon, E.: ‘Prospects for MEM logic switch technology’. IEEE Int. Electron Devices Meeting (IEDM), 2010, 2010, pp. 18–23.
-
2)
-
26. Milner, R.: ‘Communicating and mobile systems - the Pi-calculus’ (Cambridge University Press, 1999).
-
3)
-
28. van der Aalst, W.M.P., Adriansyah, A., van Dongen, B.F.: ‘Causal nets: a modeling language tailored towards process discovery’. Int. Conf. on Concurrency Theory (CONCUR), 2011, pp. 28–42.
-
4)
-
22. van Berkel, K., Kessels, J., Roncken, M., Saeijs, R., Schalij, F.: ‘The VLSI-programming language Tangram and its translation into handshake circuits’. Proc. European Conf. on Design Automation (EDAC), 1991.
-
5)
-
37. Walker, J.A., Trefzer, M.A., Bale, S.J., Tyrrell, A.M.: ‘PAnDA: a reconfigurable architecture that adapts to physical substrate variations’, IEEE Trans. Comput., 2013, 62, (8), pp. 1584–1596 (doi: 10.1109/TC.2013.59).
-
6)
-
10. Berge, H.K.O., Hasanbegovic, A., Aunet, S.: ‘Muller C-elements based on minority-3 functions for ultra low voltage supplies’. IEEE Int. Symp. on Design and Diagnostics of Electronic Circuits Systems (DDECS), April 2011, pp. 195–200.
-
7)
-
T. Murata
.
Petri nets properties, analysis and applications.
Proc. IEEE
,
4 ,
541 -
580
-
8)
-
30. Esparza, J.: ‘Decidability and complexity of Petri net problems – an introduction’, Lect. Petri Nets I, Basic Models, 1998, pp. 374–428 (doi: 10.1007/3-540-65306-6_20).
-
9)
-
5. Bryant, R.E.: ‘Algorithmic aspects of symbolic switch network analysis’, IEEE Trans. CAD Integr. Circuits, 1987, 6, pp. 618–633 (doi: 10.1109/TCAD.1987.1270309).
-
10)
-
S. Borkar
.
Designing reliable systems from unreliable components: the challenges of transistor variability and degradation.
IEEE Micro
,
6 ,
10 -
16
-
11)
-
34. Bizjak, A., Bauer, A.: ‘Alg user manual’ (Faculty of Mathematics and Physics, University of Ljubljana, 2011).
-
12)
-
8. Savage, J.E.: ‘Models of computation – exploring the power of computing’ (Addison-Wesley, 1998).
-
13)
-
29. Hoare, T., van Staden, S., Möller, B., et al: ‘Developments in concurrent Kleene algebra’, 2014, pp. 1–18.
-
14)
-
A. Mokhov ,
A. Yakovlev
.
Conditional partial order graphs: Model, synthesis and application.
IEEE Trans. Comput.
,
11 ,
1480 -
1493
-
15)
-
23. Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: ‘Logic synthesis of asynchronous controllers and interfaces’. (Springer-Verlag, 2002).
-
16)
-
19. Ciletti, M.D.: ‘Advanced digital design with the VERILOG HDL’ (Prentice-Hall PTR, 2002). .
-
17)
-
33. Mokhov, A., Khomenko, V.: ‘Algebra of parameterised graphs’, ACM Trans. Embedded Comput., 2014, 13, (4s).
-
18)
-
38. Mokhov, A., Rykunov, M., Sokolov, D., Yakovlev, A.: ‘Design of processors with reconfigurable microarchitecture’, J. Low Power Electron. Appl., 2014, 4, (1), pp. 26–43 (doi: 10.3390/jlpea4010026).
-
19)
-
16. Mokhov, A., Sokolov, D., Yakovlev, A.: ‘Adapting asynchronous circuits to operating conditions by logic parameterisation’. Int. Symp. on Asynchronous Circuits and Systems (ASYNC), 2012, pp. 17–24.
-
20)
-
17. Yakovlev, A.: ‘Energy-modulated computing’. Design Automation and Test in Europe (DATE) Conf., 2011, pp. 1340–1345.
-
21)
-
2. Shannon, C.E.: ‘The synthesis of two-terminal switching circuits’, Bell Syst. Tech. J., 1948, 28, pp. 59–98 (doi: 10.1002/j.1538-7305.1949.tb03624.x).
-
22)
-
7. Mead, C., Conway, L.: ‘Introduction to VLSI systems’ (Addison-Wesley, 1980).
-
23)
-
27. Josephs, M.B., Udding, J.T.: ‘An overview of D-I algebra’. Proc. of the 26th Hawaii Int. Conf. on System Sciences, 1993, vol. 1, pp. 329–338.
-
24)
-
36. Bjerkedok, J.E.: ‘Subthreshold real-time counter’. , Norwegian University of Science and Technology, Norway, 2013.
-
25)
-
4. Hohn, F.E., Schissler, L.R.: ‘Boolean matrices and combinational circuit design’, Bell Syst. Tech. J., 1955, (34), pp. 177–202 (doi: 10.1002/j.1538-7305.1955.tb03767.x).
-
26)
-
3. Huffman, D.A.: ‘The synthesis of sequential switching circuits’, J. Franklin Inst., 1954, 257, (3), pp. 161–190 (doi: 10.1016/0016-0032(54)90574-8).
-
27)
-
31. Mokhov, A.: ‘Conditional partial order graphs’. , Newcastle University, 2009.
-
28)
-
39. De Marchi, M., Sacchetto, D., Frache, S., et al: ‘Polarity control in double-gate, gate-all-around vertically stacked silicon nanowire fets’. IEEE Int. Electron Devices Meeting (IEDM), 2012, 2012, pp. 8–14.
-
29)
-
1. Shannon, C.E.: ‘A symbolic analysis of relay and switching circuits’, Trans. Am. Inst. Electr. Eng., 1938, 57, pp. 713–723 (doi: 10.1109/T-AIEE.1938.5057767).
-
30)
-
40. Mokhov, A., Alekseyev, A., Yakovlev, A.: ‘Encoding of processor instruction sets with explicit concurrency control’, IET Comput. Digital Tech., 2011, 5, (6), pp. 427–439 (doi: 10.1049/iet-cdt.2010.0158).
-
31)
-
S.J. Tans ,
A.R.M. Verschueren ,
C. Dekker
.
Room-temperature transistor based on a single carbon nanotube.
Nature
,
6680 ,
49 -
52
-
32)
-
R.E. Bryant
.
Boolean analysis of MOS circuits.
IEEE Trans. Comput.-Aided Des.
,
4 ,
634 -
649
-
33)
-
11. Renaudin, M., Bouesse, G.F., Proust, Ph., Tual, J.P., Sourgen, L., Germain, F.: ‘High security smartcards’. Proc. of the Conf. on Design, Automation and Test in Europe (DATE), 2004, pp. 228–233.
-
34)
-
35. Chen, W.: ‘Boolean matrices and switching nets’. Mathematics Magazine, January 1966, pp. 1–8.
-
35)
-
C.A.R. Hoare
.
Communicating sequential processes.
Commun. ACM
,
8 ,
666 -
676
-
36)
-
20. Lipsett, R., Ussery, C.A., Schaefer, C.F.: ‘VHDL, hardware description and design’ (Kluwer Academic Publishers, 1993). .
-
37)
-
21. Bardsley, A., Edwards, D.: ‘The Balsa asynchronous circuit synthesis system’. Forum on Design Languages, 2000.
-
38)
-
18. Xia, F., Mokhov, A., Zhou, Y., et al: ‘Towards power-elastic systems through concurrency management’, IET Comput. Digital Tech., 2012, 6, (1), pp. 33–42 (doi: 10.1049/iet-cdt.2010.0091).
-
39)
-
13. Liu, T.-J.K., Markovic, D., Stojanovic, V., Alon, E.: ‘MEMS switches for low-power logic’. IEEE Spectrum, April 2012.
-
40)
-
24. Spencer, M., Chen, F., Wang, C.C., et al: ‘Demonstration of integrated micro-electro-mechanical relay circuits for VLSI applications’, IEEE J. Solid-State Circuits, 2011, 46, (1), pp. 308–320 (doi: 10.1109/JSSC.2010.2074370).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2014.0135
Related content
content/journals/10.1049/iet-cdt.2014.0135
pub_keyword,iet_inspecKeyword,pub_concept
6
6