Algebra of switching networks

Algebra of switching networks

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Computers & Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.


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

Related content

This is a required field
Please enter a valid email address