access icon free Algebra of switching networks

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.

Inspec keywords: Boolean functions; graph theory; switching circuits

Other keywords: switching synthesis; graph theory; graph edge; switching circuits; switching structure; Boolean algebra; switching networks; graph vertex; Boolean functions; switching analysis; mathematical languages

Subjects: Algebra; Logic and switching circuits; Other analogue circuits; Combinatorial mathematics; Combinatorial mathematics; Algebra

References

    1. 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. 1823.
    2. 2)
      • 26. Milner, R.: ‘Communicating and mobile systems - the Pi-calculus’ (Cambridge University Press, 1999).
    3. 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. 2842.
    4. 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. 5)
    6. 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. 195200.
    7. 7)
    8. 8)
    9. 9)
    10. 10)
    11. 11)
      • 34. Bizjak, A., Bauer, A.: ‘Alg user manual’ (Faculty of Mathematics and Physics, University of Ljubljana, 2011).
    12. 12)
      • 8. Savage, J.E.: ‘Models of computation – exploring the power of computing’ (Addison-Wesley, 1998).
    13. 13)
      • 29. Hoare, T., van Staden, S., Möller, B., et al: ‘Developments in concurrent Kleene algebra’, 2014, pp. 118.
    14. 14)
    15. 15)
      • 23. Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: ‘Logic synthesis of asynchronous controllers and interfaces’. Advanced Microelectronics (Springer-Verlag, 2002).
    16. 16)
      • 19. Ciletti, M.D.: ‘Advanced digital design with the VERILOG HDL’ (Prentice-Hall PTR, 2002). ISBN: 0130891614.
    17. 17)
      • 33. Mokhov, A., Khomenko, V.: ‘Algebra of parameterised graphs’, ACM Trans. Embedded Comput., 2014, 13, (4s).
    18. 18)
    19. 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. 1724.
    20. 20)
      • 17. Yakovlev, A.: ‘Energy-modulated computing’. Design Automation and Test in Europe (DATE) Conf., 2011, pp. 13401345.
    21. 21)
    22. 22)
      • 7. Mead, C., Conway, L.: ‘Introduction to VLSI systems’ (Addison-Wesley, 1980).
    23. 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. 329338.
    24. 24)
      • 36. Bjerkedok, J.E.: ‘Subthreshold real-time counter’. Master's thesis, Norwegian University of Science and Technology, Norway, 2013.
    25. 25)
    26. 26)
    27. 27)
      • 31. Mokhov, A.: ‘Conditional partial order graphs’. PhD thesis, Newcastle University, 2009.
    28. 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. 814.
    29. 29)
    30. 30)
    31. 31)
    32. 32)
    33. 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. 228233.
    34. 34)
      • 35. Chen, W.: ‘Boolean matrices and switching nets’. Mathematics Magazine, January 1966, pp. 18.
    35. 35)
    36. 36)
      • 20. Lipsett, R., Ussery, C.A., Schaefer, C.F.: ‘VHDL, hardware description and design’ (Kluwer Academic Publishers, 1993). 9780792390305.
    37. 37)
      • 21. Bardsley, A., Edwards, D.: ‘The Balsa asynchronous circuit synthesis system’. Forum on Design Languages, 2000.
    38. 38)
    39. 39)
      • 13. Liu, T.-J.K., Markovic, D., Stojanovic, V., Alon, E.: ‘MEMS switches for low-power logic’. IEEE Spectrum, April 2012.
    40. 40)
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2014.0135
Loading

Related content

content/journals/10.1049/iet-cdt.2014.0135
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading